每日一题题解

5166. 对称山脉 - AcWing题库

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# DP 状态转移为 第i到k的答案是 第i+1到第k-1个的答案再加上 abs(h[i] - h[i + j - 1])
# 用ans记录每个长度j下的最小值
n = int(input())
nums = list(map(int, input().split()))

s = [[0] * 5010 for _ in range(5010)]
ans = [0x3f3f3f3f] * 5010
h = [0] * 5010

for i in range(n):
    h[i+1] =  nums[i]   

for j in range(2,n + 1):
    for i in range(1,n-j+2):
        s[i][i + j - 1] = s[i + 1][i + j - 2] + abs(h[i] - h[i + j - 1])
        ans[j] = min(ans[j], s[i][i + j - 1])

ans[1] = 0
for j in range(1,n + 1):
    print(ans[j],end=' ')

5180. 正方形泳池 - AcWing题库

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
"""
枚举n太复杂，枚举t，枚举每棵树的位置（按顺序）然后不断更新 ans和上下距离 ans和水平距离
"""
n = int(input())
t = int(input())
tree = []
tree.append([-1,-1]) # 占位
for i in range(1,t + 1):
    a, b = map(int,input().split())
    tree.append([a, b])

tree.append([0, 0])
tree.append([0, n + 1])
tree.append([n + 1, 0])
tree.append([n + 1, n + 1])
t += 4 # 四个顶点插入树 树的个数要加上

ans = -1
tree.sort(key=lambda x:x[0]) #  对x排序
"""
先初始化最低点最高点d,u 为0 和 n + 1 然后枚举tree[i] 右边的tree[j]
不断向右枚举 当i j的水平距离大于 上下的最大距离（u-d-1）的时候 退出（因为被上下距离限制了，再往右的话 水平距离增大，但是没有用，正方形就看最短的边）
更新ans为x-a-1 然后更新上下的最短距离（每一次都更新，因为中间有树挡着了，就会减小泳池的面积）更新u和d

"""
for i in range(1, t + 1):
    d, u = 0, n + 1
    for j in range(i + 1, t + 1):
        x, y = tree[j]
        a, b = tree[i]
        if x - a - 1 > u - d - 1:
            break
        ans = max(ans, x - a - 1)
        if y >= b:
            u = min(u, y)
        if y <= b:
            d = max(d, y)

tree.sort(key=lambda x: x[1])
for i in range(1, t + 1):
    l, r = 0, n + 1
    for j in range(i + 1, t + 1):
        x, y = tree[j]
        a, b = tree[i]
        if y - b - 1 > r - l - 1:
            break
        ans = max(ans, y - b - 1)
        if x >= a:
            r = min(r, x)
        if x <= a:
            l = max(l, x)

print(ans)

1654. 到家的最少跳跃次数 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# BFS 搜索
class Solution:
    def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:
    	q,vis = deque([[0,1,0]]), set([0])
        lower, upper = 0,max(max(forbidden) + a, x) + b
        forbiddenSet = set(forbidden)
        while q:
            position, direction, step = q.popleft()
            if x == position:
                return step
            nextposition = position + a
            nextdirection = 1
            if lower <= nextposition <= upper and nextposition * nextdirection not in vis and nextposition not in forbiddenSet:
                vis.add(nextposition * nextdirection)
                q.append([nextposition, nextdirection, step + 1])
            # 不能两次退后
            if direction == 1:
                nextposition = position - b
                nextdirection = -1
                if lower <= nextposition <= upper and nextposition * nextdirection not in vis and nextposition not in forbiddenSet:
                    vis.add(nextposition * nextdirection)
                    q.append([nextposition, nextdirection, step + 1])
    return -1

