commit 7f63e95a33b12ce9cd900c0f75c2bd422db067f6
parent 66217fb7838be3c0bbb9dbfcd72d7c344e11807c
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date: Sun, 24 Sep 2023 23:17:38 +0000
Daily Problem and 5 Random Problems
Diffstat:
7 files changed, 146 insertions(+), 0 deletions(-)
diff --git a/Problems/0169.cpp b/Problems/0169.cpp
@@ -1,3 +1,4 @@
+// Naive Solution
class Solution {
public:
int majorityElement(const vector<int> &nums) {
@@ -9,3 +10,19 @@ class Solution {
return -1;
}
};
+
+// Boyer-Moore Algorithm: O(n) time, O(1) space
+class Solution {
+ public:
+ int majorityElement(const vector<int> &nums) {
+ int candid = nums[0], count = 1;
+ for (int i = 1; i < nums.size(); i++) {
+ if (!count) candid = nums[i];
+ if (candid == nums[i])
+ count++;
+ else
+ count--;
+ }
+ return candid;
+ }
+};
diff --git a/Problems/0229.cpp b/Problems/0229.cpp
@@ -0,0 +1,30 @@
+class Solution {
+ public:
+ vector<int> majorityElement(vector<int> &nums) {
+ int a = -1, b = -1, ca = 0, cb = 0;
+ for (const int n : nums) {
+ if (n == a)
+ ca++;
+ else if (b == n)
+ cb++;
+ else if (!ca)
+ a = n, ca = 1;
+ else if (!cb)
+ b = n, cb = 1;
+ else
+ ca--, cb--;
+ }
+ ca = cb = 0;
+ for (const int n : nums) {
+ if (n == a)
+ ca++;
+ else if (n == b)
+ cb++;
+ }
+
+ vector<int> res;
+ if (ca > nums.size() / 3) res.push_back(a);
+ if (cb > nums.size() / 3) res.push_back(b);
+ return res;
+ }
+};
diff --git a/Problems/0799.cpp b/Problems/0799.cpp
@@ -0,0 +1,20 @@
+class Solution {
+ public:
+ double champagneTower(int poured, int query_row, int query_glass) {
+ static double dp[102][102];
+ memset(dp, 0x00, sizeof(dp));
+
+ dp[0][0] = (double)poured;
+ for (int i = 0; i <= query_row; i++) {
+ for (int j = 0; j <= i; j++) {
+ double split = (dp[i][j] - 1.0) / 2.0;
+ if (split > 0) {
+ dp[i + 1][j] += split;
+ dp[i + 1][j + 1] += split;
+ }
+ }
+ }
+
+ return min(1.0, dp[query_row][query_glass]);
+ }
+};
diff --git a/Problems/1170.cpp b/Problems/1170.cpp
@@ -0,0 +1,28 @@
+class Solution {
+ int f(const string &s) {
+ int res = 0, mini = s[0];
+ for (const char c : s) {
+ if (c == mini) res++;
+ if (c < mini) {
+ mini = c;
+ res = 1;
+ }
+ }
+ return res;
+ }
+
+ public:
+ vector<int> numSmallerByFrequency(const vector<string> &queries, const vector<string> &words) {
+ vector<int> res(queries.size()), mem(words.size());
+ for (int i = 0; i < words.size(); i++)
+ mem[i] = f(words[i]);
+ sort(mem.begin(), mem.end());
+
+ for (int i = 0; i < queries.size(); i++) {
+ const int t = f(queries[i]);
+ res[i] = words.size() - distance(begin(mem), upper_bound(begin(mem), end(mem), t));
+ }
+
+ return res;
+ }
+};
diff --git a/Problems/1727.cpp b/Problems/1727.cpp
@@ -0,0 +1,24 @@
+class Solution {
+ public:
+ int largestSubmatrix(vector<vector<int>> &matrix) {
+ const int n = matrix.size(), m = matrix[0].size();
+ vector<int> height(m, 0);
+ int ans = 0;
+
+ for (int i = 0; i < n; i++) {
+ for (int j = 0; j < m; j++) {
+ if (matrix[i][j] == 0)
+ height[j] = 0;
+ else
+ height[j] += 1;
+ }
+
+ vector<int> order = height;
+ sort(begin(order), end(order));
+
+ for (int j = 0; j < m; j++)
+ ans = max(ans, order[j] * (m - j));
+ }
+ return ans;
+ }
+};
diff --git a/Problems/2780.cpp b/Problems/2780.cpp
@@ -0,0 +1,22 @@
+class Solution {
+ public:
+ int minimumIndex(const vector<int> &nums) {
+ int candid = nums[0], count = 0;
+ for (const int n : nums) {
+ if (!count) candid = n;
+ count += candid == n ? 1 : -1;
+ }
+
+ int ccount = 0;
+ for (const int n : nums)
+ if (n == candid) ccount++;
+
+ count = 0;
+ for (int i = 0; i < nums.size(); i++) {
+ if (nums[i] == candid) count++;
+ if ((count * 2 > i + 1) && (ccount - count) * 2 > nums.size() - i - 1) return i;
+ }
+
+ return -1;
+ }
+};
diff --git a/README.md b/README.md
@@ -209,6 +209,7 @@ for solving problems.
| 0226 | Easy | [Invert Binary Tree](Problems/0226.cpp) |
| 0227 | Medium | [Basic Calculator II](Problems/0227.cpp) |
| 0228 | Easy | [Summary Ranges](Problems/0228.cpp) |
+| 0229 | Medium | [Majority Element II](Problems/0229.cpp) |
| 0231 | Easy | [Power of Two](Problems/0231.cpp) |
| 0232 | Easy | [Implement Queue using Stacks](Problems/0232.cpp) |
| 0234 | Easy | [Palindrome Linked List](Problems/0234.cpp) |
@@ -395,6 +396,7 @@ for solving problems.
| 0787 | Medium | [Cheapest Flights Within K Stops](Problems/0787.cpp) |
| 0791 | Medium | [Custom Sort String](Problems/0791.cpp) |
| 0797 | Medium | [All Paths From Source to Target](Problems/0797.cpp) |
+| 0799 | Medium | [Champagne Tower](Problems/0799.cpp) |
| 0802 | Medium | [Find Eventual Safe States](Problems/0802.cpp) |
| 0807 | Medium | [Max Increase to Keep City Skyline](Problems/0807.cpp) |
| 0808 | Medium | [Soup Servings](Problems/0808.cpp) |
@@ -513,6 +515,7 @@ for solving problems.
| 1146 | Medium | [Snapshot Array](Problems/1146.cpp) |
| 1161 | Medium | [Maximum Level Sum of a Binary Tree](Problems/1161.cpp) |
| 1162 | Medium | [As Far from Land as Possible](Problems/1162.cpp) |
+| 1170 | Medium | [Compare Strings by Frequency of the Smallest Character](Problems/1170.cpp) |
| 1187 | Hard | [Make Array Strictly Increasing](Problems/1187.cpp) |
| 1190 | Medium | [Reverse Substrings Between Each Pair of Parentheses](Problems/1190.cpp) |
| 1202 | Medium | [Smallest String With Swaps](Problems/1202.cpp) |
@@ -665,6 +668,7 @@ for solving problems.
| 1706 | Medium | [Where Will the Ball Fall](Problems/1706.cpp) |
| 1721 | Medium | [Swapping Nodes in a Linked List](Problems/1721.cpp) |
| 1722 | Medium | [Minimize Hamming Distance After Swap Operations](Problems/1722.cpp) |
+| 1727 | Medium | [Largest Submatrix With Rearrangements](Problems/1727.cpp) |
| 1732 | Easy | [Find the Highest Altitude](Problems/1732.cpp) |
| 1734 | Medium | [Decode XORed Permutation](Problems/1734.cpp) |
| 1743 | Medium | [Restore the Array From Adjacent Pairs](Problems/1743.cpp) |
@@ -827,6 +831,7 @@ for solving problems.
| 2707 | Medium | [Extra Characters in a String](Problems/2707.cpp) |
| 2711 | Medium | [Difference of Number of Distinct Values on Diagonals](Problems/2711.cpp) |
| 2740 | Medium | [Find the Value of the Partition](Problems/2740.cpp) |
+| 2780 | Medium | [Minimum Index of a Valid Split](Problems/2780.cpp) |
| 2785 | Medium | [Sort Vowels in a String](Problems/2785.cpp) |
| 2799 | Medium | [Count Complete Subarrays in an Array](Problems/2799.cpp) |
| 2807 | Medium | [Insert Greatest Common Divisors in Linked List](Problems/2807.cpp) |
