topic：

2679.In the matrix and the harmony.md

Thought：

One -line
First of all, the meaning is to find the largest number of each sub -list，Thenpopgo out，Finally ask for peace。
The effect of traversing again and again is too bad，So I thought of using itzip一次性Traversal多个子Array。
于yes先对每个子ArraySort，Then usezipTraversal，Find the maximum。
for example：
nums = [[7,2,1],[6,4,2],[6,5,3],[3,2,1]]
Sort后：
nums = [[1,2,7],[2,4,6],[3,5,6],[1,2,3]]
Then usezipTraversal得到：
[(1,2,3,1),(2,4,5,2),(7,6,6,3)]
Find the maximum：
[3,5,7]
Context：
15

Code：

1
2
3
4

class Solution:
    def matrixSum(self, nums: List[List[int]]) -> int:
        return sum(max(i) for i in \
        zip(*(sorted(sublist) for sublist in nums)))

*The role and the rolezip()explain

1
2
3
4
5
6
7
8
9
10

nums = [[1,2,7],[2,4,6],[3,5,6],[1,2,3]]

for i in range(len(nums[1])):
    for j in range(len(nums)):
        print(nums[j][i])
# ans = 123124527663
num1 = [1,2,7]
num2 = [2,4,6]
num3 = [3,5,6]
num4 = [1,2,3]

zip()The function corresponds to one -to -one elements in multiple lists，Then return onezipObject，Can uselist()Function convert to list。

1
2
3
4
5

for i in zip(num1, num2, num3, num4):
    print(i)
#(1, 2, 3, 1)
#(2, 4, 5, 2)
#(7, 6, 6, 3)

*numsThe role ispythonNot a pointer，InsteadnumsEach element in the parameter is passed into the function。I understand here as a list。

1
2
3
4

# Enumerate
print(*nums)
# [1, 2, 7] [2, 4, 6] [3, 5, 6] [1, 2, 3]

zip(*nums)WillnumsEach element is passed in as a parameterzip()In the function，Then return onezipObject，Can uselist()Function convert to list。
zip(*nums)Equivalent tozip(num1, num2, num3, num4)，innum1, num2, num3, num4yesnumsElement。

1
2
3
4
5
6

for i in zip(*nums):
    print(i)
# Equivalent
#(1, 2, 3, 1)
#(2, 4, 5, 2)
#(7, 6, 6, 3)

Problem: 271. Code and decoding of string

[TOC]

Thinking

Is the first reaction encrypted and decrypted the string，But after reading the question, I found that the list was converted into a string，Then the second part of the string that he has processed back to the source list。

Solution

There may be multiple elements in the list（Depend on‘，’The word group that is separated），在每个元素middle可能存在多个Depend on空格隔开的单词。So separatelistThe elements and spaces are processed。

1. First of all, the first layer traverses on the list，Each element traverses every element，Read‘ ’When the pre -declared empty list is added, adding a rotary symbol（In the beginning, I plan to customize the righteous symbol，Later discovered\tDirectly feasible）Add a new one to the list at each layer to end each layer，and‘ ’Different rotation are such as\n。at last''.join()Convert to a string，return。
2. When decoding，Pre -declaration of a empty listListAnd empty stringStr，Read when traversing‘\t’when，Add the space to the stringStr = ''.join([Str, ' '])，Same，Read’\n’when就将Stradd toListmiddle，WillStrPlace the next cycle。

the complexity

• 时间the complexity:

  添加时间the complexity, Exemplary example： $O(n)$

• 空间the complexity:

  添加空间the complexity, Exemplary example： $O(n)$

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

