汇芳书院

专注计算机视觉、机器学习、分布式计算等领域, 兼聊投资、写作、生活

0%

发表于 更新于 分类于
本文字数： 4.4k 阅读时长 ≈ 4 分钟

第一种类型：买卖限制各一次

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

 

示例 1：

输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
示例 2：

输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。

暴力法 无法通过OJ

1
2
3
4
5
6
7
8
9
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        result = 0
        for i in range(len(prices)):
            for j in range(i+1, len(prices)):
                tmp = prices[j] - prices[i]
                if tmp > result:
                    result = tmp
        return result

一次遍历

因此，我们只需要遍历价格数组一遍，记录历史最低点，然后在每一天考虑这么一个问题：如果我是在历史最低点买进的，那么我今天卖出能赚多少钱？当考虑完所有天数之时，我们就得到了最好的答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        result = 0
        if len(prices) == 0:
            return result
        min_price = prices[0]
        for i in range(1, len(prices)):
            if prices[i] < min_price:
                min_price = prices[i]
            else:
                profit = prices[i] - min_price
                if profit > result:
                    result = profit
        return result

不限制买卖次数, 但是持有股票不超过1支

买卖股票的最佳时机 II
给定一个数组 prices ，其中 prices[i] 表示股票第 i 天的价格。

在每一天，你可能会决定购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以购买它，然后在 同一天 出售。
返回 你能获得的 最大 利润 。

 
示例 1:
输入: prices = [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
  随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

示例 2:
输入: prices = [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
  注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

示例 3:
输入: prices = [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

贪心算法

收集所有的上坡即可拿到所有的收益

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func maxProfit(prices []int) int {
    ans := 0
    for i := 1; i < len(prices); i++{
        ans += max(0, prices[i]-prices[i-1])
    }
    return ans

}

func max(x, y int) int{
    if x > y{
        return x
    }else{
        return y
    }
}

动态规划的思想

由于限制了每天的最多只能持有一只股票，所以每天手头可以拥有的股票数是0或1只。
分别用dp[i][0]、dp[i][1]表示第i天交易完成后手头有0和1只股票情况下的最大收益。
dp[i][0] = max(dp[i-1][1]+prices[i], dp[i-1][0])
dp[i][1] = max(dp[i-1][0]-prices[i], dp[i-1][1])

其中dp[0][0] = 0, dp[0][1] = -prices[0]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func maxProfit(prices []int) int {
    dp := make([][2]int, len(prices))
    dp[0][1] = -prices[0]
    for i := 1; i < len(prices); i++{
        dp[i][0] = max(dp[i-1][1]+prices[i], dp[i-1][0])
        dp[i][1] = max(dp[i-1][0]-prices[i], dp[i-1][1])
    }
    return dp[len(prices)-1][0]

}

func max(x, y int) int{
    if x > y{
        return x
    }else{
        return y
    }
}

限制只能交易2次

123. 买卖股票的最佳时机 III

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

 

示例 1:

输入：prices = [3,3,5,0,0,3,1,4]
输出：6
解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
  随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。
示例 2：

输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。  
  注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。  
  因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
示例 3：

输入：prices = [7,6,4,3,1]
输出：0
解释：在这个情况下, 没有交易完成, 所以最大利润为 0。
示例 4：

输入：prices = [1]
输出：0

动态规划

只允许交易两次，那么任意一天的状态可以分为5种：

  • 0次交易
  • 1次买入
  • 1次买入1次卖出
  • 1次交易 1次买入
  • 2次交易
    第一种情况收益为0，不考虑
    分别记为buy1，sell1，buy2，sell2，则转移方程为：
    buy1[i] = max(buy1[i-1], -prices[i])
    sell1[i] = max(sell1[i-1], buy[i-1]+prices[i])
    buy2[i] = max(buy2[i-1], sell1[i-1]-prices[i])
    sell2[i] = max(sell2[i-1], buy2[i-1]+prices[i])
    初始化值为：
    buy1[0] = -prices[0]
    sell1[0] = 0
    buy2=-prices[0]
    sell2=0
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
func maxProfit(prices []int) int {
    n := len(prices)
    buy1 := make([]int, n)
    sell1 := make([]int, n)
    buy2 := make([]int, n)
    sell2 := make([]int, n)
    buy1[0], sell1[0] = -prices[0], 0
    buy2[0], sell2[0] = -prices[0], 0
    // fmt.Println(buy1,sell1, buy2, sell2)
    for i := 1; i < len(prices);i++{
        buy1[i] = max(buy1[i-1], -prices[i])
        sell1[i] = max(sell1[i-1], buy1[i-1]+prices[i])
        buy2[i] = max(buy2[i-1], sell1[i-1]-prices[i])
        sell2[i] = max(sell2[i-1], buy2[i-1]+prices[i])
        // fmt.Println(i, -prices[i], buy1,sell1, buy2, sell2)
    }
    fmt.Println(sell1, sell2)
    return max(sell2[n-1], sell1[n-1])

}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

限制改为最多进行k次交易，仍然限制最多只能同时持有1只股票

这块还没有特别懂

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
33
34
35
36
37
38
39
func maxProfit(k int, prices []int) int {
    n := len(prices)
    if n == 0{
        return 0
    }
    buy := make([][]int, n)
    sell := make([][]int, n)
    for i, _ := range buy{
        buy[i] = make([]int, k+1)
        sell[i] = make([]int, k+1)
    }
    for i := 1; i <= k; i++ {
        buy[0][i] = math.MinInt64 / 2
        sell[0][i] = math.MinInt64 / 2
    }


    buy[0][0] = -prices[0]
    for i := 1; i < n; i++{
        buy[i][0] = max(buy[i-1][0], sell[i-1][0]-prices[i])
        
        for j := 1; j <= k; j++{
            buy[i][j] = max(buy[i-1][j], sell[i-1][j]-prices[i])
            sell[i][j] = max(sell[i-1][j], buy[i-1][j-1]+prices[i])
        }
    }
    return max(sell[n-1]...)

}

func max(a ...int) int{
    res := a[0]
    for _, v := range a{
        if v > res{
            res = v
        }
    }
    return res
}

发表于 更新于 分类于
本文字数： 3.9k 阅读时长 ≈ 4 分钟

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。  

示例 1:

输入：
[“MinStack”,”push”,”push”,”push”,”getMin”,”pop”,”top”,”getMin”]
[[],[-2],[0],[-3],[],[],[],[]]

输出：
[null,null,null,null,-3,null,0,-2]

解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); –> 返回 -3.
minStack.pop();
minStack.top(); –> 返回 0.
minStack.getMin(); –> 返回 -2.

辅助栈-python实现

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
class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = [math.inf]

    def push(self, val: int) -> None:
        self.stack.append(val)
        self.min_stack.append(min(val, self.getMin()))

    def pop(self) -> None:
        self.stack.pop()
        self.min_stack.pop()

    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return self.min_stack[-1]



# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()

辅助栈-go实现

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
type MinStack struct {
    stack []int
    minStack []int
    length int
}


func Constructor() MinStack {
    return MinStack{
        stack: []int{},
        minStack: []int{math.MaxInt64},
    }
}


func (this *MinStack) Push(val int)  {
    this.stack = append(this.stack, val)
    top := this.minStack[len(this.minStack)-1]
    this.minStack = append(this.minStack, min(top, val))
}


func (this *MinStack) Pop()  {
    this.stack = this.stack[:len(this.stack)-1]
    this.minStack = this.minStack[:len(this.minStack)-1]
}


func (this *MinStack) Top() int {
    return this.stack[len(this.stack)-1]
}


func (this *MinStack) GetMin() int {
    return this.minStack[len(this.minStack)-1]
}

func min(x, y int) int {
    if x < y {
        return x
    }
    return y
}

/**
 * Your MinStack object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Push(val);
 * obj.Pop();
 * param_3 := obj.Top();
 * param_4 := obj.GetMin();
 */

存储和最小值的差值

python实现

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class MinStack:
    def __init__(self):
        self.stack = []
        self.min_value = -1

    def push(self, val: int) -> None:
        if not self.stack:
            self.stack.append(0)
            self.min_value = val
            return
        diff = val - self.min_value
        # 当出现更小的数时，此时更新min_value
        if diff < 0:
            self.min_value = val
        self.stack.append(diff)

    def pop(self) -> None:
        if not self.stack:
            return None
        diff = self.stack.pop()
        top = self.min_value + diff
        # 弹出时为负数，此时最小值即为栈顶值
        if diff < 0:
            top = self.min_value
            self.min_value = self.min_value - diff
        return top

    def top(self) -> int:
        if not self.stack:
            return -1
        diff = self.stack[-1]
        top = self.min_value + diff
        if diff < 0:
            top = self.min_value
        return top

    def getMin(self) -> int:
        if not self.stack:
            return -1
        return self.min_value



# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()

go实现

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

type MinStack struct {
    stack []int
    minValue int
}


func Constructor() MinStack {
    return MinStack{
        stack: []int{},
        minValue: 0,
    }
}


func (this *MinStack) Push(val int)  {
    if len(this.stack) == 0{
        this.stack = append(this.stack, 0)
        this.minValue = val
    }else{
        diff := val - this.minValue
        this.stack = append(this.stack, diff)
        if diff < 0{
            this.minValue = val
        }
    }
}


func (this *MinStack) Pop()  {
    if len(this.stack) > 0{
        diff := this.stack[len(this.stack)-1]
        if diff < 0{
            this.minValue = this.minValue - diff
        }
        this.stack = this.stack[:len(this.stack)-1]
    }
}


func (this *MinStack) Top() int {
    if len(this.stack) > 0{
        diff := this.stack[len(this.stack)-1]
        if diff < 0{
            top := this.minValue
            return top
        }else{
            top := diff + this.minValue
            return top
        }
    }
    return -1
}



func (this *MinStack) GetMin() int {
    return this.minValue
}

/**
 * Your MinStack object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Push(val);
 * obj.Pop();
 * param_3 := obj.Top();
 * param_4 := obj.GetMin();
 */

发表于 更新于 分类于
本文字数： 6k 阅读时长 ≈ 5 分钟

33. 搜索旋转排序数组

整数数组 nums 按升序排列，数组中的值 互不相同 。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

 

示例 1：
输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4

示例 2：
输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1

示例 3：
输入：nums = [1], target = 0
输出：-1

python语言

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        low, high = 0, len(nums)-1
        # 将数组一分为二，其中一定有一个是有序的，另一个可能是有序，也能是部分有序。
        # 此时有序部分用二分法查找。无序部分再一分为二，其中一个一定有序，另一个可能有序，可能无序。就这样循环.
        while low <= high:
            mid = low + (high-low)//2
            print('low,high,mid', low, high, mid)
            if nums[mid] == target:
                return mid
            elif nums[low] <= nums[mid]:
                # 左半有序 且目标值在左部分
                if nums[low] <= target < nums[mid]:
                    high = mid - 1
                else:
                    low = mid + 1
            else:
                # 右半有序 且目标值在右部分
                if nums[high] >= target > nums[mid]:
                    low = mid + 1
                else:
                    high = mid - 1
        return -1

go语言

go的执行效率比python真是高太多了

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
func search(nums []int, target int) int {
    low, high := 0, len(nums)-1
    // 将数组一分为二，其中一定有一个是有序的，另一个可能是有序，也能是部分有序。
    // 此时有序部分用二分法查找。无序部分再一分为二，其中一个一定有序，另一个可能有序，可能无序。就这样循环.
    // fmt.Println(low, high)
    // print(low, high)
    for low <= high{
        mid := low + (high-low)/2
        // fmt.Println(low, mid, highc)
        if nums[mid] == target{
            return mid
        }else if nums[low] <= nums[mid]{    //左半数组有序, 注意<=
            if nums[low] <= target && target < nums[mid]{
                high = mid - 1
            }else{
                low = mid + 1
            }
        }else{
            if nums[high] >= target && target > nums[mid]{
                low = mid + 1
            }else{
                high = mid - 1
            }
        }
        // fmt.Println("-----", low, mid, high)
    }
    return -1

}

C++

旋转后，每次二分的时候，一定会得到一半是有序一半是无序的数组，如果目标值落在有序部分，则可以按照经典二分处理，否则在无序部分再二分

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
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int low = 0, high = nums.size()-1;
        while (low <= high) {
            int mid = low + (high-low)/2;
            if (target == nums[mid]) {
                return mid;
            }else if (nums[low] <= nums[mid]) {
                // 结果在左半边有序的这部分，注意包含左边界
                if (nums[low] <= target && target < nums[mid]) {
                    high = mid - 1;
                }else{
                    low = mid + 1;
                }
            }else{
                // 结果在右半边有序的这部分，注意包含右边界
                if (nums[mid] < target && target <= nums[high]) {
                    low = mid + 1;
                }else{
                    high = mid - 1;
                }
            }
        }
        return -1;
    }
};

