初级算法02

用时：2.5min

class Solution {
    public void reverseString(char[] s) {
        /** 遍历左右指针交换字符 */
        int l = 0, r = s.length - 1;
        while(l < r){
            char t = s[l];
            s[l] = s[r];
            s[r] = t;
            l++;
            r--;
        }
    }
}

耗时：46min

/* 第一版有问题  最初的思路*/
class Solution {
    public int reverse(int x) {
        /** 记录正负数。然后转换为字符串反转，在转换为数的过程中判断是否超范围 */
        int f = 1;
        if(x < 0){
            f = -1;
            x *= -1;
        }
        char [] s = new String(x + "").toCharArray();
        int convertNum = 0, p = 1;
        for(char c : s){
            if(convertNum * f > Integer.MAX_VALUE / 10 || convertNum * f < Integer.MIN_VALUE / 10){
                return 0;
            }
            convertNum +=(c - '0') * p;
            p *= 10;
        }
        return convertNum * f;
    }
}

/* 第二版 还是采用字符数组的方式 */
class Solution {
    public int reverse(int x) {
        int p = 1;
        if (x < 0) {
            p = -1;
            x *= -1;
        }
        
        char[] digits = Integer.toString(x).toCharArray();
        int left = 0, right = digits.length - 1;
        while (left < right) {
            char temp = digits[left];
            digits[left] = digits[right];
            digits[right] = temp;
            left++;
            right--;
        }
        
        long result = 0;
        for (char digit : digits) {
            result = result * 10 + (digit - '0');
            if (result > Integer.MAX_VALUE || result < Integer.MIN_VALUE) {
                return 0; // 溢出处理
            }
        }
        
        return (int) (result * p);
    }
}
/* 第三版采用数学运算的优化方式*/
class Solution {
    public int reverse(int x) {
        int sum = 0;
        while(x != 0){
            int remainder = x % 10;
            x /= 10;
            if(sum > Integer.MAX_VALUE / 10 || sum < Integer.MIN_VALUE / 10){
                return 0;
            }
            sum = sum * 10 + remainder;
        }
        return sum;
    }
}

耗时：8min

class Solution {
    public int firstUniqChar(String s) {
        if(s.length() == 1){
            return 0;
        }
        int [] arr = new int[26];
        for(char c : s.toCharArray()){
            arr[c - 'a']++;
        }
        for(int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            if(arr[c - 'a'] == 1){
                return i;
            }
        }
        return -1;
    }
}

耗时：3min

class Solution {
    public boolean isAnagram(String s, String t) {
        if(s.length() != t.length()){
            return false;
        }
        int [] letter = new int[26];
        for(char c : s.toCharArray()){
            letter[c - 'a']++;
        }
        for(char c : t.toCharArray()){
            if(letter[c - 'a'] < 1){
                return false;
            }
            letter[c - 'a']--;
        }
        return true;
    }
}

耗时：24min

class Solution {
    public boolean isPalindrome(String s) {
        String dealStr = s.replaceAll("[^a-zA-Z0-9]", "").toLowerCase();
        int l = 0, r = dealStr.length() - 1;
        while(l < r){
            if(dealStr.charAt(l) != dealStr.charAt(r)){
                return false;
            }
            l++;
            r--;
        }
        return true;
    }
}

耗时：39min

class Solution {
    public int myAtoi(String s) {
        StringBuilder sb = new StringBuilder();
        String str = s.trim();
        int sign = 1;
        for(int i = 0; i < str.length(); i++){
            char c = str.charAt(i);
            // 符号
            if(c == '-' && i == 0){
                sign = -1;
                continue;
            }
            if(c == '+' && i == 0){
                continue;
            }
            // 非数字字符
            if(c < '0' || c > '9'){
                break;
            } 
            // 过滤前导零
            if(c == '0' && sb.length() == 0){
                if(i + 1 < str.length() && (str.charAt(i + 1) < '0' ||str.charAt(i + 1) > '9')){
                    break;
                }
                continue;
            }
            if(c == '0' && sb.length() == 0){
                continue;
            }
            sb.append(c);
        }

        // 计算整数值
        int sum = 0;
        for(char c : sb.toString().toCharArray()){
            // // 超范围
            // if(sum > Integer.MAX_VALUE / 10 || sum < Integer.MIN_VALUE  / 10){
            //     return sum > Integer.MAX_VALUE / 10 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
            // }
                if(sum > Integer.MAX_VALUE/10 || (sum == Integer.MAX_VALUE/10&&(c - '0')>Integer.MAX_VALUE%10)){
                    return Integer.MAX_VALUE;
                }

                if(sum < Integer.MIN_VALUE/10 || (sum == Integer.MIN_VALUE/10&&-(c - '0')<Integer.MIN_VALUE%10)){
                    return Integer.MIN_VALUE;
                }
            sum = sum * 10 + (c - '0') * sign;
        }
        return sum ;
    }
}

耗时：8.5min

class Solution {
    public int strStr(String haystack, String needle) {
         return haystack.indexOf(needle);
    }
}

耗时：9min(直接看的题解)

class Solution {
    public String countAndSay(int n) {
        String str = "1";
        for (int i = 2; i <= n; ++i) {
            StringBuilder sb = new StringBuilder();
            int start = 0;
            int pos = 0;

            while (pos < str.length()) {
                while (pos < str.length() && str.charAt(pos) == str.charAt(start)) {
                    pos++;
                }
                sb.append(Integer.toString(pos - start)).append(str.charAt(start));
                start = pos;
            }
            str = sb.toString();
        }
        
        return str;
    }
}

耗时：5min(看了大佬的思路)

class Solution {
    public String longestCommonPrefix(String[] strs) {
        /** 默认第一个字符串就是他们的公共前缀，依次比较删除 */
        String pre = strs[0];
        for(int i = 1; i < strs.length; i++){
            while(strs[i].indexOf(pre) != 0){
                pre = pre.substring(0, pre.length() - 1);
            }
        }
        return pre;
    }
}