Math Series
There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
Example 1:
nums1 = [1, 3]
nums2 = [2]
The median is 2.0
Example 2:
nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
const int m = nums1.size();
const int n = nums2.size();
int k = (m+n)/2;
if ((m+n)%2!=0)
return helper(nums1, nums2, k+1);
else
return (helper(nums1, nums2, k) + helper(nums1, nums2, k+1))/2;
}
double helper(vector<int> &nums1, vector<int> &nums2, int k) {
const int m = nums1.size();
const int n = nums2.size();
if (m>n) return helper(nums2, nums1, k);
if (m==0) return nums2[k-1];
if (k==1) return min(nums1[0], nums2[0]);
int pa = min(m, k/2), pb = k-pa;
if (nums1[pa-1] < nums2[pb-1]) {
vector<int> a(nums1.begin()+pa, nums1.end());
return helper(a, nums2, k-pa);
}
else {
vector<int> b(nums2.begin()+pb, nums2.end());
return helper(nums1, b, k-pb);
}
}
};
Implement pow(x, n).
class Solution {
public:
double myPow(double x, int n) {
if (n==0) return 1;
if (x==0) return 0;
if (n>0) return helper(x, n);
else return helper(1/x, -n);
}
double helper(double x, int n) {
if (n==0) return 1;
double half = helper(x, n/2);
if (n%2==0)
return half*half;
else
return half*half*x;
}
};
Given an integer n, return the number of trailing zeroes in n!.
Note: Your solution should be in logarithmic time complexity.
class Solution {
public:
int trailingZeroes(int n) {
int count = 0;
while (n) {
count += n/5;
n /= 5;
}
return count;
}
};
Count the number of prime numbers less than a non-negative number, n.
class Solution {
public:
int countPrimes(int n) {
vector<int> p(n, 1);
int ans = 0;
for (int i=2; i<n; i++) {
ans += p[i];
if (p[i]==1)
for (int j=i; j<n; j+=i)
p[j] = 0;
}
return ans;
}
};
Palindrome Partitioning
Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.
For example, given s = “aab”, Return
[
["aa","b"],
["a","a","b"]
]
class Solution {
public:
vector<vector<string>> partition(string s) {
vector<vector<string>> res;
vector<string> curr;
if (s.empty()) return res;
helper(s, res, 0, curr);
return res;
}
void helper(string s, vector<vector<string>> &res, int pos, vector<string> &curr) {
if (pos==s.size()) res.push_back(curr);
for (int i=pos; i<s.size(); i++) {
if (isPalindrome(s, pos, i)) {
curr.push_back(s.substr(pos, i-pos+1));
helper(s, res, i+1, curr);
curr.pop_back();
}
}
}
bool isPalindrome(string s, int i, int j) {
while (i<j && s[i]==s[j]) {
i++;
j--;
}
return i>=j;
}
};
Single Number
Given an array of integers, every element appears twice except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
class Solution {
public:
int singleNumber(vector<int>& nums) {
int res = 0;
for (int n:nums)
res ^= n;
return res;
}
};
Given an array of integers, every element appears three times except for one. Find that single one.
class Solution {
public:
int singleNumber(vector<int>& nums) {
int one = 0, two = 0;
for (int n: nums) {
two |= (n&one);
one ^= n;
int t = one & two;
one &= (~t);
two &= (~t);
}
return one;
}
};
Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.
For example: Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].
class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
int diff = 0;
for (int n: nums) diff^=n;
diff &= -diff;
int num1= 0, num2 = 0;
for (int n:nums) {
if ((diff & n)==0) num1 ^= n;
else num2^=n;
}
return {num1, num2};
}
};
Queue Basic Knowledge (some from geeksforgeeks)
Queue is a linear structure which follows a particular order in which the operations are performed. The order is First In First Out (FIFO).
The difference between stacks and queues is in removing. In a stack we remove the item the most recently added; in a queue, we remove the item the least recently added.
Mainly the following four basic operations are performed on queue: Enqueue: Adds an item to the queue. If the queue is full, then it is said to be an Overflow condition.
Dequeue: Removes an item from the queue. The items are popped in the same order in which they are pushed. If the queue is empty, then it is said to be an Underflow condition.
Front: Get the front item from queue.
Rear: Get the last item from queue.
Queue is used when things don’t have to be processed immediatly, but have to be processed in First InFirst Out order like Breadth First Search. This property of Queue makes it also useful in following kind of scenarios.
1) When a resource is shared among multiple consumers. Examples include CPU scheduling, Disk Scheduling.
2) When data is transferred asynchronously (data not necessarily received at same rate as sent) between two processes. Examples include IO Buffers, pipes, file IO, etc.
For implementing queue, we need to keep track of two indices, front and rear. We enqueue an item at the rear and dequeue an item from front. If we simply increment front and rear indices, then there may be problems, front may reach end of the array. The solution to this problem is to increase front and rear in circular manner
1) Every item has a priority associated with it.
2) An element with high priority is dequeued before an element with low priority.
3) If two elements have the same priority, they are served according to their order in the queue.
insert(item, priority): O(1)
getHighestPriority(): Returns the highest priority item. O(n)
deleteHighestPriority(): Removes the highest priority item.
We can also use Linked List, time complexity of all operations with linked list remains same as array. The advantage with linked list is deleteHighestPriority() can be more efficient as we don’t have to move items.
Using Array: A simple implementation is to use array of following structure.
struct item {
int item;
int priority;
}
Heap is generally preferred for priority queue implementation because heaps provide better performance compared arrays or linked list. In a Binary Heap, getHighestPriority() can be implemented in O(1) time, insert() can be implemented in O(Logn) time and deleteHighestPriority() can also be implemented in O(Logn) time.
With Fibonacci heap, insert() and getHighestPriority() can be implemented in O(1) amortized time and deleteHighestPriority() can be implemented in O(Logn) amortized time.
Best Time to Buy and Sell Stock
Say you have an array for which the ith element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.
Example 1:
Input: [7, 1, 5, 3, 6, 4]
Output: 5
max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price)
Example 2:
Input: [7, 6, 4, 3, 1]
Output: 0
In this case, no transaction is done, i.e. max profit = 0.
class Solution {
public:
int maxProfit(vector<int>& nums) {
if (nums.empty()) return 0;
int res = 0, minP = INT_MAX;
for (int p:nums) {
minP = min(p, minP);
res = max(res, p-minP);
}
return res;
}
};
Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
class Solution {
public:
int maxProfit(vector<int>& nums) {
int res = 0, minP = INT_MAX;
if (nums.empty()) return 0;
for (int p:nums) {
if (p>minP) res+=p-minP;
minP = p;
}
return res;
}
};
Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most two transactions.
class Solution {
public:
int maxProfit(vector<int>& prices) {
const int n = prices.size();
if (n<2) return 0;
vector<int> preProfits(n, 0);
vector<int> postProfits(n, 0);
int minP = prices[0];
for (int i=1; i<n; i++) {
minP = min(minP, prices[i]);
preProfits[i] = max(preProfits[i-1], prices[i]-minP);
}
int maxP = prices[n-1];
for (int i=n-2; i>=0; i--) {
maxP = max(maxP, prices[i]);
postProfits[i] = max(postProfits[i+1], maxP-prices[i]);
}
int res = 0;
for (int i=0; i<n; i++)
res = max(res, preProfits[i]+postProfits[i]);
return res;
}
};
Linked List Basic Knowledge (some from geeksforgeeks)
Like arrays, Linked List is a linear data structure. Unlike arrays, linked list elements are not stored at contiguous location; the elements are linked using pointers.
struct node {
int val;
node* left;
node* right;
};
Arrays can be used to store linear data of similar types, but arrays have following limitations.
1) The size of the arrays is fixed: So we must know the upper limit on the number of elements in advance. Also, generally, the allocated memory is equal to the upper limit irrespective of the usage.
2) Inserting a new element in an array of elements is expensive, because room has to be created for the new elements and to create room existing elements have to shifted.
For example, in a system if we maintain a sorted list of IDs in an array id[].
id[] = [1000, 1010, 1050, 2000, 2040].
And if we want to insert a new ID 1005, then to maintain the sorted order, we have to move all the elements after 1000 (excluding 1000).
Deletion is also expensive with arrays until unless some special techniques are used. For example, to delete 1010 in id[], everything after 1010 has to be moved.
Dynamic size and Ease of insertion/deletion
1) Random access is not allowed. We have to access elements sequentially starting from the first node. So we cannot do binary search with linked lists.
2) Extra memory space for a pointer is required with each element of the list.
Delete an element from a linked list
void delNode(ListNode *prev) {
ListNode *curr = prev->next;
prev->next = curr->next;
delete curr; // 清理trash指针
}
快慢指的是指针向前移动的步长，一般来说，快指针每次移动 2，慢指针每次移动 1, 主要有两个应用
快速找出未知长度单链表的中间节点
设置两个指针 *fast 和 *slow 都指向头节点
*fast 移动速度是 *slow 的两倍
fast 指向末尾节点时，slow 正好就在中间
判断单链表是否有环
设置两个指针 *fast 和 *slow 都指向头节点
*fast 移动速度是 *slow 的两倍
如果 *fast == null 说明该单链表不是循环链表
如果 *fast == *slow 说明该链表是循环链表
其他应用
找倒数第 N 个节点
设置两个指针 *fast 和 *slow 都指向头节点
*fast 先移动 N 步，然后两个指针一起前进
fast 到达末尾时，slow 即为倒数第 N 个节点
Link − Each link of a linked list can store a data called an element.
Next − Each link of a linked list contains a link to the next link called Next.
Prev − Each link of a linked list contains a link to the previous link called Prev.
LinkedList − A Linked List contains the connection link to the first link called First and to the last link called Last.