打卡刷题，不想再过Diwali

楼主现在十八线小公司，阿三占90%+，起早贪黑快两年，最后成全了三哥。 去年中途换了远程经理，之前的同组人步步高升，我发信给新经理要加薪居然无视，现在被发配帮其他组打杂，快要被该组的三姐经理榨干。虽然已是中年又不想就此养老，在此立flag，11月份之前要跳去一个不过Diwali，薪水x2的公司。遂开始刷题中。

补充内容 (2018-5-3 14:04):
0502
Longest Increasing Subsequence - 两种DP方法, 一种是dp[i]当前位置i的最长增加子串。第二种是dp[i]累计存放递增元素，每次用二分查找找出不小于当前元素的位置，存在则替换，不存在则添加。

补充内容 (2018-5-4 04:44):
0503
3. Longest Substring Without Repeating Characters 这题楼主自己想了两种方法都不得其解。看了clean code handbook上的最简方法，判断当前字符在charmap中记的index>=最左边字符index..

补充内容 (2018-5-9 07:12):
0508
388. Longest Absolute File Path 这题corner cases: 1. should omit the first /  2. Use dummy elem in stack, otherwise deal with empty 3. spaces are treated as normal string

tony.chenjy 发表于 2018-5-4 08:27
可能我对阿三的印象还停留昏天暗地那种落后艰苦的沙俄时代，不过还是祝福楼主心想事成！

没错 我觉得硅谷已经是昏天暗地的班加罗尔了

683. K Empty Slots
1. 容易被数组index弄迷糊
2.

   

1. public int kEmptySlots(int[] flowers, int k) {
   
2.     int days[] = new int[flowers.length+1];
   
3. 
   
4.     for(int i=0; i<flowers.length; i++){
   
5.         days[flowers[i]] = i+1; // [3,9,2,8,1,6,10,5,4,7] -> [0, 5, 3, 1, 9, 8, 6, 10, 4, 2, 7]
   
6.     }
   
7. 
   
8.     int res = Integer.MAX_VALUE;
   
9.     // 用两个指针，边界比较清楚
   
10.     for(int p1 = 1, p2 = k+2; p2<days.length; p1++, p2++){
    
11.         // check from between p1 and p2, to see if any violations, if so, break
    
12.         int p=p1+1;
    
13.         for(; p<p2; p++){
    
14.             if(days[p] <= days[p1] || days[p] <= days[p2])
    
15.                 break;
    
16.         }
    
17.         if(p==p2) // 如果k=0， 那么p==p2, 如果k>0, 那么p1,p2之间有一个数，并且通过上面的check，那么p==p2。这个条件其实包含了这两种情况。
    
18.             res = Math.min(res, Math.max(days[p1], days[p2]));   // 可能会有多个满足以上check的，比如[1,9,8] (第8天，这里day=max(1, 8)) [6,10,4] (第6天) 都满足[0, 5, 3, 1, 9, 8, 6, 10, 4, 2, 7] k=1的case, 所以要取最小值
    
19.     }
    
20.     return res==Integer.MAX_VALUE?-1:res;
    
21. }

复制代码

681. Next Closest Time
思路是把时间例如23:59转换成23*60+58=1438min, 然后依次(1438+1)%1440, (1439+1)%1440, (1440+1)%1440, ... 循环的同时再把这些分钟数转回时间，判断每个时间的每个数字都包含在String time中，如果是则立即返回。
这里注意，如果从23:59（1439）开始循环，不应该在1440就结束，而是i%1440，然后循环会重新从0开始，deadloop，但是保证会返回。
Test Case:
23:59 边界
00:00 边界
0:00 合法
24:00不合法

