如何解hard算法题？-创新互联

如何解困难题？

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

成都创新互联成立与2013年，是专业互联网技术服务公司，拥有项目网站设计、网站制作网站策划，项目实施与项目整合能力。我们以让每一个梦想脱颖而出为使命，1280元西夏做网站,已为上家服务,为西夏各地企业和个人服务,联系电话:18982081108前言

上一篇文章写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，而不是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;
    }
}

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

参考文献

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

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

网站栏目：如何解hard算法题？-创新互联
本文URL：http://dzwzjz.com/article/hdhoo.html