algorithm001 · GeekUniversity · May 13, 2019 · May 8, 2019 · May 9, 2019
diff --git a/Week_04/id_150/Leetcode_169_150.cpp b/Week_04/id_150/Leetcode_169_150.cpp
@@ -0,0 +1,52 @@
+Method 1:
+class Solution {
+public:
+    int majorityElement(vector<int>& nums) {
+        sort(nums.begin(), nums.end());
+        return nums[nums.size()/2];
+    }
+};
+
+
+Method 2:
+class Solution {
+public:
+    int majorityElement(vector<int>& nums) {
+        int num = nums[0];
+        int cnt = 1;
+        for(int i = 1; i < nums.size(); i++){
+            if(nums[i] == num) {
+                cnt++;
+            } else{
+                if(cnt > 0) cnt--;
+                else{
+                    num = nums[i];
+                    cnt = 1;
+                }
+            }
+        }
+        return num;
+    }
+};
+
+Method 3:
+class Solution {
+public:
+    int majorityElement(vector<int>& nums) {
+        vector<int> bits(32,0);
+        for(int num : nums) {
+            for(int i = 0; i < 32; i++) {
+                bits[i] += (num >> (31- i)) & 1; // get the number of 1
+            }
+        }
+
+        int res = 0;
+        for(int i = 0; i < 32; i++) {
+            if(bits[i] > (nums.size()/2)) {
+                res |= (1 << (31 - i));
+            }
+        }
+        return res;
+    }
+};
+
diff --git a/Week_04/id_150/Leetcode_241_150.cpp b/Week_04/id_150/Leetcode_241_150.cpp
@@ -0,0 +1,136 @@
+Method 1:
+class Solution {
+public:
+    vector<int> diffWaysToCompute(string input) {
+        vector<int> res;
+
+        res = dfs(input, 0, input.size());
+
+        return res;
+    }
+
+
+    vector<int> dfs(string input, int begin, int end) {
+        vector<int> res;
+        bool sign = false;
+        for(int i = begin; i < end; i++) {
+            if((input[i] == '+') || (input[i] == '-') || (input[i] == '*')) {
+                sign = true;
+                break;
+            }
+        }
+        if(!sign) {
+            int tmp = 0;
+            string validation = "";
+            for(int i = begin; i < end; i++) {
+                tmp = tmp * 10 + (input[i] - '0');
+                validation += input[i];
+            }
+            res.push_back(tmp);
+            return res;
+        }
+        for(int i = begin; i < end; i++) {
+            if((input[i] == '+') || (input[i] == '-') || (input[i] == '*')) {
+                vector<int> left = dfs(input, begin, i);
+                vector<int> right = dfs(input, i + 1, end);
+                //cout << "left:" << left << " right:" << right << endl;
+                if(input[i] == '+'){
+                    for(int le : left) {
+                        for(int ri : right) {
+                            res.push_back(le + ri);
+                        }
+                    }
+                }
+                else if(input[i] == '-') {
+                    for(int le : left) {
+                        for(int ri : right) {
+                            res.push_back(le - ri);
+                        }
+                    }
+                }
+                else{
+                    for(int le : left) {
+                        for(int ri : right) {
+                            res.push_back(le * ri);
+                        }
+                    }
+                }
+            } 
+        }
+
+        return res;
+    }
+};
+
+// 2 * 3 - 4 * 5
+// 2 * 3 - 4    * 5
+
+// (2 * 3) - 4
+// 2 * (3 - 4)
+
+// (2 * 3 - 4) * 5
+//  ((2 * 3) - 4) * 5 = 10
+//  (2 * (3 - 4)) * 5 = -10
+// 2 * (3 - 4 * 5)
+//   2 * ((3 - 4) * 5) = -10
+//   2 * (3 - (4 * 5)) = -34
+// 2 * 3 - (4 * 5) = -14
+
+// 2 * 3 - 4 * 5  * 6
+
+// (2 * 3 - 4 * 5) * 6
+// 2 * (3 - 4 * 5 * 6)
+// 2 * 3 - (4 * 5 * 6)
+// 2 * 3 - 4 * (5 * 6)
+
+Method 2:
+
+class Solution {
+
+public:
+	bool isoperator(char c){
+		if(c == '+' || c == '*' || c =='-')
+			return true;
+		return false;
+	}
+
+	vector<int> diffWaysToCompute(string input) {
+  		vector<int> ans;
+		if(input.size() == 0){
+			return ans;
+		} else{
+			for(int i = 0; i < input.length(); i++){
+				if(isoperator(input[i])){
+					vector<int> l = diffWaysToCompute(input.substr(0,i));
+					vector<int> r = diffWaysToCompute(input.substr(i+1));
+
+					for(int j = 0; j < l.size(); j++){
+						for(int k = 0; k < r.size(); k++){
+							int a = l[j];
+							int b = r[k];
+							switch(input[i]){
+								case '+':{
+									ans.push_back(a+b);
+									break;
+								} 
+								case '-':{
+									ans.push_back(a-b);
+									break;
+								}
+								case '*':{
+									ans.push_back(a*b);
+									break;
+								}
+							}
+						}
+					}
+				}
+			}
+			if(ans.empty()){
+				ans.push_back(atoi(input.c_str()));
+			}
+			return ans;
+		}
+    }
+
+};
diff --git a/Week_04/id_150/Leetcode_563_150.cpp b/Week_04/id_150/Leetcode_563_150.cpp
@@ -0,0 +1,23 @@
+class Solution {
+public:
+    int maxProfit(vector<int>& prices, int fee) {
+        if(prices.size() == 1) 
+            return 0;
+
+        int buy = prices[0];
+        int money = 0;
+        for(int i = 1; i < prices.size(); i++) {
+            if((prices[i] - buy) > fee) {
+                cout << prices[i] << " " << buy <<  " " << endl;
+                money += prices[i] - buy - fee;
+                buy = prices[i] - fee;
+            } else {
+                if(prices[i] < buy) 
+                    buy = prices[i];
+            }
+        }
+
+        return money;
+    }
+};
+
diff --git a/Week_04/id_150/Leetcode_746_150.cpp b/Week_04/id_150/Leetcode_746_150.cpp
@@ -0,0 +1,20 @@
+class Solution {
+public:
+    int minCostClimbingStairs(vector<int>& cost) {
+        vector<int> res(cost.size() + 1, 0);
+        res[0] = cost[0];
+        res[1] = cost[1];
+
+        for(int i = 2; i < cost.size() + 1; i++) {
+            if(i == cost.size()) {
+                res[i] = min(res[i - 1], res[i - 2]);
+            } else {
+                res[i] = min(res[i - 1], res[i - 2]) + cost[i];
+            }
+        }
+
+        return res[cost.size()];   
+
+    }
+
+};
diff --git a/Week_04/id_150/Leetcodede_455_10.cpp b/Week_04/id_150/Leetcodede_455_10.cpp
@@ -0,0 +1,23 @@
+class Solution {
+public:
+    int findContentChildren(vector<int>& g, vector<int>& s) {
+        sort(g.begin(), g.end());
+        sort(s.begin(), s.end());
+
+        int gdx = 0, sdx = 0;
+
+        int res = 0;
+        while((gdx < g.size()) && (sdx < s.size())) {
+            if(g[gdx] <= s[sdx]) {
+                res++;
+                gdx++;
+                sdx++;
+            } else {
+                sdx++;
+            }
+        }
+
+        return res;
+    }
+};
+