leetcode

本文最后更新于：1 年前

[TOC]

有序数组，交换两数，找出这两个数的下标

思路

用两个标志位去找乱序的那两个数字。

1
2
3
4
5
6
7
8
9
10
11
12
public static int[] change(int[] nums) {
        int first = -1;
        int second = -1;
        int[] res = new int[2];
        for (int i = 1; i < nums.length; i++) {
            if (first == -1 && nums[i - 1] > nums[i]) first = i - 1;
            if (first != -1 && nums[i - 1] > nums[i]) second = i;
        }
        res[0] = first + 1;
        res[1] = second + 1;
        return res;
    }

括号的个数

【】【】【【】3】2

表示 1+1+2（3）=8 个括号

思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public static int getBox(String s) {
       Stack<Integer> stack = new Stack<>();
       int res = 0;
       for (int i = 0; i < s.length(); i++) {
           if (s.charAt(i) == '[') {
               stack.push(1);//保底一个
           } else if (s.charAt(i) == ']') {
               int temp = stack.pop();
               if (i + 1 < s.length() && s.charAt(i + 1) <= '9' && s.charAt(i + 1) > '0') {//后面为数字，要结算
                   temp *= (s.charAt(i + 1) - '0');
                   i++;//结算完跳过这个数字
               }
               if (stack.isEmpty()) {//空的，表示一个分段算完了
                   res += temp;
               } else {
                   int top = stack.pop() + temp;
                   stack.push(top);
               }
           }
       }
       return res;
   }



子串子序列

1，最长回文子串

动态规划：o（n^2）空间复杂度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public String longestPalindrome(String s) {
    int len = s.length();
    if (len < 2) return s;
    int maxLen = 1;
    int begin = 0;
    // dp[i][j] 表示 s[i, j] 是否是回文串
    boolean[][] dp = new boolean[len][len];
    char[] charArray = s.toCharArray();
    for (int i = 0; i < len; i++) {
        dp[i][i] = true;
    }
    for (int j = 1; j < len; j++) {
        for (int i = 0; i < j; i++) {
            if (charArray[i] != charArray[j]) {
                dp[i][j] = false;
            } else {
                if (j - i <= 2) {
                    dp[i][j] = true;
                } else {
                    dp[i][j] = dp[i + 1][j - 1];
                }
            }
            // 只要 dp[i][j] == true 成立，就表示子串 s[i..j] 是回文，此时记录回文长度和起始位置
            if (dp[i][j] && j - i + 1 > maxLen) {
                maxLen = j - i + 1;
                begin = i;
            }
        }
    }
    return s.substring(begin, begin + maxLen);
}

最优解：中心扩散法。o（1）空间复杂度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public static String longestPalindrome(String s) {
       if (s.length() < 2) {
           return s;
       }
       int start = 0, max = 1;
       int len = s.length();
       for (int i = 0; i < len; ) {
           if (len - i <= max / 2) break;
           int left = i, right = i;
           while (right < len - 1 && s.charAt(right + 1) == s.charAt(right))
               ++right; //过滤掉重复的
           //下次在判断的时候从重复的下一个字符开始判断
           i = right + 1;
           //然后往两边判断，找出回文子串的长度
           while (right < len - 1 && left > 0 && s.charAt(right + 1) == s.charAt(left - 1)) {
               ++right;
               --left;
           }
           if (right - left + 1 > max) {
               max = right - left + 1;
               start = left;
           }
       }
       return s.substring(start, start + max);
   }

2，最长回文子序列

动态规划

dp[i][j]表示 i,j 范围的最长回文子序列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static int longestPalindromeSubseq(String s) {
    int[][] dp = new int[s.length()][s.length()];
    for (int i = s.length() - 1; i >= 0; i--) {
        dp[i][i] = 1;
        for (int j = i + 1; j < s.length(); j++) {
            if (s.charAt(i) == s.charAt(j)) {
                dp[i][j] = dp[i + 1][j - 1] + 2;
            } else {
                dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[0][s.length() - 1];
}

3，无重复最长子串

高频

思路：滑动窗口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public static int lengthOfLongestSubstring(String s){
        int len=s.length();
        HashMap<Character,Integer> map=new HashMap<>();
        int ans=0;
        int i=0;
        for (int j = 0; j < len; j++) {
            if (map.containsKey(s.charAt(j))){
                i=Math.max(i,map.get(s.charAt(j)));
            }
            ans=Math.max(ans,j-i+1);
            map.put(s.charAt(j),j+1);//
        }
        return ans;
    }

核心：发现了重复的字符，左边窗口就要向右一位。
    如下写法亦可。
     if (map.containsKey(s.charAt(j))){
                i=Math.max(i,map.get(s.charAt(j)+1));
            }
            ans=Math.max(ans,j-i+1);
            map.put(s.charAt(j),j);//
	}