class Codec:
    def encode(self, strs: list[str]) -> str:
        """Encodes a list of strings to a single string.
        """
        List = []
        for i in strs:
            for j in i:
                if j == ' ':
                    List.append('\t')
                else:
                    List.append(j)
            List.append('\n')
        List = ''.join(List)
        return List

    def decode(self, s: str) -> list[str]:
        """Decodes a single string to a list of strings.
        """
        List = []
        Str = ''
        for i in s:
            if i == '\t':
                Str = ''.join([Str, ' '])
            else:
                if i != '\n':
                    Str = ''.join([Str, i])
                else:
                    List.append(Str)
                    Str = ''
        return List

topic：

Thought：

1. firstBit operation有三个特性：
   1. Any number and0Different or operational，The result is still the original number，Right now a XOR 0 = a。
   2. Any number and自身Different or operational，turn out0，Right now a XOR a = 0。
   3. Different or operations meet the law of exchange and binding。

1
2
3
4
5

a = 0b1001
b = 0b0110
bin(a ^ b)

'0b1111'

first，We need to calculate the array nums All elements of all elements，Be remembered xor_sum。Our goal is to make some positions to make xor_sum equal k。

then，We can consider xor_sum XOR k the result of。Due to the characteristics of different or computing，The difference in any position will cause the bit in the result to be1。this means，We need to change xor_sum and k All different places in binary representation。

if xor_sum = 1010，k = 0011，So xor_sum XOR k = 1001。We need to change第一位and第四位来让 xor_sum become k。

That is numsHeterogeneityand kValue, in1The number is the number that needs to be converted。can watch0x3fSolution

Code：

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

class Solution:
    def minOperations(self, nums: List[int], k: int) -> int:
        xor_sum = 0
        for num in nums:
            xor_sum ^= num

        xor_diff = xor_sum ^ k
        operations = 0

        # Calculate the digits that need to be changed
        while xor_diff:
            operations += xor_diff & 1
            xor_diff >>= 1

        return operations

1
2
3
4
5
6

func minOperations(nums []int, k int) int {
	for _, x := range nums {
		k ^= x
	}
	return bits.OnesCount(uint(k))
}

topic：

Thought：

We will first x andNumber of operations 0 Put in a queue。Then，我们不断地从队列中取出当前的值andNumber of operations，Check whether the target value has reached the target value y。
if there is not，We will perform possible operation for this value，并将新值andNumber of operations加入队列中，Until finding the shortest path。

Code：

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 minimumOperationsToMakeEqual(self, x: int, y: int) -> int:
        # make用队列来进行Priority search
        queue = deque([(x, 0)])  # (The current value, Number of operations)
        visited = set()  # Used to record the values ​​that have been accessed，Avoid repeated treatment

        while queue:
            current, steps = queue.popleft()
            if current == y:
                return steps
            visited.add(current)

            # Explore four operations
            if current % 11 == 0 and current // 11 not in visited:
                queue.append((current // 11, steps + 1))
            if current % 5 == 0 and current // 5 not in visited:
                queue.append((current // 5, steps + 1))
            if current - 1 not in visited:
                queue.append((current - 1, steps + 1))
            if current + 1 not in visited:
                queue.append((current + 1, steps + 1))

        return -1  # 如果无法make x and y equal，Then return -1

topic：

3072. Allocate elements into two arrays II.md
“””

Give you a bidding 1 start、Length n 的整数Array nums 。

Now define function greaterCount ，Make greaterCount(arr, val) 返回Array arr middle Strict val Number of elements。

You need to use n Secondary operation，Will nums 的所有元素分配到两个Array arr1 and arr2 middle。In the first place一Secondary operationmiddle，Will nums[1] Add arr1 。In the first place二Secondary operationmiddle，Will nums[2] Add arr2 。after，In the first place i Secondary operationmiddle：

• if greaterCount(arr1, nums[i]) > greaterCount(arr2, nums[i]) ，Will nums[i] Add arr1 。
• if greaterCount(arr1, nums[i]) < greaterCount(arr2, nums[i]) ，Will nums[i] Add arr2 。
• if greaterCount(arr1, nums[i]) == greaterCount(arr2, nums[i]) ，Will nums[i] Add元素数量较少的Arraymiddle。
• if仍然相等，SoWill nums[i] Add arr1 。

连接Array arr1 and arr2 形成Array result 。For example，if arr1 == [1,2,3] and arr2 == [4,5,6] ，So result = [1,2,3,4,5,6] 。

返回整数Array result 。

Exemplary example 1：

enter：nums = [2,1,3,3]
Output：[2,3,1,3]
explain：exist前两Secondary operation后，arr1 = [2] ，arr2 = [1] 。
In the first place 3 Secondary operationmiddle，两个Arraymiddle大于 3 Number of elements都yes零，并and长度相等，therefore，Will nums[3] Add arr1 。
In the first place 4 Secondary operationmiddle，两个Arraymiddle大于 3 Number of elements都yes零，but arr2 Small length，therefore，Will nums[4] Add arr2 。
exist 4 Secondary operation后，arr1 = [2,3] ，arr2 = [1,3] 。
therefore，连接形成的Array result yes [2,3,1,3] 。

Exemplary example 2：

enter：nums = [5,14,3,1,2]
Output：[5,3,1,2,14]
explain：exist前两Secondary operation后，arr1 = [5] ，arr2 = [14] 。
In the first place 3 Secondary operationmiddle，两个Arraymiddle大于 3 Number of elements都yes一，并and长度相等，therefore，Will nums[3] Add arr1 。
In the first place 4 Secondary operationmiddle，arr1 middle大于 1 Number of elements大于 arr2 middle的数量（2 > 1），therefore，Will nums[4] Add arr1 。
In the first place 5 Secondary operationmiddle，arr1 middle大于 2 Number of elements大于 arr2 middle的数量（2 > 1），therefore，Will nums[5] Add arr1 。
exist 5 Secondary operation后，arr1 = [5,3,1,2] ，arr2 = [14] 。
therefore，连接形成的Array result yes [5,3,1,2,14] 。

Exemplary example 3：

enter：nums = [3,3,3,3]
Output：[3,3,3,3]
explain：exist 4 Secondary operation后，arr1 = [3,3] ，arr2 = [3,3] 。
therefore，连接形成的Array result yes [3,3,3,3] 。

hint：

• 3 <= n <= 105
• 1 <= nums[i] <= 109

Thought：

1. initialization：
   首先Will nums Array反转，以便我们可以从最后一个元素start处理。这一步exist最初与学长@Angro beatICPCI learned，pop() Compare pop(0) It is much faster。
   Will反转后的第一个元素分配给 arr1 and temp1，The second element is allocated to arr2 and temp2。

2. Iteration processing each element：
   use while Traversal nums Array的剩余元素。
   For each element，use bisect.bisect_right exist arr1 and arr2 middle找到Compare当前元素小的元素的数量。
   Re -uselen(arr1)andlen(arr2)Minus this quantity，得到Compare当前元素大的元素的数量。
   然后进行Compare较To。 为了use二分查找，therefore我们要保证 arr1 and arr2 yes有序的， Pythonmiddleuse insort() To。
   but同时我们要维持一个答案Array，thereforeappendTo。

3. Merge answer

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

import bisect
from typing import List

class Solution:
    def resultArray(self, nums: List[int]) -> List[int]:
        nums = nums[::-1]
        temp = nums.pop()
        arr1 = [temp]
        temp1 = [temp]
        temp = nums.pop()
        arr2 = [temp]
        temp2 = [temp]
        while nums:
            temp = nums.pop()
            # [28] [2]
            index1 = bisect.bisect_right(arr1, temp)
            index2 = bisect.bisect_right(arr2, temp)
            length_1 = len(arr1) - index1
            length_2 = len(arr2) - index2
            if length_1 > length_2:
                bisect.insort(arr1, temp)
                temp1.append(temp)
            elif length_1 < length_2:
                bisect.insort(arr2, temp)
                temp2.append(temp)
            else:
                if len(arr1) > len(arr2):
                    bisect.insort(arr2, temp)
                    temp2.append(temp)
                else:
                    bisect.insort(arr1, temp)
                    temp1.append(temp)

        return temp1 + temp2

topic：

2341. How much can the array be formed.md

Thought：

I am：

I don’t know if I saw it“Simple”Two words，This question has the initiative to think about the optimal solution。Actually this timeylbBig guy’s hash table method is still fast。
Sort the list，Whether two or two are equal to whether。

Hash tableThought：

CounterAfter counting，a+=v//2,b+=v%2For each number x，
if x Number of times v more than the 1，You can choose two from the array x Form a number pair，we willv Divide 2 Take down，
You can get the current number x Number pairs that can be formed，Then we accumulate this number to the variable s middle。

Code：

1
2
3
4
5
6
7
8
9
10

class Solution:
    def numberOfPairs(self, nums: List[int]) -> List[int]:
        nums.sort()
        ans = [0, len(nums)]
        for index in range(1, len(nums)):
            if nums[index - 1] == nums[index]:
                ans[0] += 1
                ans[1] -= 2
                nums[index - 1] = nums[index] = -1
        return ans

1
2
3
4
5
6
7
8
9

class Solution:
    def numberOfPairs(self, nums: List[int]) -> List[int]:
        x = Counter(nums)
        a = 0
        b = 0
        for k,v in x.items():
            a+=v//2
            b+=v%2
        return [a,b]

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

350. The intersection of two array II
Simple
883
company
Amazon
company
Byte beating
company
Facebook
Give you two integer arrays nums1 and nums2 ，Please return the intersection of two arrays in the form of an array。The number of times each element in the return result，It should be consistent with the number of times the elements appear in both arrays（If the number of times is inconsistent，Then consider taking the smaller value）。You can consider the order of the output result。

 

Exemplary example 1：

enter：nums1 = [1,2,2,1], nums2 = [2,2]
Output：[2,2]
Exemplary example 2:

enter：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output：[4,9]
 

hint：

1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 1000
 

Advance：

If the given array has been arranged, the order is good？How will you optimize your algorithm？
if nums1 Size ratio nums2 Small，Which method is better？
if nums2 The elements are stored on the disk，Memory is limited，And you can't load all elements at one time to memory，what should you do？

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

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        hash_1 = {}
        hash_2 = {}
        for index, i in enumerate(nums):
            if i not in hash_1:
                hash_1[i] = 1
                hash_2[i] = [index]
            else:
                hash_1[i] += 1
                hash_2[i].append(index)
        for i in hash_1:
            if hash_1[i] >= 2:
                for j in range(len(hash_2[i])):
                    for m in range(j + 1, len(hash_2[i])):
                        if abs(hash_2[i][j] - hash_2[i][m]) <= k:
                            return True
        return False

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

# Sort out the meaning：Whether the existence does not exceed k+1k + 1k+1 window，window内有相同元素。
class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        n = len(nums)
        s = set()
        for i in range(n):
            if i > k:
                s.remove(nums[i - k - 1])
            if nums[i] in s:
                return True
            s.add(nums[i])
        return False

&&Operate

1
2
3
4
5
6

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        num1 = collections.Counter(nums1)
        num2 = collections.Counter(nums2)
        num = num1 & num2
        return num.elements()

topic：

345. Voice letter in the reverse string.md

Thought：

Write two methods，Watch the reminder of the three leaves of the palace water，Can be made with dual pointers，See if both the elements of both ends are vowel letters。 Improved two editions。

Code：

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

class Solution:
    def reverseVowels(self, s: str) -> str:
        vowels = 'aeiouAEIOU'
        start = 0
        end = len(s) - 1
        while start < end:
            while s[end] not in vowels and start < end:
                end -= 1
            while s[start] not in vowels and start < end:
                start += 1
            if s[start] in vowels and s[end] in vowels:
                s[start], s[end] = s[end], s[start]
                start += 1
                end -= 1
        return ''.join(s)

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

class Solution:
    def reverseVowels(self, s: str) -> str:
        s = list(s)
        vowels = 'aeiouAEIOU'
        ans = []
        for i in s:
            if i in vowels:
                ans.append(i)
        a = ''
        for i in range(len(s)):
            if s[i] in vowels:
                a += ans.pop()
            else:
                a += s[i]
        return ''.join(a)

topic：

445.Two numbers

Thought：

I have been with yesterday’s question，Find by the way
What is deducted is a very strange oneprecompiled.listnode.ListNode，But mine is'__main__.ListNode'。
Because：Repeatedly defined$ListNode$
不反转Linkedof方法可能就是昨天of那种，转化为math做。
The code is still0x3fof
and昨天ofanswer法一样

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

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head is None or head.next is None:
            return head
        new_head = self.reverseList(head.next)
        head.next.next = head  # Direct the next node to yourself
        head.next = None  # 断开指向下一个节点of连接，ensure最终Linkedof末尾节点of next Is an empty node
        return new_head

    # l1 and l2 为当前遍历of节点，carry Be in place
    def addTwo(self, l1: Optional[ListNode], l2: Optional[ListNode], carry=0) -> Optional[ListNode]:
        if l1 is None and l2 is None:  # recursion边界：l1 and l2 都Is an empty node
            return ListNode(carry) if carry else None  # If you are in place，Just create an additional node
        if l1 is None:  # if l1 是空of，Then then l2 一定不Is an empty node
            l1, l2 = l2, l1  # exchange l1 and l2，ensure l1 non empty，从而简化Code
        carry += l1.val + (l2.val if l2 else 0)  # 节点值andcarry加在一起
        l1.val = carry % 10  # Each node saves a digital position
        l1.next = self.addTwo(l1.next, l2.next if l2 else None, carry // 10)  # carry
        return l1

    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        l1 = self.reverseList(l1)
        l2 = self.reverseList(l2)  # l1 and l2 Reversal，Just become【2. Two numbers】Over
        l3 = self.addTwo(l1, l2)
        return self.reverseList(l3)

topic：

“””

Give two forks search Root node，The node value of the tree is different，Please convert it to a cumulative tree（Greater Sum Tree），Make each node node The new value of the original tree is greater than or equal to the original tree node.val The sum of the value。

remind，二叉searchTree满足下列约束条件：

• The left tree of the node contains only the key Less than Node node node。
• The right tree of the node contains only the key more than the Node node node。
• 左右子Tree也必须是二叉searchTree。

Notice：This question 1038: https://leetcode-cn.com/problems/binary-search-tree-to-greater-sum-tree/ same

Exemplary example 1：

enter：[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
Output：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

Exemplary example 2：

enter：root = [0,null,1]
Output：[1,null,1]

Exemplary example 3：

enter：root = [1,0,2]
Output：[3,3,2]

Exemplary example 4：

enter：root = [3,2,4,1]
Output：[7,9,4,10]

hint：

• The number of nodes in the tree is in 0 and 104 between。
• The value of each node -104 and 104 between。
• All the values ​​in the tree 互不same 。
• 给定的Tree为二叉searchTree。

Thought：

method one：Travel in the preface
Thinking and algorithm

本题中要求我们将每个节点的值修改为原来的节点值加上所有more than the它的节点值之and。这样我们只需要Travel in the preface该二叉searchTree，记录过程中的节点值之and，Not continuously update the node value of the nodes you currently traversed，即可得到topic要求的累加Tree。

Method Two：Morris Traversal
Thinking and algorithm

There is a clever way to be online，只占用常数空间来实现中序Traversal。This method is caused by J. H. Morris exist 1979 Annual thesis「Traversing Binary Trees Simply and Cheaply」Proposed for the first time，Because it is called Morris Traversal。

我们以一个简单的Binary tree为例进行说明。假设我们要进行中序Traversal的 Morris Traversal。

1
2
3
4
5
6

    1
   / \
  2   3
 / \
4   5

1. Initialization The current node is the root node（current = 1）。

2. When the current node is not empty，Execute the following steps：

   1. The left node of the current node is not empty。We find the front -drive node of the current node，也就是左子Tree中的最右节点。exist这个例子中，The front -drive node is the node5。
   2. The right node of the front -drive node is empty，Point your right node to the current node（5 -> 1）。
   3. Move the current node to its left child node（current = 2）。

   1 2 3 4 5

   1 \ 2 / \ 4 5

   1. The left node of the current node is not empty。We find the front -drive node of the current node，也就是左子Tree中的最右节点。exist这个例子中，The front -drive node is the node4。
   2. The right node of the front -drive node is empty，Point your right node to the current node（4 -> 2）。
   3. Move the current node to its left child node（current = 4）。

   1 2 3 4 5 6 7 8

   1 \ 2 \ 4 \ 5

   1. The left node of the current node is empty。Output当前节点的值（4）。

   2. Move the current node to its right node（current = 5）。

   3. The left node of the current node is empty。Output当前节点的值（5）。

   4. Move the current node to its right node（current = 2）。

   1 2 3 4 5

   1 \ 2 \ 4

   1. The left node of the current node is empty。Output当前节点的值（2）。
   2. Move the current node to its right node（current = 1）。

   1 2 3

   1 \ 2

   1. The left node of the current node is empty。Output当前节点的值（1）。
   2. Move the current node to its right node（current = 3）。

   1 2 3

   1 \ 2

   1. The left node of the current node is empty。Output当前节点的值（3）。
   2. Move the current node to its right node（current = null）。

3. The current node is empty，Traversal结束。

According to the above steps，通过修改节点between的指针关系，我们完成了对Binary tree的中序Traversal。

Code：

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

class Solution:
    def convertBST(self, root: TreeNode) -> TreeNode:
        def dfs(root: TreeNode):
            nonlocal total
            if root:
                dfs(root.right)
                total += root.val
                root.val = total
                dfs(root.left)
        
        total = 0
        dfs(root)
        return 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
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

class Solution:
    def convertBST(self, root: TreeNode) -> TreeNode:
        # Get the successor node of the given node（中序Traversal中的下一个节点）
        def getSuccessor(node: TreeNode) -> TreeNode:
            succ = node.right
            while succ.left and succ.left != node:
                succ = succ.left
            return succ
        
        total = 0  # 记录累加的节点值之and
        node = root  # The current node initialization is the root node

        while node:
            if not node.right:  # If the right node of the current node is empty
                total += node.val  # Add the value of the current node to the cumulative value
                node.val = total  # Update the value of the current node to accumulate value
                node = node.left  # Move the current node to its left child node
            else:  # If the right node of the current node is not empty
                succ = getSuccessor(node)  # Get the successor node of the current node
                if not succ.left:  # If the left node of the successor node is empty
                    succ.left = node  # Point the left -node of the successor node to the current node，Establish a clue
                    node = node.right  # Move the current node to its right node
                else:  # If the left node of the successor node is not empty
                    succ.left = None  # Set the left node of the successor node to empty，Remove clues
                    total += node.val  # Add the value of the current node to the cumulative value
                    node.val = total  # Update the value of the current node to accumulate value
                    node = node.left  # Move the current node to its left child node

        return root  # Return to the root node

class Solution:
    def convertBST(self, root: TreeNode) -> TreeNode:
        def convert(node: TreeNode, total: int) -> int:
            if not node:
                return total

            # 递归Traversal右子Tree
            total = convert(node.right, total)

            # Update the node value to accumulate and add value
            total += node.val
            node.val = total

            # 递归Traversal左子Tree
            total = convert(node.left, total)

            return total

        convert(root, 0)
        return root