目录

1、两数之和

 26、删除有序数组的重复项

 27、移除元素

35、搜索插入位置​

 53、最大子数组和

66、加一

88、合并两个有序数组

108、将有序数组转换为二叉搜索树

 118、杨辉三角（119类似）

121、买卖股票的最佳时机

136、只出现一次的数字

167、两数之和-输出有序数组

169、多数元素 

217、存在重复元素

219、存在重复元素

228、汇总区间

268、丢失的数字

283、移动零

303、区域和检索-数组不可变

349、两个数组的交集​

350、两个数组的交集2

414、第三大的数

448、找到所有数组中消失的数字

453、最小操作次数使数组元素相等

455、分发饼干

463、岛屿的周长

485、最大连续1的个数

 495、提莫攻击

496、下一个更大元素

500、键盘行

---

1、两数之和

class Solution(object): def twoSum(self, nums, target): """ :type nums: List[int] :type target: int :rtype: List[int] """ cnt = len(nums) for i in range(cnt): for j in range(i+1,cnt): add1 = nums[i]+nums[j] if add1==target: return [i,j] else: continue

 26、删除有序数组的重复项

class Solution(object): def removeDuplicates(self, nums): """ :type nums: List[int] :rtype: int """ i, j = 0, 0 if len(nums) == 1: j += 1 else: while i < len(nums): if i != (len(nums) - 1): # i不是最后一个 if nums[i] != nums[i + 1]: # 且与后一个元素不相同 nums[j] = nums[i] # 在j处记录i j = j + 1 # j到下一个记录点 i = i + 1 # 遍历下一个i else: # i是最后一个 if j != 0: # j不为0（前面有元素） if nums[i] != nums[j - 1]:# 与前一个已经记录的元素不相同 nums[j] = nums[i] # 记录i j = j + 1 # j加一 else: nums[j] = nums[i] j = j + 1 i = i + 1 return j

 27、移除元素

class Solution(object): def removeElement(self, nums, val): """ :type nums: List[int] :type val: int :rtype: int """ i = 0 while i < len(nums): if nums[i] == val: del nums[i] else: i += 1 return len(nums)

35、搜索插入位置

class Solution(object): def searchInsert(self, nums, target): """ :type nums: List[int] :type target: int :rtype: int """ n = len(nums) for i in range(n): if nums[i] >= target: j = i break elif nums[i] < target and i == n-1: j = i+1 break return j

 53、最大子数组和

class Solution(object): def maxSubArray(self, nums): Max=[] for i in range(len(nums)): if not Max: Max.append(nums[0]) else: Max.append(max(nums[i],nums[i]+Max[i-1])) return max(Max)

 利用动态规划思想，设置Max存储以nums[i]结尾的最大子数组和。例如，Max[5]存储的是以nums[5]为结尾的最大子数组和。第一个循环，Max为空，Max[0]=nums[0]；第二个循环，Max[0]=max(nums[i],nums[i]+Max[i-1])，当nums[i]比较大时不要前面的子数组只保留nums[i]为最大子数组和，当nums[i]+Max[i-1]比较大时保留前面的子数组和并加上nums[i]为最大子数组和。

66、加一

class Solution(object): def plusOne(self, digits): """ :type digits: List[int] :rtype: List[int] """ n = len(digits) num = 0 for i in range(n): num += digits[i] * (10 ** (n - i - 1)) # 幂函数是** num += 1 if num // (10 ** n): n += 1 digits = [0 for _ in range(n)] digits[0] = 1 for i in range(1, n): digits[i] = 0 else: for i in range(n): digits[i] = num // (10 ** (n - i - 1)) num -= digits[i] * (10 ** (n - i - 1)) return digits

幂函数是**，另外列表需要先初始化才能赋值。

88、合并两个有序数组

class Solution(object): def merge(self, nums1, m, nums2, n): """ :type nums1: List[int] :type m: int :type nums2: List[int] :type n: int :rtype: None Do not return anything, modify nums1 in-place instead. """ for i in range(len(nums2)): nums1[i+m]=nums2[i] nums1.sort() #直接调用python内置函数了

108、将有序数组转换为二叉搜索树

