2303-2306 solved.

liuyubobobo · liuyubobobo · commit 74cf562652bd · 2022-06-12T00:06:08.000-07:00
diff --git a/2001-2500/2303-Calculate-Amount-Paid-in-Taxes/cpp-2303/CMakeLists.txt b/2001-2500/2303-Calculate-Amount-Paid-in-Taxes/cpp-2303/CMakeLists.txt
@@ -0,0 +1,6 @@
+cmake_minimum_required(VERSION 3.22)
+project(A)
+
+set(CMAKE_CXX_STANDARD 14)
+
+add_executable(A main.cpp)
diff --git a/2001-2500/2303-Calculate-Amount-Paid-in-Taxes/cpp-2303/main.cpp b/2001-2500/2303-Calculate-Amount-Paid-in-Taxes/cpp-2303/main.cpp
@@ -0,0 +1,41 @@
+/// Source : https://leetcode.com/problems/calculate-amount-paid-in-taxes/
+/// Author : liuyubobobo
+/// Time   : 2022-06-11
+
+#include <iostream>
+#include <vector>
+
+using namespace std;
+
+
+/// Simulation
+/// Time Complexity: O(n)
+/// Space Complexity: O(1)
+class Solution {
+public:
+    double calculateTax(vector<vector<int>>& brackets, int income) {
+
+        if(income <= brackets[0][0]){
+            return income * brackets[0][1] / (double)100.0;
+        }
+
+        int left = income - brackets[0][0];
+        double res = brackets[0][0] * brackets[0][1] / (double)100.0;
+        for(int i = 1; i < brackets.size() && left; i ++){
+            int x = brackets[i][0] - brackets[i - 1][0];
+            int t = min(x, left);
+            left -= t;
+            res += t * brackets[i][1] / (double)100.0;
+        }
+        return res;
+    }
+};
+
+
+int main() {
+
+    vector<vector<int>> br1 = {{3, 50}, {7, 10}, {12, 25}};
+    cout << Solution().calculateTax(br1, 10) << '\n';
+
+    return 0;
+}
diff --git a/2001-2500/2304-Minimum-Path-Cost-in-a-Grid/cpp-2304/CMakeLists.txt b/2001-2500/2304-Minimum-Path-Cost-in-a-Grid/cpp-2304/CMakeLists.txt
@@ -0,0 +1,6 @@
+cmake_minimum_required(VERSION 3.22)
+project(B)
+
+set(CMAKE_CXX_STANDARD 14)
+
+add_executable(B main.cpp)
diff --git a/2001-2500/2304-Minimum-Path-Cost-in-a-Grid/cpp-2304/main.cpp b/2001-2500/2304-Minimum-Path-Cost-in-a-Grid/cpp-2304/main.cpp
@@ -0,0 +1,36 @@
+/// Source : https://leetcode.com/problems/minimum-path-cost-in-a-grid/
+/// Author : liuyubobobo
+/// Time   : 2022-06-11
+
+#include <iostream>
+#include <vector>
+#include <climits>
+
+using namespace std;
+
+
+/// DP
+/// Time Complexity: O(n * m * m)
+/// Space Compelxity: O(n * m)
+class Solution {
+public:
+    int minPathCost(vector<vector<int>>& grid, vector<vector<int>>& moveCost) {
+
+        int R = grid.size(), C = grid[0].size();
+        vector<vector<int>> dp(R, vector<int>(C, INT_MAX));
+        for(int j = 0; j < C; j ++) dp[0][j] = grid[0][j];
+
+        for(int i = 0; i + 1 < R; i ++)
+            for(int j = 0; j < C; j ++){
+                for(int k = 0; k < C; k ++)
+                    dp[i + 1][k] = min(dp[i + 1][k], dp[i][j] + moveCost[grid[i][j]][k] + grid[i + 1][k]);
+            }
+        return *min_element(dp[R - 1].begin(), dp[R - 1].end());
+    }
+};
+
+
+int main() {
+
+    return 0;
+}
diff --git a/2001-2500/2305-Fair-Distribution-of-Cookies/cpp-2305/CMakeLists.txt b/2001-2500/2305-Fair-Distribution-of-Cookies/cpp-2305/CMakeLists.txt
@@ -0,0 +1,6 @@
+cmake_minimum_required(VERSION 3.22)
+project(C)
+
+set(CMAKE_CXX_STANDARD 14)
+
+add_executable(C main.cpp)
diff --git a/2001-2500/2305-Fair-Distribution-of-Cookies/cpp-2305/main.cpp b/2001-2500/2305-Fair-Distribution-of-Cookies/cpp-2305/main.cpp
@@ -0,0 +1,48 @@
+/// Source : https://leetcode.com/problems/fair-distribution-of-cookies/
+/// Author : liuyubobobo
+/// Time   : 2022-06-11
+
+#include <iostream>
+#include <vector>
+
+using namespace std;
+
+
+/// Memoization
+/// Time Complexity: O(k * 3^n)
+/// Space Complexity: O(k * 2^n)
+class Solution {
+public:
+    int distributeCookies(vector<int>& cookies, int k) {
+
+        int n = cookies.size();
+
+        vector<int> table(1 << n, 0);
+        for(int state = 1; state < (1 << n); state ++){
+            int p = __builtin_ffs(state) - 1;
+            table[state] = table[state - (1 << p)] + cookies[p];
+        }
+
+        vector<vector<int>> dp(k + 1, vector<int>(1 << n, -1));
+        return dfs((1 << n) - 1, k, table, dp);
+    }
+
+private:
+    int dfs(int state, int k, const vector<int>& table, vector<vector<int>>& dp){
+
+        if(k == 1) return table[state];
+        if(dp[k][state] != -1) return dp[k][state];
+
+        int res = table[state];
+        for (int s = state; s; s = (s - 1) & state) {
+            res = min(res, max(table[s], dfs(state - s, k - 1, table, dp)));
+        }
+        return dp[k][state] = res;
+    }
+};
+
+
+int main() {
+
+    return 0;
+}
diff --git a/2001-2500/2306-Naming-a-Company/cpp-2306/CMakeLists.txt b/2001-2500/2306-Naming-a-Company/cpp-2306/CMakeLists.txt
@@ -0,0 +1,6 @@
+cmake_minimum_required(VERSION 3.22)
+project(D)
+
+set(CMAKE_CXX_STANDARD 14)
+
+add_executable(D main.cpp)
diff --git a/2001-2500/2306-Naming-a-Company/cpp-2306/main.cpp b/2001-2500/2306-Naming-a-Company/cpp-2306/main.cpp
@@ -0,0 +1,61 @@
+/// Source : https://leetcode.com/problems/naming-a-company/
+/// Author : liuyubobobo
+/// Time   : 2022-06-11
+
+#include <iostream>
+#include <vector>
+#include <unordered_set>
+#include <numeric>
+
+using namespace std;
+
+
+/// DP
+/// Time Complexity: O(n)
+/// Space Complexity: O(n)
+class Solution {
+public:
+    long long distinctNames(vector<string>& ideas) {
+
+        int n = ideas.size();
+
+        unordered_set<string> ideas_set(ideas.begin(), ideas.end());
+
+        vector<vector<bool>> can_change(26, vector<bool>(n, false));
+        vector<vector<int>> ok(26, vector<int>(26, 0));
+        for(int i = 0; i < n; i ++){
+            char o_first = ideas[i][0];
+            for(char c = 'a'; c <= 'z'; c ++){
+                ideas[i][0] = c;
+                if(c != o_first && !ideas_set.count(ideas[i])){
+                    can_change[c - 'a'][i] = true;
+                    ok[o_first - 'a'][c - 'a'] ++;
+                }
+
+            }
+            ideas[i][0] = o_first;
+        }
+
+        long long res = 0;
+        for(int i = 0; i < n; i ++){
+            char o_first = ideas[i][0];
+            for(char c = 'a'; c <= 'z'; c ++)
+                if(can_change[c - 'a'][i]) res += ok[c - 'a'][o_first - 'a'];
+        }
+        return res;
+    }
+};
+
+
+int main() {
+
+    vector<string> ideas1 = {"coffee","donuts","time","toffee"};
+    cout << Solution().distinctNames(ideas1) << '\n';
+    // 6
+
+    vector<string> ideas2 = {"lack","back"};
+    cout << Solution().distinctNames(ideas2) << '\n';
+    // 0
+
+    return 0;
+}
diff --git a/readme.md b/readme.md
@@ -2141,11 +2141,15 @@ email: [liuyubobobo@gmail.com](mailto:liuyubobobo@gmail.com)
 | 2295 | [Replace Elements in an Array](https://leetcode.com/problems/replace-elements-in-an-array/) | [无] | [C++](2001-2500/2295-Replace-Elements-in-an-Array/cpp-2295/) | | |
 | 2296 | [Design a Text Editor](https://leetcode.com/problems/design-a-text-editor/) | [无] | [C++](2001-2500/2296-Design-a-Text-Editor/cpp-2296/) | | |
 | 2297 | [Jump Game IX](https://leetcode.com/problems/jump-game-ix/) | [无] | [C++](2001-2500/2297-Jump-Game-IX/cpp-2297/) | | |
-| | | | | | |
+| 2298 | Database Problem: [Link](https://github.com/liuyubobobo/Play-Leetcode-Database/) | - | - | - | - |
 | 2299 | [Strong Password Checker II](https://leetcode.com/problems/strong-password-checker-ii/) | [无] | [C++](2001-2500/2299-Strong-Password-Checker-II/cpp-2299/) | | |
 | 2300 | [Successful Pairs of Spells and Potions](https://leetcode.com/problems/successful-pairs-of-spells-and-potions/) | [无] | [C++](2001-2500/2300-Successful-Pairs-of-Spells-and-Potions/cpp-2300/) | | |
 | 2301 | [Match Substring After Replacement](https://leetcode.com/problems/match-substring-after-replacement/) | [无] | [C++](2001-2500/2301-Match-Substring-After-Replacement/cpp-2301/) | | |
 | 2302 | [Count Subarrays With Score Less Than K](https://leetcode.com/problems/count-subarrays-with-score-less-than-k/) | [无] | [C++](2001-2500/2302-Count-Subarrays-With-Score-Less-Than-K/cpp-2302/) | | |
+| 2303 | [Calculate Amount Paid in Taxes](https://leetcode.com/problems/calculate-amount-paid-in-taxes/) | [无] | [C++](2001-2500/2303-Calculate-Amount-Paid-in-Taxes/cpp-2303/) | | |
+| 2304 | [Minimum Path Cost in a Grid](https://leetcode.com/problems/minimum-path-cost-in-a-grid/) | [无] | [C++](2001-2500/2304-Minimum-Path-Cost-in-a-Grid/cpp-2304/) | | |
+| 2305 | [Fair Distribution of Cookies](https://leetcode.com/problems/fair-distribution-of-cookies/) | [无] | [C++](2001-2500/2305-Fair-Distribution-of-Cookies/cpp-2305/) | | |
+| 2306 | [Naming a Company](https://leetcode.com/problems/naming-a-company/) | [无] | [C++](2001-2500/2306-Naming-a-Company/cpp-2306/) | | |
 | | | | | | |
 
 ## 力扣中文站比赛
