每天编程练习和打卡记录

发表于 | 分类于 |

2022.1.24

今日天气：雪

善战者，制人而不制于人

——孙子兵法

今日编程练习

Leetcode2045.到达目的地的第二短时间

描述

城市用一个 双向连通 图表示，图中有 n 个节点，从 1 到 n 编号（包含 1 和 n）。图中的边用一个二维整数数组 edges 表示，其中每个 edges[i] = [ui, vi] 表示一条节点 ui 和节点 vi 之间的双向连通边。每组节点对由 最多一条 边连通，顶点不存在连接到自身的边。穿过任意一条边的时间是 time 分钟。

每个节点都有一个交通信号灯，每 change 分钟改变一次，从绿色变成红色，再由红色变成绿色，循环往复。所有信号灯都 同时 改变。你可以在 任何时候 进入某个节点，但是 只能 在节点 信号灯是绿色时 才能离开。如果信号灯是 绿色 ，你 不能 在节点等待，必须离开。

第二小的值 是 严格大于 最小值的所有值中最小的值。

例如，[2, 3, 4] 中第二小的值是 3 ，而 [2, 2, 4] 中第二小的值是 4 。

给你 n、edges、time 和 change ，返回从节点 1 到节点 n 需要的 第二短时间 。

注意：

你可以 任意次 穿过任意顶点，包括 1 和 n 。
你可以假设在 启程时 ，所有信号灯刚刚变成 绿色 。

思路

这个题的点有两个，一个是怎么处理次短，一个是怎么计算时间

一开始只看出了第二点，然后以为是可以无限次通过某个点的简单的BFS，遂超时

看了题解才知道只需要找出最短路，然后处理一下即可

如何记录次短路呢？我们思考次短路是怎么产生的

由于所有路径都是双向的，所以我们只需要走最短路到达某点，然后再随便从该点向它相邻的另一个点走个来回就好了

所以，任何一个点的次短路长度不会超过最短路+2

如何判断有没有长度为最短路+1的次短路呢？

在BFS序中，我们把一个点的邻接点分为三种：

父节点，权值恰好比该点少1的节点

兄弟节点，权值等于该节点的点

子节点，权值为该节点减去1的点

那么，我们可以观察到，父节点如果有长度+1次短路，子节点也一定有。如果一个节点有兄弟，可以先走最短路到兄弟节点，然后一步走到该节点形成+1次短路

子节点对父节点的+1次短路无贡献

所以，我们在BFS时，进队列时确定最短路长度，出队列时，就可以确定次短路长度

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
50
51
from queue import Queue


