Posted on | In |

你是一位系统管理员，手里有一份文件夹列表 folder，你的任务是要删除该列表中的所有 子文件夹，并以 任意顺序 返回剩下的文件夹。
如果文件夹 folder[i] 位于另一个文件夹 folder[j] 下，那么 folder[i] 就是 folder[j] 的 子文件夹 。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/remove-sub-folders-from-the-filesystem
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

在官解中这道题有两种解法，一种是基于排序的方法，一种是基于字典树的方法。基于排序的方法就是将所有输入的path进行排序然后再进行相应处理，稍微研究了一下没通过，也觉得不是“正经”解法，这道题应该是可以应用数据结构的，然后看到了方法二，基于字典树的方法。

输入的每条路径中，可以将每一层文件夹当做一个节点，添加一个向量ref，如果节点是输入中的一个路径，则ref为该路径在输入中的索引。将所有路径都保存在字典树中后，对第一层的各节点进行一次深度遍历，只要遇到ref不为-1的节点则将路径添加至答案中，因为后续的都是该节点的子文件夹。
这里仍然还有一个疑点，在dfs函数中的return的写法，没太看懂。

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 Trie:
    def __init__(self):
        self.children = dict()
        self.ref = -1
class Solution(object):
    def removeSubfolders(self, folder):
        """
        :type folder: List[str]
        :rtype: List[str]
        """
        for fold in folder:
            print(fold.split("/")[1:])
        root = Trie()
        for i,fold in enumerate(folder):
            fold = fold.split("/")
            cur = root
            for name in fold:
                if name not in cur.children:
                    cur.children[name] = Trie()
                cur = cur.children[name]
            cur.ref = i
        ans = list()
        def dfs(cur):
            if cur.ref != -1:
                ans.append(folder[cur.ref])
                return
            for child in cur.children.values():
                    dfs(child)
        dfs(root)
        return ans

Posted on | In |

你需要设计一个包含验证码的验证系统。每一次验证中，用户会收到一个新的验证码，这个验证码在 currentTime 时刻之后 timeToLive 秒过期。如果验证码被更新了，那么它会在 currentTime （可能与之前的 currentTime 不同）时刻延长 timeToLive 秒。
请你实现 AuthenticationManager 类：
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/design-authentication-manager
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

莫名其妙的一道题，题干描述莫名其妙，通过的也莫名其妙，没啥营养，也不知道有啥优化方法。

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 AuthenticationManager(object):

    def __init__(self, timeToLive):
        """
        :type timeToLive: int
        """
        self.timeToLive = timeToLive
        self.token_limit = dict()

    def generate(self, tokenId, currentTime):
        """
        :type tokenId: str
        :type currentTime: int
        :rtype: None
        """
        self.token_limit[tokenId] = currentTime + self.timeToLive

    def renew(self, tokenId, currentTime):
        """
        :type tokenId: str
        :type currentTime: int
        :rtype: None
        """
        if tokenId in self.token_limit:
            if currentTime < self.token_limit[tokenId]:
                self.token_limit[tokenId] = currentTime + self.timeToLive

    def countUnexpiredTokens(self, currentTime):
        """
        :type currentTime: int
        :rtype: int
        """
        count = 0
        for k,v in self.token_limit.items():
            if currentTime < v:
                count += 1
        return count 
# Your AuthenticationManager object will be instantiated and called as such:
# obj = AuthenticationManager(timeToLive)
# obj.generate(tokenId,currentTime)
# obj.renew(tokenId,currentTime)
# param_3 = obj.countUnexpiredTokens(currentTime)

Posted on | In |

