最近公司在搞敏捷开发，手里三四个项目在同时开发调试和设计。真的是一星期给我一个小项目，再加上最近在看面试题，所以算法也落下好一段时间了。今天刷几道题换个心情吧。。
迷你语法分析器
题目：给定一个用字符串表示的整数的嵌套列表，实现一个解析它的语法分析器。
列表中的每个元素只可能是整数或整数嵌套列表
提示：你可以假定这些字符串都是格式良好的：
字符串非空
字符串不包含空格
字符串只包含数字0-9, [, - ,, ]
示例 1：
给定 s = "324",
你应该返回一个 NestedInteger 对象，其中只包含整数值 324。
示例 2：
给定 s = "[123,[456,[789]]]",
返回一个 NestedInteger 对象包含一个有两个元素的嵌套列表：
- 一个 integer 包含值 123
- 一个包含两个元素的嵌套列表：
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.。反正其实是有规律的，但是这个规律真的是晦涩。。而且怎么用代码实现还没想到。我去简单的写写代码。
这个题怎么说呢，本来没有那么难，但是我越做越麻烦，最后开始灵机一动。先附上我本来的代码：
原始代吗
这里要说一下，上面的代码是错误的，一些细节没处理好。但是也就是上面的代码让我有了新的思路。我之前是想用两端逼近的方法，获得最终的那个数，但是处理起来细节太多，我来回来去的debug调试也没调试好（上面代码正着是对的，从后往前是反着的）我觉得是可以调试好，但是在调试过程中有了新启发。其实每轮获取第一个数的值，直到只剩下最后一个数就行。这一个数也就是最后一个数。于是新的代码更加简单易懂：
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.当是奇数的时候自动向下取整，也是完整的符合了要求。
我感觉这个代码挺好理解的，就是性能让我比较费解，没超时倒是，但是才超过百分之三十的人，我去看着优化下细节。
我就简单的把乘除换成了位运算，然后超过百分之九十九了~~哈哈，这个题就这么过了
超过百分之九十九
这篇笔记拖拖拉拉写了快半个月，最近工作比较忙，而且也有别的事情，所以刷题也没那么热衷了，反正就这样吧，以后会尽力多抽出时间的，如果稍微帮到你了也记得点个喜欢点个关注，也祝大家生活健健康康，工作顺顺利利！java技术交流群130031711欢迎各位萌新大佬踊跃加入！
网友评论