Daily question brushing record (12)

The first question is : The finger of the sword Offer II 012. The sum of the left and right subarrays is equal

LeetCode: The finger of the sword Offer II 012. The sum of the left and right subarrays is equal

describe :
Give you an array of integers nums , Please calculate the of the array Center subscript .

Array Center subscript Is a subscript of the array , The sum of all elements on the left is equal to the sum of all elements on the right .

If the central subscript is at the leftmost end of the array , Then the sum of the numbers on the left is regarded as 0 , Because there is no element to the left of the subscript . This also applies to the fact that the central subscript is at the rightmost end of the array .

If the array has multiple central subscripts , Should return to Closest to the left The one of . If the array does not have a central subscript , return -1 .

Their thinking :

1. The sum of all is directly recorded here , to rightTotal
2. Traversal array .
3. Give Way leftTotal Record the sum of all elements on the left , rightTotal Record the sum of all elements on the right .
4. If at present leftTotal and rightTotal The values are equal . Returns the current subscript .

Code implementation :

class Solution {
    
    public int pivotIndex(int[] nums) {
    
        int rightTotal = 0;
        int leftTotal = 0;
        for(int num : nums) {
    
            rightTotal += num;
        }
        for(int i = 0; i < nums.length; i++) {
    
        	//  Notice that the right side is subtracted first   Judge again   Then add .
            rightTotal -= nums[i];
            if (leftTotal == rightTotal) return i;
            leftTotal += nums[i];
        }
        return -1;
    }
}

The second question is : The finger of the sword Offer II 014. An anamorphic word in a string

LeetCode: The finger of the sword Offer II 014. An anamorphic word in a string

describe :
Given two strings s1 and s2, Write a function to judge s2 Does it include s1 An anamorphic word of .

let me put it another way , One of the permutations of the first string is the... Of the second string Substring .

Their thinking :

1. Use sliding windows to solve .
2. First use an array record s1 in Number of string occurrences
3. Then change all characters that do not appear into -1
4. Establish a range of [left,right] Sliding window of .
5. If at present right Subscript elements exist in the array
   • If the current number is greater than 0, Then the array subscript corresponding to this element is subtracted 1, Make the window bigger (right++).
   • If the current number is equal to 0, If at present left and right Subscript elements are different , You need to make the left window smaller (left++). If it's the same , Just slide the window to the right (left++,right++)
6. If at present right The subscript element does not exist in the array . If at present left and right Not in the same subscript , It means that the window has been changed , And the current element does not exist , You need to reinitialize the window ,

Code implementation :

class Solution {
    
    public boolean checkInclusion(String s1, String s2) {
    
        int[] arr = new int[26];
        for(char ch : s1.toCharArray()) {
    
            arr[ch-'a']++;
        }
        for (int i = 0; i < 26; i++) {
    
            if (arr[i] == 0) arr[i] = -1;
        }
        int left = 0;
        int right = 0;
        int total = s1.length();
        while (total > 0 && right < s2.length()) {
    
            int tmp = arr[s2.charAt(right)-'a'];
            if (tmp == -1) {
    
                while (left < right) {
    
                    arr[s2.charAt(left) - 'a']++;
                    total++;
                    left++;
                }
                left = right + 1;
                right = left;
            } else {
    
                if (tmp > 0) {
    
                    total--;
                    arr[s2.charAt(right)-'a']--;
                    right++;
                }else {
    
                    while(s2.charAt(left) != s2.charAt(right)) {
    
                        total++;
                        arr[s2.charAt(left) - 'a']++;
                        left++;
                    }
                    left++;
                    right++;
                }
            }
        }
        return total == 0;
    }
}

Third question : The finger of the sword Offer II 016. The longest substring without duplicate characters

LeetCode: The finger of the sword Offer II 016. The longest substring without duplicate characters

describe :
Given a string s , Please find out that there are no duplicate characters in it Longest continuous substring The length of .

Their thinking :

1. Here is to use sliding window to solve problems .
2. The scope is [left,right] Sliding window of . Add the string list Record
3. If at present right The subscript element exists , Just delete list The first element , Give Way left++, until right Subscript element in list Does not exist in the .
4. take right Subscript elements are added list in , Record the size of the current sliding window (right-left+1)
5. End of traversal , Returns the maximum sliding window size .

Code implementation :

class Solution {
    
