leetCode进阶算法题+解析（三十九）

打广告：java技术交流群：130031711，欢迎各位萌新大佬踊跃加入。就在今天，我的群终于迎来了第二个人！！哈哈，开心~我决定今天多刷两道题庆祝一下^ - ^。

扁平化嵌套列表迭代器

题目：给你一个嵌套的整型列表。请你设计一个迭代器，使其能够遍历这个整型列表中的所有整数。列表中的每一项或者为一个整数，或者是另一个列表。其中列表的元素也可能是整数或是其他列表。

示例 1:
输入: [[1,1],2,[1,1]]
输出: [1,1,2,1,1]
解释: 通过重复调用 next 直到 hasNext 返回 false，next 返回的元素的顺序应该是: [1,1,2,1,1]。
示例 2:
输入: [1,[4,[6]]]
输出: [1,4,6]
解释: 通过重复调用 next 直到 hasNext 返回 false，next 返回的元素的顺序应该是: [1,4,6]。

思路：这个题，怎么说呢，我目前的想法是遍历，都取出来，然后next和hasNext就用指针好了。我去实现下试试。
只能这么说，蜜汁实现，我到现在都不知道考点在哪里！

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * public interface NestedInteger {
 *
 *     // @return true if this NestedInteger holds a single integer, rather than a nested list.
 *     public boolean isInteger();
 *
 *     // @return the single integer that this NestedInteger holds, if it holds a single integer
 *     // Return null if this NestedInteger holds a nested list
 *     public Integer getInteger();
 *
 *     // @return the nested list that this NestedInteger holds, if it holds a nested list
 *     // Return null if this NestedInteger holds a single integer
 *     public List<NestedInteger> getList();
 * }
 */
public class NestedIterator implements Iterator<Integer> {
    List<Integer> list;
    int idx ;
    public NestedIterator(List<NestedInteger> nestedList) {
        list = new ArrayList<Integer>();
        dfs(nestedList);    
    }

    @Override
    public Integer next() {
        return list.get(idx++);
    }

    @Override
    public boolean hasNext() {
        return idx<list.size();
    }
    public void dfs(List<NestedInteger> nestedList){
        for(NestedInteger n : nestedList){
            if(n.isInteger()) {
                list.add(n.getInteger());
            }else{
                dfs(n.getList());
            }
        }
    }
}

/**
 * Your NestedIterator object will be instantiated and called as such:
 * NestedIterator i = new NestedIterator(nestedList);
 * while (i.hasNext()) v[f()] = i.next();
 */

反正我是先遍历，然后正常判断下一个元素的。这个题莫名其妙性能还挺好，所以这个题直接过了，下一题吧。

整数拆分

题目：给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。

示例 1:
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。
示例 2:
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
说明: 你可以假设 n 不小于 2 且不大于 58。

思路：这个题怎么说呢，乍一看很简单，再一看有点复杂，最后看其实也就那样。我刚刚仔细想了想，当数字为1，2乘积都是1，数字为3乘积最大是2（1乘2），数字为4最大乘积还是4（2乘2），只有当这个数大于4以后，乘积才会大于和。比如5可以分为2,3。变成6了，再比如6可以拆分为3,3,变成9.然后7可以拆成3,4最大积12.这里注意，如果是8的话，可以拆成3,3，2。最大积是18.看出规律没？那就是尽可能的往小拆。但是这个数不能小于2，因为1的乘积是不大的。而且这个数不能大于4.因为如果拆成5的话，完全可以再拆一下2,3这样6比5大，我感觉规律就是这样，我去用代码试试。
好了，做出来了，我直接贴代码：

class Solution {
    public int integerBreak(int n) {
        if(n<4) return n-1;
        if(n == 4) return 4;
        int sum = 3;
        n -= 3;
        while(n>=5){
            sum *= 3;
            n -= 3;
        }
        sum *= n;
        return sum;
    }
}

