topic：

1798. You can construct the maximum number of continuity

Thought：

nums = [1,4,10,3,1]1 ~ 10 All can be constructed，so11 ~ 20As well。
Traversal nums = [1,1,3,4,10]， if i<= Earlier+1

$i_0(1) <= 0+1; i_1(1) <= 1+1; i_2(3) <= 2+1; i_3(4) <= 5+1; i_4(10) <= 9+1$

, ExplainiThe previous numbers can be constructed。if i > m + 1It means that it cannot be constructed。

Code：

1
2
3
4
5
6
7
8
9

class Solution:
    def getMaximumConsecutive(self, coins: List[int]) -> int:
        m = 0  # At the beginning, it can only be constructed 0
        coins.sort()
        for c in coins:
            if c > m + 1:  # coins Sort，There is no comparison c Smaller
                break  # Unable to construct m+1，Continue to loop is meaningless
            m += c  # Can be constructed [0,m+c] All integer
        return m + 1  # [0,m] China m+1 An integer

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

func getMaximumConsecutive(coins []int) int {
	// Initialize a containing0Array
	m := 0
	sort.Ints(coins)
	for _, c := range coins {
		if c > m+1 {
			break
		}
		m += c
	}
	return m + 1
}

Just write a question every day，然后写下能让自己看懂的answer吧!
The new year has passed5All over，Write this at one time5God。

first of all1801.1802.1803，The daily questions of these three days are actually a high -quality weekly match last year，Even the simple label is also ordinary difficulty。

If the method is solved, it is a stack of a triangle，Stop increased after reaching the boundary（If it continues to increase, it will lead to timeout） 。

When both sides are reached，Just lay all the remaining bricks directly on the top layer。

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

1802. Specify the maximum value of the lower bid in the bounded array
      medium
      182
      company
      Amazon
      company
      Facebook
      Give you three positive integers n、index and maxSum 。You need to construct an array that meets all the conditions at the same time nums（Bidding from 0 start count）：

nums.length == n
nums[i] yes Positive integer ，in 0 <= i < n
abs(nums[i] - nums[i+1]) <= 1 ，in 0 <= i < n-1
nums 中所有元素之and不超过 maxSum
nums[index] Value maximize
Return to the array you constructed nums[index] 。

Notice：abs(x) equal x 的前提yes x >= 0 ；otherwise，abs(x) equal -x 。



Exemplary example 1：

enter：n = 4, index = 2,  maxSum = 6
Output：2
explain：Array [1,1,2,1] and [1,2,2,1] Meet all conditions。不存在其他在指定BiddingPlace具有更大值的有效Array。
Exemplary example 2：

enter：n = 6, index = 1,  maxSum = 10
Output：3


hint：

1 <= n <= maxSum <= 109
0 <= index < n

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 maxValue(self, n: int, index: int, maxSum: int) -> int:
        diff = maxSum - n
        left = index
        right = index
        res = 1
        dl = 0
        dr = 0
        while diff > 0:  # When there are remaining bricks
            left -= 1
            right += 1
            if left >= 0:
                dl = dl + 1  # Before reaching the left boundary
            if right < n:
                dr = dr + 1  # Have not arrived at the right boundary
            if left < 0 and right >= n:  # 当到达左边界and右边界时 Exit
                # res+=diff%n==0?diff/n:diff/n+1 #Divide the remaining bricks，Exit directly
                res += diff // n if diff % n == 0 else diff // n + 1
                return res
            res += 1  # Layer renewal
            diff -= (dl + dr + 1)  # The number of bricks needed to strictly pile the top layer into strict triangle(On the left+Need to be on the right+indexPlace1indivual)

        return res

topic

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

1814. Statistics the number of good pairs in an array
medium
86
company
Superior Uber
Give you an array nums ，The array contains only non -negative integers。definition rev(x) The value is an integer x The results obtained by the digital bits are reversed。for example rev(123) = 321 ， rev(120) = 21 。We call the lattering pair of the following conditions (i, j) yes OK ：

0 <= i < j < nums.length
nums[i] + rev(nums[j]) == nums[j] + rev(nums[i])
Please return the number of bidding pairs。Because the result may be great，Please right 109 + 7 Take a surplus Back。

 

Exemplary example 1：

