leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE |
commit78e18e6b449d43415e3f1f4ef5e1c360ea33a899
parentd73581d247cf1608adebfb2b20eb570f5ab66892
authorDimitrije Dobrota <mail@dimitrijedobrota.com>
dateSun, 26 Feb 2023 14:09:50 +0100

Random Problem

Diffstat:
AProblems/0037.cpp|+++++++++++++++++++++++++++++++
DProblems/1011|----------------
AProblems/1011.cpp|+++++++++++++++++
MREADME.md|++-

4 files changed, 50 insertions(+), 17 deletions(-)

diff --git a/Problems/0037.cpp b/Problems/0037.cpp

@@ -0,0 +1,31 @@

class Solution {
bool check(vector<vector<char>> &board, int i, int j, char val) {
for (int x = 0; x < 9; x++)
if (board[x][j] == val) return false;
for (int y = 0; y < 9; y++)
if (board[i][y] == val) return false;
i = (i / 3) * 3, j = (j / 3) * 3;
for (int x = i; x < i + 3; x++)
for (int y = j; y < j + 3; y++)
if (board[x][y] == val) return false;
return true;
}
bool solveSudoku(vector<vector<char>> &board, int i, int j) {
if (i == 9) return true;
if (j == 9) return solveSudoku(board, i + 1, 0);
if (board[i][j] != '.') return solveSudoku(board, i, j + 1);
for (char c = '1'; c <= '9'; c++) {
if (!check(board, i, j, c)) continue;
board[i][j] = c;
if (solveSudoku(board, i, j + 1)) return true;
board[i][j] = '.';
}
return false;
}
public:
void solveSudoku(vector<vector<char>> &board) { solveSudoku(board, 0, 0); }
};

diff --git a/Problems/1011 b/Problems/1011

@@ -1,16 +0,0 @@

class Solution {
public:
int shipWithinDays(vector<int>& weights, int days) {
int left = 0, right = 25000000;
for (int w: weights) left = max(left, w);
while (left < right) {
int mid = (left + right) / 2, need = 1, cur = 0;
for (int i = 0; i < weights.size() && need <= days; cur += weights[i++])
if (cur + weights[i] > mid)
cur = 0, need++;
if (need > days) left = mid + 1;
else right = mid;
}
return left;
}
};

diff --git a/Problems/1011.cpp b/Problems/1011.cpp

@@ -0,0 +1,17 @@

class Solution {
public:
int shipWithinDays(vector<int> &weights, int days) {
int left = 0, right = 25000000;
for (int w : weights) left = max(left, w);
while (left < right) {
int mid = (left + right) / 2, need = 1, cur = 0;
for (int i = 0; i < weights.size() && need <= days; cur += weights[i++])
if (cur + weights[i] > mid) cur = 0, need++;
if (need > days)
left = mid + 1;
else
right = mid;
}
return left;
}
};

diff --git a/README.md b/README.md

@@ -31,6 +31,7 @@ for solving problems.

| 0005 | Medium | [Longest Palindromic Substring](Problems/0005.cpp) |
| 0006 | Medium | [Zigzag Conversion](Problems/0006.cpp) |
| 0007 | Medium | [Reverse Integer](Problems/0007.cpp) |
| 0009 | Easy | [Palindrome Number](Problems/0009.cpp) |
| 0011 | Medium | [Container With Most Water](Problems/0011.cpp) |
| 0012 | Medium | [Integer to Roman](Problems/0012.cpp) |
| 0013 | Easy | [Roman to Integer](Problems/0013.cpp) |

@@ -52,6 +53,7 @@ for solving problems.

| 0034 | Medium | [Find First and Last Position of Element in Sorted Array](Problems/0034.cpp) |
| 0035 | Easy | [Search Insert Position](Problems/0035.cpp) |
| 0036 | Medium | [Valid Sudoku](Problems/0036.cpp) |
| 0037 | Hard | [Sudoku Solver](Problems/0037.cpp) |
| 0039 | Medium | [Combination Sum](Problems/0039.cpp) |
| 0040 | Medium | [Combination Sum II](Problems/0040.cpp) |
| 0042 | Medium | [Trapping Rain Water](Problems/0011.cpp) |

@@ -462,5 +464,4 @@ for solving problems.

| 2477 | Medium | [Minimum Fuel Cost to Report to the Capital](Problems/2477.cpp) |
| 2492 | Medium | [Minimum Score of a Path Between Two Cities](Problems/2492.cpp) |
| 2497 | Medium | [Maximum Star Sum of a Graph](Problems/2497.cpp) |
| 0009 | Easy | [Palindrome Number](Problems/0009.cpp) |