数组--LeetCode(python)

乘积最大子序列

给定一个整数数组 nums ，找出一个序列中乘积最大的连续子序列（该序列至少包含一个数）。

示例 1:

输入: [2,3,-2,4] 输出: 6 解释: 子数组 [2,3] 有最大乘积 6。 示例 2:

输入: [-2,0,-1] 输出: 0 解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

解法： 第一时间想到的是动态规划，想找当前位置上的乘积最大值，但是发现正负号的问题，即前一个位置上乘积最小值乘以当前位置上的数，可能会变成乘积最大值。 也就是两个dp数组，简化一下存储空间的话，就是两个值：前一个位置上的乘积最大值和乘积最小值。 每有一个新的数字加入，最大值要么是当前最大值*新数，要么是当前最小值（负数）*新数（负数），要么是新值。

class Solution(object): def maxProduct(self, nums): """ :type nums: List[int] :rtype: int """ cur_min = cur_max = res = nums[0] for i in range(1, len(nums)): tmp_max = max(max(cur_min * nums[i], cur_max * nums[i]), nums[i]) tmp_min = min(min(cur_min * nums[i], cur_max * nums[i]), nums[i]) cur_min = tmp_min cur_max = tmp_max if cur_max > res: res = cur_max return res

魔术索引

魔术索引。 在数组A[0…n-1]中，有所谓的魔术索引，满足条件A[i] = i。给定一个有序整数数组，编写一种方法找出魔术索引，若有的话，在数组A中找出一个魔术索引，如果没有，则返回-1。若有多个魔术索引，返回索引值最小的一个。

示例1:

输入：nums = [0, 2, 3, 4, 5] 输出：0 说明: 0下标的元素为0 示例2:

输入：nums = [1, 1, 1] 输出：1 说明:

nums长度在[1, 1000000]之间 此题为原书中的 Follow-up，即数组中可能包含重复元素的版本

解法

暴力法：从左到右依次遍历即可，O(N)如果没有重复元素的话，可以直接按照二分法跳跃法：如果当前值大于i的话，就可以从当前位置继续遍历 class Solution(object): def findMagicIndex(self, nums): """ :type nums: List[int] :rtype: int """ if not nums: return -1 i = 0 while i < len(nums): if nums[i] > i: i = nums[i] elif nums[i] == i: return i else: i += 1 return -1

旋转数组

给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。

示例 1:

输入: [1,2,3,4,5,6,7] 和 k = 3 输出: [5,6,7,1,2,3,4] 解释: 向右旋转 1 步: [7,1,2,3,4,5,6] 向右旋转 2 步: [6,7,1,2,3,4,5] 向右旋转 3 步: [5,6,7,1,2,3,4] 示例 2:

输入: [-1,-100,3,99] 和 k = 2 输出: [3,99,-1,-100] 解释: 向右旋转 1 步: [99,-1,-100,3] 向右旋转 2 步: [3,99,-1,-100] 说明:

尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。 要求使用空间复杂度为 O(1) 的 原地 算法。

解法：

每次将整个数组向右移动一步，移动k次即可运用python数组自带的切片方法，非常简单：nums[:]=nums[length-k:] + nums[:length-k]经过3次子数组的 “对称翻折”：如 [1,2,3,4,5,6,7] 和 k = 3，第一步[1,2,3,4]->[4,3,2,1]，第二步[5,6,7]->[7,6,5]，最后[4,3,2,1,7,6,5]->[5,6,7,1,2,3,4]。从第一个元素开始进行旋转，逐个将旋转位置上的元素移到下一个位置，直到旋转到该元素的初始位置。同时使用一个变量记录被旋转的元素数量，显然完成所有旋转后旋转元素数量应该是数组长度。（比较麻烦）

注意：

k要对len求一下余不知道为什么不能直接nums = list(reversed(nums))，可能是编辑器设置的问题，不过可以通过加上":"实现相同的功能

第三种解法：

class Solution(object): def rotate(self, nums, k): """ :type nums: List[int] :type k: int :rtype: None Do not return anything, modify nums in-place instead. """ k = k % len(nums) pos = len(nums) - k nums[:pos] = list(reversed(nums[:pos])) nums[pos:] = list(reversed(nums[pos:])) nums[:] = list(reversed(nums[:]))

第四种解法：

class Solution: def rotate(self, nums, k): """ :type nums: List[int] :type k: int :rtype: void Do not return anything, modify nums in-place instead. """ if len(nums)>1: length = len(nums) k = k%length if k>0: move_num = 0 move_pos = 0 move_value = nums[move_pos] while move_num<length: next_pos = (move_pos+k)%length while next_pos!=move_pos: save_value = nums[next_pos] nums[next_pos] = move_value move_value = save_value next_pos=(next_pos+k)%length move_num+=1 nums[move_pos]=move_value move_num+=1 move_pos+=1 move_value = nums[move_pos]

移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

示例:

输入: [0,1,0,3,12] 输出: [1,3,12,0,0] 说明:

必须在原数组上操作，不能拷贝额外的数组。 尽量减少操作次数。

解法：

自己想的一个，用index(0)判断最左边的0的位置是否已经是最后了，如果不是，就把0后面的所有内容往前移一个位置。总的看来，就是冒泡排序的加强版其实可以不需要管中间移动的过程，只关注最终的结果即可。只要把数组中所有的非零元素，按顺序给数组的前段元素位赋值，剩下的全部直接赋值0就可以。 class Solution(object): def moveZeroes(self, nums): """ :type nums: List[int] :rtype: None Do not return anything, modify nums in-place instead. """ if 0 not in nums: return nums right = len(nums) while nums.index(0) != right: pos = nums.index(0) nums[pos:right-1] = nums[pos+1:right] nums[right-1] = 0 right -= 1 class Solution: def moveZeroes(self, nums: List[int]) -> None: """ Do not return anything, modify nums in-place instead. """ i, j = 0, 0 while j < len(nums): if nums[j] != 0: nums[i] = nums[j] i += 1 j += 1 while i < len(nums): nums[i] = 0 i += 1 return nums

移除元素

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。 不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例 1:

给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。 你不需要考虑数组中超出新长度后面的元素。

示例 2: 给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。 注意这五个元素可为任意顺序。

你不需要考虑数组中超出新长度后面的元素。

解法 同上

class Solution: def removeElement(self, nums: List[int], val: int) -> int: i, j = 0, 0 while j < len(nums): if nums[j] != val: nums[i] = nums[j] i += 1 j += 1 return i

删除排序数组中的重复项

给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

示例 1:

给定数组 nums = [1,1,2], 函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。 你不需要考虑数组中超出新长度后面的元素。

示例 2:

给定 nums = [0,0,1,1,1,2,2,3,3,4], 函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。 你不需要考虑数组中超出新长度后面的元素。

解法 上面题目的变形，同样还是用两个指针，i和j来操作，只不过这个时候不是判断j位置是否是val了，而是判断是否和i前面的数相等。

class Solution(object): def removeDuplicates(self, nums): """ :type nums: List[int] :rtype: int """ i, j = 0, 0 while j < len(nums): if j == 0 or nums[j] != nums[i - 1]: nums[i] = nums[j] i += 1 j += 1 return i

删除排序数组中的重复项 II

