Letter Combinations of a Phone Number
"""这种题就是DFS，递归+一堆传引用。
迭代解法见http://www.cnblogs.com/grandyang/p/4452220.html，也可以用队列实现。
"""
class Solution {
public:
void helper(const string& digits, vector<string>& res, const vector<string>& m, int n, string & re){
if(digits.empty()){
res = {};
return;
}
string tmps = m[digits[n]-'0'];
for(char c:tmps){
re += c;
helper(digits, res, m, n+1, re);
if(n==digits.size()-1){
res.push_back(re);
}
re.pop_back();
}
}
vector<string> letterCombinations(string digits) {
if(digits.empty())
return {};
vector<string> m={"","","abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
vector<string> res;
string re="";
helper(digits, res, m, 0, re);
return res;
}
};
Remove Nth Node From End of List
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* slow = head;
ListNode* fast = head;
for(int i=0;i<n;i++)
fast = fast->next;
if(!fast)
return slow->next;
while(fast->next){
slow = slow->next;
fast = fast->next;
} //slow停在要删的节点前面一个节点
slow->next = slow->next->next;
return head;
}
};
Generate Parentheses
"""DFS递归法和前面那题很像
"""
class Solution {
public:
void helper(vector<string>& res, int left, int right, string re){
if(left > right)
return;
if(right == 0 && left == 0)
res.push_back(re);
else{
if(left) helper(res, left-1, right, re+"(");
if(right) helper(res, left, right-1, re+")");
}
}
vector<string> generateParenthesis(int n) {
vector<string> res;
string re="";
int left = n, right = n;
helper(res, left, right, re);
return res;
}
};
Swap Nodes in Pairs
"""递归
"""
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
if(!head || !head->next)
return head;
ListNode* tmp = head->next;
head->next = swapPairs(head->next->next);
tmp->next = head;
return tmp;
}
};
Next Permutation
class Solution {
public:
void nextPermutation(vector<int>& nums) {
// 12544321 ->
bool flag = true;
int idx = 0;
for(int i=nums.size()-1;i>0;i--){
flag = nums[i]<=nums[i-1];
if(!flag){
idx = i;
break;
}
}
if(flag){
sort(nums.begin(), nums.end());
}
else{
int idx1 = idx-1;
for(int i=nums.size()-1;i>=idx;i--){
if(nums[i]>nums[idx1]){
int tmp = nums[i];
nums[i] = nums[idx1];
nums[idx1] = tmp;
sort(nums.begin()+idx1+1, nums.end());//可以换为逆序，仔细观察规律
return;
}
}
}
}
};
Search in Rotated Sorted Array
class Solution {
public:
int helper(vector<int>& nums, int i, int j, int target) {
if(nums.empty() || i>j)
return -1;
int split = i + (j-i)/2;
if(target == nums[split])
return split;//split;
if(nums[split]<nums[j]){
if(target>nums[split] && target<=nums[j])
return helper(nums, split+1, j, target);
else
return helper(nums, i, split-1, target);
}
else{
if(target>=nums[i] && target<nums[split])
return helper(nums, i, split-1, target);
else
return helper(nums, split+1, j, target);
}
}
int search(vector<int>& nums, int target) {
return helper(nums, 0, nums.size()-1, target);
}
};
Search for a Range
"""类似上一题，只需要用一个分支的二分法。
"""
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
vector<int> res = {-1,-1};
int i=0, j=nums.size()-1;
while(i<=j){
int mid = i+(j-i)/2;
if(nums[mid]==target){
int k = mid;
while(k>=i && nums[k] == target)
k--;
res[0] = k+1;
while(mid<=j && nums[mid] == target)
mid++;
res[1] = mid-1;
return res;
}
else if(nums[mid]>target){
j = mid-1;
}
else
i = mid+1;
}
return res;
}
};
"""也可以单独搜索左边界和右边界: http://www.cnblogs.com/grandyang/p/4409379.html
"""
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
vector<int> res = {-1,-1};
if(nums.empty())
return res;
int i=0, j=nums.size()-1;
while(i<=j){
int mid = i+(j-i)/2;
if(nums[mid]>=target)
j = mid-1;
else
i = mid+1;
}
if(j+1>=nums.size() || nums[j+1]!=target)//要找的最靠右边的比target小的数字nums[j]恰好是数组最后一个元素的情况，此时nums[j+1]不存在，之前的更新一直是把i往右边移动
return {-1,-1};
else
res[0] = j+1;
j = nums.size()-1;
while(i<=j){
int mid = i+(j-i)/2;
if(nums[mid]>target)
j = mid-1;
else
i = mid+1;
}
res[1] = i-1;
return res;
}
};
Valid Sudoku
class Solution {
public:
bool isValidSudoku(vector<vector<char>>& board) {
int in_rows[9][9] = {0}, in_cols[9][9] = {0}, in_box[9][9] = {0};
for(int i=0;i<board.size();i++){
for(int j=0;j<board[i].size();j++){
if(board[i][j]!='.'){
int tmp = board[i][j] - '0' - 1;
int loc = 3 * (i / 3) + j / 3;
if(in_rows[i][tmp]||in_cols[j][tmp]||in_box[loc][tmp])
return false;
else{
in_rows[i][tmp] = 1;
in_cols[j][tmp] =1;
in_box[loc][tmp] = 1;
}
}
}
}
return true;
}
};
Combination Sum
class Solution {
public:
void helper(vector<int> & candidates, int target, vector<vector<int>>& res, vector<int>& re, int loc){
if(target<0)
return;
else if(target == 0){
res.push_back(re);
return;
}
else{
for(int i=loc;i<candidates.size();i++){
re.push_back(candidates[i]);
helper(candidates, target-candidates[i], res, re, i);
re.pop_back();
}
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
if(candidates.empty())
return {};
vector<vector<int>> res;
vector<int> re;
helper(candidates, target, res, re, 0);
return res;
}
};
Combination Sum II
class Solution {
public:
void helper(vector<int> & candidates, int target, vector<vector<int>>& res, vector<int>& re, int loc){
if(target<0)
return;
else if(target == 0){
res.push_back(re);
return;
}
else{
for(int i=loc;i<candidates.size();i++){
if (i > loc && candidates[i] == candidates[i - 1]) continue; //避免1,7和7,1这样的重复
re.push_back(candidates[i]);
helper(candidates, target-candidates[i], res, re, i+1); //同一个位置的数字不能多次使用
re.pop_back();
}
}
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
if(candidates.empty())
return {};
sort(candidates.begin(), candidates.end());
vector<vector<int>> res;
vector<int> re;
helper(candidates, target, res, re, 0);
return res;
}
};
Multiply Strings
"""这其实一种表示和计算超大数字的方法，即用字符串或数组
"""
class Solution {
public:
string multiply(string num1, string num2) {
string res = "";
int n1 = num1.size(), n2 = num2.size();
vector<int> v(n1+n2,0);
for(int i=n1-1;i>=0;i--)
for(int j=n2-1;j>=0;j--){
v[i+j+1] += (num1[i]-'0')*(num2[j]-'0');
}
int carry = 0;
for(int i=n1+n2-1;i>=0;i--){
v[i] += carry;
carry = v[i]/10;
v[i] %=10;
}
int k = 0;
while(v[k] == 0)
k++;
if(k>=v.size())
return "0";
for(int i=k;i<n1+n2;i++)
res+=('0'+v[i]);
return res;
}
};
Permutations
class Solution {
public:
void helper(vector<int>& nums, vector<vector<int>>& res, vector<int>& re, vector<int>& visited){
if(re.size() == nums.size())
res.push_back(re);
else
for(int i=0;i<nums.size();i++){
if(!visited[i]){
visited[i] = 1;
re.push_back(nums[i]);
helper(nums, res, re, visited);
re.pop_back();
visited[i] = 0;
}
}
}
vector<vector<int>> permute(vector<int>& nums) {
if(nums.empty())
return {};
vector<vector<int>> res;
vector<int> re;
vector<int> visited(nums.size(),0);
helper(nums, res, re, visited);
return res;
}
};
Permutations II
"""改改。
if (i > 0 && nums[i] == nums[i - 1] && visited[i - 1] == 0) continue; //这行配合sort才行
"""
class Solution {
public:
void helper(vector<int>& nums, vector<vector<int>>& res, vector<int>& re, vector<int>& visited){
if(re.size() == nums.size())
res.push_back(re);
else
for(int i=0;i<nums.size();i++){
if(!visited[i]){
if (i > 0 && nums[i] == nums[i - 1] && visited[i - 1] == 0) continue; //
visited[i] = 1;
re.push_back(nums[i]);
helper(nums, res, re, visited);
re.pop_back();
visited[i] = 0;
}
}
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
if(nums.empty())
return {};
sort(nums.begin(), nums.end());
vector<vector<int>> res;
vector<int> re;
vector<int> visited(nums.size(),0);
helper(nums, res, re, visited);
return res;
}
};
Rotate Image
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int n = matrix.size();
for(int i=0;i<n;i++)
for(int j=i;j<n;j++)
swap(matrix[i][j], matrix[j][i]);
for(int i=0;i<n;i++)
for(int j=0; j<n/2;j++)
swap(matrix[i][j], matrix[i][n-j-1]);
}
};
Group Anagrams
"""注意时空复杂度分析
"""
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
vector<vector<string>> res;
unordered_map<string, vector<string>> m;
int count[26] = {0};
for(string s : strs){
memset(count, 0, sizeof(count));
for(char c : s)
count[c-'a'] ++;
string encoding = "";
for(int n:count){
encoding += to_string(n);
encoding += 'c';
}
m[encoding].push_back(s);
}
for(auto i : m)
res.push_back(i.second);
return res;
}
};
Pow(x, n)
"""需要考虑时间和越界
"""
class Solution {
public:
double myPow(double x, int n) {
if(n==0)
return 1;
if(n==1)
return x;
if(n==-1)
return 1/x;
double y;
if(n%2==0){
y = myPow(x,n/2);
y *= y;
}
else{
y = myPow(x,(n-1)/2);
y *= y;
y *= x;
}
return y;
}
};