81. 搜索旋转排序数组 II

已知存在一个按非降序排列的整数数组 nums ，数组中的值不必互不相同。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转 ，使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,4,4,5,6,6,7] 在下标 5 处经旋转后可能变为 [4,5,6,6,7,0,1,2,4,4] 。

给你 旋转后 的数组 nums 和一个整数 target ，请你编写一个函数来判断给定的目标值是否存在于数组中。如果 nums 中存在这个目标值 target ，则返回 true ，否则返回 false 。

你必须尽可能减少整个操作步骤。

 

示例 1：

输入：nums = [2,5,6,0,0,1,2], target = 0
输出：true
示例 2：

输入：nums = [2,5,6,0,0,1,2], target = 3
输出：false

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
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int low = 0, high = nums.size()-1;
        while (low <= high) {
            int mid = low + (high-low)/2;
            if (target == nums[mid]) {
                return true;
            // 核心在于 如果有重复的数，可能导致无法判断哪边是有序的
            }else if (nums[low] == nums[mid] && nums[high] == nums[mid]){
                low++;
                high--;
            }else if (nums[low] <= nums[mid]) {
                // 结果在左半边有序的这部分，注意包含左边界
                if (nums[low] <= target && target <= nums[mid]) {
                    high = mid - 1;
                }else{
                    low = mid + 1;
                }
            }else{
                // 结果在右半边有序的这部分，注意包含右边界
                if (nums[mid] <= target && target <= nums[high]) {
                    low = mid + 1;
                }else{
                    high = mid - 1;
                }
            }
        }
        return false;
    }
};

153. 寻找旋转排序数组中的最小值

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]
注意，数组 [a[0], a[1], a[2], …, a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], …, a[n-2]] 。

给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

 

示例 1：

输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。
示例 2：

输入：nums = [4,5,6,7,0,1,2]
输出：0
解释：原数组为 [0,1,2,4,5,6,7] ，旋转 4 次得到输入数组。
示例 3：

输入：nums = [11,13,15,17]
输出：11
解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。

提示：

n == nums.length
1 <= n <= 5000
-5000 <= nums[i] <= 5000
nums 中的所有整数 互不相同
nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int findMin(vector<int>& nums) {
        int ans = INT_MAX;
        int left = 0, right = nums.size()-1;
        while (left <= right) {
            int mid = left + (right-left)/2;
            // 左边有序，left即为左边最小值，需要去右边找
            if (nums[left] <= nums[mid]) {
                ans = min(ans, nums[left]);
                left = mid + 1;
            }else{
                // 右边有序，mid即为右边最小值，需要去左边找
                ans = min(ans, nums[mid]);
                right = mid - 1;
            }
        }
        // cout << left << " " << right << endl;
        return ans;


    }
};

154. 寻找旋转排序数组中的最小值 II

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,4,4,5,6,7] 在变化后可能得到：
若旋转 4 次，则可以得到 [4,5,6,7,0,1,4]
若旋转 7 次，则可以得到 [0,1,4,4,5,6,7]
注意，数组 [a[0], a[1], a[2], …, a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], …, a[n-2]] 。

给你一个可能存在 重复 元素值的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

你必须尽可能减少整个过程的操作步骤。

 

示例 1：

输入：nums = [1,3,5]
输出：1
示例 2：

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

提示：

n == nums.length
1 <= n <= 5000
-5000 <= nums[i] <= 5000
nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转

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
class Solution {
public:
    int findMin(vector<int>& nums) {
        int ans = INT_MAX;
        int left = 0, right = nums.size()-1;
        while (left <= right) {
            int mid = left + (right-left)/2;
            // 重复数字会导致无法判断左右哪边是否有序
            if (nums[left] == nums[mid] && nums[mid] == nums[right]) {
                ans = min(ans, nums[mid]);
                left++;
                right--;
            }else if (nums[left] <= nums[mid]) {
                ans = min(ans, nums[left]);
                left = mid + 1;
            }else{
                ans = min(ans, nums[mid]);
                right = mid - 1;
            }
        }
        return ans;


    }
};

还有一种逐渐逼近的思路，但是容易出错

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int findMin(vector<int>& nums) {
        int ans = INT_MAX;
        int left = 0, right = nums.size()-1;
        while (left <= right) {
            // 如果全局有序，直接返回
            if (nums[left] < nums[right]) return nums[left];
            int mid = left + (right-left)/2;
            // 重复数字会导致无法判断左右哪边是否有序
            if (nums[left] == nums[mid]) {
                left++;
            // 如果左边有序，由于全局无序，则右边必无序，最小值在右边
            }else if (nums[left] < nums[mid]) {
                left = mid + 1;
            // 左边无序，右边有序，mid即为右边最小值
            }else{
                right = mid;
            }
        }
        // cout << left << " " << right;
        return nums[right];
    }
};

发表于 更新于 分类于
本文字数： 422 阅读时长 ≈ 1 分钟

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。

注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

 

示例 1：

输入：x = 4
输出：2
示例 2：

输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842…, 由于返回类型是整数，小数部分将被舍去。

二分查找的方法

在0和x中查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func mySqrt(x int) int {
    l, r := 0, x
    ans := -1
    for l <= r{
        mid := l + (r-l)/2
        if mid*mid <= x{
            ans = mid
            l = mid + 1
        }else{
            r = mid - 1
        }
    }
    return ans
}

袖珍计算器算法

「袖珍计算器算法」是一种用指数函数 exp 和对数函数 ln 代替平方根函数的方法。我们通过有限的可以使用的数学函数，得到我们想要计算的结果。

发表于 更新于 分类于
本文字数： 1.6k 阅读时长 ≈ 1 分钟

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

 
示例 1：

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
示例 2：

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

输入：nums = [7,7,7,7,7,7,7]
输出：1

动态规划

C++语言版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int result = 0;
        // dp[j] 表示以j结尾的最长递增子序列的长度
        vector<int> dp(nums.size(), 1);
        for(int j = 0; j < nums.size(); j ++){
            for(int i = 0; i < j; i++){
                if(nums[i] < nums[j]){
                    dp[j] = max(dp[j], dp[i]+1);
                }
            }
            result = max(result, dp[j]);
        }
        return result;

    }
};

go语言版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func lengthOfLIS(nums []int) int {
    result := 0;
    length := len(nums);
    dp := make([]int, length);
    for j := 0; j < length; j++{
        dp[j] = 1;
        for i := 0; i < j; i++{
            if nums[i] < nums[j]{
                if dp[i]+1 > dp[j]{
                    dp[j] = dp[i]+1;
                }
            }
        }
        if dp[j] > result{
            result = dp[j];
        }
    }
    return result;

}

python3语言版本

1
2
3
4
5
6
7
8
9
10
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        result = 0
        dp = [1]*len(nums)
        for j in range(0, len(nums)):
            for i in range(0, j):
                if nums[i] < nums[j] and dp[i]+1 > dp[j]:
                    dp[j] = dp[i]+1
            result = dp[j] if dp[j] > result else result
        return result

二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        # 开一个栈，每次取栈顶元素top和读到的元素temp做比较，如果temp > top 则将temp入栈；如果temp < top则二分查找栈中的比temp大的第1个数，并用temp替换它。 最长序列长度即为栈的大小top。
        stack = list()
        for e in nums:
            if not stack or stack[-1] < e:
                stack.append(e)
            else:
                # 二分查找，寻找第一个大于e的数
                low = 0
                high = len(stack) - 1
                while low <= high:
                    mid = low + (high-low)//2
                    if e > stack[mid]:
                        low = mid + 1
                    else:
                        high = mid -1
                stack[low] = e
        return len(stack)

输出最长子序列个数

TODO

输出所有最长子序列

TODO

发表于 更新于 分类于
本文字数： 876 阅读时长 ≈ 1 分钟

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

递归的思路

但是这里面的细节需要一些优化才能通过OJ

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
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        if not preorder or not inorder:
            return None
        if len(preorder) <=1 or len(inorder) <= 1:
            return TreeNode(preorder[0])
        
        root_val = preorder[0]
        root = TreeNode(root_val)
        
        inorder_dict = {v:k for k, v in enumerate(inorder)}

        i = 0
        inorder_index = inorder_dict[root_val]
        left_tree_num = inorder_index
        right_tree_num = len(inorder) - inorder_index - 1
        
        root.left = self.buildTree(list(preorder[1:left_tree_num+1]), list(inorder[:inorder_index]))
        root.right = self.buildTree(list(preorder[1+left_tree_num:]), list(inorder[inorder_index+1:]))
        return root


迭代法

TODO

发表于 更新于 分类于
本文字数： 1.7k 阅读时长 ≈ 2 分钟

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

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

示例 1：

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

输入：nums = []
输出：[]
示例 3：

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

暴力法

无法通过OJ

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        result = list()
        for i in range(n):
            for j in range(i+1, n):
                for k in range(j+1, n):
                    if nums[i]+nums[j]+nums[k] == 0:
                        tmp = [nums[i], nums[j], nums[k]]
                        tmp.sort()
                        if tmp in result:
                            continue
                        result.append(tmp)
        return result

先排序然后双指针

j代表的循环，双指针，k均摊到每次需要移动1次，所以本轮循环时间复杂度为O(n)
排序时间复杂度O(nlogn), 两轮循环时间复杂度O(n^2)
整体取大值为时间复杂度O(n^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        result = list()
        nums.sort()

        for i in range(n):
            if i > 0 and nums[i] == nums[i-1]:
                continue
            # print(n,i)
            target = -nums[i]
            k = n - 1
            for j in range(i+1, n):
                # 需要保证j和前一个不同
                if j > i+1 and nums[j] == nums[j-1]:
                    continue
                # 选定i,j后选k
                while j < k and nums[k] + nums[j] > target:
                    k = k - 1
                if j == k:
                    break
                if nums[k] + nums[j] == target:
                    result.append([nums[i],nums[j],nums[k]])
        return result
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
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ans;
        int n = nums.size();

        sort(nums.begin(), nums.end());
        for (int i = 0; i < n; i++){
            if (i > 0 && nums[i] == nums[i-1]){
                continue;
            }
            int target = -nums[i];
            int k = n-1;
            for (int j = i+1; j < n; j++){
                if (j > i+1 && nums[j] == nums[j-1]){
                    continue;
                }
                while (j < k && nums[j] + nums[k] >target){
                    k = k - 1;
                }
                if (j == k){
                    break;
                }
                if (nums[j] + nums[k] == target){
                    ans.push_back({nums[i], nums[j], nums[k]});
                }
            }
        }
        return ans;

    }
};

发表于 更新于 分类于
本文字数： 1k 阅读时长 ≈ 1 分钟

给你一个字符串 s，找到 s 中最长的回文子串。

 

示例 1：

输入：s = “babad”
输出：”bab”
解释：”aba” 同样是符合题意的答案。
示例 2：

输入：s = “cbbd”
输出：”bb”

中心扩展法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def longestPalindrome(self, s: str) -> str:
        def helper(s, i, j):
            while i >= 0 and j < length and s[i] == s[j]:
                i = i - 1
                j += 1
            return i+1, j-1
        length = len(s)
        count = 0
        result = ""
        for i in range(length):
            left,right = helper(s, i, i+1)
            if right -left >= count:
                count = right - left
                result = s[left:right+1]
            # 这个地方比较巧妙
            left,right = helper(s, i, i)
            if right -left >= count:
                count = right - left
                result = s[left:right+1]
        return result

动态规划的方法

1.长度为1的串 必然为回文串
2.长度为2的串 如果字母相同也是回文串
3.如果s[i+1, j-1]是回文串且s[i]==s[j]则s[i, j]也是回文串

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
class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        if n < 2:
            return s
        
        dp = [[False]*n for _ in range(n)]
        max_length = 1
        left = 0
        # L 表示子串长度
        for L in range(1, n+1):
            # i表示左index，j表示右index
            for i in range(n):
                j = L + i - 1
                # j非法时，退出循环
                if j > n - 1:
                    break
                if s[i] != s[j]:
                    dp[i][j] = False
                else:
                    if L <= 2:
                        dp[i][j] = True
                    else:
                        dp[i][j] = dp[i+1][j-1]
                if dp[i][j] and L > max_length:
                    max_length = L
                    left = i
        return s[left:left+max_length]




Manacher算法

TODO

发表于 分类于
本文字数： 482 阅读时长 ≈ 1 分钟

斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1
给定 n ，请计算 F(n) 。

 

