最近公司在搞敏捷开发，手里三四个项目在同时开发调试和设计。真的是一星期给我一个小项目，再加上最近在看面试题，所以算法也落下好一段时间了。今天刷几道题换个心情吧。。

迷你语法分析器

题目：给定一个用字符串表示的整数的嵌套列表，实现一个解析它的语法分析器。

列表中的每个元素只可能是整数或整数嵌套列表

提示：你可以假定这些字符串都是格式良好的：

字符串非空

字符串不包含空格

字符串只包含数字0-9, [, - ,, ]

示例 1：
给定 s = "324",
你应该返回一个 NestedInteger 对象，其中只包含整数值 324。
示例 2：
给定 s = "[123,[456,[789]]]",
返回一个 NestedInteger 对象包含一个有两个元素的嵌套列表：

1. 一个 integer 包含值 123
2. 一个包含两个元素的嵌套列表：
   i. 一个 integer 包含值 456
   ii. 一个包含一个元素的嵌套列表
   a. 一个 integer 包含值 789

思路：这个题怎么说呢。首先说括号问题。我的想法是有开始必然有结束。我打算是左括号记做1，右括号记做-1。当第一个满足让括号和为0的就是这个开始括号的结尾括号。这样可以实现把每一个对象都拆分出来。至于括号里的括号就要继续拆分。直到所有的都变成数组了。初步估计是个递归。我去代码实现试试
好了，和预想的有点出入，但是大体还是对的，一个递归解决问题。只不过这个括号是从最内层开始解的。遇到"["就进一层的递归，而遇到“]”则退出一层递归。因为前后括号肯定成对的，所以最终返回的也不会出错。
重点是各种奇葩测试案例，然后面向测试案例变成，不断修修改改，这个题不难，但是细节点我觉得挺多的，直接贴代码：

/**
 * // 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 null if this NestedInteger holds a single integer
 *     public List<NestedInteger> getList();
 * }
 */
class Solution {
    int idx = -1;
    public NestedInteger deserialize(String s) {
        NestedInteger res = new NestedInteger();        
        //遍历到结束
        while(++idx < s.length()){
            char t = s.charAt(idx);
            //如果是数字则获取这数字的值
            if(t == '-' || Character.isDigit(t)){
                int num = 0;
                int sign = 1;
                while(idx<s.length()&&(t == '-' || Character.isDigit(t))){
                    if(t=='-') {
                        sign = -1;
                    }else{
                        num = num*10+(t-'0');
                    }
                    if(++idx<s.length()) t = s.charAt(idx);
                }
                num = num*sign;
                NestedInteger n1 = new NestedInteger(num);
                //解析完毕返回
                if(idx == s.length()) return n1;
                res.add(n1);
                idx--;
            }else if(t == '['){
                //!!这句是专门为了“[]”这个测试案例
                if(idx == 0) return deserialize(s);
                res.add(deserialize(s));
            }else if(t == ','){
                continue;
            }else{
                break;
            }            
        }
        return res;
    }
}

就分几种情况，主要是拆分数字。遇到左括号进递归，遇到右括号出递归。遇到逗号正常跳过也就没了。
剩下中间有一句代码是第一个是左括号直接返回子结果。别的没东西了。难是不难，思路清晰就行了。下一题了。

字典序排数

题目：给定一个整数 n, 返回从 1 到 n 的字典顺序。例如，给定 n =1 3，返回 [1,10,11,12,13,2,3,4,5,6,7,8,9] 。请尽可能的优化算法的时间复杂度和空间复杂度。 输入的数据 n 小于等于 5,000,000。

思路：讲真，这个题目简洁的让我难受啊。看了两三遍没看懂。后来才明白，1开头的在字典的前面，剩下的同理。我甚至想到了一种排序：基数排序。只不过两者差别还是挺大的。因为这个正好是反过来的，基数排序是从各位开始排。而这个应该是从最高位开始排。至于具体怎么实现嘛，不考虑性能的话我觉得现在就能实现，循环往里加。我去先实现再优化啦。
好了，做完回来了，差不多就是递归到下一个数大于n为止。我直接贴代码：

