LeetCode Q89: Gray Code

The gray code is a binary numeral system where two successive values differ in only one bit.

Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.

For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:

00 - 0
01 - 1
11 - 3
10 - 2

Note:
For a given n, a gray code sequence is not uniquely defined.

For example, [0,2,3,1] is also a valid gray code sequence according to the above definition.

For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.

	class Solution {
	public:
	vector<int> grayCode(int n) {
	int p=0;
	vector<int> res;
	vector<int> flag(pow(2, n), 0);
	res.push_back(0);
	flag[0]=1;
	for(int i=1; i<pow(2, n); i++){
	for(int j=0; j<n; j++){
	int s=1<<j;
	if(flag[p^s]==0){
	flag[p^s]=1;
	res.push_back(p^s);
	p=p^s;
	break;
	}
	}
	}
	return res;
	}
	};

view raw Q89.cpp hosted with ❤ by GitHub

Rnd3 Sol:
No extra space used. Based on an observation that if two adjacent numbers are different by only 1 bit, than adding 1 to same 0 bit position of the two numbers should result in gray code too.

	vector<int> grayCode(int n)
	{
	vector<int> result(1, 0);
	for (int i = 0; i < n; i++) {
	int curCount = result.size();
	// push back all element in result in reverse order
	while (curCount) {
	curCount--;
	int curNum = result[curCount];
	curNum += (1<<i);
	result.push_back(curNum);
	}
	}
	return result;
	}

view raw 89Rnd3.cpp hosted with ❤ by GitHub

LeetCode Q86: Partition List

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.

	ListNode* partition(ListNode* head, int x) {
	if(head==NULL)
	return head;
	ListNode* less=NULL;
	ListNode* greater=NULL;
	ListNode* cur=head;
	ListNode* greaterHead=NULL;
	while(cur!=NULL){
	if(cur->val<x){
	if(less==NULL){
	less=cur;
	head=cur;
	}
	else{
	less->next=cur;
	less=cur;
	}
	cur=cur->next==NULL? NULL:cur->next;
	}else{
	if(greater==NULL){
	greater=cur;
	greaterHead=cur;
	}else{
	greater->next=cur;
	greater=cur;
	}
	cur=cur->next==NULL? NULL:cur->next;
	}
	}
	if(greater!=NULL)
	greater->next=NULL;
	if(less!=NULL)
	less->next=greaterHead;
	return head;
	}

view raw Q86PartitionList.cpp hosted with ❤ by GitHub

LeetCode Q85: Maximal Rectangle (hard)

Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area

The idea is to scan the matrix row by row. In this row, we calculate a histogram of 1's that are directly continuously above the row. Then we could solve the maximal area of histogram using  "Largest Rectangle in Histogram". Then entire algorithm takes O(n^2) time.

	class Solution {
	public:
	int largestRectangleArea(vector<int>& h) {
	stack<int> s;
	h.push_back(0);
	int p=0;
	int largest=0;
	while(!(s.empty()&&p==h.size()-1)){
	if(s.empty()&&p!=h.size()-1){
	s.push(p);
	p++;
	continue;
	}
	while(h[s.top()]<h[p]){
	s.push(p);
	p++;
	}
	int curTop=s.top();
	s.pop();
	int area;
	if(s.empty())
	area=p*h[curTop];
	else
	area=(p-s.top()-1)*h[curTop];
	largest=area>largest? area: largest;
	}
	return largest;
	}
	int maximalRectangle(vector<vector<char>>& m) {
	if(m.empty())
	return 0;
	int rows=m.size();
	int cols=m[0].size();
	vector<int> hist(cols, 0);
	int largest=0;
	for(int i=0; i<rows; i++){
	for(int j=0; j<cols; j++){
	hist[j]=m[i][j]=='0'? 0:hist[j]+1;
	}
	int area=largestRectangleArea(hist);
	largest=area>largest? area:largest;
	}
	return largest;
	}
	};

view raw Q84.cpp hosted with ❤ by GitHub

LeetCode Q84: Largest Rectangle in Histogram

Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

For example,
Given heights = [2,1,5,6,2,3],
return 10.

Solution 1: O(N^2)

	class Solution {
	public:
	int largestRectangleArea(vector<int>& heights) {
	int largest=0;
	int preArea=0;
	for(int i=0; i<heights.size(); ++i){
	int min=INT_MAX;
	for(int j=i; j<heights.size(); ++j){
	if(i==j){
	min=heights[i];
	preArea=heights[i];
	largest=preArea>largest? preArea:largest;
	continue;
	}
	if(heights[j]<min){
	preArea=heights[j]*(j-i+1);
	min=heights[j];
	}else{
	preArea=preArea*(j-i+1)/(j-i);
	}
	largest=preArea>largest? preArea:largest;
	}
	}
	return largest;
	}
	};

view raw Q84-1.cpp hosted with ❤ by GitHub

Solution 2: Divide and Conque
Once we have index of the minimum value, the max area is maximum of following three values.
a) Maximum area in left side of minimum value (not include min value)
b) Maximum area in right side of minimum value (not include min value)
c) Number of bars multiplied by minimum value.

	class Solution {
	public:
	int helper(vector<int>&h, int left, int right){
	if(left==right)
	return h[left];
	int minv=h[left];
	int minIdx=left;
	for(int i=left; i<=right; ++i)
	if(h[i]<minv){
	minv=h[i];
	minIdx=i;
	}
	int v0=helper(h, left, max(left, minIdx-1)); // left part
	int v1=helper(h, min(right, minIdx+1), right); // right part
	int v2=minv*(right-left+1);
	return max(v0, max(v1, v2));
	}
	int largestRectangleArea(vector<int>& heights) {
	if(heights.empty())
	return 0;
	return helper(heights, 0, heights.size()-1);
	}
	};

view raw Q84-2.cpp hosted with ❤ by GitHub

Solution 3: Using stack

For every bar ‘x’, we calculate the area with ‘x’ as the smallest bar in the rectangle. If we calculate such area for every bar ‘x’ and find the maximum of all areas, our task is done. How to calculate area with ‘x’ as smallest bar? We need to know index of the first smaller (smaller than ‘x’) bar on left of ‘x’ and index of first smaller bar on right of ‘x’. Let us call these indexes as ‘left index’ and ‘right index’ respectively.

We traverse all bars from left to right, maintain a stack of bars. Every bar is pushed to stack once. A bar is popped from stack when a bar of smaller height is seen. When a bar is popped, we calculate the area with the popped bar as smallest bar. How do we get left and right indexes of the popped bar – the current index tells us the ‘right index’ and index of previous item in stack is the ‘left index’. Following is the complete algorithm.

	class Solution {
	public:
	int largestRectangleArea(vector<int>& h) {
	stack<int> s;
	h.push_back(0);
	int p=0;
	int largest=0;
	while(!(s.empty()&&p==h.size()-1)){
	if(s.empty()&&p!=h.size()-1){
	s.push(p);
	p++;
	continue;
	}
	while(h[s.top()]<h[p]){
	s.push(p);
	p++;
	}
	int curTop=s.top();
	s.pop();
	int area;
	if(s.empty())
	area=p*h[curTop];
	else
	area=(p-s.top()-1)*h[curTop];
	largest=area>largest? area: largest;
	}
	return largest;
	}
	};

view raw Q84-3.cpp hosted with ❤ by GitHub

Round 2 solution:

	class Solution {
	public:
	int largestRectangleArea(vector<int>& heights) {
	if(heights.empty())
	return 0;
	int area=0;
	stack<int> myStack;
	myStack.push(0);
	for(int i=1; i<heights.size(); i++){
	int top = heights[myStack.top()];
	if(heights[i]>=top)
	myStack.push(i);
	else{
	while(top>heights[i]&&!myStack.empty()){
	myStack.pop();
	if(!myStack.empty())
	area = max(area, (i-myStack.top()-1)*top);
	else
	area = max(area, (i)*top);
	if(!myStack.empty())
	top = heights[myStack.top()];
	}
	myStack.push(i);
	}
	}
	if(!myStack.empty()){
	int d = myStack.top();
	while(!myStack.empty()){
	int top = heights[myStack.top()];
	myStack.pop();
	if(!myStack.empty())
	area = max(area, (d-myStack.top())*top);
	else
	area = max(area, (d+1)*top);
	}
	}
	return area;
	}
	};

