341
如果用栈应该就是这样解决，当然也可以直接用个list顺序递归往里面加就可以了
/** * // 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> { LinkedList<NestedInteger> stack; public NestedIterator(List<NestedInteger> nestedList) { this.stack = new LinkedList<>(); fill(nestedList); } private void fill(List<NestedInteger> nestedList ){ for (int i = nestedList.size()-1; i >= 0 ; i--) { if (nestedList.get(i).isInteger()){ stack.push(nestedList.get(i)); }else { fill(nestedList.get(i).getList()); } } } @Override public Integer next() { return stack.pop().getInteger(); } @Override public boolean hasNext() { return !stack.isEmpty(); } } /** * Your NestedIterator object will be instantiated and called as such: * NestedIterator i = new NestedIterator(nestedList); * while (i.hasNext()) v[f()] = i.next(); */
385 性能很low。。。
/** * // This is the interface that allows for creating nested lists. * // You should not implement it, or speculate about its implementation * public interface NestedInteger { * // Constructor initializes an empty nested list. * public NestedInteger(); * * // Constructor initializes a single integer. * public NestedInteger(int value); * * // @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(); * * // Set this NestedInteger to hold a single integer. * public void setInteger(int value); * * // Set this NestedInteger to hold a nested list and adds a nested integer to it. * public void add(NestedInteger ni); * * // @return the nested list that this NestedInteger holds, if it holds a nested list * // Return empty list if this NestedInteger holds a single integer * public List<NestedInteger> getList(); * } */ class Solution { public NestedInteger deserialize(String s) { LinkedList<NestedInteger> stack = new LinkedList<>(); NestedInteger node = new NestedInteger(); stack.push(node); String sb = ""; for (int i = 0; i < s.length(); i++) { char tp = s.charAt(i); if (tp == '['){ NestedInteger peek = stack.peek(); NestedInteger nets = new NestedInteger(); peek.add(nets); stack.push(nets); }else if (tp == ']'){ NestedInteger pop = stack.pop(); if (sb.length() == 0){ continue; } NestedInteger nest = new NestedInteger(); pop.add(nest); nest.setInteger(Integer.valueOf(sb.toString())); sb=""; }else if (tp == ','){ NestedInteger pop = stack.peek(); if (sb.length() == 0){ continue; } NestedInteger nest = new NestedInteger(); pop.add(nest); nest.setInteger(Integer.valueOf(sb)); sb=""; }else { sb =sb +s.charAt(i); } } if (sb.length() != 0){ return new NestedInteger(Integer.valueOf(sb)); } NestedInteger pop = stack.pop().getList().get(0); return pop; } }
394 一位大佬的思路，应该就是用一个字符串变量表示每次遇到 “ ] ”时前面的字符串 然后用栈顶元素加上这个字符串应该有的倍数
public static String decodeString(String s) { int k = 0; LinkedList<String> stack = new LinkedList<>(); LinkedList<Integer> stackCount = new LinkedList<>(); String str = ""; for (int i = 0; i < s.length(); i++) { char c = s.charAt(i); if (c == '['){ stackCount.push(k); stack.push(str); k = 0;str= ""; }else if (c == ']'){ Integer pop = stackCount.pop(); String pop1 = stack.pop(); while (pop > 0){ pop1 = pop1 + str; pop--; } str = pop1; }else if (c >= 48 && c <= 57){ k = k*10+(c-48); }else { str+=c; } } return str; }
402 标签是栈但我想的是从左开始每次找到可选择里面最小的那个 然后直到结束，例如案例中1432219中移除3个 ，那么第一个数字明显只能在1432中选择 如果再选择后面的那么将三个3个移除名额即使都用了也是不够的。
前面4个数字1最小所以选1，此时没有使用移除名额
在4322中选择最小的数2(第一个2)，那么需要移除43，此时移除名额只剩一个
在219中选择最小的数1，那么需要移除2，此时无名额，字符串还剩一个9
答案为1+2+1+9=1219
代码为如下但是因为这样的话复杂度偏高，只打败了10%的人。。。
private static String remove(String num,int k){ if (num.length() == k)return "0"; int tp = k; String res = ""; for (int i = 0; i < num.length() && res.length() < num.length()-tp; i++) { Character s = null; int p = 0; for (int j = 0; j < k + 1 && (i + j)< num.length(); j++) { char c1 = num.charAt(i + j); if (s == null || c1 < s){ s = c1; p = j; } } i+=p; res+= s; k-=p; } while (res.length() != 1 && res.startsWith("0")){ res = res.substring(1); } return res; }
456 这题用暴力模式解起来倒是很方便，不过这样的话时间复杂度大约应该是O(n^2)
public static boolean find132pattern(int[] nums) { if (nums.length < 3) return false; int min = nums[0]; for (int i = 1; i < nums.length; i++) { if (nums[i] <= min){ min = nums[i]; }else { for (int j = i+1; j < nums.length; j++) { if (nums[j] < nums[i] && nums[j] > min ){ return true; } } } } return false; }
看到个大佬的用栈的解法没太看懂 先记录下来吧。
class Solution { public: bool find132pattern(vector<int>& nums) { int n=nums.size(); int third=INT_MIN; stack<int> sta; for(int i=n-1;i>=0;i--){ if(nums[i]<third) return true; while(!sta.empty() && nums[i]>sta.top()){ third=sta.top(); sta.pop(); } sta.push(nums[i]); } return false; } };
735
public static int[] asteroidCollision(int[] asteroids) { LinkedList<Integer> list = new LinkedList<>(); A:for (int i = 0; i < asteroids.length; i++) { if (i == 0) { list.push(asteroids[i]); continue ; } int k = asteroids[i]; while (!list.isEmpty() && list.peek() > 0 && k < 0 ){ if (list.peek() > -k){ continue A; } else if (list.peek() == -k){ list.pop(); continue A; } else { list.pop(); } } list.push(k); } int[] result = new int[list.size()]; for (int i = 0; i < result.length; i++) { Integer integer = list.removeLast(); result[i]= integer; } return result; }