在职准备换工作，记录刷题

工作一年半，看着地里的大包裹，甚是羡慕。开贴记录刷题换工作

google 399. Evaluate Division

今天刷了787 Cheapest Flights within K stops. 这题以前刷过，并通过了Leetcode的测试；可是最近Leetcode加了新的test cases, 原来的算法无法通过测试。用BFS + dijkstra

今天刷了Google 的904 Fruit Into Baskets

1. class Solution {
   
2.     public int totalFruit(int[] tree) {
   
3.         int len = tree.length;
   
4.         if (len <= 2) return tree.length;
   
5.         int max = 2;
   
6.         int start = 0;
   
7.         int ind1 = 0;
   
8.         int ind2 = 1;
   
9.         while(ind2 < len && tree[ind2] == tree[ind1]) ind2++;
   
10.         if (ind2 >= len - 1) return len;
    
11.         for (int i = ind2 + 1; i <= len; i++) {
    
12.             if (i == len || (tree[i] != tree[ind1] && tree[i] != tree[ind2])) {
    
13.                 if (i - start > max) max = i - start;
    
14.                 start = Math.max(ind1, ind2);
    
15.                 ind1 = start;
    
16.                 ind2 = i;
    
17.             } else if (tree[i] == tree[i - 1]) {
    
18.                 // pass;
    
19.             } else if (tree[i] == tree[ind1]) {
    
20.                 ind1 = i;
    
21.             } else if (tree[i] == tree[ind2]) {
    
22.                 ind2 = i;
    
23.             }
    
24.         }
    
25.         return max;
    
26.     }
    
27. }

复制代码

Google 482. License Key Formatting

1. class Solution {
   
2.     public String licenseKeyFormatting(String S, int K) {
   
3.         int NAlphanumeric = 0;
   
4.         for (char c : S.toCharArray()) {
   
5.             if (c != '-') NAlphanumeric++;
   
6.         }
   
7.         if (NAlphanumeric == 0) return "";
   
8.         int NFirst = NAlphanumeric % K;
   
9.         if (NFirst == 0) NFirst = K;
   
10.         int len = NFirst + (NAlphanumeric - NFirst) / K * (K + 1);
    
11.         char[] chs = new char[len];
    
12.         int i = 0;
    
13.         for (char c : S.toCharArray()) {
    
14.             if (c == '-') continue;
    
15.             char C = c;
    
16.             if ('a' <= c && c <= 'z') C = Character.toUpperCase(c);
    
17.             if ((i - NFirst) % (K + 1) == 0) {
    
18.                 chs[i] = '-';
    
19.                 i++;
    
20.             }
    
21.             chs[i] = C;
    
22.             i++;
    
23.         }
    
24.         return new String(chs);   
    
25.     }
    
26. }

复制代码

刷了上周六Leetcode Contest的四道题目。

google 135, 299, 686

周六的Leetcode contest

注意java细节:
1.  result of `10 ^ 1` is 11.  `^` means bit wise xor. Use `(int) Math.pow(10, 1)` means power.
2. result of `string.split(".") ` is an array of empty strings. The signature of this function is `String.split(regular_expression)`. If we'd like to split a string by ".", we have to escape it by `string.split("\\.")`.
3. bound of integer is [-2^31, 2^31-1).

307 Range Sum Query - Mutable
自己想出来了一种 binary encoding 的算法

1. class NumArray {
   
2.     List<int[]> list;
   
3. 
   
4.     public NumArray(int[] nums) {
   
5.         list = new ArrayList<>();
   
6.         int[] arr = nums;
   
7.         while (true) {
   
8.             list.add(arr);
   
9.             if (arr.length <= 1) break;
   
10.             int[] sub = new int[(arr.length + 1) / 2];
    
11.             for (int i = 0; i < arr.length / 2; i++) sub[i] = arr[i * 2] + arr[i * 2 + 1];
    
12.             if (arr.length % 2 == 1) sub[arr.length / 2] = arr[arr.length - 1];
    
13.             arr = sub;
    
14.         }
    
15.     }
    
16.    
    
17.     // sum of nums[0], nums[1], ..., nums[k - 1];
    
18.     public int sumUntil(int k) {
    
19.         if (k == 0) return 0;
    
20.         int result = 0;
    
21.         int ord = k;
    
22.         for (int i = 0; i < list.size(); i++) {
    
23.             if (ord == 0) break;
    
24.             if (ord % 2 == 1) result += list.get(i)[ord - 1];
    
25.             ord = ord >> 1;
    
26.         }
    
27.         return result;
    
28.     }
    
29.    
    
30.     public void update(int i, int val) {
    
31.         int delta = val - list.get(0)[i];
    
32.         int ord = i;
    
33.         for (int level = 0; level < list.size(); level++) {
    
34.             list.get(level)[ord] += delta;
    
35.             ord = ord >> 1;
    
36.         }
    
37.     }
    
38.    
    
39.     public int sumRange(int i, int j) {
    
40.         return sumUntil(j + 1) - sumUntil(i);
    
41.     }
    
42. }

复制代码