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

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

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

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

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

    1333.Restaurant filter

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

    topic：

    screenshot2023-09-27 afternoon3.45.32.png

    1333.Restaurant filter.md

    Thought：

    This is the beginningpopThought，But time complexity is too high，400ms，It is later changed to a list derivative。
    I think of the senior said，pop()The running time is okay，But once the index is added inside，It will be particularly slow。
    sorted and lambda Usage：
    lambdayesPythonAnonymous function in。it’s here，lambda x: (x[1], x[0])Definitions a acceptance of an elementx（in this case，xyesrestaurantsA list in the list）And return a tuple(x[1], x[0])The function。

    this means，Sort首先基于每个子列表的第二个元素x[1]，Then based on this basisx[0]。in other words，It first followsx[1]进行Sort，ifx[1]same，According tox[0]进行Sort。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    while ind < len(restaurants):
         i = restaurants[ind]
         if veganFriendly == 1 and i[2] == 0:
             restaurants.pop(ind)
         elif maxPrice < i[3]:
             restaurants.pop(ind)
         elif maxDistance < i[4]:
             restaurants.pop(ind)
         else:
             ind += 1

    Code：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    class Solution:
        def filterRestaurants(self, restaurants: List[List[int]], veganFriendly: int, maxPrice: int, maxDistance: int) -> \
                List[int]:
            restaurants = [
                i for i in restaurants
                if (veganFriendly == 0 or i[2] == veganFriendly)
                   and i[3] <= maxPrice
                   and i[4] <= maxDistance
            ]
            restaurants = sorted(restaurants, key=lambda x: (x[1], x[0]), reverse=True)
            return [i[0] for i in restaurants]

    show all >>

    1253.Reconstruct 2 Line binary matrix

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

    topic：

    [1253]Reconstruct 2 Line binary matrix.md
    Reconstruct 2 Line binary matrix

    Thought：

    At first I read the wrong question again，Thought it wascolsumDivideupper and lower两个Array，
    The result iscolsum[i]Divideupper[i] and lower[i]Two numbers。
    andupper[i]andlower[i]的and等于colsum[i]。
    In each cycle，ObtaincolsumValue，Then judge0，1，2仨 仨，0Ignore，2If you allocate it on average。
    1if，直接给当前最小的那个Array。（I use hereupperandlowerThe parameters of itself to record the remaining numbers）。
    Determine at the beginningif sum(colsum) != upper + lower， Final judgmentif upper + lower != 0。

    At first, I misunderstood the question again, thinking that it was about dividing colsum into two arrays, upper and lower. However, it turned out that it was about dividing colsum[i] into two numbers, upper[i] and lower[i]. Additionally, the sum of upper[i] and lower[i] should be equal to colsum[i].
    In each iteration, the value of colsum is obtained, and then three scenarios, 0, 1, and 2, are considered. If it’s 0, it is ignored. If it’s 2, the values are evenly distributed. If it’s 1, it is assigned to the array with the current minimum value (using the remaining numbers in upper and lower than parameters).
    At the beginning, it is checked whether if sum(colsum) != upper + lower, and finally, it is checked whether if upper + lower != 0.

    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 reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:
            if sum(colsum) != upper + lower:
                return []
            upper_list = [0] * len(colsum)
            lower_list = [0] * len(colsum)
            for i in range(len(colsum)):
                if colsum[i] == 0:
                    continue
                if colsum[i] == 2:
                    upper_list[i] = 1
                    lower_list[i] = 1
                    upper -= 1
                    lower -= 1
                else:
                    if upper >= lower:
                        upper_list[i] = 1
                        upper -= 1
                    else:
                        lower_list[i] = 1
                        lower -= 1
            if upper != 0 or lower != 0:
                return []
            return [upper_list, lower_list]

    show all >>

    1460.Class ScheduleIV

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

    topic：

    img_2.png

    [1460]Class ScheduleIV.md

    Thought：

    一开始的想法是构建有向picture，然后在有向picture中找到queryDoes the two points have a father -son relationship?。
    But watchylbAfter the answer，I find that the accessability is faster first。
    First traversalprerequirements，Record all the accessibility。
    Then triple cycle，Connect all the availability。

    i->j->k，ifi->k，Soi->kIt is。

    Code：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    class Solution:
        def checkIfPrerequisite(self, n: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[
            bool]:
            f = [[False] * n for _ in range(n)]
            for a, b in prerequisites:
                f[a][b] = True
            for k in range(n):
                for i in range(n):
                    for j in range(n):
                        f[i][j] = f[i][j] or (f[i][k] and f[k][j])
            return [f[a][b] for a, b in queries]

    show all >>