Power Series
Given an integer, write a function to determine if it is a power of two.
The idea: the bit operation, only the first position is 1, others are all 0
class Solution {
public:
bool isPowerOfTwo(int n) {
return (n>0)&&!(n&(n-1));
}
};
Given an integer, write a function to determine if it is a power of three.
The idea: use the log
class Solution {
public:
bool isPowerOfThree(int n) {
double temp = log10(n)/log10(3);
return temp==int(temp);
}
};
Given an integer (signed 32 bits), write a function to check whether it is a power of 4.
The idea: it must be the power of 2, and then only even position is 1
class Solution {
public:
bool isPowerOfFour(int n) {
return (n>0) &&(!(n&n-1)) && (n-1)%3==0;
}
};
Leetcode Contain Duplicates Series
Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.
The idea: set doesn’t allow the number duplicate input
class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
return nums.size() > unordered_set<int>(nums.begin(), nums.end()).size();
}
};
The idea: use the map to store the nums[i] index
class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k) {
unordered_map<int, int> map;
for (int i=0; i<nums.size(); i++) {
if (map[nums[i]]) {
if (i+1-map[nums[i]] <= k)
return true;
}
map[nums[i]] = i+1;
}
return false;
}
};
Leetcode 220. Contains Duplicate III
The idea: use the map
class Solution {
public:
bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
if (nums.empty()) return false;
map<int, int> m;
int j = 0;
for (int i=0; i<nums.size(); i++) {
if (i-j >k && m[nums[j]]==j)
m.erase(nums[j++]);
auto a = m.lower_bound(nums[i]-t);
if (a!=m.end() && abs(a->first - nums[i])<=t)
return true;
m[nums[i]] = i;
}
return false;
}
};
Merge LinkedLists
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
The first Solution is recursion.
class Solution {
public:
ListNode* mergeTwoLists(ListNode* p, ListNode* q) {
if (!p) return q;
if (!q) return p;
if (p->val < q->val) {
p->next = mergeTwoLists(p->next, q);
return p;
}
else {
q->next = mergeTwoLists(p, q->next);
return q;
}
}
};
The second solution is non-recursion
class Solution {
public:
ListNode* mergeTwoLists(ListNode* p, ListNode* q) {
if (!p) return q;
if (!q) return p;
ListNode* prev = new ListNode(0);
ListNode* ans = prev;
while (p || q) {
if (p && q) {
if (p->val < q->val) {
ans->next = p;
p = p->next;
}
else {
ans->next = q;
q = q->next;
}
}
else if (p) {
ans->next = p;
p = p->next;
}
else {
ans->next = q;
q = q->next;
}
ans = ans->next;
}
return prev->next;
}
};
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
The idea: the half recursion to mergeTwolists
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
const int n = lists.size();
if (n==0) return NULL;
if (n==1) return lists[0];
if (n==2) return mergeTwoLists(lists[0], lists[1]);
vector<ListNode*> left(lists.begin(), lists.begin()+n/2);
vector<ListNode*> right(lists.begin()+n/2, lists.end());
return mergeTwoLists(mergeKLists(left), mergeKLists(right));
}
};
Leetcode Sum Serials
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
The idea: use the map to store the value’s index, and for loop the map to find m[target-nums[i]] exits in the map
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> res;
const int n = nums.size();
unordered_map<int, int> m;
for (int i=0; i<n; i++)
m[nums[i]] = i;
for (int i=0; i<n; i++) {
if (m[target-nums[i]]) {
res.push_back(i);
res.push_back(m[target-nums[i]]);
break;
}
}
return res;
}
};
Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.
The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution and you may not use the same element twice.
Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
int left=0, right = numbers.size()-1;
while (left<right) {
if (numbers[left]+numbers[right]==target)
return {left + 1, right + 1};
else if (numbers[left]+numbers[right]<target) left++;
else right--;
}
}
};
Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note: The solution set must not contain duplicate triplets.
For example, given array S = [-1, 0, 1, 2, -1, -4], A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]
The idea: sort the nums, and then start at i, j=i+1, and k is the last number, if the sum is smaller, then j++, if it is bigger, then k–;
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> res;
const int n = nums.size();
if (n<3) return res;
sort(nums.begin(), nums.end());
for (int i=0; i<n; i++) {
int j = i+1, k = n-1;
while (j<k) {
while (j<k && nums[i]+nums[j]+nums[k] < 0) j++;
while (j<k && nums[i]+nums[j]+nums[k] > 0) k--;
if (j<k && nums[i]+nums[j]+nums[k] == 0) {
res.push_back({nums[i], nums[j], nums[k]});
while (j<k && nums[j]==nums[j+1]) j++;
j++;
while (j<k && nums[k]==nums[k-1]) k--;
}
}
while (i<n && nums[i]==nums[i+1]) i++;
}
return res;
}
};
Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
For example, given array S = {-1 2 1 -4}, and target = 1. The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
The idea: sort the nums, keep trace the newest closet answer and difference.
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
int ans = nums[0]+nums[1]+nums[2];
int diff = abs(target - ans);
if (diff==0) return ans;
const int n = nums.size();
sort(nums.begin(), nums.end());
for (int i=0; i<n; i++) {
int j = i+1;
int k = n-1;
while (j<k) {
int temp = nums[i]+nums[j]+nums[k];
int newDiff = abs(target-temp);
if (newDiff<diff) {
ans = temp;
diff = newDiff;
}
if (temp<target) j++;
else k--;
}
}
return ans;
}
};
Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.
Note: The solution set must not contain duplicate quadruplets.
For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0. A solution set is:
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]
The idea is same as the 3Sum.
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> res;
const int n = nums.size();
if (n<4) return res;
sort(nums.begin(), nums.end());
for (int i=0; i<n; i++) {
for (int j=i+1; j<n; j++) {
int k = j+1;
int m = n-1;
while (k<m) {
while (k<m && nums[i]+nums[j]+nums[k]+nums[m] < target) k++;
while (k<m && nums[i]+nums[j]+nums[k]+nums[m] > target) m--;
if (k<m && nums[i]+nums[j]+nums[k]+nums[m] == target) {
res.push_back({nums[i], nums[j], nums[k], nums[m]});
while (k<m && nums[k]==nums[k+1]) k++;
k++;
while (k<m && nums[m]==nums[m-1]) m--;
}
}
while (j<n && nums[j]==nums[j+1]) j++;
}
while (i<n && nums[i]==nums[i+1]) i++;
}
return res;
}
};
LinkedList in Leetcode
Leetcode 206. Reverse Linked List
Reverse a singly linked list.
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if (!head || !head->next)
return head;
ListNode* newHead = reverseList(head->next);
head->next->next = head;
head->next = NULL;
return newHead;
}
};
Reverse a linked list from position m to n. Do it in-place and in one-pass.
For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,
return 1->4->3->2->5->NULL.
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int m, int n) {
ListNode* prehead = new ListNode(0);
prehead->next = head;
ListNode* tail = prehead;
n -= m;
while(--m > 0) tail = tail->next;
ListNode* curr = tail->next;
while(n-- > 0){ // pull one out to tail
ListNode* temp = curr->next;
curr->next = temp->next;
temp->next = tail->next; // easy to make mistake
tail->next = temp;
}
return prehead->next;
}
};
Leetcode Permutation Serials
Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).
The replacement must be in-place, do not allocate extra memory.
Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1
class Solution {
public:
void nextPermutation(vector<int>& nums) {
if (nums.size() < 2)
return;
int i, j;
for (i = nums.size() - 2; i >= 0; i--)
if (nums[i] < nums[i + 1])
break;
for (j = nums.size() - 1; j > i; j--)
if (nums[i] < nums[j])
break;
if (i >= 0)
swap(nums[i], nums[j]);
reverse(nums.begin() + i + 1, nums.end());
}
};
Given a collection of distinct numbers, return all possible permutations.
For example, [1,2,3] have the following permutations:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
class Solution {
public:
vector<vector<int> > permute(vector<int> &num) {
vector<vector<int> > result;
helper(result, 0, num);
return result;
}
void helper(vector<vector<int>> &res, int begin, vector<int>& nums) {
if (begin >= nums.size()) {
res.push_back(nums);
return;
}
for (int i=begin; i<nums.size(); i++) {
swap(nums[i], nums[begin]);
helper(res, begin+1, nums);
swap(nums[i], nums[begin]);
}
}
};
Given a collection of numbers that might contain duplicates, return all possible unique permutations.
For example, [1,1,2] have the following unique permutations:
[
[1,1,2],
[1,2,1],
[2,2,1],
]
class Solution {
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<vector<int>> res;
helper(res, 0, nums);
return res;
}
void helper(vector<vector<int>> &res, int begin, vector<int>& nums) {
if (begin >= nums.size()) {
res.push_back(nums);
return;
}
for (int i=begin; i<nums.size(); i++) {
swap(nums[i], nums[begin]);
helper(res, begin+1, nums);
swap(nums[i], nums[begin]);
while (i<nums.size() && nums[i]==nums[i-1])
i++;
}
}
};
Leetcode 60. Permutation Sequence
The set [1,2,3,…,n] contains a total of n! unique permutations.
By listing and labeling all of the permutations in order, We get the following sequence (ie, for n = 3):
Given n and k, return the kth permutation sequence.
class Solution {
public:
string getPermutation(int n, int k) {
vector<int> input(n);
for (int i=1; i<=n; i++)
input[i-1] = i;
k--;
string res;
while (input.size()>1) {
int f = fac(input.size()-1);
int pos = k/f;
res += input[pos] +'0';
input.erase(input.begin()+pos);
k %= f;
}
res += input[0] +'0';
return res;
}
int fac(int n) {
if (n==0) return 1;
int res = 1;
for (int i=1; i<=n; i++)
res *= i;
return res;
}
};