TBH个人博客
剑指Offer II 刷题笔记（1）
tbghg
  2022-11-06 08:49:34   2022-11-06 08:49:34    3.4k 字  15 分钟

目前是二刷阶段，记录一下刷题的思路，记录下重点，方便以后复习，目前还没写多少，持续补充

整数

整数这里主要是位运算，常见知识点：

  1. 对于一个数num，num >> i & 1表示取第i位上的二进制值
  2. 设置ans二进制的第i位一般或运算：ans = 1 << i
  3. 异或两次后会自己抵消掉，相当于没干

004 只出现一次的数字

一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。

  • 1 <= nums.length <= 3 * 104
  • -2^31 <= nums[i] <= 2^31 - 1

方法一：map遍历

1
2
3
4
5
6
7
8
9
10
11
12
 func singleNumber(nums []int) int {
    freq := map[int]int{}
    for _, v := range nums {
        freq[v]++
    }
    for num, occ := range freq {
        if occ == 1 {
            return num
        }
    }
    return 0 // 不会发生，数据保证有一个元素仅出现一次
}
  • 时间复杂度：O(n)，其中 n 是数组的长度
  • 空间复杂度：O(n)

方法二：依次确定二进制位

最先想到的肯定是和3做一些变换，如果看每一个二进制的话，加起来然后与3取余，最后汇总就行了
go的话不像python，是不是有符号自己能定义，这点注意一下就行了

1
2
3
4
5
6
7
8
9
10
11
12
13
func singleNumber(nums []int) int {
    ans := int32(0)
    for i := 0; i < 32; i++ {
        total := int32(0)
        for _, num := range nums {
            total += int32(num) >> i & 1
        }
        if total%3 > 0 {
            ans = 1 << i
        }
    }
    return int(ans)
}

005 单词长度的最大乘积

给定一个字符串数组 words，请计算当两个字符串 words[i] 和 words[j] 不包含相同字符时，它们长度的乘积的最大值。假设字符串中只包含英语的小写字母。如果没有不包含相同字符的一对字符串，返回 0。

很怪的题目，不过可以发现只包含小写字母，但是map又不太行，那就考虑位运算，把他们对应的整数做个&

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func maxProduct(words []string) (ans int) {
    masks := make([]int, len(words))
    for i, word := range words {
        for _, ch := range word {
            masks[i] = 1 << (ch - 'a')
        }
    }
    for i, x := range masks {
        for j, y := range masks[i:] {
            if x&y == 0 && len(words[i])*len(words[j]) > ans {
                ans = len(words[i]) * len(words[j])
            }
        }
    }
    return ans
}

006 排序数组中两个数字之和

给定一个已按照 升序排列 的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target
整数数组的形式返回答案，数组里放对应下标，增大的顺序
假设数组中存在且只存在一对符合条件的数字，同时一个数字不能使用两次

1
2
3
输入：numbers = [1,2,4,6,10], target = 8
输出：[1,3]
解释：2 与 6 之和等于目标数 8 。因此 index1 = 1, index2 = 3

方法一：map

只有一对符合要求，遇事不决，map解决，但空间O(n)，并且数组已经排序而没用好这个性质

方法二：双指针