# Definition for a binary tree node.# class TreeNode(object):# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclass Solution(object): def sortedArrayToBST(self, nums): """ :type nums: List[int] :rtype: TreeNode """ def buildtree(left, right): if left > right: # 左指针比右指针大（只有两个数的情况下，mid=0，buildtree(left,mid-1）） return None if left == right: return TreeNode(nums[left]) else: mid = (left+right) // 2 return TreeNode(nums[mid], buildtree(left, mid-1), buildtree(mid+1, right)) return buildtree(0, len(nums)-1)

 118、杨辉三角（119类似）

class Solution(object): def generate(self, numRows): """ :type numRows: int :rtype: List[List[int]] """ if numRows == 1: return [[1]] else: li = [[1]] li_tmp = [1] for i in range(1, numRows): # 每行 head = int((i + 1) * i / 2) # 每行起始元素的编号 tmp = [0 for _ in range(i + 1)] # 存储该行元素 for j in range(i+1): # 每行的每个元素 number = head+j #该元素编号 if j == 0 or j == i: tmp[j] = 1 else: tmp[j] = li_tmp[number-i-1]+li_tmp[number-i] li.append(tmp) li_tmp.extend(tmp) return li

121、买卖股票的最佳时机

class Solution(object): def maxProfit(self, prices): """ :type prices: List[int] :rtype: int """ n = len(prices) if n < 2: return 0 profit = 0 dp = [0 for _ in range(n)] dp[0] = prices[0] for i in range(1, n): dp[i] = min(dp[i-1], prices[i]) # 存储第i天卖出时的最低买入价 profit = max(profit, prices[i]-dp[i]) return profit

根据动态规划思想，第i天卖出的最高利润profit：prices[i] - min(prices[0:i])

第i天的最高利润profit只需要知道前i天的prices最低点就可以算出来了，而第i天以前（包括第i天）的最低点和i-1天的最低点有关，由此推导出动态方程：

dp[i] = min(dp[i-1],prices[i])
dp[0]=prices[0]

dp[i]存储假如在第i天卖出股票前(i-1)天的最低买入价。

136、只出现一次的数字

class Solution(object): def singleNumber(self, nums): """ :type nums: List[int] :rtype: int """ n = len(nums) a = 0 for i in range(n): a ^= nums[i] return a

 采用位运算技巧，任何数与0异或结果为0，与自己异或结果为0

167、两数之和-输出有序数组

# 一种超出时间限制的解法class Solution(object): def twoSum(self, numbers, target): """ :type numbers: List[int] :type target: int :rtype: List[int] """ n = len(numbers) for i in range(n): tmp = target - numbers[i] if numbers[i+1: n].count(tmp): return [i+1, numbers.index(tmp, i+1, n)+1]

li.count(a)：返回列表li中元素a出现的次数，由于li.index()方法在检索不到元素时会报错，可以利用li.count()先判断元素是否存在；

li.index(a, 1, 100)：返回在li[1:100]范围内元素a第一次出现的下标

class Solution(object): def twoSum(self, numbers, target): """ :type numbers: List[int] :type target: int :rtype: List[int] """ n = len(numbers) left = 0 right = n-1 while 1: if numbers[left] + numbers[right] > target: right -= 1 elif numbers[left] + numbers[right] < target: left += 1 else: return [left+1, right+1]

双指针方法：left指针从左向右遍历，right指针从右向左遍历，和>target则right向左移动，

169、多数元素 

