Leetcode string Easy Java 11 Road

spent a week in the morning to finish the array + string a total of 20 questions, every day has some small gains, is quite a good feeling. Let me talk about my problem solving ideas on the 9 questions of the string:

(一)344 Reverse the string:

题内容:

难级级:Easy

解Idea 1: I just started thinking about splicing strings, reading each character of s in reverse, and then assigning it to a new string. The result time complexity is too high to pass. Therefore, it is used to convert it to stringbuilder and call reverse API. It is necessary to judge that it is empty in advance.

解解思维二: Other people's methods: use toCharArray to convert it to a char type array, re-assign a new array, and traverse the assignment. And the time complexity is lower.

码:

// 1. I just started thinking about splicing strings, reading each character of s in reverse, and then assigning it to a new string. The result time complexity is too high. No, so use
    // Be sure to judge in advance, it will reduce the amount of calculation, directly use the reverse API in stringbuilder.
// public static String reverseString(String s) {
// if (s.length() == 0) {
// return "";
// }
// StringBuffer sb_01 = new StringBuffer(s);
// sb_01.reverse();
// return sb_01.toString();
// }
    //2. Convert it to a char type array, create a new array with reassignment, and read the assignment in reverse, which can also be done. And the time complexity is lower.
    Public static String reverseString(String s) {
        Char[] chars = s.toCharArray();
        Char[] newString = new char[chars.length];
        For (int i = chars.length - 1, t = 0; i >= 0; i--, t++) {
            newString[t] = chars[i];
        }
        Return new String(newString);
    }

(二)7 Inverted integer:

题内容:

难级级:Easy

解解思维: This question was quite troublesome at the time, paying attention to too much detail. Because the objects of StringBuilder and StringBuffer are variables, the operation of the variable is to directly change the object without creating and recycling. So use StringBuilder to get it. The steps are as follows: (1) to determine whether the number is greater than zero, if less than zero, the string is intercepted from the subscript 1; (2) use result += (Math.pow (10, i) * tmp); tmp is positive To each element read; result is of type long. (3) Determine whether it is greater than Integer.MAX_VALUE or less than Integer.MIN_VALUE, and return the corresponding value. Note the following: (1) MAth.abs cannot be used; (2) Integer.MAX_VALUE determines the maximum value; (3) determines whether there is an out of bounds after the inversion, rather than whether there is an out of bounds before.

码:

// The objects of StringBuilder and StringBuffer are variables. The operation of the variable is to directly change the object without creating and reclaiming it, so the speed is much faster than String.
    //md must pay attention to the cross-border problem, (1) MAth.abs can not be used. (2) Integer.MAX_VALUE determines the maximum value; (3) determines whether there is an out of bounds after the inversion, rather than whether there is a previous out of bounds.
    Public static int reverse(int x) {
        StringBuilder sb_01;
        Long result = 0;
        If (x >= 0) {
            Sb_01 = new StringBuilder(String.valueOf(x));
        } else {
            Sb_01 = new StringBuilder(String.valueOf(x).substring(1, String.valueOf(x).length()));
        }
        For(int i = 0; i<sb_01.length();i++){
            Int tmp = Integer.parseInt(sb_01.substring(i,i+1));
            Result +=(Math.pow(10,i)*tmp);
        }
        If(result<Integer.MIN_VALUE || result>Integer.MAX_VALUE){
            Result = 0;
        }
        Return x>0?(int)result:-(int)result;
    }

(三)387. The first unique character in the string:

题内容:

难级级:Easy

解解思想一:(1)Double loop traversal And change the string: traverse the repeat element to 'A'. If there is a change, set flag to true, and new_str[i] will also be set to 'A'. (2) Loop through the string to find the first element that is not equal to 'A'. Note: If the compared element is ‘A’, then it will not be compared, and the next one will speed up the efficiency.