823. 带因子的二叉树 - 力扣（LeetCode）

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
"""
dfs 先找到val的答案的个数 然后找val的左子树（x）的答案的个数 再找val的右子树（val//x）的答案 用@cache 变为记忆化搜索
"""
class Solution:
    def numFactoredBinaryTrees(self, arr: List[int]) -> int:
        s = set(arr)
        @cache
        def dfs(val):
            ans = 1
            for x in arr:
                if val % x == 0 and val // x in s:
                    ans += dfs(x) * dfs(val // x)
            return ans
       	return sum(dfs(x) for x in arr) % (10 ** 9 + 7)
    
# 递推 用f表示这个点作为根节点的时候有多少种情况 用idx反向查询这个点的下标
class Solution:
    def numFactoredBinaryTrees(self, arr: List[int]) -> int:
        arr.sort()
        idx = {x: i for i, x in enumerate(arr)}
        f = [1] * len(arr)
        for i in range(len(arr)):
            for j in range(i):
                val = arr[i]
                x = arr[j]
                if val % x == 0 and val // x in idx:
                    f[i] += f[j] * f[idx[val // x]]
        return sum(f) % (10 ** 9 + 7)

1761. 一个图中连通三元组的最小度数 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 枚举每一个三元组，然后求度数，可以预处理度数 注意最后出度要减6 因为三元组内每条相连的边被算了两次
# 用邻接矩阵来储存 

class Solution:
    def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:
        g = [[0] * n for _ in range(n)]
        degree = [0] * n
        
        for x, y in edges:
            x, y = x - 1, y - 1
            g[x][y] = g[y][x] = 1
            degree[x] += 1
            degree[y] += 1
        
        ans = inf
        for i in range(n):
            for j in range(i, n):
                if g[i][j] == 1:
                    for k in range(j, n):
                        if g[i][k] == g[j][k] == 1:
                            ans = min(ans, degree[i] + degree[j] + degree[k] - 6)
      	return -1 if ans == inf else ans

5183. 好三元组 - AcWing题库

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
"""
由于直接算不好算，所以先算出所有三元组的情况，之后再减去不符合的情况。
所有情况为n * (n - 1) * (n - 2) // 6
当三个数在同一点上时 不合规
两个点在同一点上 不合规
三个点在同一个半圆内时 不合规
同一个半圆内的点即距离（i，i + c/2]的点 这里面的每个点和Pi点都不合规
所以要预处理出前缀和，前缀和要处理到2 * c，因为环要变成链来处理的话就需要cnt不仅计数0~c-1还要计数c~2c-1
最后，当c为偶数的时候，i和i+c/2是对称的，会多减，要加回来
"""
N = 2000100
n, c = map(int, input().split())
p = list(map(int,input().split()))
cnt = [0] * N
s = [0] * N
for i in range(1, n + 1):
    cnt[p[i - 1]] += 1
    cnt[p[i - 1] + c] += 1

res = n * (n - 1) * (n - 2) // 6

s[0] = cnt[0]
for i in range(1, 2 * c):
    s[i] = s[i - 1] + cnt[i]
    
for i in range(c):
    if cnt[i] == 0:
        continue
    t = cnt[i]
    d = s[i + c // 2] - s[i]
    
    # 其实不需要判断也行
    if t >= 2:
        if t >= 3:
            res -= t * (t - 1) * (t - 2) // 6
        res -= t * (t - 1) // 2 * d
    res -= t * d * (d - 1) // 2

if c % 2 == 0:
    for i in range(c // 2):
        u, v = cnt[i], cnt[i + c // 2]
        if u >= 2:
            res += u * (u - 1) // 2 * v
        if v >= 2:
            res += v * (v - 1) // 2 * u

print(res)

5145. 同色环 - AcWing题库

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
// 判断环 那就是不能往回退 一直走到下一次遇见一个vis  注意设计dfs的时候要加上 ox oy 用于判断初始情况  注意什么时候用ox 什么时候用x  
#include <bits/stdc++.h>
using namespace std;
const int N = 100;
int n, m;
char nums[N][N];
bool vis[N][N];
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };

bool dfs(int x, int y, int ox, int oy)
{
    vis[x][y] = true;
    
    for (int i = 0; i < 4; i++)
    {
        int nx = x + dx[i];
        int ny = y + dy[i];

        if (nx >= 0 && nx < n && ny >= 0 && ny < m
            // 这一句的意思是 不能退回
            && !(nx == ox && ny == oy)
            // 颜色相同
            && nums[nx][ny] == nums[x][y])
        {
            // 再不可退回的情况下 只有存在首尾相接的环才可能碰到vis=true的情况
            if (vis[nx][ny] || dfs(nx, ny, x, y))
                return true;
        }
    }
    return false;
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> nums[i][j];
        }
    }

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (!vis[i][j])
            {
                if (dfs(i, j, -1, -1))
                {
                    cout << "Yes" << endl;
                    return 0;
                }
            }
        }
    }
    cout << "No" << endl;
    return 0;
}

1921. 消灭怪物的最大数量 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
# 看起来很简单 但是有几个点一直过不了 主要是怪物到达的时间有问题 应该是上取整  如果直接用//的话是下取整（突然觉得好傻）
class Solution:
    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:
        n = len(dist)
        # 上取整
        arrivetime = [math.ceil(dist[i] / speed[i]) for i in range(n)]

        arrivetime.sort()
        for attacktime, arrivetime in enumerate(arrivetime):
            if attacktime >= arrivetime:
                return attacktime
        return n

统计一个字符串的 k 子序列美丽值最大的数目 - 力扣 (LeetCode) 竞赛

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
# Counter 返回字典 每个元素是键 出现次数为值
# dfs
# 首先是dfs找到k子序列 在子序列满足长度为k的同时比较其美丽值是否为最大 当美丽值更新时（此时为第一个最大美丽值 所以直接让ans = mul）否则ans+mul  之后就是选或不选 add为当前这个子序列的美丽值 mul为当前这个子序列的美丽值的个数 （因为重复的元素）

class Solution:
    def countKSubsequencesWithMaxBeauty(self, s: str, k: int) -> int:
        c = Counter(s)
        if k > len(c):
            return 0
        Mod = 10 ** 9 + 7
        mx = -1
        ans = 0
        keys = list(c.keys())
        def dfs(i, count, add, mul):
            nonlocal mx, ans
            if count == k:
                if add > mx:
                    mx = add
                    ans = mul
                elif add == mx:
                    ans += mul
                ans %= Mod
                return
            if i + k - count > len(keys):
                return
            dfs(i + 1, count + 1, add + c[keys[i]], mul * c[keys[i]] % Mod)
            dfs(i + 1, count, add, mul)
        dfs(0,0,0,1)
        return ans


# 数学
# 求出出现频率前k高的字母 最大的美丽值就在这里面 需要注意的是 最后一个出现频率（k-1位）可能有多个字母（这样组成的子序列美丽值都相同且最大 ） 所以需要再次计算 算出重复的字母数量 然后进行组合计算C（n,k）n为相同的字母的个数 c为可以选的个数（前k个里面 去掉大于的 还要在等于的里面选c个 凑k子序列）
class Solution:
    def countKSubsequencesWithMaxBeauty(self, s: str, k: int) -> int:
        c = Counter(s)
        if k > len(c):
            return 0
        else:
            from math import comb
            Mod = 10 ** 9 + 7
            values = sorted(c.values(), reverse=True)
            ans = 1
            c = 0
            for i in range(k):
                if values[i] > values[k - 1]:
                    ans *= values[i]
                    ans %= Mod
                elif values[i] == values[k - 1]:
                    c += 1
                    ans *= values[i]
                    ans %= Mod
            return ans * comb(values.count(values[k - 1]),c) % Mod

2605. 从两个数字数组里生成最小数字 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# 主要是看一下这个写法 s = set(nums1) & set(nums2) 直接取出1 2 中的相同的数字
class Solution:
    def minNumber(self, nums1: List[int], nums2: List[int]) -> int:
        ret = 0
        a = min(nums1)
        b = min(nums2)
        if a > b:
            a, b = b, a
        ret = a * 10 + b

        s = set(nums1) & set(nums2)
        if not s:
            return ret 
        return min(s)

5198. 整理书籍 - AcWing题库

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
# 计算有几个L几个M 然后算有几个L不在前面 有几个M不在中间 然后至多需要交换这么多次 才能换好 但是当错位的L和M互换时 两次就只需要一次了 所以说取min(l,m)(这就是LM相互错位的个数)减掉就行
nums = list(input().strip())
n = len(nums)
cl, cm, cs = 0, 0, 0
for i, x in enumerate(nums):
    if x == 'L':
        cl += 1
    elif x == 'M':
        cm += 1
    elif x == 'S':
        cs += 1


wl, wm, lm, ml = 0, 0, 0, 0
for i in range(cl):
    if nums[i] != 'L':
        wl += 1
    if nums[i] == 'M':
        lm += 1
for i in range(cl, cl + cm):
    if nums[i] != 'M':
        wm += 1
    if nums[i] == 'L':
        ml += 1

print(wl + wm - min(lm, ml))

2594. 修车的最少时间 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
# 二分最长的时间 计算这个时间每个人可以修的车的数量 和 cars比较 （并不需要实际地去算 应该给每个人安排多少车 而是求最大修车数 看能不能修完）
class Solution:
    def repairCars(self, ranks: List[int], cars: int) -> int:
        left = 0
        right = cars * cars * min(ranks)
        
        while left < right:
            mid = (left + right) // 2
            if sum(isqrt(mid // r) for r in ranks) >= cars:
                right = mid
            else:
                left = mid + 1
        return right

Problem - F - Codeforces

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 求一个数，他的约数的个数（同一个约数可能出现很多次）最多，遍历1~n，ans[j] += len(cs[i])。因为i的所有倍数上的点，都满足条件。所以把每个ans[j] 都加上i的个数。遍历到n的时候，就把所有的数都加上了
import collections
def solve():
    n = int(input())
    a = list(map(int, input().split()))
    
    cs = collections.defaultdict(list)
    for i, x in enumerate(a):
        cs[x].append(i)
    ans = [0] * (n + 1)
    m = len(cs)
    for i in range(1, n + 1):
        j = i
        while j <= n:
            ans[j] += len(cs[i])
            j += i

    print(max(ans))

n = int(input())
for _ in range(n):
    solve()

210. 课程表 II - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 拓扑排序(注意拓扑排序 是看是不是所有的都进入过q 或者说 最后是不是所有入度都为0) 首先建图 同时增加入度 然后把入度为0的都加入q 不断循环 每次pop的同时 numCourse-1 记录进入q的个数 如果全部进了代表没有环 那么就可以返回 而上课顺序 恰好是从q pop的顺序
class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        graph = defaultdict(list)
        in_deg = [0] * numCourses
        for cur, pre in prerequisites:
            graph[pre].append(cur)
            in_deg[cur] += 1
        
        q = deque([i for i, x in enumerate(in_deg) if x == 0])
        how = []
        while q:
            pre = q.popleft()
            numCourses -= 1
            how.append(pre)
            for cur in graph[pre]:
                in_deg[cur] -= 1
                if in_deg[cur] == 0:
                    q.append(cur)
        
        if numCourses == 0:
            return how
        else:
            return []

630. 课程表 III - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 贪心＋优先队列 （反悔贪心） 很容易想到要先对结束时间排序 结束时间越晚 就越晚做，因为开始晚的先做如果做得完，可能前面的做不完了，开始晚的先做如果做不完，那前面的肯定做不完了。开始晚的后做，不管做不做得完，前一个肯定是不受影响的。
# 接着是按顺序取课 用sum记录当前总时间 h为优先队列（注意 heap默认是小根堆  为了使其成为大根堆 每次存入和取出使用相反数），如果sum+dur <= end 说明是可以都上的 那就加上 并且放入h  如果>end 不能都上 那么就判断当前的dur和之前已经存在的时间最长的课哪个时间更长 如果原来的课比当前课时间长 就要和当前的课进行替换（总数不变 sum变小） 使得sum最小 那么就更有可能多上几节课 如果当前的时间长 那这节课肯定选不了
class Solution:
    def scheduleCourse(self, courses: List[List[int]]) -> int:
        courses.sort(key = lambda x: x[1])
        n = len(courses)
        sum = 0
        h = []
        for dur, end in courses:
            if sum + dur <= end:
                sum += dur
                heappush(h, -dur)
            elif h and -h[0] > dur:
                sum -= -h[0] - dur
                heappop(h)
                heappush(h, -dur)
        return len(h)

1462. 课程表 IV - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution:
    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:
        # 拓扑排序的思路仍然是先建图 存储入度 循环找点  不同的是 （有向图） 这次0-1-2-3 不仅0-1连通 0-3也连通 要反映这样的一种关系 需要建立一个二维数组表示他们的连通关系  每次pop取出一个点 这个点是x连向的所有点 即列表graph[x] 遍历里面的每个元素 （入度减一等操作） 遍历每一个numCourse的点 如果他跟x有连接 或者跟y有连接就为True （h-y or h-x-y）
        # Toposort
        graph = defaultdict(list)
        in_deg = [0] * numCourses
        for pre, cur in prerequisites:
            graph[pre].append(cur)
            in_deg[cur] += 1
        ret = [[False] * numCourses for _ in range(numCourses)]
        q = deque([i for i, x in enumerate(in_deg) if x == 0])
        while q:
            x = q.popleft()
            for y in graph[x]:
                in_deg[y] -= 1
                ret[x][y] = True
                for h in range(numCourses):
                    ret[h][y] = ret[h][y] or ret[h][x]
                if in_deg[y] == 0:
                    q.append(y)
        return [ret[a][b] for a, b in queries]
    
    	
        # Floyd的思路 边权为True 建好图之后直接循环
        # Floyd
        graph = [[False] * numCourses for _ in range(numCourses)]
        for pre, cur in prerequisites:
            graph[pre][cur] = True
        
        for k in range(numCourses):
            for i in range(numCourses):
                for j in range(numCourses):
                    graph[i][j] = (graph[i][k] and graph[k][j]) or graph[i][j]

        return [graph[i][j] for i, j in queries]

Problem - E - Codeforces（新二分板子）

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
# 来自tllwtg的算法模板
"""
更好记录答案 也更有逻辑
if check():
res = mid
l = mid + 1
else:
r = mid - 1

return res
"""
import math
def solve():
    n, c = map(int, input().split())
    nums = list(map(int, input().split()))

    l, r, res = 1, 10 ** 9, -1

    while l <= r:
        mid = (l + r) // 2
        if c >= sum([(nums[i] + 2 * mid ) ** 2 for i in range(n)]):
            res = mid 
            l = mid + 1
        else:
            r = mid - 1
    print(res)

n = int(input())
for _ in range(n):
    solve()

Problem - D - Codeforces

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
# 求去掉几个可以使连续的最大 就是求最大然后用n减去
# 用diff记录差值 但其实可以优化 毕竟排序之后 差值只需要和前一个比较即可
def solve():
    n, k = map(int, input().split())
    nums = list(map(int, input().split()))
    nums.sort()
    diff = [0] * n
    diff[0] = nums[0]
    for i in range(1, n):
        diff[i] = nums[i] - nums[i - 1]
    # print(diff)
    cnt = 1
    maxi = 0
    for i in range(1, n):
        if diff[i] <= k:
            cnt += 1
        else:
            maxi = max(maxi, cnt)
            cnt = 1
    maxi = max(maxi, cnt)
    print(n - maxi)
    

n = int(input())
for _ in range(n):
    solve()
    
# 优化
def solve():
    n, k = map(int, input().split())
    nums = list(map(int, input().split()))
    nums.sort()
    
    
    cnt = 1
    maxi = 0
    pre = nums[0]
    for i in range(1, n):# 0不看 因为cnt初始值为1 从1开始
        if nums[i] - pre > m:
            maxi = max(maxi, cnt)
            cnt = 1
        else:
            cnt += 1
    	pre = nums[i]
    maxi = max(maxi, cnt)
    print(n - maxi)
    
    
n = int(input())
for _ in range(n):
    solve()

5151. 程序调用 - AcWing题库

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
// 通过索引找值 再通过值找索引  并且实现交换 主要是两个数组 一个是原数组 一个是pos数组 注意每次交换的时候两个数组都要交换 知道值a pos[a]即为索引 那a的前一个数就是pos[a] - 1 然后交换
#include <iostream>
using namespace std;
const int N = 1e5 + 7;
int s[N];
int f[N];
int w[N];
int main()
{
	int n, m, k;
	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++)
	{
		cin >> s[i];
		f[s[i]] = i;
		w[i] = (i - 1) / k + 1;
	}
	long long ret = 0;
	for (int i = 1; i <= m; i++)
	{
		int x;
		cin >> x;
		ret += w[f[x]];

		if (f[x] == 1)continue;

		swap(s[f[x]], s[f[x] - 1]);
		swap(f[s[f[x]]], f[s[f[x] - 1]]);
	}
	cout << ret;
}

213. 打家劫舍 II - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
# 打家劫舍1是一个动态规划问题 用f[k]来表示 前k间房子最多能偷多少钱 当k=n的时候就是答案 状态转移方程为f[i] = max(f[i -  1], f[i - 2] + nums[i]) 选i-1或者选i-2 + nums[i]  最后 如下的写法是优化空间复杂度的写法 因为每次仅需要前两个数和当前这个数 所以可以交替使用
# 打家劫舍2在1的基础上把首尾相连成环 这就导致首尾选不选的问题 这样的环的问题其实可以先排除掉环的影响再来做 即分为两类 首部选或不选（必定可且仅可分为两类）选首部的时候 尾部不能选（第二个也不能选） 那就是[2:-1] 不选首部的时候 就是[1:]然后看看哪个更大（有点类似之前实训课做过的枚举）
class Solution:
    def rob1(self, nums:List[int])->int:
        f0 = f1 = 0
        for x in nums:
            f0, f1 = f1, max(f0 + x, f1)
        
        return f1

    def rob(self, nums: List[int]) -> int:
        return max(nums[0] + self.rob1(nums[2:-1]), self.rob1(nums[1:]))

337. 打家劫舍 III - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 树形DP 还是一样分析 根节点选或者不选（注意根节点不选 下一个结点也不一定要选）求出 左子树不选根的最大值和左子树选根的最大值 和 右子树不选根的最大值和右子树选根的最大值 如果选根 那么总共的最大值就是根+左不选根+右不选根 如果不选根 那就是左子树最大（选根和不选根 的最大）和右子树最大 相加
# 注意先想好dfs是做什么的  从root开始 返回选root的最大值 和不选root的最大值

# 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 rob(self, root: Optional[TreeNode]) -> int:
        def dfs(root):
            if root is None:
                return 0, 0
           	l_rob, l_not_rob = dfs(root.left)
            r_rob, r_not_rob = dfs(root.right)
            rob = root.val + l_not_rob + r_not_rob
            not_rob = max(l_rob, l_not_rob) + max(r_rob, r_not_rob)
            return rob, not_rob
        
        return max(dfs(root))

2560. 打家劫舍 IV - 力扣（LeetCode）

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
# 二分答案 最小化能够抢到的最大值 类似的表述就是二分答案的套路
# 二分偷取的钱数（得到最小值）  当偷盗的房子数满足k的时候 就可以成为一个答案  本解还有贪心 只要遇到可偷的就立即偷
class Solution:
    def minCapability(self, nums: List[int], k: int) -> int:
        minn = min(nums)
        maxn = max(nums)
        res = -1
        while minn <= maxn:
            mid = (maxn + minn) // 2
            cnt = 0
            vis = False
            for num in nums:
                if not vis and num <= mid:
                    cnt += 1
                    vis = True
                else:
                    vis = False
            if cnt < k:
                
                minn = mid + 1
            else:
                res = mid
                maxn = mid - 1
        return res
    
# 也可以用二分+动态规划 状态表示为从0~i可偷的房间数为f[i] 状态计算为f[i] = max(f[i - 1], f[i - 1] + 1) 
class Solution:
    def minCapability(self, nums: List[int], k: int) -> int:
        def solve(mx: int) -> int:
            f0 = f1 = 0
            for num in nums:
                if num <= mx:
                   f0, f1 = f1, max(f1, f0 + 1)
            	else:
                    f0 = f1
           	return  f1
       	return bisect_left(range(max(nums)), k, key=solve)

2603. 收集树中金币 - 力扣（LeetCode）

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 collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:
        n = len(coins)
        graph = [[] for _ in range(n)]
        for a, b in edges:
            graph[a].append(b)
            graph[b].append(a)
        
        deg = list(map(len, graph))
        q = deque()
        res = n - 1 # 总边数
        # 先把没有金币的叶子节点存入数组（相当于拓扑排序的放入入度为0的点
        for i, (d, c) in enumerate(zip(deg, coins)):
            if d == 1 and c == 0:
                q.append(i)
        # 删除所有没有金币的叶子节点
        while q:
            x = q.popleft()
            res -= 1 # 每次循环都会删掉一条边
            for y in graph[x]:
                deg[y] -= 1
                if deg[y] == 1 and coins[y] == 0:
                    q.append(y)

        # 删除最下面两层结点（叶子结点和叶子节点的父节点）（此时的叶子节点是含金币的因为不含的已经删除）
        for i, (d, c) in enumerate(zip(deg, coins)):
            if d == 1 and c == 1:
                q.append(i)
        # 这一层的所有含金币的叶子都被删除了 那么这些线就不用走了 删除的总数就是len(q)      
        res -= len(q)

        # 接下来删除叶子节点的父节点（叶子在上面已经删除）
        for x in q:
            for y in graph[x]:
                deg[y] -= 1
                if deg[y] == 1:
                    res -= 1

        return max(0, res * 2)

1993. 树上的操作 - 力扣（LeetCode）

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 LockingTree:
	# 初始化需要有父节点和每个父节点的子节点
    def __init__(self, parent: List[int]):
        n = len(parent)
        self.parent = parent
        self.lockNodeUser = [-1] * n
        self.children = [[] for _ in range(n)]
        
        for node, p in enumerate(parent):
            if p != -1:
                self.children[p].append(node)


    def lock(self, num: int, user: int) -> bool:
        if self.lockNodeUser[num] == -1:
            self.lockNodeUser[num] = user
            return True
        else:
            return False

    def unlock(self, num: int, user: int) -> bool:
        if self.lockNodeUser[num] == user:
            self.lockNodeUser[num] = -1
            return True
        else:
            return False
	# 难点主要是更新 如果该结点没有上锁 并且祖先没有上锁 并且孩子有上锁（同时解锁所有孩子） 
    def upgrade(self, num: int, user: int) -> bool:
        res = self.lockNodeUser[num] == -1 and not self.haslockedansester(num) and self.checkandlockdescendant(num)
        if res:
            self.lockNodeUser[num] = user
        return res
    # 由父节点不断向上 直到根节点 如果有上锁的 就直接返回 否则就继续向上
    def haslockedansester(self, num: int) -> bool:
        res = self.parent[num]
        while num != -1:
            if self.lockNodeUser[num] != -1:
                return True
            else:
                num = self.parent[num]
        return False
	# 如果找到了一个上锁的子节 就直接解锁  因为只要有上锁 就表示满足要求 需要解锁 而如果都没有上锁 那解锁操作也不会影响原来的结点
    def checkandlockdescendant(self, num: int)->bool:
        res = self.lockNodeUser[num] != -1
        self.lockNodeUser[num] = -1
        for child in self.children[num]:
            res |= self.checkandlockdescendant(child)
        return res
# Your LockingTree object will be instantiated and called as such:
# obj = LockingTree(parent)
# param_1 = obj.lock(num,user)
# param_2 = obj.unlock(num,user)
# param_3 = obj.upgrade(num,user)

146. LRU 缓存 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
class Node:
    def __init__(self, key=0, value=0):
        self.value = value
        self.next = None
        self.prev = None
        self.key = key

class LRUCache:
    # 因为需要O(1) 的存取 所以使用双向链表加字典
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.head = Node()
        self.head.prev = self.head
        self.head.next = self.head
        self.map = dict()

    
    def get(self, key: int) -> int:
        node = self.get_node(key)
        return node.value if node else -1

    # 插入 如果已经在的话就修改 如果不在的话首先 在map中记录 如何插入链表头 如果大于capacity的话 就删除链表尾(因为一开始把每次访问的都放在头部了（LRU的特性）所以删除的时候就可以直接删除尾部)
    def put(self, key: int, value: int) -> None:
        node = self.get_node(key)
        if node:
            node.value = value
            return
        
        self.map[key] = node = Node(key, value)
        self.push_front(node)
        if len(self.map) > self.capacity:
            back_node = self.head.prev
            del self.map[back_node.key]
            self.remove(back_node)

    
    def push_front(self, x: Node):
        x.prev = self.head
        x.next = self.head.next
        self.head.next.prev = x
        self.head.next = x
    
    def remove(self, x: Node):
        x.prev.next = x.next
        x.next.prev = x.prev

    # 查找 如果key不在map的话 return None 否则把他放到链表头
    def get_node(self, key: int) -> Optional[Node]:
        if key not in self.map:
            return None
        node = self.map[key]
        self.remove(node)
        self.push_front(node)
        return node

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

460. LFU 缓存 - 力扣（LeetCode）

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
class Node:
    # 结点的定义 双向链表的结点加上字典的key和访问次数cnt
    def __init__(self, key=0,value=0,next=None,prev=None):
        self.value = value
        self.next = next
        self.prev = prev
        self.cnt = 1
        self.key = key

# 需要建一个次数表 把访问次数相同的放在一起 用字典实现 key为访问次数
class LFUCache:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.key_to_node = dict()
        def new_node()->Node:
            head = Node()
            head.next = head
            head.prev = head
            return head
        self.freq_to_head = defaultdict(new_node)
    
        

    def get(self, key: int) -> int:
        node = self.get_node(key)
        return node.value if node else -1
    # 当这本书已经存在的时候 修改值 否则要放入（访问一次）中（注意先判断是否已满）
    def put(self, key: int, value: int) -> None:
        node = self.get_node(key)
        if node:
            node.value = value
            return 
        # 如果已满就拿出访问min_freq次的最下面的书（最不常用）
        if len(self.key_to_node) == self.capacity:
            phead = self.freq_to_head[self.min_freq]
            back_node = phead.prev # 最不常用的
            del self.key_to_node[back_node.key]  # 从字典删除
            self.remove(back_node) # 从链表中删除
            # 如果删除的是头结点 那就直接把整个链表删除了
            if phead.prev == phead:
                del self.freq_to_head[self.min_freq]
        # 插入这本书
        self.key_to_node[key] = node = Node(key, value)
        # 放到最上面
        self.push_front(self.freq_to_head[1],node)
        # 刚插入的访问次数必定为1
        self.min_freq = 1

    def push_front(self, head:Node, x:Node):
        x.prev = head
        x.next = head.next
        x.next.prev = x
        x.prev.next = x

    def remove(self, x:Node):
        x.prev.next = x.next
        x.next.prev = x.prev

    def get_node(self, key: int):
        if key not in self.key_to_node:
            return None
        node = self.key_to_node[key]# 找到这本书
        self.remove(node)# 去掉
        phead = self.freq_to_head[node.cnt]
        # 如果这本书原来所在的链表只有他一个 那就删除链表
        if phead.prev == phead:
            del self.freq_to_head[node.cnt]
            # 如果这本书恰好是访问一次的链表 那么删除之后就没有访问一次的了 至少也是访问两次的
            if self.min_freq == node.cnt:
                self.min_freq += 1
        # 这本书访问次数加1
        node.cnt += 1
        # 插到最上面
        self.push_front(self.freq_to_head[node.cnt], node)
        return node
        

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

587. 安装栅栏 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution:
    def outerTrees(self, trees: List[List[int]]) -> List[List[int]]:
        # 求扫过的面积 如果<0 说明需要更新
        def cross(p: List[int], q: List[int], r: List[int]) -> int:
            return (q[0] - p[0]) * (r[1] - q[1]) - (q[1] - p[1]) * (r[0] - q[0])
        
        n = len(trees)
        if n < 4:
            return trees

        trees.sort()

        hull = [0]
        used = [False] * n
        # 求凸包下半部分
        for i in range(1, n):
            while len(hull) > 1 and cross(trees[hull[-2]], trees[hull[-1]], trees[i]) < 0:
                used[hull.pop()] = False
            used[i] = True
            hull.append(i)
        # 求凸包的上半部分
        m = len(hull)
        for i in range(n - 2, -1, -1):
            if not used[i]:
                while len(hull) > m and cross(trees[hull[-2]], trees[hull[-1]], trees[i]) < 0:
                    used[hull.pop()] = False
                used[i] = True
                hull.append(i)
        # hull[0] 是起点 同时参加上半部分的检测 所以要删掉
        hull.pop()
        return [trees[i] for i in hull]

2251. 花期内花的数目 - 力扣（LeetCode）

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
# 差分前缀和 不需要每次把每个区间全部加上 这样复杂度过高 而是只需要在区间开头处+1 在区间结尾处-1 然后排序保证访问的时候是遍历的顺序 计算前缀和  如第一个人第二分钟来 那就算出第二分钟有几朵花 就是第二分钟的前缀和 
class Solution:
    def fullBloomFlowers(self, flowers: List[List[int]], people: List[int]) -> List[int]:
        diff = Counter()
        for s, e in flowers:
            diff[s] += 1
            diff[e + 1] -= 1

        time = sorted(diff.keys())
        s = j = 0

        for p, i in sorted(zip(people, range(len(people)))):
            while j < len(time) and time[j] <= p:
                s += diff[time[j]]
                j += 1
            people[i] = s

        return people
    
# 或者更简单的 直接计算第i分钟的花的数量  用第i分钟开花的数量减去第j分钟开花的数量 对开花时间和结束时间排序获得start和end数组 通过二分寻找开花数和凋谢数
class Solution:
    def fullBloomFlowers(self, flowers: List[List[int]], people: List[int]) -> List[int]:
        start = sorted(s for s, _ in flowers)
        end = sorted(e for _, e in flowers)
        return [bisect_right(start, p) - bisect_left(end, p) for p in people]

2731. 移动机器人 - 力扣（LeetCode）

发现 最后只需要计算机器人的间隔 左右相碰之后转向 其实也就可以视为两个之间互换了 之间的 距离不会受到影响 

1
2
3
4
比如a 0R b 2L 3s 
1s 时在1 处相碰   转向 a向左 b向右
然后3s后  a在-1 b在3
其实也就相当于  a直接走3s到3  b直接走3s到-1  距离不变  机器人间不需要区分

然后计算距离 两两之间的差可以O(n)计算！！但是注意 必须有序

1
2
3
4
5
6
7
1 3 4 8 9 之间的差为
3-1 + 4-1 + 8-1 + 9-1
      4-3 + 8-3 + 9-3 
            8-4 + 9-4
                  9-8
因此每次算一个即可  ans + i * nums[i] 表示排i的数共被加了几次 3 1次 4 两次 8 三次 9 四次
再减去s  s表示每次减去的数  第一次减1  第二次减4（1 + 3） 第三次减8 （1 + 3 + 4） 第四次减16（1 + 3 + 4 + 8）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def sumDistance(self, nums: List[int], s: str, d: int) -> int:
        n = len(nums)
        for i in range(n):
            f = -1 if s[i] == 'L' else 1
            nums[i] += f * d
        nums.sort()

        ans = 0
        s = 0
        for i in range(n):
            ans += i * nums[i] - s
            s += nums[i]
        return ans % (10 ** 9 + 7)

2512. 奖励最顶尖的 K 名学生 - 力扣（LeetCode）

不需要用结构体也可以 用zip来直接sort

用split分割单词

1
2
3
4
5
6
7
8
9
10
class Solution:
    def topStudents(self, positive_feedback: List[str], negative_feedback: List[str], report: List[str], student_id: List[int], k: int) -> List[int]:
        score = defaultdict(int)
        for w in positive_feedback:
            score[w] = 3
        for w in negative_feedback:
            score[w] = -1
        a = sorted((-sum(score[w] for w in r.split()), i) for r, i in zip(report, student_id))

        return [i for _, i in a[:k]]

1488. 避免洪水泛滥 - 力扣（LeetCode）

不是每次晴天就去寻找抽哪个 而是到了后面 发现他要发洪水之后 就去前面找他下雨之后的第一个晴天 把他的水抽干 如果没找到 就直接返回空数组

注意用bisect_left寻找该湖泊下雨后第一个晴天

用pop删除这个晴天

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from sortedcontainers import SortedList

class Solution:
    def avoidFlood(self, rains: List[int]) -> List[int]:
        n = len(rains)
        ans = [1] * n
        sun_day = SortedList()
        full = {}
        for i in range(n):
            if rains[i] == 0:
                sun_day.add(i)
            else:
                if rains[i] not in full:
                    full[rains[i]] = i
                else:
                    j = sun_day.bisect_left(full[rains[i]])
                    if not 0 <= j < len(sun_day):
                        return []
                    ans[sun_day.pop(j)] = rains[i]
                    full[rains[i]] = i
                ans[i] = -1
        return ans

1726. 同积元组 - 力扣（LeetCode）

不需要三重循环来找 a * b // c 在字典里面的

而是计数 记录下同一个积的两个数 的组合有多少种 然后用a * (a - 1) 计算种数

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def tupleSameProduct(self, nums: List[int]) -> int:
        mp = defaultdict(int)
        n = len(nums)
        ans = 0
        for i in range(n):
            for j in range(i + 1, n):
                mp[nums[i] * nums[j]] += 1
        m = len(mp)
        for x in mp.values():
            ans += x * (x - 1) * 4
        return ans

2316. 统计无向图中无法互相到达点对数 - 力扣（LeetCode）

主要是最后计算乘法超时了 乘法不需要再额外循环来计算 可以直接在 BFS循环里面算出前缀和 然后相乘 求得两两相乘的和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution:
    def countPairs(self, n: int, edges: List[List[int]]) -> int:
        q = deque()
        def bfs(i):
            q.append(i)
            s = 1
            vis[i] = 1
            
            while q:
                x = q.popleft()
                for y in graph[x]:
                    if not vis[y]:
                        vis[y] = 1
                        s += 1
                        q.append(y)
            return s
            
                    

        graph = defaultdict(list)
        for (a, b) in edges:
            graph[a].append(b)
            graph[b].append(a)
        
        vis = [0] * (n + 1)
        total = ret = 0
        for i in range(n):
            if not vis[i]:
                size = bfs(i)
                ret += size * total
                total += size
        return ret

1402. 做菜顺序 - 力扣（LeetCode）

动态规划

每次有选和不选这道菜两种 用dp[i] [j] 表示前i道菜种选了j道菜 达到的最大值

当i == j的时候必须选第i道菜

其他时候 就比较不选这道菜 dp[i - 1] [j] 和选这道菜dp[i -1 ] [j -1 ] + sa[i - 1] * j 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
int dp[550][550];
class Solution {
public:
    int maxSatisfaction(vector<int>& satisfaction) {
        for(int i=0; i<550; i++){
            for(int j=0; j<550; j++)
                dp[i][j] = 0;
        }
        int n = satisfaction.size();
        sort(satisfaction.begin(), satisfaction.end());
        dp[1][0] = 0;
        dp[1][1] = satisfaction[0];
        for(int i=2; i<=n; i++){
            for(int j=0; j<=i; j++){
                if(j==0) dp[i][j] = 0;
                else{
                    if(i==j) 
                        dp[i][j]= dp[i-1][j-1]+satisfaction[i-1]*j;
                    else
                        dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]+satisfaction[i-1]*j);
                }
                
            }
        }
        int ans = 0;
        for(int i=0; i<=n; i++)
            ans = max(ans, dp[n][i]);
        return ans;


    }
};

