如何解困难题？

• 前言
• 一、案例
• 二、困难题拆解
• • 1、自己的思路
  • 2、官方的思路
  • 3、源码
  • • Java
    • golang
• 总结
• 参考文献

前言

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

一、案例

二、困难题拆解

1、自己的思路

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

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

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，而不是booleanpublic 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;}
}

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,0rs := 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 := 0remain := len(nums) - kfor _,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）多解决困难题，对提升解决问题能力有帮助，但是这是长期提升，而短期需要找工作则边界收益不大，性价比低。

参考文献

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