topic：

1233. Delete the subfolder folder

Thought：

脑子里的构思yesDictionary tree，ButClanguage的Dictionary tree，Whether it isPython
still golangI won’t write。 So helpless can only look at the answer。
ylbThe big guy is right firstlistSort，Then traverse the list。

1.ifiBefore[len(ans[-1])]Just happensans[-1]The element is consistent，Explainiyes
ans[-1]Subfolder folder，Then skip。

2.ifyes["/a/b/c","/a/b/ca","/a/b/d"]This situation，Be alone1.的判断yes不够的，at this time
"/a/b/ca"Before缀and"/a/b/c"yes一样的，但yescaandc实际上yes两个不同的文件夹，So add a judgment front end
yes否yes/，"/a/b/ca"and"/a/b/c/a"中后者才会被判定yes前面一个元素的子集。

Dictionary tree没太看懂:
我们可以使用Dictionary tree存储数组 folder All folders in。
Dictionary tree的每个节点包含 children Field，Sub -nodes for storing the current nodes，as well as fid Field，
Used to store the folder corresponding to the current node in the array folder Bidding。

For array folder Each folder in it f，We will first f according to / Divide into several skewers，
Then start from the root node，依次将子串加入Dictionary tree中。Next，我们从根节点开始搜索Dictionary tree，
if当前节点的 fid Field不为 -1，则说明当前节点对应的文件夹yes答案数组中的一个文件夹，
We add it to the array and return。otherwise，We search for all sub -nodes of the current node，Finally return to the array of answers。

Code：

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:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        folder.sort()
        ans = [folder[0]]
        for i in folder[1:]:
            m, n = len(ans[-1]), len(i)
            # if它的长度大于等于答案数组中最后一个文件夹的长度，并且它Before缀包含答案数组的最后一个文件夹再加上一个 /
            if m >= n or not (ans[-1] == i[:m] and i[m] == '/'):
                ans.append(i)
        return ans
# Dictionary tree
class Trie:
    def __init__(self):
        self.children = {}
        self.fid = -1

    def insert(self, i, f):
        node = self
        ps = f.split('/')
        for p in ps[1:]:
            if p not in node.children:
                node.children[p] = Trie()
            node = node.children[p]
        node.fid = 1

    def search(self):
        def dfs(root):
            if root.fid != -1:
                ans.append(root.fid)
                return
            for child in root.children.values():
                dfs(child)
        ans = []
        dfs(self)
        return ans
    
    
class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        trie = Trie()
        for i, f in enumerate(folder):
            trie.insert(i, f)
        return [folder[i] for i in trie.search()]

1
2
3
4
5
6
7
8
9
10
11

func removeSubfolders(folder []string) (ans []string) {
	sort.Strings(folder)
	ans = []string{folder[0]}
	for _, i := range folder[1:] {
		m, n := len(ans[len(ans)-1]), len(i)
		if m >= n || !(ans[len(ans)-1] == i[:m] && i[m] == '/'){
			ans = append(ans, i)
		}
	}
	return 
}

topic：

1250. examine「Good array」.md

Thought：

1. @PT, PT_ZhenSolution of classmates，Next is his solution：
   If there is no big convention,，Then there must be one time。
   If two numbers can be made up directly1if，Then other numbers can also be added and subtracted by addition and subtraction1get1.The major convention in a set depends on the largest number of the smallest between the two in this set

   [10000, 3, 4], 10000 + 9999 * (3 - 4) = 1

2. @ylb, Pei Shu theorem:We can first consider choosing two numbers，If the selected number is aaa and bbb，So根据topic的要求，We need to be satisfied a×x+b×y=1a \times x + b \times y = 1a×x+b×y=1，in xxx and yyy Any integer。

根据Pei Shu theorem，Can be known，if a and b Mutual quality，Then there must be solution。In fact，Pei Shu theorem也可以推广到多个数的情况，即if a1,a2,⋯,ai
Mutual quality，So a1×x1+a2×x2+⋯+ai×xi=1There must be solution，in x1,x2,⋯,xi Any integer。

Code：

1
2
3

class Solution:
    def isGoodArray(self, nums: List[int]) -> bool:
        return True if math.gcd(*nums) == 1 else False

1
2
3

class Solution:
    def isGoodArray(self, nums: List[int]) -> bool:
        return reduce(gcd, nums) == 1

topic：

1237. Find out the positive combination of the given square.md

Thought：

Want to be complicated，It turned out to be intended to recover，Then constantly find out the solution。Then Ling Shen tells us：In fact, this question is a double pointer，One on the far left is on the right。
Monoly increase function，XCan only increase，YCan only reduce，So iff(x,y)<z，ExplainXIt’s time to increase，vice versa。