示例 1：

输入：n = 2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1
示例 2：

输入：n = 3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2
示例 3：

输入：n = 4
输出：3
解释：F(4) = F(3) + F(2) = 2 + 1 = 3

递归

1
2
3
4
5
6
7
class Solution:
    def fib(self, n: int) -> int:
        if n == 0:
            return 0
        if n == 1:
            return 1
        return self.fib(n-1) + self.fib(n-2)

动态规划+滚动数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def fib(self, n: int) -> int:
        if n == 0:
            return 0
        if n == 1:
            return 1

        p = 0
        q = 0
        r = 1
        for i in range(2, n+1):
            p = q
            q = r
            r = p + q
        return r

发表于 分类于
本文字数： 1.9k 阅读时长 ≈ 2 分钟

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

示例 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]

四次旋转模拟法

第一次：从左到右，横坐标不变，纵坐标+1
第二次：从上到下，纵坐标不变，横坐标+1
第三次：从右到左，横坐标不变，纵坐标-1
第四次：从下到上，纵坐标不变，横坐标-1

思路比较清晰，比较容易理解

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        rows = len(matrix)
        columns = len(matrix[0])
        total = rows * columns

        left = 0
        right = columns - 1
        top = 0
        bottom = rows - 1
        result = []
        while total > 0:
            for i in range(left, right+1):
                # 通过总数控制循环是否停止
                if total == 0:
                    break
                # print(top, i)
                result.append(matrix[top][i])
                total = total - 1
            # 每次循环完成后，某一个坐标需要改变
            top += 1

            for i in range(top, bottom+1):
                if total == 0:
                    break
                # print(i, right)
                result.append(matrix[i][right])
                total = total - 1
            right = right - 1

            for i in range(right, left-1, -1):
                if total == 0:
                    break
                # print(bottom, i)
                result.append(matrix[bottom][i])
                total = total - 1
            bottom = bottom - 1

            for i in range(bottom, top-1, -1):
                if total == 0:
                    break
                # print("----", i, left)
                result.append(matrix[i][left])
                total = total - 1
            left += 1
        return result

逻辑优化后的模拟

其实代码初始理解起来并不直观，但是写起来比较舒适

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
class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        rows = len(matrix)
        columns = len(matrix[0])
        total = rows * columns

        visited = [[False]*columns for _ in range(rows)]
        directions = [[0, 1], [1, 0], [0, -1], [-1, 0]]

        row = 0
        column = 0
        direction_index = 0
        result = []
        for i in range(total):
            result.append(matrix[row][column])
            visited[row][column] = True
            next_row = row + directions[direction_index][0]
            next_column = column + directions[direction_index][1]
            # 如果超出边界或者数据已经访问过，则表示需要转换规则
            if next_row >= rows or next_row < 0 or next_column >= columns or next_column < 0 or visited[next_row][next_column]:
                direction_index = (direction_index+1)%4
            
            row += directions[direction_index][0]
            column += directions[direction_index][1]
        return result

按层模拟

可以将矩阵看成若干层，首先输出最外层的元素，其次输出次外层的元素，直到输出最内层的元素。
定义矩阵的第 k 层是到最近边界距离为 k 的所有顶点。
访问完一层以后，再访问里面一层，也算是一个思路。但是其实没有第一种直观。

(略过, 后面再训练这种思路)

发表于 更新于 分类于
本文字数： 2.4k 阅读时长 ≈ 2 分钟

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

 

示例 1：

输入：s = [“h”,”e”,”l”,”l”,”o”]
输出：[“o”,”l”,”l”,”e”,”h”]
示例 2：

输入：s = [“H”,”a”,”n”,”n”,”a”,”h”]
输出：[“h”,”a”,”n”,”n”,”a”,”H”]  

双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        length = len(s)
        i = 0
        j = length - 1
        while i < j:
            s[i], s[j] = s[j], s[i]
            i = i + 1
            j = j - 1
        return s

C++版本

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    void reverseString(vector<char>& s) {
        int n = s.size();
        for (int i = 0, j = n-1; i < n/2; i++, j--){
            char tmp = s[i];
            s[i] = s[j];
            s[j] = tmp;
        }
    }
};

541. 反转字符串 II

给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。

如果剩余字符少于 k 个，则将剩余字符全部反转。
如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。  

示例 1：

输入：s = “abcdefg”, k = 2
输出：”bacdfeg”
示例 2：

输入：s = “abcd”, k = 2
输出：”bacd”  

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    string reverseStr(string s, int k) {
        int n = s.size();
        for (int i = 0; i < n; i += 2*k){
            reverse(s.begin()+i, s.begin()+min(i+k, n));
        }
        return s;
    }
};

557. 反转字符串中的单词 III

给定一个字符串 s ，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。

 

示例 1：

输入：s = “Let’s take LeetCode contest”
输出：”s’teL ekat edoCteeL tsetnoc”
示例 2:

输入： s = “God Ding”
输出：”doG gniD”

直接原地一趟翻转每个单词

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
class Solution {
public:
    string reverseWords(string s) {
        int n = s.size();
        int i = 0;
        while (i < n){
            int start = i;
            while (i < n && s[i] != ' '){
                i++;
            }

            int end = i - 1;
            // cout << start << " " << end << endl;
            while (start < end){
                swap(s[start], s[end]);
                start++;
                end--;
            }

            while (i < n && s[i] == ' '){
                i++;
            }
        }
        return s;
    }
};

NC89 字符串变形

描述
对于一个长度为 n 字符串，我们需要对它做一些变形。

首先这个字符串中包含着一些空格，就像”Hello World”一样，然后我们要做的是把这个字符串中由空格隔开的单词反序，同时反转每个字符的大小写。

比如”Hello World”变形后就变成了”wORLD hELLO”。

字符串中包括大写英文字母、小写英文字母、空格。
进阶：空间复杂度 O(n)O(n) ， 时间复杂度 O(n)O(n)

输入描述：
给定一个字符串s以及它的长度n(1 ≤ n ≤ 10^6)
返回值描述：
请返回变形后的字符串。题目保证给定的字符串均由大小写字母和空格构成。

示例1
输入：
“This is a sample”,16
返回值：
“SAMPLE A IS tHIS”

示例2
输入：
“nowcoder”,8
返回值：
“NOWCODER”

示例3
输入：
“iOS”,3
返回值：
“Ios”

两次翻转：先整体翻转，然后每个单词翻转

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    string trans(string s, int n) {
        reverse(s.begin(), s.end());
        int i = 0, j = 0;
        while (i < n){
            j = i;
            while (j < n && s[j] != ' '){
                if (s[j] >='a' && s[j] <= 'z')
                    s[j] += 'A' - 'a';
                else
                    s[j] -= 'A' - 'a';
                j++;
            }
            reverse(s.begin()+i, s.begin()+j);
            i = j + 1;
        }
        return s;
    }
};

发表于 更新于 分类于
本文字数： 1.4k 阅读时长 ≈ 1 分钟

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

递归的思路

公共祖先有两种情况：
1.因为p节点和q节点都是不同且唯一的节点, p和q分别位于左和右子树，则根节点为公共祖先
2.p或者q为根节点，另一个节点在左或右子树中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if not root:
            return root
        if root.val == p.val or root.val == q.val:
            return root
        left_node = self.lowestCommonAncestor(root.left, p, q)
        right_node = self.lowestCommonAncestor(root.right, p, q)
        if not left_node:
            return right_node
        if not right_node:
            return left_node

        if left_node and right_node:
            return root

哈希表存储父节点

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
33
34
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        def helper(root, father_dict):
            if not root:
                return 
            if root.left:
                father_dict[root.left.val] = root
                helper(root.left, father_dict)
            if root.right:
                father_dict[root.right.val] = root
                helper(root.right, father_dict)
        if not root:
            return
        father_dict = dict()
        father_dict[root.val] = None
        helper(root, father_dict)
        path = dict()
        while p:
            path[p.val] = 1
            p = father_dict[p.val]
        
        while q:
            if q.val in path:
                return q
            q = father_dict[q.val]

发表于 更新于 分类于
本文字数： 1.3k 阅读时长 ≈ 1 分钟

逆序

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

模拟法

思路比较清晰，按照加法的方式顺序处理即可

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
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        dummy = ListNode()
        p = dummy
        carry = 0
        while l1 or l2 or carry:
            l1_val = l1.val if l1 else 0
            l2_val = l2.val if l2 else 0
            tmp = l1_val + l2_val + carry
            l_tmp = ListNode(tmp%10)
            carry = tmp//10
            p.next = l_tmp
            p = l_tmp
            l1 = l1.next if l1 else None
            l2 = l2.next if l2 else None

        return dummy.next

顺序

给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

你可以假设除了数字 0 之外，这两个数字都不会以零开头。

同样是模拟法 不过需要考虑使用栈

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
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        l1_stack = []
        l2_stack = []
        while l1:
            l1_stack.append(l1.val)
            l1 = l1.next
        
        while l2:
            l2_stack.append(l2.val)
            l2 = l2.next
        
        carry = 0
        dummy = ListNode()
        while l1_stack or l2_stack or carry:
            l1_val = l1_stack.pop() if l1_stack else 0
            l2_val = l2_stack.pop() if l2_stack else 0
            tmp = l1_val + l2_val + carry
            tmp_Node = ListNode(tmp%10)
            carry = tmp//10
            tmp_Node.next = dummy.next
            dummy.next = tmp_Node
        
        return dummy.next

发表于 更新于 分类于
本文字数： 1.6k 阅读时长 ≈ 1 分钟

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：
题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

自定义评测：

评测系统 的输入如下（你设计的程序 不适用 此输入）：

intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0
listA - 第一个链表
listB - 第二个链表
skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数
skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数
评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。

直观解法

先计算长度，然后长链表先走，最后一起走

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        a = 0
        b = 0
        p = headA
        q = headB
        # 先计算各自长度
        while p:
            p = p.next
            a += 1

        while q:
            q = q.next
            b += 1
        
        p = headA
        q = headB
        print('a,b', a, b)
        c = a - b
        if c > 0:
            p = headA
            q = headB
        else:
            p = headB
            q = headA
            c = -c

        # 长链表先走，然后一起走 
        while c:
            if not p or not q:
                return None
            p = p.next
            c = c - 1
        while p and q:
            if p == q:
                return p
            p = p.next
            q = q.next
        return None

哈希集合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        a_dict = dict()
        while headA:
            a_dict[headA] = 1
            headA = headA.next
        
        while headB:
            if headB in a_dict:
                return headB
            else:
                headB = headB.next
        return None

双指针法，比较巧妙

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        pA = headA
        pB = headB
        while pA != pB:
            if not pA:
                pA = headB
            else:
                pA = pA.next
            if not pB:
                pB = headA
            else:
                pB = pB.next
        return pA

发表于 更新于 分类于
本文字数： 1.5k 阅读时长 ≈ 1 分钟

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，”ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。

两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

示例 1：
输入：text1 = “abcde”, text2 = “ace”
输出：3
解释：最长公共子序列是 “ace” ，它的长度为 3 。

示例 2：
输入：text1 = “abc”, text2 = “abc”
输出：3
解释：最长公共子序列是 “abc” ，它的长度为 3 。

示例 3：
输入：text1 = “abc”, text2 = “def”
输出：0
解释：两个字符串没有公共子序列，返回 0 。

