217. Existing duplicate elements

Thought：

For the first time**C++**Write a question
Two methods：

1. The first is sorting，Detect each time the first and the latter are equal；
2. 第二种方法是Hash table，Determine whether the number has appeared for the second time。
   existC++middle，Force buckle into the arraynumsin usevector，So it can be used directlysort()function。
   I want to usePythonmiddle的字典（Hash table）if，Give to importunordered_set<int>function新建Hash table，Re -usefind()andend()判断是否已经存exist。

Code：

1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        for (int i = 0; i < nums.size() - 1; i++){
            if(nums[i] == nums[i+1]) {
                return true;
            }
        }
        return false;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        std::unordered_set<int> Hash;
        for(int i: nums){
            if(Hash.find(i) != Hash.end()){
                return true;
            }
            else{
                Hash.insert(i);
            }
        }
    return false;
    }
};

1
2
3
4
5
6
7
8

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        dict1 = Counter(nums)
        dict1 = sorted(dict1.values())
        if dict1[-1] >= 2:
            return True
        else:
            return False

Course：

1. 看了官方answer，Similar to my first approach，AllsortedLater in the new listappend。But I think I can’t prove the correctness，Because it is Zhou Sai dare not submit at will。
2. Discover when thinking about the first solution，If I keepfor i in Whole array，Determine whether to meet the conditions and then exchange the position，What should I do if I enter the dead cycle?？If a special case fails every time, it needs to be exchanged. What is the difference between random disruption?？
3. After watching the solution of other big guys，I am still too young

1
2
3
4
5
6
7
8
9
10

def rearrangeArray(self, nums: List[int]) -> List[int]:
    i = 1
    while i < len(nums)-1:
        if nums[i] == (nums[i - 1] + nums[i + 1]) // 2:
            random.shuffle(nums)
            i = 1
        else:
            i += 1
    else:
        return nums

217. Existing duplicate elements

Thought：

For the first time**C++**Write a question
Two methods：

1. The first is sorting，Detect each time the first and the latter are equal；
2. 第二种方法是Hash table，Determine whether the number has appeared for the second time。
   existC++middle，Force buckle into the arraynumsin usevector，So it can be used directlysort()function。
   I want to usePythonmiddle的字典（Hash table）if，Give to importunordered_set<int>function新建Hash table，Re -usefind()andend()判断是否已经存exist。

Code：

1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        for (int i = 0; i < nums.size() - 1; i++){
            if(nums[i] == nums[i+1]) {
                return true;
            }
        }
        return false;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        std::unordered_set<int> Hash;
        for(int i: nums){
            if(Hash.find(i) != Hash.end()){
                return true;
            }
            else{
                Hash.insert(i);
            }
        }
    return false;
    }
};

1
2
3
4
5
6
7
8

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        dict1 = Counter(nums)
        dict1 = sorted(dict1.values())
        if dict1[-1] >= 2:
            return True
        else:
            return False

topic：

221. Maximum square

Thought：

可以使用Dynamic planning降低时间复杂度。we use dp(i,j) Express (i,j) The lower right corner，Only contain 1 The maximum value of the side length of the square。If we can calculate all dp(i,j) Value，Then the maximum value is that it is only included in the matrix 1 The maximum value of the side length of the square，其平方即为Maximum square的面积。

So how to calculate dp Each element value？For each position (i,j)，检查在矩阵中该位置Value：

if该位置Value是 0，but dp(i,j)=0，Because the current location cannot 1 Folk formation of composition；

if该位置Value是 1，but dp(i,j) Value由其上方、Three adjacent locations on the left and upper left dp Value decision。in particular，The element value of the current position is equal to the minimum value of the three adjacent elements 1，The state transfer equation is as follows：

dp(i,j)=min(dp(i−1,j),dp(i−1,j−1),dp(i,j−1))+1
also，You also need to consider boundary conditions。if i and j At least one of them is 0，but以位置(i,j) The lower right corner的Maximum square的边长只能是 1，therefore dp(i,j)=1

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
25
26
27
28
29
30
31
32
33
34

package main

func maximalSquare(matrix [][]byte) int {
	dp := make([][]int, len(matrix))
	maxSide := 0
	for i := 0; i < len(matrix); i++ {
		dp[i] = make([]int, len(matrix[i]))
		for j := 0; j < len(matrix[i]); j++ {
			dp[i][j] = int(matrix[i][j] - '0')
			if dp[i][j] == 1 {
				maxSide = 1
			}
		}
	}
	for i := 1; i < len(matrix); i++ {
		for j := 1; j < len(matrix[i]); j++ {
			if dp[i][j] == 1 {
				dp[i][j] = min(min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) + 1
				if dp[i][j] > maxSide {
					maxSide = dp[i][j]
				}
			}
		}
	}
	return maxSide * maxSide
}

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

Thought