view raw Q84.cpp hosted with ❤ by GitHub

LeetCode Q83: Remove Duplicates from Sorted List

Given a sorted linked list, delete all duplicates such that each element appear only once.

For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.

	/**
	* Definition for singly-linked list.
	* struct ListNode {
	* int val;
	* ListNode *next;
	* ListNode(int x) : val(x), next(NULL) {}
	* };
	*/
	class Solution {
	public:
	ListNode* deleteDuplicates(ListNode* head) {
	if(head==NULL)
	return head;
	ListNode* newHead=new ListNode(-1);
	newHead->next=head;
	ListNode* p0=head;
	ListNode* p1=head;
	while(p0->next!=NULL){
	if(p1==NULL){
	p0->next=NULL;
	break;
	}
	if(p0->val==p1->val){
	p1=p1->next;
	}else{
	p0->next=p1;
	p0=p1;
	}
	}
	head=newHead->next;
	delete newHead;
	return head;
	}
	};

view raw Q83.cpp hosted with ❤ by GitHub

Round 2 solution:

	/**
	* Definition for singly-linked list.
	* struct ListNode {
	* int val;
	* ListNode *next;
	* ListNode(int x) : val(x), next(NULL) {}
	* };
	*/
	class Solution {
	public:
	ListNode* deleteDuplicates(ListNode* head) {
	if(head==NULL)
	return NULL;
	ListNode* newHead = new ListNode(head->val+1);
	newHead->next=head;
	ListNode* p = newHead;
	ListNode* n = p->next;
	while(n!=NULL){
	if(p->val!=n->val){
	p=p->next;
	n=p->next;
	}else{
	while(n!=NULL&&n->val==p->val){
	n=n->next;
	}
	p->next=n;
	}
	}
	return newHead->next;
	}
	};

view raw Q83.cpp hosted with ❤ by GitHub

LeetCode Q82: Remove Duplicates from Sorted List II *

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

Solution 1 (Non-recursive)

Compare value of current node and next node. Be careful to check if next node is NULL ahead. Also, be careful of some corner case such as:

[1, 1, 2]: Need to create a new head  node in front of the first node.

[1, 1]: Need to create a new head  node in front of the first node.

[1]: Need to create a new head  node in front of the first node.

[1, 2, 2, 3, 3]: when duplicate numbers are one after another, need to double check whether the first non identical number is a new start of next group of duplicate numbers.

	/**
	* Definition for singly-linked list.
	* struct ListNode {
	* int val;
	* ListNode *next;
	* ListNode(int x) : val(x), next(NULL) {}
	* };
	*/
	class Solution {
	public:
	ListNode* deleteDuplicates(ListNode* head) {
	ListNode* newHead=new ListNode(-1);
	newHead->next=head;
	ListNode* pre=newHead;
	ListNode* cur=head;
	bool dup=false;
	while(cur!=NULL){
	dup=false;
	while(cur!=NULL&&cur->next!=NULL){
	if(cur->val==cur->next->val){
	dup=true;
	cur=cur->next;
	}else
	break;
	}
	cur=(dup==true)?cur->next:cur;
	if(cur==NULL){
	pre->next=cur;
	ListNode* tmpHead=newHead->next;
	delete newHead;
	return tmpHead;
	}
	if(cur->next!=NULL){
	if(cur->val==cur->next->val)
	continue;
	}
	pre->next=cur;
	pre=cur;
	if(cur!=NULL)
	cur=cur->next;
	}
	ListNode* tmpHead=newHead->next;
	delete newHead;
	return tmpHead;
	}
	};

view raw Q82-1.cpp hosted with ❤ by GitHub

Round 2 solution:

	/**
	* Definition for singly-linked list.
	* struct ListNode {
	* int val;
	* ListNode *next;
	* ListNode(int x) : val(x), next(NULL) {}
	* };
	*/
	class Solution {
	public:
	ListNode* deleteDuplicates(ListNode* head) {
	if(head==NULL)
	return NULL;
	ListNode* newHead = new ListNode(head->val+1);
	newHead->next = head;
	ListNode* p=newHead;
	ListNode* n=head;
	ListNode* nn=n->next;
	while(nn!=NULL){
	if(nn->val!=n->val){
	p=p->next;
	n=p->next;
	nn=n->next;
	}else{
	while(nn!=NULL&&n->val==nn->val){
	n=n->next;
	nn=n->next;
	}
	p->next=nn;
	n=p->next;
	nn=n==NULL? NULL:n->next;
	}
	}
	return newHead->next;
	}
	};

view raw Q82-2.cpp hosted with ❤ by GitHub

LeetCode Q81: Search in Rotated Sorted Array II

Follow up for "Search in Rotated Sorted Array":
What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Write a function to determine if a given target is in the array.

	class Solution {
	public:
	bool search(vector<int>& nums, int target) {
	int left=0, right=nums.size()-1;
	while(left<=right){
	int mid=(left+right)/2;
	if(target==nums[mid])
	return true;
	if(nums[mid]>nums[right]){
	if(target < nums[mid] && target >= nums[left])
	right=mid-1;
	else
	left=mid+1;
	}else if(nums[mid] < nums[right]){
	if(target > nums[mid] && target<=nums[right])
	left=mid+1;
	else
	right=mid-1;
	}else if(nums[mid] == nums[right])
	// This is the only difference to the problem of Search in Rotated Array I.
	// With duplicate elements in the array. The problem happens only when the same
	// elements are showing in the same time at left, mid and right. For example:
	// [1, 3, 1, 1, 1] and we look for [3].
	// The idea is to shrink the array to remove duplicate elements on the right of mid.
	right--;
	}
	return false;
	}
	};

view raw Q81SearchSortedArrayII.cpp hosted with ❤ by GitHub

LeetCode Q78: Subsets *

Given a set of distinct integers, nums, return all possible subsets.

Note:

• Elements in a subset must be in non-descending order.
• The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,3], a solution is:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

Solution 1:

	class Solution {
	public:
	vector<vector<int>> subsets(vector<int>& nums) {
	vector<vector<int> > res;
	vector<int> emptyset;
	res.push_back(emptyset);
	if(nums.empty())
	return res;
	sort(nums.begin(), nums.end());
	int s=nums.size();
	int k=1;
	int n=nums.size();
	while(k<=s){
	int i=0;
	vector<int> p(k, -1);
	while(i>=0){
	p[i]++;
	if(p[i]>n-1){
	i--;
	continue;
	}
	if(i==k-1){
	vector<int> tmp(k, -1);
	for(int j=0; j<p.size(); j++)
	tmp[j]=nums[p[j]];
	res.push_back(tmp);
	continue;
	}
	i++;
	p[i]=p[i-1];
	}
	k++;
	}
	return res;
	}
	};

view raw Q78-1.cpp hosted with ❤ by GitHub

Solution 2

	class Solution {
	public:
	vector<vector<int> > subsets(vector<int> &S) {
	vector<vector<int> > res(1, vector<int>());
	sort(S.begin(), S.end());
	for (int i = 0; i < S.size(); i++) {
	int n = res.size();
	for (int j = 0; j < n; j++) {
	res.push_back(res[j]);
	res.back().push_back(S[i]);
	}
	}
	return res;
	}
	};

view raw Q78-2 hosted with ❤ by GitHub