动态规划的解法

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m = len(text1)
        n = len(text2)
        dp = [[0]*(n+1) for _ in range(m+1)]
        for i in range(1, m+1):
            for j in range(1, n+1):
                if text1[i-1] == text2[j-1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
        return dp[m][n]

输出最长子序列

输出所有的最长子序列

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
33
34
35
36
37
class Solution:
    def traceBack(self, i, j, text1, text2, dp, path, ans):
        while i > 0 and j > 0:
            if text1[i-1] == text2[j-1]:
                path.appendleft(text1[i-1])
                i = i - 1;
                j = j - 1;
            else:
                # 上方的大
                if dp[i-1][j] > dp[i][j-1]:
                    i = i - 1
                elif dp[i-1][j] < dp[i][j-1]:   # 左边大
                    j = j - 1
                else:
                    self.traceBack(i-1, j, text1, text2, dp, collections.deque(path), ans)
                    self.traceBack(i, j-1, text1, text2, dp, collections.deque(path), ans)
                    return
        ans.append(''.join(path))

                    

    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m = len(text1)
        n = len(text2)
        dp = [[0]*(n+1) for _ in range(m+1)]
        for i in range(1, m+1):
            for j in range(1, n+1):
                if text1[i-1] == text2[j-1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
        
        path = collections.deque()
        ans = []
        self.traceBack(m, n, text1, text2, dp, path, ans)
        print(ans)
        return dp[m][n]

发表于 更新于 分类于
本文字数： 2.1k 阅读时长 ≈ 2 分钟

给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。

暴力解法

这种解法过于粗暴，无法通过OJ

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def findLength(self, nums1: List[int], nums2: List[int]) -> int:
        ans = 0
        for i in range(len(nums1)):
            for j in range(len(nums2)):
                k = 0
                while i+k < len(nums1) and j+k < len(nums2) and nums1[i+k] == nums2[j+k]:
                    k += 1
                ans = max(ans, k)
        return ans


不太优雅的滑动窗口？

分别使用A数组的每一个数为起点与B数组比较，如果数字相同计数加1
然后交换A B重新比较

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
33
34
35
class Solution:
    def findLength(self, nums1: List[int], nums2: List[int]) -> int:
        m = len(nums1)
        n = len(nums2)
        ans = 0
        j = 0
        
        for offset in range(m):
            i = offset
            j = 0
            while i < m and j < n:
                count = 0
                while i < m and j < n and nums1[i] == nums2[j]:
                    count += 1
                    i += 1
                    j += 1
                j += 1
                i += 1
                ans = max(ans, count)
        
        for offset in range(n):
            j = offset
            i = 0
            while i < m and j < n:
                count = 0
                # print('i, j, count', i, j, count)
                while i < m and j < n and nums1[i] == nums2[j]:
                    count += 1
                    i += 1
                    j += 1
                j += 1
                i += 1
                ans = max(ans, count)
        
        return ans

滑动窗口

假设已经对齐了两个数组的起点，我们就可以对两个数组进行一趟遍历，求得最长的数组

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
class Solution:
    def findLength(self, nums1: List[int], nums2: List[int]) -> int:
        def helper(start1, start2, length):
            k = 0
            ans = 0
            for i in range(length):
                if nums1[start1+i] == nums2[start2+i]:
                    k += 1
                else:
                    k = 0
                ans = max(ans, k)
            return ans

        m = len(nums1)
        n = len(nums2)
        ans = 0
        for i in range(m):
            length = min(m-i, n)
            # 小优化，length如果小于ans，则无需比较了
            if length > ans:
                ans = max(ans, helper(i, 0, length))
        for i in range(n):
            length = min(n-i, m)
            if length > ans:
                ans = max(ans, helper(0, i, length))
        return ans

动态规划算法

dp[i][j] 表示长度为i，结尾index为i-1的nums1数组与长度为j，结尾index为j-1的nums2数组的最长公共子数组的长度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def findLength(self, nums1: List[int], nums2: List[int]) -> int:
        m = len(nums1)
        n = len(nums2)
        dp = [[0]*(n+1) for _ in range(m+1)]
        ans = 0
        for i in range(1, m+1):
            for j in range(1, n+1):
                if nums1[i-1] == nums2[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = 0
                ans = max(dp[i][j], ans)
        return ans

动态规划算法优化

发现上述dp其实每次只依赖上一行左上角的值，也就是内层循环。可以优化一下空间复杂度。
但是为了避免左上角的值被覆盖，内层循环需要从右向左计算。

可以将空间复杂度降低为O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def findLength(self, nums1: List[int], nums2: List[int]) -> int:
        m = len(nums1)
        n = len(nums2)
        dp = [0]*(n+1)
        ans = 0
        for i in range(1, m+1):
            for j in range(n, 0, -1):
                if nums1[i-1] == nums2[j-1]:
                    dp[j] = dp[j-1] + 1
                else:
                    dp[j] = 0
                ans = max(dp[j], ans)
        return ans

二分法+hash

TODO

输出子串

TODO

发表于 更新于 分类于
本文字数： 1.5k 阅读时长 ≈ 1 分钟

请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。

结果集双端队列，避免翻转

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
33
34
35
36
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        ans = []
        if not root:
            return ans
        queue = collections.deque()
        queue.append(root)
        flag = False
        while queue:
            length = len(queue)
            # 结果集也用双端队列，省去一次翻转动作
            result = collections.deque()
            for i in range(length):
                p = queue.popleft()
                if flag:
                    result.appendleft(p.val)
                else:
                    result.append(p.val)
                if p.left:
                    queue.append(p.left)
                if p.right:
                    queue.append(p.right) 
            ans.append(list(result))
            flag = not flag
        return ans




双端队列 奇偶层逻辑分离

可以实际画一个双端队列感受一下

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
33
34
35
36
37
38
39
40
41
42
43
44
45
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        ans = []
        if not root:
            return ans
        queue = collections.deque()
        queue.append(root)
        while queue:
            # 处理奇数层 从左向右打印 从左向右添加下层节点
            length = len(queue)
            result = list()
            for i in range(length):
                p = queue.popleft()
                result.append(p.val)
                if p.left:
                    queue.append(p.left)
                if p.right:
                    queue.append(p.right) 
            ans.append(list(result))
            if not queue:
                break
            
            # 处理偶数层 从右向左打印 从右向左添加下层节点
            length = len(queue)
            result = list()
            for i in range(length):
                p = queue.pop()
                result.append(p.val)
                if p.right:
                    queue.appendleft(p.right) 
                if p.left:
                    queue.appendleft(p.left)
            ans.append(list(result))
        return ans




发表于 更新于 分类于
本文字数： 683 阅读时长 ≈ 1 分钟

给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和并同样以字符串形式返回。

你不能使用任何內建的用于处理大整数的库（比如 BigInteger）， 也不能直接将输入的字符串转换为整数形式。

 

示例 1：

输入：num1 = “11”, num2 = “123”
输出：”134”
示例 2：

输入：num1 = “456”, num2 = “77”
输出：”533”
示例 3：

输入：num1 = “0”, num2 = “0”
输出：”0”

大数加法

模拟的思路

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
class Solution:
    def addStrings(self, num1: str, num2: str) -> str:
        if not num1:
            return num2
        if not num2:
            return num1
        i = len(num1)-1
        j = len(num2)-1
        carry = 0
        result = ""
        while i >= 0 or j >= 0 or carry:
            if i >= 0:
                first = num1[i]
            else:
                first = 0
            if j >= 0:
                second = num2[j]
            else:
                second = 0
            # print('i, j', i, j)
            # print('first, second, carry', first, second, carry)
            tmp = int(first) + int(second) + carry
            result = str(tmp%10) + result
            carry = tmp // 10
            i = i - 1
            j = j - 1
        return result


发表于 更新于 分类于
本文字数： 1.6k 阅读时长 ≈ 1 分钟

剑指 Offer 22. 链表中倒数第k个节点

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。

例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

 

示例：

给定一个链表: 1->2->3->4->5, 和 k = 2.

返回链表 4->5.

双指针法

让fast和slow均指向dummy，然后先让fast走k步，然后二者一起走，k为NULL时，slow到达目的地。

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        if (k <= 0) {
            return NULL;
        }
        ListNode *dummy = new ListNode(0);
        dummy->next = head;
        ListNode *fast = dummy, *slow = dummy;
        while (k > 0 && fast != NULL) {
            fast = fast->next;
            k--;            
        }
        if (fast == NULL) {
            return NULL;
        }
        while (fast != NULL) {
            fast = fast->next;
            slow = slow->next;
        }
        return slow;

    }
};

19. 删除链表的倒数第 N 个结点

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
示例 2：

输入：head = [1], n = 1
输出：[]
示例 3：

输入：head = [1,2], n = 1
输出：[1]  

提示：

链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

双指针思路

先让一个节点early早点出发，先走N步，然后再让另一个节点normal一起走。
当early节点走到链表结尾的时候，另一个节点normal就是需要被删除的节点。
注意记录normal节点的上一个节点

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
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        dummy = ListNode()
        dummy.next = head

        early = dummy
        while early and n > 0:
            early = early.next
            n = n - 1

        normal = dummy
        prev = dummy
        while early:
            prev = normal
            normal = normal.next
            early = early.next
        # print(early, normal)
        prev.next = normal.next
        del normal
        return dummy.next

使用栈

略

计算长度

略

发表于 更新于 分类于
本文字数： 637 阅读时长 ≈ 1 分钟

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。  

示例 1：

输入：s = “()”
输出：true
示例 2：

输入：s = “()[]{}”
输出：true
示例 3：

输入：s = “(]”
输出：false
示例 4：

输入：s = “([)]”
输出：false
示例 5：

输入：s = “{[]}”
输出：true  

提示：

1 <= s.length <= 104
s 仅由括号 ‘()[]{}’ 组成

和表达式计算器类似，考虑使用栈来实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def isValid(self, s: str) -> bool:
        # 若长度为偶数, 必然不是合法串
        if len(s) % 2 != 0:
            return False
        stack = []
        pairs = {
            ')': '(',
            ']': '[',
            '}': '{',
        }
        for e in s:
            # 碰到右括号则一定要有对应的左括号
            if e in pairs:
                if stack and stack.pop() == pairs[e]:
                    continue
                else:
                    return False
            else:
                stack.append(e)
        # 最后如果有落单的左括号，则非法
        return not stack

发表于 更新于 分类于
本文字数： 1.9k 阅读时长 ≈ 2 分钟

1.判断单链表是否有环

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

使用hash表标记法

遍历一次链表，用hash表记录已访问的链表，如果遍历中第二次出现已访问的元素，则证明存在环

快慢指针

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
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        if not head:
            return False
        # 构建虚拟节点
        dummy = ListNode()
        dummy.next = head
        # 慢指针一次走一步，快指针一次走两步
        slow = dummy.next
        fast = dummy.next.next
        while slow != fast:
            # 若无环，则快指针必然会先到达链表尾部
            if not fast or not fast.next:
                return False
            slow = slow.next
            fast = fast.next.next
        return True



2.寻找环的入口

给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        exists = dict()
        while head:
            if head in exists:
                return head
            exists[head] = 1
            head = head.next
        return None

快慢指针

设链表中环外部分的长度为 a。
slow指针进入环后，又走了 b 的距离与fast 相遇。
此时，fast 指针已经走完了环的 n 圈，因此它走过的总距离为 a+n(b+c)+b=a+(n+1)b+nc

根据题意，任意时刻，fast 指针走过的距离都为slow 指针的 2 倍。因此，有:
a+(n+1)b+nc=2(a+b) ⟹ a=c+(n−1)(b+c)

有了 a=c+(n-1)(b+c) 的等量关系，我们会发现：
从相遇点到入环点的距离加上 n-1圈的环长，恰好等于从链表头部到入环点的距离。

因此，当发现slow 与 fast 相遇时，我们再额外使用一个指针p。起始，它指向链表头部；随后，它和slow 每次向后移动一个位置。最终，它们会在入环点相遇。

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
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        if not head:
            return None
        dummy = ListNode()
        dummy.next = head
        slow = dummy.next
        fast = dummy.next.next
        p = dummy
        # 当slow和fast相遇时，p和slow继续前进后一定会在环入口处相遇
        while slow:
            if not fast or not fast.next:
                return None
            slow = slow.next
            fast = fast.next.next

            if slow == fast:
                while p != slow:
                    p = p.next
                    slow = slow.next
                return p
        return None

发表于 更新于 分类于
本文字数： 741 阅读时长 ≈ 1 分钟

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:
输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

示例 2:
输入: s = “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。

示例 3:
输入: s = “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
  请注意，你的答案必须是 子串 的长度，”pwke” 是一个子序列，不是子串。  

提示：
0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成

队列方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        result = []
        count = 0
        ans = 0
        for e in s:
            while e in result:
                result.pop(0)
                count = count - 1
            result.append(e)
            count += 1
            ans = max(count, ans)
        return ans

双指针的思路

使用队列，在查找效率方面比较低，改为双指针。
时间复杂度O(n), 空间复杂度O(k)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        allchar = dict()
        ans = 0
        i =0
        j = 0
        while j < len(s):
            while s[j] in allchar:
                allchar.pop(s[i])
                i += 1
            allchar[s[j]] = j
            count = j - i + 1
            j += 1
            ans = max(ans, count)
        return ans


发表于 更新于 分类于
本文字数： 1.3k 阅读时长 ≈ 1 分钟

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组 是数组中的一个连续部分。

 

示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：
输入：nums = [1]
输出：1

示例 3：
输入：nums = [5,4,-1,7,8]
输出：23  

提示：
1 <= nums.length <= 105
-104 <= nums[i] <= 104

动态规划的思想

假设nums 数组的长度是 n，下标从 0 到 n−1。
我们用 f(i) 代表以第 i个数结尾的「连续子数组的最大和」
则f(i) = max{f(i-1)+nums[i], nums[i]}
最后，求出这里面的最大值即可。
时间复杂度和空间复杂度均为O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        if not nums:
            return 0
        result = nums[0]
        f = [nums[0]]
        for i in range(1, len(nums)):
            tmp = f[i-1] + nums[i]
            if tmp >= nums[i]:
                f.append(tmp)
            else:
                f.append(nums[i])
        return max(f)

考虑到题目中只需要求出最大值即可，可以对空间复杂度做一些优化

1
2
3
4
5
6
7
8
9
10
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        if not nums:
            return 0
        result = nums[0]
        f = nums[0]
        for i in range(1, len(nums)):
            f = max(f+nums[i], nums[i])
            result = max(f, result)
        return result

如果需要打印出这个子数组

可以记录最大子数组的结尾序号，然后倒序查找和为最大值的数组

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
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        if not nums:
            return 0
        result = nums[0]
        f = nums[0]
        maxIndex = 0
        for i in range(1, len(nums)):
            tmp = f + nums[i]
            if tmp >= nums[i]:
                f = tmp
            else:
                f = nums[i]
            if f > result:
                result = f
                maxIndex = i
        # print(f,maxIndex)
        resultList = []
        for i in range(maxIndex, -1, -1):
            if sum(resultList) == result:
                print(resultList)
                break
            else:
                resultList.insert(0, nums[i])
        return result

分治法: 线段树

发表于 更新于 分类于
本文字数： 964 阅读时长 ≈ 1 分钟

可以借鉴以前的反转链表的代码，然后分别一组一组的反转。
属于细节题目，适合反复训练

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head, tail):
        if not head:
            return head
        # 注意这里需要保留与tail之后数据的连接
        pre = tail.next
        p = head
        while pre != tail:
            q = p.next
            p.next = pre
            pre = p
            p = q
        return pre, head

    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        dummy = ListNode()
        dummy.next = head
        left = dummy
        tail = dummy
        # print('left,right,head',left.val, right.val,head.val)
        while head:
            for i in range(k):
                tail = tail.next
                if not tail:
                    return dummy.next
            # print('head,tail',head,tail)
            # 开始翻转前先记录被翻转部分的左右两部分
            right = tail.next
            new_head, new_tail = self.reverseList(head, tail)
            # print('new_head,new_tail',new_head,new_tail)
            # 翻转后的新链表连接到原链表中间
            left.next = new_head
            new_tail.next = right

            # 重新初始化待翻转链表的head、tail以及左半部分
            head = new_tail.next
            tail = new_tail

            left = new_tail
        return dummy.next