class Solution {
    List<Integer> list;
    public List<Integer> lexicalOrder(int n) {
        list = new ArrayList<Integer>();
        if(n<1) return list;
        for(int i = 1;i<10;i++){
           dfs(n,i);   
        }
        return list;
    }
    public void dfs(int n,int i){
        if(i>n) return;
        list.add(i);
        i *= 10;
        for(int j = 0;j<10;j++){
            dfs(n,i+j);
        }
    }
}

然后我觉得这个题只要思路明确还是比较简单的，有点类似于穷举？我不知道具体算法叫什么，但是和当念的回溯有点类似。第一个数后面0-9.然后第三个数也是0-9。第四个也是0-9。把每一个可能按照顺序添加到list里就好了。
我这个方法的性能不咋地。我去瞅瞅性能排行第一的代码：

class Solution {

    public List<Integer> lexicalOrder(int n) {
        List<Integer> result = new ArrayList<>(n);
        for(int i = 1 ; i < 10 ; i++){
            if(i > n) break;
            result.add(i);
            dfs(result,n,i * 10);
        }
        return result;
    }

    public void dfs(List<Integer> result,int n ,int temp){
        if(temp > n) return;
        for(int i = 0 ; i < 10 ; i++){
            if(temp > n) break;
            result.add(temp);
            dfs(result, n ,temp * 10);
            temp++;
        }
    }
}

我是感觉思路差不多，具体为啥性能差这么多（我的5ms。人家的1ms）我也不清楚。反正逻辑是能理解了。不多说了。下一题。

消除游戏

题目：给定一个从1 到 n 排序的整数列表。首先，从左到右，从第一个数字开始，每隔一个数字进行删除，直到列表的末尾。第二步，在剩下的数字中，从右到左，从倒数第一个数字开始，每隔一个数字进行删除，直到列表开头。我们不断重复这两步，从左到右和从右到左交替进行，直到只剩下一个数字。返回长度为 n 的列表中，最后剩下的数字。

示例：
输入:
n = 9,
1 2 3 4 5 6 7 8 9
2 4 6 8
2 6
6
输出:
6

思路：这个题怎么说呢，最笨的办法就是一个个删除。我不知道会不会超时，但是大概率会超时，但是说技巧的话，第一次奇数都去掉了。第二次偶数隔一个去一个。别的不说起码目前肯定这个数除非是1.不然肯定是偶数。。但是这个有啥用呢。。我再想想。
刚刚看了很久这个规律。其实我觉得可不可以理解成两边逼近？第一次是1-n，第二次是2-（n是偶数是n，n是奇数是n-1）。第三次是上一次得到的尾数减去2到数字个数是奇数就2+2.数字个数是偶数是2.。反正其实是有规律的，但是这个规律真的是晦涩。。而且怎么用代码实现还没想到。我去简单的写写代码。
这个题怎么说呢，本来没有那么难，但是我越做越麻烦，最后开始灵机一动。先附上我本来的代码：

原始代吗

class Solution {
    public int lastRemaining(int n) {
        int num = n;
        int start = 1;
        int step = 1;
        boolean sign = true;
        while(num>1){
            if(sign){
                start += step;
            }else{
                if(num%2==1){//奇数个数的话第一个不选择
                    start += step;
                }
            }
            num /= 2;
            step *= 2;//步长乘2
            sign = !sign;
        }
        return start;
    }
}

下面这个代码其实就是上面的思路转换过来的。首先这个步长的概念：第一次顺序，所以步长1.第二次已经变成偶数了，所以是2.第三次是偶数的隔一个消除一个，所以是4.。。以此类推是每次乘2.然后总个数是每次消除一半（奇数多消除一个，偶数正好一半）所以是每次除2.当是奇数的时候自动向下取整，也是完整的符合了要求。
我感觉这个代码挺好理解的，就是性能让我比较费解，没超时倒是，但是才超过百分之三十的人，我去看着优化下细节。
我就简单的把乘除换成了位运算，然后超过百分之九十九了~~哈哈，这个题就这么过了

超过百分之九十九