Solution 3 (recursion)

	class Solution {
	public:
	vector<vector<int> > helper(vector<int>& nums, int s){
	vector<vector<int> > res;
	if(s==0){
	vector<int> r0;
	vector<int> r1;
	r1.push_back(nums[s]);
	res.push_back(r0);
	res.push_back(r1);
	return res;
	}
	vector<vector<int> > res0=helper(nums, s-1);
	for(int i=0; i<res0.size(); ++i){
	vector<int> r=res0[i];
	res.push_back(r);
	r.push_back(nums[s]);
	res.push_back(r);
	}
	return res;
	}
	vector<vector<int> > subsets(vector<int>& nums) {
	sort(nums.begin(), nums.end());
	vector<vector<int> > res;
	res=helper(nums, nums.size()-1);
	return res;
	}
	};

view raw Q78-4.cpp hosted with ❤ by GitHub

Solution 4 (Bit manipulation)

	class Solution {
	public:
	vector<vector<int>> subsets(vector<int>& nums) {
	sort(nums.begin(), nums.end());
	int num_subset = pow(2, nums.size());
	vector<vector<int> > res(num_subset, vector<int>());
	for (int i = 0; i < nums.size(); i++)
	for (int j = 0; j < num_subset; j++)
	if ((j >> i) & 1)
	res[j].push_back(nums[i]);
	return res;
	}
	};

view raw Q78-3.cpp hosted with ❤ by GitHub

Round 2 solution:
Idea is simple, similar to Q77, don't wait until the last to save the result, instead we save intermediate results in every recursion.

	class Solution {
	public:
	void helper(vector<vector<int> >& res, vector<int>& nums, vector<int>& curRes, int idx){
	res.push_back(curRes);
	if(curRes.size()==nums.size())
	return;
	for(int i=idx+1; i<nums.size(); i++){
	curRes.push_back(nums[i]);
	helper(res, nums, curRes, i);
	curRes.pop_back();
	}
	}
	vector<vector<int> > subsets(vector<int>& nums) {
	sort(nums.begin(), nums.end());
	vector<vector<int> > res;
	vector<int> curRes;
	res.push_back(curRes);
	for(int i=0; i<nums.size(); i++){
	curRes.push_back(nums[i]);
	helper(res, nums, curRes, i);
	curRes.pop_back();
	}
	return res;
	}
	};

view raw Q78round2.cpp hosted with ❤ by GitHub

LeetCode Q79: Word Search

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

For example,
Given board =

