leetcode

commit a8191073f125dc1c532e676a6ac182a6e9752b83
parent 1572f4d687c5ee888458c3d1dbf643da4dd197c8
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Tue,  5 Nov 2024 15:13:32 +0100

5 Random Problems

Diffstat:
A
Problems/0390.cpp
 | 
12
++++++++++++
A
Problems/0393.cpp
 | 
23
+++++++++++++++++++++++
A
Problems/0395.cpp
 | 
34
++++++++++++++++++++++++++++++++++
A
Problems/0396.cpp
 | 
20
++++++++++++++++++++
A
Problems/0397.cpp
 | 
13
+++++++++++++
M
README.md
 | 
5
+++++

6 files changed, 107 insertions(+), 0 deletions(-)
diff --git a/Problems/0390.cpp b/Problems/0390.cpp
@@ -0,0 +1,12 @@
+class Solution {
+  public:
+    int lastRemaining(int n) const {
+        int head = 1;
+
+        for (int step = 1, dir = 1; n > 1; step *= 2, n /= 2, dir = !dir) {
+            head += dir || n % 2 ? step : 0;
+        }
+
+        return head;
+    }
+};
diff --git a/Problems/0393.cpp b/Problems/0393.cpp
@@ -0,0 +1,23 @@
+class Solution {
+  public:
+    bool validUtf8(const vector<int> &data) const {
+        static const uint8_t mask[] = {0x80, 0xE0, 0xF0, 0xF8};
+        static const uint8_t val[] = {0x00, 0xC0, 0xE0, 0xF0};
+        const int n = size(data);
+
+        for (int i = 0, j, k; i < n; i++) {
+            for (j = 0; j < 4; j++) {
+                if ((data[i] & mask[j]) != val[j]) continue;
+                break;
+            }
+            if (j == 4) return false;
+
+            for (k = 0; k < j && i + 1 < n; k++) {
+                if ((data[++i] & 0xC0) != 0x80) return false;
+            }
+            if (k != j) return false;
+        }
+
+        return true;
+    }
+};
diff --git a/Problems/0395.cpp b/Problems/0395.cpp
@@ -0,0 +1,34 @@
+class Solution {
+  public:
+    int longestSubstring(const string &s, int k) const {
+        const int n = size(s);
+        static int count[26];
+        int res = 0, maxUnique = 0;
+
+        memset(count, 0x00, sizeof(count));
+        for (const char c : s)
+            maxUnique += !count[c - 'a']++;
+
+        for (int l = 1; l <= maxUnique; l++) {
+            memset(count, 0x00, sizeof(count));
+            int i = 0, j = 0, unique = 0, least = 0;
+            while (j < n) {
+                if (unique <= l) {
+                    unique += !count[s[j] - 'a']++;
+                    least += count[s[j] - 'a'] == k;
+                    j++;
+                } else {
+                    least -= count[s[i] - 'a'] == k;
+                    unique -= !--count[s[i] - 'a'];
+                    i++;
+                }
+
+                if (unique == l && least == l) {
+                    res = max(res, j - i);
+                }
+            }
+        }
+
+        return res;
+    }
+};
diff --git a/Problems/0396.cpp b/Problems/0396.cpp
@@ -0,0 +1,20 @@
+class Solution {
+  public:
+    int maxRotateFunction(const vector<int> &nums) const {
+        const int n = size(nums);
+        int sum = 0, crnt = 0;
+
+        for (int i = 0; i < n; i++) {
+            crnt += i * nums[i];
+            sum += nums[i];
+        }
+
+        int res = crnt;
+        for (int i = n - 1; i >= 0; i--) {
+            crnt += sum - nums[i] * n;
+            res = max(res, crnt);
+        }
+
+        return res;
+    }
+};
diff --git a/Problems/0397.cpp b/Problems/0397.cpp
@@ -0,0 +1,13 @@
+class Solution {
+  private:
+    unordered_map<int, int> visited;
+
+  public:
+    int integerReplacement(int n) {
+        if (n == 1) return 0;
+        if (visited.count(n)) return visited[n];
+
+        if (!(n & 1 == 1)) return visited[n] = 1 + integerReplacement(n / 2);
+        return visited[n] = 2 + min(integerReplacement(n / 2), integerReplacement(n / 2 + 1));
+    }
+};
diff --git a/README.md b/README.md
@@ -341,8 +341,13 @@ reference and a base for solving problems.
 |  0387  |    Easy    | [First Unique Character in a String](Problems/0387.cpp)                                            |
 |  0388  |   Medium   | [Longest Absolute File Path](Problems/0388.cpp)                                                    |
 |  0389  |    Easy    | [Find the Difference](Problems/0389.cpp)                                                           |
+|  0390  |   Medium   | [Elimination Game](Problems/0390.cpp)                                                              |
 |  0392  |    Easy    | [Is Subsequence](Problems/0392.cpp)                                                                |
+|  0393  |   Medium   | [UTF-8 Validation](Problems/0393.cpp)                                                              |
 |  0394  |   Medium   | [Decode String](Problems/0394.cpp)                                                                 |
+|  0395  |   Medium   | [Longest Substring with At Least K Repeating Characters](Problems/0395.cpp)                        |
+|  0396  |   Medium   | [Rotate Function](Problems/0396.cpp)                                                               |
+|  0397  |   Medium   | [Integer Replacement](Problems/0397.cpp)                                                           |
 |  0398  |   Medium   | [Random Pick Index](Problems/0398.cpp)                                                             |
 |  0399  |   Medium   | [Evaluate Division](Problems/0399.cpp)                                                             |
 |  0401  |    Easy    | [Binary Watch](Problems/0401.cpp)                                                                  |