LeetCode题目记录

用于记录LeetCode的题目、分析和答案。

4. Median of Two Sorted Arrays

描述

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

Example 1:

nums1 = [1, 3]
nums2 = [2]

The median is 2.0

Example 2:

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

分析

参考LeetCode给出的解答

题目要求寻找两个有序数组合并后的中位数且要求时间复杂度为$O(log(m+n))$,即需要采用二分法进行查找。

中位数即处在一个顺序数列中最中间的一个数（或两个数的平均值），因此，若将两个数列合二为一并进行排序形成num3，则：

$$Median= \begin{cases} num3[\frac{m+n+1}{2}-1]&m+n\text{ 为奇数}\\ \frac{num3[\frac{m+n+1}{2}-1]+num3[\frac{m+n+1}{2}]}{2}&m+n\text{ 为偶数} \end{cases}$$

设i为num1的索引，j为num2的索引，则

$$i+j=m-i+n-j$$

且

$$num2[j-1] \leq num1[j] \text{ and } num1[i-1] \geq num2[j]$$

对于$i=0$，$i=m$，$j=0$，$j=n$这种临界情况，在本题中表示已经获得了合适的$m, n$，可直接开始计算中位数。

当$m+n$为奇数时，中位数为

$$max(num1[i-1]+num2[j-1])$$

，若其中一个不存在则直接为另一个;

当$m+n$为奇数时，中位数为

$$\frac{max(num1[i-1]+num2[j-1])+min(num1[i]+num2[j])}{2}$$

，对$max$和$min$，若其中一个不存在则函数值直接为另一个。

实现

参考LeetCode给出的解答

代码

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;

        if (m > n) {
            int[] temp = nums1;
            nums1 = nums2;
            nums2 = temp;
            int temp2 = m;
            m = n;
            n = temp2;
        }
        int iMax = m, iMin = 0, half = (m + n + 1) / 2, i, j;
        while (iMax >= iMin) {
            i = (iMax + iMin) / 2;
            j = half - i;
            if (i < iMax && nums2[j - 1] > nums1[i]) {  //需将i < iMax写在前面以防止在i不是合法索引时执行后面的语句
                iMin = i + 1;  //i过小
            } else if (i > iMin && nums2[j] < nums1[i - 1]) { //同上
                iMax = i - 1;  //i过大
            } else {  //i正好
                int maxLeft;
                if (i == 0) {  //处理i = 0的特殊情况
                    maxLeft = nums2[j - 1];
                } else if (j == 0) {  //处理j = 0的特殊情况
                    maxLeft = nums1[i - 1];
                } else {
                    maxLeft = Math.max(nums1[i - 1], nums2[j - 1]);
                }
                if ((m + n) % 2 == 1) {  //m + n为奇数时中位数为maxLeft
                    return maxLeft;
                }
                int minRight;  //m + n为偶数时还需求取minRight, 中位数为两者平均值
                if (i == m) {
                    minRight = nums2[j];
                } else if (j == n) {
                    minRight = nums1[i];
                } else {
                    minRight = Math.min(nums1[i], nums2[j]);
                }
                return (maxLeft + minRight) / 2.0;
            }
        }
        return 0.0;
    }
}

复杂度分析

• 时间复杂度：$O(log(min(m,n)))$

  在该算法中，对两字符串中短的那一个进行了二分法查找，因此时间复杂度为$O(log(min(m,n)))$。

• 空间复杂度：$O(1)$

  在该算法中使用了9个变量（m, n, temp1, temp2, iMax, iMin, half, maxLeft, minRight）来存储数据。

5. Longest Palindromic Substring

描述

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

Input: "cbbd"
Output: "bb"

分析

题目要求在给出的字符串中寻找最长回文子字符串，可采用以下几种方法：

寻找最大公共子串

可使用将原始字符串倒置形成新字符串并求取两字符串的最长公共子串的方式得到结果，但是需要注意检查字串在两字符串中的索引，以防出现输入aacdefcaa最终的出的结果为acc的情况发生。寻找最长公共子串可使用动态规划。假设该字符串长为$m$，原字符串为$x$，倒置后的字符串为$y$，则创建一个$(m+1)\times (m+1)$的二维数组，令$i,j$分别为两字符串的索引（从$1$到$m+1$表示字符串索引），计算过程中满足以下公式：

$$res[i][j]= \begin{cases} 0 & i=0 \text{ or } j=0\\ res[i-1][j-1]+1 & i,j>0\text{ and }x[i]=y[j]\\ 0 & i,j>0\text{ and }x[i]\ne y[j] \end{cases}$$

