6293. Count the number of good array

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

At first glance, this question is a double pointer，But I am not familiar with the double pointer，Most of the time was wasted when you set up the framework。

This question is the third question of Zhou Sai，The first two questions were killed quickly，But because I slept，It’s only half an hour left when the computer is turned on。

always theredebug，Watch this afternoon0x3fSolution。There is a set of explanations of his sliding window algorithm and double pointer。

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
from collections import Counter
from itertools import count
from typing import List


class Solution:
    def countGood(self, nums: List[int], k: int) -> int:
        start = 0
        tail = 0
        flag = 0
        if len(set(nums)) == 1:
            if k > len(nums) * (len(nums)-1) // 2:
                return 0
        while start < len(nums) - 1:
            x = Counter(nums[start:tail])
            if len(x) >= k:
                flag2 = 0
                for j in x:
                    if x[j] >= k:
                        flag2 += 1
                if flag2 >= k:
                    flag += 1
            else:
                for i in x:
                    if x[i] * (x[i] - 1) // 2 >= k:
                        flag += 1
            if tail != len(nums):
                tail += 1
            else:
                start += 1

        return flag

show all >>

6275. Make all the minimum operations of all elements in the array II

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

2023-01-22 (1).png
6275. Make all the minimum operations of all elements in the array II

Thought:

Weekly Two Questions！！！

·First use the list derivative to calculate the difference between each element。
·Then，Initialize a counter to track the required operations required。
·The difference between traversing，And check whether each difference can be removed。
·if not，Then return -1，Because the array cannot be equal to the given operation。
·If it is eliminated，It removes the absolute value of the difference to add to the counter。
·at last，It returns the required number of operations。

for example：[3,0,-6,3]It is every positive number divided by3In harmony，Tested many times，是因为at last一种特殊情况（When two list items, etc.）No consideration。

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def minOperations(self, nums1: List[int], nums2: List[int], k: int) -> int:
        if k <= 0:
            if nums1 != nums2:
                return -1
            else:
                return 0
        diff = [nums1[i] - nums2[i] for i in range(len(nums1))]
        if sum(diff) != 0:
            return -1
        if sum(diff) % k != 0:
            return -1
        operations = 0
        for index, d in enumerate(diff):
            if d % k != 0:
                return -1
            if d > 0:
                operations += d // k
        return operations

show all >>

6323. Child that divides money the most

字数统计: 510字   |   阅读时长: 3min

topic：

I met for the first time：’2023/3/19-16:51’
screenshot2023-09-22 afternoon11.42.18.png
6323. Child that divides money the most.md

Thought：

“————–”

This question is the first half of the year3月份的时候的周赛topic，topic链接：6323

“————–”

I found that this is a mathematical problem at the beginning，I wrote for a long time, I don’t know how to deal with the last money left。
So I wrote a list，One child and one child gives money。
math：
If the remaining 0 people，and money>0，Then you must be divided into one that has been divided 8 Dollar的people，
ans minus one。
If the remaining 1 people，and money=3，To avoid allocation 4 Dollar，
Then you must be divided into one that has been divided 8 Dollar的people，ans minus one。
其它情况全部给一个people，if这个people分配到 4 Dollar，
他再给另一个people 1 Dollar，so ans constant。

The following isylbExplanation of big guys：（2023-9-22renew）
if money<children，Then there must be children who do not share money，return −1。

if money>8×children，So children−1 A child obtained 8 Dollar，剩下的一A child obtained money−8×(children−1) Dollar，return children−1。

if money=8×children−4，So children−2 A child obtained 8 Dollar，The remaining two children sharing the rest 12 Dollar（As long as not 4, 8 Dollar就行），return children−2。

if，We assumed that there are x A child obtained 8 Dollar，Then the rest of the money is money−8×x，As long as it is guaranteed to be greater than equal to the remaining number of children children−x，You can satisfy the meaning。therefore，We just need to ask x Maximum value，That is the answer。