    public int lengthOfLongestSubstring(String s) {
    
        int left = 0;
        int right = 0;
        int ans = 0;
        List<Character> list = new ArrayList<>();
        while (right < s.length()) {
    
            while(left < right && list.contains(s.charAt(right))) {
    
                list.remove(0);
                left++;
            }
            list.add(s.charAt(right));
            ans = Math.max(ans,right-left+1);
            right++;
        }
        return ans;
    }
}

Fourth question : The finger of the sword Offer II 018. Valid palindromes

LeetCode: The finger of the sword Offer II 018. Valid palindromes

describe :
Given a string s , verification s Whether it is Palindrome string , Only consider Letters and numbers character , The case of letters can be ignored .

In this question , Define an empty string as a valid Palindrome string .

Their thinking :

1. Traversal string , As long as the string is numbers and characters, it will become a new string .
2. Use double pointers to traverse the string .
3. If left Subscripts and right The contents of subscript words are the same , Just left++. right--;
4. If it's not the same , Go straight back to false ;
5. Return after traversal true ;

Code implementation :

class Solution {
    
    public boolean isPalindrome(String s) {
    
        String ret = "1234567890abcdefghijklmnopqlstuvwxyz";
        StringBuilder sb = new StringBuilder();
        s = s.toLowerCase();
        for (int i = 0; i < s.length(); i++) {
    
            if(ret.contains(s.charAt(i)+"")){
    
                sb.append(s.charAt(i));
            }
        }
        int left = 0;
        int right = sb.length()-1;
        while(left <= right) {
    
            if(sb.charAt(left) == sb.charAt(right)) {
    
                left++;
                right--;
            }else{
    
                return false;
            }
        }
        return true;
    }
}

Fifth question : The finger of the sword Offer II 019. Delete at most one character to get a palindrome

LeetCode: The finger of the sword Offer II 019. Delete at most one character to get a palindrome

describe :
Given a non empty string s, Please judge if most If you delete a character from the string, you can get a palindrome string .

Their thinking :

1. First of all, judge , Whether the current palindrome string
2. If so, go back true;
3. If not, judge the current [left,right-1] or [left+1,right] Is it a palindrome string . As long as there is one is true;

Code implementation :

class Solution {
    
    public boolean validPalindrome(String s) {
    
        int left = 0;
        int right = s.length()-1;
        while(left <= right) {
    
            if(s.charAt(left) == s.charAt(right)){
    
                left++;
                right--;
            }else{
    
                return isHui(s,left,right-1) || isHui(s,left+1,right);
            }
        }
        return true;
    }
    public boolean isHui(String s, int left, int right) {
    
        while(left <= right) {
    
            if(s.charAt(left) == s.charAt(right)) {
    
                left++;
                right--;
            }else{
    
                return false;
            }
        }
        return true;
    }
}

Sixth question : The finger of the sword Offer II 020. Number of palindrome substrings

LeetCode: The finger of the sword Offer II 020. Number of palindrome substrings

describe :
Given a string s , Please calculate how many palindrome substrings there are in this string .

A substring with different start or end positions , Even if it's made up of the same characters , It's also seen as a different substring .

Their thinking :

1. Here we use dynamic programming to solve problems .
2. state F(i,j) : Express i~j Is it a palindrome string
3. State transition equation : At present j == i when , F(i,j) = true; When j - i == 1 when ,F(i,j)=s.charAt(i) == s.charAt(j); When j-i > 1 when , F(i,j) = s.charAt(i) == s.charAt(j) && dp[i+1][j-1] (dp[i+1][j-1] , Namely [i+1,j-1] Is it a palindrome string )
4. The initial state : A single character is true;
5. Return results : dp[i][j] by true The number of

Code implementation :

class Solution {
    
    public int countSubstrings(String s) {
    
        boolean[][] dp = new boolean[s.length()][s.length()];
        int count = 0;
        for(int i = s.length()-1; i >= 0; i--) {
    
            for(int j = s.length()-1; j>=i; j--){
    
                if(j == i) dp[i][j] = true;
                else if(j - i == 1) {
    
                    dp[i][j] = s.charAt(i) == s.charAt(j);
                }else{
    
                    dp[i][j] = s.charAt(i) == s.charAt(j) && dp[i+1][j-1];
                }
                if(dp[i][j]) count++;
            }
        }
        return count;
    }
}