发表于 更新于 分类于
本文字数： 649 阅读时长 ≈ 1 分钟

青蛙爬上最后一级台阶的时候，可能是一次跳了一步，也可能是一次跳了两步
所以方案数f(n) = f(n-1) + f(n-2)

递归的方法

超时无法通过OJ，

1
2
3
4
5
6
7
class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 0 or n == 1:
            return 1
        if n == 2:
            return 2
        return self.climbStairs(n-1) + self.climbStairs(n-2)

动态规划的方法

时间复杂度和空间复杂度都是O(n)

1
2
3
4
5
6
7
8
9
10
class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 0 or n == 1:
            return 1
        result = [1] * (n+1)
        result[2] = 1
        for i in range(2, n+1):
            result[i] = result[i-1] + result[i-2]
        return result[n]

考虑到其实每次只需要结果值的前两个值，所以我们可以用p,q,r轮动的方式去推进
可以降低空间复杂度到O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 0 or n == 1:
            return 1
        p = 0
        q = 0
        r = 1
        for i in range(1, n+1):
            p = q
            q = r
            r = p + q
        return r

还有矩阵快速幂的方法

如果一个问题可与转化为求解一个矩阵的 n次方的形式，那么可以用快速幂来加速计算

还可以求通项公式

发表于 分类于
本文字数： 593 阅读时长 ≈ 1 分钟

队头插入：每次直接压入左边的栈即可
队尾删除：若右栈不为空，则直接弹出一个值即可；若右栈为空，则将左栈先全部入右栈，再弹出一个数

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
class CQueue:

    def __init__(self):
        self.left_stack = list()
        self.right_stack = list()


    def appendTail(self, value: int) -> None:
        self.left_stack.append(value)


    def deleteHead(self) -> int:
        if not self.right_stack and not self.left_stack:
            return -1
        if not self.right_stack:
            while self.left_stack:
                self.right_stack.append(self.left_stack.pop())
            return self.right_stack.pop()
        else:
            return self.right_stack.pop()
            



# Your CQueue object will be instantiated and called as such:
# obj = CQueue()
# obj.appendTail(value)
# param_2 = obj.deleteHead()

发表于 分类于
本文字数： 942 阅读时长 ≈ 1 分钟

迭代方法直接处理

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
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode()
        cur = dummy
        while list1 and list2:
            if list1.val < list2.val:
                r = list1
                list1 = list1.next
            else:
                r = list2
                list2 = list2.next
            # print(r.val, cur.val)
            cur.next = r
            cur = r
        while list1:
            cur.next = list1
            break
        while list2:
            cur.next = list2
            break
        return dummy.next

递归方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        if not list1:
            return list2
        if not list2:
            return list1
        if list1.val < list2.val:
            list1.next = self.mergeTwoLists(list1.next, list2)
            return list1
        else:
            list2.next = self.mergeTwoLists(list1, list2.next)
            return list2

发表于 更新于 分类于
本文字数： 1.1k 阅读时长 ≈ 1 分钟

暴力解法

1
2
3
4
5
6
7
8
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        n = len(nums)
        for i in range(n):
            for j in range(i+1, n):
                if nums[i] + nums[j] == target:
                    return [i, j]
        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        std::vector<int> ans;
        for (int i = 0; i < nums.size(); i++) {
            for (int j = i + 1; j < nums.size(); j++){
                if (nums[i] + nums[j] == target){
                    return std::vector<int>{i, j};
                }
            }
            
        }
        return ans;
        
    }
};

哈希表

阅读全文 »

发表于 更新于 分类于
本文字数： 1.7k 阅读时长 ≈ 2 分钟

快排划分的思想。

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
class Solution:
    def partition(self, nums, left, right):
        pivot = left
        index = left + 1
        for i in range(index, right+1):
            # print('left,right,i', left, right, i)
            if nums[i] > nums[pivot]:
                self.swap(nums, i, index)
                index += 1
        self.swap(nums, pivot, index-1)
        return index-1
            
    def swap(self, nums, i, j):
        nums[i],nums[j] = nums[j], nums[i]
    
    def partitionK(self, nums, left, right, k):
        index = self.partition(nums, left, right)
        length = index-left+1
        # 如果已划分的个数length大于需要找的数k, 则在index左半部分重新找k个数
        if length > k:
            self.partitionK(nums, left, index-1, k)
        # 如果已划分的个数length小于需要找的数k, 则在index右半部分再找k-length个数即可
        if length < k:
            self.partitionK(nums, index+1, right, k-length)

    def findKthLargest(self, nums: List[int], k: int) -> int:
        self.partitionK(nums, 0, len(nums)-1, k)
        return nums[k-1]

上面的partitionK可以改为迭代的写法

1
2
3
4
5
6
7
8
9
10
11
def partitionK(self, nums, left, right, k):
        while left < right:
            index = self.partition(nums, left, right)
            length = index-left+1
            if k == length:
                break
            if k < length:
                right = index -1
            if k > length:
                left = index + 1
                k = k - length
阅读全文 »

发表于 更新于 分类于
本文字数： 1.6k 阅读时长 ≈ 1 分钟

1.快排划分思路的解法

特别注意k=0的情况

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
class Solution:
    def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
        if not arr or k == 0:
            return []
        self.partitionK(arr, 0, len(arr)-1, k)
        return arr[:k]

    def partitionK(self, nums, l, r, k):
        index = self.partition(nums, l, r)
        length = index - l + 1
        # print("index,nums,l,r,k, length",index,nums,l,r,k, length)
        if k > length:
            self.partitionK(nums, index+1, r, k-length)
        if k < length:
            self.partitionK(nums, l, index-1, k)

    def partition(self, nums, l, r):
        self.swap(nums, l, l+(r-l)//2)
        # print("partition,nums", nums)
        pivot = l
        index = l+1
        for i in range(index, r+1):
            # print('i,index,nums', i,index,nums)
            if nums[i] < nums[pivot]:
                self.swap(nums, index, i)
                index += 1
        # print("partition2,nums", nums)
        self.swap(nums, pivot, index-1)
        return index-1

    def swap(self, nums, i, j):
        nums[i],nums[j] = nums[j], nums[i]
阅读全文 »

发表于 更新于 分类于
本文字数： 15k 阅读时长 ≈ 14 分钟

102. 二叉树的层序遍历

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

 

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]
示例 2：

输入：root = [1]
输出：[[1]]
示例 3：

输入：root = []
输出：[]  

递归的解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        result = []
        if not root:
            return result
        self.helper(root, 0, result)
        return result

    def helper(self, root, level, result):
        if len(result) == level:
            result.append([])
        result[level].append(root.val)
        if root.left:
            self.helper(root.left, level+1, result)
        if root.right:
            self.helper(root.right, level+1, result)

使用dummy标记进行迭代

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
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        result = []
        if not root:
            return result
        dummy = TreeNode()
        p = root
        queue = [root, dummy]
        level = []
        while queue:
            # print("queue,p", [e.val for e in queue],p.val)
            p = queue.pop(0)
            if p != dummy:
                level.append(p.val)
                if p.left:
                    queue.append(p.left)
                if p.right:
                    queue.append(p.right)
            else:
                result.append(list(level))
                level = []
                # 若队列中已无数据，则不再添加标记节点
                if queue:
                    queue.append(dummy)
        return result

迭代：每次直接遍历一层的数据

我们可以用一种巧妙的方法修改广度优先搜索：
首先根元素入队
当队列不为空的时候:
求当前队列的长度Si
依次从队列中取 Si个元素进行拓展，然后进入下一次迭代

它和普通广度优先搜索的区别在于，普通广度优先搜索每次只取一个元素拓展，而这里每次取 Si个元素。

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
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        result = []
        if not root:
            return result
        p = root
        queue = [root]
        while queue:
            levelQueue = []
            level = len(queue)
            # print("queue, level", [e.val for e in queue], level)
            for i in range(level):
                p = queue.pop(0)
                levelQueue.append(p.val)
                if p.left:
                    queue.append(p.left)
                if p.right:
                    queue.append(p.right)
            result.append(list(levelQueue))
        return result

C++版本，2022年5月2日重刷

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
33
34
35
36
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        if (root == nullptr) {
            return ans;
        }
        queue<TreeNode*> q;
        q.emplace(root);
        while (!q.empty()) {
            vector<int> level;
            int size = q.size();
            for (int i = 0; i < size; i++) {
                TreeNode* node = q.front(); q.pop();
                level.emplace_back(node->val);
                if (node->left) q.emplace(node->left);
                if (node->right) q.emplace(node->right);
            }
            ans.emplace_back(level);
        }
        return ans;

    }
};

103. 二叉树的锯齿形层序遍历

给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

 

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[20,9],[15,7]]
示例 2：

输入：root = [1]
输出：[[1]]
示例 3：

输入：root = []
输出：[]

双端队列-广度优先遍历

如果队列中的数据，从队头到队尾都是顺序存放的，那么：

  • 从队头依次访问队列，就是顺序访问
  • 从队尾依次访问队列，就是逆序访问

时间空间复杂度均为O(N)

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        if (root == nullptr) return ans;
        // 双端队列
        deque<TreeNode*> q;
        q.emplace_back(root);
        bool direction = true;
        while (!q.empty()) {
            int size = q.size();
            vector<int> tmp;
            for (int i = 0; i < size; i++) {
                if(direction){
                    // 从队头依次读取数据，并从左到右加入子节点到队列尾部，【这样子节点从队头到队尾是顺序的】
                    // 从队头顺序读取，相当于顺序读取
                    TreeNode* node = q.front(); 
                    q.pop_front();
                    if (node->left) q.emplace_back(node->left);
                    if (node->right) q.emplace_back(node->right);
                    tmp.emplace_back(node->val);
                }else{
                    // 从队尾依次读取数据，并从右到左加入子节点到队列头部，【这样子节点从队头到队尾是顺序的】
                    // 从队尾顺序读取，相当于反序读取
                    TreeNode* node = q.back(); 
                    q.pop_back();
                    if (node->right) q.emplace_front(node->right);
                    if (node->left) q.emplace_front(node->left);
                    tmp.emplace_back(node->val);
                }
            }
            // 通过direction标记控制读取的顺序
            direction = not direction;
            ans.emplace_back(tmp);
        }
        return ans;
    }
};