贪心

s1+2s0>s0即s1+s0>0

s2+2s1+3s0>s1+2s0即s2+s1+s0>0

因此只需要反向遍历 找到前面加起来大于0的部分 的和就是最大的

1
2
3
4
5
6
7
8
9
10
sa.sort(key=lambda x:-x)
        s = 0
        ret = 0
        for c in sa:
            if s + c > 0:
                s += c
                ret += s
            else:
                break
        return ret

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

至少有h篇论文有h引的次数

排序之后 二分下标mid 有 citation[mid] 引的文章有n - mid篇 只要引用次数大于文章数 比如8引的文章有两篇 （此时h = 2）说明要往前找 有没有更多文章 如果3引的文章有5篇（此时h = 3）说明要往后找有没有更大的引用数

最后二分得到的答案是最多引的最多文章数的 下标 比如 0 2 8 8 8 8 mid = 2

所以返回答案应该是n – mid

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 hIndex(self, citations: List[int]) -> int:
        citations.sort()
        n = len(citations)
        l, r = 0, n - 1

        if n == 0 or citations[-1] == 0:
            return 0

        def check(mid):
            if citations[mid] >= n - mid:
                return False
            return True
        ret = 0
        while l <= r:
            mid = (l + r) // 2
            if check(mid):
                l = mid + 1
            else:
                
                r = mid - 1
                ret = mid
        return n - ret

