Catalogue of series articles

Find traversal

169. Most elements

subject
Given an array of size n, find most of its elements. Most elements refer to elements that appear more than ⌊ n/2 ⌋ in the array.

You can assume that the array is non empty and that there are always many elements in a given array.

Example 1:

Input: [3,2,3]
Output: 3
Example 2:

Input: [2,2,1,1,1,2,2]
Output: 2

Advanced:

This paper attempts to design an algorithm with time complexity O(n) and space complexity O(1) to solve this problem.

Source: LeetCode
Link: https://leetcode-cn.com/problems/majority-element

analysis
If only violent search can not meet the advanced requirements, the idea of "elimination" is adopted. Here we use nub to represent the temporary mode and CNT as statistics. If the number traversed is the current mode cnt+1, if it is not cnt-1, if CNT is 0, it means that all previous numbers have been offset, and the current number should be set to mode
code

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int nub;
        int cnt=0;
        for(int i=0; i < nums.size(); i++){
            if(cnt==0){
                nub = nums[i];
            }
            if(nub==nums[i]){
                cnt++;
            }else{
                cnt--;
            }
        }
        return nub;
    }
};

219. Duplicate Element II exists

subject
Give you an integer array nums and an integer k, judge whether there are two different indexes I and j in the array, and satisfy nums[i] == nums[j] and ABS (I - J) < = K. If it exists, return true; Otherwise, false is returned.

Example 1:

Input: num = [1,2,3,1], k = 3
Output: true
Example 2:

Input: num = [1,0,1,1], k = 1
Output: true
Example 3:

Input: num = [1,2,3,1,2,3], k = 2
Output: false

Tips:

1 < = n u m s . l e n g t h < = 1 0 5 − 1 0 9 < = n u m s [ i ] < = 1 0 9 0 < = k < = 105 1 <= nums.length <= 10^5 \\ -10^9 <= nums[i] <= 10^9 \\ 0 <= k <= 105 1<=nums.length<=105−109<=nums[i]<=1090<=k<=105
Source: LeetCode
Link: https://leetcode-cn.com/problems/contains-duplicate-ii
analysis
If we use violence to solve problems, we can directly use the loop to query, but we can use the sliding window to reduce the time complexity to O(n).

Use the map to record the position of the number in the array. When the number appears again, find the difference between their positions, and update the value of the map.
code

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        set<int> s;
        map<int, int> m;
        for(int i=0; i < nums.size(); i++){
            if(s.count(nums[i])==0){
                s.insert(nums[i]);
                m[nums[i]] = i;
            }else{
                if(i - m[nums[i]] <= k){
                    return true;
                }else{
                    m[nums[i]] = i;
                }
            }
        }
        return false;
    }
};

character string

3. Longest substring without repeated characters

subject
Given a string s, please find the length of the longest substring that does not contain duplicate characters.

Example 1:

input: s = "abcabcbb"
output: 3 

Explanation: because the longest substring without repeated characters is "abc", its length is 3.
Example 2:

input: s = "bbbbb"
output: 1

Explanation: because the longest substring without repeated characters is "b", its length is 1.
Example 3:

input: s = "pwwkew"
output: 3

Explanation: because the longest substring without repeated characters is "wke", its length is 3.
Please note that your answer must be the length of the substring, "pwke" is a substring, not a substring.
Example 4:

input: s = ""
output: 0

Tips:

0 <= s.length <= 5 * 104
s consists of English letters, numbers, symbols and spaces

Source: LeetCode
Link: https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
analysis
First of all, we are most likely to think of the violent solution - three-tier loop traversal: the first two loops are used to segment strings, that is, the first loop traverses the start position and the second loop traverses the end position. The third loop is used to detect whether there are duplicate characters

However, this method will take a lot of time, so we use the sliding window method: first set a starting point start, then traverse the string, and record the latest occurrence position of each character. If the latest occurrence position of the traversed character is between start and the current position, it means that there are duplicate characters in the interval, and record the current length, And move start to the position after the latest occurrence of the character
code

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if(s==""){
            return 0;
        }
        map<char, int> m;
        set<char> st;
        int start=0;
        int ans=0;
        int tmp=0;
        for(int i=0; i < s.size(); i++){
            if(st.count(s[i])==0){
                st.insert(s[i]);
                m[s[i]] = i;
                tmp++;
            }else{
                if(m[s[i]] >= start){
                    ans = max(ans, tmp);
                    tmp = i-m[s[i]];
                    start = m[s[i]]+1;
                    m[s[i]] = i;
                }else{
                    m[s[i]] = i;
                    tmp++;
                }
            }       
        }
        ans = max(ans, tmp);
        return ans;
    }
};

