6. Z igzag transformation 9 / 2

A given string s is arranged in a zigzag manner from top to bottom and from left to right according to the given number of rows numRows.

For example, when the input string is "paypalishing" and the number of lines is 3, the arrangement is as follows:

P   A   H   N
A P L S I I G
Y   I   R

After that, your output needs to be read line by line from left to right to produce a new string, such as "PAHNAPLSIIGYIR".

Please implement this function to transform the string to the specified number of lines:

string convert(string s, int numRows);

Resolution:

Find out the rules of characters arranged in Z shape, and then save them directly.

You can see that the graph actually has cycles, 0, 1, 2... 7, a total of 8, and then start repeating the same path again. The calculation of cycle len is: cycle len = 2 × Number of rows (numRows) - 2 = 2 × 5 - 2 = 8.

We found that there is only one character in a cycle in line 0 and the last line, so the first character subscript is 0, the second character subscript is 0 + cyclen = 8, and the third character subscript is 8 + cyclen = 16.

The other lines in the middle are two characters in a cycle.

The rule of the first character and line 0 is the same.

The second character is actually the subscript of line 0 of the next cycle minus the current line. What do you mean?

Let's find the second character in the first cycle of line 1. The subscript of line 0 in the next cycle is 8. Subtract 1 from the current line to get 7.

Let's find the second character in the first line and the second character in the cycle. The subscript of line 0 in the next cycle is 16. Subtract 1 from the current line to get 15.

Let's find the second character in the first cycle of line 2. The subscript of line 0 in the next cycle is 8. Subtract 2 from the current line to get 6.

Of course, we must ensure that the subscript is less than the string length (n) to prevent cross-border.

Java implementation:

class Solution {
    public String convert(String s, int numRows) {
        //If there is only one line, the string is returned directly
        if(numRows == 1){
            return s;
        }

        //String length
        int len = s.length();
        //Used to store output strings
        StringBuilder ret = new StringBuilder();
        //Calculate the number of characters per cycle
        int cycleLen = 2 * numRows - 2;
        
        //Traversal row
        for(int i=0; i<numRows; i++){
            //Number of traversal cycles, one cycle added at a time
            for(int j=0; j+i<len; j+=cycleLen){
                //The first column of each cycle is added
                ret.append(s.charAt(j + i));
                //The second character of the j-th cycle in line i is added; That is, remove line 0 and the last line
                if(i != 0 && i != numRows - 1 && j+cycleLen-i < len){
                    ret.append(s.charAt(j + cycleLen - i));
                }
            }
        }
        return ret.toString();
    }
}

Time complexity: O (n). Although it is a two-layer loop, the second loop adds cyclen each time, which is nothing more than traversing each character once, so the number of executions in the two-layer loop must be the length of the string.

Space complexity: O (n), save string.

7. Integer inversion 9 / 3

Give you a 32-bit signed integer x and return the result after reversing the number part in X.

If the inverted integer exceeds the range of 32-bit signed integers [− 231, 231 − 1], 0 is returned.

Assume that the environment does not allow the storage of 64 bit integers (signed or unsigned).

Solution 1:

Convert an integer to a string, and then convert the string to an integer after inversion. When a negative number is required.

class Solution {
    public int reverse(int x) {
        String sx = Integer.toString(x);  //May have a negative sign
        String s = sx; //Store new string
        int flag = 1; //Default positive number
        //If x is negative, multiply by - 1 and set flag to - 1
        if(x<0){
            flag = -1; //negative
            s = sx.substring(1); //Remove minus sign
        }
        try{
            //Convert string to integer after inversion
            x = Integer.valueOf((new StringBuilder(s)).reverse().toString()) * flag;
            return x;
        }catch (Exception e){
            return 0;
        }
    }
}

Solution 2:

The integer is continuously rounded to get the single digit, and then divided by ten to remove the single digit; Then use a variable to store the results.

class Solution {
    public int reverse(int x) {
        long rev = 0; //Stored value variable
        while(x != 0){
            int pop = x % 10; //Single digit
            x /= 10; //Round to remove single digits
            rev = rev * 10 + pop;
        }
        //If it exceeds the range, it returns 0
        if(rev > Integer.MAX_VALUE || rev < Integer.MIN_VALUE) return 0;
        return (int)rev;
    }
}

Time complexity: how many cycles? The number of digits will be cycled as many times as possible, that is, log10(x)+1log_{10}(x) + 1log + 10 (x)+1 time, so the time complexity is O (log (x)).

Space complexity: O (1).

8. String to integer (atoi) 9/4

Please implement a myAtoi(string s) function to convert the string into a 32-bit signed integer (similar to the atoi function in C/C + +).

The algorithm of the function myAtoi(string s) is as follows:

• Read in the string and discard useless leading spaces
• Check whether the next character (assuming it is not at the end of the character) is a positive or negative sign, and read the character (if any). Determine whether the final result is a negative or positive number. If neither exists, the result is assumed to be positive.
• Reads the next character until the next non numeric character is reached or the end of the input is reached. The rest of the string will be ignored.
• Convert the numbers read in the previous steps to integers (i.e., "123" - > 123, "0032" - > 32). If no numbers are read in, the integer is 0. Change the symbol if necessary (starting from step 2).
• If the number of integers exceeds the range of 32-bit signed integers [− 231, 231 − 1], you need to truncate the integer to keep it within this range. Specifically, integers less than − 231 should be fixed as − 231, and integers greater than 231 − 1 should be fixed as 231 − 1.
• Returns an integer as the final result.

be careful:

• The blank characters in this question only include the space character ''.
• Do not ignore any characters other than the leading space or the rest of the string after the number.

Resolution:

Mainly consider the handling of characters.

