LeetCode
G
- Add Two Numbers
struct ListNode {
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
ListNode *
addTwoNumbers(ListNode *l1, ListNode *l2) {
ListNode *head = new ListNode(0);
ListNode *curr_1 = l1;
ListNode *curr_2 = l2;
int carry = 0;
ListNode *curr_node = head;
while (curr_1 || curr_2 || carry) {
int curr_1_val = curr_1 ? curr_1->val : 0;
int curr_2_val = curr_2 ? curr_2->val : 0;
int new_val = (curr_1_val + curr_2_val + carry) % 10;
carry = (curr_1_val + curr_2_val + carry) / 10;
ListNode *new_node = new ListNode(new_val);
curr_node->next = new_node;
curr_node = curr_node->next;
curr_1 = curr_1 ? curr_1->next : nullptr;
curr_2 = curr_2 ? curr_2->next : nullptr;
}
ListNode *res = head->next;
return res;
}
};
- Longest Substring Without Repeating Characters
class Solution {
public:
int
lengthOfLongestSubstring(std::string s) {
int N = 1000;
int len = s.length();
bool repeated[N];
int repeated_pos[N];
memset(repeated, 0, sizeof(repeated));
int max_len = 0;
int head = 0;
int tail = 0;
for (int i = 0; i < len; i++) {
if (!(repeated[s[i]] && repeated_pos[s[i]] >= head)) {
tail += 1;
} else {
head = repeated_pos[s[i]] + 1;
tail += 1;
}
repeated[s[i]] = 1;
repeated_pos[s[i]] = i;
int curr_len = tail - head;
if (curr_len > max_len) {
max_len = curr_len;
}
std::cout << head << " " << tail << std::endl;
}
return max_len;
}
};
- Longest Palindromic Substring
class Solution {
public:
string longestPalindrome(string s) {
int n = s.length();
int f[n][n];
memset(f, 0, sizeof(f));
int max_len = 1;
int max_start_index = 0;
int max_end_index = 0;
std::string res = "";
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
f[i][i] = 0;
}
}
for (int i = 0; i < n; i++) {
f[i][i] = 1;
for (int j = 0; j < i; j++) {
if (s[i] == s[j] && (i - j <= 2 || f[i - 1][j + 1])) {
f[i][j] = 1;
if (i - j + 1 > max_len) {
max_len = i - j + 1;
max_start_index = j;
max_end_index = i;
}
}
}
}
for (int k = max_start_index; k < max_end_index + 1; k++) {
res += s[k];
}
return res;
}
};
- Zigzag Conversion
class Solution {
public:
string convert(string s, int numRows) {
if (numRows == 1) {
return s;
}
int n = s.length();
std::string result[numRows];
int direction = 1;
for (int i = 0; i < numRows; i++) {
result[i] = "";
}
int curr_row = 0;
int curr_index = 0;
while (curr_index != n) {
result[curr_row] += s[curr_index];
if ((curr_row + direction == numRows || curr_row + direction == -1) && curr_index != 0) {
direction *= -1;
}
curr_row += direction;
curr_index++;
}
std::string res = "";
for (int i = 0; i < numRows; i++) {
res += result[i];
}
return res;
}
};
- Reverse Integer
class Solution {
public:
int
reverse(int x) {
int n = std::to_string(abs(x)).length();
int res = 0;
int dv = 10;
int mul = 1;
for (int i = 0; i < n - 1; i++) {
mul *= 10;
}
while (x != 0) {
if (x > 0 && (x % dv) * (mul / 10) > INT32_MAX / 10) {
return 0;
}
if (x < 0 && (x % dv) * (mul / 10) < INT32_MIN / 10) {
return 0;
}
if (x > 0 && INT32_MAX - res < (x % dv) * mul) {
return 0;
}
if (x < 0 && INT32_MIN - res > (x % dv) * mul) {
return 0;
}
res += (x % dv) * mul;
x = x / dv;
mul /= 10;
}
return res;
}
};
- String to Integer
class Solution {
public:
int
myAtoi(string s) {
int n = s.length();
int digits = 0;
int is_sign_read = 0;
bool is_number_read = 0;
bool is_lead_read = 0;
int result_arr[100];
int result_len = 0;
int result = 0;
for (int i = 0; i < n; i++) {
if (s[i] == '-' || s[i] == '+' || s[i] == ' ') {
if (is_sign_read || is_lead_read)
break;
if (s[i] == '+') {
is_sign_read = 1;
} else if (s[i] == '-') {
is_sign_read = -1;
}
} else if (s[i] >= '0' && s[i] <= '9') {
if (is_number_read || s[i] != '0') {
is_sign_read = is_sign_read == 0 ? 1 : is_sign_read;
result_arr[result_len++] = s[i] - 48;
is_number_read = 1;
}
is_lead_read = 1;
} else {
if (is_sign_read || is_number_read) {
break;
}
return 0;
}
}
int mul = 1;
for (int i = result_len - 1; i >= 0; i--) {
if (is_sign_read == 1 && result_arr[i] * (mul / 10) > INT32_MAX / 10) {
return INT32_MAX;
}
if (is_sign_read == -1 && -1 * result_arr[i] * (mul / 10) < INT32_MIN / 10) {
std::cout << result << std::endl;
return INT32_MIN;
}
if (is_sign_read == 1 && INT32_MAX - result < result_arr[i] * mul) {
return INT32_MAX;
}
if (is_sign_read == -1 && INT32_MIN - result > -1 * result_arr[i] * mul) {
std::cout << result << std::endl;
return INT32_MIN;
}
result += is_sign_read * result_arr[i] * mul;
if (i != 0 && is_sign_read == 1 && mul > INT32_MAX / 10) {
return INT32_MAX;
} else if (i != 0 && is_sign_read == -1 && -1 * mul < INT32_MIN / 10) {
return INT32_MIN;
}
if (i != 0) {
mul *= 10;
}
}
return result;
}
};
optimized:
class Solution {
public:
int myAtoi(string s) {
int len = s.size();
double num = 0;
int i=0;
while(s[i] == ' '){
i++;
}
bool positive = s[i] == '+';
bool negative = s[i] == '-';
positive == true ? i++ : i;
negative == true ? i++ : i;
while(i < len && s[i] >= '0' && s[i] <= '9'){
num = num*10 + (s[i]-'0');
i++;
}
num = negative ? -num : num;
cout<<num<<endl;
num = (num > INT_MAX) ? INT_MAX : num;
num = (num < INT_MIN) ? INT_MIN : num;
cout<<num<<endl;
return int(num);
}
};
- Regular Expression Matching
Tag: DP, Recursive
struct hash_pair {
template <class T1, class T2>
size_t
operator()(const pair<T1, T2> &p) const {
auto hash1 = hash<T1>{}(p.first);
auto hash2 = hash<T2>{}(p.second);
if (hash1 != hash2) {
return hash1 ^ hash2;
}
// If hash1 == hash2, their XOR is zero.
return hash1;
}
};
class Solution {
public:
bool
isMatch(string s, string p) {
static unordered_map<pair<string, string>, int, hash_pair> mem;
if (mem.find(make_pair(s, p)) != mem.end()) {
return mem[make_pair(s, p)];
}
int n_s = s.length();
int n_p = p.length();
if (n_p == 1 && n_s == 1) {
if (p[0] == s[0] || p[0] == '.') {
mem[make_pair(s, p)] = 1;
return 1;
} else {
mem[make_pair(s, p)] = 0;
return 0;
}
} else if (n_p > 1 && n_s > 0) {
if (p[1] == '*') {
if (p[0] == s[0] || p[0] == '.') {
int value = max(max(isMatch(s.substr(1, n_s - 1), p),
isMatch(s.substr(1, n_s - 1), p.substr(2, n_p - 2))),
isMatch(s, p.substr(2, n_p - 2)));
mem[make_pair(s, p)] = value;
return value;
} else {
int value = isMatch(s, p.substr(2, n_p - 2));
mem[make_pair(s, p)] = value;
return value;
}
} else {
if (p[0] == s[0] || p[0] == '.') {
int value = isMatch(s.substr(1, n_s - 1), p.substr(1, n_p - 1));
mem[make_pair(s, p)] = value;
return value;
} else {
mem[make_pair(s, p)] = 0;
return 0;
}
}
} else if (n_p > 1 && n_s == 0) {
if (p[1] == '*') {
int value = isMatch("", p.substr(2, n_p - 2));
mem[make_pair(s, p)] = value;
return value;
} else {
mem[make_pair(s, p)] = 0;
return 0;
}
} else if (n_p == 0 && n_s == 0) {
mem[make_pair(s, p)] = 1;
return 1;
} else {
mem[make_pair(s, p)] = 0;
return 0;
}
}
bool
isMatchDP(string s, string p) {
int n = s.length();
int m = p.length();
bool dp[n + 1][m + 1];
memset(dp, false, sizeof(dp));
dp[0][0] = 1;
for (int i = 0; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (p[j - 1] == '*') {
dp[i][j] = dp[i][j - 2]
|| (i > 0 && (p[j - 2] == s[i - 1] || p[j - 2] == '.')
&& (dp[i - 1][j - 2] || dp[i - 1][j]));
} else {
dp[i][j] = i > 0 && (p[j - 1] == s[i - 1] || p[j - 1] == '.') && dp[i - 1][j - 1];
}
}
}
std::cout << dp[1][2] << std::endl;
return dp[n][m];
}
};
- Container With Most Water
Tag: Two pointers, Greedy
class Solution {
public:
int
maxArea(vector<int> &height) {
int n = height.size();
int left = 0;
int right = n - 1;
int result = min(height[left], height[right]) * (right - left);
// int result = 0;
while (left < right) {
int value = min(height[left], height[right]) * (right - left);
if (value > result) {
result = value;
}
if (height[right] < height[left]) {
right -= 1;
} else {
left += 1;
}
}
return result;
}
};
- Integer to Roman
class Solution {
public:
string intToRoman(int num) {
std::string digits[] = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};
std::string tens[] = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
std::string hrds[] = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
std::string thud[] = {"", "M", "MM", "MMM"};
std::string result =
thud[num / 1000] + hrds[num % 1000 / 100] + tens[num % 100 / 10] + digits[num % 10];
return result;
}
};
- 3 Sum
Tag: Two pointers
class Solution {
public:
vector<vector<int>>
threeSum(vector<int> &nums) {
std::sort(nums.begin(), nums.end());
int n = nums.size();
vector<vector<int>> result;
for (int i = 0; i < n - 2; i++) {
if (i != 0) {
if (nums[i] == nums[i - 1]) {
continue;
}
}
int sum = 0 - nums[i];
int left = i + 1;
int right = n - 1;
while (left < right) {
if (nums[left] + nums[right] == sum) {
result.push_back({nums[i], nums[left++], nums[right--]});
while (left < right) {
if (nums[left] == nums[left - 1]) {
left++;
} else if (nums[right] == nums[right + 1]) {
right--;
} else {
break;
}
}
} else if (nums[left] + nums[right] < sum) {
left++;
} else {
right--;
}
}
}
return result;
}
};
- 3 Sum Closest
class Solution {
public:
int
threeSumClosest(vector<int> &nums, int target) {
std::sort(nums.begin(), nums.end());
int n = nums.size();
int diff = INT32_MAX;
int result = INT32_MAX;
for (auto &e : nums) {
std::cout << e << " ";
}
std::cout << std::endl;
for (int i = 0; i < n - 2; i++) {
if (i != 0) {
if (nums[i] == nums[i - 1]) {
continue;
}
}
int sum = target - nums[i];
int left = i + 1;
int right = n - 1;
while (left < right) {
int curr_diff = abs(sum - nums[left] - nums[right]);
if (curr_diff < diff) {
spdlog::info("{} {} {} {}", i, left, right, nums[i] + nums[left] + nums[right]);
diff = curr_diff;
result = nums[i] + nums[left] + nums[right];
}
if (sum - nums[left] - nums[right] > 0) {
left++;
} else if (sum - nums[left] - nums[right] < 0) {
right--;
} else {
break;
}
}
}
return result;
}
};
- Letter Combination of a Phone Number
void
back_trace(std::string s, std::string path_str, vector<std::string> &results,
unordered_map<int, vector<char>> &table) {
if (s.empty() && !path_str.empty()) {
results.push_back(path_str);
return;
}
char curr_num = s[0];
int n = s.length();
for (auto &letter : table[curr_num]) {
back_trace(s.substr(1, n - 1), path_str + letter, results, table);
}
}
class Solution {
public:
vector<string>
letterCombinations(string digits) {
unordered_map<int, vector<char>> table;
char curr_l = 'a';
for (int i = '2'; i <= '9'; i++) {
table[i] = {};
if (i != '7' && i != '9') {
for (int j = 0; j < 3; j++) {
table[i].push_back(curr_l++);
}
} else {
for (int j = 0; j < 4; j++) {
table[i].push_back(curr_l++);
}
}
}
vector<std::string> results;
back_trace(digits, "", results, table);
return results;
}
};
- Remove Nth Node From End of List
struct ListNode {
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
ListNode *
removeNthFromEnd(ListNode *head, int n) {
int delay = n - 1;
ListNode *curr_node = head;
ListNode *curr_node_delay = head;
ListNode *prev = head;
while (curr_node->next) {
while (delay > 0) {
curr_node = curr_node->next;
delay--;
}
if (!curr_node->next) {
break;
}
curr_node = curr_node->next;
prev = curr_node_delay;
curr_node_delay = curr_node_delay->next;
}
if (prev == curr_node_delay && curr_node_delay == curr_node) {
return nullptr;
} else if (prev != curr_node_delay && curr_node_delay == curr_node) {
prev->next = nullptr;
} else if (prev == curr_node_delay && curr_node_delay != curr_node) {
return prev->next;
} else {
prev->next = curr_node_delay->next;
}
return head;
}
};
optimized
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummy = new ListNode(0);
dummy->next = head;
ListNode* first = dummy;
ListNode* second = dummy;
for (int i = 0; i <= n; ++i) {
first = first->next;
}
while (first != nullptr) {
first = first->next;
second = second->next;
}
ListNode* temp = second->next;
second->next = second->next->next;
delete temp;
return dummy->next;
}
};
- Generate Parentheses
void
generate_parentheses(int left, int right, int n, std::vector<std::string> &results,
std::string pairs) {
if (pairs.length() == 2 * n) {
if (left == right) {
results.push_back(pairs);
}
return;
}
if (left < n) {
generate_parentheses(left + 1, right, n, results, pairs + '(');
}
if (left > right) {
generate_parentheses(left, right + 1, n, results, pairs + ')');
}
}
class Solution {
public:
vector<string>
generateParenthesis(int n) {
std::vector<std::string> results;
generate_parentheses(0, 0, n, results, "");
return results;
}
};
- Swap Node In Pairs
class Solution {
public:
ListNode *
swapPairs(ListNode *head) {
if (!head) {
return head;
}
if (head->next) {
ListNode *tmp = head->next->next;
ListNode *new_head = head->next;
head->next->next = head;
head->next = swapPairs(tmp);
return new_head;
} else {
return head;
}
}
};
- Reverse Nodes in k-Group
ListNode *
reverseList(ListNode *prev_tail, ListNode *node, int k, int max_len) {
if (!prev_tail || k == max_len) {
prev_tail = node;
}
if (k == 1) {
if (prev_tail) {
prev_tail->next = node->next;
}
return node;
} else if (!node->next) {
return k == max_len ? node : nullptr;
} else {
ListNode *tmp = node->next;
ListNode *head = reverseList(prev_tail, tmp, k - 1, max_len);
if (!head) {
return k == max_len ? node : nullptr;
}
if (prev_tail->next && k == max_len) {
prev_tail->next = reverseList(prev_tail, prev_tail->next, k, max_len);
} else {
node->next = nullptr;
}
tmp->next = node;
return head;
}
}
class Solution {
public:
ListNode *
reverseKGroup(ListNode *head, int k) {
ListNode *new_head;
new_head = reverseList(nullptr, head, k, k);
std::cout << std::endl;
return new_head;
}
};
iteration
ListNode *
reverseList(ListNode *node, int k) {
int group_len = k;
ListNode *curr = node;
ListNode *prev = nullptr;
ListNode *next = node->next;
ListNode *res = nullptr;
ListNode *tail = curr;
ListNode *next_tail = nullptr;
bool end = 0;
while (curr) {
while (curr && k >= 1) {
if (k == group_len) {
next_tail = curr;
}
next = curr->next;
if (curr) {
curr->next = prev;
prev = curr;
curr = next;
k--;
}
}
if (!res) {
res = prev;
} else {
tail->next = prev;
}
if (next) {
k = group_len;
curr = next;
tail = next_tail;
} else {
next = prev;
}
prev = nullptr;
}
if (k) {
curr = next;
prev = nullptr;
while (curr) {
ListNode *next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
tail->next = prev;
}
return res;
}
Contest
- Find the Minimum Cost Array Permutation
Tag: State Compression, DP
class Solution {
public:
vector<int>
findPermutation(vector<int> &nums) {
int n = nums.size();
vector<vector<pair<int, int>>> dp(n, vector<pair<int, int>>(1 << (n - 1)));
for (int i = 0; i < n; i++) {
for (int j = 0; j < 1 << (n - 1); j++) {
dp[i][j] = make_pair(-1, INT32_MAX);
}
}
for (int i = 1; i < n; i++) {
dp[i][1 << (i - 1)] = make_pair(0, abs(i - nums[0]));
}
for (int j = 0; j < 1 << (n - 1); j++) {
for (int i = 1; i < n; i++) {
if (j & (1 << (i - 1))) {
for (int prev = 1; prev < n; prev++) {
if (i == prev) {
continue;
}
if (j & (1 << (prev - 1))) {
if (dp[i][j].second
> dp[prev][j ^ (1 << (i - 1))].second + abs(i - nums[prev])) {
dp[i][j] = make_pair(prev, dp[prev][j ^ (1 << (i - 1))].second
+ abs(i - nums[prev]));
}
}
}
}
}
}
int start = -1;
int min_v = INT32_MAX;
int bit_len = (1 << (n - 1)) - 1;
for (int i = 1; i < n; i++) {
if (min_v > dp[i][bit_len].second + abs(-nums[i])) {
start = i;
min_v = dp[i][bit_len].second + abs(-nums[i]);
}
}
int prev = start;
vector<int> res;
res.push_back(0);
int mask = (1 << (n - 1)) - 1;
while (prev != 0) {
int tmp = prev;
res.push_back(prev);
prev = dp[prev][mask].first;
mask = mask ^ (1 << (tmp - 1));
}
return res;
}
};
- Next Permutation
class Solution {
public:
void
nextPermutation(vector<int> &nums) {
int n = nums.size();
if (n == 1) {
return;
}
int right = n - 2;
while (right >= 0) {
if (nums[right] < nums[right + 1]) {
break;
}
right--;
}
if (right == -1) {
std::sort(nums.begin(), nums.end());
return;
}
int next_large_num = INT32_MAX;
int next_large_index = right;
for (int i = right + 1; i < n; i++) {
if (nums[i] < INT32_MAX && nums[i] > nums[right]) {
next_large_num = nums[i];
next_large_index = i;
}
}
int tmp = nums[right];
nums[right] = nums[next_large_index];
nums[next_large_index] = tmp;
std::sort(nums.begin() + right + 1, nums.end());
}
};
- Substring with Concatenation of All Words
Tag: Hash Map
class Solution {
public:
vector<int>
findSubstring(string s, vector<string> &words) {
int n = s.length();
int word_num = words.size();
int word_len = words[0].length();
vector<int> result;
unordered_map<string, int> word_records;
for (auto &word : words) {
if (word_records.find(word) != word_records.end()) {
word_records[word] += 1;
} else {
word_records[word] = 1;
}
}
int curr_window_len = 0;
for (int i = 0; i < word_len; i++) {
unordered_map<string, int> word_occurence;
int left = i;
for (int j = i; j < n; j += word_len) {
string word = s.substr(j, word_len);
if (word_records.find(word) != word_records.end()) {
if (word_occurence.find(word) != word_occurence.end()) {
word_occurence[word] += 1;
while (word_occurence[word] > word_records[word]) {
word_occurence[s.substr(left, word_len)]--;
left += word_len;
}
} else {
word_occurence[word] = 1;
}
} else {
word_occurence.clear();
left = j + word_len;
}
if (j + word_len - left == word_len * word_num) {
word_occurence[s.substr(left, word_len)]--;
result.push_back(left);
left += word_len;
}
}
}
return result;
}
};
- Longest Valid Parentheses
Tag: Stack
class Solution {
public:
int
longestValidParentheses(string s) {
int n = s.length();
stack<int> stk;
stk.push(-1);
int max_len = 0;
for (int i = 0; i < n; i++) {
if (s[i] == '(') {
stk.push(i);
} else {
stk.pop();
if (stk.empty()) {
stk.push(i);
} else {
int len = i - stk.top();
max_len = len > max_len ? len : max_len;
}
}
}
return max_len;
}
};
Comments NOTHING