week1

LINEAR STRUCTURE

1. Valid Parentheses (No 423)

leetcode20---XinxinWang

2. Merge Two Sorted Lists

+ (http://lintcode.com/en/problem/merge-two-sorted-lists/)
+ leetcode21
+ xinxinWang

3. (Two Pointer) Find Optimal Weight ： Two Sum - Closest to target

+        
+ XinxinWang

  
     double capacity,     array(double[] weights),  int numOfContainers。
   array     weights       capacity    capacity        Container object  return。
first second       ，numOfContainer java     ,  double[]     length  。
public Container findOptimalWeights(double capacity, double[] weights, int numOfContainers)
class Container {
    public double first;
    public double second;
}

4. LinkedList

a. Reverse Second Half of Linked List (         ，  reverse linked list   
    

b. Reverse Linked List 2  --- leetcode 92 --- Xinxin Wang

c. Reverse Linked List --- leetcode 206 --- Xinxin Wang

d  Palindrome Linked List --- leetcode 234 ---Xinxin Wang

Other

1. Leetcode 223 RectangleArea 。

（Yifan Tian)

//  
//                 ，       ，  true  false。

2. GCD Greatest Common Divisor

(xinxin he)

  
               。
      
        ，        a b      。
  ：gcd(a,b) = gcd(b,a mod b)
  ：a     a = kb + r， r = a mod b
  d a,b      ，  
d|a, d|b， r = a - kb，  d|r
  d (b,a mod b)    
  d  (b,a mod b)    ， 
d | b , d |r ，  a = kb +r
  d  (a,b)    
  (a,b) (b,a mod b)        ，           ，  。

3. Given an array, return the number of possible arithmetic sequence.

(Linglu Wang)

     ，           

4. Day change(cell growth)

(Linglu Wang)

  
int[] dayChange(int[] cells, int days),，cells  ，  8   。
  cell，          ，        0，     1，   inactive active   ，     coding  0 1  。                     ，     0。    days， days     。
  ：
cells: [1 0 0 0 0 1 0 0]
days: 1
output: [0 1 0 0 1 0 1 0]

5. Round Robin

  
          request，        ，              q，             。               ，       。
           cpu      ，    cpu                ，  Robin Round      float。
OA   ：
  ： 【0，1，4】 【5，2，3】 q=3.     average wait time 2.3333333
 0 ，  1   。  peek            1，      1     0 ，     0 ，    1     0。    1  3 ，     2  。
       3           ，    2  1   。    2   。
         1      ，       ，    poll  1，    1 add     。
           2，  1.
      peek  ，      2.      2  1    ，      3 。       3-1=2.
         ，    2      2 ，      5 。        5        。      3    。    3   。
           2，  1，  3.
       2      ，       2 poll   ，          。
                1，  3.
     peek  。   ，    q       ，  3－2=1 ，    3 。
    peek  ，    1，     5 ，         1，     3 ，    1   2 。     2+2=4 。
    1  2 。       1  ，   5+2 ＝ 7      。         3 。
     peek，      3 ，      7 。  3       4 。    3  7-4 ＝ 3 。        3 。
         2+2+3 ＝ 7 。       7/3 ＝ 2.3333 。

6. Four Integer

  
Given four integers, make F(S) = abs(S[0]-S[1])+abs(S[1]-S[2])+abs(S[2]-S[3]) to be largest.

String

1. Rotate String (No.8)

(xinxin he)

   int[][] matirx，           path pi，pi      mi，   mi     。      .
  ：
[8, 4, 7]
[6, 5, 9]
 3 path：
8-4-7-9 min: 4
8-4-5-9 min: 4
8-6-5-9 min: 5
return: 5

//dp   
int helper(int[][] matrix){
   int[] result = new int[matrix[0].length];
   result[0] = matrix[0][0];
   for(int i=1; i= row || j >= col) return;
       if (i == row - 1 && j == col - 1) {
           min = Math.min(min, matrix[i][j]);
           max = Math.max(max, min);
           return;
       }
       min = Math.min(min, matrix[i][j]);
       dfsHelper(matrix, min, i, j + 1);
       dfsHelper(matrix, min, i + 1, j);
   }
}