解题思维二: Other people's method: Ten times faster than my method, the idea is more singular, mainly to traverse the elements of az, record whether the first occurrence of the position and the last position is the same, If they are the same, it means that it only appears once, and the position of the point is recorded. If there is a smaller position, it is continuously updated. If it is different, it will not be processed. The final decision is to set it to -1 if they are all equal.

码:

Public static int firstUniqChar(String s) {
        Char[] new_str = s.toCharArray();
        Boolean flag = false;
        // traverse and change the string. First, try to reduce the complexity; second, see the conditions clearly, if there is no result output -1, not 0. Thank you.
        If (new_str.length != 0) {
            For (int i = 0; i < s.length() - 1; i++) {
                If (new_str[i] != 'A') {
                    For (int j = i + 1; j < s.length(); j++) {
                        / / traversing once to set the repeating element to 'A'. If there is a change, set flag to true, prompting new_str[i] to also be set to 'A'
                        If (new_str[i] == new_str[j]) {
                            Flag = true;
                            New_str[j] = 'A';
                        }
                    }
                    If (flag) {
                        New_str[i] = 'A';
                    }
                    Flag = false;
                }
            }
            Int result = -1;
            For (int i = 0; i < s.length(); i++) {
                If (new_str[i] != 'A') {
                    Result = i;
                    Break;
                }
            }
            Return result;
        } else {
            Return -1;
        }
    }
    //It is ten times faster than my time. The idea is more singular, mainly to traverse the elements of a-z, and record whether the position where it first appears and the position that appears last time are the same.
// If they are the same, it means that it only appears once and records the position of the point. And keep updating it, if it is different, you don't have to deal with it. The final decision is to set it to -1 if they are all equal.
// public static int firstUniqChar(String s) {
// int index=-1;
// int result=s.length();
// for(char ch='a';ch<='z';ch++){
// index=s.indexOf(ch);
// if (index!=-1&&index==s.lastIndexOf(ch)){
// result = result>index?index:result;
// }
// }
// return result> s.length()-1?-1:result;
// }

(四)242. Valid letter ectopic:

题内容:

难级级:Easy

解解思想一:(1)String to array ; 2. Use the API to sort the array; 3. Compare each element of the array to determine whether they are equal.

解解思维二: Others' methods: 5 times faster than mine. (1) Create two arrays for storing the number of occurrences of each of the 26 characters; (2) perform traversal, if a appears 5 times, then sArr[1]=5; (3) determine two arrays Whether each position is equal.

//(1) string to array; 2. use the API to sort the array; 3. compare each element of the array to determine whether it is equal.
// public static boolean isAnagram(String s, String t) {
// if (s.length() == t.length()) {
// char[] arrays_01 = s.toCharArray();
// char[] arrays_02 = t.toCharArray();
// Arrays.sort(arrays_01);
// Arrays.sort(arrays_02);
// for(int i = 0;i<arrays_01.length;i++){
// if(arrays_01[i] != arrays_02[i]){
// return false;
// }
// }
// return true;
// } else {
// return false;
// }
// }
    //5 times faster than mine. (1) Create two arrays for storing the number of occurrences of each of the 26 characters; (2) perform traversal, if a appears 5 times, then sArr[1]=5;
    //(3) Determine if each position of the two arrays is equal.
Public static boolean isAnagram(String s, String t) {
    Int[] sArr = new int[26];
    Int[] tArr = new int[26];
    For(char c : s.toCharArray()){
        sArr[c - 'a']++;
    }
    For(char c : t.toCharArray()){
        tArr[c - 'a']++;
    }
    For(int i=0;i<26;i++){
        If(sArr[i] != tArr[i])
            Return false;
    }
    Return true;

}

(五)125. Verification palindrome:

题内容:

难级级:Easy

解解思想一:(1)Create a new Arraylist array, forward traversal If it is a letter and a number, add it to form a new array. (2) traverse the direction again, if arrayList_01.get(i)!=arrayList_01.get(arrayList_01.size()-1-i), then return false, only need to traverse the subscript to arrayList_01.size()/2 Just fine.

