如何解hard算法题？-创新互联
如何解困难题？
当前名称：如何解hard算法题？-创新互联
文章地址：http://shouzuofang.com/article/hdhoo.html
- 前言
- 一、案例
- 二、困难题拆解
- 1、自己的思路
- 2、官方的思路
- 3、源码
- Java
- golang
- 总结
- 参考文献
上一篇文章写bitCount源码解析，对困难题有一些抽象的理解。
困难题就是一个个简单的知识点组成，加上其内在的逻辑联系。所以一个困难题，应该是先观其规律，再进行逻辑转换问题，再拆解小问题，用积累的知识点解决。
当然，如果没有积累到/思考角度不对，就看题解，多调研，别浪费时间！
// target：从两个数组选出两组数据，合并倒序，就得到一个大组合值。
// 转换成有规律的问题。
// 问题
// 两数组肯定尽量单调（大的那个单调），但是取出的单调栈合并长度并不一定为k
// 如果两者合并长度大于等于k，倒排之后（依次选择），取前k个即可。
// 如果不够k怎么办？很明显，我的角度错了，但也有可取之处，比如单调栈。
而我角度错了的原因，就是没有将问题从模拟问题转化为有规律的问题，这样才能用代码实现！
将k分解为k = x + y，不断模拟两个数值数组的大拼接，记录大的那一个。
现在已经将问题规律化了，然后拆解小问题，就涉及到小知识点了
1.带remain的单调栈来取数值数数组指定长度大子序列。
2.O(N)合并两个数值数组，使其该数值数组大值。
3.两数值数组比较大小的处理方式。
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;
}
}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）多解决困难题，对提升解决问题能力有帮助，但是这是长期提升，而短期需要找工作则边界收益不大，性价比低。
[1] LeetCode 321.拼接大数
[2] LeetCode 321.拼接大数-官方题解
[3] go 数组copy用法
[4] go foreach用法
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
当前名称：如何解hard算法题？-创新互联
文章地址：http://shouzuofang.com/article/hdhoo.html