给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素最多出现两次，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

示例 1:

给定 nums = [1,1,1,2,2,3],

函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3 。

你不需要考虑数组中超出新长度后面的元素。

解法 同上，只需要稍作修改，和i-2的位置比较就可以了。因为它是排序的

class Solution(object): def removeDuplicates(self, nums): """ :type nums: List[int] :rtype: int """ i, j = 0, 0 while j < len(nums): if j == 0 or j == 1 or nums[j] != nums[i - 2]: nums[i] = nums[j] i += 1 j += 1 return i

打乱数组

打乱一个没有重复元素的数组。

示例:

// 以数字集合 1, 2 和 3 初始化数组。 int[] nums = {1,2,3}; Solution solution = new Solution(nums);

// 打乱数组 [1,2,3] 并返回结果。任何 [1,2,3]的排列返回的概率应该相同。 solution.shuffle();

// 重设数组到它的初始状态[1,2,3]。 solution.reset();

// 随机返回数组[1,2,3]打乱后的结果。 solution.shuffle();

解法： 注意这里的随机要用洗牌方法：在每次迭代中，生成一个范围在当前下标到数组末尾元素下标之间的随机整数。接下来，将当前元素和随机选出的下标所指的元素互相交换。注意，当前元素是可以和它本身互相交换的 - 否则生成最后的排列组合的概率就不对了。 注意randint(min, max)的用法，min和max的值都可能被取到的。 init的时候保存两个，否则shuffle后就变化了原始数组 不明白： self.ori必须在self.arr前面定义，而且必须是nums[:]，是内部存储的一些问题么？如果定义的是self.ori = nums，修改arr的时候会把nums修改，进而把ori修改了。

import random class Solution(object): def __init__(self, nums): """ :type nums: List[int] """ self.ori = nums[:] self.arr = nums def reset(self): """ Resets the array to its original configuration and return it. :rtype: List[int] """ return self.ori def shuffle(self): """ Returns a random shuffling of the array. :rtype: List[int] """ for i in range(len(self.arr)): j = random.randint(i, len(self.arr)-1) self.arr[i], self.arr[j] = self.arr[j], self.arr[i] return self.arr # Your Solution object will be instantiated and called as such: # obj = Solution(nums) # param_1 = obj.reset() # param_2 = obj.shuffle()

递增的三元子序列

给定一个未排序的数组，判断这个数组中是否存在长度为 3 的递增子序列。

数学表达式如下:

如果存在这样的 i, j, k, 且满足 0 ≤ i < j < k ≤ n-1， 使得 arr[i] < arr[j] < arr[k] ，返回 true ; 否则返回 false 。 说明: 要求算法的时间复杂度为 O(n)，空间复杂度为 O(1) 。

示例 1:

输入: [1,2,3,4,5] 输出: true 示例 2:

输入: [5,4,3,2,1] 输出: false

解法： 注意是递增的子序列，并没有说是“连续”子序列，但是还是走动态规划的思路，保存两个指针，一个min，一个medium； 一种方式是把min和medium初始化为最大值：float(“inf”) 另一种是设置一个flag标记下medium是否已经被初始化了。 因此遍历一遍数组，随时更新min和Medium的值，一旦遍历到比medium还大的数，直接返回ture

class Solution(object): def increasingTriplet(self, nums): """ :type nums: List[int] :rtype: bool """ if not nums: return False mi = nums[0] flag = 0 for i in range(1, len(nums)): tmp = nums[i] if tmp < mi: mi = tmp elif tmp > mi and (flag == 0 or tmp < me): me = tmp flag = 1 elif flag == 1 and tmp > me: return True return False

两个数组的交集 II

给定两个数组，编写一个函数来计算它们的交集。

示例 1:

输入: nums1 = [1,2,2,1], nums2 = [2,2] 输出: [2,2] 示例 2:

输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4] 输出: [4,9] 说明：

输出结果中每个元素出现的次数，应与元素在两个数组中出现的次数一致。 我们可以不考虑输出结果的顺序。 进阶:

如果给定的数组已经排好序呢？你将如何优化你的算法？ 如果 nums1 的大小比 nums2 小很多，哪种方法更优？ 如果 nums2 的元素存储在磁盘上，磁盘内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？

解法：

最简单的方法就是遍历两个数组，遇到相同的就记录下来，并删除掉该元素，避免重复。先给两个数组排序，使用归并排序的思路。遇到两个数组的情况，如果要加速处理，就要想到可以设置两个指针。用dict存储元素

解法1：

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

解法2：

class Solution: def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]: res = [] nums1 = sorted(nums1) nums2 = sorted(nums2) i = 0 j = 0 while i < len(nums1) and j < len(nums2): if nums1[i] > nums2[j]: j += 1 elif nums1[i] < nums2[j]: i += 1 else: res.append(nums1[i]) i += 1 j += 1 return res

解法3：

class Solution: def intersect(self, nums1, nums2): """ :type nums1: List[int] :type nums2: List[int] :rtype: List[int] """ m = len(nums1) n = len(nums2) if m == 0 or n == 0: return [] dicts = {} for i in nums1: if i in dicts: dicts[i] += 1 else: dicts[i] = 1 ret = [] for j in nums2: if j in dicts and dicts[j] > 0: ret.append(j) dicts[j] -= 1 return ret

除自身以外数组的乘积

给定长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。

示例:

输入: [1,2,3,4] 输出: [24,12,8,6] 说明: 请不要使用除法，且在 O(n) 时间复杂度内完成此题。

进阶： 你可以在常数空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组不被视为额外空间。）

解法： 最简单的思路就是用除法或者O(n^2)的遍历，但是都被禁止了 其实想到用两个指针了，但是没想到用两个数组 因为是乘法，满足交换律，所以可以在第一遍遍历的时候把nums[i]左边部分的乘积存下来，第二遍的时候把右边的存下来，最后对应相乘就可以。（注意O(kn)=O(n)） 但是要在常熟空间复杂度的话，就只能保留一个数组，可以选择保留左边数组，右边的用一个数值代替就可以了，因为每次用完就不用了。

遍历nums，在遍历的过程中将对应元素累乘，例如 1 2 3 4 1 1 2 6 这样我们就得到了对应元素左边所有元素的乘积。然后我们反向遍历nums，做相同操作即可。 1 2 3 4 24 12 4 1 再将两个结果相乘即可。 1 2 3 4 24 12 8 6

Code

class Solution(object): def productExceptSelf(self, nums): """ :type nums: List[int] :rtype: List[int] """ left = [1] * len(nums) right = 1 for i in range(1, len(nums)): left[i] = left[i-1] * nums[i-1] for i in range(len(nums)-1, -1, -1): left[i] *= right right *= nums[i] return left

寻找数组的中心索引

给定一个整数类型的数组 nums，请编写一个能够返回数组“中心索引”的方法。

我们是这样定义数组中心索引的：数组中心索引的左侧所有元素相加的和等于右侧所有元素相加的和。

如果数组不存在中心索引，那么我们应该返回 -1。如果数组有多个中心索引，那么我们应该返回最靠近左边的那一个。

示例 1:

输入: nums = [1, 7, 3, 6, 5, 6] 输出: 3 解释: 索引3 (nums[3] = 6) 的左侧数之和(1 + 7 + 3 = 11)，与右侧数之和(5 + 6 = 11)相等。 同时, 3 也是第一个符合要求的中心索引。 示例 2:

输入: nums = [1, 2, 3] 输出: -1 解释: 数组中不存在满足此条件的中心索引。 说明:

nums 的长度范围为 [0, 10000]。 任何一个 nums[i] 将会是一个范围在 [-1000, 1000]的整数。

遍历求和：模拟过程，从左到右遍历，找到中心索引首先，计算出整个数组的和；然后，可知道如果存在中心索引的话，那么左边的和的二倍，加上中心索引的值，即等于数组和；从左边开始，依次累加，直到找到中心索引以把数组分成左右两部分，这里需要注意的是，扩大左半部分的同时，右半部分会缩小，这里无需每一次都求左半部分和右半部分的和，可以根据上一次所计算的左半部分和右半部分的和，以及新增加（或删除）的元素来获得当前左半部分和右半部分的和。

解法一：

class Solution(object): def pivotIndex(self, nums): """ :type nums: List[int] :rtype: int """ if not nums: return -1 for i in range(len(nums)): left = sum(nums[:i]) right = sum(nums[i+1:]) if left == right: return i return -1

解法二：

class Solution: def pivotIndex(self, nums): """ :type nums: List[int] :rtype: int """ res = sum(nums) lsum = 0 for i, j in enumerate(nums): if lsum * 2 + j == res: return i lsum += j return -1

解法三：

class Solution: def pivotIndex(self, nums: List[int]) -> int: a=sum(nums[:0]) b=sum(nums[1:]) for i in range(0,len(nums)-1): if a==b: return i a+=nums[i] b-=nums[i+1] if a==b: return len(nums)-1 return -1

至少是其他数字两倍的最大数

在一个给定的数组nums中，总是存在一个最大元素 。

查找数组中的最大元素是否至少是数组中每个其他数字的两倍。

如果是，则返回最大元素的索引，否则返回-1。

示例 1:

输入: nums = [3, 6, 1, 0] 输出: 1 解释: 6是最大的整数, 对于数组中的其他整数, 6大于数组中其他元素的两倍。6的索引是1, 所以我们返回1.

示例 2:

输入: nums = [1, 2, 3, 4] 输出: -1 解释: 4没有超过3的两倍大, 所以我们返回 -1.

提示:

nums 的长度范围在[1, 50]. 每个 nums[i] 的整数范围在 [0, 100].

解法 就是求数组中的最大数和第二大数即可，注意第二大数的求法

class Solution(object): def dominantIndex(self, nums): """ :type nums: List[int] :rtype: int """ m1, m2 = 0, 0 res = 0 for i, x in enumerate(nums): if x > m1: m2 = m1 m1 = x res = i elif x > m2: m2 = x if m1 >= m2 * 2: return res return -1

顺时针打印矩阵

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。

示例 1：

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]] 输出：[1,2,3,6,9,8,7,4,5] 示例 2：

输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]] 输出：[1,2,3,4,8,12,11,10,9,5,6,7]

解法

按层模拟：可以将矩阵看成若干层，首先打印最外层的元素，其次打印次外层的元素，直到打印最内层的元素。设置四个指针，top, left, bottom, right，遍历完当前层的元素之后，将 left 和 top 分别增加 1，将 right 和 bottom 分别减少 1，进入下一层继续遍历，直到遍历完所有元素。主要思想为遍历第一行，然后删除第一行，再逆时针旋转矩阵，循环。代码简洁明了。

矩阵的三种操作：转置、顺时针旋转和逆时针旋转： 二维数组矩阵转置

matrix = list(map(list, zip(*matrix)))

如：

matrix = [[1, 2, 3], [4, 5, 6]] matrix = list(map(list, zip(*matrix))) print(matrix)

输出即为原矩阵的转置： [[1, 4], [2, 5], [3, 6]]

二维数组矩阵顺时针旋转 matrix = list(map(list, zip(*matrix[::-1]))) 原理：可以发现，对矩阵先上下翻转，再转置相当于顺时针旋转。

二维数组矩阵逆时针旋转 matrix = list(map(list, zip(*matrix)))[::-1] 原理：可以发现，对矩阵先转置，再上下翻转相当于逆时针旋转。

解法一：

class Solution: def spiralOrder(self, matrix: List[List[int]]) -> List[int]: if not matrix or not matrix[0]: return list() rows, columns = len(matrix), len(matrix[0]) order = list() left, right, top, bottom = 0, columns - 1, 0, rows - 1 while left <= right and top <= bottom: for column in range(left, right + 1): order.append(matrix[top][column]) for row in range(top + 1, bottom + 1): order.append(matrix[row][right]) if left < right and top < bottom: for column in range(right - 1, left, -1): order.append(matrix[bottom][column]) for row in range(bottom, top, -1): order.append(matrix[row][left]) left, right, top, bottom = left + 1, right - 1, top + 1, bottom - 1 return order

解法二：

# -*- coding:utf-8 -*- class Solution: # matrix类型为二维列表，需要返回列表 def printMatrix(self, matrix): # write code here res = [] while matrix: res += matrix.pop(0) if not matrix: break # 这里对matrix做逆时针旋转，原理见后文 matrix = list(map(list, zip(*matrix)))[::-1] return res

对角线遍历

给定一个含有 M x N 个元素的矩阵（M 行，N 列），请以对角线遍历的顺序返回这个矩阵中的所有元素，对角线遍历如下图所示。

示例:

输入: [ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ]

输出: [1,2,4,7,5,3,6,8,9]

解法 参考：https://leetcode-cn.com/problems/diagonal-traverse/solution/dui-jiao-xian-bian-li-by-leetcode/ 初始化数组 result，用于存储最后结果。 使用一个外层循环遍历所有的对角线。第一行和最后一列的元素都是对角线的起点。 使用一个内层 while 循环遍历对角线上的所有元素。可以计算指定对角线上的元素数量，也可以简单迭代直到索引超出范围。 因为不知道每条对角线上的元素数量，需要为每条对角线分配一个列表或动态数组。但是同样也可以通过计算得到当前对角线上的元素数量。 对于奇数编号的对角线，只需要将迭代结果翻转再加入结果数组即可。

class Solution(object): def findDiagonalOrder(self, matrix): """ :type matrix: List[List[int]] :rtype: List[int] """ if not matrix or not matrix[0]: return [] n, m = len(matrix), len(matrix[0]) res = [] for i in range(m + n + 1): tmp = [] r, c = 0 if i < m else i - m + 1, i if i < m else m - 1 while r < n and c > -1: tmp.append(matrix[r][c]) r += 1 c -= 1 if i % 2 == 0: res.extend(tmp[::-1]) else: res.extend(tmp) return res

奇偶位排序

一个2*N长度数组，其中N个奇数，N个偶数，要求实现1个函数，把奇数放置到奇数下标，偶数放置到偶数下标 要求：1. 不能额外开辟一个内存/数组；2. 数组只能遍历1次

解法 就是可以看成是两个数组，一个奇数数组，一个偶数数组，所以也就是两个指针，都从左往右遍历，找到有问题的就交换。

