简单

剑指 Offer 10- I. 斐波那契数列

不能使用简单递归 会超时

使用动态规划求解

由于 F(n) 只和 F(n−1) 与 F(n−2) 有关，因此可以使用「滚动数组思想」把空间复杂度优化成 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
class Solution:
    def fib(self, n: int) -> int:
        # 计算过程中，答案需要取模  1e9+7
        MOD = 10 ** 9 + 7
        if n < 2:
            return n
        else:
            # 使用滚动数组减小空间复杂度
            # f0=0 f1=1
            p = 0
            q = 0
            r = 1
            for i in range(2, n + 1):
                p = q
                q = r
                r = (p + q) % MOD
            return r


if __name__ == '__main__':
    n = 100

    f = Solution()
    b = f.fib(n)
    print(b)

剑指 Offer II 069. 山峰数组的顶部

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def peakIndexInMountainArray(self, arr: List[int]) -> int:
        s_len = len(arr)
        left=0
        right=s_len-2
        ans=1
        while left <= right:
            mid = (left+right)//2
            if arr[mid]>arr[mid+1]:
                ans = mid
                right = mid - 1 
            else:
                left =mid +1
        return ans

141. 环形链表

STL容器

set和unordered_set：其中unordered_set对元素不进行排序

find(key)：查找以值为 key 的元素，如果找到，则返回一个指向该元素的正向迭代器；反之，则返回一个指向容器中最后一个元素之后位置的迭代器（如end() 方法返回的迭代器）。

count(key)：在容器中查找值为 key 的元素的个数。

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.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        // 遍历链表 将访问过的节点存到哈希表 如果节点被多次访问 则存在环    
        set<ListNode*> nodes;
        while(head!=nullptr)
        {
            // 如果set中找不到指定元素 返回nodes.end()
            if(nodes.find(head)!=nodes.end())
                return true;
            // count(head) 在容器中查找值为 key 的元素的个数。
            // if (nodes.count(head)) {
            //     return true;
            // }
            nodes.insert(head);
            head=head->next;
        }
        return false;
        
    }
};

268. 丢失的数字

stl中vector的排序sort(nums.begin(), nums.end());

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        // 先排序 
        sort(nums.begin(), nums.end());
        // for (int v:nums)
        //     cout<<v;
        // 遍历对应位置 索引与数组值不对应 则返回该索引
        for (int i=0;i<nums.size();i++){
            if (nums[i]!=i)
                return i;
        }
        return nums.size();
    }
};

405. 数字转换为十六进制数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    
    def toHex(self, num: int) -> str:
        CONV = "0123456789abcdef"
        ans =[]
        # 32位二进制数 转成十六进制 共8位 4*8
        for _ in range(8): 
            temp = num % 16
            num = num//16
            ans.append(temp)
            if not num:
                break
        # 倒着输出
        return ''.join(CONV[j] for j in ans[::-1])

434. 字符串中的单词数

注意：python中split()函数用法

1
2
3
a="     "
a.split() # 按照空格分割 分割完删除空字符串
a.split() # 按照空格分割 但只是按照单个空格分割 分割后字符串中会包含空字符串
1
2
3
4
5
6
7
8
9
10
class Solution:
    def countSegments(self, s: str) -> int:
        ans =0 
        # s=s.strip()
        for i in range(len(s)):
            
            if(s[i]==" " and s[i-1]!=" " and i>0) or (i==(len(s)-1) and s[i]!=" "):
                ans+=1
        return ans 
        # return len(s.split())

496. 下一个更大元素 I

时间复杂度较低的解法，使用 单调栈 + 哈希表

应为nums2中没有重复的元素，构造严格单调递增的栈 并将栈中的值与小于自身的值 对应关系存储到哈希表

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        res = {}
        stack = []
        for num in reversed(nums2):
            while stack and num >= stack[-1]:
                stack.pop()
            res[num] = stack[-1] if stack else -1
            stack.append(num)
        return [res[num] for num in nums1]

598. 范围求和 II

求出区间交集即可

用不着暴力模拟 而且会超时

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int maxCount(int m, int n, vector<vector<int>>& ops) {
        // 求解 对于mxn的矩阵M 操作的交集区间 即为最大值区间
        int max_a=m,max_b=n;
        for(vector<int>op : ops)
        {
            max_a = min(op[0],max_a);
            max_b=min(op[1],max_b);
        }
        return max_b*max_a;
        
    }
};

700. 二叉搜索树中的搜索

左子树严格小于根结点 右子树严格大于根结点

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        //遍历二叉搜索树
        // 左子树严格小于根结点 右子树严格大于根结点
        if (root==nullptr)
            return NULL;
        if (root->val == val)
            return root;     
        return searchBST(val < root->val ? root->left : root->right, val);

    }
};

704. 二分查找

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 = (high - low) // 2 + low
            num = nums[mid]
            if num == target:
                return mid
            elif num > target:
                high = mid - 1
            else:
                low = mid + 1
        return -1


if __name__ == '__main__':
    nums = [-1, 0, 3, 5, 9, 12]
    target = 9

    f = Solution()
    b = f.search(nums, target)
    print(b)