enter：nums = [42,11,1,97]
Output：2
explain：Two coordinates right：
 - (0,3)：42 + rev(97) = 42 + 79 = 121, 97 + rev(42) = 97 + 24 = 121 。
 - (1,2)：11 + rev(1) = 11 + 1 = 12, 1 + rev(11) = 1 + 11 = 12 。
Exemplary example 2：

enter：nums = [13,10,35,24,76]
Output：4
 

hint：

1 <= nums.length <= 105
0 <= nums[i] <= 109

Thinking

这道题没想到yesHash table，还以为yesDouble pointer。
It has been done for a long time，Unexpectedly，Just look at the problem and solve the problem，I also understand。
总之就yes，好对子其实就yes two i - res(i) The same number!
Word gamesa feeling of：

42 + rev(97) = 42 + 79 = 121, 97 + rev(42) = 97 + 24 = 121 。
不就yes 42-res(42) == 97 - res(97) ?？

when*cnt[i-res(i)]*When there is no existence，Will return0.

ans += cnt[i-j]

Thus, incnt[i-j]have2次值的hour候才Will return到ansmiddle
becausecnt[i-j]=1hour，yes不会经过ansAssociated

cnt[i-j] += 1

solution：

·ElementnumsW - rev(num[il)
·Calculate the number of times per element
·Calculate the difference between the number of times each time
@Lazy

code show as below：

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

class Solution:
    def countNicePairs(self, nums: List[int]) -> int:
        def res(num: int) -> int:
            return int(str(num)[::-1])
        cnt = Counter()
        ans = 0
        for i in nums:
            j = res(i)
            # whencnt[i-res(i)]When there is no existence，Will return0.
            ans += cnt[i-j]
            # Thus, incnt[i-j] have2次值的hour候才Will return到ansmiddle
            # becausecnt[]=1hour，yes不会经过ansAssociated
            cnt[i-j] += 1
        return ans % (10 ** 9 + 7)

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

One sentence is composed of a single space between some words and them，And there is no excess space at the beginning and end of the sentence。for example，"Hello World" ，"HELLO" ，"hello world hello world" All sentences。Each word Only Including uppercase and lowercase English letters。

If two sentences sentence1 and sentence2 ，You can insert an arbitrary sentence by one of the sentences（Can be an empty sentence）And get another sentence，Then we call these two sentences similar 。for example，sentence1 = "Hello my name is Jane" and sentence2 = "Hello Jane" ，We can go sentence2 middle "Hello" and "Jane" Insert an intercourse "my name is" get sentence1 。

Give you two sentences sentence1 and sentence2 ，if sentence1 and sentence2 是similar，Please return true ，Otherwise, return false 。

 

Exemplary example 1：

enter：sentence1 = "My name is Haley", sentence2 = "My Haley"
Output：true
explain：Be able to sentence2 middle "My" and "Haley" Insert an intercourse "name is" ，get sentence1 。
Exemplary example 2：

enter：sentence1 = "of", sentence2 = "A lot of words"
Output：false
explain：没法往这Two sentencesmiddle的一个句子Only插入一个句子就get另一个句子。
Exemplary example 3：

enter：sentence1 = "Eating right now", sentence2 = "Eating"
Output：true
explain：Be able to sentence2 Insert at the end "right now" get sentence1 。
Exemplary example 4：

enter：sentence1 = "Luky", sentence2 = "Lucccky"
Output：false
 

hint：

1 <= sentence1.length, sentence2.length <= 100
sentence1 and sentence2 都Only包含大小写英文字母and空格。
sentence1 and sentence2 middle的单词都Only由单个空格隔开。

My solution:

What I think is to make up the judgment of the character on the left or the right, and then delete it，
但是做的过程middle耐心没了，Feeling is a proper footing。

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

class Solution:
    def areSentencesSimilar(self, sentence1: str, sentence2: str) -> bool:
        list1 = sentence1.split(' ')
        list2 = sentence2.split(' ')

        if len(list1) < len(list2):
            temp = list1
            list1 = list2
            list2 = temp
        ans=copy.deepcopy(list2)
        for i in list2:
            for index, j in enumerate(list1):
                if i == j and (index == 0 or index == len(list1) - 1):
                    ans.remove(i)
        if not ans:
            return True
        else:
            return False

Official solution：

According to the meaning，Two sentences sentence1 and sentence2，if是similar，那么这Two sentences按空格分割get的字符串数组 words1
and words2，一定能通过往其middle一个字符串数组middle插入某个字符串数组（Can be empty），get另一个字符串数组。这个验证可以通过Double pointer完成。
i Indicates that the two string array starts from left，At most i The string of the string is the same。
j It means that the remaining string array starts from right，At most j The string of the string is the same。
if i+j It happens to be the length of a string array，那么原字符串就是similar。

1
2
3
4
5
6
7
8
9
10
11

class Solution:
    def areSentencesSimilar(self, sentence1: str, sentence2: str) -> bool:
        words1 = sentence1.split()
        words2 = sentence2.split()
        i, j = 0, 0
        while i < len(words1) and i < len(words2) and words1[i] == words2[i]:
            i += 1
        while j < len(words1) - i and j < len(words2) - i and words1[-j - 1] == words2[-j - 1]:
            j += 1
        return i + j == min(len(words1), len(words2))

1817. Find the number of users of users active

我的answer：

This question is mainlyHash tableKnowledge point，But we can usedefaultdictDo，You can save a few lines of code。
defaultdictIt can assume that existencekeyInitial value，So we only use directlyappend()oradd()Be。
这次和官方answer一模一样呢!

1
2
3
4
5
6
7
8
9
10
11

class Solution:
    def findingUsersActiveMinutes(self, logs: List[List[int]], k: int) -> List[int]:
        dict1 = defaultdict(set)
        list1 = [0] * k
        for i, j in logs:
            dict1[i].add(j)
        for i in dict1:
            print(dict1[i])
            # TypeError object of type ‘type‘ has no len() Because ofdictLess1
            list1[len(dict1[i]) - 1] += 1
        return list1

https://leetcode.cn/problems/number-of-different-subsequences-gcds/solutions/?orderBy=most_votes

answer ：

Because the number of non -empty sequences is as high as

$$
2^n-1
$$

，Back traceability is overtime。May wish to change a perspective，Consider the value domain。

The maximum number of multiple numbers is equal to g，Conversely explaining these numbers are all g Multiple。For example [8,12,6] The maximum number of contracts is 2，These numbers are all 2 Multiple。

So，Can you reverse，enumerate g Multiple呢？

1,2,3,
2,4,6,⋯
3,6,9,⋯
It seems that the running time is a square level，Timeout。
⌊
1
U
​
⌋
Don’t rush to deny，There are some math here。
set up U=max(nums)，So 1 Multiple需要enumerate $⌊U1⌋\left\lfloor\dfrac{U}{1}\right\rfloor⌊
1
U
​
⌋ $indivual，222 Multiple需要enumerate ⌊U2⌋\left\lfloor\dfrac{U}{2}\right\rfloor⌊2 U ​ ⌋ indivual，……，Add these，Remove it and take it up，have4

$$⌊U1⌋+⌊U2⌋+⋯+⌊UU⌋≤U⋅(11+12+⋯+1U) \left\lfloor\dfrac{U}{1}\right\rfloor + \left\lfloor\dfrac{U}{2}\right\rfloor +\cdots + \left\lfloor\dfrac{U}{U}\right\rfloor \le U\cdot\left(\dfrac{1}{1} + \dfrac{1}{2} + \cdots + \dfrac{1}{U}\right)$$

The one in the bracket on the right is called Harmonic，Can be seen as $$O(log⁡U)O(\log U)O(logU)$$ of，因此enumerate倍数of时间复杂度为 $$O(Ulog⁡U)O(U\log U)O(UlogU)$$，不Timeout。

So就enumerate $$i=1,2,⋯ ,Ui=1,2,\cdots,Ui=1,2,⋯,U$ Its multiple，当作子序列middleof数。

子序列middleof数越多，g The smaller it may be，The more likely i。
For example，如果enumerate i=2 Multiple，in 8 and 12 In $$nums\textit{nums}nums$$ middleof，Due to 8 and 12 of最大公约数等于 4，所以无法找到一indivual子序列，Its maximum number i。但如果还have 6 Also $$nums\textit{nums}nums$$ middle，So最大公约数等于 2，so i 就可以是一indivual子序列of最大公约数了。

Code implementation，Need to use hash tables or array，记录每indivual数是否在 $$nums\textit{nums}nums$$ middle，So as to speed up judgment。数组of效率会更高一些。

https://leetcode.cn/problems/number-of-different-subsequences-gcds/solutions/2061079/ji-bai-100mei-ju-gcdxun-huan-you-hua-pyt-get7/?orderBy=most_votes

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：

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

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;