[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.


Solution:
My solution is very conventional that I use two array to track which entries are already on the path and how many neighbors (up, down, left, right) are already accessed.

	bool exist(vector<vector<char> >& board, string word) {
	stack<int> myStack;
	if(board.empty())
	return false;
	int rows=board.size();
	int cols=board[0].size();
	int p=-1;
	vector<int> flag(rows*cols, 0);
	vector<int> nbflag(rows*cols, 0);
	int count=0;
	while(p<rows*cols){
	if(myStack.empty()){
	p++;
	if(p==rows*cols)
	return count==word.length();
	if(board[p/cols][p%cols]!=word[0])
	continue;
	flag.clear();
	myStack.push(p);
	flag[p]=1;
	count++;
	}else{
	int topp=myStack.top();
	int up=(topp-cols)<0? topp:topp-cols;
	int down=(topp+cols)>=rows*cols? topp:topp+cols;
	int left=(topp%cols)==0? topp: topp-1;
	int right=(topp%cols)==cols-1? topp: topp+1;
	if(board[up/cols][up%cols]==word[count]&&flag[up]==0&&nbflag[topp]<1){
	myStack.push(up);
	flag[up]=1;
	count++;
	nbflag[topp]=1;
	continue;
	}
	if(board[down/cols][down%cols]==word[count]&&flag[down]==0&&nbflag[topp]<2){
	myStack.push(down);
	flag[down]=1;
	count++;
	nbflag[topp]=2;
	continue;
	}
	if(board[left/cols][left%cols]==word[count]&&flag[left]==0&&nbflag[topp]<3){
	myStack.push(left);
	flag[left]=1;
	count++;
	nbflag[topp]=3;
	continue;
	}
	if(board[right/cols][right%cols]==word[count]&&flag[right]==0&&nbflag[topp]<4){
	myStack.push(right);
	flag[right]=1;
	count++;
	nbflag[topp]=4;
	continue;
	}
	if(count==word.length())
	return true;
	flag[topp]=0;
	nbflag[topp]=0;
	myStack.pop();
	count--;
	}
	}
	return count==word.length();
	}

view raw Q79WordSearch.cpp hosted with ❤ by GitHub

Round 2 solution:

	class Solution {
	public:
	bool helper(vector<vector<char> >& board, vector<vector<int> >& used, string word, int idx, int row, int col){
	int dir[8]={0, -1, 0, 1, -1, 0, 1, 0};
	if(idx == word.length()-1&&word[idx]==board[row][col])
	return true;
	bool res=false;
	if(word[idx]!=board[row][col])
	return false;
	for(int i=0; i<4; i++){
	int rr = row+dir[i*2];
	int cc = col+dir[i*2+1];
	if(rr<0||rr>board.size()-1||cc<0||cc>board[0].size()-1||used[rr][cc]==1)
	continue;
	used[rr][cc]=1;
	res = res + helper(board, used, word, idx+1, rr, cc);
	used[rr][cc]=0;
	if(res)
	break;
	}
	return res;
	}
	bool exist(vector<vector<char> >& board, string word) {
	if(board.empty())
	return false;
	vector<vector<int> > used(board.size(), vector<int>(board[0].size(), 0));
	for(int i=0; i<board.size(); i++){
	for(int j=0; j<board[0].size(); j++){
	used[i][j]=1;
	bool res = helper(board, used, word, 0, i, j);
	used[i][j]=0;
	if(res)
	return true;
	}
	}
	return false;
	}
	};

view raw Q79-2.cpp hosted with ❤ by GitHub

LeetCode Q77: Combinations

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

For example,
If n = 4 and k = 2, a solution is:

[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

Solution 1: Recusion

	class Solution {
	public:
	vector<vector<int>> helper(int s, int e, int k){
	vector<vector<int> > res;
	if(k==1){
	for(int i=s; i<=e; i++){
	vector<int> r(1, i);
	res.push_back(r);
	}
	return res;
	}
	for(int i=e; i>=s; i--){
	vector<vector<int> > tmp=helper(s, i-1, k-1);
	for(int j=0; j<tmp.size(); j++){
	vector<int> t=tmp[j];
	t.push_back(i);
	res.push_back(t);
	}
	}
	return res;
	}
	vector<vector<int>> combine(int n, int k) {
	vector<vector<int> > res;
	if(n<=0||k<=0)
	return res;
	res=helper(1, n, k);
	}
	};

view raw Q77Combinations.cpp hosted with ❤ by GitHub

Solution 2: Non-recursion

	vector<vector<int>> combine(int n, int k) {
	vector<vector<int> > res;
	vector<int> p(k, 0);
	int i=0;
	while(true){
	if(i<0)
	break;
	p[i]++;
	if(p[i]>n){
	i--;
	continue;
	}
	if(i==k-1){
	res.push_back(p);
	continue;
	}
	i++;
	p[i]=p[i-1];
	}
	return res;
	}

view raw Q77-2.cpp hosted with ❤ by GitHub

Round 2 solution

	class Solution {
	public:
	void helper(vector<vector<int> >& res, vector<int>& curRes, int n, int k, int curK){
	if(curK==k){
	res.push_back(curRes);
	return;
	}
	for(int i=curRes.back()+1; i<=n; i++){
	curRes.push_back(i);
	helper(res, curRes, n, k, curK+1);
	curRes.pop_back();
	}
	}
	vector<vector<int>> combine(int n, int k) {
	vector<vector<int> > res;
	vector<int> curRes;
	for(int i=1; i<=n-k+1; i++){
	curRes.push_back(i);
	helper(res, curRes, n, k, 1);
	curRes.pop_back();
	}
	return res;
	}
	};

view raw Q77.cpp hosted with ❤ by GitHub

LeetCode Q76: Minimum Window Substring (hard*)

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

For example,

S = "ADOBECODEBANC"

T = "ABC"

Minimum window is "BANC".

Note:

If there is no such window in S that covers all characters in T, return the empty string "".

If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.

This is a typical "substring" problem. People gave many beautiful solutions. 

Solution 1

1. Initialize a vector called remaining, which contains the needed matching numbers of each character in s.
2. If there are still characters needed to be contained (increment i in this case), decrease the matching number of that character and check if it is still non-negative. If it is, then it is the character in t, so decrease the total required number required.
3. If there is no more characters required (increment start in this case), record min andleft if a smaller length is found. Recover the number of this character in the remainingand if it is a character in t increase required.

	string minWindow(string s, string t) {
	if (s.size() == 0 || t.size() == 0) return "";
	vector<int> remaining(128, 0);
	// Setup a counter to track how many characters in t are not met.
	int required = t.size();
	for (int i = 0; i < required; i++)
	remaining[t[i]]++;
	// left is the start index of the min-length substring ever found
	int min = INT_MAX, start = 0, left = 0, i = 0;
	while(i <= s.size()) {
	if(required){
	// For each character in s, we decrease remaining array.
	// Since we only initialized remaining array for characters in t,
	// So, all other characters not in t will make remaining array to be negative.
	remaining[s[i]]--;
	// If remaining array is still non-negative, means, character s[i] is a character
	// in t. Use >= to include cases where there are duplicate characters in t.
	if(remaining[s[i]]>=0)
	required--;
	i++;
	}else{
	// When all characters in t are met, check whether the shortest met ever.
	if(i-start<min){
	min=i-start;
	left=start;
	}
	// remove the leftmost character in current substring and move left bound one step ahead.
	remaining[s[start]]++;
	if(remaining[s[start]]>0)
	required++;
	start++;
	}
	}
	return min == INT_MAX? "" : s.substr(left, min);
	}

view raw Q76MinimumWinSubstring1.cpp hosted with ❤ by GitHub

Solution 2 (Similar to solution 1, but more concise.)

	string minWindow(string s, string t) {
	vector<int> map(128,0);
	for(auto c: t) map[c]++;
	int counter=t.size(), begin=0, end=0, d=INT_MAX, head=0;
	while(end<s.size()){
	if(map[s[end++]]-->0) counter--; //in t
	while(counter==0){ //valid
	if(end-begin<d) d=end-(head=begin);
	if(map[s[begin++]]++==0) counter++; //make it invalid
	}
	}
	return d==INT_MAX? "":s.substr(head, d);
	}

view raw Q76-2.cpp hosted with ❤ by GitHub

Template that can solve almost all substring problems

	int findSubstring(string s){
	vector<int> map(128,0);
	int counter; // check whether the substring is valid
	int begin=0, end=0; //two pointers, one point to tail and one head
	int d; //the length of substring
	for() { /* initialize the hash map here */ }
	while(end<s.size()){
	if(map[s[end++]]-- ?){ /* modify counter here */ }
	while(/* counter condition */){
	/* update d here if finding minimum*/
	//increase begin to make it invalid/valid again
	if(map[s[begin++]]++ ?){ /*modify counter here*/ }
	}
	/* update d here if finding maximum*/
	}
	return d;
	}

view raw Q76-3.cpp hosted with ❤ by GitHub

The code of solving Longest Substring with At Most Two Distinct Characters is below:

	int lengthOfLongestSubstringTwoDistinct(string s) {
	vector<int> map(128, 0);
	int counter=0, begin=0, end=0, d=0;
	while(end<s.size()){
	if(map[s[end++]]++==0) counter++;
	while(counter>2) if(map[s[begin++]]--==1) counter--;
	d=max(d, end-begin);
	}
	return d;
	}

view raw Q76-4.cpp hosted with ❤ by GitHub

	int findSubstring(string s){
	vector<int> map(128,0);
	int counter; // check whether the substring is valid
	int begin=0, end=0; //two pointers, one point to tail and one head
	int d; //the length of substring
	for() { /* initialize the hash map here */ }
	while(end<s.size()){
	if(map[s[end++]]-- ?){ /* modify counter here */ }
	while(/* counter condition */){
	/* update d here if finding minimum*/
	//increase begin to make it invalid/valid again
	if(map[s[begin++]]++ ?){ /*modify counter here*/ }
	}
	/* update d here if finding maximum*/
	}
	return d;
	}

view raw Q76-3.cpp hosted with ❤ by GitHub

The code of solving Longest Substring Without Repeating Characters is below:

	int lengthOfLongestSubstring(string s) {
	vector<int> map(128,0);
	int counter=0, begin=0, end=0, d=0;
	while(end<s.size()){
	if(map[s[end++]]++>0) counter++;
	while(counter>0) if(map[s[begin++]]-->1) counter--;
	d=max(d, end-begin); //while valid, update d
	}
	return d;
	}

view raw Q76-5.cpp hosted with ❤ by GitHub

LeetCode Q75: Sort Colors

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note:
You are not suppose to use the library's sort function for this problem.

click to show follow up.

Follow up:
A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0's, 1's, and 2's, then overwrite array with total number of 0's, then 1's and followed by 2's.

Could you come up with an one-pass algorithm using only constant space?

There are four difference solutions, thanks for shichaotan's post on LeetCode:

	// two pass O(m+n) space
	void sortColors(int A[], int n) {
	int num0 = 0, num1 = 0, num2 = 0;
	for(int i = 0; i < n; i++) {
	if (A[i] == 0) ++num0;
	else if (A[i] == 1) ++num1;
	else if (A[i] == 2) ++num2;
	}
	for(int i = 0; i < num0; ++i) A[i] = 0;
	for(int i = 0; i < num1; ++i) A[num0+i] = 1;
	for(int i = 0; i < num2; ++i) A[num0+num1+i] = 2;
	}
	// one pass in place solution
	void sortColors(int A[], int n) {
	int n0 = -1, n1 = -1, n2 = -1;
	for (int i = 0; i < n; ++i) {
	if (A[i] == 0)
	{
	A[++n2] = 2; A[++n1] = 1; A[++n0] = 0;
	}
	else if (A[i] == 1)
	{
	A[++n2] = 2; A[++n1] = 1;
	}
	else if (A[i] == 2)
	{
	A[++n2] = 2;
	}
	}
	}
	// one pass in place solution
	void sortColors(int A[], int n) {
	int j = 0, k = n - 1;
	for (int i = 0; i <= k; ++i){
	if (A[i] == 0 && i != j)
	swap(A[i--], A[j++]);
	else if (A[i] == 2 && i != k)
	swap(A[i--], A[k--]);
	}
	}
	// one pass in place solution
	void sortColors(int A[], int n) {
	int j = 0, k = n-1;
	for (int i=0; i <= k; i++) {
	if (A[i] == 0)
	swap(A[i], A[j++]);
	else if (A[i] == 2)
	swap(A[i--], A[k--]);
	}
	}
	//My Code
	void sortColors(vector<int>& nums) {
	int p0=0, p1=0, p2=nums.size()-1;
	while(p1<=p2){
	if(nums[p1]==0){
	swap(nums[p0++], nums[p1++]);
	continue;
	}
	if(nums[p1]==2){
	swap(nums[p2--], nums[p1]);
	continue;
	}
	if(nums[p1]==1)
	p1++;
	}
	}

view raw Q75.cpp hosted with ❤ by GitHub

LeetCode Q74: Search a 2D Matrix

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted from left to right.
• The first integer of each row is greater than the last integer of the previous row.

For example,

Consider the following matrix:

[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

Given target = 3, return true.

Solution 1:
Binary search, but at the end, you need to search two rows before making a decision. Time complexity O(logm + logn).

	class Solution {
	public:
	bool searchMatrix(vector<vector<int>>& matrix, int target) {
	int l=0, h=matrix.size()-1;
	int rows=matrix.size();
	int cols=matrix[0].size();
	int targetRow=-1;
	while(l<=h){
	int m=(l+h)/2;
	if(target==matrix[m][0])
	return true;
	if(target>matrix[m][0]&&target>matrix[m][cols-1])
	l=m+1;
	if(target>matrix[m][0]&&target<=matrix[m][cols-1]){
	targetRow=m;
	break;
	}
	if(target<matrix[m][0])
	h=m-1;
	}
	if(targetRow==-1)
	return false;
	l=0;
	h=cols-1;
	while(l<=h){
	int m = (l+h)/2;
	if(target == matrix[targetRow][m])
	return true;
	if(target > matrix[targetRow][m])
	l = m+1;
	if(target < matrix[targetRow][m])
	h = m-1;
	}
	return false;
	}
	};

view raw gistfile1.txt hosted with ❤ by GitHub

Solution 2:
Start from up right corner, if larger than move down, if smaller than move left. Time complexity O(m+n)

	bool searchMatrix(vector<vector<int>>& matrix, int target) {
	int m = matrix.size();
	if (m == 0) return false;
	int n = matrix[0].size();
	int i = 0, j = n - 1;
	while (i < m && j >= 0) {
	if (matrix[i][j] == target)
	return true;
	else if (matrix[i][j] > target) {
	j--;
	} else
	i++;
	}
	return false;
	}

view raw Q74-2.cpp hosted with ❤ by GitHub

LeetCode Q73: Set Matrix Zeros

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.

click to show follow up.

Follow up:

Did you use extra space?
A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?

Solution:

Use first row and column to save rows and cols having zeros. But need to check whether the first row and first column initially containing zeros. When filling the matrix, starting from the second row and second column. When finish, back to fill the first row and the first column if they initially contain any zero.

	class Solution {
	public:
	void setZeroes(vector<vector<int> >& matrix) {
	bool row0zero=false;
	for(int j=0; j<matrix[0].size(); j++)
	if(matrix[0][j]==0)
	row0zero=true;
	bool col0zero=false;
	for(int i=0; i<matrix.size(); i++)
	if(matrix[i][0]==0)
	col0zero=true;
	for(int i=0; i<matrix.size(); i++)
	for(int j=0; j<matrix[0].size(); j++)
	if(matrix[i][j]==0){
	matrix[0][j]=0;
	matrix[i][0]=0;
	}
	for(int j=1; j<matrix[0].size(); j++){
	if(matrix[0][j]==0){
	for(int i=1; i<matrix.size(); i++)
	matrix[i][j]=0;
	}
	}
	for(int i=1; i<matrix.size(); i++){
	if(matrix[i][0]==0){
	for(int j=1; j<matrix[0].size(); j++){
	matrix[i][j]=0;
	}
	}
	}
	if(row0zero){
	for(int j=0; j<matrix[0].size(); j++)
	matrix[0][j]=0;
	}
	if(col0zero){
	for(int i=0; i<matrix.size(); i++)
	matrix[i][0]=0;
	}
	}
	};

view raw Q73SetMatrixZeros.cpp hosted with ❤ by GitHub

LeetCode Q72: Edit Distance (hard)

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character
b) Delete a character
c) Replace a character

A classic DP problem.

Suppose DP[ i ][ j ] save the steps needed by converting word1[ 0 : i ] to word2[ 0 : j ]. Let's consider the very last step needed before word1[ 0 : i ] can be converted to word2[ 0 : j ].

If the step is DELETE, means word1[ 0 : i-1 ] = word2[ 0 : j ]. Thus DP[ i ][ j ] = DP[ i -1 ][ j ] + 1.

If the step is INSERT,  means word1[ 0 : i ] = word2[ 0 : j-1]. Thus DP[ i ][ j ] = DP[ i ][ j-1 ] + 1.

if the step is REPLACE, there could be two possibilities.

    First, if word1[ i ] = word2[ j ], then DP[ i ][ j ] = DP[ i-1 ][ j-1 ].

    Second, if word[ i ] != word2[ j ], then DP[ i ][ j ] = DP[ i-1 ][ j-1 ] + 1.

So, by taking minimum of these three possibilities, we get the value of DP[ i ][ j ].

To, initialize the boundary case, from above examples we know, to get DP[ i ][ j ], we basically, need to solve the values on it up left, left, and up. So, we only need to initialize the first row and the first column of the table DP. 

	class Solution {
	public:
	int minDistance(string word1, string word2) {
	vector<vector<int> > dp(word1.length()+1, vector<int>(word2.length()+1, 0));
	for(int i=1; i<=word2.length(); i++)
	dp[0][i]=i;
	for(int j=1; j<=word1.length(); j++)
	dp[j][0]=j;
	for(int i=1; i<=word1.length(); i++){
	for(int j=1; j<=word2.length(); j++){
	int k=(word1[i-1]==word2[j-1])? 0:1;
	dp[i][j]=min(dp[i-1][j]+1, min(dp[i][j-1]+1, dp[i-1][j-1]+k));
	}
	}
	return dp[word1.length()][word2.length()];
	}
	};

view raw Q72EditDistance.cpp hosted with ❤ by GitHub

LeetCode Q71: Simplify Path

Given an absolute path for a file (Unix-style), simplify it.

For example,
path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"







	class Solution {
	public:
	string simplifyPath(string path) {
	string res="";
	stack<string> myStack;
	if(path.empty())
	return res;
	string str="";
	path=path+"/";
	for(int i=0; i<path.length(); ++i){
	char c=path[i];
	if(c=='/'){
	if(str.empty()||str==string(".")) {
	str="";
	continue;
	}
	if(str==string("..")){
	if(!myStack.empty())
	myStack.pop();
	str="";
	continue;
	}
	myStack.push(str);
	str="";
	continue;
	}
	else{
	str=str+path[i];
	}
	}
	while(!myStack.empty()){
	res="/"+myStack.top()+res;
	myStack.pop();
	}
	res=res.empty()? "/":res;
	return res;
	}
	};

view raw Q71SimplifyPath.cpp hosted with ❤ by GitHub

LeetCode Q69: Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x.

Easy question at the first glimpse, however, some corner cases can stop you for a long time. Apparently, should solve it using binary search. However, need to change a bit in a few places than normal binary search. For example, in following code, from line 4 -- line 9, we don't wait until l>=h to stop recursion, because, in that case, we may miss a few right solutions. Also, in line 17 and line 19, we don't increase low bound by one or decrease upper bound by one to ensure the middle position is still included in the next recursion. 

	class Solution {
	public:
	long helper(long l, long h, long x){
	if(l==h-1||l==h){
	if(h*h<=x)
	return h;
	else
	return l;
	}
	long m=(l+h)/2;
	if(m*m==x)
	return m;
	if(m*m<x)
	return helper(m, h, x);
	else
	return helper(l, m, x);
	}
	int mySqrt(int x) {
	if(x<=1)
	return x;
	return helper(long(0), long(x/2), long(x));
	}
	};

view raw Q69Sqrtx.cpp hosted with ❤ by GitHub

Round 2 solution:
Using Newton's method, for details, refer to this post:

	class Solution {
	public:
	int mySqrt(int x)
	{
	long r = x;
	while (r*r > x)
	r = (r + x/r) / 2;
	return r;
	}
	};

view raw Q69-2.cpp hosted with ❤ by GitHub

LeetCode Q65: Valid Number (hard)

Validate if a given string is numeric.

Some examples:
"0" => true
" 0.1 " => true
"abc" => false
"1 a" => false
"2e10" => true

Note: It is intended for the problem statement to be ambiguous. You should gather all requirements up front before implementing one.

My solution is tedious, and I consider three possibilities separately.

	class Solution {
	public:
	bool isInt(string s){
	for(int i=0; i<s.length(); ++i){
	int c=s[i]-'0';
	if(c>9||c<0){
	if((s[i]=='+'||s[i]=='-')&&i==0&&i!=s.length()-1)
	continue;
	return false;
	}
	}
	return true;
	}
	bool isFloat(string s){
	int pofpt=-1;
	for(int i=0; i<s.length(); i++){
	if(s[i]=='.'){
	pofpt=i;
	break;
	}
	}
	if(pofpt==-1||(s.length()==1))
	return false;
	string s0=s.substr(0, pofpt);
	string s1=s.substr(pofpt+1, s.length()-pofpt);
	bool r0=isInt(s0);
	bool r1=isInt(s1);
	if(s0.length()==1&&(s0[0]=='-'||s0[0]=='+'))
	r0=true;
	if(s1[0]=='-'||s1[0]=='+')
	r1=false;
	if((s0[s0.length()-1]=='-'||s0[s0.length()-1]=='+')&&s1.empty())
	return false;
	return r0&&r1;
	}
	bool isSci(string s){
	int pofe=-1;
	for(int i=0; i<s.length(); i++){
	if(s[i]=='e'){
	pofe=i;
	break;
	}
	}
	if(pofe==0||pofe==s.length()-1||pofe==-1)
	return false;
	string s0=s.substr(0, pofe);
	string s1=s.substr(pofe+1, s.length()-pofe);
	bool r0=(isInt(s0)||isFloat(s0));
	bool r1=isInt(s1);
	return r0&&r1;
	}
	bool isNumber(string s) {
	if(s.length()==0)
	return false;
	int p=0;
	for(;p<s.length(); p++){
	if(s[p]!=' ')
	break;
	}
	s.erase(s.begin(), s.begin()+p);
	p=s.length()-1;
	for(; p>=0; p--){
	if(s[p]!=' ')
	break;
	}
	s.erase(s.begin()+p+1, s.end());
	if(s.length()==0)
	return false;
	bool r0=isInt(s);
	bool r1=isFloat(s);
	bool r2=isSci(s);
	return (r0||r1||r2);
	}
	};

view raw Q65ValidNumber.cpp hosted with ❤ by GitHub

A relatively simple solution is given by someone's post on LeetCode's forum:

	class Solution {
	public:
	bool isNumber(string s) {
	int i = 0, n = s.length();
	// Skip the leading spaces
	while (i < n && isspace(s[i])) i++;
	// Skip the sign
	if (s[i] == '+' || s[i] == '-') i++;
	// Check for the following significant parts
	int digits = 0, dots = 0;
	while (i < n && (isdigit(s[i]) || s[i] == '.')) {
	if (isdigit(s[i])) digits++;
	else dots++;
	i++;
	}
	if (digits < 1 || dots > 1) return false;
	if (i == n) return true;
	// Check for the exponential parts
	if (s[i] == 'e') {
	i++;
	if (i == n) return false;
	if (s[i] == '+' || s[i] == '-') i++;
	digits = 0;
	while (i < n && (isdigit(s[i]))) {
	digits++;
	i++;
	}
	if (digits < 1) return false;
	}
	// Skip the trailing spaces
	while (i < n && isspace(s[i])) i++;
	return i == n;
	}
	};

view raw Q65-2.cpp hosted with ❤ by GitHub

LeetCode Q64: Minimum Path Sum

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

	class Solution {
	public:
	int minPathSum(vector<vector<int>>& grid) {
	int m=grid.size();
	int n=grid[0].size();
	vector<vector<int>> dp(m+1,vector<int>(n+1,0));
	for(int i=1; i<=m; i++){
	for(int j=1; j<=n; j++){
	if(dp[i][j]!=0){
	if(i==1){
	dp[i][j]=min(dp[i][j], dp[i][j-1]+grid[i-1][j-1]);
	continue;
	}
	if(j==1){
	dp[i][j]=min(dp[i][j], dp[i-1][j]+grid[i-1][j-1]);
	continue;
	}
	dp[i][j]=min(dp[i][j], min(dp[i-1][j], dp[i][j-1])+grid[i-1][j-1]);;
	}
	else
	{
	if(i==1){
	dp[i][j]=dp[i][j-1]+grid[i-1][j-1];
	continue;
	}
	if(j==1){
	dp[i][j]=dp[i-1][j]+grid[i-1][j-1];
	continue;
	}
	dp[i][j]=min(dp[i-1][j], dp[i][j-1])+grid[i-1][j-1];
	}
	}
	}
	return dp[m][n];
	}
	};

view raw Q64MinimumPathSum.cpp hosted with ❤ by GitHub

Round 2 solution:

	class Solution {
	public:
	int minPathSum(vector<vector<int>>& grid) {
	if(grid.empty())
	return 0;
	int m=grid.size(), n=grid[0].size();
	vector<vector<int> > sums(m+1, vector<int>(n+1, 0));
	for(int i=1; i<=m; i++)
	for(int j=1; j<=n; j++){
	if(i==1)
	sums[i][j]=grid[i-1][j-1]+sums[i][j-1];
	if(j==1)
	sums[i][j]=grid[i-1][j-1]+sums[i-1][j];
	if(i!=1&&j!=1)
	sums[i][j]=grid[i-1][j-1]+min(sums[i-1][j], sums[i][j-1]);
	}
	return sums[m][n];
	}
	};

view raw Q64.cpp hosted with ❤ by GitHub

LeetCode Q63: Unique Paths II

Follow up for "Unique Paths":

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as 1 and 0 respectively in the grid.

For example,

There is one obstacle in the middle of a 3x3 grid as illustrated below.

[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]

The total number of unique paths is 2.

Note: m and n will be at most 100.

	class Solution {
	public:
	int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {
	int m = obstacleGrid.size() , n = obstacleGrid[0].size();
	vector<vector<int>> dp(m+1,vector<int>(n+1,0));
	dp[0][1] = 1;
	for(int i = 1 ; i <= m ; ++i)
	for(int j = 1 ; j <= n ; ++j)
	if(!obstacleGrid[i-1][j-1])
	dp[i][j] = dp[i-1][j]+dp[i][j-1];
	return dp[m][n];
	}
	};

view raw Q63UniquePathII.cpp hosted with ❤ by GitHub

LeetCode Q62: Unique Paths

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

How many possible unique paths are there?

Above is a 3 x 7 grid. How many possible unique paths are there?

Note: m and n will be at most 100.

Recursion, memoization.

	class Solution {
	public:
	int uniquePaths(int m, int n) {
	vector<vector<int>> dp(m+1,vector<int>(n+1,0));
	dp[0][1] = 1;
	for(int i = 1 ; i <= m ; ++i)
	for(int j = 1 ; j <= n ; ++j)
	dp[i][j] = dp[i-1][j]+dp[i][j-1];
	return dp[m][n];
	}
	};

view raw Q62UniquePaths.cpp hosted with ❤ by GitHub

LeetCode Q61: Rotate List

Given a list, rotate the list to the right by k places, where k is non-negative.

For example:
Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.

	/**
	* Definition for singly-linked list.
	* struct ListNode {
	* int val;
	* ListNode *next;
	* ListNode(int x) : val(x), next(NULL) {}
	* };
	*/
	class Solution {
	public:
	ListNode* rotateRight(ListNode* head, int k) {
	if(!head)
	return head;
	int l=0;
	ListNode* p=head;
	ListNode* tail=p;
	while(p!=NULL){
	l++;
	tail=p;
	p=p->next;
	}
	k=k%l;
	p=head;
	for(int i=0; i<l-k-1; ++i){
	p=p->next;
	}
	tail->next=head;
	head=p->next;
	p->next=NULL;
	return head;
	}
	};

view raw Q61RotateList.cpp hosted with ❤ by GitHub

LeetCode Q60: 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):

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"

