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 >>

Python beat98.40% collectionsofCounter method！

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

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空间存储若干变量。

show all >>

704. Two -point search

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

https://leetcode.cn/leetbook/read/learning-algorithms-with-leetcode/xsshgi/
Not difficult，Just recursive to take a note

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        def recursion(nums, left, right, target):
            if left > right:
                # Recursive end
                return -1
            mid = left + (right - left) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
            return recursion(nums, left, right, target)

        left = 0
        right = len(nums) - 1
        return recursion(nums, left, right, target)

https://leetcode.cn/leetbook/read/learning-algorithms-with-leetcode/xssbke/

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
# The guess API is already defined for you.
# @param num, your guess
# @return -1 if num is higher than the picked number
#          1 if num is lower than the picked number
#          otherwise return 0
# def guess(num: int) -> int:

class Solution:
        def guessNumber(self, n: int) -> int:
            def recursion(nums, left, right):
                if left > right:
                    # Recursive end
                    return -1
                mid = left + (right - left) // 2
                if guess(mid) == 0:
                    return mid
                elif guess(mid) == 1:
                    left = mid + 1
                else:
                    right = mid - 1
                return recursion(nums, left, right)

            left = 1
            right = n
            return recursion(n, left, right)

show all >>

977.Orderly array square

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

topic：

Press you Non -reduced order Sorting integer array nums，return Each number square New array of composition，The request is also pressed Non -reduced order Sort。

 

Exemplary example 1：

enter：nums = [-4,-1,0,3,10]
Output：[0,1,9,16,100]
explain：After，Array becomes [16,1,0,9,100]
Sort后，Array becomes [0,1,9,16,100]

Exemplary example 2：

enter：nums = [-7,-3,2,3,11]
Output：[4,9,9,49,121]

 

hint：

  • 1 <= nums.length <= 104
  • -104 <= nums[i] <= 104
  • nums Pressed Non -reduced order Sort

 

Advance：

  • PleaseDesign time complexity is O(n) The algorithm solves this problem