Code：

List
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def distMoney(self, money: int, children: int) -> int:
        money -= children
        children_list = [1] * children
        if money < 0:
            return -1
        counts = min(money // 7, children)
        for i in range(counts):
            children_list[i] = 8
        children_list[-1] += money - counts * 7
        counts = children_list.count(8)
        if children_list[-1] == 4:
            if children_list[-2] != 8:
                pass
            else:
                counts -= 1
        return counts
math
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def distMoney(self, money: int, children: int) -> int:
        money -= children  # 每people至少 1 Dollar
        if money < 0: return -1
        ans = min(money // 7, children)  # Preliminary allocation，让尽量多的people分到 8 Dollar
        money -= ans * 7
        children -= ans
        # children == 0 and money：Must find a previous division 8 Dollar的people，After allocating the remaining money
        # children == 1 and money == 3：不能有people恰好分到 4 Dollar
        if children == 0 and money or \
           children == 1 and money == 3:
            ans -= 1
        return ans
ylb
1
2
3
4
5
6
7
8
9
class Solution:
    def distMoney(self, money: int, children: int) -> int:
        if money < children:
            return -1
        if money > 8 * children:
            return children - 1
        if money == 8 * children - 4:
            return children - 2
        return (money-children) // 7

show all >>

6300. Minimum public value

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

2023-01-22 (2).png
6300. Minimum public value

Thought：

Originally intending to use the meta group one by one to find one by one，But timeout。
Then useintersectionFunction inO(1)Solution at time complexity

Code：

1
2
3
4
5
6
class Solution:
    def getCommon(self, nums1: List[int], nums2: List[int]) -> int:
        common = set(nums1).intersection(nums2)
        if common:
            return min(common)
        return -1

show all >>

6324. Maximize the great value of the array

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

topic：

6324. Maximize the great value of the array.md
Give you a bidding 0 Started integer array nums 。You need to nums Re -arrange into a new array perm 。

definition nums of Great value To satisfy 0 <= i < nums.length and perm[i] > nums[i] of下标数目。

Please return to re -arrangement nums 后of maximum Great value。

Exemplary example 1：

enter：nums = [1,3,5,2,1,3,1]
Output：4
explain：A optimal arrangement scheme is perm = [2,5,1,3,3,1,1] 。
The bidding is 0, 1, 3 and 4 Place，All perm[i] > nums[i] 。So we return 4 。

Thought：

Three ways to think about this question：
The first is Tian Ji horse racing（I am）： InumsContinuously reappear，Advance numbers，Then compare（time out）
Then there is a double pointer-Hash table：
每个元素只能被bigof元素指向一次（for example5Compare3big，3Can’t follow4对Compare了）
Two pointers point to the tail element at the same time，whenleft not less than rightof时候，left–。
else left– right– Counter– count ++
Last returncount
灵神ofTian Ji horse racing：
sort后直接在原数组上面找Comparewhen前元素bigof元素

Code：

I am
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def maximizeGreatness(self, nums: List[int]) -> int:
        nums.sort()
        nums_source.sort()
        max_count = 0
        
        # when新数组与旧数组相同时，Stop loop
        for _ in range(len(nums)):
             nums_source = nums_source[1:] + [nums_source[0]]
             print(nums_source, nums)
             count = 0
             for i in range(len(nums)):
                 if nums_source[i] > nums[i]:
                     count += 1
                     print(count)
             max_count = max(max_count, count)
        return max_count
Double pointer+Hash table
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 maximizeGreatness(self, nums: List[int]) -> int:
        nums.sort()
        #print(nums)
        left = len(nums) - 1
        dicts = Counter(nums)
        count = 0
        right = left
        while right >= left >= 0:
            if nums[right] <= nums[left]:
                left -= 1
            if nums[right] > nums[left]:
                if dicts[nums[left]] > 0:
                    dicts[nums[left]] -= 1
                    left -= 1
                    right -= 1
                    count += 1
                    #print(dicts, nums, count)
                else:
                    left -= 1
            elif right == 0 or left == 0:
                break

        return count
Tian Ji horse racing
1
2
3
4
5
6
7
8
class Solution:
    def maximizeGreatness(self, nums: List[int]) -> int:
        nums.sort()
        i = 0
        for x in nums:
            if x > nums[i]:
                i += 1
        return i

show all >>

6338. Number of methods of monkey collision Weekly

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

2023-01-29 (1).png
6338. Number of methods of monkey collision

Thought：

纯math问题，that is$2^n - 2$。butnAt most$10^9$So big，Return directly to timeout。
所以用了Fast power算法，

使用Fast power算法来降低计算 2^n Time complexity。
it’s here，We use variables x To store 2^n，And in each cycle x square。when n When you are a miracle，We will take the result to take the result x。This can be calculated in each cycle2^n。
Before returning the result，We need to use(res-2)%mod Remove the border situation

Code：

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def monkeyMove(self, n: int) -> int:
        mod = 10**9 + 7
        res = 1
        x = 2
        while n > 0:
            if n % 2 == 1:
                res = (res * x) % mod
            x = (x * x) % mod
            n = n // 2
        return (res-2) % mod

show all >>

6331The most prizes won in the two lines make()usage

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

topic

2023-02-05 (1).png
6331. The most prizes won in the two lines

Thought

make
make() yes Go Built -in function of language memory distribution，There are three parameters default。

1
make(Type, len, cap)

Type：type of data，Necessary parameters，Type 的值只能yes slice、 map、 channel 这三种type of data。
len：type of data实际占用的内存空间长度，map、 channel yesOptional parameter，slice yesNecessary parameters。
cap：为type of data提前预留的内存空间长度，Optional parameter。
所谓的提前预留yes当前为type of data申请内存空间的时候，Apply for additional memory space in advance，This can avoid the overhead brought by the second allocation of memory，Greatly improve the performance of the program。
You have such doubts when you see here，Since the size of the data has been specified at the time of initialization，Then why do you still specify the reserved size?？
这yes因为 make() 使用的yes一种动态数组算法，At first apply to the operating system for a small piece of memory，
这个就yes cap，wait cap quilt len After the occupation is full, you need to expand the capacity，
扩容就yes动态数组再去向操作系统申请当前长度的两倍的内存，Then copy the old data to the new memory space。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func maximizeWin(prizePositions []int, k int) (ans int) {
	n := len(prizePositions)
	pre := make([]int, n+1)
	left := 0
	for right, v := range prizePositions {
		for v-prizePositions[left] > k {
			left++
		}
		ans = max(ans, right-left+1+pre[left])
		pre[right+1] = max(pre[right],right-left+1)
	}
	return ans
}

func max(a, b int) int {
	if b > a {
		return b
	}
	return a
}

show all >>

6347Number of vowel string within the scope of statistics

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

topic

2023-02-05 (2).png

Thought：

Pay attention to pre -processing and prefixing
Prefix and an algorithm，Used to find the prefix and the array。The prefix and definition of the array are defined as the harmony of the prefix element in a certain position of the array。in other words，The prefix and the elements of each position of an array are added to the previous element。

This code uses prefix and to optimize the query process。It pre -processed whether the first letter of each word is a meta sound，Then save these results in a list。Then，It uses prefix and calculate each query result。

Specifically，For each query (i, j)，It will be statistics from words[i] arrive words[j] Conditional conditions（The first letter is a Yuan Yin）Number of words。This can be used by using counts[j+1] - counts[i] To be done。This is because counts[j+1] Contain words[0] arrive words[j] Conditional conditionsNumber of words，and counts[i] Contain words[0] arrive words[i-1] Conditional conditionsNumber of words。therefore，counts[j+1] - counts[i] That words[i] arrive words[j] Conditional conditionsNumber of words。

In the code，counts Arrays use prefix and pre -processing，therefore可以在 O(1) Calculate the results of each query within time。This makes the total running time of the code from coming from O(n^2) Fall to O(n)

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def vowelStrings(self, words: List[str], queries: List[List[int]]) -> List[int]:
        yuanyin = {'a', 'e', 'i', 'o', 'u'}
        ans = []
        for i, j in queries:
            count = 0
            for x in range(i, j + 1):
                if words[x][0] in yuanyin and words[x][-1] in yuanyin:
                    count += 1
            ans.append(count)
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def vowelStrings(self, words: List[str], queries: List[List[int]]) -> List[int]:
        yuanyin = set('aeiou')
        # Traversing each word，Determine whether its first letter is a metaphysical sound
        # Save the results in words_first_last List
        words_first_last = [(word[0] in yuanyin, word[-1] in yuanyin) for word in words]
        # Create counts List，Used to store prefixes and
        counts = [0] * (len(words) + 1)
        # Traversing each word，Calculate prefix and
        for i in range(len(words)):
            counts[i + 1] = counts[i] + int(words_first_last[i][0] and words_first_last[i][1])
        # Traversing each query，Calculate the result of the query
        ans = [counts[j + 1] - counts[i] for i, j in queries]
        # Return result
        return ans

show all >>

6351. The scores of the array after the marking all elements

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

topic：

6351. The scores of the array after the marking all elements.md
Give you an array nums ，It contains several positive integers。

Start score score = 0 ，Please find the final score according to the algorithm below：

Select the smallest and not marked integer from the array。If there are equal elements，Choose one with the smallest bidding。
Add the selected integer to score middle。
mark 被选middle元素，If there are adjacent elements，则同时mark Two elements adjacent to it 。
重复此过程直到数组middle所有元素都被mark。
Please return to the final score after executing the above algorithm。

Exemplary example 1：

enter：nums = [2,1,3,4,5,2]
Output：7
explain：我们按照如下步骤mark元素：

  • 1 是最小未mark元素，所以mark它和相邻两个元素：[2,1,3,4,5,2] 。
  • 2 是最小未mark元素，所以mark它和左边相邻元素：[2,1,3,4,5,2] 。
  • 4 是仅剩唯一未mark的元素，所以我们mark它：[2,1,3,4,5,2] 。
    Total score 1 + 2 + 4 = 7 。

Thought：

Direct violence，Then it’s timeout，But I feel like the answer is quite violent。

Code：

I am
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def findScore(self, nums: List[int]) -> int:
        while set(nums) != {inf}:
            print(nums)
            mm = min(nums)
            min_index = nums.index(mm)
            grade += mm
            nums[min_index] = inf
            if min_index > 0:
                nums[min_index - 1] = inf
            if min_index < len(nums) - 1:
                nums[min_index + 1] = inf
        return grade
Spirit Sorting
1
2
3
4
5
6
7
8
9
10
class Solution:
    def findScore(self, nums: List[int]) -> int:
        ans = 0
        vis = [False] * (len(nums) + 2)  # Guarantee the bidding does not cross the boundary
        for i, x in sorted(enumerate(nums, 1), key=lambda p: p[1]):
            if not vis[i]:
                vis[i - 1] = True
                vis[i + 1] = True  # mark相邻的两个元素
                ans += x
        return ans

show all >>

76Minimum cover string

字数统计: 752字   |   阅读时长: 4min

topic：

2023-02-05 (3).png
76. Minimum cover string

Thought：

Not existtWhen all elements are，Right shift right shift
ExisttWhen all elements are，Left finger shift right，If the right pointer does not reach the far right，Continue to move the right pointer
If you findt，Jump back

optimization：

The code finds the minimum length window in string s that contains all the characters in string t. The code uses two pointers, left and right, to traverse s and keep track of the window. The isAll function checks if the characters in t are present in the current window.
To improve the code, consider the following:
Use a dict dict_keys instead of the isAll function to track the count of each character in the current window, and update the count directly instead of using Counter function repeatedly.
Remove unused variables ans, hash_1, and dict_t.
Initialize right outside the loop, and use while right < len(s) and not isAll(dict_keys, dict_t) as the loop condition to terminate when all characters in t are present in the current window.
Keep track of the minimum window length and the start and end indices of the window, and return s[start:end + 1] at the end.
get()Method grammar：

dict.get(key[, value])

parameter

key -- The key to find in the dictionary。
value -- Optional，If the value of the specified key does not exist，Back to the default value。
return value
Return to the value of the specified key，If the key is not in the dictionary, the silent recognition value None Or the default value set。

Instance

以下Instance展示了 get() How to use the function：

Instance

1
2
3
4
5
6
7
8
9
10
11
12
#!/usr/bin/python
# -*- coding: UTF-8 -*-

tinydict = {'Name': 'Runoob', 'Age': 27}

print ("Age : %s" %  tinydict.get('Age'))

# no setting Sex，也no setting默认的值，Output None
print ("Sex : %s" %  tinydict.get('Sex'))  

# no setting Salary，Output默认的值  0.0
print ('Salary: %s' % tinydict.get('Salary', 0.0))

Code：

Mine
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
class Solution:
    def minWindow(self, s: str, t: str) -> str:
        ans = 1000001
        hash_1 = {}

        def isAll(dict_keys, target):
            for i in target:
                if i not in dict_keys:
                    return False
                else:
                    if dict_keys[i] < target[i]:
                        return False
            return True

        dict_t = Counter(t)
        left = 0
        right = 0
        while right < len(s):
            # Not existtWhen all elements are，Right shift right shift
            # ExisttWhen all elements are，Left finger shift right，If the right pointer does not reach the far right，Continue to move the right pointer
            # If you findt，Jump back
            dict1 = Counter(s[left:right + 1])
            # If there is any element
            if isAll(dict1, dict_t):
                ans = min(ans, right - left + 1)
                hash_1[right - left + 1] = s[left:right+1]
                print(ans, hash_1)
                left += 1
            else:
                right += 1
            print(ans, hash_1, dict1.keys())
        return hash_1[ans] if len(hash_1) != 0 else ""
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
class Solution:
    def minWindow(self, s: str, t: str) -> str:
        # storagetThe number of each character in the string
        dict_t = Counter(t)
        # storage当前滑动窗口middle的字符
        dict_keys = {}
        # Left pointer and right pointer
        left = 0
        right = 0
        # Record minimum length
        min_len = float('inf')
        # Record the starting position and end of the shortest string
        start = 0
        end = 0
        # Right pointer0arrivelen(s) - 1Slide
        while right < len(s):
            # If the current character is intmiddle，则把它加入当前滑动窗口的字典middle
            if s[right] in dict_t:
                dict_keys[s[right]] = dict_keys.get(s[right], 0) + 1
            # 如果当前滑动窗口middle包含了tmiddle的所有字符
            while right < len(s) and isAll(dict_keys, dict_t):
                # If the current length is less than the minimum length of the previous record，Update the minimum length and start position and end position
                if right - left + 1 < min_len:
                    min_len = right - left + 1
                    start = left
                    end = right
                # Left finger shift right，把当前字符从当前滑动窗口的字典middle移除
                if s[left] in dict_keys:
                    dict_keys[s[left]] -= 1
                    if dict_keys[s[left]] == 0:
                        del dict_keys[s[left]]
                left += 1
            right += 1
        # Return to the shortest string，If not, return the empty string
        return s[start:end + 1] if min_len != float('inf') else ""

def isAll(dict_keys, target):
    for key in target:
        if key not in dict_keys or dict_keys[key] < target[key]:
            return False
    return True

show all >>