def try(nums): i, j = 0, 1 n = len(nums) while i < n and j < n: while nums[i] % 2 == 0 and i < n: i += 2 while nums[j] % 2 == 1 and j < n: j += 2 nums[i], nums[j] = nums[j], nums[i] return nums

Excel表列序号

给定一个Excel表格中的列名称，返回其相应的列序号。

例如，

A -> 1 B -> 2 C -> 3 ... Z -> 26 AA -> 27 AB -> 28 ...

示例 1:

输入: “A” 输出: 1 示例 2:

输入: “AB” 输出: 28 示例 3:

输入: “ZY” 输出: 701

解法 其实就是把十进制改成了26进制。 注意把字符转换成整数的方法：ord() 以及’A’的整数值是65

class Solution(object): def titleToNumber(self, s): """ :type s: str :rtype: int """ res = 0 for idx in range(len(s)): res = res * 26 + (ord(s[idx]) - ord('A') + 1) return res

四数相加 II

给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。

为了使问题简单化，所有的 A, B, C, D 具有相同的长度 N，且 0 ≤ N ≤ 500 。所有整数的范围在 -228 到 228 - 1 之间，最终结果不会超过 231 - 1 。

例如:

输入: A = [ 1, 2] B = [-2,-1] C = [-1, 2] D = [ 0, 2]

输出: 2

解释: 两个元组如下:

