리트코드 64 - Minimum Path Sum (M)
더보기
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int m = grid.size();
int n = grid[0].size();
for (int i = 1; i < m; ++i)
grid[i][0] = grid[i - 1][0] + grid[i][0];
for (int j = 1; j < n; ++j)
grid[0][j] = grid[0][j - 1] + grid[0][j];
for(int i =1; i< m;++i)
for(int j=1;j<n;++j)
grid[i][j] = grid[i - 1][j] < grid[i][j - 1] ? grid[i - 1][j] + grid[i][j] : grid[i][j - 1] + grid[i][j];
return grid[m - 1][n - 1];
}
};
더보기
class Solution {
public:
string simplifyPath(string path) {
string ans;
int s;
s = 0;
for(size_t i=1;i<path.size();++i)
{
if(path[i]=='/')
{
Add(path, ans, s + 1, i-1);
s = i;
}
if(i == path.size() - 1)
{
Add(path, ans, s + 1, i);
s = i;
}
}
if (ans.empty())
ans.push_back('/');
return ans;
}
private:
void Add(const string& path, string& ans, int s, int e)
{
auto diff = e - s + 1;
if (diff <= 0) return;
if( diff == 1)
{
if (path[s] == '.') return;
}
if(diff == 2)
{
if(path[s] == '.' && path[e] == '.')
{
while (ans.size() > 1 && ans[ans.size() - 1] != '/')
ans.pop_back();
if(!ans.empty() && ans[ans.size()-1] == '/')
ans.pop_back();
return;
}
}
ans.push_back('/');
for (int i = s; i <= e; ++i)
ans.push_back(path[i]);
}
};
더보기
class Solution {
public:
int minDistance(string word1, string word2) {
string& str1 = word1.length() > word2.length() ? word1 : word2;
string& str2 = word1.length() > word2.length() ? word2 : word1;
vector<int> dp(str2.length() + 1);
for (int i = 0; i < dp.size(); ++i)
dp[i] = i;
for(int i=0;i<str1.length();++i)
{
int diag = i;
dp[0] = i+1;
for(int j=0;j<str2.length();++j)
{
int di = j + 1;
int oldValue = dp[di];
if(str1[i]==str2[j])
{
dp[di] = diag;
}
else
{
dp[di] = min(diag, dp[di], dp[di - 1]) + 1; //왼쪽이랑 대각선 위랑 구분이 안 된다. 대각선 위만 캐싱하면 된다.
}
diag = oldValue;
}
}
return dp[str2.length()];
}
private :
static int min(int a, int b, int c)
{
int min = a;
if (b < min) min = b;
if (c < min) min = c;
return min;
}
};
리트코드 73 - Set Matrix Zeroes (M)
더보기
//idea : constant space만 사용하기 위해서, 첫번째 행/열이 아닌 셀의 값이 0이면 첫번째 행/열에 "0"이라는 값을 투사함.
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
const int numRow = matrix[0].size();
const int numCol = matrix.size();
//첫번째 행/열이 0으로 채워져야 하는지를 체크한다.
bool isFirstRowZero = false;
for(int r=0;r< numRow;++r)
{
if(matrix[0][r] == 0)
{
isFirstRowZero = true;
break;
}
}
bool isFirstColumnZero = false;
for(int c=0;c<numCol;++c)
{
if(matrix[c][0] == 0)
{
isFirstColumnZero = true;
break;
}
}
//0을 만나면 첫번째 행/열에 0이라는 값을 투사한다.
for(int c=1;c<numCol;++c)
{
for(int r=1;r<numRow;++r)
{
if(matrix[c][r] == 0)
{
matrix[c][0] = 0;
matrix[0][r] = 0;
}
}
}
//첫번째 행/열이 0이면 해당 행/열을 0으로 채운다. (첫 행/열을 제외하고)
for(int c=1;c<numCol;++c)
{
if(matrix[c][0] == 0)
{
for (int r = 1; r < numRow; ++r)
matrix[c][r] = 0;
}
}
for(int r=1;r<numRow;++r)
{
if(matrix[0][r] ==0)
{
for (int c = 1; c < numCol; ++c)
matrix[c][r] = 0;
}
}
//첫 행/열이 0으로 채워져야 하는지 여부를 반영한다.
if(isFirstColumnZero)
{
for (int c = 0; c < numCol; ++c)
matrix[c][0] = 0;
}
if(isFirstRowZero)
{
for (int r = 0; r < numRow; ++r)
matrix[0][r] = 0;
}
}
};
리트코드 74 - Search a 2D Matrix (M)
더보기
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
if (matrix[0][0] > target) return false;
int row = 0;
if(matrix.size() >= 2)
{
int l = 0;
int r = matrix.size() - 1;
while(l<r)
{
int mid = (l + r + 1) / 2;
if (matrix[mid][0] < target)
{
l = mid;
}
else if (matrix[mid][0] > target)
{
r = mid - 1;
}
else
return true;
}
//l=r
row = l;
}
if (matrix[row][0] == target) return true;
if (matrix[row].size() >= 2)
{
int l = 0;
int r = matrix[row].size() - 1;
while (l < r)
{
int mid = (l + r + 1) / 2;
if (matrix[row][mid] < target)
{
l = mid;
}
else if (matrix[row][mid] > target)
{
r = mid - 1;
}
else
return true;
}
}
else
{
return matrix[row][0] == target;
}
return false;
}
};
더보기
class Solution {
public:
void sortColors(vector<int>& nums) {
int num0 = 0;
int num1 = 0;
for(auto& num : nums)
{
if(num == 0) ++num0;
else if(num == 1) ++num1;
}
for(int i=0;i<num0;++i)
nums[i]=0;
for(int i=num0; i<num0+num1;++i)
nums[i]=1;
for(int i=num0+num1; i<nums.size();++i)
nums[i]=2;
}
};
더보기
class Solution {
public:
vector<vector<int>> combine(int n, int k) {
const int size = nCr(n, k);
vector<vector<int>> ret;
ret.reserve(size);
vector<int> buffer(k);
combination(1, n, k, 0, ret, buffer);
return ret;
}
private:
static void combination(int start, int n, int k, int pos, vector<vector<int>>& container, vector<int>& buffer)
{
if (pos == k)
{
container.emplace_back(buffer);
return;
}
int maxVal = n - k + 1 + pos;
for (int i = start; i <= maxVal; ++i)
{
buffer[pos] = i;
combination(i + 1, n, k, pos + 1, container, buffer);
}
}
static int nCr(int n, int r)
{
if (r > n - r)
r = n - r;
long long numerator = 1;
long long denominator = 1;
for (int i = 0; i < r; ++i)
numerator *= n - i;
for (int i = 2; i <= r; ++i)
denominator *= i;
return static_cast<int>(numerator / denominator);
}
};
리트코드 76 - Minimum Window Substring (H)
더보기
class Solution {
public:
string minWindow(string s, string t) {
int m = s.length();
int n = t.length();
int leftMatch = n;
unordered_map<char, int> t_map;
for (auto c : t)
++t_map[c];
int start = 0;
int min = m + 1;
int left = 0;
for (int right = 0; right < m; ++right)
{
{
char ch = s[right];
if (t_map.find(ch) == t_map.end()) continue;
if (--t_map[ch] >= 0) --leftMatch;
}
if (leftMatch == 0)
{
for(;left <= right; ++left)
{
int localMin = right - left;
if (localMin < min)
{
min = localMin;
start = left;
}
char ch = s[left];
if (t_map.find(ch) == t_map.end()) continue;
if (++t_map[ch] > 0)
{
++left;
++leftMatch;
break;
}
}
}
}
if (min == m + 1)
return "";
return s.substr(start, min+1);
}
};
더보기
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> ans;
int cap = 1 << nums.size();
ans.reserve(cap);
vector<int> buffer;
buffer.reserve(nums.size());
AddSubsets(nums, 0, buffer, ans);
return ans;
}
private:
void AddSubsets(vector<int>& nums, int idx, vector<int>& buffer, vector<vector<int>>& answer)
{
if (idx >= nums.size())
{
answer.emplace_back(buffer);
return;
}
AddSubsets(nums, idx + 1, buffer, answer);
buffer.emplace_back(nums[idx]);
AddSubsets(nums, idx + 1, buffer, answer);
buffer.pop_back();
}
};
더보기
class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
for (int i = 0; i < board.size(); ++i)
for (int j = 0; j < board[0].size(); ++j)
if (search(board, word, 0, i, j)) return true;
return false;
}
private:
bool search(vector<vector<char>>& board, string& word, int idx, int i, int j)
{
if (i < 0 || j < 0 || i >= board.size() || j >= board[0].size()) return false;
if (word[idx] != board[i][j]) return false;
if (idx == word.length() - 1) return true; //answer
board[i][j] = '*'; //visited
if (search(board, word, idx + 1, i - 1, j)) return true;
if (search(board, word, idx + 1, i + 1, j)) return true;
if (search(board, word, idx + 1, i, j - 1)) return true;
if (search(board, word, idx + 1, i, j + 1)) return true;
board[i][j] = word[idx];
return false;
}
};
리트코드 82 - Remove Duplicates From Sorted List 2 (M)
더보기
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
ListNode* ans = new ListNode();
auto cur = ans;
auto iter = head;
int last = -99999999;
while (iter != nullptr)
{
if (iter->val != last && (iter->next == nullptr || iter->val != iter->next->val))
{
cur->next = iter;
cur = cur->next;
iter = iter->next;
cur->next = nullptr;
}
else
{
last = iter->val;
iter = iter->next;
}
}
return ans->next;
}
};
리트코드 84 - Largest Rectangle in Histogram (H)
더보기
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
stack<int> stk;
int max = 0;
for(size_t i = 0;i < heights.size() ; ++i)
{
CheckMaxArea(stk, heights, i, heights[i], max);
stk.push(i);
}
CheckMaxArea(stk, heights, heights.size(), 0, max);
return max;
}
private :
static void CheckMaxArea(stack<int>& stk, vector<int>& heights, int i, int curHeight, int& max)
{
while (!stk.empty())
{
auto top_height = heights[stk.top()];
if (top_height == curHeight)
stk.pop();
else if (top_height > curHeight)
{
stk.pop();
const int width = stk.empty() ? i : i - 1 - stk.top();
const int area = width * top_height;
if (area > max)
max = area;
}
else
break;
}
}
};
리트코드 85 - Maximal Rectangle (H)
더보기
class Solution {
public:
int maximalRectangle(vector<vector<char>>& matrix) {
int ans = 0;
vector<int> heights(matrix[0].size() + 1);
for(const auto& column : matrix)
{
for(size_t i=0;i< matrix[0].size();++i)
heights[i] = column[i] == '0' ? 0 : heights[i] + 1;
stack<int> stk;
for(size_t i=0;i < heights.size();++i)
{
while (!stk.empty() && heights[stk.top()] > heights[i])
{
int top = stk.top(); stk.pop();
auto rect = heights[top] * (stk.empty() ? i : i - 1 - stk.top());
ans = max(ans, rect);
}
stk.push(i);
}
}
return ans;
}
private :
static int max(int a, int b) { return a > b ? a : b; }
};