539. Minimum time difference (medium)

subject
Given a time list in 24-hour system (hour: minute "HH:MM"), find the minimum time difference between any two times in the list and express it in minutes.

Example 1:

Input: timePoints = ["23:59", "00:00"]
Output: 1
Example 2:

Input: timePoints = ["00:00", "23:59", "00:00"]
Output: 0

Tips:

2 <= timePoints <= 2 * 104
The timePoints[i] format is "HH:MM"

Source: LeetCode
Link: https://leetcode-cn.com/problems/minimum-time-difference
analysis
Because it should be accurate to minutes, we can open up an array and directly convert the time to minute format (integer). After the conversion, we sort the minutes. The difference between the two adjacent elements of the ordered array must be less than the difference between the two non adjacent elements. At the same time, the last element is compared with the first element.
code

class Solution {
public:
    int findMinDifference(vector<string>& timePoints) {
        int* timeStemps;
        timeStemps = new int[timePoints.size()];
        for(int i=0; i < timePoints.size(); i++){
            timeStemps[i] = (int(timePoints[i][0]-'0') * 10 + int(timePoints[i][1]-'0')) * 60 + int(timePoints[i][3]-'0') * 10 + int(timePoints[i][4]-'0');
        }
        sort(timeStemps, timeStemps+timePoints.size());
        int ans = 24 * 60;
        for(int i=1; i < timePoints.size(); i++){
            ans = min(ans, timeStemps[i] - timeStemps[i-1]);
        }
        //printf("%d %d", timeStemps[0] + 24 * 60, timeStemps[timePoints.size()-1]);
        ans = min(ans, timeStemps[0] + 24 * 60 - timeStemps[timePoints.size()-1]);
        return ans;
    }
};

Linked list

2. Add two numbers

subject
Give you two non empty linked lists to represent two non negative integers. They store each number in reverse order, and each node can store only one number.

Please add the two numbers and return a linked list representing sum in the same form.

You can assume that neither number starts with 0 except the number 0.

Example 1:

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807
Example 2:

Input: l1 = [0], l2 = [0]
Output: [0]
Example 3:

Input: L1 = [9,9,9,9,9,9], L2 = [9,9,9]
Output: [8,9,9,9,0,0,1]

Tips:

The number of nodes in each linked list is within the range [1, 100]
0 <= Node.val <= 9
The number represented in the title data guarantee list does not contain leading zeros

Source: LeetCode
Link: https://leetcode-cn.com/problems/add-two-numbers
analysis
First, consider several possible situations
1. The first linked list is empty
2. The second linked list is empty
3. The first linked list is longer than the second
4. The second linked list is longer than the first
5. Two are the same length

For the first two cases, you can directly return to another table. For the latter two cases, you should consider the remaining carry after the traversal of another table and the splicing of tables. For the last one, only the carry problem can be considered.

code

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){
    struct ListNode* f1, * f2, *h=l1;
    int far=0;
    if(l1==NULL){
        return l2;
    }
    if(l2==NULL){
        return l1;
    }
    while(l1!=NULL && l2!=NULL){
        int value = l1->val + l2->val + far;
        l1->val = value % 10;
        far = value / 10; 
        f1=l1;
        f2=l2;
        l1=l1->next;
        l2=l2->next;
    }
    if(l2!=NULL){
        f1->next = l2;
        l1=f1->next;
    }
    while(l1!=NULL && far){
        int value = l1->val + far;
        l1->val = value % 10;
        far = value / 10;
        f1 = l1;
        l1=l1->next;
    }
    while(far){
        struct ListNode* p;
        p = (struct ListNode *)malloc(sizeof(struct ListNode));
        p->next = NULL;
        p->val = far % 10;
        far /= 10;
        f1->next = p;
    }
    return h;
}

Breadth first search

1345. Jumping game IV

subject
Give you an integer array arr, you start at the first element of the array (subscript 0).

At each step, you can jump from subscript i to subscript:

