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

    1017. Negative binary conversion

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

    topic：

    1017. Negative binary conversion

    Thought：

    The difference from binary is just not always//2，It’s every number//-1

    Code：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    class Solution:
        def baseNeg2(self, n: int) -> str:
            k = 1
            ans = []
            while n:
                if n % 2:
                    ans.append('1')
                    n -= k
                else:
                    ans.append('0')
                n //= 2
                k *= -1
            return ''.join(ans[::-1]) or '0' 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    impl Solution {
        pub fn base_neg2(mut n: i32) -> String {
            let mut ans = Vec::new();
            while n != 0 {
                if n % 2 != 0 {
                    ans.push('1');
                    n = (n - 1) / -2;
                } else {
                    ans.push('0');
                    n /= -2;
                }
            }
            if ans.is_empty() {
                ans.push('0');
            }
            ans.reverse();
            ans.iter().collect()
        }
    }

    show all >>

    1017.Negative binary conversion

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

    topic：

    Give you an integer n ，Return to the integer in the form of a binary string Negative binary（base -2）express。

    Notice，Unless the string is "0"，Otherwise, the returned string cannot contain the front guide zero。

     

    Exemplary example 1：

    enter：n = 2
Output："110"
explain：(-2)2 + (-2)1 = 2

    Exemplary example 2：

    enter：n = 3
Output："111"
explain：(-2)2 + (-2)1 + (-2)0 = 3

    Exemplary example 3：

    enter：n = 4
Output："100"
explain：(-2)2 = 4

     

    hint：

    • 0 <= n <= 109
    Related Topics
  • math

  • 👍 111
  • 👎 0
    • [1017.Negative binary conversion.md]()

    Thought：

    We can judge n Every bit from low to high，If the bit is 1，Then the answer is 1，Otherwise 0。If the bit is 1，So we need to n minus k。Next we update n=⌊n/2⌋, k=−k。Continue to judge the next。
    at last，We will return to the answer。
    time complexity O(logn)，in n For the given integer。Ignore the space consumption of the answer，Spatial complexity O(1)。

    Code：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    class Solution:
        def baseNeg2(self, n: int) -> str:
            k = 1
            ans = []
            while n:
                if n % 2:
                    ans.append('1')
                    n -= k
                else:
                    ans.append('0')
                n //= 2
                k *= -1
            return ''.join(ans[::-1]) or '0'

    show all >>

    121.The best time for buying and selling stocks

    字数统计: 103字   |   阅读时长: 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 >>

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

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

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