Leetcode Big Manipulation 解题报告

本文主要是介绍Leetcode Big Manipulation 解题报告，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

第一部分

leetcode136. Single Number

中等难度

题意，给一个整数数组，数组中除了一个元素只有一个，其余元素都有两个，求这个只出现一次的元素。

要求时间复杂度为O(n)，空间复杂度为O(1)

思路：利用异或来解决问题，a^a=0,0^b=b

解答：

 class Solution(object):def singleNumber(self, nums):""":type nums: List[int]:rtype: int"""ret=0for i in nums:ret=ret^ireturn ret 

leetcode137. Single Number II

中等难度

题意，给一个整数数组，数组中除了一个元素只出现一次，其余元素都出现三次，求这个只出现一次的元素

要求时间复杂度为O(n),空间复杂度为O(1)

思路：用flag_i来标记当前出现i次的元素，规则如下：

• 先更新flag2，flag2=flag2^(flag1&i)
• 再更新flag1, flag1=flag1^i
• 计算flag3, flag3=flag2&flag1
• 计算flag1=flag1^flag3
• 计算flag2=flag2^flag3（因为到达flag3的元素，必然在flag1,flag2中出现，因此要把它们剔除）

class Solution(object):def singleNumber(self, nums):""":type nums: List[int]:rtype: int"""flag1=0;flag2=0;flag3=0for i in nums:flag2 ^=(flag1 & i)flag1 ^= iflag3 =(flag2 & flag1)flag1 ^=flag3flag2 ^=flag3return flag1

leetcode260. Single Number III

中等难度

题意，给一个整数数组，数组中除了两个元素只出现一次，其余元素都出现两次，求这个只出现一次的两个元素

*思路：*a^a=0,0^b=1，因为这两个元素不是同一个值，则x^y!=0，必有一位为1->flag，将数组拆分成两部分，i&flag=0 和 i&flag=1，然后各自求异或

class Solution(object):def singleNumber(self, nums):""":type nums: List[int]:rtype: List[int]"""result=0for i in nums:result=result^iflag=result&(~(result-1))ans=[0,0]for i in nums:if i&flag:ans[1]=ans[1]^ielse:ans[0]=ans[0]^ireturn ans

第二部分

leetcode371. Sum of Two Integers

简单难度

题意，不能用+、-符号，计算两个数字的和

思路：

二进制计算为：

0 + 0= 0

0 + 1= 1

1 + 0= 1

1 + 1= 0

即异或操作(^)

进位表示为:

010

011

——

(010&011)<<1=010<<1＝100

public class Solution {  public int getSum(int a, int b) {  int unit = a ^ b;  int carry_bit = a & b;  while(carry_bit != 0) {  int temp_a = unit;  int temp_b = carry_bit << 1;  unit = temp_a ^ temp_b;  carry_bit = temp_a & temp_b;  }  return unit;  }  
}  

python因为有个时间限制，所以又弄了一个版本

class Solution(object):def signfunc(self,a):if a>0:return 1,aelif a<0:return 2,-aelse:return 0,0def calsign(self, a, b):flagmatrix=[[0,1,-1],[1,1,0],[-1,0,-1]]flaga,a1=self.signfunc(a)flagb,b1=self.signfunc(b)if a1>b1:flagmatrix[2][1]=-1flagmatrix[1][2]=1else:flagmatrix[2][1]=1flagmatrix[1][2]=-1return flagmatrix[flaga][flagb],a1,b1def getSum(self, a, b):""":type a: int:type b: int:rtype: int"""if a*b>=0:flag,a,b=self.calsign(a,b)while(b):carry=a&ba=a^bb=carry<<1return flag*aelse:tmp=~(-(abs(a)^abs(b)))flag,a,b=self.calsign(a,b)if a==b:return 0ans=[]while(tmp):ans.append('%s'%((tmp%2)^1))tmp=tmp/2ans.reverse()return flag*int(''.join(ans),2)

leetcode190. Reverse Bits

简单难度

题意，32bit长的整数翻转

class Solution(object):def reverseBits(self, n):""":type n: int:rtype: int"""ret=0flag=0while(flag<32): ret=(ret<<1)+(n&1)n=n>>1flag=flag+1return ret

注意32bit

leetcode191. Number of 1 Bits

简单难度

题意，计算整数的汉明距离

class Solution(object):def hammingWeight(self, n):""":type n: int:rtype: int"""count=0while(n):count=count+(n&1)n=n>>1return count

leetcode338. Counting Bits

中等难度

题意，计算从0到num的每一个元素的汉明距离

class Solution(object):def countBits(self, num):""":type num: int:rtype: List[int]"""ret=[0 for i in range(num+1)]for i in range(1,num+1):ret[i]=ret[i&(i-1)]+1return ret

leetcode231. Power of Two

简单难度，判断数字是否是2的幂
思路: 判断汉明距离是否为1

class Solution(object):def isPowerOfTwo(self, n):""":type n: int:rtype: bool"""return (n!=0 and n&(n-1)==0)

或者

class Solution(object):def isPowerOfTwo(self, n):""":type n: int:rtype: bool"""count=0while(n):count=count+(n&1)n=n>>1return count==1

leetcode342. Power of Four

简单难度，判断数字是否是4的幂
思路: 判断汉明距离是否为1,且1是否在奇数位上

class Solution(object):def isPowerOfFour(self, num):""":type num: int:rtype: bool"""return num>0 and (num &(num-1))==0 and (num & 0x55555555) == num

leetcode318. Maximum Product of Word Lengths

中等难度
给定单词数组，返回不相交的两个单词的长度之积的最大值
思路：将单词进行编码
‘a’->0
‘b’ ->10
x&y==0说明x和y不相交

class Solution(object):def maxProduct(self, words):""":type words: List[str]:rtype: int"""ans=[]for i in words:tmp=0for j in set(i):tmp=tmp+(1<<(ord(j)-ord('a')))ans.append(tmp)MAX_P=0for i in range(len(words)):for j in range(i,len(words)):if ans[i] & ans[j]==0:MAX_P=max(MAX_P,len(words[i])*len(words[j]))return int(MAX_P)

leetcode201. Bitwise AND of Numbers Range

中等难度
计算[m,n]中每个整数相与的结果

class Solution(object):def rangeBitwiseAnd(self, m, n):""":type m: int:type n: int:rtype: int"""count=0while(m!=n):m=m>>1n=n>>1count=count+1return m<<count

leetcode78. Subsets

中等难度
给定一个集合，求子集
思路： 状态压缩法

class Solution(object):def subsets(self, nums):""":type nums: List[int]:rtype: List[List[int]]"""ret=[]if not len(nums):return retfor i in range(2**(len(nums))):tmp=[]state=list('{:b}'.format(i))state=['0']*(len(nums)-len(state))+statefor j in range(len(state)):if state[j]=='1':tmp.append(nums[j])ret.append(tmp)return ret

这篇关于Leetcode Big Manipulation 解题报告的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---