type
status
date
slug
summary
tags
category
icon
password
leetcode 算法刷题记录和总结, 主要使用Python和Go来作答.
算法
从排序数组中删除重复项
给定一个有序数组，你需要原地删除其中的重复内容，使每个元素只出现一次,并返回新的长度。不要另外定义一个数组，您必须通过用 O(1) 额外内存原地修改输入的数组来做到这一点。
示例
给定数组: nums = [1,1,2], 你的函数应该返回新长度 2, 并且原数组nums的前两个元素必须是1和2
不需要理会新的数组长度后面的元素
思路
数组是有序的, 则相同的值必定是紧挨着的, 通过定义两个变量, 一个变量a用于记录数组最后一个不重复值的下标, 使用一个变量b循环数组, 若nums[a] != nums[b] 时, 就将a值增1, 并执行nums[a] = nums[b]. 循环结束后, a+1 的值即为数组中新数组不相等的长度. 考虑到空数组的情况, 可将b初始化为-1, 在循环结束后 b > a 的情况下, 才将a增1.
代码
Python:
Go:
旋转数组
将包含 n 个元素的数组向右旋转 k 步。要求空间复杂度为 O(1)。
示例
例如，如果 n = 7 , k = 3，给定数组 [1,2,3,4,5,6,7] ，向右旋转后的结果为 [5,6,7,1,2,3,4]。
思路
- 旋转数组操作类似于一个循环队列操作, k 到队尾出队再从对首入队
- 利用切片操作将数组切为 [:len(nums)-k] 和 nums[len(nums)-k:] 再重新组合
- 将数组 [:len(nums)-k] 和 [len(nums)-k:] 分别逆序, 再将整个数组逆序
代码
Python:
思路1
思路2:
Go:
两个数组的交集 II
给定两个数组，写一个方法来计算它们的交集。
- 输出结果中每个元素出现的次数，应与元素在两个数组中出现的次数一致。
- 我们可以不考虑输出结果的顺序。
示例
例如, 给定 nums1 = [1, 2, 2, 1], nums2 = [2, 2], 返回 [2, 2].
思路
便利其中一个列表(可能的话, 优先选择较短的数组), 检查此列表中的元素是否在另一列表中存在, 存在的话即为一交集值加入返回结果的列表中, 并从了另一列表中删除
代码
Python:
思路1
思路2, 利用
collections模块Go:
两数之和
给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。
示例
给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]
思路
- 循环遍历, 依次相加验证
- 利用 map 来验证差是否在数组中
代码
Python:
思路1
Go:
思路2
有效的数独
判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。
- 数字 1-9 在每一行只能出现一次。
- 数字 1-9 在每一列只能出现一次。
- 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
思路
利用
set 和 dict 数据结构进行比对代码
Python:
旋转数组
给定一个 n × n 的二维矩阵表示一个图像。将图像顺时针旋转 90 度。你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。
示例
思路
将数据结构看做矩阵，先转置矩阵再颠倒每排数组。
代码
Go: