topic：

1824Minimum side jump number

answer：

I won’t

https://leetcode.cn/problems/minimum-sideway-jumps/solutions/2071617/cong-0-dao-1-de-0-1-bfspythonjavacgo-by-1m8z4/?orderBy=most_votes

Code：

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

class Solution:
    def minSideJumps(self, obstacles: List[int]) -> int:
        n = len(obstacles)
        dis = [[n] * 3 for _ in range(n)]
        dis[0][1] = 0
        q = deque([(0, 1)])  # starting point
        while True:
            i, j = q.popleft()
            d = dis[i][j]
            if i == n - 1: return d  # reach destination
            if obstacles[i + 1] != j + 1 and d < dis[i + 1][j]:  # To the right
                dis[i + 1][j] = d
                q.appendleft((i + 1, j))  # Add to the team
            for k in (j + 1) % 3, (j + 2) % 3:  # The other two other runways are enumerated（up/down）
                if obstacles[i] != k + 1 and d + 1 < dis[i][k]:
                    dis[i][k] = d + 1
                    q.append((i, k))  # Add to the tail

Problem -solving

maintain 3 indivual multiset：lower（Minimum kkk indivual数）、middle（Number in the middle）、upper（Most kkk indivual数）。

Insert operation

·if num≤max(lower)，Then lowerInsert num
·if num≥min(upper)，Then upper Insert num
·otherwise，exist middle Insert num
if插入后，lower or upper There are more elements than k indivual，Then middle middle Transfer element

操作过程middlemaintain middle 的element和 sum

Delete operation

·设删除的element为 d
·d 一定存exist于 lower ormiddle or upper middle的一indivualor多indivual集合middle
·Choose one delete
if删除后，lower or upper middle的element少于 k indivual，Then from middle middle Obtain element

操作过程middlemaintain middle 的element和 sum

average value操作

average value = sum/(m−2⋅k)sum / (m - 2\cdot k)sum/(m−2⋅k) （Take down）。

Code with problems：

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

class MKAverage:

    def __init__(self, m: int, k: int):
        self.m = m
        self.k = k
        self.list1 = []

    def addElement(self, num: int) -> None:
        self.list1.append(num)

    def calculateMKAverage(self) -> int:
        if len(self.list1) < self.m:
            return -1
        else:
            list2 = self.list1[-1:-self.m-1:-1]
            list2 = sorted(list2)
            list2 = list2[self.k:len(list2) - self.k]
        return sum(list2) // len(list2)

topic：

1828. Statistics the number of a circle mid -point

Thought：

Today’s question is very simple，I wonder if it is against yesterday’s question bidding。
AskqueriesThere are a few in the circlepointsPoints in an array。
To be honest, I was scared，I think this question is the question of the picture again。不过仔细读题了后发现只是一道简单的math题，
We can use European -style distance to solve（Time complexity isOn^2，I thought I had a better solution，At first glance everyone is like this（））

The formula of the European -style distance is as follows：

$\sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}$

We look at the code for specific operations：

Code

1
2
3
4
5
6
7
8
9
10
11

class Solution:
    def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:
        # Seek to solve whether the European -style distance from the center is less than r
        ans = [0] * len(queries)
        flag = 0
        for x, y, r in queries:
            for i, j in points:
                if ((x - i) ** 2 + (y - j) ** 2) ** (1 / 2) <= r:
                    ans[flag] += 1
            flag += 1
        return ans

Take a look at someone who can’t understandpythonCode：

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

class Solution:
    def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:
        points = sorted(points)

        res = [0 for _ in range(len(queries))]

        for i, (u, v, r) in enumerate(queries):
            left, right = u - r, u + r

            idx1 = bisect_left(points, [left, -inf])
            idx2 = bisect_right(points, [right, inf])

            for x, y in points[idx1: idx2 + 1]:
                if (v - r <= y <= v + r and 
                    (x - u) * (x - u) + (y - v) * (y - v) <= r * r):
  
                    res[i] += 1

        return res

topic：

Give you a linked list，Delete the countdown of the linked list n Node，And return to the head point of the linked list。

Exemplary example 1：

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

Exemplary example 2：

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

Exemplary example 3：

