d

PeterGW · PeterGW · commit 396d321ab1a3 · 2020-07-05T23:53:01.000+08:00
diff --git a/.DS_Store b/.DS_Store
diff --git a/Week03/defTemplate.js b/Week03/defTemplate.js
@@ -0,0 +1,19 @@
+var defFn = function(problem, param1, param2, ...) {
+    // recursion terminator  递归终止条件
+    if (problem) 
+        print_result 
+        return
+    // prespare data  处理当前问题
+    var data = prespare_data(problem)
+    var subproblems = split_problem(problem, data)
+
+    // conquer subproblems   解决子问题
+    var subresult1 = defFn(subproblems[0], param1, param2, ...)
+    var subresult2 = defFn(subproblems[1], param1, param2, ...)
+    var subresult3 = defFn(subproblems[2], param1, param2, ...)
+    ...
+
+    // process and generate the final result   处理最终结果
+
+    result = process_result(subresult1,subresult2,subresult3, ...)
+}
diff --git a/Week04/.DS_Store b/Week04/.DS_Store
diff --git a/Week04/NOTE.md b/Week04/NOTE.md
@@ -1 +1,5 @@
-学习笔记
+学习笔记
+
+-- Binary Search
+取n/2的位置 比较左右数据是否为有序  
+以左边、右边数据继续查找 直到找到不是有序的数据终止
diff --git a/Week04/findContentChildren.js b/Week04/findContentChildren.js
@@ -0,0 +1,21 @@
+
+/**
+ * @param {number[]} g
+ * @param {number[]} s
+ * @return {number}
+ */
+var findContentChildren = function(g, s) {
+    g = g.sort((a, b) => a - b);
+    s = s.sort((a, b) => a - b);
+    var maxNum = 0, gIndex = 0, sIndex = 0;
+    while(gIndex < g.length && sIndex < s.length) {
+        if (s[sIndex] > g[gIndex]) {
+            maxNum++;
+            sIndex++;
+            gIndex++
+        } else {
+            sIndex++
+        }
+    }
+    return maxNum;
+}
diff --git a/Week04/findMin.js b/Week04/findMin.js
@@ -0,0 +1,17 @@
+/**
+ * @param {number[]} nums
+ * @return {number}
+ */
+var findMin = function(nums) {
+    var left = 0;
+    var right = nums.length - 1;
+    while (left < right) {
+        var mid = (left + right) >> 1;
+        if (nums[mid] > nums[right]) {
+            left = mid + 1;
+        } else {
+            right = mid;
+        }
+    }
+    return nums[left];
+};
diff --git a/Week04/lemonJuice.js b/Week04/lemonJuice.js
@@ -0,0 +1,26 @@
+var lemonadeChange = function(bills) {
+    var five = 0, ten = 0;
+
+    for(let i = 0; i < bills.length; i++) {
+        if (bills[i] === 5) { 
+            five++;
+        } else if (bills[i] === 10) {
+            if ( five === 0) {
+                five--;
+            }
+            ten++;
+            five--;
+        } else if (bills[i] === 20) {
+            if (ten > 0 && five > 0) {
+                ten--;
+                five--;
+            } else if (five > 3) {
+                five -= 3;
+            } else {
+                return false;
+            }
+        }
+    }
+
+    return true;
+};
diff --git a/Week04/maxProfit.js b/Week04/maxProfit.js
@@ -0,0 +1,15 @@
+// 后一天比前一天大为收益，小则跳过
+
+/**
+ * @param {number[]} prices
+ * @return {number}
+ */
+var maxProfit = function(prices) {
+    let income = 0;
+    for (let i = 0; i < prices.length; i++) {
+        if (prices[i+1] > prices[i]) {
+            income += prices[i+1] - prices[i];
+        }
+    }
+    return income;
+};
diff --git a/Week04/numIslands.js b/Week04/numIslands.js
@@ -0,0 +1,30 @@
+/**
+ * @param {character[][]} grid
+ * @return {number}
+ */
+var numIslands = function(grid) {
+    if(!grid.length){
+        return 0;
+    }
+    let num = 0;
+    let row = grid.length;
+    let col = grid[0].length;
+    let loop = (x, y) => {
+        if(grid[x][y] == 1){
+            grid[x][y] = 0;
+            x > 0 && loop(x - 1, y);
+            x < row - 1 && loop(x + 1, y);
+            y > 0 && loop(x, y - 1);
+            y < col - 1 && loop(x, y + 1);
+        }
+    }
+    for(let i = 0; i < row; i++){
+        for(let j = 0; j < col; j++){
+            if(grid[i][j] == 1){
+                num++;
+                loop(i, j);
+            }
+        }
+    }
+    return num;
+}
