【贪心 || 动态规划】最长对数链

题目

方法一（推荐）：贪心算法

思路： 贪心算法的代码并不难写，关键是难想，下面介绍，本题如何贪心及为什么可以贪心

1. 就数对中第二个数进行排序 然后遍历排好序数组，判断 是否满足题意
   （满足跟随关系，当且仅当 b < c 时，数对(c, d) 才可以跟在 (a, b) 后面）
2. 满足题意，结果count++， 并且跟新临时变量temp为满足题意的数对第二个元素。

---

为什么可以贪心
按数对第二个元素排序后，可以保证每步都是缓慢增加的 ，若第二个元素较大的排在前面，则一定会有可行结果被丢弃，因此可以贪心

代码

		Arrays.sort(pairs, (a , b) -> a[1] - b[1]);
        int temp = pairs[0][1];
        int ans = 1;
        for(int i=1; i<pairs.length; i++){
            if(pairs[i][0] > temp){
                ans++;
                temp = pairs[i][1];
            }
        }
        return ans;
1
2
3
4
5
6
7
8
9
10

方法二（可能超时 不推荐）：动态规划

动态规划法思想： 将pairs按数对中第一个元素排序，定义一数组 dp[len]，存储第i 个元素具有的最长满足题意数对长度， 每次循环， 遍历前 i 个元素， 找到第j 个数对中第二个数小于第 i 个数对中的第一个数， 更新 dp[i] 为 Math.max(dp[i], dp[j]+1)

 		int len = pairs.length;
        int dp[] = new int[len];
        Arrays.sort(pairs, (a, b) -> (a[0] - b[0]));
        Arrays.fill(dp, 1);
   
        for(int i=0; i<len; i++){
            for(int j=0; j<i; j++){
                if(pairs[i][0] > pairs[j][1]){
                    dp[i] = Math.max(dp[i], dp[j]+1);
                }
            }
        }
        return dp[len - 1];
1
2
3
4
5
6
7
8
9
10
11
12
13

---

变式题

一. 合并区间

思路：

1. 按照数对的第一个元素对二维数组排序
2. 使用List存储需要加入结果的数对
3. 遍历排完序数组，若 intervals[i][0] > list.get(list.size() - 1) ， 则直接将该数对加入结果 List , 否则若 intervals[i][1] > list.get(list.size()-1) ， 则将 List 的最后一个元素更新为intervals[i][1]
4. 最后遍历 List , 将结果转存为 int[ ][ ]

—— 这么说不太直观，请大家直接看下列图解

代码：

   public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> (a[0] - b[0]));
        List<Integer> list = new ArrayList<>();
        list.add(intervals[0][0]);
        list.add(intervals[0][1]);
        for(int i=1; i<intervals.length; i++){
            if(intervals[i][0] > list.get(list.size() - 1)){
                list.add(intervals[i][0]);
                list.add(intervals[i][1]);
            } else{
                if(intervals[i][1] > list.get(list.size()-1)){
                    list.remove(list.size() - 1);
                    list.add(intervals[i][1]);
                }
            }
        }

        int ansLength = list.size()/2;
        int[][] ans = new int[ansLength][2];
        for(int i=0; i<ansLength; i++){
            ans[i][0] = list.get(i*2);
            ans[i][1] = list.get(i*2+1);
        }
        return ans;

    }
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