1221. 分割平衡字符串

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 balancedStringSplit(self, s: str) -> int:
        s_list = list(s)
        ch = 0
        ans = 0
        # 遍历字符串 统计两种字符出现数量之差 ch=0时 说明前缀字符串数量相同 构成平衡字符串 ans+1
        for i in s_list:
            if i == 'R':
                ch += 1
            else:
                ch -= 1
            if ch == 0:
                ans += 1
        return ans


if __name__ == '__main__':
    s = "RLRRLLRLRL"

    f = Solution()
    b = f.balancedStringSplit(s)
    print(b)

1436. 旅行终点站

注意 如果用下面的办法 字典需要遍历两遍

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
from typing import List


class Solution:
    def destCity(self, paths: List[List[str]]) -> str:

        city_dict = dict()
        for i in paths:
            if city_dict.get(i[1]):
                city_dict[i[1]] += 1
            else:
                city_dict[i[1]] = 1
        for i in paths:
            if city_dict.get(i[0]):
                city_dict[i[0]] -= 1
        # 输出值为1的城市
        for k, v in city_dict.items():
            if v == 1:
                return k


if __name__ == '__main__':
    root = [["B", "C"], ["D", "B"], ["C", "A"]]
    targetSum = 8

    f = Solution()
    b = f.destCity(root)
    print(b)

一般

面试题 17.14. 最小K个数

1
2
3
4
5
6
7
class Solution:
    def smallestK(self, arr: List[int], k: int) -> List[int]:
        if k > 0 and k < len(arr):
            arr.sort()
            return arr[0:k]
        else:
            return []

由于 C++ 语言中的堆（即优先队列）为大根堆，而 Python 语言中的堆为小根堆，因此我们要对数组中所有的数取其相反数，才能使用小根堆维护前 k 小值。、

中等

🌟29. 两数相除

有点没思路

题解：

  • 如果我们将被除数和除数都变为正数，那么可能会导致溢出。例如当被除数为 $-2^{31}$ 时，它的相反数 $2^{31}$产生了溢出。因此，我们可以考虑将被除数和除数都变为负数，这样就不会有溢出的问题，在编码时只需要考虑 1 种情况了。
  • 使用快速乘实现乘法运算。快速乘实际上是通过加法运算实现的。