(0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0(1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0

解法 本来以为会有比两次循环更简单点的解法的，但是并没有找到。 用一个存储前两个的每个结果出现的次数就可以了，不需要存储index。

class Solution(object): def fourSumCount(self, A, B, C, D): """ :type A: List[int] :type B: List[int] :type C: List[int] :type D: List[int] :rtype: int """ dic = {} res = 0 for i in range(len(A)): for j in range(len(B)): tmp = A[i] + B[j] if tmp not in dic: dic[tmp] = 1 else: dic[tmp] += 1 for i in range(len(C)): for j in range(len(D)): tmp = C[i] + D[j] if -tmp in dic: res += dic[-tmp] return res

常数时间插入、删除和获取随机元素

设计一个支持在平均 时间复杂度 O(1) 下，执行以下操作的数据结构。

insert(val)：当元素 val 不存在时，向集合中插入该项。 remove(val)：元素 val 存在时，从集合中移除该项。 getRandom：随机返回现有集合中的一项。每个元素应该有相同的概率被返回。 示例 :

// 初始化一个空的集合。 RandomizedSet randomSet = new RandomizedSet();

// 向集合中插入 1 。返回 true 表示 1 被成功地插入。 randomSet.insert(1);

// 返回 false ，表示集合中不存在 2 。 randomSet.remove(2);

// 向集合中插入 2 。返回 true 。集合现在包含 [1,2] 。 randomSet.insert(2);

// getRandom 应随机返回 1 或 2 。 randomSet.getRandom();

// 从集合中移除 1 ，返回 true 。集合现在包含 [2] 。 randomSet.remove(1);

// 2 已在集合中，所以返回 false 。 randomSet.insert(2);

// 由于 2 是集合中唯一的数字，getRandom 总是返回 2 。 randomSet.getRandom();

解法 考察比较基础的一些用法，注意获得random的值的方法是在总长度中随机找一个index。 以及random.randint(l,r)的左右都能取到

import random class RandomizedSet(object): def __init__(self): """ Initialize your data structure here. """ self.randSet = [] def insert(self, val): """ Inserts a value to the set. Returns true if the set did not already contain the specified element. :type val: int :rtype: bool """ if val not in self.randSet: self.randSet.append(val) return True else: return False def remove(self, val): """ Removes a value from the set. Returns true if the set contained the specified element. :type val: int :rtype: bool """ if val in self.randSet: self.randSet.remove(val) return True else: return False def getRandom(self): """ Get a random element from the set. :rtype: int """ l = len(self.randSet) rand = random.randint(0, l-1) return self.randSet[rand] # Your RandomizedSet object will be instantiated and called as such: # obj = RandomizedSet() # param_1 = obj.insert(val) # param_2 = obj.remove(val) # param_3 = obj.getRandom()

LRU缓存机制

运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。

获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。 写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。

进阶:

你是否可以在 O(1) 时间复杂度内完成这两种操作？

示例:

LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );

cache.put(1, 1); cache.put(2, 2); cache.get(1); // 返回 1 cache.put(3, 3); // 该操作会使得密钥 2 作废 cache.get(2); // 返回 -1 (未找到) cache.put(4, 4); // 该操作会使得密钥 1 作废 cache.get(1); // 返回 -1 (未找到) cache.get(3); // 返回 3 cache.get(4); // 返回 4

解法 实际上是考察python3中字典的用法，首先题目要存储key和value，也就是想到用字典；其次，需要在线性时间内实现三种情况：

查找item当前被查找的数被挪到最后面的位置（先pop，再添加进去）删除最前面的值（转换成list，得到第一个位置再pop） class LRUCache: def __init__(self, capacity: int): self.capacity = capacity self.cache = {} def get(self, key: int) -> int: if key not in self.cache: return -1 self.cache[key] = self.cache.pop(key) return self.cache[key] def put(self, key: int, value: int) -> None: if key in self.cache: self.cache.pop(key) self.cache[key] = value if len(self.cache) > self.capacity: x = list(self.cache)[0] self.cache.pop(x) # Your LRUCache object will be instantiated and called as such: # obj = LRUCache(capacity) # param_1 = obj.get(key) # obj.put(key,value)

中文词表读取

给两个中文路径，读取两个中文文档，一个文档是一行行的文字，一个文档是一堆词表，记录下每一个文档中出现的每个单词的位置

def test(root1, root2): s1, s2 = [], [] with open(root1, "r", encoding="utf-8") as f: data = f.readlines() for line in data: tmp = line.strip('\n') tmp = tmp.split(' ') s1.append(tmp) with open(root2, "r", encoding="utf-8") as f: data = f.readlines() for line in data: tmp = line.strip('\n').split(' ') s2.append(tmp) res = [] for i, x in enumerate(s1): dic = {} for j, y in enumerate(s2): if y in x: if y not in dic: dic[y] = [] for k, z in enumerate(x): if z == y: dic[y].append(k) res.append(dic) return res

数组变成非递减最少步骤

一个数组里面全是0和1，0可以变成1，1可以变成0，求把这个数组变成非递减的最少步骤

def test(nums): x = 0 for j in range(len(nums)): if nums[j] != 1: x += 1 res = x for i in range(0, len(nums)): tmp = x if nums[i] != 1: if nums[i] == 0: tmp -= 1 else: tmp += 1 res = min(res, tmp) x = tmp return res

切分数组，使方差和最小

有一个长度为n的数组，求一个数k，k的取值区间为[1, n-1]，使得数组的前k个数和后n-k个数的方差和最小

解法 方差与期望的关系

def minVariance(arr): sum=0 square_sum=0 length=len(arr) left_var=[0]*length right_var=[0]*length　　#从左到右求每一段的方差 for i in range(length): sum+=arr[i] square_sum+=arr[i]*arr[i] left_var[i]=square_sum/(i+1)-(sum/(i+1))**2 sum = 0 square_sum = 0 #从右到左求每一段的方差 for j in range(length-1,-1,-1): sum+=arr[j] square_sum += arr[j] * arr[j] right_var[j] = square_sum / (length-j) - (sum / (length-j)) ** 2 　　#二者合并，找出方差最小的两断 index=0 variance=left_var[0]+right_var[0] for k in range(length-1): if left_var[k]+right_var[k+1]<variance: variance=left_var[k]+right_var[k] index=k+1 return index

按照概率输出指定位置数字

给定两个数组，a:[1,2,3,4]，b:[0.1,0.05,0.75,0.1]，按照b中概率输出对应位置的a。

#a:[1,2,3,4] #b:[0.1,0.05,0.75,0.1] def test(a, b): c = [] tmp = 0 for x in b: c.append(tmp + x) tmp += x p = random.uniform(0, 1) for i in range(len(c)): if p < c[i]: return a[i] def test2(c, p): l, r = 0, len(c) - 1 while l < r: mid = (l + r) // 2 if c[mid] < p: l = mid + 1 else: r = mid return l

最大长度匹配的分词算法

给定最大长度、文本、词典，输出文本中存在于词典中的词

def test(k, dic, l): res = [] m = len(l) while m > 0: tmp = l[0: k] while tmp not in dic: if len(tmp) == 1: break tmp = tmp[0: len(tmp) - 1] res.append(tmp) l = l[len(tmp):] m = len(l) return res

和为S的两个数字

输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。 输出描述: 对应每个测试案例，输出两个数，小的先输出。

解法 开始自己一直陷在递增排序所以用二分法的解法中，然后又不希望遍历，就想找规律，什么样的两个数乘积最小，后来发现无解，于是看了题解。

哈希法：忽略递增这个条件，要求a + b = sum, 如果已知a， 那么b = sum - a，所以可以先遍历一遍将b添加入哈希中，然后遍历一遍数组设为a， 在哈希中寻找是否存在sum-a，顺便更新乘积最小值。双指针：遇到排序数组既要想到二分法也要想到双指针。一左一右，如果arr[i] + arr[j] == sum , 说明是可能解；否则如果arr[i] + arr[j] > sum, 说明和太大，所以–j ；否则如果arr[i] + arr[j] < sum, 说明和太小，所以++i # -*- coding:utf-8 -*- class Solution: def FindNumbersWithSum(self, array, tsum): # write code here l, r = 0, len(array) - 1 mul = 100000 res = [] while l < r: if array[l] + array[r] == tsum: if array[l] * array[r] < mul: res = [array[l], array[r]] mul = array[l] * array[r] l += 1 r -= 1 elif array[l] + array[r] > tsum: r -= 1 else: l += 1 return res

3Sum

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

The solution set must not contain duplicate triplets.

Example:

Given array nums = [-1, 0, 1, 2, -1, -4], A solution set is: [ [-1, 0, 1], [-1, -1, 2] ]

解法：肯定不是三重循环； 求一个列表中所有和为零的二元组的一种思路是先把列表排序，再用两个指针从两头向中间移动。如果前后两个数的和小于0，则左指针右移；如果和大于0，则右指针左移。求三元组时可以参考这种做法，第一个数a确定后，可以理解为求列表中和为-a的二元组。 由于不要考虑重复的元组，遇到重复的数可以直接跳过。（重复是指和上一个数相比，因为已经排好序了）注意i不能用for循环遍历，因为i也可能会重复，所以也要对i进行判断。

class Solution(object): def threeSum(self, nums): """ :type nums: List[int] :rtype: List[List[int]] """ res = [] n = len(nums) nums = sorted(nums) i = 0 while i < n-2: j = i+1 k = n-1 while j < k: tmp = [nums[i], nums[j], nums[k]] if sum(tmp) == 0: res.append(tmp) j += 1 k -= 1 while j < k and nums[j] == nums[j-1]: j+=1 while j < k and nums[k] == nums[k+1]: k-=1 elif sum(tmp) > 0: k -= 1 else: j += 1 i += 1 while i < n-2 and nums[i] ==nums[i-1]: i += 1 return res

3Sum Closest

Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

Example:

Given array nums = [-1, 2, 1, -4], and target = 1. The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

解法：其实是3Sum的扩展形式，更简单一些了，只需要维护一个变量就可以了。 发现，当一个数组的暴力解法需要循环两遍的时候，一般可以设置两个指针，使得只循环一遍。

class Solution(object): def threeSumClosest(self, nums, target): """ :type nums: List[int] :type target: int :rtype: int """ nums = sorted(nums) dis_min = 1000000 res = 0 i = 0 while i < len(nums)-2: j = i+1 k = len(nums) -1 while j < k : tmp = nums[i] + nums[j] + nums[k] if tmp == target: return target elif tmp > target: dis = tmp - target if dis < dis_min: dis_min = dis res = tmp k -= 1 else: dis = target - tmp if dis < dis_min: dis_min = dis res = tmp j += 1 i += 1 while i < len(nums)-2 and nums[i]==nums[i-1]: i += 1 return res

4Sum

Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note:

The solution set must not contain duplicate quadruplets.

Example:

Given array nums = [1, 0, -1, 0, -2, 2], and target = 0. A solution set is: [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]

解法：空间换时间？复杂度是O(2N^2) 既然有四个数，那就把前两个数之和和后两个数之和分别当做一个数。用字典存储下来分别两个数的和。 第二遍遍历列表，就类似于三元组加和，但是更简单一些，因为第三个数据的下标已经存在字典里面了。

class Solution(object): def fourSum(self, nums, target): """ :type nums: List[int] :type target: int :rtype: List[List[int]] """ if len(nums) < 4: return [] res = set() dic = {} for i in range(len(nums)): for j in range(i + 1, len(nums)): tmp = nums[i] + nums[j] if tmp in dic: dic[tmp].append((i, j)) else: dic[tmp] = [(i, j)] for i in range(len(nums)): for j in range(i + 1, len(nums)): need_num = target - (nums[i] + nums[j]) if need_num in dic: for idxs in dic[need_num]: if idxs[0] > j: res.add(tuple(sorted([nums[i], nums[j], nums[idxs[0]], nums[idxs[1]]]))) res = [list(x) for x in res] return res

Next Permutation

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place and use only constant extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

1,2,3 → 1,3,2 3,2,1 → 1,2,3 1,1,5 → 1,5,1

解法： 注意时间复杂度要求是o(n)的； 下一个排列的意思就是下一个比当前的数大的数； 若是以及排好序，就将其重新排列为字典序最小的排列（翻转一下） 函数没有返回值，直接修改列表； 通过一个例子来说明，原数组为[1,7,3,4,2,1]。我们想要找到比173421大一点的数，那就要优先考虑将后面的数字变换顺序，而421从后往前是升序的（也就是这三个数字能组成的最大的数），变换了反而会变小，所以要先找到降序的点。可以看出3是第一个降序的点，要想整个数变大，3就要变大，从后往前找到第一个比3大的数4，将3和4交换位置得到174321，既然原来3所在位置的数字变大了，那整个数肯定变大了，而它之后的数是最大的（从后往前是升序的），应转换成最小的，直接翻转。

class Solution(object): def nextPermutation(self, nums): """ :type nums: List[int] :rtype: None Do not return anything, modify nums in-place instead. """ target_i = 0 change_i = 0 n = len(nums) for i in range(n-1, 0, -1): if nums[i] > nums[i-1]: target_i = i-1 break for i in range(n-1, -1, -1): if nums[i] > nums[target_i]: change_i = i break nums[target_i], nums[change_i] = nums[change_i], nums[target_i] if target_i == change_i ==0: nums.reverse() else: nums[target_i+1:] = reversed(nums[target_i+1:])

和为S的连续正数序列

小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck! 输出描述: 输出所有和为S的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序

解法 参考：https://www.nowcoder.com/questionTerminal/c451a3fd84b64cb19485dad758a55ebe?answerType=1&f=discussion

暴力法：用指针i枚举目标序列的左边界，用指针j枚举目标序列的右边界，用指针k枚举区间[i, j]，来计算区间和，看是否等于目标sum。前缀法：sum[i]表示前i个数的和。比如sum[1] = 1,表示前一个数的和为1，sum[2] = 3, 表示前2个数的和为3.现在我们要求区间[2,4]表示求第2,3,4个数的和，就等于sum[4] - sum[1] = 9，代码中我们用一个变量来模拟这个前缀和。滑动窗口：初始化，i=1,j=1, 表示窗口大小为0；如果窗口中值的和小于目标值sum， 表示需要扩大窗口，j += 1；否则，如果窗口值和大于目标值sum，表示需要缩小窗口，i += 1；否则，等于目标值，存结果，缩小窗口，继续进行步骤2,3,4。 # -*- coding:utf-8 -*- class Solution: def FindContinuousSequence(self, tsum): # write code here l, r = 1, 1 tmp = 0 res = [] while l <= tsum/2: if tmp < tsum: tmp += r r += 1 elif tmp > tsum: tmp -= l l += 1 else: ans = [x for x in range(l, r)] res.append(ans) tmp -= l l += 1 return res

删掉一个元素以后全为 1 的最长子数组

给你一个二进制数组 nums ，你需要从中删掉一个元素。

请你在删掉元素的结果数组中，返回最长的且只包含 1 的非空子数组的长度。

如果不存在这样的子数组，请返回 0 。

提示 1：

输入：nums = [1,1,0,1] 输出：3 解释：删掉位置 2 的数后，[1,1,1] 包含 3 个 1 。 示例 2：

输入：nums = [0,1,1,1,0,1,1,0,1] 输出：5 解释：删掉位置 4 的数字后，[0,1,1,1,1,1,0,1] 的最长全 1 子数组为 [1,1,1,1,1] 。 示例 3：

输入：nums = [1,1,1] 输出：2 解释：你必须要删除一个元素。 示例 4：

输入：nums = [1,1,0,0,1,1,1,0,1] 输出：4 示例 5：

输入：nums = [0,0,0] 输出：0

提示：

1 <= nums.length <= 10^5 nums[i] 要么是 0 要么是 1 。

解法 设置两个辅助遍历，一个变量用来存储真实的1的个数，另一个相当于是在某个位置上的0去掉之后的结果。

class Solution(object): def longestSubarray(self, nums): """ :type nums: List[int] :rtype: int """ res = 0 a, b = 0, 0 for i, x in enumerate(nums): if x == 1: a += 1 b += 1 res = max(res, a) else: a = b b = 0 if res == len(nums): res -= 1 return res

统计人数最多的年份

给定一批人以及他们的出生、死亡年份，输入以数组的形式给出；请输出人口数目最多的年份 举例：输入：[[1940, 1970], [1965, 2003]…] 要求，时间复杂度为O(N)

解法

最简单的就是从最小年份到最大年份挨个统计每个人的区间是否包含这一年，时间复杂度是N^2用数组存储所有年份，遍历一遍每个人，按照这个人的区间更新一遍数组中对应的位置只需要更新每个时间节点增加的人。这个和第二个方法时间复杂度应该都是一样的O(N) def f(people): mi_y, ma_y = min([x[0] for x in people]), max([x[1] for x in people]) counter = [0 for x in range(ma_y - mi_y + 2)] ma_p, res = 0, 0 for s, e in people: counter[s - mi_y] += 1 counter[e - mi_y + 1] -= 1 total = 0 for i, x in enumerate(counter): total += x if ma_p < total: ma_p = total res = i return res

盛最多水的容器

给你 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器，且 n 的值至少为 2。

示例：

输入：[1,8,6,2,5,4,8,3,7] 输出：49

解法 双指针方法：每次左右两端都舍去短的那一端 ：若选择短的那一端【S=小于等于此端的高*小于等于当前的最大区间长度】， 至多的面积也是选择最左最右的一个矩形，因此不必再考虑短的一端，直接舍去逼近

class Solution(object): def maxArea(self, height): """ :type height: List[int] :rtype: int """ res = 0 l, r = 0, len(height) - 1 while l < r: tmp = min(height[l], height[r]) * (r - l) res = max(res, tmp) if height[l] < height[r]: l += 1 else: r -= 1 return res

长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。

示例： 输入：s = 7, nums = [2,3,1,2,4,3] 输出：2 解释：子数组 [4,3] 是该条件下的长度最小的子数组。

进阶： 如果你已经完成了 O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。

解法 参考：https://blog.csdn.net/qq_17550379/article/details/80540430

暴力破解，通过遍历所有的子数组找到满足条件的最小子数组：外面的循环是从第i个位置开始找以i开头的所有子数组，时间复杂度为O(N^2)二分搜索法：考虑是否存在mid长度子数组，我们将窗口的大小内元素值是否满足和>=s作为条件。时间复杂度就是O(nlogn)两个指针：通过累加两个指针的区间内的值和s比较，就可以在O(n)级别的时间内得到结果。定义指针 start 和 end 分别表示子数组的开始位置和阶数位置，维护变量 sum 存储子数组中的元素和。开始时 starts 和 end 都指向下标0，sum=0。每一轮迭代都将 nums[end] 加到 sum 中，如果 sum≥s ，更新子数组的最小常数，然后从 sum 中减掉 nums[start] ，并把 start 右移，直到 sum<s ，此过程中要更新子数组最小长度。每轮迭代后将 end 后移。

方法一：

class Solution(object): def minSubArrayLen(self, s, nums): """ :type s: int :type nums: List[int] :rtype: int """ res = len(nums) + 1 for i in range(len(nums)): cnt = 0 for j in range(i, len(nums)): cnt += nums[j] if cnt >= s: res = min(res, j - i + 1) if res == len(nums) + 1: return 0 return res

方法二：

class Solution: def getCnt(self, s, nums, k): cnt = 0 for i in range(len(nums)): cnt += nums[i] if i >= k: cnt -= nums[i - k] if cnt >= s: return True return False def minSubArrayLen(self, s: int, nums: List[int]) -> int: l, r = 1, len(nums) res = 0 while l <= r: mid = (l + r) // 2 if self.getCnt(s, nums, mid): r = mid - 1 res = mid else: l = mid + 1 return res

方法三：

class Solution(object): def minSubArrayLen(self, s, nums): n = len(nums) start, end = 0,0 mysum = 0 ans = n+1 while end < n: mysum += nums[end] while mysum >= s: ans = min(ans, end-start+1) mysum -= nums[start] start += 1 end += 1 return 0 if ans == n+1 else ans

合并区间

给出一个区间的集合，请合并所有重叠的区间。

示例 1:

输入: [[1,3],[2,6],[8,10],[15,18]] 输出: [[1,6],[8,10],[15,18]] 解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6]. 示例 2:

输入: [[1,4],[4,5]] 输出: [[1,5]] 解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

解法 先按区间的开头排序。将第一个区间加入其中，逐个比较后面的区间是否与其重叠。如果不重叠，直接加入。如果重叠就更新一下end

class Solution(object): def merge(self, intervals): """ :type intervals: List[List[int]] :rtype: List[List[int]] """ intervals = sorted(intervals, key = lambda x: x[0]) res = [] for x in intervals: if len(res) == 0 or x[0] > res[-1][1]: res.append(x) else: res[-1][1] = max(x[1], res[-1][1]) return res

旋转矩阵

给你一幅由 N × N 矩阵表示的图像，其中每个像素的大小为 4 字节。请你设计一种算法，将图像旋转 90 度。

不占用额外内存空间能否做到？

示例 1:

给定 matrix = [ [1,2,3], [4,5,6], [7,8,9] ],

原地旋转输入矩阵，使其变为: [ [7,4,1], [8,5,2], [9,6,3] ] 示例 2:

给定 matrix = [ [ 5, 1, 9,11], [ 2, 4, 8,10], [13, 3, 6, 7], [15,14,12,16] ],

原地旋转输入矩阵，使其变为: [ [15,13, 2, 5], [14, 3, 4, 1], [12, 6, 8, 9], [16, 7,10,11] ]