感觉这个题真的蛮简单的，就是一个思路的问题，代码没啥难度。然后大于等于5开始就能拆分成2,3了。也就是如果大于等于5肯定能拆出3。。。因为3的性价比大于2，所以能拆3拆3.。最后不行了才是2或者4。反正代码逻辑清楚，自己看吧。我直接下一题了。

前K个高频元素

题目：给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:
输入: nums = [1], k = 1
输出: [1]
说明：
你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。

思路：别说，这个题我还真有思路。就是我记得以前有那个找到数组中出现超过三分之一的元素。然后用的套路。就是计数器++--。然后只要存在这样的元素就会找出来。。咳咳，虽然这里不是很适合这么用，但是我说出来就是为了复习下曾经的知识。然后说这道题，没有空间复杂度但是有时间复杂度。而且是NlogN,我记得归并快排都是（附上各种算法的性能对比图）。但是这里感觉这两个都不适用。我个人暂时的想法就是map计数，然后取计数最大的前k个。至于这个计数可以用桶排来取值。感觉这个是最简单的实现了，我去试试吧。

排序算法性能对比
通过了，不过性能不好，我直接贴代码：

class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        //map计数
        HashMap<Integer,Integer> map = new HashMap();
        for(int num : nums){
            if (map.containsKey(num)) {
            map.put(num, map.get(num) + 1);
            } else {
                map.put(num, 1);
            }
        }
        //桶排
        List<Integer>[] list = new List[nums.length+1];
        for(Integer key : map.keySet()){
            int n = map.get(key);
            if(list[n]==null){
                list[n] = new ArrayList<Integer>();
            }
            list[n].add(key);
        }
        List<Integer> res = new ArrayList<Integer>();
        for(int i = list.length-1;i>=0;i--){
            if(list[i]!=null){
                for(int j : list[i]){
                    res.add(j);
                    if(res.size()==k) return res;
                }
            }
        }
        return res;
    }
}

我感觉性能不好的原因可能很多，比如map不断contains，比如list数组，比如最后的遍历，，但是！优化是懒得优化了，也就这样吧。我直接去看看性能排行第一的代码了。

class Solution {
    //前 K 个高频元素
     public List<Integer> topKFrequent(int[] nums, int k) {
         List<Integer> list=new ArrayList();
         Arrays.sort(nums);
         int distinctLen=1;
         for(int i=1;i<nums.length;i++){
             if(nums[i]!=nums[i-1]){
                 distinctLen++;
             }
         }
         int counts[]=new int[distinctLen];
         int order[]=new int[distinctLen];
         int index=0;
         int count=1;
         for(int i=1;i<nums.length;i++){
             if(nums[i]==nums[i-1]){
                 count++;
             }else{
                 counts[index]=count;
                 order[index]=count;
                 nums[index]=nums[i-1];
                 index++;
                 count=1;
             }
         }
         nums[index]=nums[nums.length-1];
         counts[index]=count;
         order[index]=count;
         Arrays.sort(order);
         int kth=order[distinctLen-k];
         for(int i=0;i<=index;i++){
             if(counts[i]>=kth){
                 list.add(nums[i]);
             }
         }
         return list;
     }
}

讲真，这个性能为什么这么好？各种sort。。。有点不平衡了啊。。。反正我只能这么说，看是可以看懂，但是性能为什么好我有点不懂。。这个不是最直觉的解法了么？大体思路是首先判断右多少种数。然后创建种类大小的数组两个，都用来计数。并与此同时把nums数组去重。最后其中一个按大小排序。取排名前k的计数个数（比如大于2次的就是前k个频率出现的）。然后再用按顺序计数的和前k的个数比较，大于等于的说明是频率前k里的，添加到结果集。
怎么说呢，我觉得这个真的是一种很直觉的做法，可能是我矫情了，并没有让我眼前一亮的感觉，反而觉得没啥计数含量。另外我觉得这个绝对不是NlogN的时间复杂度。
算了，谁让人家的性能好呢~就这样吧。反正都可以作为思路参考嘛。
今天的笔记就记到这里，如果稍微帮到你了记得点个喜欢点个关注，顺便打个广告，java技术交流群，群号130031711，欢迎各位萌新大佬踊跃加入！