围绕中心扩张

回文字符串的特点为中心对称，即对于一个回文字符串来说，其沿中心对称的两个字符一定相同。对于一个长为$n$的字符串来说，其可能的对称中心为$2n-1$个（每一个字符以及每两个字符的中间都可能是对称中心）。因此可以对这$2n-1$个可能的中心沿中心向两边扩张，记录下最长的回文字符串即可。

Manacher’s Algorithm

参考 Manacher’s Algorithm 马拉车算法

实现

寻找最大公共字串

代码

class Solution {
    public static String longestPalindrome(String s) {
        String reverse = new StringBuffer(s).reverse().toString();
        int len = s.length();
        int[][] res = new int[len + 1][len + 1];
        int index = 0, subLen = 0;
        int i, j;
        for (i = 0; i <= len; i++) {
            for (j = 0; j <= len; j++) {
                if (i == 0 || j == 0) {
                    res[i][j] = 0;
                } else if (s.charAt(i - 1) == reverse.charAt(j - 1)) {
                    res[i][j] = res[i - 1][j - 1] + 1;
                    if (subLen - 1 < res[i - 1][j - 1]) {  //如果目前记录的最大长度小于此次计算后得到的长度
                        if (s.charAt(i - res[i][j]) == reverse.charAt(len - i)) {
                            //比较当前获得的最长公共字串的第一个字符是否与反转后该字串对应位置的字串的第一个字符相同
                            //防止 "aacdefcaa" 这种情况
                            index = i;
                            subLen = res[i][j];
                        }
                    }
                } else {
                    res[i][j] = 0;
                }
            }
        }
        StringBuilder result = new StringBuilder();
        for (j = index - subLen + 1; j <= index; j++) {
            result.append(s.charAt(j - 1));
        }
        return result.toString();
    }
}

复杂度分析

• 时间复杂度：$O(n^2)$

  在该算法中对创建的$(n+1)\times(n+1)$的二维数组进行了遍历。

• 空间复杂度：$O(n^2)$

  该算法创建了大小为$(n+1)\times (n+1)$的二维数组用来存储寻找最大公共字串时用到的数据。

围绕中心扩张

代码

class Solution {
    public String longestPalindrome(String s) {
        if (s.length() < 1)
            return "";
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            //分别以i和i与i+1之间为中心
            int len = Math.max(expandFromCenter(s, i, i), expandFromCenter(s, i, i+1));
            if (len - 1 > end - start) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        return s.substring(start, end + 1);  //substring 返回beginIndex到endIndex - 1的子字符串
    }

    private static int expandFromCenter(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return right - left - 1;
    }
}

复杂度分析

• 时间复杂度：$O(n^2)$

  对于expandFromCenter函数，其循环最多可能执行$n/2$次。

• 空间复杂度：$O(1)$

Manacher’s Algorithm

代码

class Solution {
    public String longestPalindrome(String s) {
        //预处理字符串，加入#
        StringBuilder temp = new StringBuilder("$#");
        for (int i = 0; i < s.length(); i++) {
            temp.append(s.charAt(i)).append("#");
        }
        temp.append("@");
        String t = temp.toString();
        int n = t.length();
        int[] p = new int[n];
        int right = 0, c = 0, len = 0, center = 0;
        for (int i = 1; i < n - 1; i++) {
            //若i未到达右端，在与i关于c对称的p[i]值和目前回文右中取较小的
            //若i到达右端，则令其p为1
            p[i] = right > i ? Math.min(p[2 * c - i], right - i) : 1;
            //对于被右端截断或者i到达右端的情况，使用中心扩张
            while (t.charAt(i + p[i]) == t.charAt(i - p[i])) {
                p[i]++;
            }
            //更新右边界
            if (right < i + p[i]) {
                right = i + p[i];
                c = i;
            }
            //取目前的最大回文的中心和长度
            if (len < p[i]) {
                len = p[i];
                center = i;
            }
        }
        return s.substring((center - len) / 2, len + (center - len) / 2 - 1);
    }
}

复杂度分析

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

6. ZigZag Conversion

描述

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P   A   H   N
A P L S I I G
Y   I   R

And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

string convert(string s, int numRows);

Example 1:

Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"

Example 2:

Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:

P     I    N
A   L S  I G
Y A   H R
P     I

分析

