LeetCode刷题笔记——腾讯面试精选50题（3）

字符串

反转字符串

思路：一前一后双指针，直至两指针相遇，交换它们。

class Solution {
    public void reverseString(char[] s) {
        int l = 0, r = s.length-1;
        while (l<r) {
            char temp = s[l];
            s[l] = s[r];
            s[r] = temp;
            l++;
            r--;
        }
    }
}

反转字符串中的单词 III

思路：遍历字符串，遇到字母，把它添加到一个字符串缓存中，遇到空格，把字符串缓存提取出来翻转并放入结果字符串中。

class Solution {
    public String reverseWords(String s) {
        StringBuilder res = new StringBuilder();
        StringBuilder word = new StringBuilder();
        for (int i=0; i<s.length(); i++) {
            char c = s.charAt(i);
            if (c==' ') {
                res.append(reverse(word.toString())+" ");
                word = new StringBuilder();
            } else {
                word.append(c);
            }
        }
        res.append(reverse(word.toString()));
        return res.toString();
    }

    public String reverse(String s) {
        char[] c = s.toCharArray();
        int l=0, r=c.length-1;
        while (l<r) {
            char temp = c[l];
            c[l] = c[r];
            c[r] = temp;
            l++;
            r--;
        }
        return String.valueOf(c);
    }
}

最长公共前缀

思路：选取第一个字符串为公共子串，然后遍历其他字串，维持或缩小公共前缀的长度，最终结果为全部字符串的公共子串。

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs.length==0) return "";
        String prefix = strs[0];
        for (String str: strs) {
            while (str.indexOf(prefix) != 0) {
                prefix = prefix.substring(0, prefix.length()-1);
                if (prefix.isEmpty()) return "";
            }
        }
        return prefix;
    }
}

字符串相乘

标签：字符串

思路：字符串模拟竖式乘法。长度为M的数字字符串num1和长度为N的数字字符串num2乘积的长度不超过M+N，其中num1[i]和num2[j]的乘积位于结果的[i+j, i+j+1]两位，将这些和累加可得结果。注意最终结果要去掉前面无意义的零。

class Solution {
    public String multiply(String num1, String num2) {
        if (num1.equals("0") || num2.equals("0")) return "0";
        char[] char1 = num1.toCharArray();
        char[] char2 = num2.toCharArray();
        int len1 = char1.length, len2 = char2.length;
        int[] res = new int[len1+len2];
        for (int i=len1-1; i>=0; i--) {
            for (int j=len2-1; j>=0; j--) {
                int temp = res[i+j+1]+(char1[i]-'0')*(char2[j]-'0');
                res[i+j+1] = temp%10;
                res[i+j] += temp/10;
            }
        }
        StringBuilder sb = new StringBuilder();
        for (int k=0; k<res.length; k++) {
            if (k==0 && res[k]==0) continue;
            sb.append(res[k]);
        }
        return sb.toString();
    }
}

最长回文子串

思路：中心拓展法：回文子串有两种形式，一种是以一个字符为中心向两边拓展，一种是以一对相同的字符为中心向两边拓展。遍历字符串，记录回文子串的最长长度，并更新最长回文子串的起始位置和结束位置。

class Solution {
    public String longestPalindrome(String s) {
        if (s==null || s.length()==0) return "";
        char[] str = s.toCharArray();
        int start = 0, end = 0;//记录回文子串起始和终止的下标
        int len = 0;
        for (int i=0; i<str.length; i++) {
            int len1 = getPalindromeLength(str, i, i);//奇数长度的回文子串
            int len2 = getPalindromeLength(str, i, i+1);//偶数长度的回文子串
            len = Math.max(Math.max(len1, len2), len);
            if (len > (end-start+1)) {
                start = i-(len-1)/2;
                end = i+len/2;
            }
        }
        return s.substring(start, end+1);
    }
    // 获取以str[i]、str[j]为中心的回文子串的长度
    public int getPalindromeLength(char[] str, int i, int j) {
        while (i>=0 && j<str.length && str[i]==str[j]) {
            i--;
            j++;
        }
        return j-i-1;
    }
}

字符串转换整数 (atoi)

思路：要考虑的点：

1. 数字是否合法
2. 正负号
3. Integer溢出（测试用例中使用了即使是Long都会溢出的例子）

class Solution {
    public int myAtoi(String str) {
        char[] chars = str.toCharArray();
        int n = chars.length, start=0, end=0;
        if (n<1) return 0;
        for (int i=0; i<n; i++) {
            if (chars[i]!=' ') {
                if (chars[i]=='+'||chars[i]=='-'||(chars[i]<='9'&&chars[i]>='0')) {
                    start = i;
                    break;
                } else return 0;
            }
        }
        for (int j=start+1; j<=n; j++) {
            if (j==n || chars[j]>'9' || chars[j]<'0') {
                end = j-1;
                break;
            }
        }
        int res = myAtoi(chars, start, end);
        return res;
    }

    public int myAtoi(char[] chars, int start, int end) {
        long number = 0L;
        boolean isNegative = false;
        if (chars[start]=='-') {
            isNegative = true;
            start++;
        } else if (chars[start]=='+') start++;
        while(start<=end&&chars[start]<='9'&&chars[start]>='0') {
            number = number*10 + chars[start++] - '0';
            if (!isNegative && number > Integer.MAX_VALUE) return Integer.MAX_VALUE;
            if (isNegative && -1*number < Integer.MIN_VALUE) return Integer.MIN_VALUE;
        }
        if (!isNegative) return (int)number;
        else return -1*(int)number;
    }
}

位运算

只出现一次的数字

思路：本题要求使用线性时间复杂度和不使用额外的空间复杂度。利用异或运算（相同为0，不同为1，以及0^n=n）来解决此问题。

class Solution {
    public int singleNumber(int[] nums) {
        int xorSum = 0;
        for (int num: nums) {
            xorSum ^= num;
        }
        return xorSum;
    }
}

2的幂

思路：利用2进制：2^n的2进制只有1位为1，其余为0；2^n-1的2进制全为1，但位数比2^n少一位。对他们求与运算为0。

class Solution {
    public boolean isPowerOfTwo(int n) {
        if (n<=0) return false;
        return (n&(n-1)) == 0;
    }
}