class Solution {
public:
vector<int> twoSum(vector<int> &nums, int target)
{
vector<int> ans;
for (int i = 0; i < nums.size(); i++) {
for (int j = i + 1; j < nums.size(); j++) {
if (nums[i] + nums[j] == target) {
ans.push_back(i);
ans.push_back(j);
}
}
}
return ans;
}
};
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2)
{
ListNode ans(0);
ListNode* p = &ans;
int tmp = 0;
while (l1 || l2 || tmp) {
int sum = (l1 ? l1->val : 0) + (l2 ? l2->val : 0) + tmp;
tmp = sum / 10;
p->next = new ListNode(sum % 10);
p = p->next;
l1 = l1 ? l1->next : l1;
l2 = l2 ? l2->next : l2;
}
return ans.next;
}
};
class Solution {
public:
int lengthOfLongestSubstring(string s)
{
map<char, int> mp;
int max_len = 0, start = 0;
for (int i = 0; i < s.length(); i++) {
if (mp.count(s[i]) && mp[s[i]] >= start) start = mp[s[i]] + 1;
mp[s[i]] = i;
max_len = max(max_len, i - start + 1);
}
return max_len;
}
};
class Solution {
public:
char ma[2010];
int mp[2010];
void manacher(string s)
{
int l = 0;
ma[l++] = '$', ma[l++] = '#';
for (int i = 0; i < s.size(); i++) ma[l++] = s[i], ma[l++] = '#';
ma[l] = 0;
int mx = 0, id = 0;
for (int i = 0; i < l; i++) {
mp[i] = mx > i ? min(mp[2 * id - i], mx - i) : 1;
while (ma[i + mp[i]] == ma[i - mp[i] >= 0 ? i - mp[i] : 0]) mp[i]++;
if (i + mp[i] > mx) mx = i + mp[i], id = i;
}
}
string longestPalindrome(string s)
{
string ans;
manacher(s);
int max_len = 0, max_pos;
for (int i = 0; i < 2010; i++) {
if (mp[i] > max_len) max_len = mp[i], max_pos = i;
}
max_len--;
return s.substr((max_pos - max_len) / 2, max_len);
}
};
class Solution {
public:
string ans[1010];
string convert(string s, int numRows)
{
string anss = "";
int rows = numRows - 1, i = 0, j = 0, cnt = 0, cntn = 0;
for (int k = 0; k < s.length(); k++) {
if (cnt % 2)
ans[i--].push_back(s[k]);
else
ans[i++].push_back(s[k]);
cntn++;
if (cntn == rows) cntn = 0, cnt++;
}
for (auto r : ans) anss += r;
return anss;
}
};
class Solution {
public:
int reverse(int x)
{
int tmp1 = abs(x);
long long tmp2 = 0;
while (tmp1) {
tmp2 = tmp2 * 10 + tmp1 % 10;
tmp1 /= 10;
}
if (x < 0 && -tmp2 >= INT_MIN && -tmp2 <= INT_MAX)
return -tmp2;
else if (tmp2 >= INT_MIN && tmp2 <= INT_MAX)
return tmp2;
else
return 0;
}
};
class Solution {
public:
int myAtoi(string str) {
int sign = 1, base = 0, i = 0;
while (str[i] == ' ') i++;
if (str[i] == '-' || str[i] == '+')
sign = 1 - 2 * (str[i++] == '-');
while (str[i] >= '0' && str[i] <= '9') {
if (base > INT_MAX / 10 || (base == INT_MAX / 10 && str[i] - '0' > 7)) {
if (sign == 1) return INT_MAX;
else return INT_MIN;
}
base = 10 * base + (str[i++] - '0');
}
return base * sign;
}
};
class Solution {
public:
bool isPalindrome(int x) {
string s1, s2;
if (x < 0)return false;
else {
int tmp = x;
while (tmp) {
s1 += ('0' + tmp % 10);
tmp /= 10;
}
s2 = s1;
reverse(s1.begin(), s1.end());
return (s1 == s2);
}
}
};
class Solution {
public:
int maxArea(vector<int>& height)
{
long long ans = 0, h, l = 0, r = height.size() - 1;
while (l < r) {
h = min(height[l], height[r]);
ans = max(ans, h * (r - l));
while (height[l] <= h && l < r) l++;
while (height[r] <= h && l < r) r--;
}
return ans;
}
};
class Solution {
public:
int romanToInt(string s)
{
int res = 0;
for (int i = 0; i < s.size(); i++) {
if (i < s.size() - 1) {
if (s[i] == 'I' && s[i + 1] == 'V') {
res += 4;
i++;
}
else if (s[i] == 'I' && s[i + 1] == 'X') {
res += 9;
i++;
}
else if (s[i] == 'X' && s[i + 1] == 'L') {
res += 40;
i++;
}
else if (s[i] == 'X' && s[i + 1] == 'C') {
res += 90;
i++;
}
else if (s[i] == 'C' && s[i + 1] == 'D') {
res += 400;
i++;
}
else if (s[i] == 'C' && s[i + 1] == 'M') {
res += 900;
i++;
}
else if (s[i] == 'I')
res += 1;
else if (s[i] == 'V')
res += 5;
else if (s[i] == 'X')
res += 10;
else if (s[i] == 'L')
res += 50;
else if (s[i] == 'C')
res += 100;
else if (s[i] == 'D')
res += 500;
else if (s[i] == 'M')
res += 1000;
}
else {
if (s[i] == 'I')
res += 1;
else if (s[i] == 'V')
res += 5;
else if (s[i] == 'X')
res += 10;
else if (s[i] == 'L')
res += 50;
else if (s[i] == 'C')
res += 100;
else if (s[i] == 'D')
res += 500;
else if (s[i] == 'M')
res += 1000;
}
}
return res;
}
};
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
if(strs.empty())return "";
string pre = strs[0];
for (auto s : strs)
if (s.size() < pre.size())
pre = s;
int flag = 0;
for(int i=0;i<strs.size();i++){
for (int j = 0; j < pre.size(); j++) {
if (strs[i][j] != pre[j]) { flag = 1; break; }
}
if (flag) { i = -1; pre = string(pre.begin(), --pre.end()); flag = 0; }
if (pre.empty()) { flag = 1; break; }
}
if (flag)return "";
else return pre;
}
};
class Solution {
public:
vector<vector<int>>final_ans;
set<vector<int>>tmp_ans;
map<int, int>mp;
vector<vector<int>> threeSum(vector<int>& nums) {
vector<int>new_nums;
for (auto n : nums){
mp[n]++;
if(mp[n]<=3)new_nums.push_back(n);
}
sort(new_nums.begin(), new_nums.end());
for (int i = 0; i < new_nums.size(); i++) {
for (int j = i + 1; j < new_nums.size(); j++) {
int tmp = 0 - new_nums[i] - new_nums[j];
if (tmp == new_nums[i] && tmp == new_nums[j]) {
if (mp[tmp] >= 3) {
vector<int>ans = { new_nums[i],new_nums[j],tmp };
sort(ans.begin(), ans.end());
tmp_ans.insert(ans);
}
}
else if (tmp == new_nums[i] || tmp == new_nums[j]) {
if (mp[tmp] >= 2) {
vector<int>ans = { new_nums[i],new_nums[j],tmp };
sort(ans.begin(), ans.end());
tmp_ans.insert(ans);
}
}
else if (mp.find(tmp) != mp.end()) {
vector<int>ans = { new_nums[i],new_nums[j],tmp };
sort(ans.begin(), ans.end());
tmp_ans.insert(ans);
}
}
}
for (auto s : tmp_ans)final_ans.push_back(s);
return final_ans;
}
};
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
int ans = nums[0] + nums[1] + nums[2], flag = 0;
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size(); i++) {
for (int j = i + 1; j < nums.size(); j++) {
int tmp = target - nums[i] - nums[j];
auto pos = lower_bound(nums.begin() + j + 1, nums.end(), tmp);
if (pos != nums.end() && *pos == tmp) { ans = target; flag = 1; break; }
else if (pos == nums.end() && j != nums.size() - 1) {
tmp = nums[i] + nums[j] + *(--pos);
if (abs(ans - target) > abs(tmp - target))ans = tmp;
}
else if (pos != nums.end()) {
tmp = nums[i] + nums[j] + *pos;
if (abs(ans - target) > abs(tmp - target))ans = tmp;
pos--;
int loc = pos - nums.begin();
if (loc != i && loc != j && loc >= 0 && loc <= nums.size()) {
tmp = nums[i] + nums[j] + *pos;
if (abs(ans - target) > abs(tmp - target))ans = tmp;
}
}
}
if (flag)break;
}
return ans;
}
};
class Solution {
public:
vector<string>ans;
map<char, vector<char>>mp;
void dfs(string&s, string&tmp, int cur) {
if (cur == s.length()) {
ans.push_back(tmp);
return;
}
for (auto i : mp[s[cur]]) {
string t = tmp;
tmp += i;
dfs(s, tmp, cur + 1);
tmp = t;
}
}
void init() {
mp['2'] = { 'a','b','c' };
mp['3'] = { 'd','e','f' };
mp['4'] = { 'g','h','i' };
mp['5'] = { 'j','k','l' };
mp['6'] = { 'm','n','o' };
mp['7'] = { 'p','q','r','s' };
mp['8'] = { 't','u','v' };
mp['9'] = { 'w','x','y','z' };
}
vector<string> letterCombinations(string digits) {
if(digits.empty())return ans;
init();
string tmp = "";
dfs(digits, tmp, 0);
return ans;
}
};
class Solution {
public:
set<vector<int>> tmp_ans;
vector<vector<int>> final_ans;
map<int, int> mp;
vector<vector<int>> fourSum(vector<int>& nums, int target)
{
vector<int> new_nums = nums;
for (auto n : nums) {
mp[n]++;
if (mp[n] <= 4) new_nums.push_back(n);
}
sort(new_nums.begin(), new_nums.end());
int n = new_nums.size();
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
for (int k = j + 1; k < n; k++) {
int tmp = target - new_nums[i] - new_nums[j] - new_nums[k];
if (binary_search(new_nums.begin() + k + 1, new_nums.end(),
tmp)) {
vector<int> t = {new_nums[i], new_nums[j], new_nums[k],
tmp};
tmp_ans.insert(t);
}
}
}
}
for (auto s : tmp_ans) final_ans.push_back(s);
return final_ans;
}
};
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n)
{
int cnt = 1;
ListNode* tmp = head;
while (tmp->next != NULL) {
cnt++;
tmp = tmp->next;
}
if (cnt == 1)return NULL;
else if (cnt == n) {
head = head->next;
return head;
}
tmp = head, cnt -= (n + 1);
while (cnt--) tmp = tmp->next;
ListNode* t = tmp->next;
if (t == NULL)tmp->next = NULL;
else tmp->next = t->next;
return head;
}
};
class Solution {
public:
bool isValid(string s) {
for (int i = 0; i < s.size(); i++) {
if (s[i] == '(')
for (int j = 1; j + i < s.size(); j += 2)
if (s[i + j] == ')') { s[i] = '-'; s[i + j] = '-'; break; }
if (s[i] == '[')
for (int j = 1; j + i < s.size(); j += 2)
if (s[i + j] == ']') { s[i] = '-'; s[i + j] = '-'; break; }
if (s[i] == '{')
for (int j = 1; j + i < s.size(); j += 2)
if (s[i + j] == '}') { s[i] = '-'; s[i + j] = '-'; break; }
}
for (auto c : s)
if (c != '-')
return false;
return true;
}
};
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode res(INT_MIN);
ListNode*h = &res;
while (l1&&l2) {
if (l1->val < l2->val) {
h->next = l1;
l1 = l1->next;
}
else {
h->next = l2;
l2 = l2->next;
}
h = h->next;
}
if (l1)h->next = l1;
else h->next = l2;
return res.next;
}
};
class Solution {
public:
vector<string> ans;
void dfs(string str, int n, int m) {
if (!n && !m) { ans.push_back(str); return; }
if (m > 0) dfs(str + ")", n, m - 1);
if (n > 0) dfs(str + "(", n - 1, m + 1);
}
vector<string> generateParenthesis(int n) {
string tmp = "";
dfs(tmp, n, 0);
return ans;
}
};
class Solution {
public:
ListNode* swapPairs(ListNode* head)
{
ListNode **tmp = &head, *a, *b;
while ((a = *tmp) && (b = a->next)) {
a->next = b->next;
b->next = a;
*tmp = b;
tmp = &(a->next);
}
return head;
}
};
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
if(nums.empty()) return 0;
int cnt = 1;
for (int i = 1; i < nums.size(); i++)
if (nums[i] != nums[i - 1])nums[cnt++] = nums[i];
return cnt;
}
};
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int cnt = 0;
for(int i = 0 ; i < nums.size() ; ++i) {
if(nums[i] == val)cnt++;
else nums[i-cnt] = nums[i];
}
return nums.size()-cnt;
}
};
class Solution {
public:
int strStr(string haystack, string needle)
{
int loc = -1;
if (needle.empty()) return 0;
if (haystack.size() < needle.size()) return -1;
int flag = 0;
for (int i = 0; i < haystack.size(); i++) {
if (haystack[i] == needle[0]) {
for (int j = 0, temp = i;
j < needle.size() && temp < haystack.size(); j++, temp++) {
if (haystack[temp] != needle[j]) {
flag = 1;
break;
}
else loc = temp;
}
if (!flag && loc - i == needle.size() - 1)return i;
else flag = 0;
}
}
return -1;
}
};
class Solution {
public:
int divide(int dividend, int divisor) {
if (!divisor || (dividend == INT_MIN && divisor == -1))return INT_MAX;
int sign = ((dividend < 0) ^ (divisor < 0)) ? -1 : 1;
long long dvd = labs(dividend);
long long dvs = labs(divisor);
int res = 0;
while (dvd >= dvs) {
long long temp = dvs, multiple = 1;
while (dvd >= (temp << 1)) {
temp <<= 1;
multiple <<= 1;
}
dvd -= temp;
res += multiple;
}
return sign == 1 ? res : -res;
}
};
class Solution {
public:
void nextPermutation(vector<int>& nums) {
next_permutation(nums.begin(),nums.end());
}
};
int search(vector<int>& nums, int target) {
int n = nums.size();
int lo = 0, hi = n - 1;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (nums[hi] < nums[mid])lo = mid + 1;
else hi = mid;
}
int pos = lo;
lo = 0, hi = n - 1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
int rmid = (pos + mid) % n;
if (nums[rmid] == target)return rmid;
if (nums[rmid] < target)lo = mid + 1;
else hi = mid - 1;
}
return -1;
}
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int ans1, ans2;
if (nums.empty()) {
vector<int>ans_empty = { -1,-1 };
return ans_empty;
}
auto pos1 = lower_bound(nums.begin(), nums.end(), target);
auto pos2 = upper_bound(nums.begin(), nums.end(), target);
if (nums.size() > 1) {
if (pos1 == nums.end() || *pos1 != target)ans1 = -1;
else ans1 = pos1 - nums.begin();
if (*(pos2 - 1) != target)ans2 = -1;
else ans2 = pos2 - nums.begin() - 1;
}
else {
if (pos1 == nums.end() || *pos1 != target)ans1 = -1, ans2 = -1;
else ans1 = 0, ans2 = 0;
}
vector<int>ans = { ans1,ans2 };
return ans;
}
};
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
return lower_bound(nums.begin(), nums.end(), target) - nums.begin();
}
};
class Solution {
public:
bool isValidSudoku(vector<vector<char>>& board) {
bool flag = true;
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] == '.')continue;
else {
int up = i - 1, down = i + 1, l = j - 1, r = j + 1, lc, rc;
while (l >= 0)
if (board[i][l--] == board[i][j]) return false;
while (r < 9)
if (board[i][r++] == board[i][j]) return false;
while (up >= 0)
if (board[up--][j] == board[i][j]) return false;
while (down < 9)
if (board[down++][l] == board[i][j]) return false;
lc = i / 3 * 3, rc = j / 3 * 3;
for (int x = 0; x < 3; x++) {
for (int y = 0; y < 3; y++) {
int curx = lc + x, cury = rc + y;
if (curx != i && cury != j && board[curx][cury] == board[i][j])return false;
}
}
}
}
}
return true;
}
};
class Solution {
public:
string countAndSay(int n)
{
string s = "1";
for (int i = 0; i < n - 1; i++) {
string tmp;
int cnt = 0;
for (int j = 0; j < s.size(); j++) {
if (s.size() == 1) {
tmp = s + "1";
break;
}
if (j == s.size() - 1) {
if (s[s.size() - 2] != s[s.size() - 1]) {
cnt++;
tmp += to_string(cnt);
tmp += s[j];
break;
}
else {
cnt++;
tmp += to_string(cnt);
tmp += s[j];
break;
}
}
if (s[j] == s[j + 1])
cnt++;
else {
cnt++;
tmp += to_string(cnt);
tmp += s[j];
cnt = 0;
}
}
s = tmp;
}
return s;
}
};
class Solution {
public:
set<vector<int>> tmp_ans;
vector<vector<int>> anss;
stack<int> ans;
void dfs(vector<int>& v, int s, int t)
{
if (s == t) {
vector<int> tmp;
stack<int> tmps = ans;
while (!tmps.empty()) {
tmp.push_back(tmps.top());
tmps.pop();
}
sort(tmp.begin(), tmp.end());
tmp_ans.insert(tmp);
return;
}
else if (s > t)
return;
for (auto n : v) {
s += n;
ans.push(n);
dfs(v, s, t);
ans.pop();
s -= n;
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target)
{
if (candidates.empty()) return anss;
dfs(candidates, 0, target);
for (auto v : tmp_ans) anss.push_back(v);
return anss;
}
};
const int maxn = 1e2+10;
class Solution {
public:
set<vector<int>>tmp_ans;
vector<vector<int>>anss;
stack<int>ans;
int vis[maxn];
void dfs(vector<int>&v, int s, int t) {
if (s == t) {
vector<int>tmp;
stack<int>tmps = ans;
while (!tmps.empty()) {
tmp.push_back(tmps.top());
tmps.pop();
}
sort(tmp.begin(), tmp.end());
tmp_ans.insert(tmp);
return;
}
else if (s > t)return;
for (int i = 0; i < v.size();i++) {
if (!vis[i]) {
s += v[i];
vis[i] = 1;
ans.push(v[i]);
dfs(v, s, t);
vis[i] = 0;
ans.pop();
s -= v[i];
}
}
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
if(candidates.empty())return anss;
dfs(candidates,0,target);
for(auto v:tmp_ans)anss.push_back(v);
return anss;
}
};
class Solution:
def multiply(self, num1, num2):
"""
:type num1: str
:type num2: str
:rtype: str
"""
return str(int(num1)*int(num2))
class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>>ans;
if(nums.empty())return ans;
sort(nums.begin(),nums.end());
do{
ans.push_back(nums);
}while(next_permutation(nums.begin(),nums.end()));
return ans;
}
};
class Solution {
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<vector<int>>ans;
if(nums.empty())return ans;
sort(nums.begin(),nums.end());
do{
ans.push_back(nums);
}while(next_permutation(nums.begin(),nums.end()));
return ans;
}
};
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int n = matrix[0].size(), cnt = 0, lx = 0, ly = 0, jump = n;
while (cnt++ <= n / 2) {
int tag = 0;
for (int i = 1; i < jump; i++) {
swap(matrix[lx][ly + tag], matrix[lx + tag][ly + jump - 1]);
swap(matrix[lx][ly + tag], matrix[lx + jump - 1 - tag][ly]);
swap(matrix[lx + jump - 1 - tag][ly], matrix[lx + jump - 1][ly + jump - 1 - tag]);
tag++;
}
lx++, ly++, jump -= 2;
}
}
};
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, multiset<string>> mp;
for (auto s : strs) {
string t = s;
sort(t.begin(), t.end());
mp[t].insert(s);
}
vector<vector<string>> anagrams;
for (auto m : mp) {
vector<string> anagram(m.second.begin(), m.second.end());
anagrams.push_back(anagram);
}
return anagrams;
}
};
class Solution:
def myPow(self, x, n):
"""
:type x: float
:type n: int
:rtype: float
"""
return x**n