2003. 每棵子树内缺失的最小基因值 - 力扣（LeetCode）

只要nums中没有1 那么直接返回1 所有的最小缺失值都是1

那么同理 只要一棵子树中没有1 那么这颗子树上的所有点的缺失值都是1

于是用一次dfs找出1 的位置 找到1 之后 从根到1 的这条链上 所有点的缺失值要重新计算 而其他链上的缺失值全部为1

计算根到 1 的这条链的缺失值 应该自底向上来找 由于缺失值是单调不减的 可以维护一个缺失值now 一旦now已经访问过 那就直接让now++ 直到最小的未访问的值

到底之后开始向上寻找 注意 链上的每个结点都有自己的子树 缺失值要在整棵子树上寻找 于是到达一个结点 要先访问所有的非链上的所有结点 把所有值做标记 最终把最小缺失值赋值给i

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 smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:
        n = len(nums)
        if 1 not in nums:
            return [1 for _ in range(n)] 
        g = defaultdict(list)
        for i in range(1, n):
            g[parents[i]].append(i)
        visit = [False] * 100010
        has1 = [False] * 100010
        ans = [0] * n
        now = 1
        def dfs1(i):
            if nums[i] == 1:
                has1[i] = True
            else:
                has1[i] = False
            for f in g[i]:
                dfs1(f)
                has1[i] |= has1[f]
            if not has1[i]:
                ans[i] = 1


        def dfs3(i):
            for j in g[i]:
                dfs3(j)
            visit[nums[i]] = True
                
        def dfs2(i):
            nonlocal now
            if not has1[i]:
                return 
            for j in g[i]:
                if has1[j]:
                    dfs2(j)
            
            for j in g[i]:
                if not has1[j]:
                    dfs3(j)
            visit[nums[i]] = True

            while visit[now]:
                now += 1
            ans[i] = now
        
        dfs1(0)
        dfs2(0)
        return ans

