力扣初级算法（Python）（一）：https://developer.aliyun.com/article/1538127
6 排序和搜索
6.1 合并两个有序数组
class Solution: def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None: """ Do not return anything, modify nums1 in-place instead. """ # 两个中存在空数组的时，直接返回 if m == 0: nums1[:] = nums2[:] return if n == 0: return index1,index2 = 0,0 t = [] while index1<m and index2<n: if nums1[index1] <= nums2[index2]: t.append(nums1[index1]) index1 += 1 else: t.append(nums2[index2]) index2 += 1 if index1 < m: t += nums1[index1:m] else: t += nums2[index2:n] nums1[:] = t[:]
6.2 第一个错误的版本
二分搜索
# The isBadVersion API is already defined for you. # @param version, an integer # @return an integer # def isBadVersion(version): class Solution: def firstBadVersion(self, n): """ :type n: int :rtype: int """ mid = n//2 left = 0 right = n while not self.isFirstBad(mid): if isBadVersion(mid): right = mid-1 else: left = mid+1 mid = (left+right)//2 return mid def isFirstBad(self,n): if isBadVersion(n) and not isBadVersion(n-1): return True else: return False
7 动态规划
7.1爬楼梯
直接用递归会在n较大时超时。
class Solution: def climbStairs(self, n: int) -> int: if n == 1 or n == 2: return n ans = [0,1,2] i = 3 while i <= n: ans.append(ans[i-1]+ans[i-2]) i +=1 return ans[n]
7.2 买卖股票的最佳时机
只能一次买卖。
所以当前能获得的最大利润为：当前卖出价-之前最低价(price-min_price)。
只要在遍历中更新每一天可获得的最大利润。
class Solution: def maxProfit(self, prices: List[int]) -> int: r = 0 min_price = float('inf') # float('inf')表示正无穷 for price in prices: min_price = min(min_price, price) # 截止到当前的最低价（买入价） r = max(r, price - min_price) # 截止到目前的最高利润 return r
7.3 最大子序和
@yichendai
dp[i] 表示终点在i的子序列的最佳子序和，这样就可以建立其dp[i]和dp[i-1]的关系。
dp[i] = max(dp[i - 1], 0) + nums[i]
class Solution: def maxSubArray(self, nums: List[int]) -> int: length = len(nums) dp = [0 for i in range(length)] max_r = nums[0] for i in range(length): dp[i] = max(dp[i - 1], 0) + nums[i] max_r = max(max_r,dp[i]) return max_r
7.4 打家劫舍
核心就是决定在第i个房间偷还是不偷，偷就是dp[i-2] + nums[2],不偷就是dp[i-1]，两者取max。
class Solution: def rob(self, nums: List[int]) -> int: if len(nums) <=0 : return 0 if len(nums) == 1: return nums[0] if len(nums) == 2: return max(nums[0],nums[1]) dp = [0 for i in nums] dp[0] = nums[0] dp[1] = max(nums[1],dp[0]) i = 2 while i < len(nums) : dp[i] = max(dp[i-2]+nums[i],dp[i-1]) i += 1 length = len(nums) return dp[length-1]
空间优化：实际上每次只会用到dp[i-2]和dp[i-1] ，可以用两个变量代替数组。
@NeilJi
class Solution: def rob(self, nums: List[int]) -> int: if len(nums) <=0 : return 0 if len(nums) == 1: return nums[0] if len(nums) == 2: return max(nums[0],nums[1]) pre1 = nums[0] pre2 = max(nums[0],nums[1]) max_r = 0 i = 2 while i < len(nums) : max_r = max(pre1+nums[i],pre2) (pre1,pre2) = (pre2,max_r) i += 1 return max_r
8 设计问题
8.1 打乱数
主要问题是打乱数组的实现，可以使用随机下标交换
import random class Solution: def __init__(self, nums: List[int]): self.length = len(nums) self.reset_nums = nums[:] self.shuffle_nums = nums[:] def reset(self) -> List[int]: return self.reset_nums def shuffle(self) -> List[int]: i = 0 while i < self.length: t = random.randint(1,self.length-1) self.shuffle_nums[i],self.shuffle_nums[t] = self.shuffle_nums[t],self.shuffle_nums[i] i += 1 return self.shuffle_nums # Your Solution object will be instantiated and called as such: # obj = Solution(nums) # param_1 = obj.reset() # param_2 = obj.shuffle()
8.2 最小栈
要求在常数时间内检索到最小元素，而栈的push和pop操作都可能改变最小元素。
考虑用一个栈来保存最小元素。
class MinStack: def __init__(self): self.min_v = [] self.stack = [] def push(self, val: int) -> None: self.stack.append(val) if len(self.min_v) == 0 or val <= self.min_v[len(self.min_v)-1]: self.min_v.append(val) def pop(self) -> None: t = self.stack.pop() if t == self.min_v[len(self.min_v)-1]: self.min_v.pop() def top(self) -> int: return self.stack[len(self.stack)-1] def getMin(self) -> int: return self.min_v[len(self.min_v)-1] # Your MinStack object will be instantiated and called as such: # obj = MinStack() # obj.push(val) # obj.pop() # param_3 = obj.top() # param_4 = obj.getMin()
9 数学
找规律题
9.1 Fizz Buzz
if else练习
class Solution: def fizzBuzz(self, n: int) -> List[str]: list = [] for i in range(1,n+1): if i % 3 == 0 and i % 5 == 0: list.append("FizzBuzz") elif i % 3 == 0: list.append("Fizz") elif i % 5 == 0: list.append("Buzz") else: list.append(str(i)) return list
9.2 计数质数
爱氏筛求质数
class Solution: def countPrimes(self, n: int) -> int: isPrimes = [True for _ in range(n)] count = 0 for i in range(2,n): if isPrimes[i]: count += 1 #埃氏筛，i的倍数不是素数 for j in range(2*i,n,i): isPrimes[j] = False return count
9.3 3的幂
class Solution: def isPowerOfThree(self, n: int) -> bool: t = 1 while t < n : t *= 3 return True if t == n else False
9.4 罗马数字转整数
可以用字典做
class Solution: def romanToInt(self, s: str) -> int: store = [1000,900,500,400,100,90,50,40,10,9,5,4,1] strs = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"] maps = dict(zip(strs,store)) result = 0 i = 0 while i < len(s): if i+1 < len(s) and s[i:i+2] in maps: result += maps.get(s[i:i+2]) i += 2 else: result += maps.get(s[i:i+1]) i += 1 return result
10 其它
前3题和二进制相关，用到位运算符。
10.1 位1的个数
class Solution: def hammingWeight(self, n: int) -> int: # 第一种解法 使用python特性 bin(3) = ob11 #return bin(n).count("1") # 第二种使用 位运算 特性 & 与预算符号， >> 右进位预算符号 res = 0 while n: res += n & 1 # res += （n & 1） 11&1 =1 , 10&1=0 比较最后一位相同1，不同0 n >>= 1 # 右滑动进位 return res
10.2 汉明距离
异或后用10.1求1个数
class Solution: def hammingDistance(self, x: int, y: int) -> int: #return bin(x^y).count("1") cnt = 0 z = x^y while z: cnt += z & 1 z >>= 1 return cnt
10.3 颠倒二进制位
class Solution: def reverseBits(self, n: int) -> int: res = 0 for i in range(32): res <<= 1 res += (n & 1) n >>= 1 return res
10.4 杨辉三角
找规律
class Solution: def generate(self, numRows: int) -> List[List[int]]: res = [[]for _ in range(numRows)] res[0] = [1] for i in range(1,numRows): res[i].append(1) for j in range(0,len(res[i-1])-1): res[i].append(res[i-1][j] + res[i-1][j+1]) res[i].append(1) return res
10.5 有效的括号
用栈匹配括号
class Solution: def isValid(self, s: str) -> bool: stack = [] for i in range(0,len(s)): c = s[i] if c == '(' or c =='[' or c =='{': stack.append(c) else: if len(stack) == 0: return False left = stack.pop() if (c == ')' and left == '(') : continue elif (c == ']' and left == '['): continue elif (c == '}' and left == '{'): continue else: return False if len(stack) == 0: return True else: return False
10.6 缺失数字
class Solution: def missingNumber(self, nums: List[int]) -> int: length = len(nums) jg = [False for _ in range(length+1)] for num in nums: jg[num] = True return jg.index(False)
在评论区看到的求和及异或方法。
求和：
class Solution: def missingNumber(self, nums: List[int]) -> int: length = len(nums) sum_n = (length+1)*length//2 sum_nums = sum(nums) return sum_n - sum_nums
a^b^a = a^a^b = b, b和a异或两次还等于b。
在下面的循环中，最终nums[i]中存在的数都会异或两次消掉，得到nums[i]中缺失的数。
class Solution: def missingNumber(self, nums: List[int]) -> int: length = len(nums) xor = 0 for i in range(length): xor ^= nums[i] ^ (i+1) return xor
