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]

topic：

Give you a linked list，Two or two exchanges are adjacent nodes，And return to the head node of the linked list after exchange。You must complete this question without modifying the internal value of the node（Right now，Can only exchange nodes）。

Exemplary example 1：

enter：head = [1,2,3,4]
Output：[2,1,4,3]

Exemplary example 2：

enter：head = []
Output：[]

Exemplary example 3：

enter：head = [1]
Output：[1]

hint：

• The number of nodes in the linked list is in the range [0, 100] Inside
• 0 <= Node.val <= 100

24.Two or two exchanges linked watches.md

Thought：

use head 表示原始Linked的头节点，新的Linked的第二个节点，use newHead 表示新的Linked的头节点，原始Linked的第二个节点，则原始Linked中的其余节点的头节点是 newHead.next。make head.next = swapPairs(newHead.next)，Indicates two or two exchanges for the rest of the nodes，The new head node after the exchange is head The next node。然后make newHead.next = head，Right now完成了所有节点的交换。最后返回新的Linked的头节点 newHead。

Code：

1
2
3
4
5
6
7
8

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head
        virtual_head = head.next
        head.next = self.swapPairs(virtual_head.next)
        virtual_head.next = head
        return virtual_head

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

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if (head == nullptr or head->next == nullptr){
            return head;
        }
        ListNode *yummyNode = head->next;
        head->next = swapPairs(yummyNode->next);
        yummyNode->next = head;
        return yummyNode;
    }
};

6289.Query array Xor Beautiful value。

This question has been studied for a long time，Discovering a mathematical problem，But I didn’t want to be transparent，Because unfamiliar or valuable。So there is no better solution。

The first is to read the question and learn(nums[i]|nums[j])&nums[k]，becauseijkCan be any value in the array，So the tripleforcycle（It will definitely timeout），Then he was a little bit out of his own，Just a little bit，feeli，jThe value of the value is the same，So add an additional layer of judgment（Dictionary）。

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 xorBeauty(self, nums: List[int]) -> int:
        ans = []
        record = {}
        for i in range(len(nums)):
            for j in range(len(nums)):
                for k in range(len(nums)):
                    if k not in record:
                        if (i,j) not in record.values():
                            record[k] = (i,j)
                            flag = (nums[i]|nums[j])&nums[k]
                            if flag not in ans:
                                ans.append(flag)
                            else:
                                ans.remove(flag)
        if len(ans) == 0:
            return 0
        answer = ans[0]

        for i in range(1,len(ans)):
            answer ^= ans[i]
        return answer

I have been thinking about how to judge the same situation when I go out today，As a result@Lingcha Mountain AifuSolution，One by one，That’s okay。

1
2
3
4

class Solution:
    def xorBeauty(self, nums: List[int]) -> int:
        return reduce(xor, nums)

Then do，Search online，It turns out that if the two values ​​are the same，for exampleA^B^A = B，Soappend，removeTo implement this function。at lastforcycle求异或值。

Big Big Code is still studyinging

topic：

2639. Query the width of each column in the grid diagram.md

Thought：

The first thing I think is to usemapTo solve，[list(map(lambda x: len(str(x)), row)) for row in grid] Build such an expression，但是topic要求找到列的最大值，If it is done by yourself so manually, you need itO(n^2)Time complexity，SonumpyYou can easily find the iterative value of each column。

Code：

1
2
3
4
5
6
7
8
9
10
11

import numpy as np

class Solution:
    def findColumnWidth(self, grid: List[List[int]]) -> List[int]:
         # let's convert the grid to a numpy array
        np_grid = np.array(grid, dtype=str)
        # calculate the length of each element in the grid
        lengths = np.vectorize(len)(np_grid)
        # find the maximum length of each column
        max_lengths = lengths.max(axis=0)
        return max_lengths.tolist()

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

impl Solution {
    pub fn find_column_width(grid: Vec<Vec<i32>>) -> Vec<i32> {
        let col_n = grid[0].len();
        let mut ans = vec![0; col_n];

        for row in grid.iter() {
            for (i, &num) in row.iter().enumerate() {
                let length = num.to_string().len() as i32;
                if length > ans[i] {
                    ans[i] = length;
                }
            }
        }
        ans
    }
}

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：

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)