Monthly Archives: February 2017

LeetCode Insertion Sort List

LeetCode Insertion Sort List
Sort a linked list using insertion sort.


对一个链表进行插入排序。
简单题,每次从原链表中断一个节点下来,然后在新的有序链表中线性查找插入的位置。这里有个技巧,有可能链表的第一个节点很大,后续节点需要插入表头;也可能后续节点很大,需要插入表尾;还可能是不大不小,插入中间。情况比较多,为了方便统一代码形式,可以在新的有序链表的表头插入一个INT_MIN的最小节点,这样所有代码都统一了,也不容易出错。
完整代码如下:

class Solution {
public:
	ListNode* insertionSortList(ListNode* head) {
		if (head == NULL || head->next == NULL)return head;
		ListNode *newHead = new ListNode(INT_MIN);
		newHead->next = head;
		head = head->next;
		newHead->next->next = NULL;
		while (head) {
			ListNode *insertPos = newHead->next, *pre = newHead;
			while (insertPos&&insertPos->val < head->val) {
				insertPos = insertPos->next;
				pre = pre->next;
			}
			ListNode *tmp = head;
			head = head->next;
			tmp->next = insertPos;
			pre->next = tmp;
		}
		return newHead->next;
	}
};

本代码提交AC,用时59MS。

LeetCode Construct Binary Tree from Inorder and Postorder Traversal

LeetCode Construct Binary Tree from Inorder and Postorder Traversal
Given inorder and postorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.


本题要根据树的中序和后序遍历结果,重构出树的结构。
有了之前LeetCode Construct Binary Tree from Preorder and Inorder Traversal根据前序和中序重构树的算法,这一题就是照猫画虎了。因为后序遍历是最后一个数为根节点,和前序遍历其实没本质差别。找准inorder和postorder下标的起止位置就可以开始写代码了:

class Solution {
private:
	TreeNode* dfs(vector<int>& inorder, vector<int>& postorder, int inL, int inR, int postL, int postR, unordered_map<int, int>& hash) {
		if (inL > inR || postL > postR)return NULL;
		TreeNode* root = new TreeNode(postorder[postR]);
		int idx = hash[root->val];
		root->right = dfs(inorder, postorder, inL + 1, inR, postR - (inR - idx), postR - 1, hash);
		root->left = dfs(inorder, postorder, inL, idx - 1, postL, postR - (inR - idx) - 1, hash);
		return root;
	}
public:
	TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
		if (inorder.size() == 0)return NULL;
		unordered_map<int, int> hash;
		for (int i = 0; i < inorder.size(); ++i) {
			hash[inorder[i]] = i;
		}
		return dfs(inorder, postorder, 0, inorder.size() - 1, 0, postorder.size() - 1, hash);
	}
};

本代码提交AC,用时16MS。

LeetCode Construct Binary Tree from Preorder and Inorder Traversal

LeetCode Construct Binary Tree from Preorder and Inorder Traversal
Given preorder and inorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.


根据树的先序遍历和中序遍历结果,重构这棵树。
其实大学的时候就有这样的作业,如果在纸上做,还是很简单的,但要实现成代码,稍微有点难理清这里的关系。
我们先来看一个纸上的解题过程,假设有下面这样一棵树:

        3
     /     \
    9       20
  /  \     /   \
 1    2  15    17
  • 先序遍历结果为:3, 9, 1, 2, 20, 15, 17
  • 中序遍历结果为:1, 9, 2, 3, 15, 20, 17

首先我们可以根据先序遍历结果找到根节点3,然后在中序遍历中看看3所处的位置,那么3左边的就是左孩子节点,右边的就是右孩子节点。我们在中序遍历中看看3左边有3个节点,说明3的左子树共有3个节点,同理右子树有3个节点。所以我们在先序遍历中也能知道3后面的3个节点是左子树,再后面3个节点是右子树,这样就把两个遍历结果分成了两部分:

  • 先序遍历结果为:3, 9, 1, 2, 20, 15, 17
  • 中序遍历结果为:1, 9, 2, 3, 15, 20, 17

在红色部分递归就是3的左子树,在蓝色部分递归就是3的右子树。
纸上解题好说,但是代码实现,我开始还把自己搞糊涂了,代码很复杂,后来参考了这位大神的博客,代码好简洁易懂,赞一个:

class Solution {
private:
	TreeNode* dfs(vector<int>& preorder, vector<int>& inorder, int preL, int preR, int inL, int inR, unordered_map<int, size_t>& hash) {
		if (preL > preR || inL > inR)return NULL;
		TreeNode* root = new TreeNode(preorder[preL]);
		size_t idx = hash[root->val];
		root->left = dfs(preorder, inorder, preL + 1, idx - inL + preL, inL, idx - 1, hash);
		root->right = dfs(preorder, inorder, idx - inL + preL + 1, preR, idx + 1, inR, hash);
		return root;
	}
public:
	TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
		if (preorder.size() == 0)return NULL;
		unordered_map<int, size_t> hash;
		for (size_t i = 0; i < inorder.size(); ++i) {
			hash[inorder[i]] = i;
		}
		return dfs(preorder, inorder, 0, preorder.size() - 1, 0, inorder.size() - 1, hash);
	}
};

本代码提交AC,用时16MS。
代码中有两点需要注意的,一是为了在中序遍历中快速找到根节点,提前对中序遍历结果hash了,因为题目中说了不会有重复元素;二是在dfs递归的时候,要算好下标的起止位置,一定不要弄错了,特别是preorder在左右子树中的起止位置。

LeetCode Binary Tree Zigzag Level Order Traversal

LeetCode Binary Tree Zigzag Level Order Traversal
Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).
For example:
Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its zigzag level order traversal as:

[
  [3],
  [20,9],
  [15,7]
]

本题还是树的层次遍历,但是稍微有点不一样,要求奇数层从左往右输出,偶数层从右往左输出。常规的层次遍历使用BFS实现,即队列,这里要求颠倒顺序,马上想到用堆栈。
维护一个left2right布尔变量,当tru时,把孩子从左往右压栈,这样下一层的输出顺序就是从右往左了;当为false时相反。这里我们还需要用到两个堆栈,分别保存当前层和下一层的结果。
talk is cheap, show you the code!

class Solution {
public:
	vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
		vector<vector<int>> ans;
		if (!root)return ans;
		bool left2right = true;
		stack<TreeNode*> stk;
		stk.push(root);
		while(!stk.empty()) {
			stack<TreeNode*> stk2;
			vector<int> cand;
			size_t n = stk.size();
			for (size_t i = 0; i < n; ++i) {
				TreeNode* top = stk.top();
				stk.pop();
				if (!top)continue;
				cand.push_back(top->val);
				if (left2right) {
					stk2.push(top->left);
					stk2.push(top->right);
				}
				else {
					stk2.push(top->right);
					stk2.push(top->left);
				}
			}
			left2right = !left2right;
			if (!cand.empty()) ans.push_back(cand);
			stk = stk2;
		}
		return ans;
	}
};

本代码提交AC,用时6MS。

LeetCode Intersection of Two Linked Lists

LeetCode Intersection of Two Linked Lists
Write a program to find the node at which the intersection of two singly linked lists begins.
For example, the following two linked lists:

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗
B:     b1 → b2 → b3

begin to intersect at node c1.
 
Notes:

  • If the two linked lists have no intersection at all, return null.
  • The linked lists must retain their original structure after the function returns.
  • You may assume there are no cycles anywhere in the entire linked structure.
  • Your code should preferably run in O(n) time and use only O(1) memory.

给定两个链表,如果这两个链表在某个点相交,并且此后合并为一个链表,要找出这个交点;如果不想交,返回NULL。
简单的方法是,如果两个链表相交,比如题图在c1相交,则对于两个链表,从相交点往后长度是一样的,所以我们可以先求出两个链表的长度,假设长度差是delta,则较长链表先前进delta步,此时长短链表的往后的路都是一样长了,这样两个链表一起走,如果发现有相等的节点,则是相交节点,否则两个链表不相交。
本思路代码如下:

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    	int len1 = 0, len2 = 0;
    	ListNode *h1 = headA, *h2 = headB;
    	while(h1){
    		++len1;
    		h1 = h1->next;
    	}
    	while(h2){
    		++len2;
    		h2 = h2->next;
    	}
    	h1 = headA;
    	h2 = headB;
    	if(len1 > len2){
    		while(len1 > len2){
    			h1 = h1->next;
    			--len1;
    		}
    	} else if(len2 > len1) {
    		while(len2 > len1){
    			h2 = h2->next;
    			--len2;
    		}
    	}
    	while(h1 && h2 && h1 != h2){
    		h1 = h1->next;
    		h2 = h2->next;
    	}
    	if(!h1 || !h2)return NULL;
    	else return h1;
    }
};