class Solution:
    def cal(self, cur: int, time: int, change: int) -> int:
        if time % (2 * change) == 0:
            return time * cur
        else:
            base = 0
            wait = 0
            for i in range(1, cur + 1):
                if (i * time // change) % 2 == 1:
                    base = i
                    wait = change - i * time % change
                    break
            if base == 0:
                return time * cur
            else:
                return time * cur + wait * ((cur - 1) // base)
            


    def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:
        d = defaultdict(list)
        v = []
        sv = []
        for edge in edges:
            d[edge[0]].append(edge[1])
            d[edge[1]].append(edge[0])
        
        for i in range(n + 1):
            v.append(-1)
            sv.append(-1)

        q = Queue()
        q.put([1, 0])
        v[1] = 0
        while not q.empty():
            cur = q.get()
            sv[cur[0]] = v[cur[0]] + 2
            for i in d[cur[0]]:
                if v[i] == -1:
                    q.put([i, cur[1] + 1])
                    v[i] = cur[1] + 1
                else:
                    if v[i] == v[cur[0]]:
                        sv[cur[0]] = v[cur[0]] + 1
                    if v[i] + 1 == sv[i] and v[i] == v[cur[0]] - 1:
                        sv[cur[0]] = v[cur[0]] + 1

        return self.cal(sv[n], time, change)

2022.1.23

今日天气：多云

人生不得长少年，莫惜床头沽酒钱

——蜀葵花

今日编程练习

Leetcode2034.股票价格波动

描述

给你一支股票价格的数据流。数据流中每一条记录包含一个 时间戳 和该时间点股票对应的 价格 。

不巧的是，由于股票市场内在的波动性，股票价格记录可能不是按时间顺序到来的。某些情况下，有的记录可能是错的。如果两个有相同时间戳的记录出现在数据流中，前一条记录视为错误记录，后出现的记录 更正 前一条错误的记录。

请你设计一个算法，实现：

更新 股票在某一时间戳的股票价格，如果有之前同一时间戳的价格，这一操作将 更正 之前的错误价格。
找到当前记录里 最新股票价格 。最新股票价格 定义为时间戳最晚的股票价格。
找到当前记录里股票的 最高价格 。
找到当前记录里股票的 最低价格 。

请你实现 StockPrice 类：

StockPrice() 初始化对象，当前无股票价格记录。
void update(int timestamp, int price) 在时间点 timestamp 更新股票价格为 price 。
int current() 返回股票 最新价格 。
int maximum() 返回股票 最高价格 。
int minimum() 返回股票 最低价格 。

思路

建立大顶小顶两个二叉堆

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
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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
class StockPrice:

    def __init__(self):
        self.maxkey = defaultdict(int)
        self.maxheap = [[0, 0]]
        self.minkey = defaultdict(int)
        self.minheap = [[0, 0]]
        self.curprice = [0, 0]

    def maxdown(self, p: int) -> None:
        s = p * 2
        while s < len(self.maxheap):
            if not (s + 1 >= len(self.maxheap) or self.maxheap[s + 1][1] < self.maxheap[s][1]):
                s += 1
            if self.maxheap[s][1] > self.maxheap[p][1]:
                t = self.maxheap[s]
                self.maxheap[s] = self.maxheap[p]
                self.maxheap[p] = t
                t = self.maxkey[self.maxheap[p][0]]
                self.maxkey[self.maxheap[p][0]] = self.maxkey[self.maxheap[s][0]]
                self.maxkey[self.maxheap[s][0]] = t
                p = s
                s = p * 2
            else:
                break

    def maxup(self, p: int) -> None:
        s = p // 2
        while s > 0:
            if self.maxheap[s][1] < self.maxheap[p][1]:
                t = self.maxheap[s]
                self.maxheap[s] = self.maxheap[p]
                self.maxheap[p] = t
                t = self.maxkey[self.maxheap[p][0]]
                self.maxkey[self.maxheap[p][0]] = self.maxkey[self.maxheap[s][0]]
                self.maxkey[self.maxheap[s][0]] = t
            p = s
            s = p // 2

    def mindown(self, p: int) -> None:
        s = p * 2
        while s < len(self.minheap):
            if not (s + 1 >= len(self.minheap) or self.minheap[s + 1][1] > self.minheap[s][1]):
                s += 1
            if self.minheap[s][1] < self.minheap[p][1]:
                t = self.minheap[s]
                self.minheap[s] = self.minheap[p]
                self.minheap[p] = t
                t = self.minkey[self.minheap[p][0]]
                self.minkey[self.minheap[p][0]] = self.minkey[self.minheap[s][0]]
                self.minkey[self.minheap[s][0]] = t
                p = s
                s = p * 2
            else:
                break

    def minup(self, p: int) -> None:
        s = p // 2
        print(p, s)
        while s > 0:
            if self.minheap[s][1] > self.minheap[p][1]:
                t = self.minheap[s]
                self.minheap[s] = self.minheap[p]
                self.minheap[p] = t
                t = self.minkey[self.minheap[p][0]]
                self.minkey[self.minheap[p][0]] = self.minkey[self.minheap[s][0]]
                self.minkey[self.minheap[s][0]] = t
            p = s
            s = p // 2

    def remove(self, timestamp: int) -> None:
        p = self.maxkey[timestamp]
        del self.maxkey[timestamp]
        if p != len(self.maxheap) - 1:
            self.maxheap[p] = self.maxheap[len(self.maxheap) - 1]
            self.maxkey[self.maxheap[p][0]] = p
            del self.maxheap[-1]
            self.maxdown(p)
            self.maxup(p)
        else:
            del self.maxheap[-1]

        p = self.minkey[timestamp]
        del self.minkey[timestamp]
        if p != len(self.minheap) - 1:
            self.minheap[p] = self.minheap[len(self.minheap) - 1]
            self.minkey[self.minheap[p][0]] = p
            del self.minheap[-1]
            self.mindown(p)
            self.minup(p)
        else:
            del self.minheap[-1]

    def insert(self, timestamp: int, price: int) -> None:
        self.maxheap.append([timestamp, price])
        self.maxkey[timestamp] = len(self.maxheap) - 1
        self.maxup(len(self.maxheap) - 1)
        self.minheap.append([timestamp, price])
        self.minkey[timestamp] = len(self.minheap) - 1
        self.minup(len(self.minheap) - 1)

    def update(self, timestamp: int, price: int) -> None:
        if timestamp >= self.curprice[0]:
            self.curprice[0] = timestamp
            self.curprice[1] = price
        
        if self.maxkey[timestamp] != 0:
            self.remove(timestamp)
        self.insert(timestamp, price)

        #print(self.maxheap)
        #print(self.minheap)
        

    def current(self) -> int:
        return self.curprice[1]

    def maximum(self) -> int:
        return self.maxheap[1][1]

    def minimum(self) -> int:
        return self.minheap[1][1]


# Your StockPrice object will be instantiated and called as such:
# obj = StockPrice()
# obj.update(timestamp,price)
# param_2 = obj.current()
# param_3 = obj.maximum()
# param_4 = obj.minimum()

2022.1.22

今日天气：晴

无论面对怎样的困难，比克服困难的技能更重要的，是克服困难的动机。只要内心的火焰没有熄灭，无论寒风再凛冽，活着也是一件温暖的事情

今日编程练习

Leetcode1332.删除回文子序列

描述

给你一个字符串 s，它仅由字母 ‘a’ 和 ‘b’ 组成。每一次删除操作都可以从 s 中删除一个回文 子序列。

返回删除给定字符串中所有字符（字符串为空）的最小删除次数。

「子序列」定义：如果一个字符串可以通过删除原字符串某些字符而不改变原字符顺序得到，那么这个字符串就是原字符串的一个子序列。

「回文」定义：如果一个字符串向后和向前读是一致的，那么这个字符串就是一个回文。

思路

所有的a构成回文子序列，所有的b也构成回文子序列，因此最差情况下也可以先删除a再删除b来得到

所以，如果原字符串是回文字符串，答案是1，否则是2

Python

1
2
3
4
5
6
class Solution:
    def removePalindromeSub(self, s: str) -> int:
        for i in range(len(s) // 2):
            if s[i] != s[len(s) - 1 - i]:
                return 2
        return 1

2021.1.21

今日天气：雪

天下雷行，物与无妄。先王以茂对时，育万物

——易经

今日编程练习

Leetcode1345.跳跃游戏 IV

描述

给你一个整数数组 arr ，你一开始在数组的第一个元素处（下标为 0）。

每一步，你可以从下标 i 跳到下标：

i + 1 满足：i + 1 < arr.length
i - 1 满足：i - 1 >= 0
j 满足：arr[i] == arr[j] 且 i != j

请你返回到达数组最后一个元素的下标处所需的 最少操作次数 。

注意：任何时候你都不能跳到数组外面。

思路

从起点开始的BFS

但为了准备这个BFS，我们需要建立一个邻接表，之后我注意到，当某个邻接表的一个元素被遍历到的时候，整个邻接表的其它元素接着就会被遍历到，因此，我又设置了一个标记数组来表示某个邻接表是否被遍历了

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
from queue import Queue


class Solution:
    def minJumps(self, arr: List[int]) -> int:
        d = defaultdict(list)
        d2 = defaultdict(int)
        v = []
        p = []
        for i in range(len(arr)):
            d[arr[i]].append(i)
            d2[arr[i]] = 0
            v.append(False)
            p.append(0x7fffffff)

        cur = 0
        p[0] = 0
        q = Queue()
        q.put(0)
        v[0] = True
        while q.qsize() != 0:
            cur = q.get()
            if cur > 0 and not v[cur - 1]:
                p[cur - 1] = p[cur] + 1
                q.put(cur - 1)
                v[cur - 1] = True
            if cur < len(arr) - 1 and not v[cur + 1]:
                p[cur + 1] = p[cur] + 1
                q.put(cur + 1)
                v[cur + 1] = True
            if d2[arr[cur]] == 0:
                for i in d[arr[cur]]:
                    if v[i]:
                        continue
                    p[i] = p[cur] + 1
                    q.put(i)
                    v[i] = True
                d2[arr[cur]] = 1

        return p[len(arr) - 1]

2022.1.20

今日天气：雪

孤独如荒漠，理性如孤岛

今日编程练习

Leetcode2029.石子游戏 IX

描述

Alice 和 Bob 再次设计了一款新的石子游戏。现有一行 n 个石子，每个石子都有一个关联的数字表示它的价值。给你一个整数数组 stones ，其中 stones[i] 是第 i 个石子的价值。

Alice 和 Bob 轮流进行自己的回合，Alice 先手。每一回合，玩家需要从 stones 中移除任一石子。

如果玩家移除石子后，导致 所有已移除石子 的价值 总和 可以被 3 整除，那么该玩家就 输掉游戏 。
如果不满足上一条，且移除后没有任何剩余的石子，那么 Bob 将会直接获胜（即便是在 Alice 的回合）。

假设两位玩家均采用 最佳 决策。如果 Alice 获胜，返回 true ；如果 Bob 获胜，返回 false 。

思路

先考虑问题的初始状态，此时拿走的总价值是0

那么Alice第一次该怎么拿呢？显然她不能拿走3的倍数，不然一下就输了

所以Alice的策略只有两种：拿走模3余1的数和拿走模3余2的数

假设Alice拿走了模3余1的数，总价值现在模3余1，那么Bob此时又该怎么选呢？

显然Bob只能也选择模3余1的数，把总价值变成模3余2，或者Bob选择3的倍数，总价值还是模3余1

我们先不考虑3的倍数，因为3的倍数拿走之后，总价值不会变化，实际上它起到了仅仅是一个“空过”的作用

没有3的情况

假设只有模3余1的数（以下简称为1）N1个，模3余2的数（以下简称为2）N2个，那么，Alice有没有必胜策略呢？

简单推导一下发现，如果Alice拿了1，Bob也只能拿1，然后Alice只能拿2，Bob又只能拿1，如此循环，如果1先没了，Alice胜，2先没了，Bob胜

简单来说，游戏过程变成了：

1.Alice拿走了X（X表示1或2）

2.Bob拿走了X，接着Alice拿走了Y（Y = 3 - X）

3.重复2，直到某个人无法拿到他想要的石头

上述游戏过程中，Alice拿走了1个X，n个Y，Bob拿走了n个X，然后，X没有了

那么，Alice的必胜策略其实很简单了，她只需要保证X的数量首先大于1，并且小于等于Y即可

所以在这种情况下，只要1和2的数量大于0，Alice必胜

如果至少有一种的数量小于0，Bob必胜

有3的情况

假设有3的倍数（简称为3），该怎么办呢？

上面说了，3起到一个空过的作用，当某人发现自己情况不利时，可以选3的倍数，空过，让对方面临自己的局面

但事情没有这么简单，如果Bob发现Alice给他设局，Bob选择空过的话，Alice也可以选择空过，让Bob的空过作废

所以，当3的次数是偶数次的时候，对Alice来说局势和没有3的情况一致

如果是奇数次呢？

这意味着Bob空过之后，Alice将没有反制他的机会。对于Alice来说，此时需要反其道而行之，选择数目较多的，等待Bob空过来使得局面反转

要是Bob不反转怎么办？那Alice就要主动帮他反转

此时，一局游戏应该是这样的：

1.Alice拿走了X

2.Bob拿走了X，Alice拿走了3

3.Bob拿走了Y，Alice拿走了X

4.重复3，直到某人拿不到他想要的石头

发现Alice拿走了n+1个X，Bob拿走了n个Y，1个X

所以，需要X的数量严格大于Y+2才行，否则，无论Alice怎么空过，等待她的只有死局

Python

1
2
3
4
5
6
7
8
9
class Solution:
    def stoneGameIX(self, stones: List[int]) -> bool:
        temp = [0, 0, 0]
        for i in stones:
            temp[i % 3] += 1
        if temp[0] % 2 == 1:
            return abs(temp[1] - temp[2]) > 2
        else:
            return not(temp[1] == 0 or temp[2] == 0)

2022.1.19

今日天气：阴转晴

楚伐随，随曰：“我无罪”，楚曰：“我蛮夷也”

——史记·楚世家

今日编程练习

Leetcode219.存在重复元素 II

描述

给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。

思路

字典题，只不过需要搞一个过期处理

Python

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        d = defaultdict(int)
        
        for i in range(len(nums)):
            if d[nums[i]] > 0:
                return True
            d[nums[i]] += 1
            if i >= k:
                d[nums[i - k]] -= 1
        
        return False

2021.11.3

今日天气：晴

“你的面前有一面墙，向上无限高，向下无限深，向左无限长，向右也无限长，这面墙是什么？”

“死亡”

——三体2·黑暗森林

今日编程练习

Leetcode367.有效的完全平方数

描述

给定整数num，不用内置函数判断它是否是完全平方数。

思路

根据num的范围二分即可。标准答案用了牛顿迭代法……

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        low = 0
        high = 1 << 16
        while low < high:
            mid = (low + high) >> 1
            temp = mid * mid
            if num == temp:
                return True
            elif num < temp:
                high = mid
            else:
                low = mid + 1
        return False

2021.11.1

今日天气：晴

并非是我选择了这样的一生，而是这一生选择了我

——刺客信条

今日编程练习

Leetcode575.分糖果

描述

给定一个偶数长度的数组，其中不同的数字代表着不同种类的糖果，每一个数字代表一个糖果。你需要把这些糖果平均分给一个弟弟和一个妹妹。返回妹妹可以获得的最大糖果的种类数。

思路

每种都给妹妹一块即可，最多给她m/2种

Python

1
2
3
4
5
6
7
8
9
10
class Solution:
    def distributeCandies(self, candyType: List[int]) -> int:
        max_l = len(candyType) // 2
        max_t = 0
        d = defaultdict(int)
        for i in candyType:
            if d[i] == 0:
                max_t += 1
            d[i] += 1
        return min(max_l, max_t)

2021.10.31

今日天气：阴

他知道要想逃避现实，最好的方式就是深深介入现实之中。

——三体·黑暗森林

今日编程练习

Leetcode500.键盘行

描述

给你一个字符串数组 words ，只返回可以使用在 美式键盘 同一行的字母打印出来的单词。键盘如下图所示。

美式键盘 中：

第一行由字符 "qwertyuiop" 组成。
第二行由字符 "asdfghjkl" 组成。
第三行由字符 "zxcvbnm" 组成。

思路

简简单单一个数组

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def findWords(self, words: List[str]) -> List[str]:
        temp = [
            2, 3, 3, 2, 1, 2, 2, 2, 1, 2, 2, 2, 3, 3,
            1, 1, 1, 1, 2, 1, 1, 3, 1, 3, 1, 3
        ]
        ret = []
        for s in words:
            flag = temp[ord(s[0].lower()) - ord('a')]
            for i in range(1, len(s)):
                if flag != temp[ord(s[i].lower()) - ord('a')]:
                    flag = 0
                    break
            if flag != 0:
                ret.append(s)
        return ret

2021.10.30

今日天气：晴

她缓慢地点点头：“人生苦短啊。”，她最后这句话出动了他心灵深处的什么东西，他那被冬风吹得发干的双眼突然有些湿润：“是啊，人生苦短。”。

——思想者

今日编程练习

Leetcode260.只出现一次的数字Ⅲ

描述

给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。

思路

异或+lowbit，有两个数不一样，那么所有数异或的结果等于这两个数的异或结果

使用lowbit取出最低位1，说明在这一位，数a是1，数b是0

再把所有在该位是1的数异或起来，结果就是数a

同理得数b

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        x = 0
        for i in nums:
            x ^= i
        x &= -x
        a = 0
        b = 0
        for i in nums:
            if i & x == 0:
                a ^= i
            else:
                b ^= i
        return [a, b]

2021.10.28

今日天气：晴

真正的智者不会向你指明真相，而是教导你去发现真相。

——刺客信条

今日编程练习

Leetcode869.重新排序得到2的幂

描述

给定正整数 N ，我们按任何顺序（包括原始顺序）将数字重新排序，注意其前导数字不能为零。

如果我们可以通过上述方式得到 2 的幂，返回 true；否则，返回 false。

思路

记录2的幂中各数字出现的次数

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    base = [1, 10, 100, 1000, 10000, 100000, 1000000,10000000, 100000000, 1000000000, 10000000000]
    
    def encode(self, n: int) -> int:
        ret = 0
        while n > 0:
            cur = n % 10
            ret += self.base[cur]
            n //= 10
        return ret

    def reorderedPowerOf2(self, n: int) -> bool:
        if n == 0:
            return False
        d = defaultdict(int)
        t = 1
        for i in range(32):
            d[self.encode(t)] = 1
            t <<= 1
        return d[self.encode(n)] == 1

2021.10.27

今日天气：晴

不知所措，才是人生。

——海贼王

今日编程练习

Leetcode301.删除无效的括号

描述

给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。

返回所有可能的结果。答案可以按 任意顺序 返回。

思路

爆搜

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
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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
class Solution:
    def initation(self, s: str) -> List[str]:
        ret = []

        flag1 = -1
        for i in range(len(s)):
            if flag1 != -1:
                break
            if s[i] == '(':
                flag1 = i

        flag2 = 1
        for i in range(-1, -len(s) - 1, -1):
            if flag2 != 1:
                break
            if s[i] == ')':
                flag2 = i

        if flag1 == -1:
            for i in s:
                if i != ')':
                    ret.append(i)
        elif flag2 == 1:
            for i in s:
                if i != '(':
                    ret.append(i)
        else:
            flag2 += len(s)

            if flag1 > flag2:
                for i in s:
                    if i != '(' and i != ')':
                        ret.append(i)
            else:
                for i in range(flag1):
                    if s[i] != ')':
                        ret.append(s[i])
        
                ret += s[flag1 : flag2]

                for i in range(flag2, len(s)):
                    if s[i] != '(':
                        ret.append(s[i])

        return ret
    
    def calnum(self, s: List[str]) -> int:
        t = 0
        num = 0
        for i in s:
            if i == ')':
                t -= 1
                if t < 0:
                    num -= t
                    t = 0
            elif i == '(':
                t += 1

        if t < 0:
            num -= t
        else:
            num += t
        return num

    def decode(self, s: List[str]) -> str:
        ret = ""
        for i in s:
            ret += i
        return ret

    def dfs(self, ret: List[str], s: List[str], num: int, pos: int):
        if num < 0:
            return
        if pos + num > len(s):
            return
        if num == 0:
            if self.calnum(s) == 0:
                ret.append(self.decode(s))
        else:
            if s[pos] == '(':
                end = pos
                while end < len(s) and s[end] == '(':
                    end += 1
                self.dfs(ret, s, num, end)
                for i in range(end - pos):
                    del s[pos]
                    self.dfs(ret, s, num - i - 1, end - i - 1)
                for i in range(end - pos):
                    s.insert(pos, '(')      
            elif s[pos] == ')':
                end = pos
                while end < len(s) and s[end] == ')':
                    end += 1
                self.dfs(ret, s, num, end)
                for i in range(end - pos):
                    del s[pos]
                    self.dfs(ret, s, num - i - 1, end - i - 1)
                for i in range(end - pos):
                    s.insert(pos, ')')          
            else:
                self.dfs(ret, s, num, pos + 1)

    def removeInvalidParentheses(self, s: str) -> List[str]:
        ns = self.initation(s)
        print(self.decode(ns))
        num = self.calnum(ns)
        print(num)
        ret = []
        self.dfs(ret, ns, num, 0)
        return ret

2021.10.26

今日天气：晴

遇到迷茫时，任何人都会变得软弱。 一旦坚信自己可以帮到别人，他们就会变得很强大。

——海贼王

今日编程练习

Leetcode496.下一个更大元素 I

描述

给你两个 没有重复元素 的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。

请你找出 nums1 中每个元素在 nums2 中的下一个比其大的值。

nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出 -1 。

思路

维护单调栈+一个字典

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        d = defaultdict(int)
        s = [nums2[0]]
        for i in range(1, len(nums2)):
            while len(s) > 0 and nums2[i] > s[-1]:
                d[s[-1]] = nums2[i]
                del s[-1]
            s.append(nums2[i])
        
        for i in s:
            d[i] = -1

        ret = []
        for i in nums1:
            ret.append(d[i])
        
        return ret

2021.10.25

今日天气：晴

一个人的死，对于这个世界来说不过是多了一座坟墓，但对于相依为命的人来说、却是整个世界都被坟墓掩埋

——海贼王

今日编程练习

Leetcode240.搜索二维矩阵Ⅱ

描述

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

每行的元素从左到右升序排列。
每列的元素从上到下升序排列。

思路

z字型查找，先从矩阵的左上角或者右下角查找，以左下角为例：

若target比当前元素大，说明比当前元素小的全部忽略，则当前元素右移一格

反之，左移一格，总复杂度O(m + n)

我一直在找复杂度O(logm + logn)的双重二分，写了3小时还是不行

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        n = len(matrix)
        m = len(matrix[0])
        i = n - 1
        j = 0
        
        while i >= 0 and j < m:
            if matrix[i][j] < target:
                j += 1
            elif matrix[i][j] > target:
                i -= 1
            else:
                return True
        return False

2021.10.24

今日天气：晴

因为孤独比受伤还要痛苦

——海贼王

今日编程练习

Leetcode638.大礼包

描述

在 LeetCode 商店中， 有 n 件在售的物品。每件物品都有对应的价格。然而，也有一些大礼包，每个大礼包以优惠的价格捆绑销售一组物品。

给你一个整数数组 price 表示物品价格，其中 price[i] 是第 i 件物品的价格。另有一个整数数组 needs 表示购物清单，其中 needs[i] 是需要购买第 i 件物品的数量。

还有一个数组 special 表示大礼包，special[i] 的长度为 n + 1 ，其中 special[i][j] 表示第 i 个大礼包中内含第 j 件物品的数量，且 special[i][n] （也就是数组中的最后一个整数）为第 i 个大礼包的价格。

返回 确切 满足购物清单所需花费的最低价格，你可以充分利用大礼包的优惠活动。你不能购买超出购物清单指定数量的物品，即使那样会降低整体价格。任意大礼包可无限次购买。

思路

dp，不过实现得太笨重了点

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
class Solution {
public:
    int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {
        int n = 6 - needs.size();
        if(n){
            for(int i = 0; i < n; ++i){
                price.push_back(0);
                needs.push_back(0);
            }

            for(int i = 0; i < special.size(); ++i){
                int temp = special[i].size() - 1;
                for(int j = 0; j < n; ++j){
                    special[i].push_back(0);
                }
                swap(special[i][temp], special[i][6]);
            }
        }

        int d[11][11][11][11][11][11];
        memset(d, 0x7f, sizeof(d));
        d[0][0][0][0][0][0] = 0;
        for(int i0 = 0; i0 <= needs[0]; ++i0){
            for(int i1 = 0; i1 <= needs[1]; ++i1){
                for(int i2 = 0; i2 <= needs[2]; ++i2){
                    for(int i3 = 0; i3 <= needs[3]; ++i3){
                        for(int i4 = 0; i4 <= needs[4]; ++i4){
                            for(int i5 = 0; i5 <= needs[5]; ++i5){
                                int *cur = &d[i0][i1][i2][i3][i4][i5];
                                if(i0) *cur = min(*cur, d[i0 - 1][i1][i2][i3][i4][i5] + price[0]);
                                if(i1) *cur = min(*cur, d[i0][i1 - 1][i2][i3][i4][i5] + price[1]);
                                if(i2) *cur = min(*cur, d[i0][i1][i2 - 1][i3][i4][i5] + price[2]);   
                                if(i3) *cur = min(*cur, d[i0][i1][i2][i3 - 1][i4][i5] + price[3]);
                                if(i4) *cur = min(*cur, d[i0][i1][i2][i3][i4 - 1][i5] + price[4]);
                                if(i5) *cur = min(*cur, d[i0][i1][i2][i3][i4][i5 - 1] + price[5]);
                                for(int i = 0; i < special.size(); ++i){
                                    if(i0 < special[i][0]) continue;
                                    if(i1 < special[i][1]) continue;
                                    if(i2 < special[i][2]) continue;
                                    if(i3 < special[i][3]) continue;
                                    if(i4 < special[i][4]) continue;
                                    if(i5 < special[i][5]) continue;
                                    *cur = min(*cur, d[i0 - special[i][0]][i1 - special[i][1]][i2 - special[i][2]][i3 - special[i][3]][i4 - special[i][4]][i5 - special[i][5]] + special[i][6]);
                                }
                            }
                        }   
                    }
                }
            }
        }
        return d[needs[0]][needs[1]][needs[2]][needs[3]][needs[4]][needs[5]];
    }
};

2021.10.23

今日天气：晴

即使相处的时间不多，但真挚的友情是不在意时间长短的

——海贼王

今日编程练习

Leetcode492.构造矩形

描述

作为一位web开发者， 懂得怎样去规划一个页面的尺寸是很重要的。 现给定一个具体的矩形页面面积，你的任务是设计一个长度为 L 和宽度为 W 且满足以下要求的矩形的页面。要求：

  1. 你设计的矩形页面必须等于给定的目标面积。

  2. 宽度 W 不应大于长度 L，换言之，要求 L >= W 。

  3. 长度 L 和宽度 W 之间的差距应当尽可能小。

你需要按顺序输出你设计的页面的长度 L 和宽度 W。

思路

分解因数

Python

1
2
3
4
5
6
7
8
9
10
class Solution:
    def constructRectangle(self, area: int) -> List[int]:
        ret = [area]
        i = 2
        while i * i <= area:
            if area % i == 0:
                ret[0] = area // i 
            i += 1
        ret.append(area // ret[0])
        return ret

2021.10.21

今日天气：晴

人的梦想，是不会终结的！

——海贼王

今日编程练习

Leetcode66.加一

描述

给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。

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

思路

模拟即可，注意999之类的数

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        flag = True
        for i in range(-1, -len(digits) - 1, -1):
            if digits[i] == 9:
                digits[i] = 0
            else:
                digits[i] += 1
                flag = False
                break
        if flag:
            digits.insert(0, 1)
        return digits

2021.10.20

今日天气：晴

永无止境便是终结！

——JoJo的奇妙冒险·黄金之风

今日编程练习

Leetcode453.最小操作次数使数组元素相等

描述

给你一个长度为 n 的整数数组，每次操作将会使 n - 1 个元素增加 1 。返回让数组所有元素相等的最小操作次数。

思路

每次使n - 1个元素加1，相当于每次让一个元素减1，肯定让所有元素减1等于最小的那个

Python

1
2
3
4
5
6
7
8
9
class Solution:
    def minMoves(self, nums: List[int]) -> int:
        ret = 0
        mn = 1000000000
        for i in nums:
            ret += i
            if i < mn:
                mn = i
        return ret - mn * len(nums)

2021.10.18

今日天气：晴

我终将逝去，而你，即将加冕为王！

——魔兽争霸·巫妖王之怒

今日编程练习

Leetcode476.数字的补数

描述

对整数的二进制表示取反（0 变 1 ，1 变 0）后，再转换为十进制表示，可以得到这个整数的补数。

例如，整数 5 的二进制表示是 "101" ，取反后得到 "010" ，再转回十进制表示得到补数 2 。

给你一个整数 num ，输出它的补数。

思路

直接找到恰恰大于num的二进制整数，然后相减即可

Python

1
2
3
4
5
6
class Solution:
    def findComplement(self, num: int) -> int:
        base = 1
        while base <= num:
            base <<= 1
        return base - num - 1

2021.10.17

今日天气：晴

不要为别人给你的爱加上理由！

——海贼王

今日编程练习

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

描述

给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 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
# 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 find(self, root: Optional[TreeNode], k: int) -> (int, int):
        if root == None:
            return 0, -1
        else:
            num, ret = self.find(root.left, k)
            if ret == -1:
                if k - num == 1:
                    return -1, root.val
                else:
                    tnum, ret = self.find(root.right, k - num - 1)
                    return tnum + num + 1, ret
            else:
                return -1, ret

    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        num, ret = self.find(root, k)
        return ret

2021.10.16

今日天气：晴

人的欲望如同高山上的滚石，一旦开始，就再也停不下来了

——超兽武装

今日编程练习

Leetcode282.给表达式添加运算符

描述

给定一个仅包含数字 0-9 的字符串 num 和一个目标值整数 target ，在 num 的数字之间添加 二元 运算符（不是一元）+、- 或 * ，返回所有能够得到目标值的表达式。

思路

爆搜

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:
    target = 0
    num = ""
    ret = []

    def dfs(self, layer, sum, lastmul, lastnum, s):
        if layer == len(self.num):
            if sum == self.target:
                self.ret.append(s)
        else:
            cur = int(self.num[layer])
            self.dfs(layer + 1, sum + cur, cur, cur, s + "+" + str(cur))
            self.dfs(layer + 1, sum - cur, -cur, cur, s + "-" + str(cur))
            self.dfs(layer + 1, sum + lastmul * (cur - 1), lastmul * cur, cur, s + "*" + str(cur))
            if lastnum != 0:
                self.dfs(layer + 1, sum + lastmul // lastnum * (lastnum * 10 + cur) - lastmul, lastmul // lastnum * (lastnum * 10 + cur), lastnum * 10 + cur, s + str(cur))

    
    def addOperators(self, num: str, target: int) -> List[str]:
        self.ret = []
        self.target = target
        self.num = num
        self.dfs(1, int(num[0]), int(num[0]), int(num[0]), num[0])
        return self.ret

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
class Solution {
public:
    int tar;
    string n;
    vector<string> ret;

    void dfs(int layer, long long sum, long long lastmul, long long lastnum, string s){
        if(layer == n.length()){
            if(sum == tar){
                cout << s << " " << sum << endl;
                ret.push_back(s);
            }
        }else{
            long long cur = n[layer] - '0';
            dfs(layer + 1, sum + lastmul * (cur - 1), lastmul * cur, cur, s + '*' + n[layer]);
            if(lastnum){
                dfs(layer + 1, sum + lastmul / lastnum * (10 * lastnum + cur) - lastmul, lastmul / lastnum * (10 * lastnum + cur), 10 * lastnum + cur, s + n[layer]);
            }
            dfs(layer + 1, sum + cur, cur, cur, s + '+' + n[layer]);
            dfs(layer + 1, sum - cur, -cur, cur, s + '-' + n[layer]);
        }
    }

    vector<string> addOperators(string num, int target) {
        tar = target;
        n = num;
        dfs(1, num[0] - '0', num[0] - '0', num[0] - '0', num.substr(0, 1));
        return ret;
    }
};

2021.10.15

今日天气：晴

我自狂歌空度日，飞扬跋扈为谁雄

——赠李白

今日编程练习

Leetcode38.外观数列

描述

给定一个正整数 n ，输出外观数列的第 n 项。

「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。

你可以将其视作是由递归公式定义的数字字符串序列：

countAndSay(1) = "1"
countAndSay(n) 是对 countAndSay(n-1) 的描述，然后转换成另一个数字字符串。

前五项如下：

  1. 1
  2. 11
  3. 21
  4. 1211
  5. 111221

第一项是数字 1
描述前一项，这个数是 1 即 “ 一 个 1 ”，记作 “11”
描述前一项，这个数是 11 即 “ 二 个 1 ” ，记作 “21”
描述前一项，这个数是 21 即 “ 一 个 2 + 一 个 1 ” ，记作 “1211”
描述前一项，这个数是 1211 即 “ 一 个 1 + 一 个 2 + 二 个 1 ” ，记作 “111221”

要 描述 一个数字字符串，首先要将字符串分割为 最小 数量的组，每个组都由连续的最多 相同字符 组成。然后对于每个组，先描述字符的数量，然后描述字符，形成一个描述组。要将描述转换为数字字符串，先将每组中的字符数量用数字替换，再将所有描述组连接起来。

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
class Solution {
    public String countAndSay(int n) {
        String lst = "";
        String ret = "1";
        while(--n > 0){
            lst = ret;
            ret = "";

            int count = 1;
            for(int i = 0; i < lst.length() - 1; ++i){
                if(lst.charAt(i) == lst.charAt(i + 1)){
                    ++count;
                }else{
                    ret += Integer.toString(count);
                    ret += lst.charAt(i);
                    count = 1;
                }
            }

            ret += Integer.toString(count);
            ret += lst.charAt(lst.length() - 1);
        }
        return ret;
    }
}

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
class Solution {
public:
    string countAndSay(int n) {
        string lst = "";
        string ret = "1";
        while(--n > 0){
            lst = ret;
            ret = "";
            int count = 1;
            for(int i = 0; i < lst.length() - 1; ++i){
                if(lst[i] == lst[i + 1]){
                    ++count;
                }else{
                    ret += to_string(count);
                    ret += lst[i];
                    count = 1; 
                }
            }
            ret += to_string(count);
            ret += lst[lst.length() - 1];
            //cout << ret << endl;
        }
        return ret;
    }
};

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def countAndSay(self, n: int) -> str:
        last = ""
        ret = "1"
        while n > 1:
            n -= 1
            last = ret
            ret = ""
            count = 1
            for i in range(len(last) - 1):
                if last[i] == last[i + 1]:
                    count += 1
                else:
                    ret += str(count)
                    ret += last[i]
                    count = 1
            ret += str(count)
            ret += last[len(last) - 1]
        return ret

语法

值得注意的是，C++直接使用string类型的ret和int类型的count相加，这样处理得到的答案是错误的，必须使用全局函数to_string（注意这个是C++11标准的函数，在早先的版本中无法使用）。

猜测可能是把int型自动转换成了char型？

但在本地编译，直接使用string类型加int类型是不通过的。

2021.10.14

今日天气：晴

长铗归来乎！食无鱼

——战国策·冯谖客孟尝君

今日编程练习

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

描述

数组arr长度至少为3，满足两端向中间严格递增，找出中间最大值的下标

思路

三分法

需要注意的地方和二分法类似，即取不取边界的问题，这里下界可以不取，但上界一定要取

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def peakIndexInMountainArray(self, arr: List[int]) -> int:
        l = 0
        h = len(arr) - 1
        while h > l:
            lm = (2 * l + h) // 3
            hm = (l + 2 * h) // 3
            if arr[lm] == arr[hm]:
                l = lm
                h = hm
            elif arr[lm] < arr[hm]:
                l = lm + 1
            else:
                h = hm
        return l

2021.10.13

今日天气：晴

宁赴常流而葬乎江鱼腹中耳。又安能以皓皓之白，而蒙世之温蠖乎？

——史记·屈原列传

今日编程练习

Leetcode.412 Fizz Buzz

描述

给出数字n，从1到n的数里面，若能被3整除则对应Fizz，能被5整除则对应Buzz，同时被两者整除的对应FizzBuzz，否则对应原数字，返回字符串组成的数组

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<string> fizzBuzz(int n) {
        vector<string> r;
        for(int i = 1; i <= n; ++i){
            string ret = "";
            if(i % 3 == 0){
                ret += "Fizz";
            }
            if(i % 5 == 0){
                ret += "Buzz";
            }
            if(ret == ""){
                ret = to_string(i);
            }
            r.push_back(ret);
        }
        return r;
    }
};

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public List<String> fizzBuzz(int n) {
        List<String> ret = new LinkedList<>();
        for(int i = 1; i <= n; ++i){
            String r = "";
            if(i % 3 == 0){
                r += "Fizz";
            }
            if(i % 5 == 0){
                r += "Buzz";
            }
            if(r.equals("")){
                r = Integer.toString(i);
            }
            ret.add(r);
        }
        return ret;
    }
}

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def fizzBuzz(self, n: int) -> List[str]:
        r = []
        for i in range(1, n + 1):
            ret = ""
            if i % 3 == 0:
                ret += "Fizz"
            if i % 5 == 0:
                ret += "Buzz"
            if ret == "":
                ret = str(i)
            r.append(ret)
        return r

语法

1.Java的int转String

int是基本类型，不能看作对象，没有toString方法，一种方法是使用String类的静态方法valueOf，另一种方法是使用Integer类的静态方法toString，还可以新建一个值相等的Integer对象，再利用其toString方法

2021.10.12

今日天气：晴

沉吟此事泪满衣，黄金买醉未能归

——梁园吟

今日编程练习

Leetcode.29 两数相除

描述

给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。

返回被除数 dividend 除以除数 divisor 得到的商。

整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2

如果结果超过了32位有符号整形的范围，返回0x7fffffff

思路

模拟实现二进制除法，先判断符号

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
class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        sign = True
        if dividend < 0:
            sign = not sign
            dividend = -dividend
        if divisor < 0:
            sign = not sign
            divisor = -divisor
        temp = 0
        while dividend >= divisor:
            divisor <<= 1
            temp += 1
        divisor >>= 1
        ret = 0
        for i in range(temp):
            ret <<= 1
            if dividend >= divisor:
                dividend -= divisor
                ret += 1
            divisor >>= 1
        if not sign:
            ret = -ret
        if ret > 0x7fffffff or ret < -0x80000000:
            ret = 0x7fffffff
        return ret

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
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
    public int divide(int dividend, int divisor) {
        boolean flag = true;
        long tdividend = dividend;
        long tdivisor = divisor;
        if(tdividend < 0){
            flag = !flag;
            tdividend = -tdividend;
        }
        if(tdivisor < 0){
            flag = !flag;
            tdivisor = -tdivisor;
        }

        int temp = 0;
        while(tdividend >= tdivisor){
            tdivisor <<= 1;
            ++temp;
        }

        long ret = 0;
        tdivisor >>= 1;
        for(int i = 0; i < temp; ++i){
            ret <<= 1;
            if(tdividend >= tdivisor){
                tdividend -= tdivisor;
                ++ret;
            }
            tdivisor >>= 1;
        }

        if(!flag){
            ret = -ret;
        }

        if(ret > Integer.MAX_VALUE || ret < Integer.MIN_VALUE){
            ret = Integer.MAX_VALUE;
        }

        return (int)ret;
    }
}

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
class Solution {
public:
    int divide(int dividend, int divisor) {
        bool flag = true;
        long long tdividend = dividend;
        long long tdivisor = divisor;
        if(tdividend < 0){
            flag = !flag;
            tdividend = -tdividend;
        }
        if(tdivisor < 0){
            flag = !flag;
            tdivisor = -tdivisor;
        }

        int temp = 0;
        while(tdividend >= tdivisor){
            tdivisor <<= 1;
            ++temp;
        }

        long long ret = 0;
        tdivisor >>= 1;
        for(int i = 0; i < temp; ++i){
            ret <<= 1;
            if(tdividend >= tdivisor){
                tdividend -= tdivisor;
                ++ret;
            }
            tdivisor >>= 1;
        }

        if(!flag){
            ret = -ret;
        }

        //cout << -0x80000000;

        if(ret > 0x7fffffff || ret < -(long long)0x80000000){
            ret = 0x7fffffff;
        }

        return (int)ret;
    }
};

语法

1.有意思的0x80000000

假设long long ret = 1，我们看下面几个表达式：

1
2
3
4
5
ret < 0x80000000
ret < -0x80000000
ret < (long long)-0x80000000
ret < -(long long)0x80000000
ret < (int)0x80000000

它们的结果是：

1
2
3
4
5
true
true
true
false
false

这里就要说一下C语言的常数判断规则了：

一个常数，如果在有符号int型范围内，就判断它为有符号int型，如果超出，则扩展为unsigned int，如果还不够，就扩展为long long，再到unsigned long long，再超还是按unsigned long long但会对64位取模

1
2
3
4
5
6
7
8
9
10
11
#include <cstdio>
using namespace std;
int main(){
	int a = 1;
	printf("%d\n", a < 0x80000000);
	printf("%d\n", sizeof(0x80000000));
	printf("%d\n", sizeof(0x800000000));
	printf("%d\n", sizeof(0x8000000000000000));
	printf("%d\n", sizeof(0x8000000000000001));
	return 0;
}

结果：

1
2
3
4
5
1
4
8
8
8

这时，我们再引入运算规则，两个不同类型的数进行运算，范围较小的会自动向范围较大的扩展，其顺序是int->unsigned int->long long->unsigned long long。

需要注意的是，int和unsigned int本质上是一种类型，长度和内部的存储都一样，只不过可以看成是一种数的两种解读方式

下面我们逐个分析：

1.ret < 0x80000000

0x80000000是unsigned int型，和ret比较自动转为long long值不变，比1大

2.ret < -0x80000000

这里为什么还是true呢？因为0x80000000是unsigned int型，取负运算是把它转为int型下做的，做完之后不变，还是0x80000000

3.ret < (long long)-0x80000000

同上，取负是在int型下做的，值不变

4.ret < -(long long)0x80000000

这里的是先转为long long，再取负数，当然就变成负数了

5.ret < (int)0x80000000

强制将值按int型解释，解释出的值是负数

2021.10.11

今日天气:晴

古来圣贤皆寂寞，唯有饮者留其名。

——将进酒

今日编程练习

Leetcode273.整数转换英文表示

描述

将非负整数 num 转换为其对应的英文表示，范围是正数int范围

思路

正数int范围的话，最多10位整数，英文的习惯是每3位为一组，后分别加Thousand，Million，Billion，所以可以把num分开讨论

注意空格的问题和0的表示

由于本题麻烦，所以不写C++和Java代码了

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
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
86
class Solution:
    words = [   "Zero",
                "One", 
                "Two", 
                "Three", 
                "Four", 
                "Five", 
                "Six", 
                "Seven", 
                "Eight", 
                "Nine", 
                "Ten", 
                "Eleven", 
                "Twelve", 
                "Thirteen",
                "Fourteen",
                "Fifteen", 
                "Sixteen", 
                "Seventeen", 
                "Eighteen", 
                "Nineteen", 
                "Twenty", 
                "Thirty", 
                "Forty", 
                "Fifty", 
                "Sixty", 
                "Seventy", 
                "Eighty", 
                "Ninety",
            ]
    def numberToWords(self, num: int) -> str:
        ret = ""
        flag = True
        if num >= 1000000000:
            ret += self.numberToWords(num // 1000000000)
            num %= 1000000000
            ret += " Billion"
            flag = False
        if num >= 1000000:
            if flag:
                flag = False
            else:
                ret += " "
            ret += self.numberToWords(num // 1000000)
            num %= 1000000
            ret += " Million"
        if num >= 1000:
            if flag:
                flag = False
            else:
                ret += " "
            ret += self.numberToWords(num // 1000)
            num %= 1000
            ret += " Thousand"
        if num >= 100:
            if flag:
                flag = False
            else:
                ret += " "
            ret += self.words[num // 100]
            ret += " Hundred"
            num %= 100
        if num >= 20:
            if flag:
                flag = False
            else:
                ret += " "
            ret += self.words[num // 10 + 18]
            num %= 10
            if num > 0:
                if flag:
                    flag = False
                else:
                    ret += " "
                ret += self.words[num]
        elif num > 0:
            if flag:
                flag = False
            else:
                ret += " "
            ret += self.words[num]
        else:
            if flag:
                ret += self.words[num]
                flag = False
        return ret

这里不用递归，直接把每组的转换摘出来就能提升一些效率

2021.10.10

今日天气：雾

不要为明天忧虑，因为明天自有明天的忧虑，一天的难处一天当就好了

——新约·马太福音

今日编程练习

Leetcode.441 排列硬币

描述

你总共有 n 枚硬币，并计划将它们按阶梯状排列。对于一个由 k 行组成的阶梯，其第 i 行必须正好有 i 枚硬币。阶梯的最后一行 可能 是不完整的。

给你一个数字 n ，计算并返回可形成 完整阶梯行 的总行数。

思路

很简单的数学题，找出最大的满足(k+1)×k >= n的n即可。

Python

1
2
3
4
class Solution:
    def arrangeCoins(self, n: int) -> int:
        k = int((2 * n + 0.25) ** 0.5 - 0.5)
        return k

Java

1
2
3
4
5
class Solution {
    public int arrangeCoins(int n) {
        return (int)(Math.sqrt((double)n * 2.0 + 0.25) - 0.5);
    }
}

C++

1
2
3
4
5
6
class Solution {
public:
    int arrangeCoins(int n) {
        return (int)(sqrt(2 * (double)n + 0.25) - 0.5);
    }
};

语法

1.开方：

1
2
3
C++:	sqrt(x);
Java:	Math.sqrt(x);
Python:	x ** 0.5

2.取整

1
2
3
C++:	(int)x;
Java:	(int)x;
Python:	int(x)

2021.10.8

今日天气：雨

凡有的，还要加给他，叫他有余；凡没有的，连他所有的也要夺去。

——新约·马太福音

今日编程练习

Leetcode187.重复的DNA序列

描述

所有 DNA 都由一系列缩写为 ‘A’，’C’，’G’ 和 ‘T’ 的核苷酸组成，例如：”ACGAATTCCG”。在研究 DNA 时，识别 DNA 中的重复序列有时会对研究非常有帮助。

编写一个函数来找出所有目标子串，目标子串的长度为 10，且在 DNA 字符串 s 中出现次数超过一次。

思路

使用哈希表存储子串出现次数，做到不重不漏

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<string> findRepeatedDnaSequences(string s) {
        vector<string> ret;
        map<string, int> mp;
        if(s.length() > 10){
            for(int i = 0; i < s.length() - 9; ++i){
                string t = s.substr(i, 10);
                if(mp[t] == 1){
                    ret.push_back(t);
                }
                ++mp[t];
            }
        }
        return ret;
    }
};

Python

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def findRepeatedDnaSequences(self, s: str) -> List[str]:
        ret = []
        if len(s) > 10:
            d = collections.defaultdict(int)
            for i in range(0, len(s) - 9):
                cur = s[i : i + 10]
                if d[cur] == 1:
                    ret.append(cur)
                d[cur] += 1
        return ret

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public List<String> findRepeatedDnaSequences(String s) {
        List<String> ret = new LinkedList<>();
        if(s.length() > 10){
            Map<String, Integer> mp = new HashMap<>();
            for(int i = 0; i < s.length() - 9; ++i){
                String cur = s.substring(i, i + 10);
                if(mp.get(cur) != null){
                    if(mp.get(cur) == 1){
                        ret.add(cur);
                        mp.put(cur, 2);
                    }    
                }else{
                    mp.put(cur, 1);
                }
            }
        }
        return ret;
    }
}

语法复习

1.关于子串

1
2
3
4
5
C++：string.substr(int 起始下标, int 子串长度)

Java：String.substring(int 起始下标, int 结束下标)//不包括结束下标

Python：字符串名\[起始下标 : 结束下标\]//直接数组操作，不包括结束下标

2.关于map

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
C++：
声明：map<string, int> mp;
赋值：下标
读取：下标
查找：下标，不存在的为0

Java：
声明：Map<String, Integer> mp = new HashMap<>();
赋值：put(key, value);
读取：get(key);//不存在为null
查找：containsKey(key);

Python；(字典)
声明：d = collections.defaultdict(int)
赋值：下标
读取：下标
查找：下标，不存在的为0

3.关于vector，List，Arrays

1
2
3
4
5
6
7
8
9
10
11
C++：Vector
声明：Vector<int> ret;
添加：push_back(value);

Java：List
声明：List<String> ret = new LinkedList<>();//还可以使用ArrayList
添加：add(value);

Python：Arrays
声明：ret = []
添加：append(value)

2021.10.7

今日天气：阴/下午转雨

现在他只看到星星和墓碑，但这却是两样最能象征永恒的东西。

——三体·黑暗森林

今日编程练习

Leetcode434.字符串中的单词数

描述

统计字符串中的单词个数，这里的单词指的是连续的不是空格的字符。

请注意，你可以假定字符串里不包括任何不可打印的字符。

思路

遍历数组，设置标记表示前面是否为空格，若前面是空格后面不是，改变标记并计数；前面不是空格后面是，改变标记不计数

Python代码

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def countSegments(self, s: str) -> int:
        ret = 0
        flag = False
        for i in s:
            if i == ' ' and flag:
                flag = False
            elif i != ' ' and not flag:
                flag = True
                ret += 1
        return ret

Java代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int countSegments(String s) {
        int ret = 0;
        boolean flag = false;
        for(int i = 0; i < s.length(); ++i){
            if(flag && s.charAt(i) == ' '){
                flag = false;
            }else if(!flag && s.charAt(i) != ' '){
                flag = true;
                ++ret;
            }
        }
        return ret;
    }
}

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int countSegments(string s) {
        int flag = 0;
        int ret = 0;
        for(int i = 0; i < s.length(); ++i){
            if(flag && s[i] == ' '){
                flag = 0;
            }else if(!flag && s[i] != ' '){
                flag = 1;
                ++ret;
            }
        }
        return ret;
    }
};

2021.10.6

今日天气：阴/风

人的天性生来不适宜欢乐，只会紧紧地抱住痛苦

——基督山伯爵

今日练习

Leetcode414.第三大的数

描述

给你一个非空数组，返回此数组中 第三大的数 。如果不存在，则返回数组中最大的数。

解题思路

如果题目只要一个最大值的话，我们会用类似于“打擂台”的方法，一个最大值变量来记录当前最大值，然后再一个个地比较下去

但题目要第三大值，我们仍然可以使用“打擂台”的方法，只不过这次需要记录最大，次大，第三大这三个值，每次拿新数去和它们比较

只需要遍历一次时间复杂度是O(N)，空间复杂度是O(1)

还有一种类似于快速排序的方法也可以在O(n)时间复杂度下求出第k大数，详见https://jameci.github.io/2021/03/22/%E7%AC%ACk%E5%A4%A7%E6%95%B0/

代码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
class Solution:
    def thirdMax(self, nums: List[int]) -> int:
        m = [nums[0]]
        for i in range(1, len(nums)):
            cur = nums[i]
            if len(m) == 1:
                if cur > m[0]:
                    m.append(m[0])
                    m[0] = cur
                elif cur < m[0]:
                    m.append(cur)
            elif len(m) == 2:
                if cur > m[0]:
                    m.append(m[1])
                    m[1] = m[0]
                    m[0] = cur
                elif cur < m[0]:
                    if cur > m[1]:
                        m.append(m[1])
                        m[1] = cur
                    elif cur < m[1]:
                        m.append(cur)
            else:
                if cur > m[0]:
                    m[2] = m[1]
                    m[1] = m[0]
                    m[0] = cur
                elif cur < m[0]:
                    if cur > m[1]:
                        m[2] = m[1]
                        m[1] = cur
                    elif cur < m[1]:
                        if cur > m[2]:
                            m[2] = cur

        if len(m) == 3:
            return m[2]
        else:
            return m[0]

代码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
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
class Solution {
    public int thirdMax(int[] nums) {
        int count = 1;
        int[] temp = new int[3];
        temp[0] = nums[0];
        for(int i = 1; i < nums.length; ++i){
            if(count == 1){
                if(nums[i] > temp[0]){
                    temp[1] = temp[0];
                    temp[0] = nums[i];
                    ++count;
                }else if(nums[i] < temp[0]){
                    temp[1] = nums[i];
                    ++count;
                }
            }else if(count == 2){
                if(nums[i] > temp[0]){
                    temp[2] = temp[1];
                    temp[1] = temp[0];
                    temp[0] = nums[i];
                    ++count;
                }else if(nums[i] < temp[0]){
                    if(nums[i] > temp[1]){
                        temp[2] = temp[1];
                        temp[1] = nums[i];
                        ++count;
                    }else if(nums[i] < temp[1]){
                        temp[2] = nums[i];
                        ++count;
                    }
                }
            }else{
                if(nums[i] > temp[0]){
                    temp[2] = temp[1];
                    temp[1] = temp[0];
                    temp[0] = nums[i];
                }else if(nums[i] < temp[0]){
                    if(nums[i] > temp[1]){
                        temp[2] = temp[1];
                        temp[1] = nums[i];
                    }else if(nums[i] < temp[1]){
                        if(nums[i] > temp[2]){
                            temp[2] = nums[i];
                        }
                    }
                }
            }
        }
        if(count == 3){
            return temp[2];
        }else{
            return temp[0];
        }
    }
}

2021.10.4

今日天气：晴

有什么能阻挡一个男人扬帆起航？

——海贼王

今日练习

Leetcode482.密钥格式化

题目描述

有一个密钥字符串 S ，只包含字母，数字以及 ‘-‘（破折号）。其中， N 个 ‘-‘ 将字符串分成了 N+1 组。

给你一个数字 K，请你重新格式化字符串，使每个分组恰好包含 K 个字符。特别地，第一个分组包含的字符个数必须小于等于 K，但至少要包含 1 个字符。两个分组之间需要用 ‘-‘（破折号）隔开，并且将所有的小写字母转换为大写字母。

给定非空字符串 S 和数字 K，按照上面描述的规则进行格式化。

思路

暴力模拟即可

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
class Solution:
    def licenseKeyFormatting(self, s: str, k: int) -> str:
        l = len(s)
        for i in range(len(s)):
            if s[i] == '-':
                l -= 1
        lst = l % k
        if lst == 0:
            lst = k
        
        ret = ''
        num = lst
        for i in range(len(s)):
            if s[i] == '-':
                continue
            elif s[i].islower():
                ret += s[i].upper()
            else:
                ret += s[i]
            num -= 1
            l -= 1
            if num == 0 and l != 0:
                num = k
                ret += '-'

        return ret

Java解法

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public String licenseKeyFormatting(String s, int k) {
        s = s.replaceAll("-", "");
        int startpos = s.length() % k == 0 ? Math.min(k, s.length()) : s.length() % k;
        StringBuilder ret = new StringBuilder(s.substring(0, startpos));
        for(int i = startpos; i < s.length(); i += k){
            ret.append("-");
            ret.append(s.substring(i, i + k));
        }
        return ret.toString().toUpperCase();
    }
}

2021.10.3

今日天气：晴

历经苦难而不厌，此乃修罗之道！

——海贼王

今日python练习

Leetcode166.分数到小数

题目描述

给定两个整数，分别表示分数的分子 numerator 和分母 denominator，以 字符串形式返回小数 。

如果小数部分为循环小数，则将循环的部分括在括号内。

如果存在多个答案，只需返回 任意一个 。

对于所有给定的输入，保证 答案字符串的长度小于 10^4 。

思路

循环小数分为两种，纯循环和混循环，纯循环如1/3=0.33333……，这里小数部分只要循环节3，而混循环如1/6=0.166666……，这里6是循环节，而小数部分不仅仅是由循环节6组成，还有一个1

我们再引入形如9，99，999，9999，99999这样只有9组成的数，这样的数做分母的真分数化为小数有一个特殊性质——它们都是纯循环小数，循环节长度等于9的个数，并且循环节就是带前导零的分子本身

如1/9=0.11111……，1/99=0.0101……，56/999=0.056056……

因此，所有的纯循环小数都可以化为这种特定形式的分数，以1/7=0.142857……为例，循环节为142857，所以有：

1/7 = 142857/999999 = 0.142857……

那么，假设我们要计算1/7，那么其实我们只需要找到一个全是9组成的数x，令x能被7整除，自然就可以把1/7化为上面这种形式的分数，然后直接得到循环节

那么混循环怎么办，我们再引出一个结论，所有混循环小数的分母上一定带有因子2或因子5，如1/6=0.1666……，1/15=0.06666……，这是为什么呢？因为2和5是10的因数，所以十进制下的任何整数都可以被其因数仅仅含有2，5的除尽。比如任何整数除以10，20，50，25，8，125，都肯定是能除得尽的。

这造成了混循环，为什么这么说呢，例如1/14，实际上相当于1先除以2，再除以7，也就变成了0.5除以7，这时循环节和5除以7的循环节是一模一样的，只不过因为先除以2的存在，小数点后移了一位，造成小数部分的第一位不是循环节的一部分，产生了混循环

经过上面的分析，如何处理混循环的思路也很明确了，先做一个预处理：即先把分母中的因子2，5去掉，如果分子也含2，5，先约分，如果不含，分子分母同时除以2或5，但这样做会在预处理时把分子变成小数，为了避免这样，我们可以换种方式，用一个变量记录混循环的位数，我们知道，每当分子分母同时除以10，相当于小数点后移一位，混循环位数加1，我们利用混循环位数加1的操作代替分子除以10，来避免预处理时把分子变成小数，具体做法是先约分2和5，之后，如果分母中有多余的一对2和5，则分母除以10，记录混循环位数加一，不再对分子进行处理，同理，如果分母只有多余的2，我们就除掉它，并给分子乘5，再记录小数点后混循环位数加1，若只有多余的5，我们就除掉它，并给分子乘2，混循环位数加1

剔除2和5之后，再按照处理纯循环的方式处理

最后，还需要针对结果为负数以及结果是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
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
class Solution:
    def fractionToDecimal(self, numerator: int, denominator: int) -> str:
        ret = ''
        if numerator == 0:
            return '0'
        elif numerator < 0 and denominator < 0:
            denominator = -denominator
            numerator = -numerator
        elif numerator < 0:
            ret += '-'
            numerator = -numerator
        elif denominator < 0:
            ret += '-'
            denominator = -denominator
        ret += str(numerator // denominator)
        numerator %= denominator
        if numerator != 0:
            ret += "."
            temp_denominator = 0
            while denominator % 2 == 0:
                denominator //= 2
                if numerator % 2 == 0:
                    numerator //= 2
                else:
                    if denominator % 5 == 0:
                        denominator //= 5
                    else:
                        numerator *= 5
                    temp_denominator += 1
            while denominator % 5 == 0:
                if numerator % 5 == 0:
                    numerator //= 5
                else:
                    denominator //= 5
                    temp_denominator += 1
                    numerator *= 2
            temp_denominator2 = 1
            if denominator == 1:
                temp_denominator2 = 0
            else:
                while ((10 ** temp_denominator2) - 1) % denominator != 0:
                    temp_denominator2 += 1
            print(temp_denominator)
            print(temp_denominator2)
            print(numerator)
            if temp_denominator2 == 0:
                ret += ('0' * (temp_denominator - len(str(numerator))))
                ret += str(numerator)
            else:
                numerator *= (((10 ** temp_denominator2) - 1) // denominator)
                if temp_denominator != 0:
                    part1 = numerator // ((10 ** temp_denominator2) - 1) 
                    ret += ('0' * (temp_denominator - len(str(part1))))
                    ret += str(part1)
                ret += '('
                part2 = numerator % ((10 ** temp_denominator2) - 1)
                ret += ('0' * (temp_denominator2 - len(str(part2))))
                ret += str(part2)
                ret += ')'
        return ret

2021.10.2

今日天气：晴

灾难总是接踵而至，这正是世间的常理，你以为只要解释一下，就有谁会来救你吗？要是死了，就只能说明我不过是如此程度的男人

——海贼王

今日python练习

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

题目描述

给定一个整数，编写一个算法将这个数转换为十六进制数。对于负整数，我们通常使用 补码运算 方法。

注意:

十六进制中所有字母(a-f)都必须是小写。
十六进制字符串中不能包含多余的前导零。如果要转化的数为0，那么以单个字符'0'来表示；对于其他情况，十六进制字符串中的第一个字符将不会是0字符。 
给定的数确保在32位有符号整数范围内。
不能使用任何由库提供的将数字直接转换或格式化为十六进制的方法。

思路

直接转换比较容易，但补码较为麻烦，可以使用加上0x100000000的方法，让负数也变成正数，之后再按位转换

解决

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 toHex(self, num: int) -> str:
        if num < 0:
            num += 0x100000000
        elif num == 0:
            return '0'
        ret = ''
        while num > 0:
            if num % 16 < 10:
                ret = str(num % 16) + ret
            elif num % 16 == 10:
                ret = 'a' + ret
            elif num % 16 == 11:
                ret = 'b' + ret
            elif num % 16 == 12:
                ret = 'c' + ret
            elif num % 16 == 13:
                ret = 'd' + ret
            elif num % 16 == 14:
                ret = 'e' + ret
            else:
                ret = 'f' + ret
            num //= 16
        return ret

2021.10.1

今日天气：晴

一个人诞生在这个世界上，绝对不会是永远孤单的

——海贼王

今日python练习

Leetcode1436.旅行终点站

题目描述

给你一份旅游线路图，该线路图中的旅行线路用数组 paths 表示，其中 paths[i] = [cityAi, cityBi] 表示该线路将会从 cityAi 直接前往 cityBi 。请你找出这次旅行的终点站，即没有任何可以通往其他城市的线路的城市。

题目数据保证线路图会形成一条不存在循环的线路，因此恰有一个旅行终点站。

思路

统计出度，肯定只有旅行终点站的出度是0

解决

1
2
3
4
5
6
7
8
9
class Solution:
    def destCity(self, paths: List[List[str]]) -> str:
        d = collections.defaultdict(int)
        for a, b in paths:
            d[a] += 1
        
        for a, b in paths:
            if d[b] == 0:
                return b

语法复习

创建字典d = collections.defaultdict(int)

2021.9.30

今日天气：晴

你将拔掉龙的牙齿，将狮子踩在脚下！

——基督山伯爵

今日python练习

Leetcode223.矩形面积

题目描述

给你 二维 平面上两个 由直线构成的 矩形，请你计算并返回两个矩形覆盖的总面积。

每个矩形由其 左下 顶点和 右上 顶点坐标表示：

第一个矩形由其左下顶点 (ax1, ay1) 和右上顶点 (ax2, ay2) 定义。
第二个矩形由其左下顶点 (bx1, by1) 和右上顶点 (bx2, by2) 定义。

思路

已知四个端点，判断两个线段不相交的方法是，若某个线段的左端点在另一线段的右端点右方，或者其右端点在另一线段的左端点左方，则不相交，否则相交

可以把矩形投影到x轴上，如果两个矩形构成的线段不相交，那么矩形一定不相交

同理可以投影到y轴上，如果两个投影中有任意一个不相交，那么矩形一定不相交，否则一定相交

同样的办法可以用在三维，四维甚至更高维的图形上

若线段相交，那么相交线段的左端点肯定是两线段左端点中坐标最小的，右端点肯定是两线段右端点中坐标最大的

这个结论也能推广到多个线段相交

同样，我们把矩形的投影到各个坐标轴上，得出相交线段，两条相交线段就分别是矩形的长和宽

这个结论也能用于高维图形上

所以本题虽简单，但很有启发意义，那些一味画图判断几种情况嵌套if的人这题相当于白做了，假设又遇到高维的，他们的嵌套if就会变得复杂，直到情况过多难以写出来的程度

解决

1
2
3
4
5
6
7
class Solution:
    def computeArea(self, ax1: int, ay1: int, ax2: int, ay2: int, bx1: int, by1: int, bx2: int, by2: int) -> int:
        ret = (ay2 - ay1) * (ax2 - ax1) + (by2 - by1) * (bx2 - bx1)
        if bx1 > ax2 or ax1 > bx2 or by1 > ay2 or ay1 > by2:
            return ret
        else:
            return ret - (min(ax2, bx2) - max(ax1, bx1)) * (min(ay2, by2) - max(ay1, by1))

2021.9.27

今日天气：小雨/阴

如果你停止抱怨，不再追求你永远都得不到的东西，你就可以过上好日子

——丧钟为谁而鸣

今日python练习

Leetcode639.解码方法 II

题目描述

一条包含字母 A-Z 的消息通过以下的方式进行了编码：

‘A’ -> 1
‘B’ -> 2
…
‘Z’ -> 26

要 解码 一条已编码的消息，所有的数字都必须分组，然后按原来的编码方案反向映射回字母（可能存在多种方式）。例如，”11106” 可以映射为：

"AAJF" 对应分组 (1 1 10 6)
"KJF" 对应分组 (11 10 6)

注意，像 (1 11 06) 这样的分组是无效的，因为 “06” 不可以映射为 ‘F’ ，因为 “6” 与 “06” 不同。

除了 上面描述的数字字母映射方案，编码消息中可能包含 ‘‘ 字符，可以表示从 ‘1’ 到 ‘9’ 的任一数字（不包括 ‘0’）。例如，编码字符串 “1“ 可以表示 “11”、”12”、”13”、”14”、”15”、”16”、”17”、”18” 或 “19” 中的任意一条消息。对 “1*” 进行解码，相当于解码该字符串可以表示的任何编码消息。

给你一个字符串 s ，由数字和 ‘*’ 字符组成，返回 解码 该字符串的方法 数目 。

由于答案数目可能非常大，返回对 109 + 7 取余 的结果。

思路

dp，在一个字符串s后面添加一个字符，有两种解码方法

1该字符单独作为一个字母解码，这样总解码方法在s的解码方法数基础上乘以该字符的解码方法数

2该字符和s的最后一个字符合并起来解码，这样总解码数需要在s去掉最后一个字符后的解码数上乘最后一个字符与该字符合并起来后的解码方法数

解决

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
class Solution:
    def numDecodings(self, s: str) -> int:
        r = [1]
        if s[0] == '*':
            r.append(9)
        elif s[0] == '0':
            r.append(0)
        else:
            r.append(1)
        
        for i in range(1, len(s)):
            if s[i - 1] == '*':
                if s[i] == '*':
                    r.append(r[i - 1] * 15 + r[i] * 9)
                elif s[i] == '0':
                    r.append(r[i - 1] * 2)
                elif s[i] in ('7', '8', '9'):
                    r.append(r[i - 1] + r[i])
                else:
                    r.append(r[i - 1] * 2 + r[i])
            elif s[i - 1] == '1':
                if s[i] == '*':
                    r.append(r[i - 1] * 9 + r[i] * 9)
                elif s[i] == '0':
                    r.append(r[i - 1])
                else:
                    r.append(r[i - 1] + r[i])
            elif s[i - 1] == '2':
                if s[i] == '*':
                    r.append(r[i - 1] * 6 + r[i] * 9)
                elif s[i] == '0':
                    r.append(r[i - 1])
                elif s[i] in ('7', '8', '9'):
                    r.append(r[i])
                else:
                    r.append(r[i - 1] + r[i])
            else:
                if s[i] == '*':
                    r.append(r[i] * 9)
                elif s[i] == '0':
                    r.append(0)
                else:
                    r.append(r[i])
            r[i + 1] %= 1000000007

        return r[len(s)]

改进

经过我们思考分析，发现实际上r数组只用到了当前位置前两个，所以我们使用三个变量让他们原地计算

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 Solution:
    def numDecodings(self, s: str) -> int:
        tr = 1
        r = 9
        if s[0] == '*':
            pass
        elif s[0] == '0':
            r = 0
        else:
            r = 1
        
        for i in range(1, len(s)):
            nr = 0
            if s[i - 1] == '*':
                if s[i] == '*':
                    nr = tr * 15 + r * 9
                elif s[i] == '0':
                    nr = tr * 2
                elif s[i] in ('7', '8', '9'):
                    nr = tr + r
                else:
                    nr = tr * 2 + r
            elif s[i - 1] == '1':
                if s[i] == '*':
                    nr = tr * 9 + r * 9
                elif s[i] == '0':
                    nr = tr
                else:
                    nr = tr + r
            elif s[i - 1] == '2':
                if s[i] == '*':
                    nr = tr * 6 + r * 9
                elif s[i] == '0':
                    nr = tr
                elif s[i] in ('7', '8', '9'):
                    nr = r
                else:
                    nr = tr + r
            else:
                if s[i] == '*':
                    nr = r * 9
                elif s[i] == '0':
                    nr = 0
                else:
                    nr = r
            tr = r
            r = nr % 1000000007

        return r

语法复习

if a in (a, b, v, s):

这样的语句可以判断a是否在某个集合里

2021.9.24

今日天气：多云

基本粒子虽小，却构成了我们，宇宙虽大，我们却身处其中

——坍缩

今日python练习

Leetcode430.扁平化多级双向链表

题目描述

多级双向链表中，除了指向下一个节点和前一个节点指针之外，它还有一个子链表指针，可能指向单独的双向链表。这些子列表也可能会有一个或多个自己的子项，依此类推，生成多级数据结构，如下面的示例所示。

给你位于列表第一级的头节点，请你扁平化列表，使所有结点出现在单级双链表中。

思路

递归，遇到有子节点的，先扁平化子节点，然后把子节点连接在当前节点后，继续向后遍历

解决

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 a Node.
class Node:
    def __init__(self, val, prev, next, child):
        self.val = val
        self.prev = prev
        self.next = next
        self.child = child
"""

class Solution:
    def flatten(self, head: 'Node') -> 'Node':
        p = head
        while p != None:
            if p.child == None:
                p = p.next
            else:
                q = self.flatten(p.child)
                p.child = None
                np = p.next
                p.next = q
                q.prev = p
                while q.next != None:
                    q = q.next
                q.next = np
                if np != None:
                    np.prev = q
                p = np
        return head

2021.9.23

今日天气：晴

宇宙本身就是疯狂而混乱的

——Rick and Morty

今日python练习

Leetcode326.3的幂

题目描述

判断一个整数是否是3的幂

思路

直接暴力循环除以3，注意负数和0

解决

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        flag = True
        if n <= 0:
            return False
        while True:
            if n == 1:
                break
            elif n % 3 != 0:
                flag = False
                break
            else:
                n /= 3
        return flag

2021.9.22

今日天气：多云

过去就像攥在手中的干沙，自以为攥得很紧，实际早已从指缝流光了，记忆是一条干涸的河流，只在毫无生气的河床中剩下零落的砾石

——三体·地球往事

今日python练习

Leetcode725.分割链表

题目描述

一个头结点为 head 的单链表和一个整数 k ，请你设计一个算法将链表分隔为 k 个连续的部分。

每部分的长度应该尽可能的相等：任意两部分的长度差距不能超过 1 。这可能会导致有些部分为 null 。

这 k 个部分应该按照在链表中出现的顺序排列，并且排在前面的部分的长度应该大于或等于排在后面的长度。

返回一个由上述 k 部分组成的数组。

思路

很简单，也是暴力题

解决

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
# 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]:
        l = 0
        p = head
        while p != None:
            p = p.next
            l += 1
        base = l // k
        time = l - k * base
        p = head
        ret = []
        for i in range(time):
            lkd = ListNode(val = p.val)
            hlkd = lkd
            p = p.next
            for j in range(base):
                nlkd = ListNode(val = p.val)
                p = p.next
                lkd.next = nlkd
                lkd = nlkd
            ret.append(hlkd)
        for i in range(time, k):
            if base == 0:
                ret.append(None)
            else:
                lkd = ListNode(val = p.val)
                hlkd = lkd
                p = p.next
                for j in range(base - 1):
                    nlkd = ListNode(val = p.val)
                    p = p.next
                    lkd.next = nlkd
                    lkd = nlkd
                ret.append(hlkd)
        return ret

语法复习

None表示空对象

2021.9.21

今日天气：多云/风

活着本身就是一种幸运

——三体·死神永生

今日python练习

Leetcode58.最后一个单词的长度

题目描述

一个字符串 s，由若干单词组成，单词前后用一些空格字符隔开。返回字符串中最后一个单词的长度。

单词 是指仅由字母组成、不包含任何空格字符的最大子字符串。

思路

暴力即可

解决

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def lengthOfLastWord(self, s: str) -> int:
        flag = False
        ret = 0
        for i in range(len(s) - 1, -1, -1):
            if s[i] != ' ':
                if flag:
                    ret += 1
                else:
                    flag = True
                    ret += 1
            else:
                if flag:
                    break
        return ret

2021.9.20

今日天气：大雨转阴

寒风造就了维京勇士

——JOJO的奇妙冒险·幻影之血

今日python练习

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

题目描述

给定一个未排序的整数数组，找到最长递增子序列的个数。

思路

最长递增子序列使用dp，dp的同时更新个数，统计出长度后再统计个数之和

这题有更简单的做法，但我没想

解决

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 findNumberOfLIS(self, nums: List[int]) -> int:
        dplen = [[], [nums[0]]]
        dptime = [[], [1]]
        for i in range(1, len(nums)):
            l = nums[i]
            t = 1
            for j in range(len(dplen) - 1, -1, -1):
                if dplen[j][-1] < nums[i]:
                    
            dplen.append(l)
            dptime.append(t)

        maxl = 0
        maxt = 0
        for i in range(len(nums)):
            if dplen[i] > maxl:
                maxl = dplen[i]
                maxt = dptime[i]
            elif dplen[i] == maxl:
                maxt += dptime[i]
        
        return maxt

2021.9.19

今日天气：晴

所谓的觉悟，并非牺牲的意念

而是在黑暗的荒野中，开辟出一条理应前进的光明大道！

——JOJO的奇妙冒险·黄金之风

今日python练习

Leetcode650.只有两个键的键盘

题目描述

最初记事本上只有一个字符 ‘A’ 。你每次可以对这个记事本进行两种操作：

Copy All（复制全部）：复制这个记事本中的所有字符（不允许仅复制部分字符）。
Paste（粘贴）：粘贴 上一次 复制的字符。

给你一个数字 n ，你需要使用最少的操作次数，在记事本上输出 恰好 n 个 ‘A’ 。返回能够打印出 n 个 ‘A’ 的最少操作次数。

思路

分解质因数

如果最终的目标数有因子，那么我们一定可以凑出这个因子，然后复制若干次

假设最终要得到30个A，30有一对因子5和6，为此我们凑出6，再复制5次得到30个

6有因子2和3，为此我们凑出2，再复制3次得到6个，

那么我们可以先得到复制2次得到2个A

因此答案就是数n所有质因数的和

解决

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def minSteps(self, n: int) -> int:
        i = 2
        ret = 0
        while i <= n:
            if n % i == 0:
                n /= i
                ret += i
            else:
                i += 1
        return ret

2021.9.18

今日天气：晴

瞬间啊，我们是活在瞬间的生物啊！

——日常

今日python练习

Leetcode292.Nim 游戏

题目描述

你和你的朋友，两个人一起玩 Nim 游戏：

桌子上有一堆石头。
你们轮流进行自己的回合，你作为先手。
每一回合，轮到的人拿掉 1 - 3 块石头。
拿掉最后一块石头的人就是获胜者。

假设你们每一步都是最优解。请编写一个函数，来判断你是否可以在给定石头数量为 n 的情况下赢得游戏。如果可以赢，返回 true；否则，返回 false 。

思路

经典Nim，直接返回模4是否为0

解决

1
2
3
class Solution:
    def canWinNim(self, n: int) -> bool:
        return n % 4 != 0

2021.9.17

今日天气：多云

飞蛾并不觉得阴暗，它至少享受了短暂的光明

——朝闻道

今日python练习

Leetcode36.有效的数独

题目描述

判断一个 9x9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

数独部分空格内已填入了数字，空白格用 ‘.’ 表示。

思路

暴力，先检查每行，设置容量为9的数组，遇到一个数字就标记，若该数字之前标记过，则数独不合法

同样的方法检查每一列，每个九宫格

还有更快的方法，直接设立每列，每行，每九宫格的数字出现标记，一次遍历就检查完，但我一时间没想到，写博客的时候突然想到的

解决

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
import numpy
class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        flag = True;

        for i in range(9):
            flags = numpy.zeros(9, bool)
            for j in range(9):
                if board[i][j] == ".":
                    continue
                else:
                    num = int(board[i][j])
                    if flags[num - 1]:
                        flag = False
                        break
                    else:
                        flags[num - 1] = True
            if not flag:
                break

        for i in range(9):
            flags = numpy.zeros(9, bool)
            for j in range(9):
                if board[j][i] == ".":
                    continue
                else:
                    num = int(board[j][i])
                    if flags[num - 1]:
                        flag = False
                        break
                    else:
                        flags[num - 1] = True
            if not flag:
                break

        for xi in range(3):
            x = 3 * xi
            for yi in range(3):
                y = 3 * yi
                flags = numpy.zeros(9, bool)
                for i in range(3):
                    for j in range(3):
                        if board[x + i][y + j] == ".":
                            continue
                        else:
                            num = int(board[x + i][y + j])
                            if flags[num - 1]:
                                flag = False
                                break
                            else:
                                flags[num - 1] = True
        
        return flag

2021.9.16

今日天气：多云

在疯狂面前，理智是软弱无力的

——三体·地球往事

今日python练习

Leetcode212.单词搜索 II

题目描述

给定一个 m x n 二维字符网格 board 和一个单词（字符串）列表 words，找出所有同时在二维网格和字典中出现的单词。

单词必须按照字母顺序，通过 相邻的单元格 内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。

数据范围

1 <= m, n <= 12，words列表长度3e4，每个单词长度不超过10

思路

本题不能直接暴力搜索，暴力的话，起点数12 * 12，每个点做四次判断，4 ^ 10约为1e6，再加上每个字符串都需要搜索一次，3e4 * 12 * 12 * 4 ^ 10，总体运算次数已经不能承受了

采取构造字典树的办法，构造字典树的复杂度只有12 * 12 * 4 ^ 10约为1e8，每次查找字典树的复杂度是10，总计查找复杂度约为3e5

解决

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
import numpy
class Solution:
    def findAllWrods(self, visit, board, x, y, n, m, tire, totlist, p, times):
        nxt = ord(board[x][y]) - ord('a') 
        visit[x][y] = 1
        
        if tire[p][nxt] == 0:
            tire[p][nxt] = totlist[0]
            totlist[0] += 1
        p = tire[p][nxt]

        #print("%d %d %s" %(x, y, board[x][y]))

        times -= 1
        if times == 0:
            visit[x][y] = 0
            return

        if x + 1 < n and visit[x + 1][y] == 0:
            self.findAllWrods(visit, board, x + 1, y, n, m, tire, totlist, p, times)
        if y + 1 < m and visit[x][y + 1] == 0:
            self.findAllWrods(visit, board, x, y + 1, n, m, tire, totlist, p, times)
        if x - 1 > -1 and visit[x - 1][y] == 0:
            self.findAllWrods(visit, board, x - 1, y, n, m, tire, totlist, p, times)
        if y - 1 > -1 and visit[x][y - 1] == 0:
            self.findAllWrods(visit, board, x, y - 1, n, m, tire, totlist, p, times)
        visit[x][y] = 0

    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        totlist = [1]
        tire = numpy.zeros((100000, 26), int)
        
        n = len(board)
        m = len(board[0])
        for i in range(n):
            for j in range(m):
                visit = numpy.zeros((n, m))
                #print(i, j)
                self.findAllWrods(visit, board, i, j, n, m, tire, totlist, 0, 10)
            
        ret = []
        for word in words:
            p = 0
            flag = True
            for cha in word:
                nxt = ord(cha) - ord('a')
                if tire[p][nxt] == 0:
                    flag = False
                    break
                p = tire[p][nxt]
            if flag:
                ret.append(word)
        return ret

语法复习

1.参数传递方式

python中，字典，列表，元组参数都是可以在函数内部修改其值的，修改之后会影响到函数外，而数字，布尔等参数无法在函数内部修改其值，修改后不会影响函数外

python中无法像c++一样传递引用

2021.9.15

今日天气：晴

“What is my purpose？”

“You pass butter”

——Rick & Morty

今日python练习

Leetcode162.寻找峰值

题目描述

峰值元素是指其值严格大于左右相邻值的元素。

给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。

你可以假设 nums[-1] = nums[n] = -∞ 。

你必须实现时间复杂度为 O(log n) 的算法来解决此问题。

数据范围

数组长度不超过1000，暴力可做，但本题要求nlogn

思路

知道是二分，但不知道怎么二分，于是参考了思路，原来是随便比较两个数，峰值一定在偏大的那一侧，不得不说把两端设定为低谷实在是妙了

解决

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        l = 0
        h = len(nums) - 1
        m = (l + h) >> 1
        while l < h:
            if nums[m] < nums[m + 1]:
                l = m + 1
            else:
                h = m
            m = (l + h) >> 1
        return m

2021.9.14

今日天气：晴

没有了对高处的恐惧就体会不到高处之美

——三体·黑暗森林

今日python练习

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

题目描述

给你一个字符串 s 和一个字符串数组 dictionary ，找出并返回 dictionary 中最长的字符串，该字符串可以通过删除 s 中的某些字符得到。

如果答案不止一个，返回长度最长且字典序最小的字符串。如果答案不存在，则返回空字符串。

数据范围

s的长度，字典长度，字典中每字符串的长度都不会超过1000

思路

字符串子串的匹配只需要O(n + m)，忘记了，这题只需要直接暴力就行了

当时写了一个字典树

解决

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 adapt(self, s, words):
        j = 0
        flag = False
        for i in range(len(words)):
            while j < len(s) and s[j] != words[i]:
                j += 1
            if j == len(s):
                flag = True
                break
            j += 1

        if flag:
            return ""
        else:
            return words

    def cmp(self, s1, s2):
        if len(s1) > len(s2):
            return True
        elif len(s1) < len(s2):
            return False
        else:
            return s1 < s2

    def findLongestWord(self, s: str, dictionary: List[str]) -> str:
        ret = ""
        for words in dictionary:
            temp = self.adapt(s, words)
            if self.cmp(temp, ret):
                ret = temp
        return ret

语法复习

1.数组初始化

可以使用numpy库，调用numpy.zeros()方法来得到一个多维全0数组

知识点复习

1.字典树

字典树可以满足在一堆字符串中快速查找一个字符串的要求，其查找的复杂度不会超过被查找字符串的长度

建立方法：

首先建立一个节点数组，第一维是节点个数，等于字典中字符串长度×字符串数目，第二维是符号数，比如字符串中只有小写字母，那么第二维大小就是26

建立节点计数器tot，令其初值为1

遍历字典中的每一个字符串，每遇到一个新的字符串，设立一个指针为p，初始值为0即指向字典树的根节点，根据字符串的每个字符来挪动指针，比如当前字符为a，a是第0个字符，那么查看p指向的当前节点的下标为0的指针是否有值，若有，p移动过去，若没有，在tot处建立新节点，并使指针指向它，然后p移动过去

查找时，只需要按照同样的方法挪动指针，只不过遇到指针没有指向的，不再建立新节点而是直接返回查找失败

照这种方法，假设我们有catch在字典中，那么cat也可以查找成功，这显然不是我们想要的，所以，我们还需要建立ed数组对应每个节点，若该节点是某个字符串的结尾，我们就在ed数组里面加一个标记

2021.9.13

今日天气：晴

无言是最大的轻蔑

——三体·黑暗森林

今日python练习

Leetcode447.回旋镖的数量

题目描述

给定平面上 n 对 互不相同 的点 points ，其中 points[i] = [xi, yi] 。回旋镖 是由点 (i, j, k) 表示的元组 ，其中 i 和 j 之间的距离和 i 和 k 之间的距离相等（需要考虑元组的顺序）。

返回平面上所有回旋镖的数量。

数据范围

总计不到500个点

每个点坐标绝对值不大于1000

思路

这题数据比较弱，但直接暴力也肯定不行，但我们可以先顺着暴力的思路想：

首先，每个点都可以做中间的点，对每个点都求出它到其它点的距离

求出这些距离后，放入数组，找到相等的距离，计算出回旋镖数

找相等的距离可以使用排序后再遍历的方式

这样整个复杂度就是n²logn

看了题解，有很多人使用的是哈希表，复杂度会降到n²

哈希表还是弱项啊

解决

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def numberOfBoomerangs(self, points: List[List[int]]) -> int:
        ret = 0
        for i in points:
            d = []
            for j in points:
                dist = (i[0] - j[0]) ** 2 + (i[1] - j[1]) ** 2
                d.append(dist)
            d.sort()
            seqtime = 1
            for j in range(1, len(d)):
                if d[j] == d[j - 1]:
                    seqtime += 1
                else:
                    if seqtime == 1:
                        continue
                    ret += seqtime * (seqtime - 1)
                    seqtime = 1
            if seqtime != 1:
                ret += seqtime * (seqtime - 1)
        return ret

2021.9.12

今日天气：晴

弱小和无知从来都不是生存的障碍，傲慢才是

——三体·死神永生

今日python练习

Leetcode678.有效的括号字符串

题目描述

给定一个只包含三种字符的字符串：（ ，） 和 *，写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则：

任何左括号 ( 必须有相应的右括号 )。
任何右括号 ) 必须有相应的左括号 ( 。
左括号 ( 必须在对应的右括号之前 )。
* 可以被视为单个右括号 ) ，或单个左括号 ( ，或一个空字符串。
一个空字符串也被视为有效字符串。

数据范围

字符串长度为100以内

思路

看到这题就觉得是文法判断，一直想着怎么用自动机，仔细分析下发现这是个上下文有关文法，傻眼了

看了一眼提示才明白过来没那么难，分析下规律用贪心法就能做了

先不考虑星号，假设只有左右括号，我们可以推出来的关于合法字符串的结论：

1.任何一个前缀中，左括号数只可能比右括号数多

2.最终的字符串中左右括号一样多

那么我们可以记录一个数，每遇到一次右括号就减一，遇到左括号就加一，如果中间某个地方这个数变成了负数，我们认为这个字符串不合法，或者最终这个数不为0，我们也认为这个字符串不合法

那么，加入星号之后，我们就用贪心法，每次都尽量把星号当成一个右括号，这样，遇到星号时，我们上面记录的这个数也会减一，同时，我们记录一下星号数，这时，每遇到一个星号，我们把这个数目加2，至于为什么加2不加1，我们后面讲

那么，如果我们配对着配对着，发现左括号数不够了怎么办，我们就把原来看做右括号的星号，变回单纯的星号，如果还不够，再把星号变成左括号，即当左括号数为0，我们遇到一个右括号，就把星号数减一，这样就是为什么我们一开始统计星号数目时每次加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
class Solution:
    def checkValidString(self, s: str) -> bool:
        l_para = 0
        star = 0
        for i in s:
            if i == '(':
                l_para += 1
            elif i == '*':
                if l_para > 0:
                    l_para -= 1
                    star += 2
                else:
                    star += 1
            else:
                if l_para > 0:
                    l_para -= 1
                else:
                    if star > 0:
                        star -= 1
                    else:
                        return False
        
        if l_para == 0:
            return True
        else:
            return False

2021.9.11

今日天气：晴

“你父亲在回忆这件事后，对我发出这样的感叹：在中国，任何超脱飞扬的思想都会砰然坠地的，现实的引力太沉重了”

——三体·地球往事

今日python练习

Leetcode600.不含连续1的非负整数

题目描述

给定一个正整数 n，找出小于或等于 n 的非负整数中，其二进制表示不包含 连续的1 的个数。

数据范围

n最多1e9

思路

统计一个数n的二进制是否有连续1没有太好的方法，直接暴力的复杂度是log(n)，从1到n总计nlog(n)的复杂度对于1e9的规模来说肯定是不能接受的

那么我们另辟蹊径，寻找规律

设f(n)是我们要找的答案

我们不妨先找n的二进制为一连串1的数，比如3，7，15，找到f(n)的规律

为什么从这样的数开始找呢？因为具有代表性，比如3的二进制是两个1，那么f(3)就代表了所有二进制数位小于等于2的满足要求的数

那么，我们不妨设g(2) = f(3)，因为f(3)代表了所有二进制数位小于等于2的满足要求的数，以此类推g(3) = f(7)， g(4) = f(15)

下面就找f(15)

接下来，我们应该如何入手呢？15的二进制是四位数，四个1，我们如果把所有小于15的数分成两类，一类是四位数，另一类不是，那么不是四位数的一类肯定数位小于等于3位，就是g(3) = f(7)

那么满足要求的四位数的个数怎么求？我们试着构建一下，满足四位数，最高位是1，那么第三位肯定是0，这时候我们发现，可以自由选择的就是剩下的几位，剩下两位，个数为g(2) = f(3)

根据上面的推理，找到g的递推公式g(n) = g(n - 1) + g(n - 2)

g是一个斐波那契数列，我们找到最初两项g(0) = 1， g(1) = 2

接下来，我们把结论从二进制全1的数推到任意数，我们知道，对于任意正数n，其二进制最高位一定是1，假设n是l位二进制数，那么小于它的数又可以分成两种：

1.数位小于l的

2.数位等于l的

对于情况1，显然符合要求的数为g(l-1)

对于情况2呢？显然这些数的第l位都是1，那么第l-1位一定是0，那能不能说符合要求的数一定是g(l-2)呢？

可以看一个样例10010（十进制为18），对这个数来说，小于它的5位二进制数只有10000，10001两个，原因是我们确定前两位为10，后面三位并不会像我们之前推导类似11111这样的数时，是可以任意挑选的，而是只能在小于后三位010的基础上挑选

但如果n最高，次高位都是1，我们显然后几位就可以随意挑选了，这时候就是g(l-2)

所以，情况2的个数要再分两种情况：

2.1.若n首两位为10，则去掉n的最高位得到数t，f(t)即为情况2的结果，换句话说假设n为l位，则为f(n-1000……0)（l-1个0）

2.2.若n首两位为11，则情况2的结果为g(l-2)

得到了上面的思路，我们果断写了一份代码，结果超时了，为什么呢？因为斐波那契数列的实现方式有问题，我们使用的是递归实现return g(n - 1) + g(n - 2)这样在n非常大的时候时间复杂度就会指数级增长，因此，我们改用数组存储这个数列前100个的值，需要的时候直接取用

或许也可以使用非常装逼的矩阵快速幂来实现斐波那契数列，但没必要

解决

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
class Solution:
    def init(self):
        ret = []
        ret.append(1)
        ret.append(2)
        ret.append(3)
        for i in range(3, 100):
            ret.append(ret[i - 1] + ret[i - 2])
        return ret

    def f(self, n, num_of_0xf):
        if n == 0:
            return 1
        
        i = 1
        s = 1
        while i < n:
            i <<= 1
            i += 1
            s += 1
            #print("i = %x s = %d" % (i, s))

        if i == n:
            return num_of_0xf[s]
        else:
            s -= 1
            mask = 1
            mask <<= s
            i >>= 1
            #print("mask = %x, i = %x, s = %d" % (mask, i, s))
            n ^= mask
            #print(n)
            mask >>= 1
            t1 = num_of_0xf[s]
            t2 = 0
            if n & mask == 0:
                t2 = self.findIntegers(n)
            else:
                t2 = num_of_0xf[s - 1]
            #print(t1)
            return t1 + t2

    def findIntegers(self, n: int) -> int:
        num_of_0xf = self.init()
        return self.f(n, num_of_0xf)

语法复习

1.python的位运算

与C++的算符基本一致，若想要输出二进制，可以使用bin()函数

2021.9.10

今日天气：晴

“人类的伟大就在于面对恐惧时的崇高姿态”

——JOJO的奇妙冒险·战斗潮流

今日python练习

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

题目描述

一个班级里有 n 个学生，编号为 0 到 n - 1 。每个学生会依次回答问题，编号为 0 的学生先回答，然后是编号为 1 的学生，以此类推，直到编号为 n - 1 的学生，然后老师会重复这个过程，重新从编号为 0 的学生开始回答问题。

给你一个长度为 n 且下标从 0 开始的整数数组 chalk 和一个整数 k 。一开始粉笔盒里总共有 k 支粉笔。当编号为 i 的学生回答问题时，他会消耗 chalk[i] 支粉笔。如果剩余粉笔数量 严格小于 chalk[i] ，那么学生 i 需要 补充 粉笔。

请你返回需要 补充 粉笔的学生 编号 。

思路

这题标了中等难度，但这题不过是个简单暴力题而已

先统计一轮下来需要的粉笔数，然后取余，再从头到尾遍历找到需要补充的学生编号即可

不得不吐槽一句，leetcode的题难度标的实在太随意了，有时候太简单，这样的题也能标中等难度，有时候又太难，上次一个线段树居然标了简单，我愣是一时没想出来

解决

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def chalkReplacer(self, chalk: List[int], k: int) -> int:
        total = 0
        for i in chalk:
            total += i
        
        k %= total
        for i in range(len(chalk)):
            if k < chalk[i]:
                return i
            else:
                k -= chalk[i]

2021.9.9

今日天气：多云

“不知道会发生什么，这才是生活”

——日常

今日python练习

Leetcode68.文本左右对齐

题目描述

给定一个单词数组和一个长度 maxWidth，重新排版单词，使其成为每行恰好有 maxWidth 个字符，且左右两端对齐的文本。

你应该使用“贪心算法”来放置给定的单词；也就是说，尽可能多地往每行中放置单词。必要时可用空格 ‘ ‘ 填充，使得每行恰好有 maxWidth 个字符。

要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。

文本的最后一行应为左对齐，且单词之间不插入额外的空格。

说明:

单词是指由非空格字符组成的字符序列。
每个单词的长度大于 0，小于等于 maxWidth。
输入单词数组 words 至少包含一个单词。

思路

这题标了困难，但其实我觉得这种题只是繁琐，算不上困难，在大三上学期我练习准备CSP考试的时候，我曾经做了不少这样的题，什么字符串分割，markdown语法渲染等等。破这种题的诀窍就是自顶而下，逐步求精，不要事无巨细地从头模拟到尾，一个函数写下来，那样铁失败，铁难调bug

先看懂规则，这题就是把单词放在宽度有限的行里，大体分三种情况：

1.本行就一个单词，那么单词左对齐，后面空格补齐

2.本行是结尾行，单词左对齐，单词间有一个空格，后面空格补齐

3.除1，2外的情况，第一个单词左对齐，最后一个右对齐，平均分配空格，若除不开，则左边多分配一点

所以，关键就是看清本行是哪种情况，这里我们先实现一个函数，让这个函数能够判断本行能装下几个单词

有了这个函数之后，我们再考虑三种情况的区分和具体的渲染怎么做

情况1：判断当前单词+当前行单词数是否为总单词数

渲染方法：遍历输出当前单词+空格隔开，最后空格补齐

情况2：不是情况1，并判断当前单词数是否为1

渲染方法：直接当前单词+空格补齐

情况3：直接写else

渲染方法：先算出空格数除以单词间隔数的余数x和商y，在第1到x个单词之间，输出y+1个空格，之后输出y个空格

这样，我们的思路清晰，代码层次强，定位bug也迅速

解决

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
class Solution:
    def how_many_words(self, words, cur, maxWidth):
        i = cur
        num = 0
        last = maxWidth
        while i < len(words):
            if last - num < len(words[i]):
                break
            else:
                last -= len(words[i])
                num += 1
                i += 1
        return num, last

    def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
        i = 0
        ret = []
        
        while True:
            num, last = self.how_many_words(words, i, maxWidth)
            #print("num = %d, last = %d" % (num, last))
            i += num
            temp = ""
            if i == len(words):
                for j in range(num - 1):
                    temp += words[i - num + j]
                    temp += " "
                    #print(temp)
                temp += words[i - 1]
                temp += (" " * (last - num + 1))
                #print(temp)
                ret.append(temp)
                break
            elif num == 1:
                temp += words[i - 1]
                temp += (" " * (last - num + 1))
                #print(temp)
                ret.append(temp)
            else:
                base = last // (num - 1)
                eta = last % (num - 1)
                for j in range(0, eta):
                    temp += words[i - num + j]
                    temp += (" " * (base + 1))
                    #print(temp)
                for j in range(eta, num - 1):
                    temp += words[i - num + j]
                    temp += (" " * base)
                    #print(temp)
                temp += words[i - 1]
                #print(temp)
                ret.append(temp)

        return ret

语法复习

1.python不换行输出：

1
print(str, end="") # 表示输出str后，尾部什么都不加

2.函数多个返回值

直接返回元组即可，接收时也可以使用元组接收

1
2
3
4
5
def func()
	return x, y
    

x, y = func()

2021.9.8

今日天气：乌云

“爱而得其人，乃最佳；爱而失其人，次佳”

——JOJO的奇妙冒险·幻影之血

今日python练习

Leetcode502.IPO

题目描述

假设 力扣（LeetCode）即将开始 IPO 。为了以更高的价格将股票卖给风险投资公司，力扣 希望在 IPO 之前开展一些项目以增加其资本。 由于资源有限，它只能在 IPO 之前完成最多 k 个不同的项目。帮助 力扣 设计完成最多 k 个不同项目后得到最大总资本的方式。

给你 n 个项目。对于每个项目 i ，它都有一个纯利润 profits[i] ，和启动该项目需要的最小资本 capital[i] 。

最初，你的资本为 w 。当你完成一个项目时，你将获得纯利润，且利润将被添加到你的总资本中。

总而言之，从给定项目中选择 最多 k 个不同项目的列表，以 最大化最终资本 ，并输出最终可获得的最多资本。

答案保证在 32 位有符号整数范围内。

思路

这是一道贪心题目，显然在成本足够的情况下的时候，我们选的项目肯定是利润越高越好。而且，我们显然是不会选择负利润的项目的，这样我们的资本肯定会越来越多

这样的话，我们可以把当前可以选择的项目的利润，存在一个优先队列里，每次从队列里面取出利润最高的一项来完成之，这会导致我们的资本增加，以至于我们能够接到更多的项目，我们进一步把这样的项目来进入优先队列里。为了让我们能够更快捷地知道能够接到哪些项目，我们按照项目成本从小到大排序

这样，我们的复杂度就是排序的复杂度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
34
35
36
37
from queue import PriorityQueue
class Solution:
    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:
        pq = PriorityQueue()
        
        t = []
        for i in range(len(capital)):
            t.append((capital[i], -profits[i]))

        t.sort()
        
        index = 0
        for i in range(k):
            #print("i = %d" % i)
            
            while index < len(t):
                #print("index = %d" % index)
                #print(t[index][0])
                #print(w)
                if t[index][0] <= w:
                    #print("push %d" % t[index][1])
                    pq.put(t[index][1])
                    index += 1
                else:
                    break    

            if pq.empty():
                break

            nw = pq.get()
            if nw < 0:
                w -= nw
                #print("nw %d" % nw)
            else:
                break

        return w

语法复习

1.python优先队列：

1
2
3
4
from queue import PriorityQueue # 导入模块
pq = PriorityQueue()			# 建立队列
pq.put(elem)					# push操作
pq.got()						# pop()

2.数组排序

数组名.sort()

注意当数组元素是多元组时，会按照第一个的大小顺序排序，然后在第一个元素相对的情况下进行第二个的比较

sort不提供排序方法的话，会默认按照从小到大来排序，如果想要从大到小排序，需要把reverse参数设置为True

2021.9.6

今日天气：小雨/雾/乌云

“人不可能抑制自己指甲的生长，也不可能一直压抑自己的欲望！”

——JOJO的奇妙冒险·疯狂钻石

今日python练习

Leetcode704.二分查找

题目描述

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

思路

如题名

解决

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        low = 0
        high = len(nums) - 1
        mid = (low + high) // 2
        while low < high:
            if nums[mid] >= target:
                high = mid
            else:
                low = mid + 1
            mid = (low + high) // 2
        if nums[mid] == target:
            return mid
        else:
            return -1

语法复习

在py文件的第一行加入特定的注释

1
#!/usr/bin/env ……

这是一个解释器位置，如果想要可以直接在终端执行，就可以在文件第一行加入这样的注释，然后使用sudo chmod +x 文件名

2021.8.29

今日天气：小雨转阴

“我所追求的，不仅仅是一个结果”

“人一旦只追求结果，就会想方设法地抄近路”

“在抄近路的过程中，人又容易迷失真相，最终连做事的干劲也消耗殆尽了”

——JOJO的奇妙冒险·黄金之风

今日python练习

Leetcode1588.所有奇数长度子数组的和

题目描述

给你一个正整数数组 arr ，请你计算所有可能的奇数长度子数组的和。

子数组 定义为原数组中的一个连续子序列。

请你返回 arr 中所有奇数长度子数组的和。

思路

统计每个数被计算了几次即可，可以这样考虑，要形成一个奇数长子数组，假设我们需要在下标为i的数左边取a个数，右边取b个数，那么a，b要么都是奇数，要么都是偶数。

只要能计算出小于某个数的奇数个数和偶数个数即可

解决

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def odd(self, x):
        return (x + 1) // 2


    def even(self, x):
        return x // 2 + 1


    def sumOddLengthSubarrays(self, arr: List[int]) -> int:
        ret = 0
        for i in range(len(arr)):
            left = i
            right = len(arr) - i - 1
            ret += arr[i] * (self.odd(left) * self.odd(right) + self.even(right) * self.even(left))
        return ret

语法复习

python类方法中的self参数：

python的self类似于C++中的this，表示当前对象，使用self.方法名/属性名就可以在方法定义中使用该对象的方法和属性

值得注意的是，python类方法的第一个参数一定是self

今日知识点

1.弧长

若已知y=f(x)，那么可以将弧切分成数小段，然后使用勾股定理计算出每段的弧长为：

(dx²+dy²)^0.5

那么有弧长微元：

dl=(dx²+dy²)^0.5=(f'(x)²+1)^0.5*dx

那么在x1到x2之间的弧长，可以使用上面式子的定积分来计算

2021.8.28

今日天气：阴

我们所度过的每一个平凡的日常，也许就是接连不断发生的奇迹！

——日常

今日python练习

Leetcode1480.一维数组的动态和

题目描述

给出一个数值，返回其前缀和数组

解决

1
2
3
4
5
6
7
class Solution:
    def runningSum(self, nums: List[int]) -> List[int]:
        ret = [0]
        for i in range(len(nums)):
            ret.append(ret[i] + nums[i])
        del ret[0]
        return ret

语法复习

del的用法：

python的del不同于C的free和C++的delete。

由于python都是引用，而python有GC机制，所以，del语句作用在变量上，而不是数据对象上。

if __name__=='__main__':  
    a=1       # 对象 1 被 变量a引用，对象1的引用计数器为1  
    b=a       # 对象1 被变量b引用，对象1的引用计数器加1  
    c=a       #1对象1 被变量c引用，对象1的引用计数器加1  
    del a     #删除变量a，解除a对1的引用  
    del b     #删除变量b，解除b对1的引用  
    print(c)  #最终变量c仍然引用1

del删除的是变量，而不是数据。

if __name__=='__main__':  
    li=[1,2,3,4,5]  #列表本身不包含数据1,2,3,4,5，而是包含变量：li[0] li[1] li[2] li[3] li[4]   
    first=li[0]     #拷贝列表，也不会有数据对象的复制，而是创建新的变量引用  
    del li[0]  
    print(li)      #输出[2, 3, 4, 5]  
    print(first)   #输出 1

今日知识点

1.t分布

假设随机变量X服从标准正态分布，Y服从自由度为n的卡方分布，那么Z=X/(Y/n)^0.5服从自由度为n的t分布

t分布的性质

t分布的均值为0，概率密度左右对称

2021.8.23

今日天气：雨

人类的伟大就是勇气的伟大，人类的赞歌就是勇气的赞歌！

——JOJO的奇妙冒险·幻影之血

今日python练习

Leetcode1646.获取生成数组中的最大值

题目描述

给你一个整数 n 。按下述规则生成一个长度为 n + 1 的数组 nums ：

nums[0] = 0
nums[1] = 1
当 2 <= 2 * i <= n 时，nums[2 * i] = nums[i]
当 2 <= 2 * i + 1 <= n 时，nums[2 * i + 1] = nums[i] + nums[i + 1]

返回生成数组 nums 中的 最大 值。

数据范围

0 ≤ n ≤ 100

思路

模拟，把100个数都算出来就好

解决

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def getMaximumGenerated(self, n: int) -> int:
        if n == 0:
            return 0
        elif n == 1:
            return 1
        else:
            ret = 1
            nums = [0, 1]
            for i in range(2, n + 1):
                newnum = nums[i // 2]
                if i % 2 == 1:
                    newnum += nums[i // 2 + 1]
                if ret < newnum:
                    ret = newnum
                nums.append(newnum)
            return ret

语法复习

range的用法：

python3的range()返回的是一个可迭代对象，常和for连用

函数语法为：

range(start，stop，step)

表示以step为步长，从start开始，遍历到stop之前结束

注意是stop之前，换句话说，就是不包括stop

如果步长是1，可以省略step

还有一种用法是range(stop)

此时表示从0开始以步长为一遍历到stop-1

今日知识点

1.矩阵的迹

在线性代数中，一个n×n矩阵A的主对角线（从左上方至右下方的对角线）上各个元素的总和被称为矩阵A的迹（或迹数），一般记作tr(A)

迹的性质

1.迹不仅仅是对角线元素的和，还是所有特征值的和

2.tr(mA+nB) = mtr(A) + ntr(B)

3.tr(AB) = tr(BA)

2.三花猫

猫的花色位于X染色体上，因此三花猫一般都是有两条X染色体的母猫