107. 二叉树的层序遍历 II

给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

 

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[15,7],[9,20],[3]]
示例 2：

输入：root = [1]
输出：[[1]]
示例 3：

输入：root = []
输出：[]  

看题解基本都是将102题的答案翻转得到，没有想到更好的办法，暂时重写一遍，就当练习了。

广度优先-队列

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
33
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> ans;
        if (root == nullptr) return ans;
        queue<TreeNode*> q;
        q.emplace(root);
        while (!q.empty()){
            int size = q.size();
            vector<int> tmp;
            for (int i = 0; i < size; i++) {
                TreeNode* node = q.front();q.pop();
                tmp.emplace_back(node->val);
                if (node->left) q.emplace(node->left);
                if (node->right) q.emplace(node->right);
            }
            ans.emplace_back(tmp);
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

深度优先-递归

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
    void levelOrder(TreeNode* root, int level, vector<vector<int>> &ans) {
        if (root == nullptr) return;
        // 注意初始时ans的大小为0
        if (ans.size() < level) ans.emplace_back(vector<int>());
        ans[level-1].emplace_back(root->val);
        if (root->left) levelOrder(root->left, level+1, ans);
        if (root->right) levelOrder(root->right, level+1, ans);
    }
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> ans;
        if (root == nullptr) return ans;

        levelOrder(root, 1, ans);
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

637. 二叉树的层平均值

给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。

 

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[3.00000,14.50000,11.00000]
解释：第 0 层的平均值为 3,第 1 层的平均值为 14.5,第 2 层的平均值为 11 。
因此返回 [3, 14.5, 11] 。
示例 2:

输入：root = [3,9,20,15,7]
输出：[3.00000,14.50000,11.00000]

还是沿用广度优先和深度优先的思路分别求解

广度优先遍历-队列

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
33
34
35
36
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<double> averageOfLevels(TreeNode* root) {
        vector<double> ans;
        if (root == nullptr) return ans;
        queue<TreeNode*> q;
        q.emplace(root);
        while (!q.empty()){
            int size = q.size();
            // 如果先求和然后算平均值，sum可能会溢出，需要为long int
            // 或者也可以记录当前所有数的平均数和个数,每次更新平均数
            double avg = 0;
            int count = 0;
            for (int i = 0; i < size; i++) {
                TreeNode* node = q.front();
                q.pop();
                avg = (avg*count+node->val)/(++count);
                if (node->left) q.emplace(node->left);
                if (node->right) q.emplace(node->right);
            }
            ans.emplace_back(avg);
        }
        return ans;
    }
};

深度优先遍历

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
33
34
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
    void dfs(TreeNode* root, int level, vector<double> &avg, vector<int> &count) {
        if (root == nullptr) return;
        if (avg.size() < level) {
            avg.emplace_back(0);
            count.emplace_back(0);
        }
        avg[level-1] = (avg[level-1]*count[level-1]+root->val)/(count[level-1]+1);
        count[level-1] += 1;
        if (root->left) dfs(root->left, level+1, avg, count);
        if (root->right) dfs(root->right, level+1, avg, count);
    }
    
public:
    vector<double> averageOfLevels(TreeNode* root) {
        vector<double> ans;
        vector<int> count;
        if (root == nullptr) return ans;
        dfs(root, 1, ans, count);
        return ans;
    }
};

111. 二叉树的最小深度

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明：叶子节点是指没有子节点的节点。

 

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：2
示例 2：

输入：root = [2,null,3,null,4,null,5,null,6]
输出：5

深度优先

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
    void dfs(TreeNode* root, int level, int &ans) {
        if (root == nullptr) return;
        if (!root->left && !root->right) {
            ans = min(ans, level);
            return;
        }
        if (root->left) dfs(root->left, level+1, ans);
        if (root->right) dfs(root->right, level+1, ans);
    }
public:
    int minDepth(TreeNode* root) {
        if (root == nullptr) return 0;
        int ans = INT_MAX;
        dfs(root, 1, ans);
        return ans;
    }
};

广度优先

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
33
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int minDepth(TreeNode* root) {
        if (root == nullptr) return 0;
        int ans = 0;
        queue<TreeNode*> q;
        q.emplace(root);
        while(!q.empty()) {
            int size = q.size();
            ans++;
            for (int i = 0; i < size; i++) {
                TreeNode* node = q.front();
                q.pop();
                // 由于是从上到下分层遍历，所以当某层出现叶子结点时，即为最小深度，即刻返回。
                if (!node->left && !node->right) return ans;
                if (node->left) q.emplace(node->left);
                if (node->right) q.emplace(node->right);
            }
        }
        return ans;
    }
};

429. N 叉树的层序遍历

给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。

树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。

 

示例 1：

输入：root = [1,null,3,2,4,null,5,6]
输出：[[1],[3,2,4],[5,6]]
示例 2：

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

广度优先遍历-队列

多叉树的子节点是一个vector对象

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
33
34
35
36
37
38
39
40
41
42
43
/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        vector<vector<int>> ans;
        if (root == nullptr) return ans;

        queue<Node*> q;
        q.emplace(root);
        while (!q.empty()) {
            int size = q.size();
            vector<int> tmp;
            for (int i = 0; i < size; i++) {
                Node* node = q.front(); q.pop();
                tmp.emplace_back(node->val);
                for(auto child : node->children) {
                    q.emplace(child);
                }
            }
            ans.emplace_back(tmp);
        }
        return ans;
    }
};

深度优先遍历

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
33
34
35
36
37
38
39
/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
    void dfs(Node* root, int level, vector<vector<int>> &ans) {
        if (root == nullptr) return;
        if (ans.size() < level) ans.emplace_back(vector<int>());
        ans[level-1].emplace_back(root->val);
        for (auto child : root->children) {
            dfs(child, level+1, ans);
        }
    }
public:
    vector<vector<int>> levelOrder(Node* root) {
        vector<vector<int>> ans;
        if (root == nullptr) return ans;

        dfs(root, 1, ans);
        return ans;
    }
};

993. 二叉树的堂兄弟节点

在二叉树中，根节点位于深度 0 处，每个深度为 k 的节点的子节点位于深度 k+1 处。

如果二叉树的两个节点深度相同，但 父节点不同 ，则它们是一对堂兄弟节点。

我们给出了具有唯一值的二叉树的根节点 root ，以及树中两个不同节点的值 x 和 y 。

只有与值 x 和 y 对应的节点是堂兄弟节点时，才返回 true 。否则，返回 false。

 

示例 1：

输入：root = [1,2,3,4], x = 4, y = 3
输出：false
示例 2：

输入：root = [1,2,3,null,4,null,5], x = 5, y = 4
输出：true
示例 3：

输入：root = [1,2,3,null,4], x = 2, y = 3
输出：false

还是二叉树的层序遍历：

  1. 层序遍历二叉树，记录x和y的层数以及父节点，当树遍历完或者x，y均遍历到时，结束遍历
  2. 判断x和y是否是堂兄弟节点

广度优先遍历

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isCousins(TreeNode* root, int x, int y) {
        if (root == nullptr) return false;

        // 记录x和y的层数以及父节点
        int level = 0, xLevel = 0 , yLevel = 0;
        TreeNode* xFather, *yFather;

        queue<TreeNode*> q, fatherQueue;
        q.emplace(root);
        fatherQueue.emplace(nullptr);
        while (!q.empty()) {
            level++;
            int size = q.size();
            for (int i = 0; i < size; i++) {
                TreeNode* node = q.front(); q.pop();
                TreeNode* father = fatherQueue.front(); fatherQueue.pop();
                if (node->val == x) {
                    xLevel = level;
                    xFather = father;
                }
                if (node->val == y) {
                    yLevel = level;
                    yFather = father;
                }
                if (node->left) {
                    q.emplace(node->left);
                    fatherQueue.emplace(node);
                }
                if (node->right) {
                    q.emplace(node->right);
                    fatherQueue.emplace(node);
                }

                if (xLevel != 0 && yLevel != 0) break;
            }
            if (xLevel != 0 && yLevel != 0) break;
        }
        if (xLevel == 0 || yLevel == 0) return false;
        return xLevel == yLevel && xFather != yFather;
    }
};

深度优先遍历

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
33
34
35
36
37
38
39
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
    // 记录x和y的层数以及父节点
    int level = 0, xLevel = 0 , yLevel = 0;
    TreeNode* xFather, *yFather;
    void dfs(TreeNode* root, TreeNode* pre, int level, int x, int y) {
        if (root == nullptr) return;
        if (root->val == x) {
            xLevel = level;
            xFather = pre;
        }
        if (root->val == y) {
            yLevel = level;
            yFather = pre;
        }
        if (xLevel != 0 && yLevel != 0) return;
        if (root->left) dfs(root->left, root, level+1, x, y);
        if (root->right) dfs(root->right, root, level+1, x, y);
    }
public:
    bool isCousins(TreeNode* root, int x, int y) {
        if (root == nullptr) return false;

        dfs(root, nullptr, 1, x, y);
        if (xLevel == 0 || yLevel == 0) return false;

        return xLevel == yLevel && xFather != yFather;
    }
};

314. 二叉树的垂直遍历

给定一个二叉树，返回其结点 垂直方向（从上到下，逐列）遍历的值。

如果两个结点在同一行和列，那么顺序则为 从左到右。

输入: [3,9,20,null,null,15,7]

3
/
/
9 20
/
/
15 7

输出:

[
[9],
[3,15],
[20],
[7]
]

思路：以根节点为(0,0)坐标，然后层序遍历。其中需要用一个队列记录每个节点的列。

每一个子节点的列号：

  • 若子节点为左孩子，则列号减1
  • 若子节点为右孩子，则列号加1

具体实现同样可以用BFS或DFS均可。

此题现在需要会员，暂时不给答案。

发表于 更新于 分类于
本文字数： 2.9k 阅读时长 ≈ 3 分钟

前序遍历

递归版本

递归的一个思想就是：假设子问题已经解决。
对于遍历来说，就是左子树的结果已经知道了，右子树的结果也已经知道了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        result = []
        if not root:
            return result
        result.append(root.val)
        result += self.preorderTraversal(root.left)
        result += self.preorderTraversal(root.right)
        return result


非递归版本

根-左-右，使用栈的思路。
核心要点，访问完根节点后，考虑栈先进后出的特点，需要先将右子树压栈，再将左子树压栈。

阅读全文 »

发表于 更新于 分类于
本文字数： 2.5k 阅读时长 ≈ 2 分钟

请你设计并实现一个满足  LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类：
LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

 

示例：

输入
[“LRUCache”, “put”, “put”, “get”, “put”, “get”, “put”, “get”, “get”, “get”]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4  

提示：

1 <= capacity <= 3000
0 <= key <= 10000
0 <= value <= 105
最多调用 2 * 105 次 get 和 put

题解

核心思路是 哈希表+双向链表。

哈希表存储key和双向链表中的位置。
双向链表队头的元素是最近访问过的元素，队尾是最近未访问过的元素

注意：所有put操作和get读取到的情况，都要将数据插入到队头
设置head和tail的dummy节点，可以简化操作。
由于空间满的时候需要删除队尾数据，所以使用单链表的时间复杂度会达到O(k), 而双向链表可以做到读写都是O(1)

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
class DLinkedNode:
    def __init__(self, key=0, value=0):
        self.key = key
        self.value = value
        self.next = None
        self.prev = None

class LRUCache:
    def __init__(self, capacity: int):
        self.head = DLinkedNode()
        self.tail = DLinkedNode()
        #双向链表初始化时，head.prev和tail.next均为None
        self.head.next = self.tail
        self.tail.prev = self.head
        self.cache = dict()
        self.capacity = capacity
        self.size = 0
     
    # 将节点插入头节点head之后，思路和单链表类似，先将node连上head之后的节点，再将head指向node
    def insertHead(self, node):
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node
    
    #删除动作，两次指针变换，node节点的后一个节点的前驱，node节点的前一个节点的后继
    def remove(self, node):
        node.next.prev = node.prev
        node.prev.next = node.next

    # 删除队尾节点就是删除tail节点前一个节点
    def removeTail(self):
        node = self.tail.prev
        self.remove(node)
        return node

    def get(self, key: int) -> int:
        # print("get1 ", self.head.next.next.key, self.head.next.next.value)
        # print("get2 ", self.head.next.next.key, self.head.next.next.value)
        if key in self.cache.keys():
            node = self.cache[key]
            self.remove(node)
            self.insertHead(node)
            return node.value
        else:
            return -1

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            node = self.cache[key]
            node.value = value
            self.remove(node)
            self.insertHead(node)
        else:
            node = DLinkedNode(key, value)
            self.insertHead(node)
            self.size += 1
            self.cache[key] = node
            if self.size > self.capacity:
                removed = self.removeTail()
                self.cache.pop(removed.key)
                self.size = self.size - 1



# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

发表于 更新于 分类于
本文字数： 7.7k 阅读时长 ≈ 7 分钟

python3

冒泡排序

核心动作：比较和交换

  1. n-1次循环(因为最后一个数不用冒泡了)，每次循环将一个值”冒泡”至最终位置，i为循环轮次
  2. 每次循环两两比较相邻数，若不符合要求就交换，j表示比较的数
  3. 若上一次循环没有交换数据，则表示已完成排序，可以终止循环了，flag标记

复杂度：时间复杂度O(n^2), 空间复杂度O(1)

稳定性：比较的时候可以设定相等的元素不交换，所以是稳定的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# NC140 排序
class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        length = len(nums)
        flag = False
        for i in range(length-1):
            for j in range(length-1-i):
                # 升序或降序只需要修改下面的比较符号即可
                if nums[j] > nums[j+1]:
                    tmp = nums[j]
                    nums[j] = nums[j+1]
                    nums[j+1] = tmp
                    flag = True
            if not flag:
                break
        return nums

选择排序

每次选择最小的一个数据放置在指定位置
核心动作：比较和交换

  1. 循环n-1次，每次循环选择一个最小的数，与未处理部分的第一个元素交换

复杂度：时间复杂度O(n^2), 空间复杂度O(1)

稳定性：交换动作可能会导致未处理部分的第一个元素与其重复值相对顺序改变，所以是不稳定的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        length = len(nums)
        for i in range(length-1):
            min_index = i
            for j in range(i+1, length):
                # 升序或降序只需要修改下面的比较符号即可
                if nums[j] < nums[min_index]:
                    min_index = j
            # 未排序部分中的最小值 与 未排序部分的第一个元素 交换
            # 此部分导致选择排序的不稳定性，因为如果「未排序部分的第一个元素」存在重复元素，交换时会导致这个值相对顺序的改变
            # 如果需要改变稳定性，可以改为：将未排序部分中的最小值 插入 到未排序部分第一个元素 之前
            # 如果是链表实现的，则比较容易实现上述插入动作
            tmp = nums[i]
            nums[i] = nums[min_index]
            nums[min_index] = tmp
        return nums

插入排序

直接插入排序

将数组分为已排序和未排序两部分，然后将未排序部分的数依次插入到已排序数组中的合适位置
核心动作：比较和移动
1.将第1个数视为已排序部分，剩下部分视为未排序部分
2.未排序部分：i表示需要依次遍历的数，从第二个数到最后一个数
3.已排序部分：i左边的所有数
4.将本次需要插入的数和已排序部分依次比较，如果需要插入的数比已排序部分这个数大，就将这个数后移一位，直到第0个数
5.将待插入数据插入到查到到的位置

复杂度：时间复杂度O(n^2), 空间复杂度O(1)

稳定性：插入的过程不改变相对位置，是稳定排序

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        length = len(nums)
        for i in range(1, length):
            j = i - 1
            tmp = nums[i]
            # 同样的，升序或降序只需要修改下面的比较符号即可
            while j >=0 and nums[j] > tmp:
                nums[j+1] = nums[j]
                j = j - 1
            nums[j+1] = tmp
            
        return nums

折半插入排序

寻找需要插入位置的时候，其实是一个二分查找过程，可以使用二分查找减少比较次数，但是移动次数不会改变

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        length = len(nums)
        for i in range(1, length):
            j = i - 1
            low = 0
            high = j
            tmp = nums[i]
            # 注意这里是<=, 可以保证最终值在low和high之间。
            while low <= high:
                mid = low + (high - low)//2
                # 如果数值相同，右边的数认为更大，可以保持排序稳定
                # 同样的，升序或降序只需要修改下面的比较符号即可
                if nums[mid] <= tmp:
                    low = mid + 1
                else:
                    high = mid - 1
            while j >=0 and j > high:
                nums[j+1] = nums[j]
                j = j - 1
                
            nums[high+1] = tmp
        return nums

快速排序

核心在于partition动作, 实现方式有多种，这里的这种比较巧妙

复杂度：时间复杂度O(nlogn), 空间复杂度O(1)

稳定性：大间隔交换动作可能导致相对顺序改变，不稳定排序

递归版本

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
class Solution:
    def partition(self, nums, left, right):
        # 选择pivot是一个比较关键的点，影响最好最快的复杂度
        if nums[left] < nums[right]:
            self.swap(nums, left, left+(right-left)//2)
        pivot = left
        index = left+1
        for i in range(index, right+1):
            # 同样的，升序或降序只需要修改下面的比较符号即可
            if nums[i] < nums[pivot]:
                self.swap(nums, i, index)
                index += 1
        self.swap(nums, index-1, pivot)
        return index-1

    def swap(self, nums, left, right):
        nums[left], nums[right] = nums[right], nums[left]
    
    def quickSort(self, nums, left, right):
        if left < right:
            pivot_index = self.partition(nums, left, right)
            self.quickSort(nums, left, pivot_index-1)
            self.quickSort(nums, pivot_index+1, right)
        return nums

    def sortArray(self, nums: List[int]) -> List[int]:
        return self.quickSort(nums, 0, len(nums)-1)

Partition函数还有一种写法，pivot，内存2个while顺序和最后1次交换者，很值得琢磨

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def partition(self, nums, left, right):
        if nums[left] < nums[right]:
            self.swap(nums, right, left+(right-left)//2)
        begin=left
        end=right
        pivot=right
        # 最终begin和end都指向一处。
        # 若pivot指向右边，则需要先走左边的while，否则先走右边
        while begin < end:
            while begin < end and nums[begin] <= nums[pivot]:
                begin += 1
            while begin < end and nums[end] >= nums[pivot]:
                end = end - 1
            self.swap(nums, begin, end)
        self.swap(nums, begin, pivot)
        return begin

非递归版本

只修改了quickSort部分的代码

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
33
34
class Solution:
    def partition(self, nums, left, right):
        if nums[left] < nums[right]:
            self.swap(nums, left, left+(right-left)//2)
        pivot = left
        index = left+1
        for i in range(index, right+1):
            if nums[i] < nums[pivot]:
                self.swap(nums, i, index)
                index += 1
        self.swap(nums, index-1, pivot)
        return index-1

    def swap(self, nums, left, right):
        nums[left], nums[right] = nums[right], nums[left]
    
    def quickSort(self, nums, left, right):
        if left < right:
            stack = [right, left]
            while stack:
                i = stack.pop()
                j = stack.pop()
                pivot_index = self.partition(nums, i, j)
                if i < pivot_index:
                    stack.append(pivot_index-1)
                    stack.append(i)
                if pivot_index < j:
                    stack.append(j)
                    stack.append(pivot_index+1)
        return nums

    def sortArray(self, nums: List[int]) -> List[int]:
        return self.quickSort(nums, 0, len(nums)-1)

C++版本

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        quickSort2(nums, 0, nums.size()-1);
        // quickSort(nums, 0, nums.size()-1);
        return nums;

    }

    // 递归版本
    void quickSort(vector<int>& nums, int left, int right){
        if (left < right){
            int pivot = partition(nums, left, right);
            quickSort(nums, left, pivot-1);
            quickSort(nums, pivot+1, right);
        }
    }

    // 非递归版本
    void quickSort2(vector<int>& nums, int left, int right){
        if (left < right){
            stack<int> s;
            s.push(right);
            s.push(left);
            while (!s.empty()){
                int l = s.top(); s.pop();
                int r = s.top(); s.pop();
                int pivot = partition(nums, l, r);
                // l, pivot-1
                // pivot+1, r
                if (l < pivot-1){
                    s.push(pivot-1);
                    s.push(l);
                }
                if (pivot+1 < r){
                    s.push(r);
                    s.push(pivot+1);
                }
            }
        }
    }

    //快排的核心函数
    int partition(vector<int>& nums, int left, int right){
        int mid = left + (right - left)/2;
        if (nums[left] < nums[right]){
            swap(nums[left], nums[mid]);
        }
        int pivot = left;
        int index = left+1;
        for (int i = left+1; i <= right; i++){
            if (nums[i] < nums[pivot]){
                swap(nums[i], nums[index++]);
            }
        }
        swap(nums[index-1], nums[pivot]);
        return index-1;
    }
};

归并排序

核心是merge函数，主体函数里面先将数组划分为两部分，分别mergesort后，执行两部分结果的merge

时间复杂度：O(nlogn), 但是空间复杂度为O(n)
稳定性：属于稳定排序

递归版本

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
class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        return self.mergeSort(nums)

    def mergeSort(self, nums):
        if len(nums) < 2:
            return nums
        mid = len(nums)//2
        left = self.mergeSort(nums[0:mid])
        right = self.mergeSort(nums[mid:])
        return self.merge(left, right)
        

    def merge(self, left, right):
        result = []
        while left and right:
            if left[0] <= right[0]:
                result.append(left.pop(0))
            else:
                result.append(right.pop(0))
        while left:
            result.append(left.pop(0))
        while right:
            result.append(right.pop(0))
        return result

非递归版本

假设 nums = [5,4,0,3,1,6,2,7]
第一次：我们将数组分为 8个子数组 每个数组 1 个元素，对相邻的两个数组进行排序合并。
第二次：我们将数组分为 4个子数组 每个数组 2 个元素，对相邻的两个数组进行排序合并。
第三次：我们将数组分为 2个子数组 每个数组 4 个元素，对相邻的两个数组进行排序合并。
第一步：划分每个子数组元素的个数（也就是子数组的长度)

  1. 第一次 每个子数组元素 个数 为 1.
  2. 第二次 每个子数组元素 个数 为 2.
  3. 第三次 每个子数组元素 个数 为 4.
    可以看出来 每个子数组元素个数 以2的倍数递增. 设置step步长，初始1，2倍递增
    首先：求得要合并的两个相邻数组的区间 [low:mid) [mid:high)
  4. 当子数组长度为 1 的时候 要合并的相邻两个数组的区间为：
    [0,1) [1,2) [2,3) [3,4) [4,5) [5,6) [6,7) [7,8) 子数组长度为 1
  5. 子数组长度为 2 要合并的相邻两个数组的区间为：
    [0,2) [2,4) [4,6) [6,8) 子数组长度为 2
  6. 子数组长度为 4 要合并的相邻两个数组的区间为：
    [0,4) [4,8) 子数组长度为 4
    下面来求 区间中的 low mid height:
    low = low + 2 x step
    mid = low + step
    high = low + 2 x step

但是要注意nums长度不为2的整数倍时，high可能越界，需要优化。

中间过程可能存在轮空的情况，mid和high的关系也需要确保mid<high

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
33
class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        return self.mergeSort(nums)

    def mergeSort(self, nums):
        step = 1
        while step < len(nums):
            low = 0
            while low < len(nums):
                mid = low + step
                high = min(len(nums), low+2*step)
                if mid < high:
                    self.merge(nums, low, mid, high)
                low += 2*step
            step = step * 2
        return nums
                
        

    def merge(self, nums, begin, mid, end):
        result = []
        i, j = begin, mid
        while i < mid and j < end:
            if nums[i] <= nums[j]:
                result.append(nums[i])
                i += 1
            else:
                result.append(nums[j])
                j += 1
        result += nums[i:mid]
        result += nums[j:end]
        nums[begin:end] = result

堆排序

核心是一个调整动作adjust函数，

建堆过程，从倒数第一个非叶子节点开始调整，直到第一个节点。
排序过程，每次选择堆顶元素与最后一个交换后调整第一个节点。