本代码提交AC,用时39MS。
还有一种思路很巧妙,参考:http://www.cnblogs.com/yuzhangcmu/p/4128794.html
具体是这样的,比如题目中的例子,假设指针pA和pB分别指向A,B两个链表,两个指针同时不断的一步一步走,当pA走到结尾时,pA指向B链表表头开始走,同理当pB走到结尾时,pB指向A链表表头开始走。不断的走,当pA和pB指向同一个节点时,就是那个相交的节点。这个很巧妙呀,当pA和pB走到相交点时,他们走过的路程其实是相等的,比如题目中,他们都走了9个节点后相遇了。
代码如下:

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    	if(headA == NULL || headB == NULL) return NULL;
    	ListNode *h1 = headA, *h2 = headB;
    	ListNode *tail1 = NULL, *tail2 = NULL;
    	while(true){
    		if(h1 == NULL) h1 = headB;
    		if(h2 == NULL) h2 = headA;
    		if(h1->next == NULL) tail1 = h1;
			if(h2->next == NULL) tail2 = h2;
    		if(tail1 != NULL && tail2 != NULL && tail1 != tail2) return NULL;
    		if(h1 == h2) return h1;
    		h1 = h1->next;
    		h2 = h2->next;
    	}
    }
};

本代码提交AC,用时36MS。

LeetCode Word Ladder

LeetCode Word Ladder
Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

  1. Only one letter can be changed at a time.
  2. Each transformed word must exist in the word list. Note that beginWord is not a transformed word.

For example,
Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]
As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.
Note:

  • Return 0 if there is no such transformation sequence.
  • All words have the same length.
  • All words contain only lowercase alphabetic characters.
  • You may assume no duplicates in the word list.
  • You may assume beginWord and endWord are non-empty and are not the same.

UPDATE (2017/1/20):
The wordList parameter had been changed to a list of strings (instead of a set of strings). Please reload the code definition to get the latest changes.


很有意思的一个题。给定两个单词beginWord和endWord,以及一个字典数组,问从beginWord到endWord,最少需要多少次变换,每次只能变换一个字母,而且变换的单词都必须存在于字典数组中。
很明显是一个BFS题,从beginWord开始广搜,直到第一次搜到endWord时停止,此时走过的变换数就是最小变换数。因为广搜会搜索所有的空间,那么第一次到达endWord也就是最早到达的。
当然BFS的题也都能用DFS来做,但是DFS显然会慢,想想便知,DFS必须搜索完一条完整的路径才能知道结果,才能进入下一条路径开始搜索;而BFS是每条路径同步进行,只要有一条路径到达,就结束搜索。
常规的BFS代码如下:

typedef struct Item {
	string cur;
	string used;
	int step;
	Item(string c, string u, int s) :cur(c), used(u), step(s) {};
};
class Solution {
public:
	bool differOne(const string &s1, const string &s2) {
		int cnt = 0;
		for (size_t i = 0; i < s1.size(); ++i) {
			if (s1[i] != s2[i]) {
				++cnt;
				if (cnt > 1)return false;
			}
		}
		return cnt == 1;
	}
	int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
		size_t n = wordList.size();
		queue<Item> q;
		Item it(beginWord, string(n, '0'), 1);
		q.push(it);
		while (!q.empty()) {
			Item t = q.front();
			q.pop();
			if (t.cur == endWord)return t.step;
			for (size_t i = 0; i < n; ++i) {
				if (t.used[i] == '0'&&differOne(t.cur, wordList[i])) {
					string newUsed = t.used;
					newUsed[i] = '1';
					Item tmp(wordList[i], newUsed, t.step + 1);
					q.push(tmp);
				}
			}
		}
		return 0;
	}
};

本代码很好理解,定义一个结构体Item,cur为当前到达的单词,用一个和wordList大小相同的字符串used表示走到cur时走过的单词,step表示当前走过的步数。很可惜,这个版本的代码提交MLE,超空间了。肯定是因为Item这个结构体太大了,两个string,一个int。
后来想到一个优化的方法,当某条路径path1走到单词cur时,其他路径就没必要再经过cur了,因为一旦经过cur,必定后续步骤和path1后续要走的路径就相同了,造成了重复搜索。所以我们走过每个单词时,可以直接将该单词置空,这样后续就不会再走该路了,同时这样也不需要Item结构体了。新版代码如下:

