打广告：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，欢迎各位萌新大佬踊跃加入！
网友评论