Java implementation:

class Solution {
    public int myAtoi(String s) {
        int i = 0;
        int len = s.length(); //String length
        int sign = 1; //A positive number is 1 and a negative number is - 1
        int res = 0; //Store integer
        while (i < len && s.charAt(i) == ' ') { //If the leading position of the string is a space, loop to the position with data
            i++;
        }
        int start = i;  //Record the starting position of all data after the current
        for (; i < len; i++) {
            int c = s.charAt(i); //Current character
            if (i == start && c == '+') {   //Judge whether it is +, and + should be in the initial position
                sign = 1;
            } else if (i == start && c == '-') {    //Judgment is-
                sign = -1;
            } else if (Character.isDigit(c)) {  //Judgment is a number
                int num = c - '0';
                //If it is a number, the others do not need to be considered, but only two out of limit situations need to be considered
                if (res > Integer.MAX_VALUE / 10 || (res == Integer.MAX_VALUE / 10 && num > Integer.MAX_VALUE % 10)) {
                    return Integer.MAX_VALUE;
                } else if (res < Integer.MIN_VALUE / 10 || (res ==Integer.MIN_VALUE / 10 && -num < Integer.MIN_VALUE % 10)) {
                    return  Integer.MIN_VALUE;
                }
                //Calculate integer value
                res = res * 10 + sign * num;
            } else {    //If a cycle is neither a number nor '+' and '-', exit the cycle immediately and return the value already stored in the current res
                break;
            }
        }
        return res;
    }
}

9. Number of palindromes 9 / 5

Give you an integer X. if x is a palindrome integer, return true; Otherwise, false is returned.

Palindromes are integers whose positive (left to right) and reverse (right to left) reads are the same. For example, 121 is a palindrome, not 123.

Solution 1:

Convert an integer to a string, using a double pointer.

class Solution {
    public boolean isPalindrome(int x) {
        String s = String.valueOf(x); //Convert integer to string
        int left = 0; //Left pointer
        int right = s.length() - 1; //Right pointer
        while(left < right){ 
            if(s.charAt(left) != s.charAt(right)){ //If the left character is not equal to the right character, it is not a palindrome
                return false;
            }
            left++; //Move left pointer
            right--; //Move right pointer
        }
        return true;
    }
}

Solution 2:

Just invert the right half and compare it with the left half. For example, 1221, just compare 21 transpose with 12.

class Solution {
    public boolean isPalindrome(int x) {
        if(x<0){
            return false;
        }
        int n = (int) (Math.log(x) / Math.log(10) + 1); //Total digits 
        int rev = 0; //Store the value reversed on the right
        int pop = 0; //Store single digit value
        //Inverted right half
        for(int i=0; i<n/2; i++){
            pop = x % 10; //Single digit
            rev = rev * 10 + pop; //Calculated value
            x /= 10; //Round to remove the calculated single digits
        }
        //If it is an integer, the total number of digits is even
        if(n % 2 == 0 && x == rev){
            return true;
        }
        //If the total number of digits of an integer is odd, remove one digit of x and compare it with the right
        if(n % 2 != 0 && x/10 == rev){
            return true;
        }
        return false;
    }
}

Time complexity: half of the total number of bits of cycle x, so the time complexity is still O (log (x)).

Spatial complexity: O (1), constant, variable.

10. Regular expression matching 9 / 6

Give you a string s and a character rule p, please implement a support '.' Matches the regular expression for '*'.

• ‘.’ Match any single character
• '*' matches zero or more preceding elements

The so-called matching is to cover the whole string s, not part of the string.

Solution 1:

recursion

class Solution {
    public boolean isMatch(String s, String p) {
        //Judge that when p is empty, if s is also empty, it will return true, otherwise it will be false
        if(p.isEmpty()) return s.isEmpty();

        //When s is not empty and p is equal to the first character of s or p is'. ' true when
        boolean first_match = (!s.isEmpty() && (p.charAt(0) == s.charAt(0) || p.charAt(0) == '.'));

        //'*' is considered only when p length is greater than or equal to 2
        if(p.length() >= 2 && p.charAt(1) == '*'){
            //Two cases
            //1. p skip two characters directly: it means that the character before * appears 0 times
            //2. p remains unchanged. For example, s=aa,p=a * matches the first a, and then the second a of s matches the first a of p: it means that * is replaced by the previous character.
            return (isMatch(s,p.substring(2))) || (first_match && isMatch(s.substring(1),p));
        } else {
        //recursion
        return first_match && isMatch(s.substring(1),p.substring(1)); 
        }


    }
}

Solution 2:

dynamic programming

class Solution {
    public boolean isMatch(String text, String pattern) {
        // One more dimensional space, because when seeking dp[len - 1][j], you need to know the situation of dp[len][j],
        // If you have more than one dimension, you can write the pair dp[len - 1][j] into the loop
        boolean[][] dp = new boolean[2][pattern.length() + 1]; 
        dp[text.length()%2][pattern.length()] = true;

        // Decrease from len
        for (int i = text.length(); i >= 0; i--) {
            for (int j = pattern.length(); j >= 0; j--) {
                if(i==text.length()&&j==pattern.length()) continue;
                boolean first_match = (i < text.length() && j < pattern.length()
                        && (pattern.charAt(j) == text.charAt(i) || pattern.charAt(j) == '.'));
                if (j + 1 < pattern.length() && pattern.charAt(j + 1) == '*') {
                    dp[i%2][j] = dp[i%2][j + 2] || first_match && dp[(i + 1)%2][j];
                } else {
                    dp[i%2][j] = first_match && dp[(i + 1)%2][j + 1];
                }
            }
        }
        return dp[0][0];
    }
}