Given n and k, return the kth permutation sequence.

Note: Given n will be between 1 and 9 inclusive.

    I didn't end up with this solution myself again, sigh... But, my idea is almost there as similar as the code I show below. The idea is not to do the swapping or insertion to the string. Instead, we can directly "compute" the string by looking at how many permutations are available for each given number n. Say, if n=4, and in total it will give 24 permutations, and we are going to pick the k=10 string. To decide which number we should use for the most significant bit, we should look at how many permutations are there for digits that are after the most significant digit. In this example, there 3 digits after the most significant one, and with 3 digits, there will be 6 possible permutations. So, we know the significant digit can not be 1, because there are only 6 possible string in form of 1XXX. Thus, the most signification digit has to be 2, because, 2XXX has another groups of 6 permutations which must contain our target one.

    So on so forth,  we can compute the digit from significant digit to least significant digit.

	class Solution {
	public:
	string getPermutation(int n, int k) {
	int pTable[10] = {1};
	for(int i = 1; i <= 9; i++)
	pTable[i] = i * pTable[i - 1];
	string result;
	vector<string> numSet;
	for(int i=1; i<=9; i++)
	numSet.push_back(to_string(i));
	while(n > 0){
	int temp = (k - 1) / pTable[n - 1];
	result += numSet[temp];
	numSet.erase(numSet.begin() + temp);
	k = k - temp * pTable[n - 1];
	n--;
	}
	return result;
	}
	};