This question was done on the phone at first，直接用的是双Hash table，An element，One depositindex，When a certain element exceeds2Judging whether there are two of them when they areindexSubtission is equal tokCase。So the complexity of time isO(n^3)。

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        hash_1={}
        hash_2={}
        for index, i in enumerate(nums):
            if i not in hash_1:
                hash_1[i] = 1
                hash_2[i] = [index]
            else:
                hash_1[i] += 1
                hash_2[i].append(index)
        for i in hash_1:
            if hash_1[i] >= 2:
                for j in range(len(hash_2[i])):
                    for m in range(j + 1, len(hash_2[i])):
                        if abs(hash_2[i][j]-hash_2[i][m]) <= k:
                            return True
        return False

look@Gongshui SanyeGongshui Sanye的解法后，Only think of，这道题的目的是为了练习双指针在Hash table中的应用，TAThe original words are sorting the meaning：Whether the existence does not exceed k+1k + 1k+1 window，window内有相同元素。

1
2
3
4
5
6
7
8
9
10
11
12

#Sort out the meaning：Whether the existence does not exceed k+1k + 1k+1 window，window内有相同元素。
class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        n = len(nums)
        s = set()
        for i in range(n):
            if i > k:
                s.remove(nums[i - k - 1])
            if nums[i] in s:
                return True
            s.add(nums[i])
        return False

2283.Determine whether the number of a number is equal to the value of the digital position。

1
2
3
4
5
6
7
8
9
10

class Solution:
    def digitCount(self, num: str) -> bool:
        hash_1 = {}
        for index, i in enumerate(num):
            if int(i) != 0:
                hash_1[str(index)] = int(i)
        hash_2 = Counter(num)
        if hash_1 == dict(hash_2):
            return True
        return False

I read this question for a while，MeaningindexRead，indexAppearnum[index]Second-rate，1210that is”0Appear1Second-rate，”1Appear2Second-rate，”2Appear1Second-rate，”3Appear0Second-rate。ThennumJust count the things in。

Because I was doing the practice of hash table two days ago，So at a glance at this question，Use directlyCounterFunction counts，Compare，Finish

Although it is a simple question，But there are recursive ideas。

Constantly convert the one -dimensional list into a two -dimensional list for operation（This can be avoidedindexChaos caused by changes）

Then useflagCount，Comparison of maximum and minimum values。

Just return to the end，Although it must be returned to a number，Still‘nums[0]’To avoid warning。

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

2293. Great mini game
Simple
39
company
Google Google
Give you a bidding 0 Started integer array nums ，Its length is 2 Power。

right nums Execute the following algorithm：

set up n equal nums length，if n == 1 ，termination Algorithm。otherwise，create A new integer array newNums ，The length of the new array is n / 2 ，Bidding from 0 start。
right于满足 0 <= i < n / 2 Every even Bidding i ，Will newNums[i] Assignment for min(nums[2 * i], nums[2 * i + 1]) 。
right于满足 0 <= i < n / 2 Every odd number Bidding i ，Will newNums[i] Assignment for max(nums[2 * i], nums[2 * i + 1]) 。
use newNums replace nums 。
From steps 1 start repeat the whole process。
After executing the algorithm，return nums The remaining numbers。

 

Exemplary example 1：



enter：nums = [1,3,5,2,4,8,2,2]
Output：1
explain：repeat执行算法会得到下述数组。
first round：nums = [1,5,4,2]
second round：nums = [1,4]
Third round：nums = [1]
1 Is the last number left，return 1 。
Exemplary example 2：

enter：nums = [3]
Output：3
explain：3 Is the last number left，return 3 。
 

hint：

1 <= nums.length <= 1024
1 <= nums[i] <= 109
nums.length yes 2 Power

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution:
    def minMaxGame(self, nums: List[int]) -> int:
        flag = 0
        while len(nums) > 1:
            nums = [nums[i:i + 2] for i in range(0, len(nums), 2)]
            # Divide2dimension
            for i in range(len(nums)):
                if flag % 2 == 0:
                    nums[i] = min(nums[i])
                    flag += 1
                else:
                    nums[i] = max(nums[i])
                    flag += 1
        return nums[0]

2309. The best English letters with both appropriates and lowercases

Thought：

1. Hash table：The first thing to think of the question is to solve it with a dictionary。But find that you can directly traverse the alphabet，fromZStart looking for，See if the applause exists，Just return directly。
   
   Running time exceeds99.9%
2. Bit operation：We can use two integers mask1 and mask2 Record string separately s 中出现的小写字母and大写字母，in mask1 First i
   Position representation i Does a lowercase letter appear，and mask2 First i Position representation i Whether an uppercase letter appears。

Then we will mask1 and mask2 Perform and calculate，The results obtained mask First i Position representation i Whether the lethals of the letter appear at the same time。

As long as you get mask The highest level of binary representation 1 s position，Convert it to the corresponding capital letter。If all binary positions are not 1，Explain that there is no letter that appears at the same time,，Return to an empty string。