class Solution(object): def majorityElement(self, nums): """ :type nums: List[int] :rtype: int """ n = len(nums) nums.sort() return nums[n//2]

 先对数组进行排序，出现在n/2位置上的一定是众数。

217、存在重复元素

class Solution(object): def containsDuplicate(self, nums): """ :type nums: List[int] :rtype: bool """ n = len(nums) nums.sort() for i in range(n-1): if nums[i] == nums[i+1]: return True return False

 借用上一题的思想，先排序再比较相邻元素是否相同。

219、存在重复元素

# 一种超出时间限制的解法class Solution(object): def containsNearbyDuplicate(self, nums, k): """ :type nums: List[int] :type k: int :rtype: bool """ n = len(nums) for i in range(n): if nums[i+1:min(i+k+1, n)].count(nums[i]): # 在范围内存在重复元素 return True return False

li.count(a)：返回列表li中a元素的数量；

li.index(a, 1, 100)：返回列表1~100范围内首次出现a元素的下标，当元素a不存在时会报错，最好先用li.count()方法判断一下。

class Solution(object): def containsNearbyDuplicate(self, nums, k): """ :type nums: List[int] :type k: int :rtype: bool """ li = [] n = len(nums) for i in range(n): if i > k: del li[0] if nums[i] in li: return True li.append(nums[i]) return False

利用滑动窗口的思想，用长度为k的滑动窗口在数组上从头到尾遍历，当滑动窗口内有重复数字时return true（虽然通过了，耗时依旧很长）

class Solution(object): def containsNearbyDuplicate(self, nums, k): """ :type nums: List[int] :type k: int :rtype: bool """ s = set() for i, num in enumerate(nums): if i > k: s.remove(nums[i - k - 1]) if num in s: return True s.add(num) return False

与上一种方法同样利用滑动窗口的思想，但是利用集合速度更快（因为不需要前后次序信息，只需要有or没有，因此可以利用集合）

228、汇总区间

# 一种很笨蛋的方法（列举所有情况逐一讨论）class Solution(object): def summaryRanges(self, nums): """ :type nums: List[int] :rtype: List[str] """ n = len(nums) li = [] if not nums: return [] head = nums[0] tail = head head_v = 0 tail_v = 0 while tail_v <= n-1: if tail_v != n-1 and nums[tail_v + 1] == tail + 1: tail_v += 1 tail = nums[tail_v] elif tail_v != n-1 and nums[tail_v + 1] != tail + 1: if head_v == tail_v: li.append("%s" % head) else: li.append("%s->%s" % (head, tail)) head_v = tail_v + 1 tail_v = head_v head = nums[head_v] tail = nums[tail_v] else: if head_v == tail_v: li.append("%s" % head) else: li.append("%s->%s" % (head, tail)) tail_v += 1 return li

# 一种简单些的写法class Solution(object): def summaryRanges(self, nums): """ :type nums: List[int] :rtype: List[str] """ nums.append(2 ** 32) ret, start = [], 0 for i in range(1, len(nums)): if nums[i] - nums[i - 1] > 1: # nums[i]不在连续区间内 if i - 1 == start: # 该区间内只有一个元素 ret.append(str(nums[start])) else: # 该区间内有多个元素 ret.append(f"{nums[start]}->{nums[i - 1]}") start = i # 设置下一个区间起始点start = nums[i] return ret

这种题和单调栈有一个共同的思路就是添加哨兵节点。nums的末尾append一个2 ** 32，可以减少循环后的再次判断场景。（如果不在nums末尾添加这个数字，i只循环判断到倒数第二个数，最后一个数的判断还需要写另外的判断语句很麻烦。）

另外字符串的写法li.append("%s->%s" % (head, tail))可以转换成li.append(f"{head}->{tail}")，测试了一下需要在python3环境下使用。

268、丢失的数字

class Solution(object): def missingNumber(self, nums): """ :type nums: List[int] :rtype: int """ b = max(nums) flag = 1 for val in range(b + 1): if val not in nums: return val flag = 0 if flag == 0: return len(nums)

283、移动零

class Solution(object): def moveZeroes(self, nums): """ :type nums: List[int] :rtype: None Do not return anything, modify nums in-place instead. """ count0 = nums.count(0) while 0 in nums: nums.remove(0) for i in range(count0): nums.append(0) return nums

删除列表中所有指定元素时，可以用循环while element in list:进行判断，当元素还在列表中时，继续使用list.remove(element)执行删除操作。

303、区域和检索-数组不可变

class NumArray(object): def __init__(self, nums): """ :type nums: List[int] """ self.sums = [0] for num in nums: self.sums.append(self.sums[-1] + num) def sumRange(self, left, right): """ :type left: int :type right: int :rtype: int """ _sums = self.sums return _sums[right+1] - _sums[left]

349、两个数组的交集

class Solution(object): def intersection(self, nums1, nums2): """ :type nums1: List[int] :type nums2: List[int] :rtype: List[int] """ li = [] for val in nums1: if val in nums2: if val not in li: li.append(val) return li

350、两个数组的交集2

class Solution(object): def intersect(self, nums1, nums2): """ :type nums1: List[int] :type nums2: List[int] :rtype: List[int] """ li = [] for val in nums1: if val in nums2: li.append(val) nums2.remove(val) return li

414、第三大的数

class Solution(object): def thirdMax(self, nums): """ :type nums: List[int] :rtype: int """ nums.sort(reverse=True) li = sorted(set(nums), key=nums.index) if len(li) < 3: return max(li) return li[2]

nums.sort(reverse=True) 列表nums中的元素由大到小排列；

li = sorted(set(nums), key=nums.index) 将列表nums转换为集合消除重复元素，但是这种方法很慢，可以直接使用内置函数set转换。

class Solution(object): def thirdMax(self, nums): """ :type nums: List[int] :rtype: int """ nums = list(set(nums)) nums.sort(reverse=True) if len(nums) < 3: return max(nums) return nums[2]

注意使用list(set())这种方法生成的集合是由小到大排序后的，因此之后重新排序。

如果想要实现set不改变原列表元素顺序，使用sort(key=a.index)，其中a为原列表。

448、找到所有数组中消失的数字

# 超出时间限制class Solution(object): def findDisappearedNumbers(self, nums): """ :type nums: List[int] :rtype: List[int] """ n = len(nums) li = [] for val in range(1, n+1): if val not in nums: li.append(val) return li

 利用哈希表思想（妙啊）：

class Solution(object): def findDisappearedNumbers(self, nums): """ :type nums: List[int] :rtype: List[int] """ n = len(nums) for val in nums: i = (val - 1) % n nums[i] += n ret = [i + 1 for i, num in enumerate(nums) if num <= n] return ret

遍历数组nums中的元素，当[1,n]中的元素全都存在时，nums[i] = i+1。每遍历到一个元素，就使nums中元素值对应位置的元素+n（比如第一个元素值为2，使nums[1]的值+n），遍历完成后值没有超过n的元素对应位置即为缺少的元素。

453、最小操作次数使数组元素相等

class Solution(object): def minMoves(self, nums): """ :type nums: List[int] :rtype: int """ n = len(nums) a = min(nums) count = 0 for i in range(n): tmp = nums[i] - a count += tmp return count

同时使n-1个数+1相当于每次给一个数-1，因此遍历数组获取每个数与最小值的差值，差值的和即为运算次数。

455、分发饼干

class Solution(object): def findContentChildren(self, g, s): """ :type g: List[int] :type s: List[int] :rtype: int """ n_children = len(g) n_biscuits = len(s) g.sort() s.sort() i, j = 0, 0 count = 0 while i < n_children and j < n_biscuits: if s[j] >= g[i]: count += 1 i += 1 j += 1 else: j += 1 return count

463、岛屿的周长

class Solution(object): def islandPerimeter(self, grid): """ :type grid: List[List[int]] :rtype: int """ n_row = len(grid) n_col = len(grid[0]) count = 0 for i in range(n_row): for j in range(n_col): if grid[i][j]: count += 4 if i > 0: if grid[i-1][j]: # 上 count -= 1 if i < n_row-1: if grid[i+1][j]: # 下 count -= 1 if j > 0: if grid[i][j-1]: # 左 count -= 1 if j < n_col-1: if grid[i][j+1]: # 右 count -= 1 return count

485、最大连续1的个数

class Solution(object): def findMaxConsecutiveOnes(self, nums): """ :type nums: List[int] :rtype: int """ n = len(nums) count = 0 i = 0 while i < n: if nums[i] == 1: k = 0 tmp = 0 while i+k < n and nums[i+k] == 1: tmp += 1 k += 1 count = max(count, tmp) i = i+k+1 else: i += 1 return count

 495、提莫攻击

class Solution(object): def findPoisonedDuration(self, timeSeries, duration): """ :type timeSeries: List[int] :type duration: int :rtype: int """ n = len(timeSeries) count = duration for i in range(n-1): if timeSeries[i+1]-timeSeries[i] < duration: count += timeSeries[i+1]-timeSeries[i] else: count += duration return count

当两次中毒时间差=duration时，中毒时间累计为duration。

496、下一个更大元素

class Solution(object): def nextGreaterElement(self, nums1, nums2): """ :type nums1: List[int] :type nums2: List[int] :rtype: List[int] """ n2 = len(nums2) li = [] for val in nums1: flag = 0 for i in range(nums2.index(val)+1, n2): if nums2[i] > val: li.append(nums2[i]) flag = 1 break if flag == 0: li.append(-1) return li

500、键盘行

class Solution: def findWords(self, words): LINES = [set("qwertyuiop"), set("asdfghjkl"), set("zxcvbnm")] ans = [] for word in words: flag = 0 for val in LINES: if set(word.lower()).issubset(val): # word.lower() # 转成小写 # set(word.lower()) # 将单词字符串转换为集合 # .issubset(val) # 判断是否为子集 flag = 1 if flag: ans.append(word) return ans