i + 1: i + 1 < arr.length
i - 1 satisfies: i - 1 > = 0
J satisfy: arr[i] == arr[j] and I= j
Please return the minimum number of operations required to reach the subscript of the last element of the array.

Note: you can't jump out of the array at any time.

Example 1:

Input: arr = [100, - 23, - 23404100,23,23,3404]
Output: 3
Explanation: you need to jump 3 times with subscripts 0 -- > 4 -- > 3 -- > 9. Subscript 9 is the subscript of the last element of the array.
Example 2:

Input: arr = [7]
Output: 0
Explanation: it starts at the last element, so you don't need to jump.
Example 3:

Input: arr = [7,6,9,6,9,6,9,7]
Output: 1
Explanation: you can jump directly from subscript 0 to subscript 7, which is the last element of the array.
Example 4:

Input: arr = [6,1,9]
Output: 2
Example 5:

Input: arr = [11,22,7,7,7,7,7,7,7,22,13]
Output: 3

Tips:

1 <= arr.length <= 5 * 10^4
-10^8 <= arr[i] <= 10^8

Source: LeetCode
Link: https://leetcode-cn.com/problems/jump-game-iv
analysis
It can be seen from the problem that this problem can be solved by breadth first search. The number of steps required is the number of layers when traversing to the end. But the problem here is timeout, because direct violent search will have repeated node access, which can be optimized by pruning.

Because the complete graph through violent search may be infinite in theory, only part of the graph is drawn here for convenience of understanding

As shown in the figure below

In order to solve this problem, we can mark the node. If it has been accessed, it will not be accessed. The purpose of set < int > s and m.erase in the code is to remove the accessed node for pruning, so as to optimize the time
code

struct Node{
    int idx;
    int level;
};

class Solution {
public:
    int minJumps(vector<int>& arr) {
        map<int, vector<int>> m;
        set<int> s;
        queue<Node> q;
        for(int i=0; i < arr.size(); i++){
            m[arr[i]].push_back(i);
        }
        Node n;
        n.idx = 0;
        n.level = 0;
        q.push(n);
        while(!q.empty()){
            Node p=q.front();

            q.pop();
            if(p.idx == arr.size()-1){
                return p.level;
            }
            s.insert(p.idx);
            if(m.count(arr[p.idx])){
                for(int i=0; i < m[arr[p.idx]].size(); i++){
                    if(!s.count(m[arr[p.idx]][i])){
                        Node tmp;
                        tmp.idx = m[arr[p.idx]][i];
                        tmp.level = p.level + 1;
                        q.push(tmp);
                    }
                }
                m.erase(arr[p.idx]);
            }
            
            if(p.idx > 0 && !s.count(p.idx-1)){
                Node tmp;
                tmp.idx = p.idx - 1;
                tmp.level = p.level + 1;
                q.push(tmp);
            }
            if(p.idx <= arr.size()-1 && !s.count(p.idx+1)){
                Node tmp;
                tmp.idx = p.idx + 1;
                tmp.level = p.level + 1;
                q.push(tmp);
            }
        }
        return -1;
    }
};

brain twists

1332. Delete palindrome subsequence

subject
Give you a string s, which consists only of the letters' a 'and' b '. Each deletion operation can delete a palindrome subsequence from S.

Returns the minimum number of times to delete all characters in a given string (the string is empty).

Definition of "subsequence": if a string can be obtained by deleting some characters of the original string without changing the order of the original characters, then the string is a subsequence of the original string.

"Palindrome" definition: if a string is read backwards and forwards the same, then the string is a palindrome.

analysis
Because there are only a and b characters, you can delete all the characters at most the second time. You can delete them once when the string palindrome is not palindrome, and you need to delete them twice.
code
Example 1:

Input: s = "ababa"
Output: 1
 Explanation: the string itself is a palindrome sequence, which only needs to be deleted once.

Example 2:

Input: s = "abb"
Output: 2
 Explanation:"abb" -> "bb" -> "". 
Delete palindrome subsequence first "a"，Then delete "bb". 

Example 3:

Input: s = "baabb"
Output: 2
 Explanation:"baabb" -> "b" -> "". 
Delete palindrome subsequence first "baab"，Then delete "b". 

Tips:

1 <= s.length <= 1000
s contains only the letters' a 'and' b '

Source: LeetCode
Link: https://leetcode-cn.com/problems/remove-palindromic-subsequences

Game theory