class Solution {
public:
	bool differOne(const string &s1, const string &s2) {
		int cnt = 0;
		for (size_t i = 0; i < s1.size(); ++i) {
			if (s1[i] != s2[i]) {
				++cnt;
				if (cnt > 1)return false;
			}
		}
		return cnt == 1;
	}
	int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
		size_t n = wordList.size();
		queue<string> q;
		q.push(beginWord);
		int step = 1;
		while (!q.empty()) {
			size_t len = q.size();
			for (size_t i = 0; i < len; ++i) {
				string t = q.front();
				q.pop();
				if (t == endWord)return step;
				for (size_t j = 0; j < wordList.size(); ++j) {
					if (wordList[j] != ""&&differOne(t, wordList[j])) {
						q.push(wordList[j]);
						wordList[j] = "";
					}
				}
			}
			++step;
		}
		return 0;
	}
};

本代码提交AC,用时632MS。

LeetCode Word Search

LeetCode 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.


给定一个字符面板和一个单词,问能否在该面板中搜索到该单词,搜索路径只能水平或垂直。
简单的深度搜索题,首先找到第一个字符的起始位置,然后深度往该字符的上下左右搜,只要有一个true就返回true,否则重置标记位,返回false。
完整代码如下:

class Solution {
private:
	bool dfs(vector<vector<char>>& board, vector<vector<char>>& mark, int row, int col, string& word, int step) {
		if (board[row][col] != word[step])return false;
		if (step == word.size() - 1)return true;
		mark[row][col] = 1;
		if (row - 1 >= 0 && mark[row - 1][col] == 0) {
			bool ans = dfs(board, mark, row - 1, col, word, step + 1);
			if (ans)return true;
		}
		if (row + 1 < board.size() && mark[row + 1][col] == 0) {
			bool ans = dfs(board, mark, row + 1, col, word, step + 1);
			if (ans)return true;
		}
		if (col - 1 >= 0 && mark[row][col - 1] == 0) {
			bool ans = dfs(board, mark, row, col - 1, word, step + 1);
			if (ans)return true;
		}
		if (col + 1 <board[0].size() && mark[row][col + 1] == 0) {
			bool ans = dfs(board, mark, row, col + 1, word, step + 1);
			if (ans)return true;
		}
		mark[row][col] = 0;
		return false;
	}
public:
	bool exist(vector<vector<char>>& board, string word) {
		if (word.size() == 0)return true;
		int m = board.size();
		if (m == 0)return false;
		int n = board[0].size();
		if (n == 0)return false;
		vector<vector<char>> mark(m, vector<char>(n, 0));
		for (int i = 0; i < m; ++i) {
			for (int j = 0; j < n; ++j) {
				if (board[i][j] == word[0] && dfs(board, mark, i, j, word, 0))return true;
			}
		}
		return false;
	}
};

本代码提交AC,用时9MS,击败95.63%的人。

LeetCode Insert Interval

LeetCode 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].


一个已经排好序的区间数组,现在要插入一个新的区间,并且如果能合并则需要合并。最简单的方法就是把新加入的区间和原有区间一起排个序,然后统一合并,问题就转换为LeetCode Merge Intervals了。
但是原有区间数组是已经按start排序了,所以有更简单的办法。我们可以分三个过程插入新的区间,首先把明显小于新区间的区间放到结果数组中,然后处理所有可能和新区间有overlap的区间,不断合并并更新新区间,直到无法再合并时,把新区间加入结果数组中,最后把明显大于新区间的区间放到结果数组中。
完整代码如下:

class Solution {
public:
	vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {
		vector<Interval> ans;
		int i = 0, n = intervals.size();
		while (i < n&&intervals[i].end < newInterval.start)ans.push_back(intervals[i++]);
		while (i < n&&newInterval.end >= intervals[i].start) {
			newInterval.start = min(newInterval.start, intervals[i].start);
			newInterval.end = max(newInterval.end, intervals[i].end);
			++i;
		}
		ans.push_back(newInterval);
		while (i < n)ans.push_back(intervals[i++]);
		return ans;
	}
};

本代码提交AC,用时13MS。

LeetCode Merge Intervals

LeetCode 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].


