리트코드 24 - Swap Nodes in Pairs (M)
더보기
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode * root = new ListNode(0, head);
auto cur = root;
while(cur->next != nullptr && cur->next->next != nullptr)
{
auto left = cur->next;
auto right = left->next;
cur->next = right;
left->next = right->next;
right->next = left;
cur = left;
}
return root->next;
}
};리트코드 25 - Reverse Nodes in k-Group (H)
더보기
class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
if (k == 1) return head;
ListNode root;
root.next = head;
auto prev = &root;
while(prev->next != nullptr)
{
auto from = prev->next;
auto to = from;
int leftCnt = k - 1;
while(leftCnt-- > 0)
{
to = to->next;
if (to == nullptr) return root.next;
}
Reverse(from, to);
prev->next = to;
prev = from;
}
return root.next;
}
private:
inline static void Reverse(ListNode* from, ListNode * to)
{
ListNode* end = to->next;
ListNode* cur = from;
ListNode* next = cur->next;
while(next!=end)
{
ListNode* new_next = next->next;
next->next = cur;
cur = next;
next = new_next;
}
from->next = end;
}
};리트코드 31 - Next Permutation (M)
더보기
class Solution {
public:
void nextPermutation(std::vector<int>& nums) {
int len = nums.size();
if (len < 2) return;
//step1 뒤에서부터 봤을 때 숫자가 작아지는 지점(target_idx)을 찾는다.
int target_idx = -1;
for(int i= len - 2;i>=0;--i)
{
if(nums[i] < nums[i+1])
{
target_idx = i;
break;
}
}
if (target_idx >= 0)
{
//step2 뒤에서부터 타겟보다 큰 지점(swap_idx)을 찾는다.
int swap_idx;
for (int i = len - 1; i > target_idx; --i)
{
if (nums[i] > nums[target_idx])
{
swap_idx = i;
break;
}
}
//step3 target_idx과 swap_idx의 값을 바꾼다
int temp = nums[target_idx];
nums[target_idx] = nums[swap_idx];
nums[swap_idx] = temp;
}
//step4 target_idx의 뒷 부분 원소 순서를 거꾸로 바꾼다.
int back_len = len - target_idx - 1;
for(int i=1;i<=back_len/2;++i)
{
int left = target_idx + i ;
int right = len - i;
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
}
}
};리트코드 32 - Longest Valid Parentheses (H)
더보기
class Solution {
public:
int longestValidParentheses(string s) {
int max = 0;
stack<int> stk; // 0 = '(' , n = local num of valid parentheses (n>0)
for(auto ch : s)
{
if(ch =='(')
stk.push(0);
else
{
//invalid
if (stk.empty()) continue;
int cur_cnt = 0;
if (stk.top() > 0)
{
cur_cnt += stk.top();
stk.pop();
}
//invalid
if (stk.empty()) continue;
stk.pop();
cur_cnt += 2;
if(!stk.empty() && stk.top() > 0)
{
cur_cnt += stk.top();
stk.pop();
}
stk.push(cur_cnt);
if (max < cur_cnt)
max = cur_cnt;
}
}
return max;
}
};리트코드 33 - Search in Rotated Sorted Array (M)
더보기
int search(vector<int>& nums, int target) {
int lo = 0, hi = int(nums.size()) - 1;
while (lo < hi) {
int mid = (lo + hi) / 2;
if ((nums[0] > target) ^ (nums[0] > nums[mid]) ^ (target > nums[mid]))
lo = mid + 1;
else
hi = mid;
}
return lo == hi && nums[lo] == target ? lo : -1;
}리트코드 34 - Find First and Last Position of… (M)
더보기
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int left, right, mid;
left = 0;
right = nums.size() - 1;
int start = -1;
int end = -1;
while(left<=right && start < 0)
{
mid = (left + right) / 2;
if (nums[mid] == target)
{
if (mid > 0)
{
if (nums[mid - 1] < nums[mid])
start = mid;
else
right = mid - 1;
}
else
{
start = 0;
}
}
else if (nums[mid] < target)
left = mid + 1;
else
right = mid - 1;
}
if(start == -1) return vector<int> {-1, -1};
left = start;
right = nums.size() - 1;
while(left<=right && end < 0)
{
mid = (left + right) / 2;
if (nums[mid] == target)
{
if (mid < nums.size() - 1)
{
if (nums[mid + 1] > nums[mid])
end = mid;
else
left = mid + 1;
}
else
{
end = nums.size() -1 ;
}
}
else if (nums[mid] < target)
left = mid + 1;
else
right = mid - 1;
}
return vector<int> {start, end};
}
};리트코드 35 - Search Insert Position (E)
더보기
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int left = 0;
int right = nums.size() -1;
if(target <= nums[0] ) return 0;
if(nums[right] < target ) return right+1;
while(left <= right)
{
int mid = (left+right)/2;
if(nums[mid] < target)
left = mid+1;
else if(nums[mid > target])
right = mid-1;
else
return mid;
}
return left;
}
};리트코드 36 - Valid Sudoku (M)
더보기
class Solution {
public:
bool isValidSudoku(vector<vector<char>>& board) {
vector<vector<bool>> rows(9, vector<bool>(9));
vector<vector<bool>> columns(9, vector<bool>(9));
vector<vector<bool>> cells(9, vector<bool>(9));
for(size_t i=0;i<board.size();++i)
{
for(size_t j=0;j<board[0].size();++j)
{
char ch = board[i][j];
if (ch == '.')
continue;
int val = ch - '0' - 1;
if (rows[i][val] || columns[j][val]) return false;
int cell_idx = (i / 3) * 3 + j / 3;
if (cells[cell_idx][val]) return false;
rows[i][val] = true;
columns[j][val] = true;
cells[cell_idx][val] = true;
}
}
return true;
}
};리트코드 37 - Sudoku Solver (H)
더보기
#include <vector>
#include <unordered_set>
using namespace std;
class Solution {
public:
void solveSudoku(vector<vector<char>>& board) {
vector<vector<unordered_set<char>>> candidates(9, vector <unordered_set<char>>(9));
vector<unordered_set<char>> rows(9);
vector<unordered_set<char>> columns(9);
vector<unordered_set<char>> cells(9);
for (size_t i = 0; i < board.size(); ++i)
{
for (size_t j = 0; j < board[0].size(); ++j)
{
char ch = board[i][j];
if (ch == '.')
continue;
write(i, j, ch, rows, columns, cells);
}
}
setCandidates(board, candidates, rows, columns, cells);
while(flushCandidates(board,candidates,rows,columns,cells))
setCandidates(board, candidates, rows, columns, cells);
tryWrite(0, board, candidates, rows, columns, cells);
}
private:
static void setCandidates(vector<vector<char>>& board, vector<vector<unordered_set<char>>>& candidates, vector<unordered_set<char>>& rows, vector<unordered_set<char>>& columns, vector<unordered_set<char>>& cells)
{
for(int i=0;i<board.size();++i)
for(int j=0;j<board.size();++j)
candidates[i][j].clear();
for (int i = 0; i < board.size(); ++i)
{
for (int j = 0; j < board[0].size(); ++j)
{
char ch = board[i][j];
if (ch != '.') continue;
for (char val = '1'; val <= '9'; ++val)
{
if (!canWrite(i, j, val, rows, columns, cells)) continue;
candidates[i][j].emplace(val);
}
}
}
}
static bool flushCandidates(vector<vector<char>>& board, vector<vector<unordered_set<char>>>& candidates, vector<unordered_set<char>>& rows, vector<unordered_set<char>>& columns, vector<unordered_set<char>>& cells)
{
bool updated = false;
for (int i = 0; i < board.size(); ++i)
{
for (int j = 0; j < board[0].size(); ++j)
{
char ch = board[i][j];
if (ch != '.') continue;
if (candidates[i][j].size() != 1) continue;
char val = '.';
for (auto v : candidates[i][j]) val = v;
write(i, j, val, board, rows, columns, cells);
updated = true;
}
}
return updated;
}
static bool tryWrite(int idx, vector<vector<char>>& board, vector<vector<unordered_set<char>>>& candidates, vector<unordered_set<char>>& rows, vector<unordered_set<char>>& columns, vector<unordered_set<char>>& cells)
{
int i = idx / 9;
if (i >= 9) return true; //다 썻으니 성공
int j = idx % 9;
if (board[i][j] != '.')
return tryWrite(idx + 1, board, candidates, rows, columns, cells);
for (auto val : candidates[i][j])
{
if (false == canWrite(i, j, val, rows, columns, cells)) continue;
write(i, j, val, board, rows, columns, cells);
auto ret = tryWrite(idx + 1, board, candidates, rows, columns, cells);
if (ret) return true;
erase(i, j, val, board, rows, columns, cells);
}
//candidate가 없었음.. 리턴 false
return false;
}
static bool canWrite(int i, int j, char val, vector<unordered_set<char>>& rows, vector<unordered_set<char>>& columns, vector<unordered_set<char>>& cells)
{
if (rows[i].find(val) != rows[i].end()) return false;
if (columns[j].find(val) != columns[j].end()) return false;
const int ci = getCellIdx(i, j);
if (cells[ci].find(val) != cells[ci].end()) return false;
return true;
}
static void write(int i, int j, char val, vector<vector<char>>& board, vector<unordered_set<char>>& rows, vector<unordered_set<char>>& columns, vector<unordered_set<char>>& cells)
{
board[i][j] = val;
write(i, j, val, rows, columns, cells);
}
static void write(int i, int j, char val, vector<unordered_set<char>>& rows, vector<unordered_set<char>>& columns, vector<unordered_set<char>>& cells)
{
rows[i].emplace(val);
columns[j].emplace(val);
cells[getCellIdx(i, j)].emplace(val);
}
static void erase(int i, int j, char val, vector<vector<char>>& board, vector<unordered_set<char>>& rows, vector<unordered_set<char>>& columns, vector<unordered_set<char>>& cells)
{
board[i][j] = '.';
erase(i, j, val, rows, columns, cells);
}
static void erase(int i, int j, char val, vector<unordered_set<char>>& rows, vector<unordered_set<char>>& columns, vector<unordered_set<char>>& cells)
{
rows[i].erase(val);
columns[j].erase(val);
cells[getCellIdx(i, j)].erase(val);
}
static int getCellIdx(int i, int j)
{
return (i / 3) * 3 + j / 3;
}
};리트코드 39 - Combination Sum (M)
더보기
class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> ret;
vector<int> current;
sort(candidates.begin(), candidates.end(), greater<int>());
search(0, target, current, candidates, ret);
return ret;
}
//dfs
void search(int startIdx, int left, vector<int>& current, const vector<int>& candidates, vector<vector<int>>& ans)
{
if(left == 0)
{
ans.emplace_back(vector<int>(current));
return;
}
if (startIdx >= candidates.size()) return;
const int num = candidates[startIdx];
int num_add = 0;
while(left >= 0)
{
search(startIdx + 1, left, current, candidates, ans);
current.emplace_back(num);
++num_add;
left -= num;
}
while(num_add-- > 0)
current.erase(current.cend() - 1);
}
};