view raw Q60PermutationSequence.cpp hosted with ❤ by GitHub

LeetCode Q58: Length of Last Word

Given a string s consists of upper/lower-case alphabets and empty space characters ' ', return the length of last word in the string.

If the last word does not exist, return 0.

Note: A word is defined as a character sequence consists of non-space characters only.

For example,
Given s = "Hello World",
return 5.

Straightforward solution, just take care of continuous training empty signs.

	class Solution {
	public:
	int lengthOfLastWord(string s) {
	int count=0;
	int emptyMet=1;
	for(int i=0; i<s.length(); ++i){
	char c=s[i];
	if(c==' '){
	emptyMet=1;
	continue;
	}
	if(c!=' '&&emptyMet==1){
	count=1;
	emptyMet=0;
	continue;
	}
	if(c!=' '&&emptyMet==0)
	count++;
	}
	return count;
	}
	};

view raw Q58LegnthOfLastWord.cpp hosted with ❤ by GitHub

Round 2 Solution:

	class Solution {
	public:
	int lengthOfLastWord(string s) {
	int len=0;
	for(int i=0; i<s.length(); i++){
	if(i-1>=0 && s[i-1]==' ' && s[i]!=' ')
	len=0;
	if(s[i]!=' ')
	len++;
	}
	return len;
	}
	};