时间复杂度：O(nlogn), 有空可以详细推导一下
稳定性：中间交换过程不可控，不稳定

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
33
class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        return self.heapSort(nums)

    def heapSort(self, nums):
        self.buildHeap(nums)
        for i in range(len(nums)-1, -1, -1):
            self.swap(nums, i, 0)
            self.adjust(nums, 0, i)
        return nums
                
    def swap(self, nums, i, j):
        nums[i], nums[j] = nums[j], nums[i]

    def buildHeap(self, nums):
        for i in range(len(nums)//2, -1, -1):
            self.adjust(nums, i, len(nums))

    def adjust(self, nums, i, length):
        temp = nums[i]
        k = 2*i + 1
        while k < length:
            # 升序和降序修改此处第二个比较符号
            if k+1 < length and nums[k+1] > nums[k]:
                k += 1
            # 升序和降序修改此处比较符号
            if nums[k] > temp:
                nums[i] = nums[k]
                i = k
            k = 2*k + 1
        nums[i] = temp


桶排序

基数排序

计数排序

发表于 更新于 分类于
本文字数： 2.1k 阅读时长 ≈ 2 分钟

python3

方法一：依次插入空头节点后完成反转

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
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# 1.构造带头节点的空链表，注意next为None，后续会变为最后一个节点
# 2. 将链表节点p依次插入空链表的头节点之后
# 3. 注意终止条件，q=NULL
# 4. 注意处理最后一个p节点
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head:
            return head
        dummy = ListNode(0)

        p = head
        q = head.next
        while q:
            p.next = dummy.next
            dummy.next = p
            p = q
            q = q.next
        p.next = dummy.next
        dummy.next = p
        return dummy.next

方法二：直接链表一次遍历完成反转

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# pre初始指向空，p指向当前待处理节点，初始为head，q记录p的下一个节点
# p连上上一个节点pre，pre变为当前节点p，p后移指向下一个待处理节点q
# 结束时，p为空，pre为最后被处理的节点，即新链表的头节点
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head:
            return head
        pre = None
        p = head
        while p:
            q = p.next
            p.next = pre
            pre = p 
            p = q
        return pre

方法三：迭代求解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# 以第一个节点为未反转部分，剩下部分为已求解部分
# 第二个节点为已求解部分最后的一个节点，将最后一个未反转节点加入已求解部分
# 注意两点：1. head.next为空需要提前判断，否则有语法错误   2.最终一个节点的next为None
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        right = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return right

Golang

C

C++

92. 反转链表 II

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

复用以前的反转算法

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
33
34
35
36
37
38
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode:
        # head为第一个要处理的节点，tail为要处理节点的下一个节点，可能为None
        def reverseList(head, tail):
            prev = tail
            cur = head
            p = head
            while p != tail:
                p = p.next
                cur.next = prev
                prev = cur
                cur = p
            return prev

        dummy = ListNode(next=head)
        p = dummy
        count = 0
        prev_node = dummy
        right_node = None
        while p:
            if count == left-1:
                prev_node = p
            if count == right:
                right_node = p
                break
            p = p.next
            count += 1
        # print(prev_node.val, right_node.val)
        if not right_node:
            prev_node.next = reverseList(prev_node.next, None)
        else:
            prev_node.next = reverseList(prev_node.next, right_node.next)
        return dummy.next

发表于
本文字数： 1.2k 阅读时长 ≈ 1 分钟

算法全局概览

算法概览图

TOP20

10个数据结构
数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie树；

10个算法
递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法

学习原则

学习它的“来历”“自身的特点”“适合解决的问题”以及“实际的应用场景”

学习路径

  • 算法专栏
  • 剑指offer
  • 牛客高频300
  • leetcode各分类3题

3链表：https://leetcode.com/problemset/all/?topicSlugs=linked-list

3栈: https://leetcode.com/problemset/all/?topicSlugs=stack

3队列：https://leetcode.com/problemset/all/?topicSlugs=queue

散列表：

6二叉树：https://leetcode.com/problemset/all/?topicSlugs=tree

3堆：https://leetcode.com/problemset/all/?topicSlugs=heap

跳表：

6图：https://leetcode.com/problemset/all/?topicSlugs=graph

3Trie树：https://leetcode.com/problemset/all/?topicSlugs=trie

3递归：https://leetcode.com/problemset/all/?topicSlugs=recursion

6排序：https://leetcode.com/problemset/all/?topicSlugs=sort

3二分查找：https://leetcode.com/problemset/all/?topicSlugs=binary-search

搜索：

哈希算法：

6贪心算法：https://leetcode.com/problemset/all/?topicSlugs=greedy

6分治算法：https://leetcode.com/problemset/all/?topicSlugs=divide-and-conquer

6回溯算法：https://leetcode.com/problemset/all/?topicSlugs=backtracking

6+动态规划：https://leetcode.com/problemset/all/?topicSlugs=dynamic-programming

字符串匹配：

其他：

哈希表https://leetcode.com/problemset/all/?topicSlugs=hash-table

经典算法题目梳理

  • 1.单链表是否有环 环的入口
  • 2.最长公共子串和最长公共子序列
  • 3.二叉树的先序，中序，后序，层序遍历
  • 4.快速排序，归并排序，堆排序
  • 5.atoi

发表于 更新于
本文字数： 823 阅读时长 ≈ 1 分钟

12月5日 后续通过flomo记录，并改为每周计划与复盘

11月24日 后续改为评论区记录，可以更加清楚的看出时间线

2021年11月23日

TODO 是否完成 完成时间与说明
锻炼 是 下午4点跑步3km
早上阅读 是 9.30-10:30点阅读。合计1h
中午阅读 是 13-14阅读 合计1h
晚上阅读 是 晚上阅读0.5h, 感觉长时间阅读同一个东西，有点厌烦的感觉，应该交替着进行

2021年11月22日

TODO 是否完成 完成时间与说明
锻炼 是 下午5点跑步5km
早上阅读 是 早上8-8.15, 9.30-11点阅读。合计1.5h
中午阅读 否 有点困，未完成。今天早点睡，明天要不顾一切的完成
晚上阅读 否 做规划，未完成。明天要不顾一切的完成

目标

  1. 每周锻炼3次，2021年11月20日启动
  2. 每周阅读20小时，2021年11月22日启动
  3. 每周刷一道算法题，2021年11月22日启动

为什么

  • 锻炼可以有良好的身体，身体是一切的基础。不阅读有如文盲，文盲无法在这个社会生存。
  • 二者都属于第二象限的人生要事，需要保证
  • 每日记载总结，周级复盘，理论-实践-反馈分析的循环必超凡入圣

时间从哪来

锻炼：

  • 工作日：每天下午5点，如果5点有会，就4点；如果没有跑步机，就早起跑步
  • 周末：公司跑步或早起跑步
  • 没有特殊情况，比如下雨就在家keep，总之不找理由尽可能想办法实现。

阅读：

  • 工作日：早上10点半以前，中午1点至2点，晚上6点至7点
  • 周末：尽可能安排在上午，原则是补足20小时，若已满20小时，则至少阅读1小时
  • 第二象限的工作，不找借口，保证完成。最终必会反哺工作和生活

衡量指标

锻炼：

  • 体重
  • BMI
  • 最大摄氧量
  • 仰卧起坐个数
  • 俯卧撑个数
  • 头发色泽和密度
  • 三围
  • 身材图(正面和侧面)

阅读：

  • 每日阅读时长
  • 每月阅读书本数
  • 产出读书笔记数

如何做

锻炼：

  • 第一阶段：跑步
  • 第二阶段：跑步与力量训练交替

阅读：

  • 方式：主题阅读(技术、成长、业务、效能、管理、财务)
  • 阅读什么书？要阅读当下感兴趣的书，快速阅读，吸取有用的部分即可
    书的分类
  • 如何选书：豆瓣评分7.0以上的书，豆瓣评论，大咖推荐

发表于 更新于 分类于
本文字数： 22 阅读时长 ≈ 1 分钟

记录一些生活中的误解

现象

错误归因

真实原因原因

发表于 更新于 分类于
本文字数： 4.1k 阅读时长 ≈ 4 分钟

2022-1 Week3 四个维度平衡发展

每周学习20小时
2022.1.17-2022.1.23

TOP1: 家庭幸福
TODO：未计划

TOP2: 精力充沛(锻炼、饮食、休息)
TODO：每周运动3次+，每次30min

TOP2: 工作发展(晋升，技术业务管理)
TODO：每天看一章节，刷1道题

TOP2: 财务自由
TODO：每天学习30min；周末输出一篇文章

阅读全文 »

发表于 更新于 分类于
本文字数： 586 阅读时长 ≈ 1 分钟

经过知识点梳理、目标确定、行动拆分后确定第一阶段推荐策略入门规划如下

理论(3月)—-框架(1.5月)—–实战(1.5月)—–面试(3月)

前6个月学习大致拆分如下：

  • 9.1-9.15 0.5月, 通读花书数学基础章节
  • 9.1-10.15 1.5月, 吴恩达课程
  • 10.1-10.31 1月, 通读统计学习方法
  • 11.1-11.30 1月, 通读花书CNN、RNN、LSTM部分
  • 12.1-12.15 0.5月, 学习sklearn框架，实现3个算法
  • 12.16-1.15 1月, 学习pytorch框架，实现图片分类功能
  • 1.16-2.16 1月, 通读机器学习实战
  • 2.17-2.28 0.5月, 推荐系统专栏
阅读全文 »

发表于 更新于 分类于
本文字数： 3.9k 阅读时长 ≈ 4 分钟

前言

本文简单介绍一下北京摩托车驾照获得的流程和考试的一些心得，希望能帮到大家。

背景

长安居大不易，相信每一个帝都生活的朋友都对生活的艰难有自己的感受，在汽车摇号无望，电动车续航不给力，地铁太挤，打车太堵且贵，长期骑单车太累的情况下，
摩托通勤成为了一个勉强可以接受的方案，虽然明知”肉包铁”，也不得已而为之。

话不多说，直入主题，我是2021年5月份在海淀驾校报名的，主要是因为海驾班车比较方便。

我报的是二轮摩托车，也就是俗称的E本，活动优惠后价格是900元，大概7月中旬考完科目一后，连续预约了3次练习，8月1日晚上集训一次，8月2日科目二科目三科目四都是一把过，成功拿本。

其实如果不差钱且想快速拿本的话，建议报三轮摩托车，由于三轮摩托车车速较慢且不需要考虑平衡性问题，考试较简单。三轮是D本，涵盖了E本的全部功能。

阅读全文 »

发表于 更新于 分类于
本文字数： 2.2k 阅读时长 ≈ 2 分钟

hexo next 为文章添加分类

新建一个页面，命名为 categories 。命令如下：

1
hexo new page categories

编辑刚新建的页面，将页面的类型设置为 categories ，主题将自动为这个页面显示所有分类

可选是否关闭评论

1
2
3
4
title: 分类
date: 2014-12-22 12:39:04
type: "categories"
comments: false
阅读全文 »

发表于 更新于 分类于
本文字数： 42k 阅读时长 ≈ 38 分钟

Cracking The Coding Interview

1.Foreword

As you get ready for your interviews, consider these suggestions:

  • Write Code on Paper
  • Know Your Resume
  • Don’t Memorize Solutions
  • Talk Out Loud

Receiving an offer is not about solving questions flawlessly (very few candidates do!), but rather, it is about answering questions better than other candidates. So don’t stress out when you get a tricky question - everyone else probably thought it was hard too!

2.Introduction

3.Behind the Scenes

3.1 The Microsoft Interview

阅读全文 »

发表于 更新于 分类于
本文字数： 8.7k 阅读时长 ≈ 8 分钟

这篇文章写了好久，感觉还是没写完。接下来准备慢慢看书，实习，不断更新吧。

分割线********************

按照侯捷先生在《Effective C++》的观点，以及自己的一些理解，可以将互联网技术岗位关于C＋＋的知识点归纳为以下五个部分：

  • C＋＋基础知识
  • 面向过程的特性
  • 面向对象的特性
  • 泛型编程的特性
  • 标准模板库和算法
阅读全文 »

发表于 更新于 分类于
本文字数： 1.8k 阅读时长 ≈ 2 分钟

背景

  • 对几何3D模型不断增长的需求：电影 游戏 虚拟环境等行业
  • VR&AR的火爆
  • 房地产 三维地图等领域的需求

应用

  • 中国古代建筑三维数字化保护
  • 三维数字化城市
  • 三维地图
  • VR&&AR游戏，电影等
  • 医疗行业：三维心脏
  • 教育行业等
    阅读全文 »

发表于 更新于 分类于
本文字数： 6.5k 阅读时长 ≈ 6 分钟

最近两天加周三的一个晚上，参照网上的博客搭建了属于自己的博客，其实之前也对比过Jekyll，Octopress，Python实现的myblog, 以及第三方博客，如Blogger，cnblogs，csdn等等，只能说各有千秋吧，还是希望能够有一个属于自己的空间。为避免忘记，也为了表示对社区的感谢，现在对部署过程进行一下纪录。主要包括：

  1. 基本Hexo的搭建
  2. 主题的选择
  3. 扩展功能的介绍
阅读全文 »

发表于 更新于 分类于
本文字数： 576 阅读时长 ≈ 1 分钟

这个问题我思考了很久，却仍然没有一个能够让自己很满意的答案。不得不承认，建立技术博客的初衷是因为找工作，哈哈，说起来还是有点功利的性质的。但是凡事总是一半一半吧，想了想，坚持写博客的好处可能会有下面几点吧。

阅读全文 »