117. 填充每个节点的下一个右侧节点指针 II - 力扣（LeetCode）

层序遍历

关键在于 s = len(q) 直接取出当前层的结点数 然后通过for循环来遍历

层序+链表

遍历当前层的时候 连接下一层的结点

设置哨兵结点 遍历完当前层之后从哨兵结点开始下一层遍历

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
"""
# Definition for a Node.
class Node:
    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next
"""

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        if root is None:
            return root
        """q = deque([root])
        while q:
            s = len(q)
            pre = None
            for i in range(s):
                x = q.popleft()
                if pre:
                    pre.next = x
                pre = x
                if x.left:
                    q.append(x.left)
                if x.right:
                    q.append(x.right)
                
        return root"""
        cur = root
        while cur:
            dummy = Node()
            pre = dummy
            while cur:
                if cur.left:
                    pre.next = cur.left
                    pre = pre.next
                if cur.right:
                    pre.next = cur.right
                    pre = pre.next
                cur = cur.next
            cur = dummy.next
        return root

318. 最大单词长度乘积 - 力扣（LeetCode）

哈希->位运算

一开始想到用哈希表存储 每个单词中 每个字母是否出现 即用列表存储哈希表 但是这样时间复杂度太高 每次查重的时候都需要遍历前i个单词的每个字母

