01.数组
# 01.求两数之和
- 题目
给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 的那 两个 整数,并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。
示例 1:
输入:nums = [2,7,11,15], target = 9
输出:[0,1]
解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1]
2
3
4
5
6
# 1.1 python答案
nums = [2,11,15,3,6,7]
target = 9
def towSum(nums, target):
dic = {}
for k, v in enumerate(nums):
if target - v in dic: # 证明字典中存在一个value与当前value和等于target
print(dic[target - v], k) # 打印这两个值的索引
dic[v] = k
towSum(nums, target)
# 3 4
# 0 5
2
3
4
5
6
7
8
9
10
11
# 1.2 golang答案
package main
import "fmt"
func twoSum(nums []int, target int) []int {
tmpMap := map[int]int{}
for index, num := range nums {
_,ok := tmpMap[target-num]
if ok { // 证明字典中存在一个value与当前value和等于target
return []int{tmpMap[target-num], index} // 返回这两个值的索引
}
tmpMap[num] = index
}
return []int{}
}
func main() {
nums := []int{2,7,11,15}
target := 9
li := twoSum(nums, target)
fmt.Println(li) // [0,1]
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 02.最大子序和
# 2.1 题目描述
给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
输入:nums = [-2,1,-3,4,-1,2,1,-5,4]
输出:6
解释:连续子数组 [4,-1,2,1] 的和最大,为 6 。
2
3
# 2.2 python
- 基本思路就是遍历一遍,用两个变量,一个记录最大的和,一个记录当前的和。
如果当前和小于0,当前最长序列到此为止。以该元素为起点继续找最大子序列
- 时空复杂度貌似还不错......(时间复杂度 O(n),空间复杂度 O(l)
def maxSub(nums):
max_ = nums[0] # 假设第一个为最大和
for i in range(1, len(nums)):
if nums[i - 1] > 0: # 如果当前和大于0就将当前和加上当新数据,否则重新开始当前和
nums[i] += nums[i - 1]
max_ = max(max_, nums[i]) # 当前和 于 记录最大和比较,大的为新的最大和
return max_
nums = [-2,1,-3,4,-1,2,1,-5,4]
print(maxSub(nums)) # 6 ==》[4,-1,2,1]
2
3
4
5
6
7
8
9
10
# 2.3 golang
- 基本思路就是遍历一遍,一个记录最大的和,一个记录当前的和。
- 如果当前的和大于0,就继续加下一个元素,然后比较max,如果更大就更新max
- 时空复杂度貌似还不错......(时间复杂度 O(n),空间复杂度 O(l)
package main
import "fmt"
func maxSubArray(nums []int) int {
max := nums[0] // 假设第一个为最大和
for i := 1; i < len(nums); i++ {
if nums[i] + nums[i-1] > nums[i] { // 如果nums[i-1]当前和大于0,将当前和加上当新数据,否则重新开始当前和
nums[i] += nums[i-1]
}
if nums[i] > max { // 当前和与记录最大的和比较,如果当前和更大就更新
max = nums[i]
}
}
return max
}
func main() {
nums := []int{-2,1,-3,4,-1,2,1,-5,4}
fmt.Println( maxSubArray(nums) ) // 6
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 03.买卖股票的最佳时机
# 3.1 题目要求
给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易(即买入和卖出一支股票),设计一个算法来计算你所能获取的最大利润。
注意你不能在买入股票前卖出股票。
输入: [7,4,6,3,1]
输出: 2
2
# 3.2 python
有 买入(buy) 和 卖出(sell) 这两种状态
当天买的话意味着损失
-prices[i]
,当天卖的话意味着增加prices[i]
,当天卖出总的收益就是buy+prices[i]
所以我们只要考虑当天买和之前买哪个收益更高,当天卖和之前卖哪个收益更高。
- buy = max(buy, -price[i]) (注意:根据定义 buy 是负数)
- sell = max(sell, prices[i] + buy)
s = [7,4,6,3,1]
def maxProfit(prices):
if len(prices) <= 1:
return 0
buy = prices[0] # 当天买的话意味着损失 -prices[i]
sell = 0
for i in prices:
buy = min(buy, i) # 当前买的价格 比 以前买入的大,就在当前节点买入
sell = max(sell, i-buy) # 卖的价钱 = 现在成交价格i - 购买价格buy
return sell
print(maxProfit(s)) # 2
2
3
4
5
6
7
8
9
10
11
12
13
# 3.3 golang
package main
import (
"fmt"
)
func maxProfit(prices []int) int {
if len(prices) <= 1{
return 0
}
buy := prices[0] // 当天买的话意味着损失 -prices[i]
sell := 0 // 初始化利润为0
for _, price := range prices{
if price < buy { // 当前买的价格 比 以前买入的大,就在当前节点买入
buy = price // 卖的价钱 = 现在成交价格i - 购买价格buy
}
if price-buy > sell{ // 如果当前价格减卖的价格 大于记录的最大利润,就更新最大利润
sell = price-buy
}
}
return sell
}
func main() {
prices := []int{7,4,6,3,1}
ret := maxProfit(prices)
fmt.Println(ret) // 2
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# 04.买卖股票最大亏损
# 4.1 题目要求
给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易(即买入和卖出一支股票),设计一个算法来计算你所能获取的最大亏损。
注意你不能在买入股票前卖出股票。
输入: [7,6,4,3,1]
输出: -6
2
# 4.2 python
s = [7,6,4,3,1]
class Solution:
def maxProfit(self, prices):
if len(prices)<=1:
return 0
buy = -prices[0] # 当天买的话意味着损失 -prices[i]
sell=0 # 初始化利润为0
for i in prices:
buy = min(buy, -i) # 当前价格与买进价格那个大就为新的买进价格
sell= min(sell, i + buy) # 计算最大亏损
return sell
print( Solution().maxProfit(s) )
2
3
4
5
6
7
8
9
10
11
12
13
14
# 05.合并两个有序数组
# 5.1 题目说明
给你两个有序整数数组
nums1
和nums2
,请你将nums2
合并到nums1
中*,*使nums1
成为一个有序数组。初始化 nums1 和 nums2 的元素数量分别为 m 和 n
你可以假设 nums1 的空间大小等于 m + n,这样它就有足够的空间保存来自 nums2 的元素。
输入:nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出:[1,2,2,3,5,6]
2
# 5.2 普通合并方案
def merge(num1, num2):
tmp = []
n1 , n2 =0, 0 # 使用n1, n2两个指针分别指向num1, num2两个数组开始位置
while n1 < len(num1) and n2 < len(num2): # 只要有一个指针遍历完就结束
if num1[n1] < num2[n2]:
tmp.append(num1[n1])
n1 = n1 + 1
else:
tmp.append(num2[n2])
n2 = n2 + 1
return tmp + num1[n1:] if n1 < len(num1) else tmp + num2[n2:] # 将没有遍历完的数组的数据局追加
num1 = [1,4,7,15,19]
num2 = [2,4,9]
print( merge(num1, num2) ) # [1, 2, 4, 4, 7, 9, 15, 19]
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 5.3 python双指针
- 将两个数组看作队列,每次从两个数组头部取出比较小的数字放到结果中。
- 我们为两个数组分别设置一个指针p1 与 p2 来作为队列的头部指针
def merge(nums1, m, nums2, n):
tmp = []
p1, p2 = 0, 0 # 分别设置一个指针p1 与 p2 来作为队列的头部指针
while p1 < m or p2 < n:
if p1 == m: # p1 == m证明 nums1遍历完了,直接遍历num2,添加到tmp中即可
tmp.append(nums2[p2])
p2 += 1
elif p2 == n: # p2 == n证明 nums2遍历完了,直接遍历num1,添加到tmp中即可
tmp.append(nums1[p1])
p1 += 1
elif nums1[p1] < nums2[p2]:
tmp.append(nums1[p1])
p1 += 1
else:
tmp.append(nums2[p2])
p2 += 1
nums1[:] = tmp # [1, 2, 2, 3, 5, 6]
print(nums1)
nums1 = [1,2,3,0,0,0] # nums1 的空间大小等于 m + n
m = 3 # nums1的元素数量为m个
nums2 = [2,5,6]
n = 3 # nums2的元素数量为n个
merge(nums1,m, nums2, n)
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 5.4 golang双指针
package main
import "fmt"
func merge(nums1 []int, m int, nums2 []int, n int) {
//nums1 = nums1[:m]
tmp := []int{}
p1, p2 := 0, 0 // 分别设置一个指针p1 与 p2 来作为队列的头部指针
for p1 < m || p2 < n {
if p1 == m { // p1 == m证明 nums1遍历完了,直接遍历num2,添加到tmp中即可
tmp = append(tmp, nums2[p2:]...)
p2 += 1
}else if p2 == n { // p2 == n证明 nums2遍历完了,直接遍历num1,添加到tmp中即可
tmp = append(tmp, nums1[p1:]...)
p1 += 1
}else if nums1[p1] < nums2[p2] {
tmp = append(tmp, nums1[p1])
p1 += 1
}else {
tmp = append(tmp, nums2[p2])
p2 += 1
}
}
copy(nums1, tmp)
}
func main() {
nums1 := []int{1,2,3,0,0,0} // nums1 的空间大小等于 m + n
nums2 := []int{2,5,6}
m,n := 3,3
merge(nums1, m, nums2, n)
fmt.Println(nums1) // [1 2 2 3 5 6]
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
# 06.数组中重复的数字
# 6.1 题目描述
找出数组中重复的数字。
在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。
数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。
请找出数组中任意一个重复的数字。
输入:
[2, 3, 1, 0, 2, 5, 3]
输出:2 或 3
2
3
# 6.2 python
- 利用字典查找时间复杂度为O(1)的特点
def findRepeat(nums):
d = {}
for i in nums:
if i in d:
return i
d[i] = True
nums = [2, 3, 1, 0, 2, 5, 3]
print( findRepeat(nums) ) # 2
2
3
4
5
6
7
8
9
# 6.2 golang
package main
import "fmt"
func findRepeatNumber(nums []int) int {
d := map[int]bool{}
for _,v := range nums {
_,ok := d[v]
if ok{
return v
}
d[v] = true
}
return 0
}
func main() {
nums := []int{2, 3, 1, 0, 2, 5, 3}
v := findRepeatNumber(nums)
fmt.Println(v) // 2
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 07.删除有序数组中重复项
删除有序数组中的重复项 (opens new window)
# 7.1 题目描述
- 给你一个有序数组
nums
,请你** 原地 (opens new window)** 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。 - 不要使用额外的数组空间,你必须在 原地 (opens new window)修改输入数组 并在使用 O(1) 额外空间的条件下完成。
输入:nums = [1,1,2]
输出:2, nums = [1,2]
2
# 7.2 python
使用 count指针记录当前列表中无重复数字的长度
使用 i 指针遍历列表,如果 相邻两个元素不相等,什么都不处理
如果相邻两个元素不相等,就将 不重复的值放到 count指针位置
遍历完结果:
nums = [0, 0, 1, 1, 1, 2, 2 ,3, 3, 4] # 原始列表 nums = [0, 1, 2, 3, 4, 2, 2, 3, 3, 4] # 遍历后结果,count=5,遍历后取出 nums[5],就是目标结果
1
2
def removeDulp(nums):
count = 1
for i in range(1, len(nums)):
if nums[i] != nums[i - 1]:
nums[count] = nums[i] # 如果相邻两个元素不相等,就将 不重复的值放到 count指针位置
count += 1
return count, nums
nums = [0,0,1,1,1,2,2,3,3,4]
print( removeDulp(nums) ) # (5, [0, 1, 2, 3, 4, 2, 2, 3, 3, 4])
2
3
4
5
6
7
8
9
10
# 7.3 golang
package main
import "fmt"
func removeDuplicates(nums []int) int {
if len(nums) == 0 {
return 0
}
count := 1
for i := 1; i < len(nums); i++ {
if nums[i] != nums[i - 1] {
nums[count] = nums[i] // 如果相邻两个元素不相等,就将 不重复的值放到 count指针位置
count += 1
}
}
return count
}
func main() {
nums := []int{1,1,2}
v := removeDuplicates(nums)
fmt.Println(v) // 2
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 08.两数之和 II
# 8.1 题目描述
- 给定一个已按照 升序排列 的整数数组
numbers
- 请你从数组中找出两个数满足相加之和等于目标数
target
- 你可以假设每个输入只对应唯一的答案,而且你不可以重复使用相同的元素
输入:numbers = [2,3,4], target = 6
输出:[1,3]
输入:numbers = [-1,0], target = -1
输出:[1,2]
2
3
4
# 8.2 python
- 初始时两个指针分别指向第一个元素位置和最后一个元素的位置。
- 每次计算两个指针指向的两个元素之和,并和目标值比较。
- 如果两个元素之和等于目标值,则发现了唯一解。
- 如果两个元素之和小于目标值,则将左侧指针右移一位。
- 如果两个元素之和大于目标值,则将右侧指针左移一位
def twoSum(numbers, target):
low, high = 0, len(numbers) - 1 # 初始时两个指针分别指向第一个元素位置和最后一个元素的位置。
while low < high: # 只要左右指针没有相遇就循环
total = numbers[low] + numbers[high]
if total == target: # 判断两个元素之和等于目标值,则发现了唯一解
return [low + 1, high + 1]
elif total < target:
low += 1
else:
high -= 1
return [-1, -1]
if __name__ == '__main__':
numbers = [2,3,4]
target = 6
print( twoSum(numbers, target) )
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 8.3 golang
package main
import "fmt"
func twoSum(numbers []int, target int) []int {
low, high := 0, len(numbers) - 1 // 初始时两个指针分别指向第一个元素位置和最后一个元素的位置。
for low < high { // 只要左右指针没有相遇就循环
total := numbers[low] + numbers[high]
if total == target{ // 判断两个元素之和等于目标值,则发现了唯一解
return []int{low+1, high+1}
}else if total < target {
low += 1
}else {
high -= 1
}
}
return nil
}
func main() {
nums := []int{2,7,11,15}
target := 9
v := twoSum(nums, target)
fmt.Println(v) // [1 2]
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# 09.多数元素
# 9.1 题目描述
给定一个大小为 n 的数组,找到其中的多数元素。
多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的,并且给定的数组总是存在多数元素
输入:[3,2,3]
输出:3
输入:[2,2,1,1,1,2,2]
输出:2
2
3
4
# 9.2 解题思路
- 我们先将
nums
数组排序,然后返回上文所说的下标对应的元素。 - 应为肯定出现多数元素,那么排序后,中位数一定是这个多数
def manyNums(nums):
nums.sort()
return nums[len(nums) // 2]
nums = [3,2,3]
print( manyNums(nums) ) # 3
2
3
4
5
6
# 10.旋转数组的最小数字
# 10.1 题目描述
- 把一个有序数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。
输入:[3,4,5,1,2]
输出:1
# 上面旋转数组的最小值就为1
2
3
# 10.2 python
- 左边界为low,右边界为high,区间的中点为 m,被分为下面三情况
- 如果 m的值小于 R的值,最小值一定在左半部分
- 如果m的值大于R的值,最小值一定在右半部分
- 如果中间值m等于 R的值,那么右指针就向左移动一位
def minArray(nums):
# 左边界为L,右边界为R,区间的中点为 m
L, R = 0, len(nums) - 1
while L < R:
m = L + (R - L) // 2
if nums[m] < nums[R]: # 如果 m的值小于 R的值,最小值一定在左半部分
R = m
elif nums[m] > nums[R]: # 如果m的值大于R的值,最小值一定在右半部分
L = m + 1
else: # 如果中间值m等于 R的值,那么右指针就向左移动一位
R -= 1 # R右指针向左移动,值是会变小的
return nums[L]
nums = [3,4,5,1,2]
print( minArray( nums ) ) # 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 10.3 golang
package main
import "fmt"
func minArray(numbers []int) int {
// 左边界为L,右边界为R,区间的中点为 m
L, R := 0, len(numbers) - 1
for L < R {
m := L + (R-L) / 2
if numbers[m] < numbers[R] { // 如果 m的值小于 R的值,最小值一定在左半部分
R = m
} else if numbers[m] > numbers[R] { // 如果m的值大于R的值,最小值一定在右半部分
L = m + 1
} else { // 如果中间值m等于 R的值,那么右指针就向左移动一位
R -= 1 // R右指针向左移动,值是会变小的
}
}
return numbers[L]
}
func main() {
nums := []int{3,4,5,1,2}
v := minArray(nums)
fmt.Println(v) // 1
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# 11.两个数组的交集
# 11.1 题目描述
输入:nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出:[9,4]
2
# 11.2 python
def disNum(nums1, nums2):
_set = set(nums1) # 将nums1转换成集合
result = []
for num in nums2:
if num in _set: # 如果nums2中元素在集合中
result.append(num)
_set.discard(num) # 集合中去除刚刚已经添加的元素,避免重复解
return result
if __name__ == '__main__':
nums1 = [4,9,5]
nums2 = [9,4,9,8,4]
print( disNum(nums1, nums2) )
2
3
4
5
6
7
8
9
10
11
12
13
14
# 11.3 golang
package main
import "fmt"
func intersection(nums1 []int, nums2 []int) []int {
set1 := map[int]bool{}
for _, v := range nums1 { // 将nums1转换成集合
set1[v] = true
}
tmp := []int{}
for _,v2 := range nums2 {
_,ok := set1[v2]
if ok { // 如果nums2中元素在集合中
tmp = append(tmp,v2)
delete(set1, v2) // 集合中去除刚刚已经添加的元素,避免重复解
}
}
return tmp
}
func main() {
nums1 := []int{4,9,5}
nums2 := []int{9,4,9,8,4}
v := intersection(nums1, nums2)
fmt.Println(v) // [9 4]
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# 12.加一
# 12.1 题目描述
给定一个由 整数 组成的 非空 数组所表示的非负整数,在该数的基础上加一。
输入:digits = [1,2,3]
输出:[1,2,4]
输入:digits = [9,9,9]
输出:[1,0,0,0]
2
3
4
# 12.2 python
def plusOne(li):
tmp = 1 # 设置临时变量 1
n = len(li) - 1 # 列表最右侧元素下标为 n
while (n >= 0): # 从列表右侧向左遍历
sum = li[n] + tmp # 当前值加上井位为当前位置 总值
digit = sum % 10 # 取余获得当前位置值
li[n] = digit
tmp = sum // 10 # 井位
n -= 1 # 下标向左移动一位
if (tmp > 0): # 如果是 999这种情况,循环结束列表还存在井位
li = [tmp] + li # 直接将井位添加到列表头部即可
return li
print(plusOne([9,9,9])) # [1, 0, 0, 0]
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 12.3 golang
package main
import "fmt"
func plusOne(digits []int) []int {
tmp := 1 // 设置临时变量 1
n := len(digits) - 1 // 列表最右侧元素下标为 n
for n >= 0 { // 从列表右侧向左遍历
sum := digits[n] + tmp // 当前值加上井位为当前位置 总值
digit := sum % 10 // 取余获得当前位置值
digits[n] = digit
tmp = sum / 10 // 井位
n -= 1 // 下标向左移动一位
}
if tmp > 0 { // 如果是 999这种情况,循环结束列表还存在井位
digits = append([]int{tmp}, digits...) // 直接将井位添加到列表头部即可
}
return digits
}
func main() {
nums := []int{9,9,9}
v := plusOne(nums)
fmt.Println(v) // [1 0 0 0]
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# 13.和为s的连续正数序列
# 13.1 题目描述
- 和为s的连续正数序列 (opens new window)
- 输入一个正整数 target ,输出所有和为 target 的连续正整数序列(至少含有两个数)。
- 序列内的数字由小到大排列,不同序列按照首个数字从小到大排列。
输入:target = 9
输出:[[2,3,4],[4,5]]
输入:target = 15
输出:[[1,2,3,4,5],[4,5,6],[7,8]]
2
3
4
# 13.2 python滑动窗口
我们一开始要找的是 1 开头的序列,只要窗口的和小于 target,窗口的右边界会一直向右移动。
假设 1+2+⋯+8 小于 target,再加上一个 9 之后, 发现1+2+⋯+8+9 又大于 target 了。
这说明 1 开头的序列找不到解。此时滑动窗口的最右元素是 9。
接下来,我们需要找 2 开头的序列,我们发现,2+⋯+8 < 1+2+⋯+8 <target。
这说明 2 开头的序列至少要加到 9。
那么,我们只需要把原先 1~9 的滑动窗口的左边界向右移动,变成 2~9 的滑动窗口,然后继续寻找。
而右边界完全不需要向左移动。
以此类推,滑动窗口的左右边界都不需要向左移动,所以这道题用滑动窗口一定可以得到所有的解。
时间复杂度是 O(n)。
def findTarget(target):
i = 1 # 滑动窗口的左边界
j = 1 # 滑动窗口的右边界
sum = 0 # 滑动窗口中数字的和
res = []
while i <= target // 2:
if sum < target: # 右边界向右移动
sum += j
j += 1
elif sum > target:
sum -= i # 左边界向右移动
i += 1
else:
arr = list(range(i, j)) # 记录结果
res.append(arr)
sum -= i # 左边界向右移动
i += 1
return res
print( findTarget(9) ) # [[2, 3, 4], [4, 5]]
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 13.3 golang滑动窗口
package main
import "fmt"
func findContinuousSequence(target int) [][]int {
i := 1 // 滑动窗口的左边界
j := 1 // 滑动窗口的右边界
sum := 0 // 滑动窗口中数字的和
res := [][]int{} // 初始化这样的数据结构 [[2, 3, 4], [4, 5]]
for i <= target / 2 {
if sum < target {
sum += j // 右边界向右移动
j += 1
}else if sum > target {
sum -= i // 左边界向右移动
i += 1
}else {
arr := []int{}
for i1 := i; i1 < j; i1++ {
arr = append(arr, i1)
}
res = append(res, arr) // 记录结果
sum -= i // 左边界向右移动
i += 1
}
}
return res
}
func main() {
target := 9
v := findContinuousSequence(target)
fmt.Println(v) // [[2 3 4] [4 5]]
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
# 14.两个数组的交集 II
# 14.1 题目描述
# 两个数组的交集 II (opens new window)
给定两个数组,编写一个函数来计算它们的交集。
输入:nums1 = [1,2,2,1], nums2 = [2,2]
输出:[2,2]
输入:nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出:[4,9]
2
3
4
# 14.2 python字典方法
def findCom(nums1, nums2):
d = {}
for i in nums1:
d[i] = d.get(i,0) + 1
tmp = []
for i in nums2:
if i in d:
tmp.append(i)
d[i] = d.get(i) - 1
if d[i] == 0: d.pop(i)
return tmp
nums1 = [4, 9, 4, 5]
nums2 = [9, 4, 9, 8, 4]
print(findCom(nums1, nums2)) # [4, 9]
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 14.3 python排序双指针
- 将两个数组进行排序,随后用双指针顺序查找相同的元素
- 创建一个指针 i指向 nums1 数组首位,指针 j 指向 nums2 数组首位。
- 创建一个临时栈,用于存放结果集。
- 开始比较指针 i 和指针 j的值大小,若两个值不等,则数字小的指针,往右移一位。
- 若指针 i和指针 j的值相等,则将交集压入栈。
- 若 nums 或 nums2 有一方遍历结束,代表另一方的剩余值,都是唯一存在,且不会与之产生交集的。
def findCom(nums1, nums2):
nums1.sort()
nums2.sort()
ret = [] # 创建一个临时栈,用于存放结果集
i, j = 0, 0
while i < len(nums1) and j < len(nums2):
# 若两个值不等,则数字小的指针,往右移一位。
if nums1[i] < nums2[j]:
i += 1
elif nums1[i] == nums2[j]: # 如果两个值相等,将数据添加,两个指针都向右移动一位
ret.append(nums1[i])
i += 1
j += 1
else:
j += 1
return ret
nums1 = [4, 9, 5]
nums2 = [9, 4, 9, 8, 4]
print(findCom(nums1, nums2)) # [4, 9]
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 14.4 golang排序双指针
package main
import (
"fmt"
"sort"
)
func intersect(nums1 []int, nums2 []int) []int {
sort.Ints(nums1)
sort.Ints(nums2)
ret := []int{} // 创建一个临时栈,用于存放结果集
i,j := 0,0 // i,j两个指针分别指向nums1,nums2的头部
for i < len(nums1) && j < len(nums2) { // 只要有一个数组遍历完就结束循环
if nums1[i] < nums2[j] { // 若两个值不等,则数字小的指针,往右移一位。
i += 1
}else if nums1[i] == nums2[j] {
ret = append(ret, nums1[i])
i += 1
j += 1
}else {
j += 1
}
}
return ret
}
func main() {
num1 := []int{1,2,2,1}
num2 := []int{2,2}
v := intersect(num1, num2)
fmt.Println(v) // [2,2]
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
# 15.找到所有数组中消失的数字
# 15.1 题目描述
给定一个范围在 1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组,数组中的元素一些出现了两次,另一些只出现一次。
找到所有在 [1, n] 范围之间没有出现在数组中的数字。
您能在不使用额外空间且时间复杂度为O(n)的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内。
输入:
[4,3,2,7,8,2,3,1]
输出:
[5,6]
2
3
4
# 15.2 python
- 由于nums的数字范围均在
[1,n]
中,我们可以利用这一范围之外的数字,来表达「是否存在」的含义。 - 遍历 nums,每遇到一个数 x,就让 nums[x−1] 增加 n
- 由于nums 中所有数均在
[1,n]
中,增加以后,这些数必然大于 n - 最后我们遍历nums,若]nums[i] 未大于 n,就说明没有遇到过数i+1,这样我们就找到了缺失的数字。
def findNums(nums):
n = len(nums)
for num in nums:
x = (num - 1) % n # 由于原始值都小于n,所以对n取余可以找到原始的这个数
nums[x] += n # 遍历 nums,每遇到一个数 x,就让 nums[x−1] 增加 n
# 最后我们遍历nums,若]nums[i] 未大于 n,就说明没有遇到过数i+1,这样我们就找到了缺失的数字
ret = [i + 1 for i, num in enumerate(nums) if num <= n]
return ret
nums = [4,3,2,7,8,2,3,1]
print( findNums(nums) ) # [5, 6]
2
3
4
5
6
7
8
9
10
11
# 16.列表去重
# 16.1 python
#1、set去重
a=[1,2,3,4,1,2,3,4]
print( list(set(a)) ) # [1, 2, 3, 4]
#2、使用字典去重
b = {}
b=b.fromkeys(a).keys()
print(list(b)) # [1, 2, 3, 4]
2
3
4
5
6
7
8
- 列表去重:不改变顺序
a=[1,2,3,4,1,2,3,4]
#1、去重不改变顺序
d = {}
tmp = []
for i in a:
if not d.get(i):
tmp.append(i)
d[i] = True
print(tmp) # [1, 2, 3, 4]
2
3
4
5
6
7
8
9
10
# 16.2 golang
package main
import (
"fmt"
)
func listRemoveDupl(nums []int) []int {
d := map[int]bool{}
tmp := []int{}
for _,v := range nums {
_,ok := d[v]
if !ok { // 如果没有在字典中就添加到列表中,同时记录到字典中
tmp = append(tmp, v)
d[v] = true
}
}
return tmp
}
func main() {
nums := []int{1,2,2,3,5,4,6,3,1}
v := listRemoveDupl(nums)
fmt.Println(v) // [1 2 3 5 4 6]
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 17.实现enumerate函数
l = [1,2,3,4]
def my_enumerate(l):
n = 0
for val in l:
print(n,val)
n += 1
my_enumerate(l)
2
3
4
5
6
7
# 18.列表连续相同数据放一起
# 18.1 题目要求
将列表:# [1,2,2,3,4,4,5,6,6,6,7,8,2,2,2]
转换成:# [[1], [2, 2], [3], [4, 4], [5], [6, 6, 6], [7], [8], [2, 2, 2]]
2
# 18.2 解题思路
# -*- coding: utf-8 -*-
li = [1,2,2,3,4,4,5,6,6,6,7,8,2,2,2]
def func(li):
ret = []
n = 1
while n < len(li):
if li[n] == li[n-1]:
tmp = [li[n-1]]
while n < len(li) and li[n] == li[n-1]:
tmp.append(li[n])
n = n + 1
else:
ret.append(tmp)
else:
ret.append([li[n-1]])
n = n + 1
return ret
print( func(li) )
# [[1], [2, 2], [3], [4, 4], [5], [6, 6, 6], [7], [8], [2, 2, 2]]
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 19.盛最多水的容器
# 19.1 题目描述
- 给你 n 个非负整数 a1,a2,...,an,每个数代表坐标中的一个点 (i, ai) 。
- 在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。
- 找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。
示例 1:
输入:[1,8,6,2,5,4,8,3,7]
输出:49
解释:图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为 49。
示例 2:
输入:height = [1,1]
输出:1
2
3
4
5
6
7
8
# 19.2 python
算法流程:
- 设置双指针 i,j 分别位于容器壁两端,根据规则移动指针(后续说明)
- 并且更新面积最大值
res
,直到i == j
时返回res
指针移动规则与证明:
- 每次选定围成水槽两板高度 h[i],h[j] 中的短板,向中间收窄 1格
- 由于水槽的实际高度由两板中的短板决定,则可得面积公式 S(i, j) = min(h[i], h[j]) × (j - i)
- 在每一个状态下,无论长板或短板收窄 1格,都会导致水槽 底边宽度 -1
- 左右长度,那个小,就移动哪一个,才有可能让面积增大
def maxArea(nums):
# L左指针,J右指针, 面积S(i, j) = min(h[i], h[j]) × (j - i)
L, R, S = 0, len(nums) - 1, 0
while L < R: # 只要左右指针不重合就一直循环
if nums[L] < nums[R]: # 如果做指针小,那么移动左指针才有可能使面积增大
S = max(S, nums[L] * (R - L))
L += 1
else: # 否则若果有指针小,只有移动右指针才有可能使面积增大
S = max(S, nums[R] * (R - L))
R -= 1
return S
nums = [1,8,6,2,5,4,8,3,7]
print( maxArea(nums) )
2
3
4
5
6
7
8
9
10
11
12
13
14
# 19.3 golang
package main
import (
"fmt"
)
func maxArea(height []int) int {
// L左指针,J右指针, 面积S(i, j) = min(h[i], h[j]) × (j - i)
L, R, S := 0, len(height)-1, 0
for L < R { // 只要左右指针不重合就一直循环
if height[L] < height[R] {
if height[L] * (R - L) > S { // 如果做指针小,那么移动左指针才有可能使面积增大
S = height[L] * (R - L)
}
L += 1
} else { // 否则若果有指针小,只有移动右指针才有可能使面积增大
if height[R] * (R - L) > S {
S = height[R] * (R - L)
}
R -= 1
}
}
return S
}
func main() {
nums := []int{1,8,6,2,5,4,8,3,7}
v := maxArea(nums)
fmt.Println(v) // 49
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
# 20.合并区间
# 20.1 题目说明
以数组 intervals 表示若干个区间的集合,其中单个区间为 intervals[i] = [starti, endi]
请你合并所有重叠的区间,并返回一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间
输入:intervals = [[1,3],[2,6],[8,10],[15,18]]
输出:[[1,6],[8,10],[15,18]]
解释:区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6]
2
3
# 20.2 解题思路
- 首先,我们将列表中的区间按照左端点升序排序
- 相邻两个列表如果前一个列表最大值小于下一个列表最小值,肯定无需合并,直接添加到空列表
- 否则找到这两个列表中的最大值,拓展区间
def merge(intervals):
intervals.sort(key=lambda x: x[0]) # 首先,我们将列表中的区间按照左端点升序排序
merged = []
for interval in intervals:
# 如果列表为空,或者 一个列表右边的值 < 下一个列表左边的元素
if not merged or merged[-1][1] < interval[0]:
merged.append(interval) # 直接添加,无需合并
else:
# 否则的话,我们就可以与上一区间进行合并, 右边值为两个列表右侧较大的值
merged[-1][1] = max(merged[-1][1], interval[1])
return merged
intervals = [[2,3],[1,6],[8,10],[15,18]]
print(merge(intervals)) # [[1, 6], [8, 10], [15, 18]]
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 21.搜索旋转排序数组
# 21.1 题目描述
整数数组
nums
按升序排列,数组中的值 互不相同nums
在预先未知的某个下标k
(0 <= k < nums.length
)上进行了 旋转给你 旋转后 的数组
nums
和一个整数target
,如果nums
中存在这个目标值target
,则返回它的索引,否则返回-1
原始数组:[0,1,2,4,5,6,7]
旋 转 后:[4,5,6,7,0,1,2]
输入:nums = [4,5,6,7,0,1,2], target = 0
输出:4
2
3
4
# 21.2 解题思路
- 可以发现的是,我们将数组从中间分开成左右两部分的时候,一定有一部分的数组是有序的
def search(nums, target):
if not nums:
return -1
l, r = 0, len(nums) - 1
while l <= r:
mid = (l + r) // 2
if nums[mid] == target:
return mid
# 如果 第一个元素 < 中间值 证明前半部分有序
if nums[0] <= nums[mid]:
# 如果目标元素 在前半部分,就移动右指针为 mid-1
if nums[0] <= target < nums[mid]:
r = mid - 1
else: # 否则移动左指针 为 mid+1
l = mid + 1
# 否则 后半部分有序
else:
# 如果目标元素 在后半部分,就移动左指针为 mid+1
if nums[mid] < target <= nums[len(nums) - 1]:
l = mid + 1
else: # 否则右指针为 mid - 1
r = mid - 1
return -1
target = 0
nums = [4,5,6,7,0,1,2]
print( search(nums, target) ) # 4
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# 22.数组中的第K个最大元素
数组中的第K个最大元素 (opens new window)
- 在未排序的数组中找到第 k 个最大的元素
- 请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素
例:寻找第二大元素
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
2
3
# 22.1 heapq模块找到前十大元素
- 1、取列表前10个元素建立一个小根堆,堆顶就是目前的10大的数(建立小根堆)
- 2、依次向后遍历原列表,对于列表中的元素,如果小于堆顶,则忽略该元素,如果大于堆顶,则将堆顶更换为该元素,并且对堆进行依次调整
- 3、遍历列表所有元素后,倒序弹出堆顶
def findKthLargest(nums, k):
import heapq
ret = heapq.nlargest(k, nums) # 使用heapq模块建立一个K大的堆
return ret[k-1]
nums = [3,2,1,5,6,4]
print( findKthLargest(nums,2) )
2
3
4
5
6
7
# 22.2 自己实现堆排实现
# !/usr/bin/env python
# -*- coding:utf-8 -*-
class Solution:
def sift(self, data, low, high):
''' 构造小根堆 : 堆中某节点的值总是不小于父节点的值
:param data: 传入的待排序的列表
:param low: 需要进行排序的那个小堆的根对应的号
:param high: 需要进行排序那个小堆最大的那个号
:return:
'''
root = low # i最开始创建堆时是最后一个有孩子的父亲对应根的号
child = 2 * root + 1 # j子堆左孩子对应的号
tmp = data[root] # tmp是子堆中原本根的值(拿出最高领导)
while child <= high: # 只要没到子堆的最后(每次向下找一层)孩子在堆里
if child + 1 <= high and data[child] > data[child + 1]: # 如果有右孩纸,且比左孩子更小
child += 1
if tmp > data[child]: # 如果孩子还比子堆原有根的值tmp小,就将孩子放到子堆的根
data[root] = data[child] # 孩子成为子堆的根
root = child # 孩子成为新父亲(向下再找一层)
child = 2 * root + 1 # 新孩子 (此时如果j<=high证明还有孩,继续找)
else:
break # 如果能干就跳出循环就会留出一个空位
data[root] = tmp # 最高领导放到父亲位置
def topn(self, nums, k):
# 1、构建10个数量的小根堆
heap = nums[0:k] # 先取10个元素
for i in range(k // 2 - 1, -1, -1): # 使用这10个元素构建出一个小根堆
self.sift(heap, i, k - 1)
# 2、找出li中前10大元素放入heap中
for i in range(k, len(nums)): # 依次取出剩下的元素
if nums[i] > heap[0]: # 如果新元素比堆顶元素大
heap[0] = nums[i] # 就将新元素替换堆顶元素
self.sift(heap, 0, k - 1) # 重新构建小根堆
# 3、利用堆排将这个小根堆倒序排列
for i in range(k - 1, -1, -1): # 上面的for循环已经找出了前十大元素,这里是排序
heap[0], heap[i] = heap[i], heap[0]
self.sift(heap, 0, i - 1)
print(heap) # [6, 5]
return heap[k - 1]
nums = [3, 2, 1, 5, 6, 4]
print(Solution().topn(nums, 2)) # 5
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46