commit 54acc06d144ad32abdb7e43a6ddc1f1d69a02545
parent 985ea2690da12d511963bdec17486d86773e9c81
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date: Wed, 20 Sep 2023 19:59:10 +0000
Daily Problem and 5 Random Problems
Diffstat:
7 files changed, 102 insertions(+), 8 deletions(-)
diff --git a/Problems/0643.cpp b/Problems/0643.cpp
@@ -0,0 +1,15 @@
+class Solution {
+ public:
+ double findMaxAverage(const vector<int> &nums, int k) {
+ int sum = 0;
+ for (int i = 0; i < k; i++)
+ sum += nums[i];
+ int maxi = sum;
+ for (int i = k; i < nums.size(); i++) {
+ sum -= nums[i - k];
+ sum += nums[i];
+ maxi = max(maxi, sum);
+ }
+ return (double)maxi / k;
+ }
+};
diff --git a/Problems/1004.cpp b/Problems/1004.cpp
@@ -0,0 +1,13 @@
+class Solution {
+ public:
+ int longestOnes(const vector<int> &nums, int k) {
+ int maxi = 0, left = 0;
+ for (int i = 0; i < nums.size(); i++) {
+ maxi = max(maxi, i - left);
+ if (!nums[i]) k--;
+ while (k < 0)
+ if (!nums[left++]) k++;
+ }
+ return max(maxi, (int)nums.size() - left);
+ }
+};
diff --git a/Problems/1207.cpp b/Problems/1207.cpp
@@ -0,0 +1,16 @@
+class Solution {
+ public:
+ bool uniqueOccurrences(const vector<int> &arr) {
+ static int count[2001], seen[1001];
+ memset(count, 0x00, sizeof(count));
+ memset(seen, 0x00, sizeof(seen));
+ for (const int n : arr)
+ count[n + 1000]++;
+ for (const int n : count) {
+ if (!n) continue;
+ if (seen[n]) return false;
+ seen[n] = 1;
+ }
+ return true;
+ }
+};
diff --git a/Problems/1557.cpp b/Problems/1557.cpp
@@ -1,15 +1,24 @@
class Solution {
public:
- vector<int> findSmallestSetOfVertices(int n, vector<vector<int>> &edges) {
- vector<int> root(n), res;
- iota(root.begin(), root.end(), 0);
+ bool closeStrings(const string &word1, const string &word2) {
+ if (word1.size() != word2.size()) return false;
+ const int n = word1.size();
+ int w1[27] = {0}, w2[27] = {0};
- for (auto &p : edges)
- root[p[1]] = p[0];
+ for (int i = 0; i < word1.size(); i++) {
+ w1[word1[i] & 0x1F]++;
+ w2[word2[i] & 0x1F]++;
+ }
- for (int i = 0; i < n; i++)
- if (i == root[i]) res.push_back(i);
+ for (int i = 1; i <= 26; i++)
+ if ((bool)w1[i] ^ (bool)w2[i]) return false;
- return res;
+ sort(begin(w1), end(w1));
+ sort(begin(w2), end(w2));
+
+ for (int i = 0; i < 26; i++)
+ if (w1[i] != w2[i]) return false;
+
+ return true;
}
};
diff --git a/Problems/1658.cpp b/Problems/1658.cpp
@@ -0,0 +1,18 @@
+class Solution {
+ public:
+ int minOperations(const vector<int> &nums, int x) {
+ const int goal = accumulate(begin(nums), end(nums), 0) - x;
+ if (goal < 0) return -1;
+ if (goal == 0) return nums.size();
+
+ int sum = 0, start = 0, end = 0, res = 0;
+ for (int i = 0; i < nums.size(); i++) {
+ sum += nums[i];
+ while (sum > goal)
+ sum -= nums[start++];
+ if (sum == goal) res = max(res, i - start + 1);
+ }
+
+ return res != 0 ? nums.size() - res : -1;
+ }
+};
diff --git a/Problems/1679.cpp b/Problems/1679.cpp
@@ -0,0 +1,17 @@
+class Solution {
+ public:
+ int maxOperations(vector<int> &nums, const int k) {
+ sort(nums.begin(), nums.end());
+ int i = 0, j = nums.size() - 1, res = 0;
+ while (i < j) {
+ const int sum = nums[i] + nums[j];
+ if (sum == k)
+ i++, j--, res++;
+ else if (sum < k)
+ i++;
+ else
+ j--;
+ }
+ return res;
+ }
+};
diff --git a/README.md b/README.md
@@ -343,6 +343,7 @@ for solving problems.
| 0617 | Easy | [Merge Two Binary Trees](Problems/0617.cpp) |
| 0621 | Medium | [Task Scheduler](Problems/0621.cpp) |
| 0637 | Easy | [Average of Levels in Binary Tree](Problems/0637.cpp) |
+| 0643 | Easy | [Maximum Average Subarray I](Problems/0643.cpp) |
| 0646 | Medium | [Maximum Length of Pair Chain](Problems/0646.cpp) |
| 0647 | Medium | [Palindromic Substrings](Problems/0647.cpp) |
| 0649 | Medium | [Dota2 Senate](Problems/0649.cpp) |
@@ -466,6 +467,7 @@ for solving problems.
| 0994 | Medium | [Rotting Oranges](Problems/0994.cpp) |
| 0997 | Easy | [Find the Town Judge](Problems/0997.cpp) |
| 0998 | Medium | [Maximum Binary Tree II](Problems/0998.cpp) |
+| 1004 | Medium | [Max Consecutive Ones III](Problems/1004.cpp) |
| 1008 | Medium | [Construct Binary Search Tree from Preorder Traversal](Problems/1008.cpp) |
| 1011 | Medium | [Capacity To Ship Packages Within D Days](Problems/1011.cpp) |
| 1014 | Medium | [Best Sightseeing Pair](Problems/1014.cpp) |
@@ -507,6 +509,7 @@ for solving problems.
| 1190 | Medium | [Reverse Substrings Between Each Pair of Parentheses](Problems/1190.cpp) |
| 1202 | Medium | [Smallest String With Swaps](Problems/1202.cpp) |
| 1203 | Hard | [Sort Items by Groups Respecting Dependencies](Problems/1203.cpp) |
+| 1207 | Easy | [Unique Number of Occurrences](Problems/1207.cpp) |
| 1209 | Medium | [Remove All Adjacent Duplicates in String II](Problems/1209.cpp) |
| 1218 | Medium | [Longest Arithmetic Subsequence of Given Difference](Problems/1218.cpp) |
| 1219 | Medium | [Path with Maximum Gold](Problems/1219.cpp) |
@@ -632,10 +635,13 @@ for solving problems.
| 1641 | Medium | [Count Sorted Vowel Strings](Problems/1641.cpp) |
| 1646 | Easy | [Get Maximum in Generated Array](Problems/1646.cpp) |
| 1647 | Medium | [Minimum Deletions to Make Character Frequencies Unique](Problems/1647.cpp) |
+| 1657 | Medium | [Determine if Two Strings Are Close](Problems/1657.cpp) |
+| 1658 | Medium | [Minimum Operations to Reduce X to Zero](Problems/1658.cpp) |
| 1663 | Medium | [Smallest String With A Given Numeric Value](Problems/1663.cpp) |
| 1669 | Medium | [Merge In Between Linked Lists](Problems/1669.cpp) |
| 1672 | Easy | [Richest Customer Wealth](Problems/1672.cpp) |
| 1675 | Hard | [Minimize Deviation in Array](Problems/1675.cpp) |
+| 1679 | Medium | [Max Number of K-Sum Pairs](Problems/1679.cpp) |
| 1689 | Medium | [Partitioning Into Minimum Number Of Deci-Binary Numbers](Problems/1689.cpp) |
| 1696 | Medium | [Jump Game VI](Problems/1696.cpp) |
| 1697 | Hard | [Checking Existence of Edge Length Limited Paths](Problems/1697.cpp) |