view raw Q58-2.cpp hosted with ❤ by GitHub

LeetCode Q57: Insert Interval

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].

Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].

This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

One consideration is, the i-place method maybe slower than using extra space for the new vector. So I create a new vector res for result returned.

Linear scan, and keep updating newInterval until intervals[i].start is larger than newInterval.end.

	/**
	* Definition for an interval.
	* struct Interval {
	* int start;
	* int end;
	* Interval() : start(0), end(0) {}
	* Interval(int s, int e) : start(s), end(e) {}
	* };
	*/
	class Solution {
	public:
	vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {
	vector<Interval> res;
	if(intervals.empty()){
	res.push_back(newInterval);
	return res;
	}
	int start=newInterval.start;
	int end=newInterval.end;
	int low=intervals[0].start;
	int high=intervals[0].end;
	int i=0;
	for(; i<intervals.size(); ++i){
	//
	if(intervals[i].start>end){
	res.push_back(newInterval);
	break;
	}
	if((start>=intervals[i].start && start<=intervals[i].end)||
	intervals[i].start>=start && intervals[i].end<=end ||
	end>=intervals[i].start && end<=intervals[i].end){
	start=min(start, intervals[i].start);
	end=max(end, intervals[i].end);
	newInterval.start=start;
	newInterval.end=end;
	continue;
	}
	res.push_back(intervals[i]);
	}
	if(i==intervals.size()){
	res.push_back(newInterval);
	}
	for(; i<intervals.size(); ++i){
	res.push_back(intervals[i]);
	}
	return res;
	}
	};

view raw Q57InsertInterval.cpp hosted with ❤ by GitHub

LeetCode Q54: Spiral Matrix

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

For example,
Given the following matrix:

[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]

You should return [1,2,3,6,9,8,7,4,5].

	class Solution {
	public:
	vector<int> spiralOrder(vector<vector<int>>& matrix) {
	vector<int> result;
	if(matrix.empty())
	return result;
	int m=matrix.size();
	int n=matrix[0].size();
	int u=n, r=m, d=n, l=m;
	int row=0, col=0;
	while(true){
	if(u==0)
	return result;
	int t=col+u;
	for(;col<t; col++){
	result.push_back(matrix[row][col]);
	}
	col--; r--; l--; row++;
	if(r==0)
	return result;
	t=row+r;
	for(;row<t; row++){
	result.push_back(matrix[row][col]);
	}
	row--; d--; u--; col--;
	if(d==0)
	return result;
	t=col-(d-1);
	for(;col>=t; col--){
	result.push_back(matrix[row][col]);
	}
	col++; l--; r--; row--;
	if(l==0)
	return result;
	t=row-(l-1);
	for(;row>=t; row--){
	result.push_back(matrix[row][col]);
	}
	row++; u--; d--; col++;
	}
	}
	};

view raw Q54SpiralMatrix.cpp hosted with ❤ by GitHub

LeetCode Q56: Merge Intervals

Given a collection of intervals, merge all overlapping intervals.

For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

Nothing hard, but need to be careful when using vector::erase.

For example, when erase elements from i to j in A. 

When j>i, to remove [A[i], A[j]]:

erase(a.begin()+i, a.begin()+j+1)

because, erase(A.begin()+i, A.begin()+j), actually only remove [i, j) from A.

When j==i, to remove A[i]:

erase(A.begin()+i)

	/**
	* Definition for an interval.
	* struct Interval {
	* int start;
	* int end;
	* Interval() : start(0), end(0) {}
	* Interval(int s, int e) : start(s), end(e) {}
	* };
	*/
	class Solution {
	public:
	static bool myfunction(Interval& a, Interval& b){
	return a.start<b.start;
	}
	vector<Interval> merge(vector<Interval>& intervals) {
	sort(intervals.begin(), intervals.end(), myfunction);
	if(intervals.size()==0)
	return intervals;
	int startIdx=0;
	int end=intervals[0].end;
	for(int i=1; i<intervals.size(); ++i){
	Interval itv=intervals[i];
	if(itv.start<=end){
	end=max(itv.end, end);
	if(i==intervals.size()-1){
	if(i>startIdx+1)
	intervals.erase(intervals.begin()+startIdx+1, intervals.begin()+i+1);
	else
	intervals.erase(intervals.begin()+startIdx+1);
	intervals[startIdx].end=end;
	return intervals;
	}
	}else{
	//erase
	if(i-1>startIdx+1)
	intervals.erase(intervals.begin()+startIdx+1, intervals.begin()+i);
	if(i-1==startIdx+1)
	intervals.erase(intervals.begin()+startIdx+1);
	intervals[startIdx].end=end;
	i=startIdx+1;
	startIdx=i;
	end=intervals[i].end;
	}
	}
	return intervals;
	}
	};

view raw Q56MergeIntervals.cpp hosted with ❤ by GitHub