Because you need to continue to find after equal，So continue f(x,y)<zTalent operation，After modificationf(x+1,y)>f(x,y)=z，Depending on the circumstances 2，Can y minus one。

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution:
    def findSolution(self, customfunction: 'CustomFunction', z: int) -> List[List[int]]:
        ans = []
        x, y = 1, 1000
        while x <= 1000 and y:
            res = customfunction.f(x, y)
            if res < z:
                x += 1
            elif res > z:
                y -= 1
            else:
                ans.append([x, y])
                x += 1
                y -= 1
        return ans

1

142.Ring listII.md

Thought：

Problem -solving：

这类Linkedtopic一般都yes使用双pointer法解决的，For example, looking for distance tail K Node、Find a ring entrance、Find the entrance of the public tail, etc.。

Algorithm：

1. Double pointer met for the first time： Set two pointers fast，slow 指向Linked头部 head，fast Walk per round 2 step，slow Walk per round 1 step；

   a. First result： fast pointer走过Linked末端，说明Linked无环，直接return null；

   .TIPS: If there is a ring，Two pointers will definitely meet。Because every time I go 1 wheel，fast and slow Pitch +1，fast The event will catch up slow；
   b. Second result： whenfast == slowhour， Two pointers in the ring First encounter 。下面分析此hourfast and slowPassing step数关系 ：

   .设Linked共have a+b Node，in Linked头部到Linked入口 have a Node（不计Linked入口节点）， Linked环 have b Node（这里需要Notice，a and b yes未知数，例如图解上Linked a=4 , b=5）；Set two pointers分别走了 f，s step，则have：
   a. fast 走的step数yesslowstep数的 2 Double，Right now f=2s；（Analyze： fast Walk per round 2 step）
   b.fast Compare slowGo more n Length of a ring，Right now f=s+nb；（ Analyze： Double pointers have gone through a step，然后在环Inside绕圈直到重合，重合hour fast Compare slow Go 环的长度整数Double ）；
   .The above two types are reduced：f=2nb，s=nb，Right nowfastandslow The pointer left separately 2n，n indivual Circumference of the ring （Notice： n yes未知数，不同Linked的情况不同）。

Thought：

It is the second question of the weekly match：6275Make all the minimum operations of all elements in the arrayII.md
The first edition of the heart of the heart。It’s completely different from the second edition，Originally wanted to practice the greedy algorithm。但是做着做着就发现了存在math规律。
Quote[yong]Big guy’s words：
Because it is the difference between the difference,很可能找到一个math公式,useO(1)Time complexity solution. Get a few simple examples first to find the rules

1. n=3 The minimum operation is 2
2. n=4 The minimum operation is 1 + 3
3. n=5 The minimum operation is 2 + 4
4. n=6 The minimum operation is 1 + 3 + 5
5. n=7 The minimum operation is 2 + 4 + 6
   whennWhen the number is,The minimum operation is1 + 3 + 5 + ... + n-1 = n*n/4
   whennWhen it is a strange number,The minimum operation is2 + 4 + ... + n-1 = (n*n - 1) / 4

Get this question,Feel a bit around,Careful analysis discovery arr[i] = (2 * i) + 1 (0 <= i < n)Is a typical equal number list(1,3,5,7,9...).
According to the formula of the equal number column,It’s easy to find a grouparrThe total element isn^2. In the question design, two bids are selected for each operationx ymakearr[x]minus onearr[y]plus one.
in other words,No matter how you choosex y,No matter how many times the operation,The sum of the array will not change. The design and guarantee that all elements in the array can ultimately be equal equal.
Then we assume that the final element is equal toaSon*a == n^2,soa == n,That is to say, the final array elements are alln.actuallynIs the average value of the array.
Know the end element is allnback,Start traversing in the middle by starting from the start and end of the array,You can reach the smallest number of operations.
Suppose the bidding on the left isi ((2 * i) + 1 < n)So相应右边的下标是n - i.
The corresponding two elemental values ​​andnThe difference isn - 1 + 2 * i.so我们只要计算数组中值小于nElements andnSummary of difference,Get the minimum operation number.

Code：

1
2
3
4

 int minOperations(int n) {
     return n * n / 4;
}
// Time and space complexity is all O(1)

1
2
3
4
5
6
7
8

 int minOperations(int n) {
    int operation = 0;
    for(int i = 1; i < n ; i += 2) {
        operation += (n - i);
    }
    return operation;
}
// Time complexity isO(n) Space complexity isO(1)

1
2
3
4
5
6

class Solution:
    def minOperations(self, n: int) -> int:
        operate = 0
        for i in range(1, n, 2):
            operate += (n - i)
        return operate

1
2
3

-spec min_operations(N :: integer()) -> integer().
min_operations(N) ->
N * N div 4.

1
2
3
4
5

class Solution {
  int minOperations(int n) {
    return n * n ~/ 4;
  }
}

1
2
3
4
5
6

defmodule Solution do
  @spec min_operations(n :: integer) :: integer
  def min_operations(n) do
        div(n * n , 4)
  end
end

topic

Thought：

Pay attention to the data pre -processing of this time question，You can convert time to minutes，You can look at the notes in the code。Thought andylbThe consistency of the big man。
Pay attention to，In fact, use the order directlysortIt’s okay。
python: :=Walrus operator，Can be assigned in judgment
Golang: SScanfSscanfStringstrScanning text，according toformat The format specified by the parameter will save the values ​​of the blank separation that is successfully read in the parameters that successfully passed to the function of this function。
Back to the number of entries for successful scanning and any error encountered。

Code：

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 alertNames(self, keyName: List[str], keyTime: List[str]) -> List[str]:
        ans = set()
        dict1 = defaultdict(list)
        for name, time in zip(keyName, keyTime):
            dict1[name].append(int(time[:2])*60+int(time[3:]))
        print(dict1)
        for i in dict1:
            # definition10：00-11：00Three counts appear，Warn
            if len(dict1[i]) >= 3:
                dict1[i].sort()
                print(dict1[i])
                for j in range(len(dict1[i])):
                    # Traversing the current hour to one hour,It seems to be able to watch the slice directly
                    # for k in range(len(dict1[i]) + 1, len(dict1[i])+3):
                    if j + 2 < len(dict1[i]):
                        # if dict1[i][j:j + 3][0].replace(":", "")[:2]
                        if abs(dict1[i][j:j + 3][-1] -
                            dict1[i][j:j + 3][0]) <= 60:
                            ans.add(i)
                        print(dict1[i][j:j + 3])
        ans = list(ans)
        ans.sort()
        return ans

topic：

1653. The minimum number of times to balance the string balance.md

Thought：

ask：Why if-else Write (c - ‘a’) * 2 - 1 It will be much faster？

answer：CPU I encounter a branch（Condition jump instruction）Which branch of the code will be predicted when the code is executed，If the prediction is correct，
CPU It will continue to execute the program in accordance with the predicted path。But if the prediction fails，CPU You need to roll back the previous instructions and load the correct instructions，To ensure the correctness of the program execution。

For the data of this question，character ‘a’ and ‘b’ It can be considered to appear random，In this case, the branch prediction will be available 50% Probability failure。
失败导致的回滚and加载操作需要消耗额外的 CPU cycle，If the branch can be removed at a smaller price，The situation of this question can inevitably bring efficiency improvement。

Notice：This optimization method often reduces readability，It’s best not to use in business code。

Code：

1
2
3
4
5
6
7
8
9

class Solution:
    def minimumDeletions(self, s: str) -> int:
        ans = delete = s.count('a')
        for c in s:
            delete -= 1 if c == 'a' else -1
            if delete < ans:  # Manually min It will be much faster
                ans = delete
        return ans

topic：

1590.Make the array and energyPDivide.md

Thought：

‘≡’Together
For example nums=[11,2,5,7,8,9]，p=10，So [5,7] Remove，The remaining numbers add 30，Be able to p Divide。
All elements and $42mod10 = 2$
设All elements andx，RemoveElementsand为y，Makex-y Be able topDivide,satisfy

y≡x(mod p)->x % p = y % p

By prefix and，The problem converts：Find two numbers on the prefix and array s[left] and s[right]，satisfy right−left Minimum

$$
s[right] - s[left] ≡ x (mod p)
->s[right] - x ≡ s[left] (mod p)
$$

((s[right]-x)modp+p) mod p = s[left] mod p

Traversal sss At the same time，Hash table last\textit{last}last Record s[i]mod p The last time the bidding appeared，if lastlast Contain
(s[i] mod p−x mod p+p) mod p，Let’s set its corresponding setting j，So [j,i) Is a符合topic要求的子数组。

Enumerate i，Calculate the minimum value of the child array length that meets the requirements，Is the answer。if没有符合要求的子数组，Then return −1。

Code implementation，You can initialize the answer to nums length n。if最后答案等于 n，It means that there are no sub -array that does not meet the requirements，因为topic不允许将整个数组都移除。

lastIs amap，The key is an integer，Value is an integer。j, ok := last[(v-x+p)%p]This line code is inlastThe search key is(v-x+p)%pElements，And give its value to variablesj。if这个键不存在，SookThe value will befalse，otherwiseokThe value will betrue。
The return value of this grammar is two values，The first value is the value corresponding to the key，第二个值Is a布尔值，Indicates whether the key exists。
ifokThe value istrue，SoCode中的ifThe statement will be executed，It willansThe value update isi-jandansMinimum value。ifokThe value isfalse，SoifThe statement will be skipped，The program will continue to execute。

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        s = list(accumulate(nums, initial=0))
        x = s[-1] % p
        if x == 0: return 0  # Remove the air array（This line can not be）

        ans = n = len(nums)
        last = {}
        for i, v in enumerate(s):
            last[v % p] = i
            j = last.get((v - x) % p, -n)  # if不存在，-n Be guaranteed i-j >= n
            ans = min(ans, i - j)
        return ans if ans < n else -1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

package main

func minSubarray(nums []int, p int) int {
	n := len(nums)
	s := make([]int, n+1)
	for i, v := range nums {
		s[i+1] = (s[i] + v) % p
	}
	x := s[n]
	if x == 0 {
		return 0
	}

	ans := n
	last := map[int]int{}
	for i, v := range s {
		last[v] = i
		if j, ok := last[(v-x+p)%p]; ok {
			ans = min(ans, i-j)
		}
	}
	if ans < n {
		return ans
	}
	return -1
}

func min(a, b int) int {
	if b < a {
		return b
	}
	return a
}

1663. The smallest string with a given value

Thought：

今天的One question daily读题可以得知：Actually I want to ask for：
27 How to disassemble 3 Number 1 + 1 + 25
73 How to disassemble 5 Number 1 + 1 + 19 + 26 + 26
nIs the number of string we are going to return，So we put itaAs1，Createnindivual1list of[1]*n
贪心Thought
First time：从第一Number开始加，Add to26。Determine whether it is with each timekequal，Timeout。
Second attempt：Turn all the numbers passed directly into26，Turn all the numbers passed directly into26，kEvery time-25，最后将Remaining数字Add to我们遍历到的位置
，Last+Remainingk。
The optimal solution is not usedlambdaThe function converts the number into a string，Instead‘a’Become up to become‘z’。Save a lot of time。

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution:
    def getSmallestString(self, n: int, k: int) -> str:
        def find(list_ans):
            for i in range(n):
                while list_ans[i] < 26:
                    if sum(list_ans) == k:
                        return list_ans
                    list_ans[i] += 1
            return list_ans

        list1 = [1] * n
        list1 = ''.join(list(map(lambda x: chr(x), map(lambda x: x + 96, find(list1)))))[::-1]
        return list1

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution:
    def getSmallestString(self, n: int, k: int) -> str:
        index = n - 1
        list1 = [1] * n
        k -= n
        while k > 25:
            list1[index] += 25
            k -= 25
            index -= 1
        # How much is left？
        print(k)
        list1[index] += k
        return ''.join(list(map(lambda x: chr(x), map(lambda x: x + 96, list1))))

1
2
3
4
5
6
7
8
9
10

class Solution:
    def getSmallestString(self, n: int, k: int) -> str:
        ans = ['a'] * n
        i, d = n - 1, k - n
        while d > 25:
            ans[i] = 'z'
            d -= 25
            i -= 1
        ans[i] = chr(ord(ans[i]) + d)
        return ''.join(ans)

1664. Number of schemes to generate balance numbers

Thought：

See when you read the question medium I know that it is definitely not really going to delete an element。Otherwise it will time out，So I tried to try polepythonFeature code：Use slice to process all data；
But it’s timeout。。

然后看官方answer，用的Dynamic planning。中心Thought是：

General nature，Now we will settle down i Delete elements，
Obviously the bidding i The previous element bidding will not change from this，Bidding i
The original was originally j，j>iThe array elements of the bid will move to the bidding j−1，
Immediately bidding i The subsequent bidding elements will become the rated element，
The even bidding element will become a strange number of bidding elements。

Code

1
2
3
4
5
6
7
8

class Solution:
    def waysToMakeFair(self, nums: List[int]) -> int:
        flag = 0
        for i in range(len(nums)):
            temp_nums = nums[:i] + nums[i+1:]
            if sum(temp_nums[::2])==sum(temp_nums[1::2]):
                flag += 1
        return flag

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
    def waysToMakeFair(self, nums: List[int]) -> int:
        res = odd1 = even1 = odd2 = even2 = 0
        for i, num in enumerate(nums):
            if i & 1:
                odd2 += num
            else:
                even2 += num
        for i, num in enumerate(nums):
            if i & 1:
                odd2 -= num
            else:
                even2 -= num
            if odd1 + even2 == odd2 + even1:
                res += 1
            if i & 1:
                odd1 += num
            else:
                even1 += num
        return res