Jackson Blog
0%

动态规划之最长上升子序列问题

Posted on

139. 单词拆分

难度中等388收藏分享切换为英文关注反馈

给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict*，判定 *s 是否可以被空格拆分为一个或多个在字典中出现的单词。

说明：

  • 拆分时可以重复使用字典中的单词。
  • 你可以假设字典中没有重复的单词。

示例 1：

1
2
3
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。

示例 2：

1
2
3
4
输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
     注意你可以重复使用字典中的单词。

示例 3：

1
2
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//1.dp solution so slow
class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set <String> w=new HashSet(wordDict);
        int len=s.length();
        boolean[] dp= new boolean[len+1];
        dp[0]=true;
        for(int i=1;i<=len;i++){
            for(int j=0;j<i;j++){
                if(dp[j] && w.contains(s.substring(j,i))){
                    dp[i]=true;
                }
            }
        }
        return dp[len];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//2.bfs真香
public class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> wordDictSet=new HashSet(wordDict);
        Queue<Integer> queue = new LinkedList<>();
        int[] visited = new int[s.length()];
        queue.add(0);
        while (!queue.isEmpty()) {
            int start = queue.remove();
            if (visited[start] == 0) {
                for (int end = start + 1; end <= s.length(); end++) {
                    if (wordDictSet.contains(s.substring(start, end))) {
                        queue.add(end);
                        if (end == s.length()) {
                            return true;
                        }
                    }
                }
                visited[start] = 1;
            }
        }
        return false;
    }
}

300. 最长上升子序列

难度中等639收藏分享切换为英文关注反馈

给定一个无序的整数数组，找到其中最长上升子序列的长度。

示例:

1
2
3
输入: [10,9,2,5,3,7,101,18]
输出: 4 
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。

说明:

  • 可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
  • 你算法的时间复杂度应该为 O(n2) 。

进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//dp真慢
class Solution {
    public int lengthOfLIS(int[] nums) {
        int len=nums.length;
        if(len<=0)
            return 0;
        int[] dp=new int[len];
        dp[0]=1; 
        int maxans=1;
        for(int i=1;i<len;i++){
            int maxval=0; 
            for(int j=0;j<i;j++){
                if(nums[i]>nums[j])
                    maxval=Math.max(maxval,dp[j]);
            dp[i]=maxval+1;
            maxans=Math.max(maxans,dp[i]);        
            }
        }
        return maxans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {//binary search加dp真香
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        int len = 0;
        for (int num : nums) {
            int i = Arrays.binarySearch(dp, 0, len, num);
            if (i < 0) {
                i = -(i + 1);
            }
            dp[i] = num;
            if (i == len) {
                len++;
            }
        }
        return len;
    }
}