13.Number of 1 Bits
Write a function that takes an unsigned integer and returns the number of ’1’ bits it has (also known as the Hamming weight).
For example, the 32-bit integer ’11’ has binary representation 00000000000000000000000000001011, so the function should return 3.
Analysis
返回位为1的数量，so easy
看了下面这个链接里五花八门的方法感觉这个世界真大
http://www.cnblogs.com/graphics/archive/2010/06/21/1752421.html
Solution-C/C++
我的普通解法
int hammingWeight(uint32_t n)
{
int i=0,sum=0;
for(i=0;i<32;i++)
sum=sum+((n>>i)&1);
return sum;
}
其实看给的标准函数名是hamming 就应该想到这个是哈明码，用来纠错的，或者说是奇偶校验码
hamming算法
算法思路是什么呢？
其实就是每两个位相加，将之前的一个32位的数，转换为用16位来表示的数，然后把16位的数再次压缩为8位，再压缩到16位，那么这个时候就已经计算出来了32位所具有的1的个数
0x55555555则是用010101为间隔，将32位的中的每两位的1的个数 用两位来表示，而每两位最多具有2个1 所以用两位来表示足够
0x33333333则是用00110011为间隔，将上面的两位表示的1的个数再通过两两组合合并成用四位表示的二进制。
之后都是以此类推最终得到最后的解
例：
如果n=0xABCDEFAA（1010 1011 1100 1101 1110 1111 1010 1010 ）
按照算法思路先要把每两位的1的个数统计出来，并且用二进制表示
那么就需要得到这样的结果
原数二进制 1010 1011 1100 1101 1110 1111 1010 1010
2位压缩 0101 0110 1000 1001 1001 1010 0101 0101
4位压缩 0010 0011 0010 0011 0011 0100 0010 0010
8位压缩 0101 0101 0111 0100
16位压缩 1010 1011
32位压缩 10101 = 21
这样就得到了最后的结果21，剩下的问题就集中在于如何把这样的想法用算法实现了
首先看每两位计算1的个数要怎么做，两位，那就各取一位，然后相加不就可以了吗？
取位则用&，而每次只取两位中的1位 那么就可以用 01和10分别取高低位
但是这样取来的高位还是在高位上，低位还是在低位上
我们需要他们在低位的地方相加才行，那要怎么弄？
自然选择用01来获取低位，之后将原数右移1位，丢失了一位低位（但低位已经取过了所以没关系）
而原来的高位顺移到了以前的低位的位置上，那么就能得到原来高位的0/1了，然后将二者相加即可得到用两位表示的两位的1的个数
之后就是将上面的两位表示的两位的1的个数两两相加，从而得到用四位表示的四位的1的个数,由于是用四位表示了
可以从中分开分成高两位和低两位 同样的要面对获取高两位和低两位的问题
那么扩展之前的 使用0011来获取，移位时向右移动2位便可以获得低位/高位
以此类推就能得到 8位的时候应该用 00001111 移动4位 16位的时候是 0000 0000 1111 1111 移动8位
最后则是32位的压缩 0000 0000 0000 0000 1111 1111 1111 1111 移动16位
由于原数自身是32位的那么 所得到的结果32位的压缩 通过内存编译解释出来的数（1的个数的二进制表示）
自然也就是最后的结果1的个数的 如果原数是64位的 那么最后还需要再进一步 64位的压缩 然后才能得到结果
int hammingWeight(uint32_t n)
{
int count = n;
int a = 0x55555555; //010101010101010101010101010101 //用于相邻的两位相加
int b = 0x33333333; //用于相邻的四位相加
int c = 0x0f0f0f0f;
int d = 0x00ff00ff;
int e = 0x0000ffff;
count = (count & a) + ((count>>1) & a);
count = (count & b) +((count>>2) & b);
count = (count & c) + ((count>>4) & c);
count = (count & d) + ((count>>8) & d);
count = (count & e) + ((count>>16) & e);
return count;
}
HAKMEM算法
HAKMEM算法和上面的也有类似的地方 他是使用3位为一组来做的 只是最后需要对63来进行求余 得到的余数就是结果了，但是算法原理跟上面的根本不同！！详见此blog的分析，二进制的数的本质
http://blog.csdn.net/msquare/article/details/4536388
这里0开头的是八进制
int hammingWeight(uint32_t n)
{
unsigned x;
x = (n >> 1) & 033333333333;
n = n - x;
x = (x >> 1) & 033333333333;
n = n - x;
n = (n + (n >> 3)) & 030707070707;
n = n%63;
return n;
}
Solution-Python
class Solution(object):
def hammingWeight(self, n):
"""
:type n: int
:rtype: int
"""
sum=0
for i in range(0,32):
sum=((n>>i)&1)+sum
return sum
14.Roman to Integer
Given a roman numeral, convert it to an integer.
Input is guaranteed to be within the range from 1 to 3999.
Analysis
把罗马数字转换为普通数字
首先得知道罗马数字的表示方法
罗马数字共有七个，即I(1)，V(5)，X(10)，L(50)，C(100)，D(500)，M(1000)。按照下面的规则可以表示任意正整数。
当小符号在大符合旁边时，左减右加，并且左减时不能跨级别 比如99应该=100-1=IC 但由于跨级别了需要用中间量补齐
那就等于 99=100-10+10-1=XCIX
I, 1 II, 2 III, 3 IV, 4 V, 5 VI, 6 VII, 7 VIII,8 IX, 9
X, 10 XI, 11 XII, 12 XIII, 13 XIV, 14 XV, 15 XVI, 16 XVII, 17 XVIII, 18
XIX, 19 XX, 20 XXI, 21 XXII, 22 XXIX, 29 XXX, 30 XXXIV, 34 XXXV, 35 XXXIX, 39
XL, 40 L, 50 LI, 51 LV, 55 LX, 60 LXV, 65 LXXX, 80 XC, 90 XCIII, 93
XCV, 95 XCVIII, 98 XCIX, 99 C, 100 CC, 200 CCC, 300 CD, 400 D, 500 DC,600
DCC, 700 DCCC, 800 CM, 900 CMXCIX,999 M, 1000 MC, 1100 MCD, 1400 MD, 1500 MDC, 1600
MDCLXVI, 1666 MDCCCLXXXVIII, 1888 MDCCCXCIX, 1899 MCM, 1900 MCMLXXVI, 1976
MCMLXXXIV, 1984 MCMXC, 1990 MM, 2000 MMMCMXCIX, 3999
这里需要把这个规则转换为数字
- 如果当前处理的字符对应的值和上一个字符一样，那么临时变量加上这个字符。比如III = 3
- 如果当前比前一个大，说明这一段的值应该是当前这个值减去前面记录下的临时变量中的值。比如IIV = 5 – 2
- 如果当前比前一个小，那么就可以先将临时变量的 值加到结果中，然后开始下一段记录。比如VI = 5 + 1
http://blog.unieagle.net/2012/10/18/leetcode%E9%A2%98%E7%9B%AE%EF%BC%9Aroman-to-integer/
（在他blog看到一个会动的球形tags，并且会根据鼠标移动轨迹来顺着移动好流弊的样子，有空研究一下，扒一个过来）
Solution-C/C++
int flagtoint(char f)
{
if(f=='I')
return 1;
if(f=='V')
return 5;
if(f=='X')
return 10;
if(f=='L')
return 50;
if(f=='C')
return 100;
if(f=='D')
return 500;
if(f=='M')
return 1000;
}
int romanToInt(char* s)
{
int sum=0;
int temp=flagtoint(*s);
while(*s)
{
s++;
if(flagtoint(*s)==temp)
{
sum+=temp;
temp=flagtoint(*s);
}
else if(flagtoint(*s)>temp)
{
sum-=temp;
temp=flagtoint(*s);
}
else
{
sum+=temp;
temp=flagtoint(*s);
}
}
return sum;
}
Solution-Python
class Solution(object):
def flagtoint(self, f):
"""
:type f: str
:rtype: int
"""
if f=='I':
return 1
if f=='V':
return 5
if f=='X':
return 10
if f=='L':
return 50
if f=='C':
return 100
if f=='D':
return 500
if f=='M':
return 1000
def romanToInt(self, s):
"""
:type s: str
:rtype: int
"""
sum=0
temp=self.flagtoint(s[0])
i=0
while i<len(s)-1:
i=i+1
if self.flagtoint(s[i])==temp:
sum=sum+temp
temp=self.flagtoint(s[i])
elif self.flagtoint(s[i])>temp:
sum=sum-temp
temp=self.flagtoint(s[i])
else:
sum=sum+temp
temp=self.flagtoint(s[i])
sum=sum+self.flagtoint(s[-1])
return sum
15.Reverse Linked List
Reverse a singly linked list.
click to show more hints.
Hint: A linked list can be reversed either iteratively or recursively. Could you implement both?
Analysis
用两种方法来翻转单链表，这个练得比较多，easy
首先需要明白 如何翻转
null head head->next -> first first.next -> second second.next -> third third.next -> forth....
^ ^ ^
|pre |cur |next 第一次的时候是这么指向的，要翻转就得改变箭头的方向变成下面这样的
null<-head.next head <-first.next first second second.next -> third third.next -> forth forth.next->....
^ ^ ^
|pre |cur |next 第二次是这样的 按照这个顺序循环就可以了
如果要用递归，也简单，只需要递归到最后一个next为空的情况下，开始进行翻转就可以了。
Solution-C/C++
递归
struct ListNode* reverseList(struct ListNode* head)
{
struct ListNode* temp;
if(head==NULL||head->next==NULL)
{
//开始翻转
return head;
}
else
{
//temp保存着老尾指针,最后返回作为新头指针.
temp=reverseList(head->next);
head->next->next=head;
head->next=NULL;
return temp;
}
}
迭代
struct ListNode* reverseList(struct ListNode* head)
{
struct ListNode*pre=NULL;
struct ListNode*cur=head;
if(!head||!head->next)
return head;
struct ListNode*temp=head->next;
struct ListNode*next=head->next;
while(1)
{
if(next->next!=NULL)
temp=next->next;
else
temp=NULL;
next->next=cur;
cur->next=pre;
pre=cur;
cur=next;
if(temp==NULL)
break;
else
next=temp;
}
return cur;
}
另外一份 逻辑上更简单明了一些
class Solution
{
public:
ListNode* reverseList(ListNode* head)
{
ListNode* pre=NULL;
ListNode* cur=head;
ListNode* nex=NULL;
while(cur)
{
nex=cur->next;
cur->next=pre;
pre=cur;
cur=nex;
}
return pre;
}
};
Solution-Python
递归
class Solution(object):
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if(head==None or head.next==None ):
return head
temp=self.reverseList(head.next)
head.next.next=head
head.next=None
return temp
迭代
class Solution(object):
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
pre=None
cur=head
if(head==None or head.next==None ):
return head
next=head.next
while(cur):
cur.next=pre
pre=cur
cur=next
if(next.next!=None):
next=next.next
else:
break
cur.next=pre
pre=cur
return cur
逻辑更好的
class Solution(object):
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
pre=None
cur=head
while(cur):
next=cur.next
cur.next=pre
pre=cur
cur=next
return pre
16.Remove Duplicates from Sorted List
Given a sorted linked list, delete all duplicates such that each element appear only once.
For example, Given 1->1->2, return 1->2. Given 1->1->2->3->3, return 1->2->3.
Analysis
删除有序链表中的重复部分，看起来也很简单啊。
Solution-C/C++
struct ListNode* deleteDuplicates(struct ListNode* head)
{
struct ListNode*cur=head;
struct ListNode*next;
if(head==NULL||head->next==NULL)
return head;
while(cur)
{
if(cur->next!=NULL)
next=cur->next;
else
break;
if(next->val==cur->val)
{
if(next->next!=NULL)
cur->next=next->next;
else
{cur->next=NULL;cur=NULL;}
continue;
}
cur=next;
}
return head;
}
2017年2月21日 13:04:12
上面代码有一个问题,用C写的话,这里删除对应的节点,是直接修改了指针,而原节点还真实存在,应该加上一个free释放了那个节点才是正确的
如果是其他语言,有内存回收机制的话应该是没问题的.
Solution-Python
python在上面c的基础上，把一些重复的逻辑去掉了，稍微简洁了一些
class Solution(object):
def deleteDuplicates(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if(head==None or head.next==None):
return head
cur=head
while (cur):
if cur.next==None:
break;
if cur.val==cur.next.val:
cur.next=cur.next.next
else:
cur=cur.next
return head
Quote
http://iask.sina.com.cn/b/1775817.html
http://blog.csdn.net/autumn20080101/article/details/7607148