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

topic：

I met for the first time：’2023/3/19-16:51’

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：

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

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

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

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：

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

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

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

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

topic

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
}

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

topic

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

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：

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

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

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

Pyhton collection In the bag Counter() Be rightlist里出现of元素conduct计数，And the output is a dictionary。
for examplenums=[1, 1, 1, 2, 2, 3] ToCounter后of结果是Counter({1: 3, 2: 2, 3: 1})。

1. So traverse a dictionary，whenvalue>3of时候value=2，Can be greater than2indivualof元素计数become2indivual。
2. So we willCounter({1: 3, 2: 2, 3: 1})becomeCounter({1: 2, 2: 2, 3: 1})后再Toelementsconductlist操作就可以得到改变后of列表了。

Due to the meaning of the question“Input the array「Quote」方式传递of”，So we willnumsJust fill in and fill in

1
2
3
4
5
6
7
8
9
10
11

from collections import Counter # Imported package
class Solution:
    def removeDuplicates(self, nums: List[int]) -> List[int]:
        dict1 = Counter(nums)
        for i in dict1:
            if dict1[i] > 2:
                dict1[i] = 2
        list1 = list(dict1.elements())
        nums.clear() # clear the list
        nums.extend(list1) # Add the collection to the list
        return len(nums)

Complexity analysis

time complexity：O(n)，in n 是数组of长度。We have a maximum of this array once。

Spatial complexity：O(1)。我们只需要常数of空间存储若干变量。