如何解hard算法题？

前言

上一篇文章写bitCount源码解析，对困难题有一些抽象的理解。
困难题就是一个个简单的知识点组成，加上其内在的逻辑联系。所以一个困难题，应该是先观其规律，再进行逻辑转换问题，再拆解小问题，用积累的知识点解决。
当然，如果没有积累到/思考角度不对，就看题解，多调研，别浪费时间！

一、案例

二、困难题拆解

1、自己的思路

	// target：从两个数组选出两组数据，合并倒序，就得到一个最大组合值。
    // 转换成有规律的问题。
    // 问题
    // 两数组肯定尽量单调（最大的那个单调），但是取出的单调栈合并长度并不一定为k
    // 如果两者合并长度大于等于k，倒排之后（依次选择），取前k个即可。
    // 如果不够k怎么办？
1
2
3
4
5
6

很明显，我的角度错了，但也有可取之处，比如单调栈。
而我角度错了的原因，就是没有将问题从模拟问题转化为有规律的问题，这样才能用代码实现！

2、官方的思路

将k分解为k = x + y，不断模拟两个数值数组的最大拼接，记录最大的那一个。
现在已经将问题规律化了，然后拆解小问题，就涉及到小知识点了
1.带remain的单调栈来取数值数数组指定长度最大子序列。
2.O(N)合并两个数值数组，使其该数值数组最大值。
3.两数值数组比较大小的处理方式。

3、源码

Java

class Solution {
    // target：从两个数组选出两组数据，合并倒序，就得到一个最大组合值。
    // 转换成有规律的问题。
    // 问题
    // 两数组肯定尽量单调（最大的那个单调），但是取出的单调栈合并长度并不一定为k
    // 如果两者合并长度大于等于k，倒排之后（依次选择），取前k个即可。
    // 如果不够k怎么办？

    // 调研思路
    // 将k分成 k = x + y，不断寻找x和y，然后拼接，比较，记录最大值。 
    public int[] maxNumber(int[] nums1, int[] nums2, int k) {
        int m = nums1.length,n = nums2.length;

        int start = Math.max(0,k - n);
        int end = Math.min(k,m);
        int[] maxRs = new int[k];
        // 强行分解k = x + y，进行遍历记录最大值。
        // hard-mark：问题转换(规律非模拟问题)+问题拆解(多个小知识点)+多个小问题的逻辑联系。
        for(int i = start;i <= end;i++){
            int[] seq1 = getSeq(nums1,i);
            int[] seq2 = getSeq(nums2,k - i);

            int[] curRs = merge(seq1,seq2);

            if(compare(maxRs,0,curRs,0) < 0) System.arraycopy(curRs,0,maxRs,0,k);
        }
        return maxRs;
    }
    // 知识点1：O(N)合并两个数值数组，使其该数值数组最大值。
    public int[] merge(int[] nums1,int[] nums2){
        int m = nums1.length,n = nums2.length;
        if(m == 0) return nums2;
        if(n == 0) return nums1;

        int i = 0,j = 0;
        int[] rs = new int[m + n];

        for(int k = 0;k < m + n;k++){
            if(compare(nums1,i,nums2,j) > 0) rs[k] = nums1[i++];
            else rs[k] = nums2[j++];
        }
        return rs;
    }
    // 知识点2：两数值数组比较大小，尽量返回int，而不是boolean
    public int compare(int[] nums1,int i,int[] nums2,int j){
        int m = nums1.length,n = nums2.length;

        while(i < m && j < n){
            int gap = nums1[i] - nums2[j];
            if(gap != 0) return gap;

            ++i;
            ++j;
        }
        return (m - i) - (n - j);
    }
    // 知识点3：单调减栈 配合 remain，可以做到求指定长度的最大子序列。
    public int[] getSeq(int[] nums,int k){
        int[] stack = new int[k];
        int top = 0,remain = nums.length - k;

        for(int cur : nums){
            while(top > 0 && stack[top - 1] < cur && remain > 0){
                top--;
                remain--;// 不需要的上限
            }
            if(top < k){
                stack[top++] = cur;
            }else remain--;
        }
        return stack;
    }
}
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

golang

func maxNumber(nums1 []int, nums2 []int, k int) []int {
    m,n := len(nums1),len(nums2)
    start,end := max(0,k - n),min(k,m)
    maxRs := make([]int,k)
    // k = x + y,取子序列，再合并，最后比较大小，并记录。
    for i := start;i <= end;i++ {
        seq1 := getSeq(nums1,i)
        seq2 := getSeq(nums2,k - i)

        curRs := merge(seq1,seq2)

        if compare(curRs,0,maxRs,0) > 0 {
            copy(maxRs,curRs)
        }
    }
    return maxRs
}
// 知识点1：O(N)合并两个数值数组，使其该数值数组最大值。
func merge(nums1 []int,nums2 []int) []int {
    m,n := len(nums1),len(nums2)
    if m == 0 {
        return nums2
    }
    if n == 0 {
        return nums1
    }
    i,j := 0,0
    rs := make([]int,m + n)
    for k := 0;k < m + n;k++ {
        if compare(nums1,i,nums2,j) > 0 {
            rs[k] = nums1[i]
            i++
        }else {
            rs[k] = nums2[j]
            j++
        }
    }
    return rs
}
// 知识点2：两数值数组比较大小，尽量返回int，而不是boolean
func compare(nums1 []int,i int,nums2 []int,j int) int {
    m,n := len(nums1),len(nums2)
    for ; i < m && j < n; {
        gap := nums1[i] - nums2[j]
        if gap != 0 {
            return gap
        }
        i++
        j++
    }
    return (m - i) - (n - j)
}
// 知识点3：单调减栈 配合 remain，可以做到求指定长度的最大子序列。
func getSeq(nums []int,k int) []int {
    stack := make([]int,k)
    top := 0
    remain := len(nums) - k

    for _,cur := range nums {
        for ; top > 0 && stack[top - 1] < cur && remain > 0; {
            top--;
            remain--;
        }
        if top < k {
            stack[top] = cur;
            top++
        }else {
            remain--
        }
    }
    return stack
}
// 取大值
func max(i int,j int) int {
    if i > j {
        return i
    }
    return j
}
// 取小值
func min(i int,j int) int {
    if i < j {
        return i
    }
    return j
}
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

总结

1）一个困难题，应该是先观其规律，再进行逻辑转换问题，再拆解小问题，用积累的知识点解决。
2）如果没有积累到/思考角度不对，就看题解，多调研，别浪费时间！
3）多解决困难题，对提升解决问题能力有帮助，但是这是长期提升，而短期需要找工作则边界收益不大，性价比低。

参考文献

[1] LeetCode 321.拼接最大数
[2] LeetCode 321.拼接最大数-官方题解
[3] go 数组copy用法
[4] go foreach用法