解法 想了半天，本来找到了原始矩阵行列和转换后矩阵行列的转换关系，但是却只想一个个的交换元素，这样会有很多问题。可以直接根据这个转换关系在整体矩阵上面求。 转换关系：ne_row, ne_col = col, n - 1 - row 所以这个就是先上下翻转矩阵，然后再主对角线翻转。

class Solution(object): def rotate(self, matrix): """ :type matrix: List[List[int]] :rtype: None Do not return anything, modify matrix in-place instead. """ n = len(matrix) for i in range(n // 2): for j in range(len(matrix[0])): matrix[i][j], matrix[n - 1 - i][j] = matrix[n - 1 - i][j], matrix[i][j] for i in range(n): for j in range(i): matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j] return matrix

零矩阵

编写一种算法，若M × N矩阵中某个元素为0，则将其所在的行与列清零。

示例 1：

输入： [ [1,1,1], [1,0,1], [1,1,1] ] 输出： [ [1,0,1], [0,0,0], [1,0,1] ] 示例 2：

输入： [ [0,1,2,0], [3,4,5,2], [1,3,1,5] ] 输出： [ [0,0,0,0], [0,4,5,0], [0,3,1,0] ]

解法

用两个set存储原数组中为0的位置，然后重新赋值，时间复杂度为O(mn)，空间复杂度也是o(mn)遇到为0的位置，将该位置的第一行，第一列设置为0，根据第一行和第一列进行清零。注意 第一行和第一列的数据 matrix[0][0] 既表示第一行又表示第一列，需要特殊处理 class Solution(object): def setZeroes(self, matrix): """ :type matrix: List[List[int]] :rtype: None Do not return anything, modify matrix in-place instead. """ n, m = len(matrix), len(matrix[0]) row_dic, col_dic = set(), set() for i in range(n): for j in range(m): if matrix[i][j] == 0: row_dic.add(i) col_dic.add(j) for i in range(n): for j in range(m): if i in row_dic or j in col_dic: matrix[i][j] = 0 return matrix class Solution: def setZeroes(self, matrix: List[List[int]]) -> None: """ Do not return anything, modify matrix in-place instead. """ m, n = len(matrix), len(matrix[0]) row, col = False, False for i in range(m): for j in range(n): if(matrix[i][j] == 0): if(i == 0): row = True if(j == 0): col = True matrix[i][0] = 0 matrix[0][j] = 0 for i in range(1, m): if(matrix[i][0] == 0): for j in range(n): matrix[i][j] = 0 for i in range(1, n): if(matrix[0][i] == 0): for j in range(m): matrix[j][i] = 0 if(row): for i in range(n): matrix[0][i] = 0 if(col): for i in range(m): matrix[i][0] = 0

数组拆分 I

给定长度为 2n 的数组, 你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), …, (an, bn) ，使得从1 到 n 的 min(ai, bi) 总和最大。

示例 1:

输入: [1,4,3,2]

输出: 4 解释: n 等于 2, 最大总和为 4 = min(1, 2) + min(3, 4). 提示:

n 是正整数,范围在 [1, 10000]. 数组中的元素范围在 [-10000, 10000].

解法 就是排序一下，把最小值加进去，也就是偶数位置上的值

class Solution(object): def arrayPairSum(self, nums): """ :type nums: List[int] :rtype: int """ nums = sorted(nums) nums2 = [nums[i] for i in range(len(nums)) if i % 2 == 0] return sum(nums2)

求数组的最大值和最小值

给定一个含有n个元素的整型数组a，找出其中的最大值和最小值

解法

常规的做法是遍历一次，分别求出最大值和最小值。分治法，将数组分成左右两部分，先求出左半部份的最大值和最小值，再求出右半部份的最大值和最小值，然后综合起来求总体的最大值及最小值。这是个递归过程，对于划分后的左右两部分，同样重复这个过程，直到划分区间内只剩一个元素或者两个元素。 def helper(nums, l, r): if l == r: return nums[l], nums[r] if l + 1 == r: ma, mi = max(nums[l], nums[r]), min(nums[l], nums[r]) return ma, mi mid = (l + r) // 2 l_ma, l_mi = helper(nums, l, mid) r_ma, r_mi = helper(nums, mid + 1, r) ma, mi = max(l_ma, r_ma), min(l_mi, r_mi) return ma, mi def Max_Min(nums): if not nums: return -1, -1 l, r = 0, len(nums) - 1 ma, mi = helper(nums, l, r) return ma, mi a = [9,4,2,5,7,3] ma, mi = Max_Min(a) print(ma, mi)

求一个整数数组元素间最小差值

给定一个含有n个元素的整型数组，找出数组中的两个元素x和y使得abs(x - y)值最小

解法

暴力穷举：利用数组中所有数据两两相减的对比来求出这个最小差值，也可以得到这两个元素分别位置idx先排序，再求相邻两个数的差值设立辅助数组:设辅助数组为Bn.原来题目中给定的数组是An,则Bn等于：

B1 = A1 - A2;

B2 = A2 - A3;

B3 = A3 - A4;

……

Bn-1 = An-1 - An.

注意，Bn的长度是n-1，正好比An要小一个。因为这样做的话，我们能够把这道看似无从下手求出最优解的问题转化为求Bn的绝对值最小的最长连续子序列和，因为Bn的连续子序列和便是An任意两数之差（注意，由于题目要求的是绝对值最小，所以求出A1-A2等效于得出A2-A1），例如：

A2 - A5 = B2 + B3 + B4 = A2 - A3 + A3 - A4 + A4 - A5 = A2 - A5