enter：head = [1,2], n = 1
Output：[1]

hint：

• The number of nodes in the linked list is sz
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

Advance：Can you try to use a scanning implementation?？

19.Delete the countdown of the linked listNNode.md

Thought：

It is definitely possible to solve the problem by taking dual traversal，但topic要求我们一次遍历解决问题，Then we have to diverge on our ideas。

我们可以设想假设设定了Double pointer p and q if，when q Pointed to the end NULL，p and q The number of elements separated from each other is n hour，Then delete p The next pointer completes the requirements。

Set up virtual nodes dummyHead direction head
设定Double pointer p and q，初始都direction虚拟节点 dummyHead
move q，until p and q The number of elements separated from each other is n
同hourmove p and q，until q direction的为 NULL
Will p 的下一Nodedirection下下Node

Code：

1
2
3
4
5
6
7
8
9
10

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummyHead = ListNode(val=0, next=head)
        head = tail = dummyHead
        for _ in range(n):
            tail = tail.next
        while tail.next is not None:
            head, tail = head.next, tail.next
        head.next = head.next.next
        return dummyHead.next

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 {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *yummyNode = new ListNode(0);
        yummyNode->next = head;
        ListNode *fast = yummyNode;
        ListNode *slow = yummyNode;
        for(int i = 0; i < n; i++){
            slow = slow->next;
        }
        while (slow->next != nullptr){
            fast = fast->next;
            slow = slow->next;
        }
        //Recycling memory
        ListNode *del = fast->next;
        fast->next = del->next;
        delete del;
        //Return to node
        ListNode *ret = yummyNode->next;
        delete yummyNode;
        return ret;

Course：

1. 看了官方answer，Similar to my first approach，AllsortedLater in the new listappend。But I think I can’t prove the correctness，Because it is Zhou Sai dare not submit at will。
2. Discover when thinking about the first solution，If I keepfor i in Whole array，Determine whether to meet the conditions and then exchange the position，What should I do if I enter the dead cycle?？If a special case fails every time, it needs to be exchanged. What is the difference between random disruption?？
3. After watching the solution of other big guys，I am still too young

1
2
3
4
5
6
7
8
9
10

def rearrangeArray(self, nums: List[int]) -> List[int]:
    i = 1
    while i < len(nums)-1:
        if nums[i] == (nums[i - 1] + nums[i + 1]) // 2:
            random.shuffle(nums)
            i = 1
        else:
            i += 1
    else:
        return nums

topic：

Given n The array of a positive integer and a positive integer target 。

Find out the array to satisfy it ≥ target The smalle Continuous array [numsl, numsl+1, ..., numsr-1, numsr] ，And return its length。If there is no conditional sub -array，return 0 。

Exemplary example 1：

enter：target = 7, nums = [2,3,1,2,4,3]
Output：2
explain：Sub -array [4,3] 是该条件下的Small length array。

Exemplary example 2：

enter：target = 4, nums = [1,4,4]
Output：1

Exemplary example 3：

enter：target = 11, nums = [1,1,1,1,1,1,1,1]
Output：0

hint：

• 1 <= target <= 109
• 1 <= nums.length <= 105
• 1 <= nums[i] <= 105

Advance：

• If you have achieved it O(n) Time complexity solution, Please try to design a O(n log(n)) Time complexity solution。

Thought：

Originally planned to use double pointers，But my double pointer is over time。

Code：

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

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        n = len(nums)
        ans = n+1   # inf
        s = 0
        left = 0
        for right, x in enumerate(nums):
            # Record the results of the previous additional addition
            s += x
            # Move the left point,left <= right,Because of this and the front of this numbersalready>=targetOver，SosReduce the number of digital judgments can still be reduced
            while s - nums[left] >= target:
                s -= nums[left]
                left += 1
            if s >= target:
                ans = min(ans, right-left+1)
        return ans if ans <= n else 0

217. Existing duplicate elements

Thought：

For the first time**C++**Write a question
Two methods：

1. The first is sorting，Detect each time the first and the latter are equal；
2. 第二种方法是Hash table，Determine whether the number has appeared for the second time。
   existC++middle，Force buckle into the arraynumsin usevector，So it can be used directlysort()function。
   I want to usePythonmiddle的字典（Hash table）if，Give to importunordered_set<int>function新建Hash table，Re -usefind()andend()判断是否已经存exist。

Code：

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

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        for (int i = 0; i < nums.size() - 1; i++){
            if(nums[i] == nums[i+1]) {
                return true;
            }
        }
        return false;
    }
};

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

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        std::unordered_set<int> Hash;
        for(int i: nums){
            if(Hash.find(i) != Hash.end()){
                return true;
            }
            else{
                Hash.insert(i);
            }
        }
    return false;
    }
};