给定一个区间数组,也就是数组中保存的是一个个的区间[s,t],要求把数组中所有有overlap的区间合并起来。
简单题,先给数组排个序,然后只要看相邻的两个区间是否有重复就好了。排序的规则是先比较start,如果start相等,再比较end。
其实这个区间完全可以用pair来存,但是题目用一个自定义的Interval结构体存储。有两种方法可以对自定义结构体(或类)排序,一是重载Interval的小于<比较运算符,这样就可以直接sort(vector.begin(),vector.end())了,但是这样改变了Interval;还有一种方法是不改变Interval,自定义一个comp比较函数,传递给sort算法的第三个参数。
代码如下:

bool comp(const Interval& i, const Interval& j) {
	return (i.start < j.start) || ((i.start == j.start) && (i.end < j.end));
}
class Solution {
public:
	vector<Interval> merge(vector<Interval>& intervals) {
		if (intervals.size() == 0)return vector<Interval>();
		sort(intervals.begin(), intervals.end(), comp);
		vector<Interval> ans = { intervals[0] };
		for (int i = 1; i < intervals.size(); ++i) {
			if (intervals[i].start <= ans.back().end) {
				ans.back().end = max(ans.back().end, intervals[i].end);
			}
			else {
				ans.push_back(intervals[i]);
			}
		}
		return ans;
	}
};

本代码提交AC,用时12MS。

LeetCode Jump Game II

LeetCode Jump Game II
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.
Your goal is to reach the last index in the minimum number of jumps.
For example:
Given array A = [2,3,1,1,4]
The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)
Note:
You can assume that you can always reach the last index.


上一题是问能否跳到数组右边,本题问最少需要多少跳能跳到数组右边,第一反应是DP。
设dp[i]表示从位置i跳到数组右边最少需要的跳数,则dp[n-1]=0,dp[0]就是最终结果。此时我们需要从数组右边往左边遍历,假设dp[i+1,...,n-1]都求出来了,现在要求dp[i]。站在位置i,我们最远能跳到i+A[i],所以我们就看看从i跳到哪个j\in[i,i+A[i]]能获得最少的跳数,从i跳到j需要增加一跳,所以递推式就是

dp[i]=min\{dp[j]+1\},\quad j\in[i+1,i+A[i]]


这种思路的代码如下:

class Solution {
public:
	int jump(vector<int>& nums) {
		int n = nums.size();
		if (n <= 1)return 0;
		int maxJump = n - 1;
		vector<int> dp(n, 0);
		for (int i = n - 2; i >= 0; --i) {
			int curMinJump = maxJump;
			for (int j = i + 1; j <= nums[i] + i&&j < n; ++j) {
				curMinJump = min(curMinJump, dp[j] + 1);
			}
			dp[i] = curMinJump;
		}
		return dp[0];
	}
};

可惜,本代码提交TLE,在最后一个大数据集上超时了。但是我还是觉得DP方法是一个基本法,而且如果要求出最小跳的路径,也很方便,如下代码,打印的时候,从pre[n-1]不断找前驱位置就好。

class Solution {
public:
	int jump(vector<int>& nums) {
		int n = nums.size();
		if (n <= 1)return 0;
		int maxJump = n - 1;
		vector<int> dp(n, 0), pre(n, 0);
		for (int i = n - 2; i >= 0; --i) {
			int curMinJump = maxJump, k = 0;
			for (int j = i + 1; j <= nums[i] + i&&j < n; ++j) {
				if (dp[j] + 1 < curMinJump) {
					curMinJump = dp[j] + 1;
					k = j;
				}
			}
			dp[i] = curMinJump;
			pre[k] = i; // 从i跳到k能获得最小跳数
		}
		return dp[0];
	}
};

讨论区看到一个O(n)的解法,很厉害。思路和上一题LeetCode Jump Game很类似,依旧维护一个当前能跳到的最远位置curFarthest,同时维护一个当前跳能跳到的范围[curBegin, curEnd],一旦i超过了curEnd,说明应该开启下一跳了,同时更新curFarthest。
这种算法的思路很巧妙,他不管你当前跳到底跳到哪里,只管你能够跳到的范围,一旦走出这个范围,就必须开启下一跳了。代码如下:

class Solution {
public:
	int jump(vector<int>& nums) {
		int jumps = 0, curEnd = 0, curFarthest = 0;
		for (int i = 0; i < nums.size() - 1; ++i) {
			curFarthest = max(curFarthest, i + nums[i]);
			if (i == curEnd) {
				curEnd = curFarthest;
				++jumps;
				if (curEnd >= nums.size() - 1)break;
			}
		}
		return jumps;
	}
};

本代码提交AC,用时22MS。第10行是增加的提前结束的代码。
参考: