## 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]; } }