解题思维2: Other people's methods: no additional storage space, use their own array to traverse from the front and back at the same time, and then use the isLetterOrDigit and toLowerCase two API to calculate. Stop when low>=high.

码:

// public static boolean isPalindrome(String s) {
// ArrayList <Character>arrayList_01 = new ArrayList<Character>();
// if(s.length()>1) {
// for (int i = 0; i < s.length(); i++) {
// if ((s.charAt(i) >= 'a' && s.charAt(i) <= 'z') || (s.charAt(i) >= 'A' && s.charAt(i) <= 'Z')
// || (s.charAt(i) >= '0' && s.charAt(i) <= '9')) {
// if (s.charAt(i) >= 'A' && s.charAt(i) <= 'Z') {
// arrayList_01.add((char) (s.charAt(i)+32));
// } else {
// arrayList_01.add(s.charAt(i));
// }
// }
// }
// for(int i = 0;i<arrayList_01.size()/2;i++){
// if(arrayList_01.get(i)!=arrayList_01.get(arrayList_01.size()-1-i)){
// return false;
// }
// }
// return true;
// }else{
// return true;
// }
// }
    //2. His solution is to use no additional storage space, use its own array to traverse from the front and back at the same time, and then use isLetterOrDigit and
// toLowerCase two APIs to calculate specifically. When low>=high is stopped.
Public static boolean isPalindrome(String s) {
    If(s.isEmpty()){
        Return true;
    }
    Int head=0,tail=s.length()-1;
    Char cHead,cTail;
    While(head<tail){
        cHead=s.charAt(head);
        cTail=s.charAt(tail);
        If(!Character.isLetterOrDigit(cHead)){
            Head++;
        }
        Else if(!Character.isLetterOrDigit(cTail)){
            Tail--;
        }
        Else{
            If(Character.toLowerCase(cHead)!=Character.toLowerCase(cTail))
                Return false;
            Head++;
            Tail--;
        }

    }
    Return true;
}

(六)8. String to integer (atoi):

题内容:

难级级:Medium

解解思想一:Medium's question really considers more, (1) After converting the string into a character array, traversing the array once, setting the flag bit and considering the following five cases: (1) if it is a space and the flag is False, its subscript is incremented; (2) if it is - If the number is + or + and the flag is False, add it to the array; (3) If the number is not between 0-9, and the flag is flase, it will jump out; (4) If it is 0-9, Add it to the array; (5) If the flag is true, if the number is not 0-9, it will pop up. (2) Check the validity of the string. The length of the string is zero, etc.; (3) using the try...catch conversion failure exception to get more than 2^31.

解题思维2: Other people's method: twice faster than me, the idea is particularly clear: make full use of the trim() API: (1) first judge the string is empty and str.trim length is zero (2) first judge the first character of the string after trim and then +-; (3) then read the characters one by one, and calculate the res value if the character character is >=0<=9; When it is greater than MAx or <min, it returns the corresponding maximum and minimum value; if it is not a number, it breaks; (4) Finally, according to the value of +- output, the idea is too clear.

码:

// public static int myAtoi(String str) {
// char[] new_str = str.toCharArray();
// boolean flag = false;
// String result = new String();
// Set the flag bit, which is divided into four cases. (1) If it is a space and the flag is False, its subscript is incremented; (2) If it is a - sign and the flag is False, it is added to the array;
// (3) If the number is not between 0-9, and the flag is flase, it will jump out; (4) If it is at the time, add it to the array; (5) If the flag is true, if the number is not 0-9, jump out
// for (int i = 0; i < new_str.length; i++) {
// if (new_str[i] == 32 && !flag) {
// continue;
// } else if (new_str[i] == 45 && !flag || new_str[i] == 43 && !flag) {
// result += new_str[i];
// flag = true;
// } else if ((new_str[i] < 48 && !flag) || (new_str[i] > 57 && !flag)) {
// break;
// } else if (new_str[i] >= 48 && new_str[i] <= 57) {
// result += new_str[i];
// flag = true;
// } else if (flag) {
// break;
// }
// }
// boolean flag_02 = false;
// if (result.length() != 0) {
// if ((result.charAt(0) != 45 && result.charAt(0) < 48 && result.charAt(0) != 43)
// || result.charAt(0) != 45 && result.charAt(0) != 43 && result.charAt(0) > 57) {
// flag_02 = true;
// }
// //Check the validity of the string, traverse it again
// for (int i = 1; i < result.length(); i++) {
// if (result.charAt(i) < 48 && result.charAt(i) > 57) {
// flag_02 = true;
// }
// }
// if (result.charAt(0) == 45 && result.length() == 1 || result.charAt(0) == 43 && result.length() == 1) {
// return 0;
// }
// } else {
// return 0;
// }
// long back_result;
// // This piece uses try...catch, my little brother, isn’t it silly.
// try {
// back_result = Long.parseLong(result);
// // Output the result if <min_value, if >max_value. If normal.
// } catch (Exception ee) {
// if (result.charAt(0) == '-')
// return Integer.MIN_VALUE;
// else
// return Integer.MAX_VALUE;
// }
//
// if (flag_02) {
// return 0;
// } else {
// if (back_result < Integer.MIN_VALUE) {
// return Integer.MIN_VALUE;
// } else if (back_result > Integer.MAX_VALUE) {
// return Integer.MAX_VALUE;
// } else {
// return (int) back_result;
// }
// }
// }
    / / twice faster than me, the idea is particularly clear (1) first judge the string is empty and str.trim length is zero; (2) first judge the string after the trim +-;
    //(3) Then read the characters one by one, and calculate the res value if the character character is >=0<=9; if it is greater than MAx or <min, return the corresponding maximum and minimum value; if it is not a number, break;
    //(4) Finally judge +-, the idea is too clear.
    Public static int myAtoi(String str) {
        If(str == null || str.trim().length() == 0) return 0;
        Long res = 0;
        Int flag = 1;
        Int i = 0;
        String newstr = str.trim();
        If(newstr.charAt(i) == '+') {
            Flag = 1;
            i++;
        }else if(newstr.charAt(i) == '-'){
            Flag = -1;
            i++;
        }
        While(i < newstr.length()){
            If(newstr.charAt(i) >= '0' && newstr.charAt(i) <= '9'){
                Res = res * 10 + (newstr.charAt(i++) - '0');
                If(flag == 1 && res > Integer.MAX_VALUE) return Integer.MAX_VALUE;
                If(flag == -1 && (flag * res) < Integer.MIN_VALUE) return Integer.MIN_VALUE;
            }else{
                Break;
            }
        }
        Return flag == 1 ? (int)res : (int)(flag*res);
    }

(七)28. Implement strStr()

Topic content:

难级级级级级级##

@解解思思:1) The length of the string, if the first one is smaller than the second, then return -1; (2) record the index of each first equal position, and then compare on this basis, if traversing to the last element of the second string If they are equal, they end, and the position where return starts. If the middle is different, break breaks out; at the same time, it is necessary to prevent the first string from crossing the boundary during the traversal. (3) It is judged that the length of the second character string is not zero. The first pass failed to take into account: (1) the length of the haystack is less than the length of the needle; (2) the position acquired by the haystack cannot be out of bounds when compared.

解题思维2: Other people's methods: simple, use indexof API to solve, and in order to speed up execution time, first consider the case where the length of the needle is zero and the length of the haystack is zero.

码:

// does not take into account (1) the length of the haystack is less than the length of the needle; (2) the position acquired by the haystack cannot be out of bounds when compared.
    / / Solution ideas: (1) determine the length of two strings, if the first one is less than the second, then return -1; (2) record the index of the first equal position each time,
    // Then compare on this basis, if the last element traversed to the second string is equal, then the end, and the position where the return starts, if the middle is different, the break jumps out;
    // Also prevent the first string from crossing the boundary during the traversal.
    //(3) Determine that the length of the second string is not zero.
    //Execution time: 812ms
