300. Longest Increasing Subsequence

发表于 | 分类于 | 阅读次数

DFS 的优化问题，当然是在想不到DP数组的情况下的优化，第二道是括号匹配问题，也是DFS，这种常考类型，很不好做。

  1. Given an unsorted array of integers, find the length of longest increasing subsequence.
    For example,
    Given[10, 9, 2, 5, 3, 7, 101, 18],
    The longest increasing subsequence is[2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.
    Your algorithm should run in O(n^2) complexity.

  2. Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.
    Note: The input string may contain letters other than the parentheses ( and ).
    Examples:

    1
    2
    3
    "()())()" -> ["()()()", "(())()"]
    "(a)())()" -> ["(a)()()", "(a())()"]
    ")(" -> [""]

[leetcode 300] Longest Increasing Subsequence

最简单的方法就是遍历一遍该数组，分别以每一个元素作为开头，然后向后查找大于前一个元素的数，将所有的情况走一遍，记录最大值，然后返回即可找到最大值，这个是万无一失也不用思考的解法，但是显然会超时，所以不可取，然后我就想如果用一个boolean类型记录走过的结点，不以走过的结点为起始结点即可，leetcode上提交后是21/24，上面的情况后面是会重复的，比如1,2,3,4,5,6,7,8我第一个for循环只能走1，到第二个for循环就能走1->2,1->3,1->4...，进一步是：1->2->3->4,1->3->4,1->4...，显然第二个走到3的没必要继续走了，第三个走到4的也没有必要继续走了，但是怎么样判断呢，于是想到用一个整形数组来记录当前数对应的最大步数，如果后面走到该数的时候，没有该数组对应的值大，那么就不向下走了，这样就不会重复了，那么果然leetcode就通过了，代码如下(当然是可以继续优化的，懒了…)：

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
public static int lengthOfLIS(int[] nums) {
    if(nums==null||nums.length==0)return 0;
    int count=0;
    boolean []flag=new boolean[nums.length];
    int[] curMax=new int[nums.length];
    for(int i=0;i<nums.length;i++){
        if(!flag[i]){
            flag[i]=true;
            count=Math.max(count,dfs(i,nums,nums[i],1,flag,curMax));
            //System.out.println("flag:"+i);
        }
    }
    return count;
}
private static int dfs(int i, int[] nums, int num,int out,boolean[]flag,int[]currMax) {
    if(i==nums.length-1){
        return out;
    }
    int temp=0;
    for(int j=i;j<nums.length;j++){
        if(nums[j]>num&&out>currMax[j]){
            flag[j]=true;
            currMax[j]=out;
            temp=Math.max(temp,dfs(j,nums,nums[j],out+1,flag,currMax));
        }
    }
    return Math.max(temp,out);
}

我想这种方法还是太过普通，于是看了一下leetcode上的discuss，果然不出所料，dp解法，我虽然知道dp可解，但是想不出来这个dp数组如何构造，下面这个代码主要是能够理解Arrays.binarySearch这个函数，我这里摘抄一下Arrays.binarySearch() 方便记忆版上面的解释：
1） binarySearch(Object[] a, Object key)
a: 要搜索的数组
key：要搜索的值
如果key在数组中，则返回搜索值的索引；
否则返回-1或“-”（插入点）。插入点是指索引键key将要插入数组的那一点，即第一个大于该键key的元素的索引。
[1] 搜索值不是数组元素，且在数组大小范围内，从0开始计数，得“ - 插入点索引值 -1”；
[2] 搜索值是数组元素，从0开始计数，得搜索值的索引值；
[3] 搜索值不是数组元素，且大于数组内元素，索引值为 – (length + 1)，其实也是 - 插入点索引值 -1，只不过在此插入点索引值为length;
[4] 搜索值不是数组元素，且小于数组内元素，索引值为 – 1( - 0 -1=-1)。

2） binarySearch(Object[], int fromIndex, int toIndex, Object key)
a：要搜索的数组
fromIndex：指定范围的开始处索引（包含）
toIndex：指定范围的结束处索引（不包含）
key：要搜索的值
如果要搜索的元素key在指定的范围内，则返回搜索值的索引；否则返回-1或“-”（插入点）。
[1] 该搜索键在范围内，但不是数组元素，由0开始计数，得“ - 插入点索引值 -1”；
[2] 该搜索键在范围内，且是数组元素，由0开始计数，得搜索值的索引值；
[3] 该搜索键不在范围内，且小于范围（数组）内元素，返回–fromIndex - 1；
[4] 该搜索键不在范围内，且大于范围（数组）内元素，返回 –toIndex - 1。

如上，理解后，实质上就是用dp记录一个最长的链，不断的更新这个链，只有超过链的长度，len才会更新，不然只是修改对应的dp值

1
2
3
4
5
6
7
8
9
10
11
12
13
   public int lengthOfLIS(int[] nums) {
    int[] dp = new int[nums.length];
    int len = 0;
    for(int x : nums) {
        int i = Arrays.binarySearch(dp, 0, len, x);
        if(i < 0) i = -(i + 1);
        dp[i] = x;
        if(i == len) len++;
    }
    return len;
}

[leetcode 301] Remove Invalid Parentheses

这道题不好做，我是直接参考了discuss上第一的解答，其解决办法是先判断右括号多的情况，消去右括号的原则是要么是第一个要么前面一个不是右括号，这样就不会出现重复；至于左括号呢，将字符串反转就可以重复利用原先的代码了，详细见Easy, Short, Concise and Fast Java DFS 3 ms solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public List<String> removeInvalidParentheses(String s) {
    List<String> ans = new ArrayList<>();
    remove(s, ans, 0, 0, new char[]{'(', ')'});
    return ans;
}
public void remove(String s, List<String> ans, int last_i, int last_j,  char[] par) {
    for (int stack = 0, i = last_i; i < s.length(); ++i) {
        if (s.charAt(i) == par[0]) stack++;
        if (s.charAt(i) == par[1]) stack--;
        if (stack >= 0) continue;
        for (int j = last_j; j <= i; ++j)
            if (s.charAt(j) == par[1] && (j == last_j || s.charAt(j - 1) != par[1]))
                remove(s.substring(0, j) + s.substring(j + 1, s.length()), ans, i, j, par);
        return;
    }
    String reversed = new StringBuilder(s).reverse().toString();
    if (par[0] == '(') // finished left to right
        remove(reversed, ans, 0, 0, new char[]{')', '('});
    else // finished right to left
        ans.add(reversed);
}

如果觉得有帮助，给我打赏吧！