头(low)尾( `heigh)一块出发，二者的和记为sum，如果比target小，low++，大的话heigh--，相等直接输出。for循环条件是low<heigh
比较难考虑的是会不会错过去，可以这样想，反正low和heigh肯定会有第一个先到答案的位置，这个时候另一个必须根据sum和target的比较做配合，最后肯定能到相应的地方。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func twoSum(numbers []int, target int) []int {
    low, high := 0, len(numbers) - 1
    for low < high {
        sum := numbers[low] + numbers[high]
        if sum == target {
            return []int{low, high}
        } else if sum < target {
            low++
        } else {
            high--
        }
    }
    return []int{-1, -1}
}

方法三：二分查找

时间复杂度：O(nlog⁡n)，其中 n 是数组的长度。需要遍历数组一次确定第一个数，时间复杂度是 O(n)，寻找第二个数使用二分查找，时间复杂度是 O(log⁡n)
空间复杂度：O(1)

复杂度这块不如双指针，主要还是练习一下二分，目前不细说二分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func twoSum(numbers []int, target int) []int {
    for i := 0; i < len(numbers); i++ {
        low, high := i + 1, len(numbers) - 1
        for low <= high {
            mid := (high - low) / 2 + low
            if numbers[mid] == target - numbers[i] {
                return []int{i, mid}
            } else if numbers[mid] > target - numbers[i] {
                high = mid - 1
            } else {
                low = mid + 1
            }
        }
    }
    return []int{-1, -1}
}

数组

这块就要寄出我曾经总结的东西了：算法总结——数组，当初打算给大一写的，但似乎没啥人看，不过个人感觉很全面，主要参考的代码随想录

数组主要知识点：

  1. 二分查找（莫得办法，多练）
  2. 前缀和（一维二维）：计算给定区间的和
  3. 差分（一维二维）：某一特定范围内的所有值都加上或减去一个常数
  4. 双指针
  5. 滑动窗口
  6. 螺旋矩阵（就是跟着逻辑来）

建议先看我的算法总结(・∀・)ノ

007 数组中和为 0 的三个数

【典型的双指针】

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。

注意： 答案中不可以包含重复的三元组。

1
2
3
示例：
给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为： [ [-1, 0, 1], [-1, -1, 2] ]

思路：先排序，固定一个，另外俩双指针。

注意点：

  1. 但是固定的那个需要考虑去重，去重为了防止把之后的撅了，可以去和前一个比较
  2. 因为双指针遍历时碰到的答案不止一个，所以碰到正解后装入ans，left++（right–也行，反正就是离开舒适区），但是因为要去重，所以for l < r && nums[l] == n2内进行l++（n2指之前的nums[l]）
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
26
27
28
func threeSum(nums []int) (ans [][]int) {
    sort.Ints(nums)
    for i := 0 ; i < len(nums)-2 ; i++ {
        if nums[i] > 0 {
            continue
        }
        if i > 0 && nums[i] == nums[i-1] {
            continue
        }
        l,r := i+1,len(nums)-1
        n1 := nums[i]
        for l<r {
            n2,n3 := nums[l],nums[r]
            sum := n1+n2+n3
            if sum == 0 {
                ans = append(ans,[]int{n1,n2,n3})
                for l < r && nums[l] == n2 {
                    l++
                }
            } else if sum > 0 {
                r--
            } else {
                l++
            }
        }
    }
    return
}

008 和大于等于 target 的最短子数组

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

二分查找

算法总结——数组，当初总结的，二分查找模块挺细的

left<right时，一般left=mid+1，right=mid，而不是left=mid，right=mid-1，要不容易出现死循环

068 查找插入位置

给定一个排序的整数数组 nums 和一个整数目标值target ，请在数组中找到 target，并返回其下标。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func searchInsert(nums []int, target int) int {
    left, right := 0, len(nums)-1
    mid := (left + right) / 2
    for left <= right {
        if nums[mid] == target {
            return mid
        } else if nums[mid] < target {
            left++
        } else {
            right--
        }
        mid = (left + right) / 2
    }
    return left
}

069 山峰数组的顶部

符合下列属性的数组 arr 称为 山峰数组（山脉数组） ：

  • arr.length >= 3
  • 存在i(0 < i < arr.length - 1)
  • arr[0] < arr[1] < ... arr[i-1] < arr[i]
  • arr[i] > arr[i+1] > ... > arr[arr.length - 1]

给定由整数组成的山峰数组 arr ，返回任何满足 arr[0] < arr[1] < ... arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1] 的下标 i ，即山峰顶部。

  • 3 <= arr.length <= 104
  • 0 <= arr[i] <= 106
  • 题目数据保证 arr 是一个山脉数组

虽然形式变了，但是我们可以变换比较方式，还是用二分查找，left<=right时最后return是什么可能不太好理解，最好自己找些数对比对比就出来了，当然最好还是left<right，把区间当成左闭右开，这样直接无脑返回右就行了（但其实左右是相等的）

1
2
3
4
5
6
7
8
9
10
11
12
13
func peakIndexInMountainArray(arr []int) int {
    left, right := 0,len(arr)-2
    mid := (left+right)>>1
    for left <= right {
        if arr[mid] < arr[mid+1] {
            left = mid + 1
        } else {
            right = mid - 1
        }
        mid = (left+right)>>1
    }
    return left
}

sort.search使用模板
index := sort.Search(n int,f func(i int) bool) int
使用二分查找的方法，会从[0, n)中取出一个值index，index为[0, n)中最小的使函数f(index)为True的值，并且f(index+1)也为True
如果无法找到该index值，则该方法为返回n

例如：

1
2
3
4
5
6
func main() {
    a := []int{1,2,3,4,5}
    d := sort.Search(len(a), func(i int) bool { return a[i]>=3})
    fmt.Println(d)
}
// output 2
1
2
3
4
// 使用sort.search的做法
func peakIndexInMountainArray(arr []int) int {
    return sort.Search(len(arr)-1, func(i int) bool { return arr[i] > arr[i+1] })
}

070 排序数组中只出现一次的数字

给定一个只包含整数的有序数组 nums ，每个元素都会出现两次，唯有一个数只会出现一次，请找出这个唯一的数字。

你设计的解决方案必须满足 O(log n) 时间复杂度和 O(1) 空间复杂度。

方法一：全数组的二分查找

相对好想一些，这个是保证每次比较时根据索引与对应的位置比较

  • 如果 mid 是偶数，则比较 nums[mid] 和 nums[mid+1] 是否相等；
  • 如果 mid 是奇数，则比较 nums[mid−1] 和 nums[mid] 是否相等。

利用按位异或的性质，可以得到 mid 和相邻的数之间的如下关系，其中 ⊕ 是按位异或运算符：

  • 当 mid 是偶数时，mid+1=mid⊕1；
  • 当 mid 是奇数时，mid−1=mid⊕1。
1
2
3
4
5
6
7
8
9
10
11
12
func singleNonDuplicate(nums []int) int {
    low, high := 0, len(nums)-1
    for low < high {
        mid := low + (high-low)/2
        if nums[mid] == nums[mid^1] {
            low = mid + 1
        } else {
            high = mid
        }
    }
    return nums[low]
}

方法二：偶数下标的二分查找

保证索引都是偶数，每次比较直接与+1位置比较

通过mid -= mid & 1保证mid每次变为偶数

1
2
3
4
5
6
7
8
9
10
11
12
13
func singleNonDuplicate(nums []int) int {
    low, high := 0, len(nums)-1
    for low < high {
        mid := low + (high-low)/2
        mid -= mid & 1
        if nums[mid] == nums[mid+1] {
            low = mid + 2
        } else {
            high = mid
        }
    }
    return nums[low]
}

071 按权重生成随机数

给定一个正整数数组 w ，其中 w[i] 代表下标 i 的权重（下标从 0 开始），请写一个函数 pickIndex ，它可以随机地获取下标 i，选取下标 i 的概率与 w[i] 成正比。

例如，对于 w = [1, 3]，挑选下标 0 的概率为 1 / (1 + 3) = 0.25 （即，25%），而选取下标 1 的概率为 3 / (1 + 3) = 0.75（即，75%）。

也就是说，选取下标 i 的概率为 w[i] / sum(w)

方法：前缀和 + 二分查找

我人傻了，这思路，咋想出来的

例如[3,1,2,4]，求前缀和[3,4,6,10]，然后随机数落在1-10十个数之间，记这个数为x，再看看大于等于x的第一个位置是哪里，例如x=2，落在了1-2-3之间，所以3是选择的数。因为前缀和有序，且要查找第一个比x大的数，所以用二分查找。

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
26
27
28
29
30
31
32
type Solution struct {
    preSum []int
}
func Constructor(w []int) Solution {
    for i:=1;i<len(w);i++ {
        w[i] += w[i-1]
    }
    return Solution{w}
}

// 自己实现二分查找
func (s *Solution) PickIndex() int {
    target := rand.Intn(s.preSum[len(s.preSum)-1]) + 1
    left,right := 0,len(s.preSum)-1
    mid := (left+right)>>1
    for left < right {
        if s.preSum[mid] == target {
            return mid
        }else if s.preSum[mid] < target {
            left = mid + 1 
        } else {
            right = mid
        }
        mid = (left+right)>>1
    }
    return left
}
// 调用sort.SearchInts进行二分查找
func (s *Solution) PickIndex() int {
    target := rand.Intn(s.preSum[len(s.preSum)-1]) + 1
    return sort.SearchInts(s.preSum,target)
}

072 求平方根

给定一个非负整数 x ，计算并返回 x 的平方根，即实现 int sqrt(int x) 函数
正数的平方根有两个，只输出其中的正数平方根
如果平方根不是整数，输出只保留整数的部分，小数部分将被舍去

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 注意：要返回的是平方小于或等于x的第一个数
// 如果找不到合适的：
// left: 乘积大于x    right: 乘积小于x
func mySqrt(x int) int {
    left,right := 0,x
    mid := (left+right)>>1
    for left <= right {
        value := mid * mid
        if value == x {
            return mid
        }else if value < x {
            left = mid + 1
        } else {
            right = mid - 1
        }
        mid = (left+right)>>1
    }
    return right
}

073 狒狒吃香蕉

狒狒喜欢吃香蕉。这里有 n 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 h 小时后回来。

狒狒可以决定她吃香蕉的速度 k （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 k 根。如果这堆香蕉少于 k 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉，下一个小时才会开始吃另一堆的香蕉。

狒狒喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。

返回她可以在 h 小时内吃掉所有香蕉的最小速度 k（k 为整数）。

 评论
评论插件加载失败
正在加载评论插件
  1. 1. 整数
    1. 1.1. 004 只出现一次的数字
      1. 1.1.1. 方法一：map遍历
      2. 1.1.2. 方法二：依次确定二进制位
    2. 1.2. 005 单词长度的最大乘积
    3. 1.3. 006 排序数组中两个数字之和
      1. 1.3.1. 方法一：map
      2. 1.3.2. 方法二：双指针
      3. 1.3.3. 方法三：二分查找
  2. 2. 数组
    1. 2.1. 007 数组中和为 0 的三个数
    2. 2.2. 008 和大于等于 target 的最短子数组
  3. 3. 二分查找
    1. 3.1. 068 查找插入位置
    2. 3.2. 069 山峰数组的顶部
    3. 3.3. 070 排序数组中只出现一次的数字
      1. 3.3.1. 方法一：全数组的二分查找
      2. 3.3.2. 方法二：偶数下标的二分查找
    4. 3.4. 071 按权重生成随机数
      1. 3.4.1. 方法：前缀和 + 二分查找
    5. 3.5. 072 求平方根
    6. 3.6. 073 狒狒吃香蕉
  1. 1. 整数
    1. 1.1. 004 只出现一次的数字
      1. 1.1.1. 方法一：map遍历
      2. 1.1.2. 方法二：依次确定二进制位
    2. 1.2. 005 单词长度的最大乘积
    3. 1.3. 006 排序数组中两个数字之和
      1. 1.3.1. 方法一：map
      2. 1.3.2. 方法二：双指针
      3. 1.3.3. 方法三：二分查找
  2. 2. 数组
    1. 2.1. 007 数组中和为 0 的三个数
    2. 2.2. 008 和大于等于 target 的最短子数组
  3. 3. 二分查找
    1. 3.1. 068 查找插入位置
    2. 3.2. 069 山峰数组的顶部
    3. 3.3. 070 排序数组中只出现一次的数字
      1. 3.3.1. 方法一：全数组的二分查找
      2. 3.3.2. 方法二：偶数下标的二分查找
    4. 3.4. 071 按权重生成随机数
      1. 3.4.1. 方法：前缀和 + 二分查找
    5. 3.5. 072 求平方根
    6. 3.6. 073 狒狒吃香蕉