2029. Stone game IX

subject
Alice and Bob designed a new stone game again. There are n stones in a row, and each stone has an associated number to represent its value. Give you an integer array stones, where stones[i] is the value of the ith stone.

Alice and Bob take turns in their rounds, and Alice takes the lead. Each turn, players need to remove any stones from stones.

If the total value of all removed stones can be divided by 3 after the player removes the stones, the player will lose the game.
If the previous one is not satisfied and there are no stones left after removal, Bob will win directly (even in Alice's turn).
Suppose both players make the best decision. If Alice wins, return true; If Bob wins, false is returned.

Example 1:

Input: stones = [2,1]
Output: true
Explanation: the game proceeds as follows:

• Turn 1: Alice can remove any stone.
• Turn 2: Bob removes the remaining stones.
  The sum of the values of the removed stones is 1 + 2 = 3 and can be divided by 3. So Bob lost and Alice won.
  Example 2:

Input: stones = [2]
Output: false
Explanation: Alice will remove the only stone. The sum of the removed stones is 2.
Since all stones have been removed and the sum of values cannot be divided by 3, Bob wins.
Example 3:

Input: stones = [5,1,2,4,3]
Output: false
Explanation: Bob always wins. One possible way to play the game is as follows:

• Turn 1: Alice can remove the second stone with a value of 1. The sum of the removed stones is 1.
• Turn 2: Bob can remove the 5th stone with a value of 3. The sum of the removed stones is = 1 + 3 = 4.
• Turn 3: Alice can remove the fourth stone with a value of 4. The sum of the removed stones is = 1 + 3 + 4 = 8.
• Turn 4: Bob can remove the third stone with a value of 2. The sum of the removed stones is = 1 + 3 + 4 + 2 = 10
• Turn 5: Alice can remove the first stone with a value of 5. The sum of the removed stones is = 1 + 3 + 4 + 2 + 5 = 15
  Alice loses the game because the sum of the removed stones (15) can be divided by 3 and Bob wins.

Tips:

1 <= stones.length <= 105
1 <= stones[i] <= 104

Source: LeetCode
Link: https://leetcode-cn.com/problems/stone-game-ix

analysis
Here, the number represented by the stone is converted into the remainder, i.e. 0, 1 and 2. Alice and Bob are set as A and B for discussion

So the two situations in the process of taking stones are

Take 1 first:

The remainder of 3 of the sum of the stones taken out	1	2	1	2	1	2	...
The process of removing stones	1	1	2	1	2	1	...

Take 2 First:

The remainder of 3 of the sum of the stones taken out	2	1	2	1	2	1	...
The process of removing stones	2	2	1	2	1	2	...

It can be found that in any case, it is necessary to take the same stone twice. Regardless of 0, A wins as follows:
1. When the number of 1 is 1 and the number of 2 is greater than 0, A wins
2. When the number of 1 is 2 and the number of 2 is greater than 0, A wins
3. When the number of 1 is greater than or equal to 2 and the number is not greater than 2, A wins
4. When the number of 2 is 1 and the number of 1 is greater than 0, A wins
5. When the number of 2 is 2 and the number of 1 is greater than 0, A wins
6. When the number of 2 is greater than or equal to 2 and the number is not greater than 1, A wins
It can be seen that

A wins when the number of 1 is greater than 0 and the number of 2 is greater than 0

When the number of 0 is even, it will not affect
When the number of zeros is odd, it is equivalent to exchanging first and then hands. At this time, it will be very troublesome for A to win according to the previous consideration. Therefore, we start from the table. If we follow the best choice, we must follow the cycle of the table. Because we want to get the result of A winning, we need to make B unable to get the number before the end of the cycle, Considering that the number of zeros is odd, we can find the situation in the table that makes A unable to get the number that should be taken

1. The number of 1 is at least 2 more than the number of 2
2. The number of 2 is at least 2 more than the number of 1
code

class Solution {
public:
    bool stoneGameIX(vector<int>& stones) {
        int cnt[3]={0,0,0};
        for(int i=0; i < stones.size(); i++){
            cnt[stones[i]%3]++;
        }
        if(cnt[0] % 2 == 0){
            return cnt[1] >= 1 && cnt[2] >=1;
        }else{
            return cnt[1] - cnt[2] > 2 || cnt[2] - cnt[1] > 2;
        }
    }
};