Leetcode 02: sword finger offer 58 - I. flip the word order (simple); T123. Verify palindrome string; T9. Palindromes

T4: The finger of the sword Offer 58 - I. Flip word order （ Simple ）

Enter an English sentence , Turn over the order of the words in the sentence , But the order of the characters in the word is the same . For the sake of simplicity , Punctuation is treated like ordinary letters . For example, input string "I am a student. “, The output "student. a am I”.

explain ：

No space characters make up a word .
The input string can contain extra spaces before or after , But the reversed characters cannot include .
If there are extra spaces between two words , Reduce the space between inverted words to just one .

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/fan-zhuan-dan-ci-shun-xu-lcof
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Ideas

Double finger needling , Two pointers are upside down , If you encounter a space, skip . Note that the first space is removed at the end , multi-purpose while

solution :

class Solution {
    public String reverseWords(String s) {
        String tmp = s.trim();
        int start = tmp.length() - 1;
        int end = tmp.length() - 1;
        String res = "";
        while(start >= 0) {
            while(start >= 0 && tmp.charAt(start) != ' ') {
                start--;
            }
            res += tmp.substring(start + 1, end + 1) + " ";
            while(start >= 0 && tmp.charAt(start) == ' ') {
                start--;
            }
            end = start;
        }
        return res.trim();
    }
}

T5: 125. Verify the palindrome string （ Simple ）

Given a string , Verify that it is a palindrome string , Consider only alphabetic and numeric characters , The case of letters can be ignored .

explain ： In this question , We define an empty string as a valid palindrome string .

Example 1:

 Input : "A man, a plan, a canal: Panama"
 Output : true

Example 2:

 Input : "race a car"
 Output : false

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/valid-palindrome
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Ideas

Reverse and compare the strings or use double pointers to determine

solution 1: Reverse the string and compare

class Solution {
    
    public boolean isPalindrome(String s) {
    
        StringBuffer sb = new StringBuffer();
        for(int i = 0; i<s.length();++i){
    
            if(Character.isLetterOrDigit(s.charAt(i))){
    
                sb.append(Character.toLowerCase(s.charAt(i)));
            }
        }
        StringBuffer sb2 = new StringBuffer(sb).reverse();
        return sb.toString().equals(sb2.toString());
//  Why is this wrong 
// StringBuffer sb2 = sb.reverse();
// return sb.toString().equals(sb2.toString());
    }
}

Execution time ：6 ms, In all Java Defeated in submission **30.08%** Users of

Memory consumption ：38.6 MB, In all Java Defeated in submission **37.37%** Users of

solution 2: In situ comparison double pointer

class Solution {
    
    public boolean isPalindrome(String s) {
    
        int n = s.length();
        int left = 0, right = n - 1;
        while (left < right) {
    
            while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {
    
                ++left;
            }
            while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {
    
                --right;
            }
            if (left < right) {
    
                if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
    
                    return false;
                }
                ++left;
                --right;
            }
        }
        return true;
    }
}

Execution time ：3 ms, In all Java Defeated in submission **92.88%** Users of

Memory consumption ：38.3 MB, In all Java Defeated in submission **87.85%** Users of

Time complexity ：O(|s|), among |s| Is string s The length of .

Spatial complexity ：O(1).

T6: 9. Palindrome number （ Simple ）

Give you an integer x , If x Is a palindrome integer , return true ; otherwise , return false .

Palindrome number refers to positive order （ From left to right ） Reverse order （ From right to left ） Read all the same integers . for example ,121 It's palindrome. , and 123 No .

Example 1：

 Input ：x = 121
 Output ：true

Example 2：

 Input ：x = -121
 Output ：false
 explain ： Read left to right ,  by  -121 .  Read right to left ,  by  121- . So it's not a palindrome number .

Example 3：

 Input ：x = 10
 Output ：false
 explain ： Read right to left ,  by  01 . So it's not a palindrome number .

Example 4：

 Input ：x = -101
 Output ：false

Tips ：

• 231 <= x <= 231 - 1

Advanced ： Can you solve this problem without converting integers into strings ？

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/palindrome-number
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Ideas

First, replace the integer with a string, and then double pointers

solution : Double pointer

class Solution {
    
    public boolean isPalindrome(int x) {
    
        if(x<0){
    
            return false;
        }
        if(x>=0&&x<10){
    
            return true;
        }
        String str = x + "";
        int left = 0, right = str.length()-1;
        while(left<right){
    
            if(str.charAt(left)!=str.charAt(right)){
    
                return false;
            }
            ++left;
            --right;
        }
        return true;
    }
}

Execution time ：18 ms, In all Java Defeated in submission **10.15%** Users of

Memory consumption ：38.1 MB, In all Java Defeated in submission **25.11%** Users of