1
2
3
4
5
6
7
8

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        dict1 = Counter(nums)
        dict1 = sorted(dict1.values())
        if dict1[-1] >= 2:
            return True
        else:
            return False

217. Existing duplicate elements

Thought：

For the first time**C++**Write a question
Two methods：

1. The first is sorting，Detect each time the first and the latter are equal；
2. 第二种方法是Hash table，Determine whether the number has appeared for the second time。
   existC++middle，Force buckle into the arraynumsin usevector，So it can be used directlysort()function。
   I want to usePythonmiddle的字典（Hash table）if，Give to importunordered_set<int>function新建Hash table，Re -usefind()andend()判断是否已经存exist。

Code：

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

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        for (int i = 0; i < nums.size() - 1; i++){
            if(nums[i] == nums[i+1]) {
                return true;
            }
        }
        return false;
    }
};

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

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        std::unordered_set<int> Hash;
        for(int i: nums){
            if(Hash.find(i) != Hash.end()){
                return true;
            }
            else{
                Hash.insert(i);
            }
        }
    return false;
    }
};

1
2
3
4
5
6
7
8

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        dict1 = Counter(nums)
        dict1 = sorted(dict1.values())
        if dict1[-1] >= 2:
            return True
        else:
            return False

Thought

This question was done on the phone at first，直接用的是双Hash table，An element，One depositindex，When a certain element exceeds2Judging whether there are two of them when they areindexSubtission is equal tokCase。So the complexity of time isO(n^3)。

Code：

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

look@Gongshui SanyeGongshui Sanye的解法后，Only think of，这道题的目的是为了练习双指针在Hash table中的应用，TAThe original words are sorting the meaning：Whether the existence does not exceed k+1k + 1k+1 window，window内有相同元素。

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

topic：

221. Maximum square

Thought：

可以使用Dynamic planning降低时间复杂度。we use dp(i,j) Express (i,j) The lower right corner，Only contain 1 The maximum value of the side length of the square。If we can calculate all dp(i,j) Value，Then the maximum value is that it is only included in the matrix 1 The maximum value of the side length of the square，其平方即为Maximum square的面积。

So how to calculate dp Each element value？For each position (i,j)，检查在矩阵中该位置Value：

if该位置Value是 0，but dp(i,j)=0，Because the current location cannot 1 Folk formation of composition；

if该位置Value是 1，but dp(i,j) Value由其上方、Three adjacent locations on the left and upper left dp Value decision。in particular，The element value of the current position is equal to the minimum value of the three adjacent elements 1，The state transfer equation is as follows：

dp(i,j)=min(dp(i−1,j),dp(i−1,j−1),dp(i,j−1))+1
also，You also need to consider boundary conditions。if i and j At least one of them is 0，but以位置(i,j) The lower right corner的Maximum square的边长只能是 1，therefore dp(i,j)=1

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

package main

func maximalSquare(matrix [][]byte) int {
	dp := make([][]int, len(matrix))
	maxSide := 0
	for i := 0; i < len(matrix); i++ {
		dp[i] = make([]int, len(matrix[i]))
		for j := 0; j < len(matrix[i]); j++ {
			dp[i][j] = int(matrix[i][j] - '0')
			if dp[i][j] == 1 {
				maxSide = 1
			}
		}
	}
	for i := 1; i < len(matrix); i++ {
		for j := 1; j < len(matrix[i]); j++ {
			if dp[i][j] == 1 {
				dp[i][j] = min(min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) + 1
				if dp[i][j] > maxSide {
					maxSide = dp[i][j]
				}
			}
		}
	}
	return maxSide * maxSide
}

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}