题目要求将给出的字符串排列成规定行数的“Z”字型（从上到下，再到右上），并输出按照从左到右、从上到下的正常顺序重新组合的字符串。

对“Z”字形排列进行观察可以发现，字符排列是有周期的，每个周期中第一行和最后一行只有一个字符，其它行则有两个。每个周期中每一行的第一个字符索引为：行数+单周期长度*目前已经过的周期数，而对于有第二个字符的行来说，第二个字符的索引为：单周期长度*（目前已经过的周期数+1）-行数。

实现

代码

来自LeetCode

class Solution {
    public String convert(String s, int numRows) {

        if (numRows == 1) return s;

        StringBuilder ret = new StringBuilder();
        int n = s.length();
        int cycleLen = 2 * numRows - 2;

        for (int i = 0; i < numRows; i++) {
            for (int j = 0; j + i < n; j += cycleLen) {
                ret.append(s.charAt(j + i));
                if (i != 0 && i != numRows - 1 && j + cycleLen - i < n)
                    ret.append(s.charAt(j + cycleLen - i));
            }
        }
        return ret.toString();
    }
}

复杂度分析

• 时间复杂度：$O(n)$

  字符串中每一个字符都只访问了一次。

• 空间复杂度：$O(n)$

  创建了一个长度与原字符串长度相同的字符串来存储转换后的字符串。

7. Reverse Integer

描述

Given a 32-bit signed integer, reverse digits of an integer.

Example 1:

>Input: 123
>Output: 321

Example 2:

>Input: -123
>Output: -321

Example 3:

>Input: 120
>Output: 21

Note:
Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.

分析

题目要求将输入的整数逆序后输出并保留正负号，且当处理后的数超过了32位int的范围时返回0。

得到逆序的数可使用不断对原数取除以10的余数并依次乘10相加即可得到逆转后的数。由于除法和取余会保留负号，因此无需对负号进行特殊处理。要验证得出的结果是否在32位int范围内（即[2147483647, -2147483648]），可验证目前已经得到的数（还未乘10并加上目前得到的余数前的数）是否小于MAX_INT / 10或者大于MIN_INT / 10，满足则未溢出；另外，若已经得到的数等于MAX_INT / 10，则需验证当前得到的余数是否大于7，若大于7则溢出，同时还需检验已经得到的数等于MIN_INT / 10，则需检验目前得到的余数是否小于-8，若小于-8则溢出。

实现

代码

class Solution {
    public int reverse(int x) {
        int result = 0;
        while (x != 0) {
            int num = x % 10;
            x /= 10;
            if (result > Integer.MAX_VALUE/10 || (result == Integer.MAX_VALUE / 10 && num > 7)) {
                return 0;
            } else if (result < Integer.MIN_VALUE / 10 || (result == Integer.MIN_VALUE / 10 && num < -8)) {
                return 0;
            }
            result = result * 10 + num;
        }
        return result;
    }
}

复杂度分析

• 时间复杂度：$O(log(x))$

  $x$中有$\lceil log_{10}(x)\rceil$ 或$\lceil log_{10}(x)\rceil + 1$个数字

• 空间复杂度：$O(1)$

8. String to Integer (atoi)

描述

Implement atoi which converts a string to an integer.

The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.

The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.

If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.

If no valid conversion could be performed, a zero value is returned.

Note:

• Only the space character ' ' is considered as whitespace character.
• Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. If the numerical value is out of the range of representable values, INT_MAX (231 − 1) or INT_MIN (−231) is returned.

Example 1:

Input: "42"
Output: 42

Example 2:

Input: "   -42"
Output: -42
Explanation: The first non-whitespace character is '-', which is the minus sign.
             Then take as many numerical digits as possible, which gets 42.

Example 3:

Input: "4193 with words"
Output: 4193
Explanation: Conversion stops at digit '3' as the next character is not a numerical digit.

Example 4:

Input: "words and 987"
Output: 0
Explanation: The first non-whitespace character is 'w', which is not a numerical 
             digit or a +/- sign. Therefore no valid conversion could be performed.

Example 5:

Input: "-91283472332"
Output: -2147483648
Explanation: The number "-91283472332" is out of the range of a 32-bit signed integer.
             Thefore INT_MIN (−231) is returned.

分析

题目给出一个字符串，要求获取其第一个不为空格的字符，若该字符为正号、负号或者数字，则获取其之后若干个数字，遇到其它字符则停止，最后将获取到的数字组合成int 类型的整数返回；若第一个非空格字符不是前面说的三种字符或该字符串为空或该字符串只包含空格，则直接返回0。另外，若组合成的数字超过了int类型的范围，则输出int类型的最大值或最小值（取决于获取的实际数字的正负）。