// public static int strStr(String haystack, String needle) {
// int backresult = -1;
// if (haystack.length() < needle.length()) {
// return -1;
// }
// if (needle.length() != 0) {
// for (int i = 0; i < haystack.length(); i++) {
// int j;
// if (haystack.charAt(i) == needle.charAt(0)) {
// for (j = 0; j < needle.length(); j++) {
// if (i + j < haystack.length()) { // must not exceed the length of haystack
// if (haystack.charAt(i + j) == needle.charAt(j)) {
// continue;
// } else {
// break;
// }
// }else{
// break;
// }
// }
// if (j == needle.length()) {
// return i;
// }
// }
// }
// return backresult;
// } else {
// return 0;
// }
// }

    / / Use the indexof API to calculate the position of the needle in the haystack, and also need to consider the case where the length of the needle is zero and the length of the haystack is zero. Execution time: 6ms
    Public static int strStr(String haystack, String needle) {
        Int m = needle.length();//needle string length
        If (m == 0) {
            Return 0;
        } else {
            If (haystack.length() == 0) {
                Return -1;
            } else {
                //return haystack.substr(needle); cannot directly use the substr function, substr indicates how long the specified output starts from the substring
                Return haystack.indexOf(needle);
            }
        }
    }

(八)38. Report number:

题Content:

难级级级级级级级级级级级级级级级级级级级级的级级和和和和和和和和和和和和和和和和和和和和和和和和和和和和和和和和和。

解题思想一: This question should be assigned to the medium, and the light understanding of the question will be a small half. 1. First split the string Stringbuilder, set the begin subscript position to 0, (1) If the character in the string is not equal to the latter, then the position and character of the begin subscript are counted in the ArrayList. (The number and number of repetitions are stored in the Arraylist), and the value of begin is updated; (2) If the end of the string is reached, it is also stored. 2. Update the Stringbuilder content, be careful when calculating, repeat n-1 times.

解题思维2: Other people's method: The execution time is 2ms, no extra space is needed. Every digital content has been determined, and only the number of times he appears is counted. Each time append(count).append(cha) is perfectly resolved, the number of statistics is reset each time the string and new characters are updated. Look at the code hahahaha. Append() can be played like this.

码:

Public class Main {

    Public static void main(String[] args) {
        // write your code here
        Int n = 4;
        System.out.println(countAndSay(6));
    }

// //Execution time 2ms;
// // Solution ideas: no extra space required. Every digital content has been determined, and only the number of times he appears is counted. Every time append(count).append(cha)
// // It works perfectly, resetting the number of statistics every time you update strings and new characters.
// public static String countAndSay(int n) {
// int count = 1;
// String s = "1";
// while (count ++ < n) {
// s = readString(s);
// }
// return s;
// }
//
// private static String readString(String s) {
// char[] chs = s.toCharArray();
// char c = chs[0];
// int count = 1;
// StringBuilder sb = new StringBuilder();
// for (int i = 1; i < chs.length; i++) {
// if (chs[i] == c) {
// count ++;
// } else {
// sb.append(count).append(c);
// c = chs[i];
// count = 1;
// }
// }
//
// sb.append(count).append(c);
// return sb.toString();
// }
    // Execution time: 9 ms, more than 55%.
    / / 1. First split the string Stringbuilder, set the begin subscript position to 0, if the character in the string is not equal to the latter, then the position and character of the begin subscript to the place, put into the ArrayList;
    //If the end of the string is reached, store it (first judge this)
    //2. Update the Stringbuilder content, be careful when calculating, repeat n-1 times.
    Public static String countAndSay(int n) {
        String init_Str = "1";
        StringBuilder init_stb = new StringBuilder(init_Str);
        For (int j = 0; j < n-1; j++) {
            Int begin = 0; // Record the beginning of each string.
            ArrayList<stru> arrArrayList_01 = new ArrayList<stru>();
            // Split each string into a corresponding ArrayList.
            For (int i = 0; i < init_stb.length(); i++) {
                If (i == init_stb.length() - 1) {
                    Stru stru_01 = new stru();
                    Stru_01.array_con = init_stb.charAt(i);
                    Stru_01.array_amo = init_stb.length() - begin;
                    arrArrayList_01.add(stru_01);//Store the length and contents into the array.
                } else if (init_stb.charAt(i) != init_stb.charAt(i + 1)) {
                    Stru stru_01 = new stru();
                    Stru_01.array_con = init_stb.charAt(i);
                    Stru_01.array_amo = i + 1 - begin;
                    arrArrayList_01.add(stru_01);//Store the length and contents into the array.
                    Begin = i + 1; / / update the position where the split string begins.
                }
            }
            / / Update the contents of the old array.
            For (int i = 0; i < arrArrayList_01.size(); i++) {
                Init_stb.replace(i * 2, i * 2 + 1, String.valueOf(arrArrayList_01.get(i).array_amo));
                Init_stb.replace(i * 2 + 1, i * 2 + 2, String.valueOf(arrArrayList_01.get(i).array_con));
            }
        }
        Return init_stb.toString();
    }

}