可以用位运算优化 26个单词对应26个bit位 每次查重只需要 做与运算就可以判断是否有重复的单词

（前面单词的长度 为len(word[j]) 因为是for j in range(i)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def maxProduct(self, words: List[str]) -> int:
        sc = []
        maxret = 0
        n = len(words)
        for i in range(n):
            mask = 0
            for c in words[i]:
                mask |= (1 << ord(c) - ord('a'))
            sc.append(mask)
            if i == 0:continue
            for j in range(i):
                if mask & sc[j] == 0 and len(words[j]) * len(words[i]) > maxret:
                    maxret = len(words[j]) * len(words[i])
        return maxret

位运算+哈希

哈希表不止能放1 然后判断是否出现啊 可以放每个单词的长度

如果两个单词相同的话 就是对应的位运算值相同 也就是mask相同 那么只需要取最大的长度就可以了 即保证哈希表中存放的都是这个单词最大的长度 可以减少重复的循环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def maxProduct(self, words: List[str]) -> int:
        mp = dict()
        maxret = 0
        n = len(words)
        for i in range(n):
            mask = 0
            l = len(words[i])
            for c in words[i]:
                mask |= (1 << ord(c) - ord('a'))
            if mask in mp and len(words[i]) > mp[mask]:
                mp[mask] = l
            elif mask not in mp:
                mp[mask] = l
            if i == 0:continue
            for m, v in mp.items():
                if mask & m == 0 and v * l > maxret:
                    maxret = v * l
        return maxret

2258. 逃离火灾 - 力扣（LeetCode）

其实类似于脑筋急转弯 最后分类完只需要看 人是不是比火先到达安全屋即可

  • 人能到安全屋
    • 火不能到安全屋10**9
    • 火能到安全屋
      • 火比人先到 -1
        • 火能不能在中途烧到人？ 不可能 因为火如果在中途烧到人 那么火就可以沿着 人的这条路走到安全屋 那么火一定是比人先到的
      • 火比人后到 t
  • 人不能到安全屋 -1

最后再看 火如果烧到了安全屋的上和左两格 那就把路封死了 即人和火同时到这两格 是不行的 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
def bfs(q: List[Tuple[int, int]]) -> (int, int, int):
            d = [[-1] * m for _ in range(n)]
            for i, j in q:
                d[i][j] = 0
            ti = 1
            while q:
                t = q
                q = []
                for i, j in t:
                    for k in range(4):
                        ni, nj = i + dx[k], j+ dy[k]
                        if 0 <= ni < n and 0 <= nj < m and grid[ni][nj] == 0 and d[ni][nj] < 0:
                            d[ni][nj] = ti
                            q.append((ni, nj))
                ti += 1
            return [d[-1][-1], d[-1][-2], d[-2][-1]]
        
        man, m1, m2 = bfs([(0,0)])
        if man < 0:
            return -1
        
        fire_pos = [(i, j) for i, row in enumerate(grid) for j, x in enumerate(row) if x == 1]
        fire, f1, f2 = bfs(fire_pos)
        if fire < 0:
            return 10 ** 9
        
        d = fire - man
        if d < 0:
            return -1
        
        if m1 != -1 and m1 + d < f1 or m2 != -1 and m2 + d < f2:
            return d
        return d - 1

Problem - 1169B - Codeforces

思考题 乍一看很难 但是其实很简单

找是否有两个数 x y 使得每个数对至少有一个x 或y

那我们就用第一个数对的两个数 这两个数 必定有一个是x

但是不知道哪个是 于是枚举

假设a[0] 是x 到所有的数对中找 是否都含了a[0] 如果不含 那么这个数对中 的a[i] b[i] 必定有一个数 是y 然后再用x y 到后面的每个数组中找 如果有不含x y 的就是NO 否则为YES 实现的话这里可以从0到m 找到就++ 看最后是不是m个

注意 不要用+=i 最后算 (m - 1) * m / 2 会爆int

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
//这段代码还可以优化就是说...
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using PII = pair<int, int>;

#define pb push_back
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define endl '\n'

#define debug(x)                          \
    {                                     \
        cerr << #x << " = " << x << endl; \
    }
#define debugfull(x)                                                      \
    {                                                                     \
        cerr << #x << " = " << x << " (line " << __LINE__ << ")" << endl; \
    }

/*-------------------------------------------*/
int n, m;
const int N = 3e5 + 10;
vector<int> a(N), b(N), ca(N), cb(N);
bool check(int x)
{

    int p = -1, q = -1;
    for (int i = 0; i < m; i++)
    {
        if (a[i] == x || b[i] == x)
            continue;
        else
        {
            p = a[i];
            q = b[i];
            break;
        }
    }
    int va = 0, vb = 0;
    for (int i = 0; i < m; i++)
    {
        if (a[i] == x || b[i] == x || a[i] == p || b[i] == p)
            va++;
        if (a[i] == x || b[i] == x || a[i] == q || b[i] == q)
            vb++;
    }
    if (va == m || vb == m)
        return true;
    else
        return false;
}