author：ylb
Link：https://leetcode.cn/problems/greatest-english-letter-in-upper-and-lower-case/solutions/2077636/by-lcbin-zbg0/
source：Deduction（LeetCode）
著作权归author所有。商业转载请联系author获得授权，Non -commercial reprint Please indicate the source。

Code：

1
2
3
4
5
6

class Solution:
    def greatestLetter(self, s: str) -> str:
        for i in range(90, 64, -1):
            if chr(i) in s and chr(i+32) in s:
                return chr(i)
        return ""

1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
public:
    string greatestLetter(string s) {
        unordered_set<char> strin(s.begin(),s.end());
        for(char c = 'Z'; c >= 'A'; --c){
            if(strin.count(c) && strin.count(char(c+32))){
                return string(1,c);
            }
        }
        return "";
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution:
    def greatestLetter(self, s: str) -> str:
        # We can use two integers mask1 and mask2
        # Record string separately s 中出现的小写字母and大写字母，in mask1 First i Position representation i Does a lowercase letter appear，
            # and mask2 First i Position representation i Whether an uppercase letter appears。
        mask1 = mask2 = 0
        for i in s:
            if i.islower():
                mask1 |= 1 << (ord(i) - ord("a"))
            else:
                mask2 |= 1 << (ord(i) - ord("A"))
        mask = mask1 & mask2
        return chr(mask.bit_length() - 1 + ord("A")) if mask else ""

Excess when executing100%User，What can I say about this question，But oneBit operationKnowledge point

My code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution:
    def strongPasswordCheckerII(self, password: str) -> bool:
        flag1 = flag2 = flag3 = flag4 = 1
        ret = None
        for i in password:
            if ret == i:
                return False
            if i.isdigit():
                flag1 = 0
            elif i.isupper():
                flag2 = 0
            elif i.islower():
                flag3 = 0
            else:
                flag4 = 0
            ret = i
        if sum([flag1, flag2, flag3, flag4]) == 0 and len(password) >= 8:
            return True
        return False

Bit operation代码：

method one：simulation + Bit operation

According to the description of the topic，我们可以simulation检查密码是否满足题目要求的过程。

first，We check whether the length of the password is less than 8，in the case of，Then return false。

Next，We use a mask mask To record whether the password contains a lowercase letter、uppercase letter、Numbers and special characters。We traverse the password，Like a character every time，First determine whether it is the same as the previous character，in the case of，Then return false。Then，Update mask according to the type of character mask。at last，We check the mask mask Whether it is 15，in the case of，Then return true，否Then return false。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution:
    def strongPasswordCheckerII(self, password: str) -> bool:
        if len(password) < 8:
            return False
        mask = 0
        for i, c in enumerate(password):
            if i and c == password[i - 1]:
                return False
            if c.islower():
                mask |= 1
            elif c.isupper():
                mask |= 2
            elif c.isdigit():
                mask |= 4
            else:
                mask |= 8
        return mask == 15

author：ylb
Link：https://leetcode.cn/problems/strong-password-checker-ii/solutions/2068878/by-lcbin-hk2a/

2303. Calculate the total taxable amount

Thought：

Sit a long time，It feels rare“Simple”。Not to do，The solution of the question。There are many judgments，So I wrote a lot of judgments，The more you write, the more you feel wrong。

Let’s take a look at the official solution

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
25
26
27

from typing import List

class Solution:
    def calculateTax(self, brackets: List[List[int]], income: int) -> float:
        if income == 0:
            return 0
        tax: float = 0
        index: int = 1
        if income < brackets[0][0]:
            return income * brackets[0][1] / 100
        else:
            tax += brackets[0][0] * brackets[0][1] / 100
        while index < len(brackets):
            # Judging whether it is the last one
            if index == len(brackets) - 1:
                # ComparebracketsThe last one is still big
                if income - brackets[index][0] < 0:
                    tax += (income - brackets[index - 1][0]) * brackets[index][1] / 100
                    return tax
            if income >= brackets[index][0]:
                tax += (brackets[index][0]- brackets[index-1][0]) * brackets[index][1] / 100
            if income < brackets[index-1][0]:
                break
            index += 1
        return tax

print(Solution.calculateTax(Solution(), brackets = [[1,0],[4,25],[5,50]], income = 2))

Let’s take a look at the official solution

1
2
3
4
5
6
7
8
9
10

class Solution:
    def calculateTax(self, brackets: List[List[int]], income: int) -> float:
        totalTax = lower = 0
        for upper, percent in brackets:
            tax = (min(income, upper) - lower) * percent
            totalTax += tax
            if income <= upper:
                break
            lower = upper
        return totalTax / 100

@ylb

1
2
3
4
5
6
7

class Solution:
    def calculateTax(self, brackets: List[List[int]], income: int) -> float:
        ans = prev = 0
        for upper, percent in brackets:
            ans += max(0, min(income, upper) - prev) * percent
            prev = upper
        return ans / 100