1. public String nextClosestTime(String time) {               
   
2.     // convert time to # of minutes
   
3.     String hour = time.split(":")[0];
   
4.     String min = time.split(":")[1];
   
5.     int m = Integer.valueOf(hour)*60 + Integer.valueOf(min);
   
6. 
   
7.     // Get next time in the next minute, until found
   
8.     for(int i=m+1; ; i++){
   
9.         i=i%1440;
   
10.         String h1 = String.valueOf(i/60/10);
    
11.         String h2 = String.valueOf((i/60)%10);
    
12.         String m1 = String.valueOf((i%60)/10);
    
13.         String m2 = String.valueOf((i%60)%10);
    
14.         //System.out.println(h1+h2+m1+m2);
    
15. 
    
16.         if(time.lastIndexOf(h1)!=-1 && time.lastIndexOf(h2)!=-1 && time.lastIndexOf(m1)!=-1 && time.lastIndexOf(m2)!=-1){
    
17.             return h1+h2+":"+m1+m2;
    
18.         }
    
19.         else
    
20.             continue;
    
21.     }
    
22. }

复制代码

补充内容 (2018-5-11 05:09):
else continue可以去掉

340. Longest Substring with At Most K Distinct Characters
这题要注意两个指针，charmap自增不要搞错或者丢掉，否则分分钟越界、死循环。
int k=5;
System.out.println(k--==5); // true , k--无论作为返回值还是放在表达式里，都是先返回当前值。

还有ASCII字符个数是256（128 basic + extended）

1. class Solution {
   
2.     public int lengthOfLongestSubstringKDistinct(String s, int k) {
   
3.         int charmap[] = new int[256];
   
4. 
   
5.         int distinct = 0;
   
6.         int len = 0, maxlen = 0;
   
7.         int i = 0, j = 0;
   
8. 
   
9.         while (j < s.length()) {
   
10.             if (charmap[s.charAt(j)]++ == 0)
    
11.                 distinct++;
    
12. 
    
13.             while (distinct > k) {
    
14.                 if (charmap[s.charAt(i++)]-- == 1)
    
15.                     distinct--;
    
16.             }
    
17.             len = j++ - i + 1;
    
18.             maxlen = Math.max(maxlen, len);
    
19.         }
    
20.         return maxlen;
    
21.     }
    
22. }

复制代码

482. License Key Formatting
需要处理返回值：
1. 为空的情况
2. 开头多加了一个'-'的情况

1. class Solution {
   
2.     public String licenseKeyFormatting(String S, int K) {
   
3.         StringBuilder sb = new StringBuilder();
   
4.         int k = 0;
   
5. 
   
6.         for (int i = S.length() - 1; i >= 0; i--) {
   
7.             char c = S.charAt(i);
   
8.             if (c != '-') {
   
9.                 sb.insert(0, c);
   
10.                 if (++k % K == 0)
    
11.                     sb.insert(0, '-');
    
12.             }
    
13.         }
    
14.         String res = sb.toString().toUpperCase();
    
15.         return res.indexOf("-") == 0 ? res.substring(1) : res; // 避免用res[0]，res为空时会导致越界；处理了上述两种情况
    
16.     }
    
17. }

复制代码

346. Moving Average from Data Stream
简单题主要复习一下Deque和Queue用法。
1. offer() 和 add() 区别： offer入队失败会返回false，add可能直接就exception了
2. 用Queue更简单，不需要offerFirst()和pollLast()
3. 注意数字个数少于moving average windows length的处理
4. 注意队头出列（减去），队尾插入新数字（加上）

楼主求个交流方式，互相鼓励下。

378543248 发表于 2018-5-2 06:23
楼主求个交流方式，互相鼓励下。

加我wechat - hanchen2011
互相督促。。

hername 发表于 2018-5-1 12:15
薪水+++可能，不过diwali不可能

去国厂分部 不信还过Diwali

薪水+++可能，不过diwali不可能

非专业小白可以问一个比较蠢的问题嘛… 大家说的刷题都是什么刷什么题?… 打扰了!

几十卓卓 发表于 2018-5-1 23:51
非专业小白可以问一个比较蠢的问题嘛… 大家说的刷题都是什么刷什么题?… 打扰了!

leetcode / lintcode / careercup (cc189) etc

LZ加油！

hankok 发表于 2018-5-1 12:20
去国厂分部 不信还过Diwali

求问什么叫diwali

sirius27 发表于 2018-5-2 23:43
求问什么叫diwali

印度的一个节日咯。相当于新年好像。