void solve()
{

    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        cin >> a[i] >> b[i];
    }
    if (check(a[0]) || check(b[0]))
        puts("YES");
    else
        puts("NO");
}
int main()
{
    // clock_t st = clock(), ed;
    ios::sync_with_stdio(0);
    cin.tie(0);
    // cout << setprecision(15) << fixed;

    solve();

    // ed = clock();
    // double endtime = (double)(ed - st) / CLOCKS_PER_SEC;
    // cout << "Total time: " << endtime << endl;
    return 0;
}

1457. 二叉树中的伪回文路径 - 力扣（LeetCode）

朴素1

主要问题在于判断叶子结点 直接写root is None： 可能会出现 某结点只有一个孩子 也进入判断的情况 （这肯定不是叶子）

所以要改成左右都为空才是叶子 相应的 cnt计数的操作也需要变化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def pseudoPalindromicPaths (self, root: Optional[TreeNode]) -> int:
        res = 0
        cnt = [0] * 11
        def dfs(root):
            nonlocal res, cnt
            
            if root.left is None and root.right is None:
                cnt[root.val] += 1
                odd = 0
                for i in range(10):
                    print(cnt[i],end='')
                    if cnt[i] % 2:
                        odd += 1
                print()
                if odd <= 1:
                    res += 1
                cnt[root.val] -= 1
                return
            cnt[root.val] += 1
            if root.left:
                dfs(root.left)
            if root.right:
                dfs(root.right)
            cnt[root.val] -= 1

        dfs(root)
        return res

朴素2

这个是 res作为返回值的 要注意 res 什么时候是直接return 什么时候是res += 什么时候是 res =

然后是这个 用了一个 root is None 判空 空 就不用加

再用一个 if root.left is root.right 判叶子 是叶子就看能不能加1 不是叶子就继续递归 注意不是return

还有 不需要记录cnt 的值 然后去数 只需要记录cnt 的奇偶就可以了 （由此导出位运算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# Definition for 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 pseudoPalindromicPaths (self, root: Optional[TreeNode]) -> int:
        cnt = [0] * 10
        def dfs(root):
            
            if root is None:
                return 0

            cnt[root.val] ^= 1

            if root.left is root.right:
                res = 1 if sum(cnt) <= 1 else 0
            else:
                res = dfs(root.left) + dfs(root.right)
             
            cnt[root.val] ^= 1
            return res

        return dfs(root)

位运算

既然只需要看每一位的奇偶 那也不用数组了 直接用一个数 的每一位 来异或就可以

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# 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 pseudoPalindromicPaths (self, root: Optional[TreeNode]) -> int:
        mask = 0
        def dfs(root):
            nonlocal mask
            if root is None:
                return 0

            mask ^= 1 << root.val

            if root.left is root.right:
                res = 1 if mask & (mask - 1) == 0 else 0
            else:
                res = dfs(root.left) + dfs(root.right)

            mask ^= 1 << root.val             
            return res

        return dfs(root)

1038. 从二叉搜索树到更大和树 - 力扣（LeetCode）

从右往左遍历 可以达到一次遍历的效果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 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:
    su = 0
    def bstToGst(self, root: TreeNode) -> TreeNode:
        if root is None:
            return
        self.bstToGst(root.right)
        self.su += root.val
        root.val = self.su
        self.bstToGst(root.left)
        return root

0最少刷题数 - 蓝桥云课 (lanqiao.cn)

求中间的数 因为有重复数字 就需要用计数的方法 遍历 而不能用数学方法

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
#include <iostream>
#include <algorithm>
using namespace std;
int nums[100010];
int ret[100010];
int main()
{
  // 请在此输入您的代码
    int n;
    cin>>n;
    for (int i = 1; i <= n; i++)
    {
        cin>>nums[i];
        ret[i] = nums[i];
    }
    sort(nums + 1, nums + n + 1);
    int ans = -1;
    int j = 0;
    for(int i = 1; i <= n && ans == -1; )
    {
        j = i++;
        while (i <= n && nums[i] == nums[i - 1])i++;
        int l = j - 1, r = n - i + 1;
        // cout<<l<<" "<<r<< " "<<nums[j]<<endl;
        if (l > r)ans = nums[j];
        else if (l < r)continue;
        else ans = nums[j] + 1;
    }
    // cout<<ans<<endl;
    for (int i = 1; i <= n; i++)
    {
        int x = 0;
        if (ret[i] < nums[j])x = ans - ret[i];
        cout<< x <<" ";
    }
    
  return 0;
}


0矩形拼接 - 蓝桥云课 (lanqiao.cn)

枚举 先选3个矩形的顺序 再选每个矩形的边的顺序

枚举就是要达到 每个图形的每条边 都可以直接表示出来 比如a[i] [ii] 这样 而且比如第二个if （if (a[i] [ii] == a[j] [jj] + a[k] [kk])）这里只用写一个 而**不需要写a[j] [jj] = a[i] [ii] + a[k] [kk] ** 因为循环会枚举到

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
#include <iostream>
using namespace std;

void solve()
{
    int a[3][2];
    for (int i = 0; i < 3; i++)
    for (int j = 0; j < 2; j++)
    cin>>a[i][j];

    int ans = 8;
    for (int i = 0; i < 3; i++)
    for (int j = 0; j < 3; j++)
    if (i != j)
    for (int k = 0; k < 3; k++)
    if (i != k && j != k)
    for (int ii = 0; ii < 2; ii++)
    for (int jj = 0; jj < 2; jj++)
    for (int kk = 0; kk < 2; kk++)
    {
        if (a[i][ii] == a[j][jj] || a[i][ii] == a[k][kk])
        {
            ans = min(ans, 6);
            if (a[j][jj] == a[k][kk])
            ans = min(ans, 4);
        }
        if (a[i][ii] == a[j][jj] + a[k][kk])
        {
            ans = min(ans, 6);
            if (a[j][1 - jj] == a[k][1 - kk])
            ans = min(ans, 4);
        }
    }
    cout<<ans<<endl;


}
int main()
{
    int T;
    cin>>T;
    while(T--)
    solve();
    return 0;
}

1405. 最长快乐字符串 - 力扣（LeetCode）

思路很好想 就是先放多的 再放少的 但是具体的实现比较困难

由于只有三个数 不用优先队列 可以直接用排序

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
typedef pair<int, char> PII;
class Solution {
public:
    string longestDiverseString(int a, int b, int c) 
    {
        string ans = "";
        vector<PII>arr = {{a, 'a'}, {b, 'b'}, {c, 'c'}};
        
        while (true)
        {
            sort(arr.begin(), arr.end(), [&](PII a, PII b){a.first > b.first;});
            bool hasNext = false;
            for (auto &[n, c]: arr)
            {
                int len = ans.size();
                if (len > 2 && ans[len - 1] == c && ans[len - 2] == c)
                    continue;
                hasNext = true;
                ans += c;
                n--;
                break;
            }
            if(!hasNext)
                break;
        }
        return a
    }
};
algorithm
#Ans
每日一题题解
https://brtulien.github.io/2023/08/26/每日一题题解/
作者
Brtulien
发布于
2023年8月26日
更新于
2024年7月1日
许可协议