算法笔记

summary

所以数组是非常繁杂的，也很难用几个固定的套路去定义它，只好常刷常新啦

how

**算法不是拼智商和天赋，算法是一种可以通过科学合理的方式训练出来的能力**

151 reverse words in a string

完全自己实现： ```go func reverseWords(s string) string { length := len(s) left, right := 0, length - 1

538 convert bst to greater tree

var sum int

416 partition equal subset sum

dp := make([]bool, target + 1) dp[0] = true

常见算法思想与方法

主要思想是利用两个指针（或称“变量索引”）在数据结构（通常为数组、链表或字符串）上进行遍历

search

它的目标是**快速定位一个目标元素在数组中的位置**，基本前提是数组必须已经排序，否则二分查找无法正确地工作

sort

在一个待排序序列里，元素往往不仅有用来比较大小的“关键字”，还附带其他属性，例如一组学生记录按成绩排序，成绩相同的同学原本在名单中的先后顺序就体现了他们在班级花名册中的位置

time and space complexity

换句话说，时间复杂度告诉我们一个算法运行多少步（或基本操作次数）随着问题规模 n 变化的**趋势**

array

* **连续内存存储**： 数组在内存中占用一块**连续**区域，每个元素的存储位置可以通过起始地址加上偏移量计算得到 * 所以我们不能单独删除数组中的某个元素，只能**覆盖**，也就是**移动其他元素的地址** * **下标**：数组的下标是**从0**开始的 * **固定大小**： 在大多数**静态数组**实现中（如 C 语言的数组、C++ 中的传统数组

binary tree

它的**基本特性**包括：

hash table

需要将 `key` 映射到 `[0, N)` 的整数范围，其中 `N` 是哈希表的桶（bucket）数量

linked list

主要类型有：

stack and queue

int main() { std::stack<int> st; // 底层默认是 deque<int> st.push(10); // 压入元素 st.push(20); std::cout << "栈顶元素: " << st.top() << "\n"; // 20 st.pop(); // 弹出 20 std::cout << "弹出后栈顶: " <<

string

从最底层来看，字符串其实就是**一段有序的字符序列**（在计算机中通常用字节序列或 Unicode 码点序列来表示），并且会以某种方式标明“结束”或“长度”

209 min len sub array

class Solution { public: int minSubArrayLen(int target, vector<int>& nums) { int slow = 0; int sum = 0; int results = INT_MAX; //宏 int length = 0;

26 delete reduplicative elements in a sorted array

class Solution { public: int removeDuplicates(vector<int>& nums) { int slow = 0; //没有修改初始值，导致数组索引越界 for (int fast = 0; fast < nums.size(); fast++) //没有修改初始值，导致数组索引越界 { if (nums[fas

27 delete elements

class Solution { public: int removeElement(vector<int>& nums, int val) { int slow = 0; //创建慢指针 for (int fast = 0; fast < nums.size(); fast++) { if (nums[fast] != val) //快指针先遍历 { nu

283 remove zero

class Solution { public: void moveZeroes(vector<int>& nums) { int slow = 0; for (int fast = 0; fast < nums.size(); fast++) { if (nums[fast] != 0) { swap(nums[slow], nums[fast]); //

34 find the first and last position of elements in a sorted array

class Solution { public: vector<int> searchRange(vector<int>& nums, int target) { int Left = findLeftBoundary(nums, target); int Right = findRightBoundary(nums, target); if (Left =

35 search insert location

class Solution { public: int searchInsert(vector<int>& nums, int target) { int left = 0; //和上一题代码基本没有什么大变化 int right = nums.size() - 1; while (left <= right) { //为了防止int越界，先计算左右边界的

367 valid perfect square numbers

class Solution { public: bool isPerfectSquare(int num) { int square = 0; if (num < 2) { square = num; } int left = 1; int right = num / 2; while (left <= right) { int mid = left +

59. spiral matrix ii

class Solution { public: vector<vector<int>> generateMatrix(int n) { // 初始化一个二维数组，这里是嵌套的，仔细分析即可弄清楚逻辑 // 有 n 行个 vector，每个 vector 有 n 列，每列都初始化为 0 vector<vector<int>> matrix(n, vector

69 x's square root

class Solution { public: int mySqrt(int x) { if (x < 2) //此时无论什么数都会直接返回1 { return x; } int left = 1; //防止出现0在分母 int right = x / 2; //提前缩小范围，提升效率 int result = 0; while (left <= righ

704 binary search

class Solution { public: int search(vector<int>& nums, int target) { int left = 0; int right = nums.size() - 1; //通过vector自带的size函数得到数组终点位置 while(left <= right) { // (right - left)

977 square of a sorted array

class Solution { public: vector<int> sortedSquares(vector<int>& nums) { int i = 0; while (i < nums.size()) { nums[i] = nums[i] * nums[i]; //溢出越界了 } int right = 0, left = 1; while (

array reflections

这道题主要是对**二分查找**概念的检验，以及如何在 cpp 中实现二分查找算法，通过将基本想法转化一下可得下面的细分步骤： - 创建 left、right 变量用于记录数组起始和结束位置 * left 初始为 0 * right 初始为数组长度减一 - 利用 while 循环，仅当 **left <= right** 时才进入 * 这里考虑使用左闭右闭区间

131 palindrome partitioning

func backtrack(s string, results *[][]string, path []string, start int) { if start == len(s) { temp := make([]string, len(path)) copy(temp, path) *results = append(*results, temp)

17 letter combinations of a phone number

mapping := map[byte]string{ '2': "abc", '3': "def", '4': "ghi", '5': "jkl", '6': "mno", '7': "pqrs", '8': "tuv", '9': "wxyz", }

216 combination sum iii

return results }

332 reconstruct itinerary

```

