leetcode

commit 3635a481964340790a14ef5ce177a09dd7b7bebf
parent 647f2b6c7f1403d22bff11ea67fb1e7b7a04e4d4
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sun, 27 Oct 2024 18:12:07 +0100

1 Random Problem, 1 Update

Diffstat:
A
Problems/0313.cpp
 | 
21
+++++++++++++++++++++
M
Problems/1277.cpp
 | 
24
+++++++-----------------
M
README.md
 | 
1
+

3 files changed, 29 insertions(+), 17 deletions(-)
diff --git a/Problems/0313.cpp b/Problems/0313.cpp
@@ -0,0 +1,21 @@
+class Solution {
+  public:
+    int nthSuperUglyNumber(int n, const vector<int> &primes) const {
+        using type_t = tuple<long long, int, int>;
+        priority_queue<type_t, vector<type_t>, greater<>> pq;
+
+        for (int i = 0; i < size(primes); i++) {
+            pq.emplace(primes[i], primes[i], 0);
+        }
+
+        static int nums[100002] = {1, 0};
+        for (int i = 1; i < n;) {
+            const auto [num, prime, idx] = pq.top();
+            pq.pop();
+            if (num != nums[i - 1]) nums[i++] = num;
+            pq.emplace(1ll * prime * nums[idx + 1], prime, idx + 1);
+        }
+
+        return nums[n - 1];
+    }
+};
diff --git a/Problems/1277.cpp b/Problems/1277.cpp
@@ -1,23 +1,13 @@
 class Solution {
   public:
-    int countSquares(const vector<vector<int>> &matrix) {
-        int n = matrix.size(), m = matrix[0].size();
-        vector<vector<int>> count(n + 1, vector<int>(m + 1));
-
-        for (int i = 1; i <= n; i++) {
-            for (int j = 1; j <= m; j++) {
-                count[i][j] = matrix[i - 1][j - 1] + count[i - 1][j] + count[i][j - 1] - count[i - 1][j - 1];
-            }
-        }
-
+    int countSquares(vector<vector<int>> &matrix) const {
+        const int n = size(matrix), m = size(matrix[0]);
         int res = 0;
-        for (int i = 1; i <= n; i++) {
-            for (int j = 1; j <= m; j++) {
-                int x = i, y = j;
-                for (int k = 1, x = i, y = j; x <= n && y <= m; x++, y++, k++) {
-                    int sum = count[x][y] - count[i - 1][y] - count[x][j - 1] + count[i - 1][j - 1];
-                    if (sum != k * k) break;
-                    res++;
+
+        for (int i = 0; i < n; i++) {
+            for (int j = 0; j < m; res += matrix[i][j], j++) {
+                if (matrix[i][j] && i && j) {
+                    matrix[i][j] += min({matrix[i - 1][j - 1], matrix[i - 1][j], matrix[i][j - 1]});
                 }
             }
         }
diff --git a/README.md b/README.md
@@ -290,6 +290,7 @@ reference and a base for solving problems.
 |  0309  |   Medium   | [Best Time to Buy and Sell Stock with Cooldown](Problems/0309.cpp)                                 |
 |  0310  |   Medium   | [Minimum Height Trees](Problems/0310.cpp)                                                          |
 |  0312  |    Hard    | [Burst Balloons](Problems/0312.cpp)                                                                |
+|  0313  |   Medium   | [Super Ugly Number ](Problems/0313.cpp)                                                            |
 |  0315  |    Hard    | [Count of Smaller Numbers After Self](Problems/0315.cpp)                                           |
 |  0316  |   Medium   | [Remove Duplicate Letters](Problems/0316.cpp)                                                      |
 |  0318  |   Medium   | [Maximum Product of Word Lengths](Problems/0318.cpp)                                               |