官方题解还是有点懵，找到一篇思路简单的题解：

  • 举个例子：11 除以 3 。
    首先11比3大，结果至少是1， 然后我让3翻倍，就是6，发现11比3翻倍后还要大，那么结果就至少是2了，那我让这个6再翻倍，得12，11不比12大，吓死我了，差点让就让刚才的最小解2也翻倍得到4了。但是我知道最终结果肯定在2和4之间。也就是说2再加上某个数，这个数是多少呢？我让11减去刚才最后一次的结果6，剩下5，我们计算5是3的几倍，也就是除法，看，递归出现了。
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 {
public:
    int divide(int dividend, int divisor) {
        if(dividend == 0) return 0;
        if(divisor == 1) return dividend;
        if(divisor == -1){
            if(dividend>INT_MIN) return -dividend;// 只要不是最小的那个整数，都是直接返回相反数就好啦
            return INT_MAX;// 是最小的那个，那就返回最大的整数啦
        }
        long a = dividend;
        long b = divisor;
        int sign = 1; 
        if((a>0&&b<0) || (a<0&&b>0)){
            sign = -1;
        }
        a = a>0?a:-a;
        b = b>0?b:-b;
        long res = div(a,b);
        if(sign>0)return res>INT_MAX?INT_MAX:res;
        return -res;
    }
    int div(long a, long b){  // 似乎精髓和难点就在于下面这几句
        if(a<b) return 0;
        long count = 1;
        long tb = b; // 在后面的代码中不更新b
        while((tb+tb)<=a){
            count = count + count; // 最小解翻倍
            tb = tb+tb; // 当前测试的值也翻倍
        }
        return count + div(a-tb,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
36
37
38
39
40
41
class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        # 边界情况 
        INT_MIN = -(2<<30)
        INI_MAX = (2<<30)-1
        # 判断特殊情况
        # 被除数为0
        if dividend==0:
            return 0
        if divisor==-1:
            # INT_MIN/-1 为2^31 正数越界
            if dividend == INT_MIN:
                return INI_MAX
            return -dividend
        # 方便后面找倍数关系 转为正数计算
        # 记录符号
        sign = -1
        if (dividend>0 and  divisor>0 ) or (dividend<0 and divisor<0):
            sign = 1
        dividend = dividend if dividend>0 else -dividend
        divisor = divisor if divisor>0 else -divisor
        # 计算结果
        # print(dividend,divisor)
        ans = self.div(dividend,divisor)

        if sign == 1:
                return ans
        else:
                return -ans

    def div(self,x,y):
        # 判断 x/y可以除几轮 不能用除号 用倍数来代替
        if x<y :
            return 0 
        # x > y x中至少包含一个y
        times =1
        ty= y
        while (ty<<1) <= x:
            times += times
            ty = ty<<1
        return times + self.div(x-ty,y)

36. 有效的数独

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
import numpy as np


class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:

        dict_col = {}
        # 先进行行检测 确保不出现重复数字
        row = self.signal_num(board)
        # print(row)
        if row:
            # 再进行列检测 确保每一列数据不包含重复数字
            #  矩阵转置
            t_board = np.transpose(np.array(board))
            col = self.signal_num(list(t_board))
            # print(col)
            if col:
                # 判断3x3 区间是否有重复数字
                # 使用numpy实现矩阵切片
                np_board = np.transpose(np.array(board))
                # print(np_board)
                for j in range(3):
                    for i in range(3):
                        index_i = i * 3
                        index_j = j * 3
                        new_board = np_board[index_i:index_i + 3, index_j:index_j + 3]
                        # 矩阵展开成一纬度
                        d1_new_board = new_board.flatten()
                        # print(d1_new_board)
                        if not self.signal_num(list([d1_new_board])):
                            return False
            else:
                return False

        else:
            return False
        return True

    def signal_num(self, board_self: List[List[str]]) -> bool:
        for row in board_self:
            dict_row = {}
            for i in row:
                if i != '.' and dict_row.get(i):
                    return False
                else:
                    dict_row[i] = i
        return True

38. 外观数列

可以当作双指针来做 一个记录开始位置 一个记录结束为止 相减即为字符串长度

循环次数不确定的时候要用 while

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def countAndSay(self, n: int) -> str:
        prev = "1"
        # 循环n-1次 因为第一次为确定的'1'
        # 每次循环解释 prev
        for i in range(n - 1):
            curr = ""
            pos = 0
            start = 0

            while pos < len(prev):
                while pos < len(prev) and prev[pos] == prev[start]:
                    pos += 1
                curr += str(pos - start) + prev[start]
                start = pos
            prev = curr

        return prev

46. 全排列

回溯

其中要注意 python 中数组拷贝要用 new = old[:]

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
import copy
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        # 回溯算法实现
        # 定义一个布尔数组 标记每个节点的访问状态
        used = [False for i in range(len(nums))]

        # def
        depth = 0 #遍历层的深度
        res=[]
        len_nums = len(nums) 
        path=[]
        def dfs(depth,len_nums,path):
            if depth == len_nums:
                # 遍历到最后一层 添加一个排列结果
                # 用path会出错 必须用 path[:] 它复制列表old到new
                res.append(path[:])
            for i in range(len_nums):
                if  used[i]:
                    continue
                else:
                    path.append(nums[i])
                    used[i]=True
                    dfs(depth+1,len_nums,path)
                    path.pop()
                    used[i]=False
        dfs(depth,len_nums,path)
        return res

47. 全排列 II

去掉重复排列

先对数组排序 避免同一个数字多次使用

要解决重复问题，我们只要设定一个规则，保证在填第 i个数的时候重复数字只会被填入一次即可。而在本题解中，我们选择对原数组排序，保证相同的数字都相邻，然后每次填入的数一定是这个数所在重复数集合中「从左往右第一个未被填过的数字」，即如下的判断条件：

关键代码：

1
2
if  used[i] or (i > 0 and not used[i - 1] and nums[i] == nums[i - 1]):
                    continue
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
import copy
class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:

        # 回溯算法实现
        # 定义一个布尔数组 标记每个节点的访问状态
        used = [False for i in range(len(nums))]
        # 必须要排序
        nums.sort()
        # def
        depth = 0 #遍历层的深度
        res=[]
        len_nums = len(nums) 
        path=[]
        def dfs(depth,len_nums,path):
            if depth == len_nums:
                # 遍历到最后一层 添加一个排列结果
                # 用path会出错 必须用 path[:] 它复制列表old到new
                res.append(path[:])
            for i in range(len_nums):
                if  used[i] or (i > 0 and not used[i - 1] and nums[i] == nums[i - 1]):
                # 遇到相同的数字 只有当前一个相同的数字没有被使用才可以 
                    continue
                else:
                    path.append(nums[i])
                    used[i]=True
                    dfs(depth+1,len_nums,path)
                    path.pop()
                    used[i]=False
        dfs(depth,len_nums,path)
        return res

162. 寻找峰值

找出最大值即满足条件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from typing import List

import numpy as np


class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        max_value = np.max(np.array(nums))

        return nums.index(int(max_value))


if __name__ == '__main__':
    nums = [1, 2, 3, 1]

    f = Solution()
    b = f.findPeakElement(nums)
    print(b)

166. 分数到小数

参考了一个非常清晰的题解

  • java
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
class Solution {
    public String fractionToDecimal(int numerator, int denominator) {
        // 转 long 计算，防止溢出
        long a = numerator, b = denominator;
        // 如果本身能够整除，直接返回计算结果
        if (a % b == 0) return String.valueOf(a / b);
        StringBuilder sb = new StringBuilder();
        // 如果其一为负数，先追加负号
        if (a * b < 0) sb.append('-');
        a = Math.abs(a); b = Math.abs(b);
        // 计算小数点前的，部分，并将余数赋值给 a
        sb.append(String.valueOf(a / b) + ".");
        a %= b;
        Map<Long, Integer> map = new HashMap<>();
        while (a != 0) {
            // 记录当前余数所在答案的位置
            map.put(a, sb.length());
            a *= 10;
            sb.append(a / b);
            a %= b;
            // 如果当前余数之前出现过，则将 [出现位置 - 当前位置] 的部分抠出来（循环小数部分）
            if (map.containsKey(a)) {
                int u = map.get(a);
                return String.format("%s(%s)", sb.substring(0, u), sb.substring(u));
            }
        }
        return sb.toString();
    }
}

  • python

    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
class Solution:
    def fractionToDecimal(self, numerator: int, denominator: int) -> str:
        # 判断是否可以整除
        if numerator % denominator == 0:
            return str(numerator // denominator)
        ans = ''
        # 如果不能整除 判断符号
        if numerator * denominator < 0:
            ans += '-'
            numerator = abs(numerator)
            denominator = abs(denominator)
        # 计算整数部分
        ans += str(numerator // denominator)
        # 计算小数部分
        ans += '.'
        # 出现过的小数位存储
        nums = []
        # 当前余数
        numerator = numerator % denominator
        len_ans = len(ans)
        while numerator != 0:
            nums.append(numerator)
            numerator *= 10
            # 存储数位
            ans += str(numerator // denominator)
            numerator %= denominator
            # 判断当前余数是否出现过
            if nums.__contains__(numerator):
                loc = nums.index(numerator)
                end = len_ans + loc
                return ans[0:end] + '(' + ans[len_ans + loc:] + ')'
        return ans

187. 重复的DNA序列

关键字：哈希表

defaultdict的作用是在于，当字典里的key不存在但被查找时，返回的不是keyError而是一个默认值

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def findRepeatedDnaSequences(self, s: str) -> List[str]:
        ans =[]
        substr=defaultdict(int)
        for i in range(len(s)-10+1):
            temp = s[i:i+10]
            # 切片时间复杂度 O（N）
            substr[temp]+=1
            if substr[temp]==2:
                ans.append(temp)
        return ans

200. 岛屿数量

图的DFS遍历

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
class Solution {
private:
    void dfs(vector<vector<char>>& grid, int r, int c) {
        // 行列范围
        int nr = grid.size();
        int nc = grid[0].size();
        
        //将已经便利过的岛屿标记为2
        grid[r][c] = '2';
        //判断边界情况
        if (r - 1 >= 0 && grid[r-1][c] == '1') dfs(grid, r - 1, c);
        if (r + 1 < nr && grid[r+1][c] == '1') dfs(grid, r + 1, c);
        if (c - 1 >= 0 && grid[r][c-1] == '1') dfs(grid, r, c - 1);
        if (c + 1 < nc && grid[r][c+1] == '1') dfs(grid, r, c + 1);
    }
public:
    int numIslands(vector<vector<char>>& grid) {
        // dfs遍历
        int nr = grid.size();
        if (!nr) return 0;
        int nc = grid[0].size();

        int num_islands = 0;
        for (int r = 0; r < nr; ++r) {
            for (int c = 0; c < nc; ++c) {
                // dfs搜索未访问过的岛屿
                if (grid[r][c] == '1') {
                    ++num_islands;
                    dfs(grid, r, c);
                }
            }
        }

        return num_islands;
    }
};

211. 添加与搜索单词 - 数据结构设计

字典树 神奇！

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
# 字典树
class TreeNode:
    def __init__(self):
        self.children = [None] * 26
        self.isEnd = False

    def insert(self, word: str) -> None:
        node = self
        for ch in word:
            num = ord(ch)-ord('a') # asscii 
            if not node.children[num]:
                node.children[num]= TreeNode()
            node = node.children[num]
        node.isEnd =True

class WordDictionary:

    def __init__(self):
        self.trieRoot = TreeNode()

    def addWord(self, word: str) -> None:
        self.trieRoot.insert(word)

    def search(self, word: str) -> bool:
        def dfs(index: int, node: TreeNode) -> bool:
            if index == len(word):
                return node.isEnd #搜索到叶子结点
            ch = word[index]
            if ch != '.':
                child = node.children[ord(ch) - ord('a')]
                if child is not None and dfs(index + 1, child):
                    return True
            else:
                for child in node.children: # . 可以表任意一个节点 从每一个分支继续搜索
                    if child is not None and dfs(index + 1, child):
                        return True
            return False

        return dfs(0, self.trieRoot)

# Your WordDictionary object will be instantiated and called as such:
# obj = WordDictionary()
# obj.addWord(word)
# param_2 = obj.search(word)

223. 矩形面积

学到一招 先减后加 避免溢出

重叠部分可以求投影的交集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def computeArea(self, ax1: int, ay1: int, ax2: int, ay2: int, bx1: int, by1: int, bx2: int, by2: int) -> int:
        # 计算重叠面积边界
        bothx1 = max(ax1,bx1)
        bothx2 = min(ax2,bx2)

        bothy1 = max(ay1,by1)
        bothy2 = min(ay2,by2)
        # 计算重叠面积
        both_area = 0
        if bothx1<bothx2 and bothy1<bothy2:
            both_area = abs(bothx2-bothx1)*abs(bothy2-bothy1)

        # 先减后加 避免溢出
        return abs(ax1-ax2)*abs(ay1-ay2) - both_area + abs(bx1-bx2)*abs(by1-by2)

230. 二叉搜索树中第K小的元素

二叉搜索树性质：

左子树小于根节点 右子树大于根节点。

二叉搜索树的中序遍历是有序的。

  • pop()函数默认pop最后一个元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 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 kthSmallest(self, root: TreeNode, k: int) -> int:
        stack = []
        # 左根右
        while root or stack:
            while root:
                # 一直遍历到左子树叶子节点 即为最小值 
                stack.append(root)
                root = root.left
            root = stack.pop()
            k -= 1 # 出栈的次序为最小值次序
            if k == 0:
                return root.val
            root = root.right

240. 搜索二维矩阵 II

两种解法 从右上角搜索还是比较巧妙的！

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 searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        # # 先行搜索 找到最接近target 的值
        # ans_row=[]
        # for row in matrix:
        #     for i in row:
        #         if i == target:
        #             return True
        #         elif i > target:
        #             break
        #         else:
        #             ans_row = matrix.index(row)
        # print(ans_row)
        # return 0 
        # 解法2 右上角搜索 大于target说明当前列全部大于 向左移动 小于，说明当前行全部小于 向下移动（因为在最右上角）
        m,n=len(matrix),len(matrix[0])
        x,y=0,n-1
        while x<m and y>=0 :
            if matrix[x][y]==target:
                return True
            elif matrix[x][y] >target:
                y-=1
            elif matrix[x][y]<target:
                x+=1
        return False

319. 灯泡开关

脑筋急转弯 降维打击

如果我们将所有的灯泡从左到右依次编号为1,2,3…n 会发现第i次只对i的倍数进行切换状态

灯泡初始状态是灭的，偶数次切换也是灭的 奇数次切换变亮，所以求k的约数个数即可

但目的是判断奇偶性，所以只用判断k是不是完全平方数，如果是一定存在 k=x*x 即约数个数为奇数个

判断1,2,3…n中有几个完全平方数，对n开根号即可

  • sqrt(n + 0.5); sqrt是浮点数运算，强制类型转换为int会向下取整，因此增加0.5保证精度。
1
2
3
4
5
6
class Solution {
public:
    int bulbSwitch(int n) {
        return sqrt(n + 0.5);
    }
};

🌟430. 扁平化多级双向链表

参考的题解 再看看

447. 回旋镖的数量

  • hash_points = defaultdict(int)

defaultdict，当字典里的key不存在但被查找时，返回的不是keyError而是一个工厂函数的默认值，比如list对应[ ]，str对应的是空字符串，set对应set( )，int对应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
from collections import defaultdict
from math import sqrt
from typing import List


class Solution:
    def numberOfBoomerangs(self, points: List[List[int]]) -> int:
        ans = 0
        for p in points:
            # defaultdict，当字典里的key不存在但被查找时，返回的不是keyError而是一个工厂函数的默认值，比如list对应[ ]，str对应的是空字符串，set对应set( )，int对应0
            hash_points = defaultdict(int)
            # 使用哈希表存储到该点距离相等的point个数
            for temp_q in points:
                dis = sqrt(pow((p[0] - temp_q[0]), 2) + pow((p[1] - temp_q[1]), 2))
                hash_points[dis] += 1
            for v in hash_points.values():
                # 全排列
                ans += v * (v - 1)

        return ans


if __name__ == '__main__':
    points = [[0, 0], [1, 0], [2, 0]]

    f = Solution()
    b = f.numberOfBoomerangs(points)
    print(b)

437. 路径总和 III

注意节点正负性 一定要遍历到最后

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.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def pathSum(self, root: TreeNode, targetSum: int) -> int:
        # 判断当前节点的路径数量
        def get_sum(node, target):
            # 采用递归的思路 遍历左子树和右子树
            temp_ans=0
            if node is None:
                return 0
            if node.val == target:
                temp_ans+=1
                # return temp_ans
                # 不能直接return 因为节点有可能为负数
            temp_ans+=get_sum(node.left, target - node.val)
            temp_ans+=get_sum(node.right, target - node.val)
            return temp_ans
        if root is None:
            return 0
        # 寻找当前节点路径数量
        ans = get_sum(root, targetSum)
        # 寻找当前节点子树的路径数量
        ans +=self.pathSum(root.left,targetSum)
        ans +=self.pathSum(root.right,targetSum)
        return ans

524. 通过删除字母匹配到字典里最长单词

匹配两个字符串 可以使用双指针的方法

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
from typing import List


class Solution:
    def findLongestWord(self, s: str, dictionary: List[str]) -> str:
        # 使用双指针实现字符串匹配
        ans = ''
        # 循环匹配字典中的字符串
        for word in dictionary:
            # 双指针
            i, j = 0, 0
            while i < len(word) and j < len(s):
                # 在字符串s中寻找word 也就是说word中的每个字母都要在s中按顺序出现
                if word[i] == s[j]:
                    i += 1
                j += 1
            if i == len(word):
                # 匹配成功 维护最长字串 长度相同 返回长度最长且 字典序 最小的字符串
                if (len(word) > len(ans)) or (len(word) == len(ans) and word < ans):
                    ans = word

        return ans


if __name__ == '__main__':
    s = "abpcplea"
    dictionary = ["ale", "apple", "monkey", "plea"]

    f = Solution()
    b = f.findLongestWord(s,dictionary)
    print(b)

583. 两个字符串的删除操作

值得注意的是 text[0:i-1]对应的dp数组位置为dp[i-1][j]

text 数组对应的字符下标从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
class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)
        # dp[i][j] 表示word1[0:i] 和 word[0:j] 的最大公共子序列长度
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        # print(dp)
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                # 当前位置字符串相同
                if word1[i - 1] == word2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    # 当前位置字符串不相同 取当前位置  dp[i - 1][j] 和 dp[i][j - 1] 的最大值
                    # 若text1[i-1] != text2[j-1]，也就是说两个字符串的最后一位不相等，那么字符串text1的[1,i]区间和字符串text2的[1,j]区间的最长公共子序列长度无法延长，因此f[i][j]就会继承f[i-1][j]与f[i][j-1]中的较大值
                    # 值得注意的是 text[0:i-1]对应的dp数组位置为dp[i-1][j]
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

        lcs = dp[m][n]
        return m - lcs + n - lcs


if __name__ == '__main__':
    word1 = "sea"
    word2 = "eata"

    f = Solution()
    b = f.minDistance(word1, word2)
    print(b)

638. 大礼包

使用了 lru_cache 参数必须可以使用hash值作为索引

  • 可哈希的元素：int、float、str、tuple、自定义的类的实例对象

  • 不可哈希的元素：list、set、dict

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
from functools import lru_cache
class Solution:
    def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int:
        # 价格 price
        # 大礼包种类 special
        # 总需求 need

        # 1. 过滤掉 不优惠的大礼包组合
        filter_sp=[]
        for sp in special:
            temp_sp=[]
            for i in range(len(sp)-1):
                temp_sp.append(sp[i]*price[i])
            if sum(temp_sp)>sp[-1]: # 比直接购买便宜
                filter_sp.append(sp)
        # 2.计算最优组合
        @lru_cache(None)
        # 缓存 加速重复计算
        def dfs(cur_needs):
            # 不购买任何大礼包，原价购买购物清单中的所有物品
            min_price = sum(need * price[i] for i, need in enumerate(cur_needs))
            for sp in filter_sp:
                # 大礼包价格  
                sp_price =sp[-1]
                # 当前需求为 cur_needs 剩余需求为 next_needs
                next_needs=[]
                for good_index in range(len(price)):
                    if sp[good_index]>cur_needs[good_index]:
                        # 不能购买超过需求的商品
                        break
                    next_needs.append(cur_needs[good_index]-sp[good_index])
                if len(next_needs)==len(cur_needs): #大礼包可以购买 没有超出数量限制
                    # 比较最优价格
                    min_price=min(min_price,sp_price+dfs(tuple(next_needs)))
            return min_price

        return dfs(tuple(needs))
        # 因为使用了 lru_cache 而list不能hash 所以必须转换为tuple

673. 最长递增子序列的个数

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
from typing import List


class Solution:

    def findNumberOfLIS(self, nums: List[int]) -> int:

        # 使用动态规划 dp 数组存当前位置最长子序列长度
        # cnt 数组存放当前位置最长子序列数量
        # 状态转移方程 dp[i] = max(dp[j]) + 1) 且num[j]<num[i]
        max_len = 0
        ans = 0
        dp = [0] * len(nums)
        cnt = [0] * len(nums)
        # 遍历数组
        for i, value in enumerate(nums):
            dp[i] = 1
            cnt[i] = 1
            # 寻找当前位置的最长子序列
            # 往历史最长子序列中加入nums[i]
            # 相应的dp[i]+1 cnt[i]根据历史cnt[j]更新

            for j in range(i):
                if value > nums[j]:
                    if dp[j] + 1 > dp[i]:
                        dp[i] = dp[j] + 1
                        cnt[i] = cnt[j]
                    elif dp[j] + 1 == dp[i]:
                        cnt[i] += cnt[j]
            if dp[i] > max_len:
                # 更新数据
                max_len = dp[i]
                ans = cnt[i]
            elif dp[i] == max_len:
                # 答案为多有满足 dp[i] == max_len 的cnt[i]之和
                ans += cnt[i]
        return ans


if __name__ == '__main__':
    board = [1, 3, 5, 4, 7]

    f = Solution()
    b = f.findNumberOfLIS(board)
    print(b)

678. 有效的括号字符串

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 checkValidString(self, s: str) -> bool:
        # 堆栈模拟实现
        left_stack = []
        star_stack = []
        for index, ch in enumerate(s):
            # 遇到左括号 和 星号 分别入栈
            # 存储下标 方便比较
            if ch == '(':
                left_stack.append(index)
            elif ch == "*":
                star_stack.append(index)
            # 遇到右括号匹配
            elif ch == ')':
                # 因为星号可以任意匹配 所以优先匹配左括号
                if left_stack:
                    left_stack.pop()
                # 左括号不足的情况下使用星号匹配
                elif star_stack:
                    star_stack.pop()
                # 都不能匹配则不满足有效的括号字符串
                else:
                    return False

        # 遍历寻找右括号结束后 匹配左括号和星号
        # 匹配时必须是右侧的星号和左侧的左括号的匹配

        while left_stack:
            # 星号消耗完了
            if not star_stack:
                return False
            # 右侧星号消耗完了
            elif left_stack[-1] > star_stack[-1]:
                return False
            else:
                left_stack.pop()
                star_stack.pop()
        return True


if __name__ == '__main__':
    str = "()()()((((()((()(()())(()))(())))((()((()())*(((())()))(()((())(((((((())()*)())((())*))))*)())()))"

    f = Solution()
    b = f.checkValidString(str)
    print(b)

725. 分隔链表

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 singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def splitListToParts(self, head: ListNode, k: int) -> List[ListNode]:
        print(head)
        cur, l = head, 0
        # 计算链表长度
        while cur:
            l += 1
            cur = cur.next
        # 均分 求余
        each, remain = l // k, l % k
        cur, ans, idx = head, [None] * k, 0
        while cur:
            ans[idx] = cur
            # 使用last断开链表 last.next = None
            last = None
            # idx < remain控制左侧数链表于右侧链表
            for i in range(each + (idx < remain)):
                last = cur
                cur = cur.next
            idx += 1
            last.next = None
        return ans



1218. 最长定差子序列

动态规划实现

从左到右遍历，计算以arr[i]为结尾的最长的等差子序列的长度。

学到一招，vector的遍历 除了使用迭代器for (vector<int>::iterator it=arr.begin();it!=arr.end();it++) ,还可以简写for (int v: arr)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int longestSubsequence(vector<int>& arr, int difference) {
            // 动态规划 
            // unordered_map存储dp值
            unordered_map<int, int> dp;
            int ans =0;
            for (vector<int>::iterator it=arr.begin();it!=arr.end();it++)
            {
                dp[*it]=dp[*it-difference]+1;
                // 以当前数值为结尾的等差序列长度
                ans = max(ans,dp[*it]);
            }
            return ans;
    }
};

1894. 找到需要补充粉笔的学生编号

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
from typing import List


class Solution:
    def chalkReplacer(self, chalk: List[int], k: int) -> int:
        # 判断第几轮需要补充粉笔
        signal_loop = sum(chalk)
        if (k % signal_loop) == 0:
            return 0
        else:
            chalk_loop = k // signal_loop
            k -= chalk_loop * signal_loop
            # 找出粉笔不足的下标
            # 重整数组 计算当前位置需要累计消耗粉笔数量
            for i in range(len(chalk)):
                if chalk[i] > k:
                    return i
                else:
                    k -= chalk[i]


if __name__ == '__main__':
    chalk = [3, 4, 1, 2]
    k = 25

    f = Solution()
    b = f.chalkReplacer(chalk, k)
    print(b)

困难

68. 文本左右对齐

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
from typing import List


class Solution:
    def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
        # 使得每行单词接近maxWidth
        """
        每个单词之间至少有一个空格
        特殊情况：
        1.单词数大于1时 左侧空格数多于右侧
        2.当前行只有一个单词时 居左对齐 空格补充长度
        3.最后一行 居左对齐 每个单词之间1个空格 末尾空格补充长度
        """
        totalLineWords = []
        signalLineWord = []

        for temp_len in words:
            if len(temp_len) + self.get_sum(signalLineWord) + len(signalLineWord) <= maxWidth:
                signalLineWord.append(temp_len)
                # print(signalLineWord)
            else:
                totalLineWords.append(signalLineWord)
                signalLineWord = [temp_len]
        totalLineWords.append(signalLineWord)
        ans = self.put_blank(totalLineWords, maxWidth)
        print(ans)
        for lens in ans:
            print(len(lens))
        return ans

    # 得到单词总长度
    def get_sum(self, word_lsits: List[str]):
        # 统计每个单词长度
        word_len = [len(i) for i in word_lsits]
        return sum(word_len)

    # 填充空格
    def put_blank(self, totalLineWords: List[List[str]], maxWidth: int):
        # print(totalLineWords[:-1])
        ans = []
        for line in totalLineWords[:-1]:
            if len(line) == 1:
                ans.append(line[0] + self.insert_blank(maxWidth - len(line[0])))
            else:
                # 计算平均可插入空格
                temp_sum_word = self.get_sum(line)
                mean_blank = int((maxWidth - temp_sum_word) / (len(line) - 1))
                # 计算从左到右的空格数
                mod_blank = (maxWidth - temp_sum_word) % (len(line) - 1)
                # print(temp_sum_word)
                # print(temp_blank, mod_blank)
                # 填充空格
                temp_str = ''
                temp_word_line = line[:-1]
                # mean
                for word_index in range(len(line[:-1])):
                    temp_word_line[word_index] = line[:-1][word_index] + self.insert_blank(mean_blank)
                # mod
                for index in range(mod_blank):
                    temp_word_line[index] += ' '
                # str
                for word in temp_word_line:
                    temp_str += word
                temp_str += line[-1]
                ans.append(temp_str)
        # 最后一行
        if len(totalLineWords[-1]) == 1:
            ans.append(totalLineWords[-1][0] + self.insert_blank(maxWidth - len(totalLineWords[-1][0])))
        else:
            temp_str = ''
            for word in totalLineWords[-1][:-1]:
                temp_str += word + ' '
            temp_str += totalLineWords[-1][-1]
            ans.append(temp_str + self.insert_blank(maxWidth - len(temp_str)))
        return ans

    def insert_blank(self, num: int):
        return ' ' * num


if __name__ == '__main__':
    words = ["What", "must", "be", "acknowledgment", "shall", "be"]
    maxWidth = 16
    f = Solution()
    b = f.fullJustify(words, maxWidth)

🌟212. 单词搜索 II

有点难 暂时不看

282. 给表达式添加运算符

官方题解比较巧妙 后缀表达式可以解决带括号的

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
from typing import List


class Solution:
    def addOperators(self, num: str, target: int) -> List[str]:
        num_len = len(num)
        ans = []

        # 递归函数

        def backtrack(expr, loc, res, mul):
            """
            :param expr: 当前构造的表达式
            :param loc: 当前枚举到的字符串位置
            :param res: 当前表达式的计算结果
            :param mul: 最后一个连乘表达式的计算结果 因为乘法的优先级高 下一步计算时 如果为乘法 应该为res-mul+mul*new_num
            :return: null
            """
            if loc == num_len:
                if target == res:
                    ans.append(''.join(expr))
                return
                # 未达到最大长度 继续递归寻找可能的字符串
            signIndex = len(expr)  # 符号位
            if loc > 0:
                expr.append('')  # 符号位占位
            temp_num = 0  # 连续的数字
            for j in range(loc, num_len):
                # 去除前导0 即第一位不能是0
                if j > loc and num[loc] == '0':
                    break
                temp_num = temp_num * 10 + int(num[j])
                expr.append(num[j])
                # 判断符号的情况
                if loc == 0:
                    backtrack(expr, j + 1, temp_num, temp_num)
                else:
                    expr[signIndex] = '+'
                    backtrack(expr, j + 1, res + temp_num, temp_num)
                    expr[signIndex] = '-'
                    backtrack(expr, j + 1, res - temp_num, -temp_num)
                    expr[signIndex] = '*'
                    backtrack(expr, j + 1, res - mul + mul * temp_num, mul * temp_num)
            del expr[signIndex:]  # 清除计算多余的字符串

        backtrack([], 0, 0, 0)
        return ans


if __name__ == '__main__':
    num = "123"
    target = 6

    f = Solution()
    b = f.addOperators(num, target)
    print(b)

301. 删除无效的括号

暂时不做

352. 将数据流变为多个不相交区间

说实话 题目给的示例没看懂

看了官方题解后发现这是一个区间问题 https://leetcode-cn.com/problems/data-stream-as-disjoint-intervals/solution/jiang-shu-ju-liu-bian-wei-duo-ge-bu-xian-hm1r/

使用有序映射支持查询「最大的比某个元素小的键」以及「最小的比某个元素大的键」这两个操作。

题目有点难，先学学bisect模块吧，用在二分搜索。

502. IPO

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
from heapq import heappush, heappop
from typing import List


class Solution:
    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:
        # 收益肯定比投资大 所以当 当前资本可以完成耗资最大的项目时 所获利润一定足够完成剩余项目 因此从项目中选择k个利润最大的项目完成即可
        if w >= max(capital):
            return w + sum(nlargest(k, profits))
        #  nlargest(k,list) nsmallest() 找出集合中最大或者最小的k个元素
        n = len(profits)
        # 已完成项目数
        curr = 0
        # 将投资成本和利润绑定
        arr = [(capital[i], profits[i]) for i in range(n)]
        # 按从小到大的顺序排序
        arr.sort(key=lambda x: x[0])
        print(arr)
        pq = []
        for _ in range(k):
            while curr < n and arr[curr][0] <= w:
                # 成本充足的情况下 将利润压入大根堆中
                heappush(pq, -arr[curr][1])
                curr += 1
            print(pq)
            if pq:
                # 取相反数 相加
                w -= heappop(pq)
            else:
                break

        return w


if __name__ == '__main__':
    k = 3
    w = 0
    profits = [1, 2, 3]  # 纯利润
    capital = [0, 1, 2]  # 投资最小资本
    f = Solution()
    b = f.findMaximizedCapital(k, w, profits, capital)

🌟600. 不含连续1的非负整数

题解：https://leetcode-cn.com/problems/non-negative-integers-without-consecutive-ones/solution/suan-fa-xiao-ai-wo-lai-gei-ni-jie-shi-qi-4nh4/

太难了慢慢攻克