Related Topics
  • Array
  • Double pointer
  • Sort

  • 👍 777
  • 👎 0
    • [977.Orderly array square.md]()

    Thought：

    I originally planned to write an insertion after each calculation was calculated，The result is timeout。IgnoresortPuzzle。

    Code：

    1
    2
    3
    4
    5
    6
    7
    class Solution:
        def sortedSquares(self, nums: List[int]) -> List[int]:
            nu = []
            for i in nums:
                nu.append(i * i)
            nu.sort()
            return nu

    show all >>

    Sword finger Offer 43. 1～n Integer 1 Number of times

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

    Sword finger Offer 43. 1～n Integer 1 Number of times

    1
    2
    3
    4
    5
    6
    7
    8
    class Solution:
        def countDigitOne(self, n: int) -> int:
            mulk = 1
            ans = 0
            while n >= mulk:
                ans += (n//(mulk * 10)) * mulk + min(max(n % (mulk * 10) - mulk + 1, 0), mulk)
                mulk *= 10
            return ans

    That day, I made a set of Xiaomi measurement questions.，The first one is calculation1～nmiddle1Number of times。

    Deduction的题号yesSword fingeroffer 43
    nyes12in the case of，1 10 11 12middle就出现了5Second-rate1。

    因为那套题middle选择题都yes简单难度，So naturally I want to use violent algorithm to crack。

    但yes拿到Deductionmiddle找相同的题的时候却发现标签yesdifficulty[Be ashamedR]。Surmo after timeout[picture2]。

    Then I actually thought about it directly with mathematical methods，But why too lazy, don’t want to find the rules，[picture三]yes标答，I feel that I have to sink in the future and slowly go to do it.。
    #Deduction #algorithm#Deductionalgorithm #Python

    Error answer：

    []class Solution:
    1
    2
    3
    4
    5
    6
    7
    def countDigitOne(self, n: int) -> int:
        flag = 0
        for i in range(1, int(n)+1):
            for j in ''.join(str(i)):
                if j == '1':
                    flag += 1
        return flag

    show all >>

    121.The best time for buying and selling stocks

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

    topic：

    screenshot2023-10-01 afternoon6.24.27.png

    2251.The number of flowers during the flowering period.md

    Thought：

    Dynamic planning，Find the least problem
    Minority problem：FirstiThe maximum profit of heaven = max(Firsti-1The maximum profit of heaven, FirstiHeavenly price - forwardi-1The minimum price of heaven)

    Code：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    class Solution:
        def maxProfit(self, prices: List[int]) -> int:
            # Minority problem：FirstiThe maximum profit of heaven = max(Firsti-1The maximum profit of heaven, FirstiHeavenly price - forwardi-1The minimum price of heaven)
            dp = [0] * len(prices)
            min_price = prices[0]
            for i in range(1, len(prices)):
                dp[i] = max(dp[i - 1], prices[i] - min_price)
                min_price = min(min_price, prices[i])
            return dp[-1]

    show all >>

    1222.Can attack the queen of the king

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

    topic：

    screenshot2023-09-15 morning12.10.07.png
    topic链接

    Thought：

    直接simulation，Determine horizontal，Vertical，Whether the queen on the diagonal line exists，if it exists，Just record，Last return。

    The answer method is similar to mine，But more concise，Go out of the king，The first queen that recording encountered。

    Code：

    I am
    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
    42
    43
    44
    45
    46
    class Solution:
        def queensAttacktheKing(self, queens: List[List[int]], king: List[int]) -> List[List[int]]:
            x = king[0]
            y = king[1]
            x_left_diff = 64
            x_right_diff = 64
            left_high_diff = 64
            left_low_diff = 64
            right_high_diff = 64
            right_low_diff = 64
            y_left_diff = 64
            y_right_diff = 64
            res = [[]] * 8
            print(res)
            for i, j in queens:
                # Horizontal
                if i == x:
                    if j < y and abs(j - y) < x_left_diff:
                        res[0] = [i, j]
                        x_left_diff = abs(j - y)
                    elif j > y and abs(j - y) < x_right_diff:
                        res[1] = [i, j]
                        x_right_diff = abs(j - y)
                # Vertical
                elif j == y:
                    if i < x and abs(i - x) < y_left_diff:
                        res[6] = [i, j]
                        y_left_diff = abs(i - x)
                    elif i > x and abs(i - x) < y_right_diff:
                        res[7] = [i, j]
                        y_right_diff = abs(i - x)
                # Diagonal
                elif abs(i - x) == abs(j - y):
                    if i < x and j < y and abs(i - x) < left_high_diff:
                        res[2] = [i, j]
                        left_high_diff = abs(i - x)
                    elif i < x and j > y and abs(i - x) < left_low_diff:
                        res[3] = [i, j]
                        left_low_diff = abs(i - x)
                    elif i > x and j < y and abs(i - x) < right_high_diff:
                        res[4] = [i, j]
                        right_high_diff = abs(i - x)
                    elif i > x and j > y and abs(i - x) < right_low_diff:
                        res[5] = [i, j]
                        right_low_diff = abs(i - x)
            return [i for i in res if i != []]
    Answer
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    class Solution:
        def queensAttacktheKing(self, queens: List[List[int]], king: List[int]) -> List[List[int]]:
            s = set(map(tuple, queens))
            ans = []
            for dx, dy in (1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1):
                x, y = king[0] + dx, king[1] + dy
                while 0 <= x < 8 and 0 <= y < 8:
                    if (x, y) in s:
                        ans.append([x, y])
                        break
                    x += dx
                    y += dy
            return ans

    show all >>

    122.The best time for buying and selling stocksII

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

    topic：

    screenshot2023-10-02 afternoon11.16.25.png

    122.The best time for buying and selling stocksII.md

    Thought：

    I can forget that the price will be reduced the price one day after the first day.，Thinking is to build the minimum child。
    Then I found that it seems a bit complicated，Have done it again（2023.1.13），I found out that it seems that only one line can be done。

    Code：

    1
    2
    3
    class Solution:
        def maxProfit(self, prices: List[int]) -> int:
            return sum(max(0, prices[i] - prices[i - 1]) for i in range(1, len(prices)))

    show all >>