Round 2 solution:

	class Solution {
	public:
	static bool myfunction(Interval& a, Interval& b){
	return a.start<b.start;
	}
	vector<Interval> merge(vector<Interval>& intervals) {
	sort(intervals.begin(), intervals.end(), myfunction);
	vector<Interval> res;
	if(intervals.size()==0)
	return res;
	Interval newItv(intervals[0].start, intervals[0].end);
	for(int i=1; i<intervals.size(); i++){
	Interval itv = intervals[i];
	if(itv.start<=newItv.end)
	newItv.end=max(newItv.end, itv.end);
	else{
	res.push_back(newItv);
	newItv.start = itv.start;
	newItv.end = itv.end;
	}
	}
	res.push_back(newItv);
	return res;
	}
	};

view raw Q56-2.cpp hosted with ❤ by GitHub

LeetCode Q55: Jump Game

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

For example:
A = [2,3,1,1,4], return true.

A = [3,2,1,0,4], return false.

Different than Jump game II, this one only need to determine whether can reach the end. The situation where it can not reach the end is because all jumps stops at some cell with 0 possible steps. I use linear scan to solve the question. During scanning, keep updating the furthest  position can reach. Return false when the furthest position stop updating.

	class Solution {
	public:
	bool canJump(vector<int>& nums) {
	int n=nums.size();
	int start=0;
	int end=0;
	int maxend=0;
	while(end<n-1){
	for(int i=start; i<=end; ++i){
	if(i+nums[i]>=n-1)
	return true;
	maxend=max(maxend, i+nums[i]);
	}
	start=end+1;
	if(end==maxend)
	return false;
	end=maxend;
	}
	return true;
	}
	};

view raw Q56JumpGame.cpp hosted with ❤ by GitHub

Round 2 Solution:
Check whether current location can be reached by previous steps.

	class Solution {
	public:
	bool canJump(vector<int>& nums) {
	int farReach=0;
	for(int i=0; i<nums.size(); i++){
	if(farReach<i)
	return false;
	farReach = max(i+nums[i], farReach);
	}
	return true;
	}
	};

view raw Q55-2.cpp hosted with ❤ by GitHub

Calculating the output size of each layer in CNN based on filter parameter

A general formula for this is:

(D+2P-F)/S +1

where D is the input size of one dimension (assuming the input is a D by D matrix), P is the padding, F is the filter size, and S is the stride. Padding is extra pixels outside each side of boundary, stride is the number of pixels skips by filter when scanning the image.

LeetCode Q53: Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
the contiguous subarray [4,−1,2,1] has the largest sum = 6.

	class Solution {
	public:
	int maxSubArray(vector<int>& nums) {
	int maxSum=-INT_MAX;
	int curSum=0;
	int p=0;
	while(p<=nums.size()-1){
	curSum=curSum+nums[p];
	curSum=curSum<0? nums[p]:curSum;
	maxSum=curSum>maxSum? curSum:maxSum;
	curSum=curSum>0? curSum:0;
	p++;
	}
	return maxSum;
	}
	};

view raw Q53MaximumSubarray.cpp hosted with ❤ by GitHub

A neater solution:

	class Solution {
	public:
	int maxSubArray(vector<int>& nums) {
	int maxSum = INT_MIN, currentSum = 0;
	for( int i = 0; i < nums.size(); ++i ){
	maxSum = max( maxSum, currentSum+= nums[i] );
	currentSum = ( currentSum < 0 ) ? 0 : currentSum;
	}
	return maxSum;
	}
	};

view raw Q53-2.cpp hosted with ❤ by GitHub

Round 2 solution:
This solution will take into account a case where all numbers are negative.

	class Solution {
	public:
	int maxSubArray(vector<int>& nums) {
	if(nums.empty())
	return 0;
	int maxSum=nums[0];
	int curSum=0;
	for(int i=0; i<nums.size(); i++){
	curSum = curSum + nums[i];
	maxSum = max(curSum, maxSum);
	curSum = curSum<0? 0:curSum;
	}
	return maxSum;
	}
	};

view raw Q53.cpp hosted with ❤ by GitHub

An overview of gradient descent optimization algorithms

Recently, a post that summarize almost every gradient descent optimization algorithms used in deep neural network has been created by Sebastian Ruder at:
http://sebastianruder.com/optimizing-gradient-descent/
Thanks for his effort, it is helpful.

LeetCode Q49: Group Anagrams

Given an array of strings, group anagrams together.

For example, given: ["eat", "tea", "tan", "ate", "nat", "bat"],
Return:

[
  ["ate", "eat","tea"],
  ["nat","tan"],
  ["bat"]
]

Use sort and hash. The key used in hash is in format C1X1C2X2... where C is a character, X is the number of C showing up in the string.

	class Solution {
	public:
	vector<vector<string> > groupAnagrams(vector<string>& strs){
	vector<vector<string> > r;
	unordered_map<string, int> myMap;
	unordered_map<string, int>::const_iterator itr;
	sort(strs.begin(), strs.end());
	for(int i=0; i<strs.size(); ++i){
	string s = strs[i];
	vector<int> f(26, 0);
	for(int j=0; j<s.length(); ++j){
	char c=s[j];
	f[c-'a']++;
	}
	string m="";
	for(int j=0; j<f.size(); ++j){
	if(f[j]!=0){
	char c='a'+j;
	m=m+string(1, c)+to_string(f[j]);
	}
	}
	itr=myMap.find(m);
	if(itr!=myMap.end()){
	int id=itr->second;
	r[id].push_back(s);
	}else{
	vector<string> ng;
	ng.push_back(s);
	r.push_back(ng);
	myMap[m]=r.size()-1;
	}
	}
	return r;
	}
	};

view raw Q49GroupAngrams.cpp hosted with ❤ by GitHub

LeetCode Q50: Pow(x, n)

Iplement pow(x, n)

Easy question can sometimes be very hard and this question is typically belongs to this family. x is integer, n is double. As usual, you should come up with an idea of solving it using recursion. Further, you may want to use memoization when you aware your solution can hardly finish running itself in required time. By this point, I tried to use vector to record the value of every possible pow(x, n) for n starting from 1 to n. However, this fails when n is very very large, say INT_MAX. Because the size is excess the maximum size that is allowed to allocate memory for vector. So, looks like we have to dynamically allocate memory for each subsolution which leads to an idea of using unordered_map and BOOM~, we are done.

	class Solution {
	public:
	double helper(double x, int n, unordered_map<int, double>& myMap){
	double r=0;
	unordered_map<int, double>::const_iterator itr;
	if(n<=3){
	r=pow(x, n);
	myMap[n]=r;
	return r;
	}
	if(n%2==0){
	itr=myMap.find(n/2);
	if(itr!=myMap.end())
	r=myMap[n/2]*myMap[n/2];
	else
	r=helper(x, n/2, myMap)*helper(x, n/2, myMap);
	myMap[n]=r;
	}else{
	itr=myMap.find((n-1)/2);
	if(itr!=myMap.end())
	r=myMap[(n-1)/2]*myMap[(n-1)/2]*x;
	else
	r=helper(x, (n-1)/2, myMap)*helper(x, (n-1)/2, myMap)*x;
	myMap[n]=r;
	}
	return r;
	}
	double myPow(double x, int n) {
	if(n<0){
	x=1/x;
	n=n*-1;
	}
	if(n==0)
	return 1;
	unordered_map<int, double> myMap;
	double r=helper(x, n, myMap);
	return r;
	}
	};

view raw Q50Pow.cpp hosted with ❤ by GitHub

Round 2 Solution: Be careful of negative power and overflow. I am also suppressed by how much I improve my code by comparing this solution with my previous one. Practice makes perfect!!!

	class Solution {
	public:
	double myPow(double x, int n) {
	if(n==0)
	return 1;
	double res;
	if(n<0){
	long _n = -1*long(n);
	res=_n%2==0? 1/myPow(x*x, _n/2):1/(myPow(x*x, _n/2)*x);
	}
	else
	res=n%2==0? myPow(x*x, n/2):myPow(x*x, n/2)*x;
	return res;
	}
	};

view raw Q50-1.cpp hosted with ❤ by GitHub