1604Warn alert person who uses the same employee card within one hour One question daily

字数统计: 251字   |   阅读时长: 1min

topic

2023-02-08.png

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

show all >>

1664. Number of schemes to generate balance numbers One question daily

字数统计: 235字   |   阅读时长: 1min

1674887518406.png
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

slice
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
官方answer
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

show all >>

1663. The smallest string with a given value One question daily

字数统计: 315字   |   阅读时长: 1min

2023-01-26.png
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：

[]First time(time out)
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
[]Second attempt（500ms）
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))))
[]Optimal solution（100ms）
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)

show all >>

1669. Merge two linked watches One question daily

字数统计: 163字   |   阅读时长: 1min

topic：

1675057199631.png
1669. Merge two linked watches

Thought：

直接放上官方answer了，就yes模拟Linked。

topic要求将 list1
First a arrive b Delete all nodes，Replace it for list2
。therefore，我们首先找arrive list1
B a−1 Node preA，As well as b+1 Node aftB。because 1≤a≤b<n−1
（in n yes list1 length），so preA and aftB yes一定存在of。

Then we let us give up preA of next direction list2
of头节点，Give up list2
of尾节点of next direction aftB To。

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None
class Solution:
    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:
        preA = list1
        for _ in range(a-1):
            preA = preA.next
        preB = preA
        for _ in range(b - a + 2):
            preB = preB.next
        preA.next = list2
        while list2.next:
            list2 = list2.next
        list2.next = preB
        return list1

show all >>

1798You can construct the maximum number of continuity One question daily

字数统计: 193字   |   阅读时长: 1min

topic：

2023-02-05.png
1798. You can construct the maximum number of continuity

Thought：

4A052176419779588F1300C93180C44A.png
img.png
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
}

show all >>

1801-1803 Liech buckle novice！

字数统计: 427字   |   阅读时长: 2min

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

show all >>

1813. Sentence similarity III

字数统计: 625字   |   阅读时长: 3min 
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))

show all >>

1814. Statistics the number of good pairs in an array One question daily

字数统计: 391字   |   阅读时长: 2min

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)

show all >>

1817. Find the number of users of users active One question daily

字数统计: 108字   |   阅读时长: 1min

2023-01-21.png

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

show all >>

1819.Different numbers in the sequence

字数统计: 440字   |   阅读时长: 2min

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

2023-01-20 (1).png

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

show all >>