37 sudoku solver

```

39 combination sum

func combinationSum(candidates []int, target int) [][]int { sort.Ints(candidates)

40 combination sum ii

func combinationSum2(candidates []int, target int) [][]int { sort.Ints(candidates)

46 permutations

func backtrack(nums, path []int, res *[][]int, used []bool) { if len(path) == len(nums) { temp := make([]int, len(path)) copy(temp, path) *res = append(*res, temp) }

47 permutations ii

func permuteUnique(nums []int) [][]int { sort.Ints(nums) var res [][]int var path []int used := make([]bool, len(nums)) backtrack(nums, path, &res, used) return res }

491 non decreasing subsequences

func backtrack(nums, path []int, res *[][]int, start int) { if len(path) >= 2 { temp := make([]int, len(path)) copy(temp, path) *res = append(*res, temp) }

51 n queens

```

77 combinations

return results }

78 subsets

func backtrack(nums, path []int, res *[][]int, start int) { temp := make([]int, len(path)) copy(temp, path) *res = append(*res, temp)

90 subsets ii

func subsetsWithDup(nums []int) [][]int { var res [][]int var path []int sort.Ints(nums) backtrack(nums, path, &res, 0) return res }

93 restore ip addresses

func restoreIpAddresses(s string) []string { var results []string var path []string backtrack(&results, path, 0, s) return results }

backtracking reflections

[我的解答](https://github.com/EthanQC/my-learning-record/blob/main/data-structure-and-algorithm/problems-record/backtracking/77-combinations.md)

101 symmetric tree

return isMirror(root.Left, root.Right) }

102 binary tree level order traversal

var results [][]int queue := []*TreeNode{root} // 由于传入的 root 就是指针类型，这里也要用指针类型

104 maximum depth of binary tree

queue := []*TreeNode{root} depth := 0

105.construct binary tree from preorder and inorder traversal

idxMap := make(map[int]int, n) for i, v := range inorder { idxMap[v] = i }

106 construct binary tree from inorder and postorder traversal

idxMap := make(map[int]int, n) for i, v := range inorder { idxMap[v] = i }

107 binary tree level order traversal ii

var results [][]int queue := []*TreeNode{root}

108 convert sorted array to binary search tree

func build(nums []int, l, r int) *TreeNode { if l > r { return nil }

110 balanced binary tree

func checkHeight(node *TreeNode) int { if node == nil { return 0 }

111 minimum depth of binary tree

queue := []*TreeNode{root} depth := 0 levels := 0

112 path sum

remaining := targetSum - root.Val

113 path sum ii

return results }

116 populating next right pointers in each node

func connect(root *Node) *Node { if root == nil { return nil }

117 populating next right pointers in each node ii

func connect(root *Node) *Node { if root == nil { return nil }

144 binary tree preorder traversal

return results } ```

145 binary tree postorder traversal

var results []int results = append(results, postorderTraversal(root.Left)...) results = append(results, postorderTraversal(root.Right)...) results = append(results, root.Val)

199 binary tree right side view

var results []int queue := []*TreeNode{root}

222 count complete tree nodes

count := 0 queue := []*TreeNode{root}

226 invert binary tree

queue := []*TreeNode{root}

235 lowest common ancestor of a binary search tree

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode { for root != nil { if p.Val < root.Val && q.Val < root.Val { root = root.Left } else if p.Val > root.Val && q.Val > root.

236 lowest common ancestor of a binary tree

l := lowestCommonAncestor(root.Left, p, q) r := lowestCommonAncestor(root.Right, p, q)

257 binary tree paths

import "strconv"

404 sum of left leaves

var sum int

429 n ary tree level order traversal

func levelOrder(root *Node) [][]int { if root == nil { return nil }

450 delete node in a bst

if key < root.Val { root.Left = deleteNode(root.Left, key) return root } if key > root.Val { root.Right = deleteNode(root.Right, key) return root }

501 find mode in binary search tree

func bfs(node *TreeNode, arr *[]int) { if node == nil { return }

513 find bottom left tree value

var v int queue := []*TreeNode{root}

515 find largest value in each tree row

var results []int queue := []*TreeNode{root}

530 minimum absolute difference in bst

import "math"

617 merge two binary trees

if root2 == nil { return root1 }

637 average of levels in binary tree

var results []float64 queue := []*TreeNode{root}

654 maximum binary tree

maxIdx := 0 for i, _ := range nums { if nums[maxIdx] < nums[i] { maxIdx = i } }

669 trim a binary search tree

if root.Val < low { return trimBST(root.Right, low, high) } if root.Val > high { return trimBST(root.Left, low, high) }

700 search in a binary search tree

switch { case root.Val == val: return root case root.Val > val : return searchBST(root.Left, val) default: return searchBST(root.Right, val) } } ```

701 insert into a binary search tree

if root.Val > val { root.Left = insertIntoBST(root.Left, val) } else { root.Right = insertIntoBST(root.Right, val) }

94 binary tree inorder traversal

var results []int results = append(results, inorderTraversal(root.Left)...) results = append(results, root.Val) results = append(results, inorderTraversal(root.Right)...)

98 validate binary search tree

var prev *TreeNode

binary tree reflections

[我的解答](https://github.com/EthanQC/my-learning-record/blob/main/data-structure-and-algorithm/problems-record/binary-tree/144-binary-tree-preorder-traversal.md)

1035 uncrossed lines

for i := 1; i <= n; i++ { pre := 0

1049 last stone weight ii

dp := make([]bool, cap + 1) dp[0] = true for _, w := range stones { if w > cap { continue }

1143 longest common subsequence

for i := 1; i <= n; i++ { pre := 0

115 distinct subsequences

for i := 0; i < len(s); i++ { for j := m; j >= 1; j-- { if s[i] == t[j - 1] { dp[j] += dp[j - 1] } } }

121 best time to buy and sell stock

for i := 1; i < len(prices); i++ { if profit < prices[i] - minPrice { profit = prices[i] - minPrice }

122 best time to buy and sell stock ii

for i := 1; i < len(prices); i++ { preCash, preHold := cash, hold cash = max(preCash, preHold + prices[i]) hold = max(preHold, preCash - prices[i]) }

123 best time to buy and sell stock iii

buy1, sell1 := -prices[0], 0 buy2, sell2 := -prices[0], 0

139 word break

for i := 1; i <= n; i++ { for _, w := range wordDict { lw := len(w) if i >= lw && dp[i - lw] && s[i - lw : i] == w { dp[i] = true } } }

188 best time to buy and sell stock iv

if k >= n / 2 { ans := 0 for i := 1; i < n; i++{ diff := prices[i] - prices[i - 1] if diff > 0 { ans += diff } } return ans }

198 house robber

return pre1 } ```

213 house robber ii

a, b := r(nums[1 :]), r(nums[: n - 1]) if a > b { return a } return b }

279 perfect squares

for i := 1; i <= n; i++ { for j := 1; j * j <= i; j++ { if dp[i] > dp[i - j * j] + 1 { dp[i] = dp[i - j * j] + 1 } } }

300 longest increasing subsequence

dp, ans := make([]int, n), 0

309 best time to buy and sell stock with cooldown

hold, sold, rest := -prices[0], -prices[0], 0

322 coin change

for _, c := range coins { for j := c; j <= amount; j++ { if dp[j] > dp[j - c] + 1 { dp[j] = dp[j - c] + 1 } } }

337 house robber iii

func dfs(node *TreeNode) (notTake, take int) { if node == nil { return 0, 0 }

343 integer break

for i := 2; i <= n; i++ { max := 0 for j := 1; j < i; j++ { if max < j * (i - j) { max = j * (i - j) } if max < j * dp[i - j] { max = j * dp[i - j] } } dp[i] = max }

377 combination sum iv

for j := 1; j <= target; j++ { for _, n := range nums { if j >= n { dp[j] += dp[j - n] } } }

392 is subsequence

return i == len(s) } ```

474 ones and zeroes

for _, s := range strs { zeros, ones := 0, 0 for _, ch := range s{ if ch == '0' { zeros++ } else { ones++ } }

494 target sum

if (target + s) % 2 != 0 || abs(target) > s { return 0 } p := (target + s) / 2 dp := make([]int, p + 1) dp[0] = 1

509 fibonacci number

a, b := 0, 1 for i := 2; i <= n; i++ { a, b = b, a + b } return b } ```

518 coin change ii

for _, c := range coins { for j := c; j <= amount; j++{ dp[j] += dp[j - c] } }

53 maximum subarray

if currSum > maxSum { maxSum = currSum } } return maxSum } ```

583 delete operation for two strings

for i := 1; i <= n; i++ { pre := 0

62 unique paths

for i := 1; i < m; i++ { for j := 1; j < n; j++ { dp[i][j] = dp[i - 1][j] + dp[i][j - 1] } }

63 unique paths ii

for i := 1; i < m; i++ { if obstacleGrid[i][0] == 0 && dp[i - 1][0] == 1 { dp[i][0] = 1 } } for j := 1; j < n; j++ { if obstacleGrid[0][j] == 0 && dp[0][j - 1] == 1{ dp[0][j] = 1 }

647 palindromic substrings

for i := 0; i < n; i++ { t[i] = s[n - 1 - i] }

674 longest continuous increasing subsequence

return ans } ```

70 climbing stairs

a, b := 1, 2 for i := 3; i <= n; i++ { a, b = b, a+ b }

714 best time to buy and sell stock with transaction fee

cash, hold := 0, -prices[0] for i := 1; i < n; i++{ newCash, newHold := cash, hold

718 maximum length of repeated subarray

for i := 1; i <= n; i++ { for j := m; j >= 1; j-- { if nums1[i - 1] == nums2[j - 1] { dp[j] = dp[j - 1] + 1

72 edit distance

// 空串 -> word2[:j]：插 j 次 for j := 0; j <= m; j++ { dp[j] = j }

746 min cost climbing stairs

for i := 2; i < n; i++{ a, b = b, min(a, b) + cost[i] } return min(a, b) }

96 unique binary search trees

for i := 2; i <= n; i++ { total := 0 for j := 1; j <= i; j++ { total += dp[j - 1] * dp[i - j] } dp[i] = total }

dynamic programming reflections

[我的解答](https://github.com/EthanQC/my-learning-record/blob/main/data-structure-and-algorithm/problems-record/dynamic-programming/509-fibonacci-number.md)

1005 maximize sum of array after k negations

func largestSumAfterKNegations(nums []int, k int) int { sort.Ints(nums) for i := 0; i < len(nums) && nums[i] < 0 && k > 0; i++ { nums[i] = -nums[i] k-- } sort.Ints(nums) sum := 0 i

122 best time to buy and sell stock ii

return earn } ```

134 gas station

for i := 0; i < len(gas); i++ { gSum += gas[i] cSum += cost[i]

135 candy

sum, right := 0, 1 for i := n - 1; i >= 0; i-- { if i < n - 1 && ratings[i] > ratings[i + 1] { right++ } else { right = 1 }

376 wiggle subsequence

count, prediff := 1, 0 for i := 1; i < len(nums); i++ { diff := nums[i] - nums[i - 1] if (diff > 0 && prediff <= 0) || (diff < 0 && prediff >= 0) { count++ prediff = diff } }

406 queue reconstruction by height

func reconstructQueue(people [][]int) [][]int { sort.Slice(people, func(i, j int) bool { if people[i][0] != people[j][0] { return people[i][0] > people[j][0] } return people[i][1]

435 non overlapping intervals

func eraseOverlapIntervals(intervals [][]int) int { if len(intervals) == 0 { return 0 }

45 jump game ii

end, f, count := 0, 0, 0 for i, v := range nums { if f < i + v { f = i + v }

452 minimum number of arrows to burst balloons

func findMinArrowShots(points [][]int) int { if len(points) == 0 { return 0 }

455 assign cookies

func findContentChildren(g []int, s []int) int { sort.Ints(g) sort.Ints(s)

53 maximum subarray

if currSum > maxSum { maxSum = currSum } } return maxSum } ```

55 jump game

56 merge intervals

func merge(intervals [][]int) [][]int { if len(intervals) == 1 { return intervals }

738 monotone increasing digits

func monotoneIncreasingDigits(n int) int { s := strconv.Itoa(n) digits := []byte(s) mark := len(digits) for i := len(digits) - 1; i > 0; i-- { if digits[i] < digits[i - 1] { digits

763 partition labels

res, start, end := make([]int, 0), 0, 0 for i := 0; i < len(s); i++ { if last[s[i] - 'a'] > end { end = last[s[i] - 'a'] } if i == end { res = append(res, end - start + 1) start =

860 lemonade change

for _, v := range bills { switch v { case 5: five++ case 10: if five == 0 { return false } five-- ten++ case 20: if ten > 0 && five > 0 { ten-- five-- } else if five > 2 { five -=

968 binary tree cameras

var dfs func(node *TreeNode) int dfs = func(node *TreeNode) int { if node == nil { return COVERED }

greedy algorithm reflections

[我的解答](https://github.com/EthanQC/my-learning-record/blob/main/data-structure-and-algorithm/problems-record/greedy-algorithm/455-assign-cookies.md)

1 two sum

```go func twoSum(nums []int, target int) []int { seen := make(map[int]int, len(nums))

1002 find common characters

```go func commonChars(words []string) []string { counts := make([]int, 26)

15 3sum

```go import "sort"

18 4sum

```go import "sort"

202 happy number

```go func isHappy(n int) bool { visited := make(map[int]struct{})

242 valid anagram

```go func isAnagram(s string, t string) bool { counts := make([]int, 26)

349 intersection of two arrays

```go func intersection(nums1 []int, nums2 []int) []int { if len(nums1) > len(nums2) { return intersection(nums2, nums1) }

383 ransom note

```go func canConstruct(ransomNote string, magazine string) bool { if len(magazine) < len(ransomNote) { return false }

454 4sum ii

```go func fourSumCount(nums1 []int, nums2 []int, nums3 []int, nums4 []int) int { sum12 := make(map[int]int, len(nums1))

hash table reflections

[我的解答](https://github.com/EthanQC/my-learning-record/blob/main/data-structure-and-algorithm/problems-record/hash-table/242-valid-anagram.md)

142 linked list cycle ii

```go /** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */ func detectCycle(head *ListNode) *ListNode { fast, slow := head, head

160 intersection of two linked lists

```go /** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */ func getIntersectionNode(headA, headB *ListNode) *ListNode { pA, pB := hea

19 remove nth node from end of list

```go /** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */ func removeNthFromEnd(head *ListNode, n int) *ListNode { dummy := &ListNod

203 remove linked list elements

```cpp /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {

206 reverse linked list

```go /** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */ func reverseList(head *ListNode) *ListNode { cur := head var pre *ListNode

24 swap nodes in pairs

```go /** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */

707 design linked list

```cpp class MyLinkedList { private: class MyNode { public: int val; MyNode* next;

linked list reflections

[我的解答](https://github.com/EthanQC/my-learning-record/blob/main/data-structure-and-algorithm/problems-record/linked-list/203-remove-linked-list-elements.md)

42 trapping rain water

l, r := 0, n - 1 lM, rM := 0, 0 water := 0

496 next greater element i

for _, x := range nums2 { for len(stack) > 0 && x > stack[len(stack) - 1] { v := stack[len(stack) - 1] stack = stack[: len(stack) - 1] next[v] = x } stack = append(stack, x) } for

503 next greater element ii

for i := 0; i < n; i++ { ans[i] = -1 }

739 daily temperatures

for i := 0; i < n; i++ { for len(stack) > 0 && temperatures[i] > temperatures[stack[len(stack) - 1]] { j := stack[len(stack) - 1] stack = stack[: len(stack) - 1] ans[j] = i - j } s

84 largest rectangle in histogram

st := []int{} max := 0

monotonic stack reflections

[我的解答](https://github.com/EthanQC/my-learning-record/blob/main/data-structure-and-algorithm/problems-record/monotonic-stack/739-daily-temperatures.md)

1047 remove all adjacent duplicates in string

for i := 0; i < len(s); i++ { v := s[i]

150 evaluate reverse polish notation

func evalRPN(tokens []string) int { stack := make([]int, 0, len(tokens))

20 valid parentheses

if length % 2 == 1 { return false }

225 implement stack using queues

func (q *myQueue) Push(v int) { q.data = append(q.data, v) }

232 implement queue using stacks

func (s *myStack) Push(val int) { s.data = append(s.data, val) }

239 sliding window maximum

dq := make([]int, 0, k) results := make([]int, 0, length - k + 1)

347 top k frequent elements

for _, v := range nums { freq[v]++ }

stack and queue reflections

[我的解答](https://github.com/EthanQC/my-learning-record/blob/main/data-structure-and-algorithm/problems-record/stack-and-queue/232-implement-queue-using-stacks.md)

28 find the index of the first occurrence in a string

if m == 0 { return 0 } if n < m { return -1 }

344 reverse string

```go func reverseString(s []byte) { left, right := 0, len(s) - 1

459 repeated substring pattern

if length < 2 { return false }

541 reverse string ii

```go func reverse(ch []byte) { left, right := 0, len(ch) - 1

844 compare strings having backspace

错误代码1：

string reflections

[我的解答](https://github.com/EthanQC/my-learning-record/blob/main/data-structure-and-algorithm/problems-record/string/344-reverse-string.md)