给你一个长度为 n 的整数数组 nums ，和一个长度为 m 的整数数组 queries 。
返回一个长度为 m 的数组 answer ，其中 answer[i] 是 nums 中 元素之和小于等于 queries[i] 的 子序列 的 最大 长度 。
子序列 是由一个数组删除某些元素（也可以不删除）但不改变剩余元素顺序得到的一个数组。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/longest-subsequence-with-limited-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
这道题拿过来第一眼就觉得nums可以排序，然后又仔细看了看题目说不能影响顺序，就放弃了排序的想法，经过评论区提醒才发现，加法条件，排序不排序对元素顺序哪有什么影响。。又是被忽悠的一天。。。
可以排序就省事很多了，首先想到的就是循环解决，然后觉得递归也能解决，然后还觉得quries那里应该也可以做一些手脚。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def answerQueries(self, nums, queries):
        """
        :type nums: List[int]
        :type queries: List[int]
        :rtype: List[int]
        """
        nums.sort()
        answer = list()
        for i in range(len(queries)):
            res = 0
            count = 0
            for item in nums:
                res += item
                if res <= queries[i]:
                    count += 1
                # else:
            answer.append(count) 
        return answer

然后想办法写成递归，好像写不成递归啊，递归的出口是已知的，这里是未知的，所以应该写不成递归？？quries想了想好像也没什么动手脚的余地，折腾来折腾去每次遍历的次数也不会改变。
然后在官解中看到了“前缀和”的概念。

Posted on | In |

返回所有长度为 n 且满足其每两个连续位上的数字之间的差的绝对值为 k 的 非负整数 。
请注意，除了 数字 0 本身之外，答案中的每个数字都 不能 有前导零。例如，01 有一个前导零，所以是无效的；但 0 是有效的。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/numbers-with-same-consecutive-differences
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

时常有这种想法，就是为什么在学编程的时候要学“循环”这种东西，超时了。。。

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(object):
    def numsSameConsecDiff(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: List[int]
        """
        mini_num,max_num = 10**(n-1),10**n
        def seperate(num,k):
            num = [item for item in str(num)]
            flag = True
            for i in range(1,len(num)):
                if abs(int(num[i]) - int(num[i-1])) != k:
                    flag = False
            if flag:
                return int("".join(num))
            else:
                return None
        result = list()
        for i in range(mini_num,max_num):
            res = seperate(i,k)
            if res:
                result.append(res)
        return result

然后看到了这个题解:

找到了类似思路的代码，但是没看懂

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def numsSameConsecDiff(self, N, K):
        """
        :type N: int
        :type K: int
        :rtype: List[int]
        """
        if N == 1:
            return list(range(10))
        
        res = list(range(1, 10))
        for _ in range(1, N):
            tmp_res = list()
            for num in res:
                num_s = num % 10
                for i in {num_s - K, num_s + K}:
                    if 0 <= i <= 9:
                        tmp_res.append(num * 10 + i)
            res = tmp_res
        return res

Posted on | In |

现有一台饮水机，可以制备冷水、温水和热水。每秒钟，可以装满 2 杯 不同 类型的水或者 1 杯任意类型的水。
给你一个下标从 0 开始、长度为 3 的整数数组 amount ，其中 amount[0]、amount[1] 和 amount[2] 分别表示需要装满冷水、温水和热水的杯子数量。返回装满所有杯子所需的 最少 秒数。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/minimum-amount-of-time-to-fill-cups
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

评论区都是数学解，我就想用程序解，然后被一道简单题干服了。

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
class Solution(object):
    def fillCups(self, amount):
        """
        :type amount: List[int]
        :rtype: int
        """
        sequence = deque()
        mapping = {0:"Cold",1:"Normal",2:"Hot"}
        #每次将amount中的最大值和最小值对应的饮品加入队列
        while amount[0] or amount[1] or amount[2]:
            index_max = amount.index(max(amount))
            sequence.appendleft(mapping[index_max])
            amount[index_max] -= 1
            #杯数相同时直接使用index会报错，所以需要带着索引排序，就可以直接使用最小值的索引
            temp = [(amount[i],i) for i in range(len(amount)) if amount[i] > 0 and i != index_max]
            temp.sort()
            if temp:
                index_min = temp[-1][-1]
                if index_max != index_min:
                    sequence.appendleft(mapping[index_min])
                    amount[index_min] -= 1
        cost = 0
        #每次从队列中pop两个值出来，不同cost + 1，相同cost + 2，有空值或均为空时退出循环
        while True:
            try:
                type1 = sequence.pop()
            except:
                type1 = None
            try:
                type2 = sequence.pop()
            except:
                type2 = None
            if type1 and type2:
                if type1 != type2:
                    cost += 1
                else:
                    cost += 2
            elif type1 or type2:
                cost += 1
                break
            else:
                break
        return cost

Posted on | In |

我们从一块字母板上的位置 (0, 0) 出发，该坐标对应的字符为 board[0][0]。
在本题里，字母板为board = [“abcde”, “fghij”, “klmno”, “pqrst”, “uvwxy”, “z”]，如下所示。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/alphabet-board-path
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

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(object):
    def alphabetBoardPath(self, target):
        """
        :type target: str
        :rtype: str
        """
        operation = list()
        current_location = [0,0]
        for tar in target:
            row = (ord(tar) - 97) / 5
            col = (ord(tar) - 97) % 5
            row_moving = row - current_location[0]
            col_moving = col - current_location[1]
            if current_location[0] == 5 and row_moving !=0 and col_moving != 0:
                operation += "U"
                current_location[0] -= 1
                row_moving += 1
            if col_moving > 0:
                operation += ["R"] * col_moving
                current_location[1] += col_moving
            if col_moving < 0:
                operation += ["L"] * abs(col_moving)
                current_location[1] += col_moving
            if row_moving > 0:
                operation += ["D"] * row_moving
                current_location[0] += row_moving
            if row_moving < 0:
                operation += ["U"] * abs(row_moving)
                current_location[0] += row_moving
            operation += ["!"]
            print(operation,row_moving,col_moving)
        return "".join(operation)

Posted on | In |

给你一个 非负 整数 num 。如果存在某个 非负 整数 k 满足 k + reverse(k) = num ，则返回 true ；否则，返回 false 。
reverse(k) 表示 k 反转每个数位后得到的数字。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/sum-of-number-and-its-reverse
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def sumOfNumberAndReverse(self, num):
        """
        :type num: int
        :rtype: bool
        """
        if num == 0:
            return True
        flag = False
        for i in range(0,num,-1):
            rev = int("".join(reversed(str(i))))
            if i + rev == num:
                flag = True
                break
        return flag

Posted on | In |

在1250-检查「好数组」中接触到该定理。
对于任何整数a、b和它们的的最大公约数d。在关于未知数x和y的线性不定方程中，若a，b是整数，且gcd(a,b)=d，那么对于任意的整数x,y,ax+by都一定是d的倍数，特别地，一定存在整数x,y使得ax+by=d成立。

Posted on | In |

什么是前缀和（2389）
前缀和指一个数组的某下标之前的所有数组元素的和（包含其自身）。前缀和分为一维前缀和，以及二维前缀和。前缀和是一种重要的预处理，能够降低算法的时间复杂度。
什么是一维前缀和？
一维前缀和的公式：sum[i] = sum[i-1] + arr[i] ; sum是前缀和数组, arr是内容数组。拥有前缀和数组后, 我们可以在O(1)的时间复杂度内求出区间和。
[i, j]的区间和公式: interval [i, j] = sum[j] - sum[i - 1]
作者：dyhtps
链接：https://juejin.cn/post/6944913393627168798
来源：稀土掘金
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

Posted on | In |

给你一份工作时间表 hours，上面记录着某一位员工每天的工作小时数。
我们认为当员工一天中的工作小时数大于 8 小时的时候，那么这一天就是「劳累的一天」。
所谓「表现良好的时间段」，意味在这段时间内，「劳累的天数」是严格 大于「不劳累的天数」。
请你返回「表现良好时间段」的最大长度。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/longest-well-performing-interval
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
对前缀和的理解还是很模糊。

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(object):
    def longestWPI(self, hours):
        """
        :type hours: List[int]
        :rtype: int
        """
        n = len(hours)
        score = [1 if item > 8 else -1 for item in hours ]

        presum = [0] * ( n + 1 )
        for i in range(1, n+1):
            presum[i] = presum[i-1] + score[i-1]

        index_record = list()
        for i in range(len(presum)):
            if len(index_record) == 0 or presum[i] < presum[index_record[-1]]:
                index_record.append(i)
        result = 0
        for i in range(len(presum) -1 ,-1,-1):
            while len(index_record) and presum[i] - presum[index_record[-1]] > 0 :
                result = max(i - index_record[-1] , result)
                index_record.pop()
        return result