Class stru {
    Char array_con;//content
    Int array_amo;//number
}

(九)14. The longest public prefix:

topic content:

difficulty level and execution time: Easy, 12ms.

解解思一一: (1) first find the length of the smallest string, and then record it; (2) the minimum length for the outer loop. The inner loop is performed with the length of the array, and the traversal is performed. If the former is equal to the latter, the string is accumulated and the first digits of the second and third strings are compared. If not, break, set the flag, tell the system to end; if the last string is equal to the length of the array, compare the next bit. (The first commit did not take into account: if the array length is empty, it returns an empty string; if the length is 1, it returns all the strings of the first array).

解解思思2: Other people's method: Execution time: 6 ms. The idea is more succinct, making full use of the indexof API. (1) If the character array length is zero, then return is empty; (2) the first element of the record array is result; (3) traversing each subsequent string, if indexof() is not zero, the intercepted character String (0, s.length()-1), if zero, indexof(s) on the next string.

码:

/ / Solution: 1. First find the length of the smallest string, and then record it; 2. The minimum length for the outer loop. Traverse the inner loop with the length of the array,
    // If the former is equal to the latter, accumulate the string and compare the first digits of the second and third strings. If not waiting, break, set flag, tell the system to end; if the last string
    // equals the length of the array, then compares the next one. (The first commit does not take into account: if the array length is empty, it returns an empty string; if the length is 1, returns all the strings of the first array
    // Execution time: 12 ms
// public static String longestCommonPrefix(String[] strs) {
// if(strs.length == 0) return "";
// if(strs.length == 1) return strs[0];
// String result = new String();
// int min = strs[0].length();
// for (int i = 1; i < strs.length; i++) {
// if (min > strs[i].length()) {
// min = strs[i].length();
// }
// }
// boolean flag = false;
// for (int i = 0; i < min; i++) {
// for(int j = 0;j<strs.length-1;j++){
// if(strs[j].charAt(i) == strs[j+1].charAt(i)){
// if(j==strs.length-2){
// result += strs[j].charAt(i);
// }
// continue;
// }else{
// flag =true;
// break;
// }
// }
// if(flag) break;
// }
// return result;
// }
    // Execution time: 6 ms
    //1. If the character array length is zero, then return is empty; 2. Record the first array as result; 3. traverse each subsequent string, if indexof()
    //Not zero, then for s-1, iterate over all the strings in the array. If not, then -- if it contains, the next string. Very curious thinking. Take advantage of the indexof API.
    Public static String longestCommonPrefix(String[] strs) {
        If (strs.length == 0) {
            Return "";
        }
        String s = strs[0];
        For (int i = 1; i < strs.length; i++) {
            While (strs[i].indexOf(s) != 0) {
                s = s.substring(0, s.length() - 1);
                If (s.isEmpty()) {
                    Return "";
                }
            }
        }
        Return s;
    }