def getMinSum(nums): mi = 100000 for i in range(len(nums)): for j in range(i + 1, len(nums)): sub = abs(nums[i] - nums[j]) if mi > sub: mi = sub return mi a = [9,4,2,5,7,3] print(getMinSum(a)) def getMinSum_2(nums): nums = sorted(nums) sub = [] for i in range(len(nums) - 1): sub.append(abs(nums[i] - nums[i + 1])) return min(sub)

求数组中满足给定和的数对

给定两个有序整型数组a和b，各有n个元素，求两个数组中满足给定和的数对，即对a中元素i和b中元素j，满足i + j = d(d已知)

解法 类似于在同一个数组中的求解方式，还是设置两个指针i和j分别指向两个数组分别的首尾，然后从两端同时向中间遍历。

def search(nums1, nums2, target): l, r = 0 , len(nums2) - 1 while l < len(nums1) and r >= 0: if nums1[l] + nums2[r] < target: l += 1 elif nums1[l] + nums2[r] > target: r -= 1 else: return l, r return -1, -1 a = [9, 4, 2, 5, 7, 3] b = [1, 4, 7, 1] l, r = search(a, b, 10) print(l, r)

一次编辑

字符串有三种编辑操作:插入一个字符、删除一个字符或者替换一个字符。 给定两个字符串，编写一个函数判定它们是否只需要一次(或者零次)编辑。

示例 1:

输入: first = “pale” second = “ple” 输出: True

示例 2:

输入: first = “pales” second = “pal” 输出: False

解法 开始想法是对两个数组分别设置指针，都从左到右遍历，再设置一个flag，标识是否已经进行了一次修改，但是发现这样的判断条件太多。因为这个题目的是自不同位起，后续都一样。所以只要出现不同后，比较后续即可。注意：比较时，如果第1个字符串比较长，可能会index溢出；又因为增和删其实是逆操作，可直接把两个字符串交换；因为第2个肯定比第1个长了，所以只存在增和改的比较

class Solution: def oneEditAway(self, first: str, second: str) -> bool: if abs(len(second) - len(first)) > 1: return False if len(second) - len(first) < 0: first, second = second, first for i in range(len(first)): if first[i] == second[i]: continue # 遇到不一样了，可能：增；改 return first[i:] == second[i + 1:] or first[i+1:] == second[i+1:] return True

加油站

在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。

如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。

说明:

如果题目有解，该答案即为唯一答案。 输入数组均为非空数组，且长度相同。 输入数组中的元素均为非负数。 示例 1:

输入: gas = [1,2,3,4,5] cost = [3,4,5,1,2]

输出: 3

解释: 从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油 开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油 开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油 开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油 开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油 开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。 因此，3 可为起始索引。

解法

两重遍历：检查每一个加油站，选择该加油站为出发站，模拟汽车环路行驶，在每一个加油站检查我们还剩多少升汽油。时间复杂度为O(N^2)。一次遍历：设置两个变量，一个是total_tank表示整个环形过程中油箱中剩下的油；另一个是cur_tank表示从start位置开始油箱中剩下的油。则如果cur_tank小于0了，就表示不能从start位置开始，而要从当前位置加一的位置开始继续尝试。最后判断若是total_tank大于0则返回start位置。

解法一：

class Solution: def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int: start = 0 n = len(gas) while start < n: gas_2, cost_2 = gas[start: n] + gas[: start], cost[start: n] + cost[: start] tmp_gas = 0 flag = 0 for i in range(n): tmp_gas = tmp_gas + gas_2[i] - cost_2[i] if tmp_gas < 0: flag = 1 break if flag == 0: return start start += 1 return -1

解法二：

class Solution: def canCompleteCircuit(self, gas, cost): """ :type gas: List[int] :type cost: List[int] :rtype: int """ n = len(gas) total_tank, curr_tank = 0, 0 starting_station = 0 for i in range(n): total_tank += gas[i] - cost[i] curr_tank += gas[i] - cost[i] # If one couldn't get here, if curr_tank < 0: # Pick up the next station as the starting one. starting_station = i + 1 # Start with an empty tank. curr_tank = 0 return starting_station if total_tank >= 0 else -1

滑动窗口最大值

给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回滑动窗口中的最大值。 示例:

输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3 输出: [3,3,5,5,6,7] 解释: 滑动窗口的位置 最大值 --------------- ----- [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7

解法 Sliding Window法。 维护window这个数组，使得在任意时刻，window【0】都是当前Window内最大值的下标。 并且window从左到右恰恰是第一大、第二大、。。。。。第K大的元素（也就是C++中的双端队列，在队列中存储元素在数组中的位置， 并且维持队列的严格递减） 维护过程为：

如果window不为空，并且 window[0] 比 i - k 小 （这就说明window[0]在当前Window的左界的左侧，应该被踢出去）， 把window【0】弄出去把从队尾倒着数的每个比item 大的元素都弄出去把item 弄进Window如果index > = k - 1， 就说明Window size 已经有k了，可以输出答案了。因为如果 index < k - 1， 说明Window size还没到k。 class Solution(object): def maxSlidingWindow(self, nums, k): """ :type nums: List[int] :type k: int :rtype: List[int] """ if not nums: return [] res, window = [], [] for index, item in enumerate(nums): if window and window[0] <= index - k: window.pop(0) while window and nums[window[-1]] <= item: window.pop() window.append(index) if index >= k-1: res.append(nums[window[0]]) return res

螺旋矩阵

给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。

示例 1:

输入: [ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ] 输出: [1,2,3,6,9,8,7,4,5] 示例 2:

输入: [ [1, 2, 3, 4], [5, 6, 7, 8], [9,10,11,12] ] 输出: [1,2,3,4,8,12,11,10,9,5,6,7]

解法

模拟：4个指针，分别表示上下左右的位置，注意循环中要不断判断是否要break模仿dfs的走法

方法一：

class Solution: def spiralOrder(self, matrix: List[List[int]]) -> List[int]: res = [] if len(matrix) == 0 or len(matrix[0]) == 0: return res left, right, top, bottom = 0, len(matrix[0]) - 1, 0, len(matrix) - 1 while left <= right and top <= bottom: i = left while i <= right: x = matrix[top][i] res.append(x) i += 1 top += 1 if left > right or top > bottom: break i = top while i <= bottom: x = matrix[i][right] res.append(x) i += 1 right -= 1 if left > right or top > bottom: break i = right while i >= left: x = matrix[bottom][i] res.append(x) i -= 1 bottom -= 1 if left > right or top > bottom: break i = bottom while i >= top: x = matrix[i][left] res.append(x) i -= 1 left += 1 return res

方法二：

class Solution: def spiralOrder(self, matrix: List[List[int]]) -> List[int]: m = len(matrix) if not m: return [] n = len(matrix[0]) if not n: return [] D = [[0, 1], [1, 0], [0, -1], [-1, 0]] seen, res = set(), [] i, j, d = 0, 0, 0 while len(res) < m * n: res.append(matrix[i][j]) seen.add((i, j)) _i, _j = i + D[d][0], j + D[d][1] if (_i, _j) in seen or _i < 0 or _j < 0 or _i >= m or _j >= n: d = (d + 1) % 4 _i, _j = i + D[d][0], j + D[d][1] i, j = _i, _j return res