本题总的来说就是一堆if-else的堆砌（这也许就是该题在LeetCode上被骂的原因吧）。分析在下面代码的注释中。

实现

代码

class Solution {
    public int myAtoi(String str) {
        if (str.equals("")) {
            return 0;
        }
        int i = 0;
        int flag = 1;
        int result = 0;
        while (i < str.length() && str.charAt(i++) == ' ') ;  //让i到达非空格位
        i -= 1;
        //当str只有空格或接在空格后第一位不是数字或正负号时返回0
        if (i == str.length() || (str.charAt(i) != '-' && str.charAt(i) != '+' && str.charAt(i) < '0' && str.charAt(i) > '1')) {
            return 0;
        }
        //为正负号时处理i和符号标志位flag
        if (str.charAt(i) == '-') {
            flag = -flag;
            i++;
        } else if (str.charAt(i) == '+') {
            i++;
        }
        while (i < str.length() && str.charAt(i) >= '0' && str.charAt(i) <= '9') {
            int num = str.charAt(i) - '0';
            //当result在正数方向溢出时负数方向的输出一定为Integer.MIN_VALUE
            if (result > Integer.MAX_VALUE / 10 || (result == Integer.MAX_VALUE / 10 && num > 7)) {
                if (flag == 1) {
                    return Integer.MAX_VALUE;
                } else {
                    return Integer.MIN_VALUE;
                }
            }
            result = result * 10 + num;
            i++;
        }
        return result * flag;
    }
}

复杂度分析

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

9. Palindrome Number

描述

Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.

Example 1:

Input: 121
Output: true

Example 2:

Input: -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.

Example 3:

Input: 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.

Follow up:

Coud you solve it without converting the integer to a string?

分析

题目给出一个数字，要求判断该数字正读和反读是否相同。

可将该数字转换为字符串，判断逆转后的字符串和原字符串是否相同即可；也可以不借助字符串，将原数每位取余并逐位添加到新数上，最后比较两数是否相同。

实现

代码

class Solution {
    public boolean isPalindrome(int x) {
        //小于0一定不符合
        if (x < 0) {
            return false;
        }
        int source = x;
        int result = 0;
        //逆转
        while (x != 0) {
            int num = x % 10;
            x /= 10;
            //若超出int范围一定不符合
            if (result > Integer.MAX_VALUE / 10 || (result == Integer.MAX_VALUE / 10 && num > 7)) {
                return false;
            }
            result = result * 10 + num;
        }
        return result == source;
    }
}

复杂度分析

• 时间复杂度：$O(log(x))$
• 空间复杂度：$O(1)$

10. Regular Expression Matching

描述

Given an input string (s) and a pattern (p), implement regular expression matching with support for '.' and '*'.

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

Note:

• s could be empty and contains only lowercase letters a-z.
• p could be empty and contains only lowercase letters a-z, and characters like . or *.

Example 1:

Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Example 2:

Input:
s = "aa"
p = "a*"
Output: true
Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".

Example 3:

Input:
s = "ab"
p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".

Example 4:

Input:
s = "aab"
p = "c*a*b"
Output: true
Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore, it matches "aab".

Example 5:

Input:
s = "mississippi"
p = "mis*is*p*."
Output: false

分析

题目要求实现简单的正则匹配，只需支持.和*。

可采用递归或者动态规划。

实现

递归

代码

class Solution {
    public boolean isMatch(String s, String p) {
        //若p为空，则只有空字符串能匹配
        if (p.isEmpty()) return s.isEmpty();
        //匹配两字符串的第一个字符
        boolean first_match = (!s.isEmpty() &&
                (p.charAt(0) == s.charAt(0) || p.charAt(0) == '.'));
        if (p.length() >= 2 && p.charAt(1) == '*') {
            //如果p长度大于1且第二个字符为*，则表示第一个字符可匹配0次或者任意多次
            //||的前半部分表示匹配0次，后半部分表示至少匹配一次
            return (isMatch(s, p.substring(2)) ||
                    (first_match && isMatch(s.substring(1), p)));
        } else {
            //如果不满足if条件，则表示p要么长度为1，要么第二位不是*，则可直接继续匹配
            return first_match && isMatch(s.substring(1), p.substring(1));
        }
    }
}

复杂度分析

• 时间复杂度：