Monthly Archives: October 2016

LeetCode Contains Duplicate II

LeetCode Contains Duplicate II
Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j]and the difference between i and j is at most k.


本题是LeetCode Contains Duplicate的升级版,要求是判断是否有距离不超过k的两个相同的数。
首先想到暴力方法,一种是直接两层长度为n的循环,判断是否有距离不超过k的两个相等的数,另一种是外层循环为n,内层只要循环长度k,因为即使超过k有相等数的,也不符合题意。尝试之后显然超时。
然后我想到了另一种方法,把数组中所有相同数字的下标都放到一个桶里,后续再在这个桶里看是否有距离不超过k的两个下标对;如果桶里只有一个下标,说明这个下标对应的数没有重复出现,直接continue。完整代码如下:

class Solution {
public:
	bool containsNearbyDuplicate(vector<int>& nums, int k) {
		if (nums.size() == 0)return false;
		unordered_map<int, int> hash_table;
		int distinct_cnt = 1; // 相异元素的个数
		vector<vector<int>> duplicate_indices = { {} }; // 跳过第0个桶
		for (int i = 0; i < nums.size(); i++) {
			if (hash_table[nums[i]] == 0) {
				hash_table[nums[i]] = distinct_cnt++;
				duplicate_indices.push_back({ i });
			}
			else {
				duplicate_indices[hash_table[nums[i]]].push_back(i); // 把相同元素的下标都放到一个桶里
			}
		}
		for (int i = 1; i < duplicate_indices.size(); i++) { // 查每个桶
			if (duplicate_indices[i].size() < 2)continue;
			for (int u = 0; u < duplicate_indices[i].size() - 1; u++) {
				for (int v = u + 1; v < duplicate_indices[i].size(); v++) {
					if (duplicate_indices[i][v] - duplicate_indices[i][u] <= k)return true;
				}
			}
		}
		return false;
	}
};

本代码提交AC,用时46MS。
后来看欣欣的解法LeetCode Contains Duplicate II,发现这个解法好厉害啊,用到了高级的unordered_set,之前只用过unordered_map,赶紧来学习一下。
她的思路是这样的,题目要求相同元素的距离不超过k,则我们维护一个长度为k的滑动窗口,把这个窗口里的所有数都hash到unordered_set里,后续每来一个元素,去这个hash_set里查之前是否出现过,因为我们的hash_set里只保留了前k个元素,所以如果hash_set查到了,他们的距离肯定是不超过k的。这种解法真是漂亮!完整代码如下:

class Solution {
public:
	bool containsNearbyDuplicate(vector<int>& nums, int k) {
		if (nums.size() == 0 || k <= 0)return false;
		if (k >= nums.size())k = nums.size() - 1;
		unordered_set<int> hash_set;
		for (int i = 0; i < nums.size(); i++) {
			if (i > k)hash_set.erase(nums[i - k - 1]); // 滑动窗口,删掉窗口第一个元素
			if (hash_set.find(nums[i]) != hash_set.end())return true;
			hash_set.insert(nums[i]); // 把新元素插入窗口
		}
		return false;
	}
};

本代码提交AC,用时29MS,果然比我的速度快,厉害~
二刷。用一个hash表记录每个数最近出现的下标,如果新来一个数,之前在hash表中出现过,则看看下标之差是否小于等于k,是则返回true;否则更新hash。
思路非常简单,代码如下:

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_map<int,int> hash;
        for(int i = 0; i < nums.size(); ++i) {
            if(hash.find(nums[i]) != hash.end() && i - hash[nums[i]] <= k) return true;
            hash[nums[i]] = i;
        }
        return false;
    }
};

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

LeetCode Contains Duplicate

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


判断一个数组中是否有重复元素,简单题,hash即可。沾欣欣的光,也来用用unordered_map 🙂
完整代码如下:

class Solution {
public:
	bool containsDuplicate(vector<int>& nums) {
		unordered_map<int, int> hash_table;
		for (int i = 0; i < nums.size(); i++) {
			hash_table[nums[i]]++; // 如果元素不存在hash_table中,会自动插入,并赋值为0,++之后为1
			if (hash_table[nums[i]] > 1)return true;
		}
		return false;
	}
};

本代码提交AC,用时49MS。
当然也可以用set或map这种树结构来实现,如果知道数据范围,也可以用桶来实现。

LeetCode Sum Root to Leaf Numbers

LeetCode Sum Root to Leaf Numbers
Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.
An example is the root-to-leaf path 1->2->3 which represents the number 123.
Find the total sum of all root-to-leaf numbers.
For example,

    1
   / \
  2   3

The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Return the sum = 12 + 13 = 25.


睡前刷一题。把每一条从根到叶子的路径经过的数字拼起来组成一个数,求这些数的和。
简单的DFS题,不解释。完整代码如下:

class Solution {
public:
	void dfs(int& sum, int sub_sum, TreeNode* root) {
		if (root->left == NULL&&root->right == NULL) {
			sum += (sub_sum * 10 + root->val);
			return;
		}
		if (root->left != NULL)dfs(sum, sub_sum * 10 + root->val, root->left);
		if (root->right != NULL)dfs(sum, sub_sum * 10 + root->val, root->right);
	}
	int sumNumbers(TreeNode* root) {
		if (root == NULL)return 0;
		int sum = 0;
		dfs(sum, 0, root);
		return sum;
	}
};

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

LeetCode Binary Tree Level Order Traversal

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

    3
   / \
  9  20
    /  \
   15   7

return its level order traversal as:

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

本题要求实现二叉树的层次遍历,居然没要求同时实现递归和迭代版本了,不过要求分层输出,还真是头一回见。
层次遍历不难,用队列+BFS实现,但是为了实现分层输出,我的方法是标记下一层的第一个节点,当队列走到下一层第一个节点时,说明该层结束,进入下一个循环。该版本的完整代码如下:

class Solution {
public:
	void bfs(vector<vector<int>>& ans, TreeNode* root) {
		queue<TreeNode*> tree;
		tree.push(root);
		TreeNode* front;
		while (!tree.empty()) {
			vector<int> cand;
			bool pushed = false;
			TreeNode* next_level = NULL; // 下一层的第一个节点
			front = tree.front();
			while (!tree.empty() && front != next_level) {
				tree.pop();
				cand.push_back(front->val);
				if (front->left != NULL) {
					tree.push(front->left);
					if (!pushed) {
						next_level = front->left; // 标记
						pushed = true; // 标记
					}
				}
				if (front->right != NULL) {
					tree.push(front->right);
					if (!pushed) {
						next_level = front->right; // 标记
						pushed = true; // 标记
					}
				}
				if (tree.empty())break;
				front = tree.front();
			}
			ans.push_back(cand);
		}
	}
	vector<vector<int>> levelOrder(TreeNode* root) {
		vector<vector<int>> ans;
		if (root == NULL)return ans;
		bfs(ans, root);
		return ans;
	}
};

本代码提交AC,用时9MS。
但是这个版本的代码看起来不够简洁,网上看题解发现递归迭代各一种简洁漂亮的解法。
我的解法不够简洁的原因是需要记录下一层第一个节点,然后判断当前层是否已遍历结束。但是仔细想想,这一层需要遍历的次数不就是这一层的节点数吗,而节点都存在队列中了,所以可以获取队列大小n,每层只循环n次即可。这个版本的代码如下,简洁了许多。

class Solution {
public:
	vector<vector<int>> levelOrder(TreeNode* root) {
		vector<vector<int>> ans;
		if (root == NULL)return ans;
		queue<TreeNode*> tree;
		tree.push(root);
		TreeNode* f;
		while (!tree.empty()) {
			int n = tree.size();
			vector<int> one_level;
			for (int i = 0; i < n; i++) {
				f = tree.front();
				tree.pop();
				one_level.push_back(f->val);
				if (f->left != NULL)tree.push(f->left);
				if (f->right != NULL)tree.push(f->right);
			}
			ans.push_back(one_level);
		}
		return ans;
	}
};

本代码提交AC,用时6MS,也稍快了一点。
至于递归版本,我是没想到层次遍历也可以用递归来实现。递归的思路是,当当前遍历的层数和结果二维数组中的大小相等时,说明此时是第一次走到这一层,需要往二维数组中加一个空的一维数组,同时把这个节点的值加进去。然后依次先左后右的递归下去。
注意用递归实现层次遍历时,并不和我们肉眼层次遍历的顺序一致,它相当于DFS,只是把深搜的结果存到指定层的数组中了,最终输出的效果和普通的层次遍历一样。递归版本的代码如下:

class Solution {
public:
	void work(vector<vector<int>>& ans, int level, TreeNode* root) {
		if (ans.size() == level)ans.push_back({}); // 重点
		ans[level].push_back(root->val);
		if (root->left != NULL)work(ans, level + 1, root->left); // 先左
		if (root->right != NULL)work(ans, level + 1, root->right); // 后右
	}
	vector<vector<int>> levelOrder(TreeNode* root) {
		vector<vector<int>> ans;
		if (root == NULL)return ans;
		work(ans, 0, root);
		return ans;
	}
};

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

LeetCode Remove Linked List Elements

LeetCode Remove Linked List Elements
Remove all elements from a linked list of integers that have value val.
Example
Given: 1 --> 2 --> 6 --> 3 --> 4 --> 5 --> 6, val = 6
Return: 1 --> 2 --> 3 --> 4 --> 5


把链表中等于val的所有节点都删掉。简单题,为了方便,先添加一个0号节点,然后记录prior和tail指针,当tail->val==val时,删掉tail节点,prior节点不动;否则prior和tail都往后移一个位置。直到tail为NULL。完整代码如下:

class Solution {
public:
	ListNode* removeElements(ListNode* head, int val) {
		ListNode* new_head = new ListNode(0);
		new_head->next = head;
		ListNode *prior = new_head, *tail = prior->next;
		while (tail != NULL) {
			if (tail->val == val) {
				prior->next = prior->next->next;
				tail = prior->next;
			}
			else {
				prior = prior->next;
				tail = prior->next;
			}
		}
		return new_head->next;
	}
};

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

LeetCode Path Sum II

LeetCode Path Sum II
Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.
For example:
Given the below binary tree and sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1

return

[
   [5,4,11,2],
   [5,8,4,5]
]

相比上一题LeetCode Path Sum更进一步,本题要把所有等于sum的路径记录下来,所以递归求解的时候要带着一个数组,把从根节点到当前节点的路径记录下来。常规题,完整代码如下:

class Solution {
public:
	void dfs(vector<vector<int>>& ans, vector<int>& path, int& target, int cur, TreeNode* root) {
		if (root->left == NULL&&root->right == NULL) {
			if (cur + root->val == target) {
				path.push_back(root->val);
				ans.push_back(path);
				path.pop_back();
			}
			return;
		}
		if (root->left != NULL) {
			path.push_back(root->val);
			dfs(ans, path, target, cur + root->val, root->left);
			path.pop_back();
		}
		if (root->right != NULL) {
			path.push_back(root->val);
			dfs(ans, path, target, cur + root->val, root->right);
			path.pop_back();
		}
	}
	vector<vector<int>> pathSum(TreeNode* root, int sum) {
		vector<vector<int>> ans;
		if (root == NULL)return ans;
		vector<int> path;
		dfs(ans, path, sum, 0, root);
		return ans;
	}
};

本代码提交AC,用时16MS。
二刷。更简洁的代码,如下:

class Solution {
private:
    void dfs(vector<vector<int>>& ans, vector<int>& candidate, TreeNode* root, int sum) {
        candidate.push_back(root->val);
        sum -= root->val;
        if(root->left == NULL && root->right == NULL && sum == 0) {
            ans.push_back(candidate);
        }
        if(root->left != NULL) dfs(ans, candidate, root->left, sum);
        if(root->right != NULL) dfs(ans, candidate, root->right, sum);
        candidate.pop_back();
    }
public:
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        if(root == NULL) return {};
        vector<vector<int>> ans;
        vector<int> candidate;
        dfs(ans, candidate, root, sum);
        return ans;
    }
};

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

LeetCode Path Sum

LeetCode Path Sum
Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
For example:
Given the below binary tree and sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.


本题要一个数是否等于从树根到某个叶子的和。简单题,直接dfs把所有从根到叶子的路径和算出来,存到set里面,然后用sum去set里查。当然如果还想更高效,可以用hash,比如unordered_map。
完整代码如下:

class Solution {
public:
	void dfs(set<int>& vals, int cur, TreeNode* root) {
		if (root->left == NULL&&root->right == NULL) {
			vals.insert(cur + root->val);
			return;
		}
		if (root->left != NULL) {
			dfs(vals, cur + root->val, root->left);
		}
		if (root->right != NULL) {
			dfs(vals, cur + root->val, root->right);
		}
	}
	bool hasPathSum(TreeNode* root, int sum) {
		if (root == NULL)return false;
		set<int> vals;
		dfs(vals, 0, root);
		if (vals.count(sum) > 0)return true;
		else return false;
	}
};

本代码提交AC,用时13MS。
二刷。直接递归判断某一条路径的和是否等于sum就好了,代码如下:

class Solution {
public:
    bool hasPathSum(TreeNode* root, int sum) {
        if(root == NULL) return false;
        if(root->left == NULL && root->right == NULL && root->val == sum) return true;
        if(root->left == NULL && root->right == NULL && root->val != sum) return false;
        if(root->left != NULL)
            if(hasPathSum(root->left, sum - root->val))
                return true;
        if(root->right != NULL)
            if(hasPathSum(root->right, sum - root->val))
                return true;
        return false;
    }
};

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

LeetCode Binary Tree Postorder Traversal

LeetCode Binary Tree Postorder Traversal
Given a binary tree, return the postorder traversal of its nodes' values.
For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [3,2,1].
Note: Recursive solution is trivial, could you do it iteratively?


实现二叉树的后续遍历算法,需要非递归形式哦~这题好难...是三种非递归遍历算法中最难的一种了。
惯例,先上递归算法:

class Solution {
public:
	void work(vector<int>& ans, TreeNode* root) {
		if (root == NULL)return;
		work(ans, root->left);
		work(ans, root->right);
		ans.push_back(root->val);
	}
	vector<int> postorderTraversal(TreeNode* root) {
		vector<int> ans;
		work(ans, root);
		return ans;
	}
};

本代码提交AC,用时3MS。
下面来想非递归算法。续遍历的顺序是:左右,根节点是最后访问的。还是用堆栈来实现,那么根据堆栈的后进先出性质,压栈的顺序应该是根右左
那么什么时候可以访问根节点呢,只有当这个节点是叶子节点或者左右孩子都访问完之后才可以。判断是否为叶子节点很容易,那么怎么判断左右孩子都访问完了呢,此时我们可以用一个变量pre来记录上一次访问的节点,curr为当前栈顶节点。如果pre是curr的左或右孩子节点,则说明左右孩子已经访问过了,此时我们就可以访问curr了。
本算法的代码如下:

class Solution {
public:
	vector<int> postorderTraversal(TreeNode* root) {
		vector<int> ans;
		if (root == NULL)return ans;
		stack<TreeNode*> tree;
		TreeNode *curr, *pre = NULL;
		tree.push(root); // 根
		while (!tree.empty()) {
			curr = tree.top();
			if ((curr->left == NULL && curr->right == NULL) || // 已到叶子节点
				(pre != NULL && (curr->left == pre || curr->right == pre))) { // 回溯的时候
				ans.push_back(curr->val);
				tree.pop();
				pre = curr;
			}
			else {
				if (curr->right != NULL)tree.push(curr->right); // 右
				if (curr->left != NULL)tree.push(curr->left); // 左
			}
		}
		return ans;
	}
};

本代码提交AC,用时0MS。
可能有同学担心curr->left==pre不能一定说明左右孩子都访问完了,只能说明左孩子访问完了。但是根据我们的压栈顺序,当curr同时又左右孩子的时候,不会走这条判断。如下左图所示,首先4会弹栈,然后栈顶变为了5,此时pre=4, curr=5,访问5;然后5弹栈,栈顶为2,此时pre=5,curr=2,所以走的是curr->right==pre,访问2。只有当curr只有左孩子没有右孩子的时候才会判断curr->left==pre,如下右图,此时是可以访问curr的。

还有一种很简洁漂亮的解法,用两个堆栈。再次回忆序遍历顺序:左右,我们怎样用两个堆栈得到这样的顺序呢。如下图所示,第一个堆栈压栈顺序是左右根,然后弹出来压到第二个堆栈里,则从第二个堆栈里弹出来的顺序就是左右根了。注意,虽然第一次压栈的顺序已经是左右根了,我们要得到的也是左右根,为什么还要经过第二个堆栈这样倒腾一下呢?因为堆栈1的左右根和从堆栈2出来的左右根是不一样的,前者是靠近根节点的左右根,但是我们的后序遍历是要从叶子节点开始得到左右根,而从堆栈2出来的就是从叶子节点开始的左右根。

下面结合代码来说:

class Solution {
public:
	vector<int> postorderTraversal(TreeNode* root) {
		vector<int> ans;
		if (root == NULL)return ans;
		stack<TreeNode*> s1, s2;
		TreeNode* top;
		s1.push(root); // 根
		while (!s1.empty()) {
			top = s1.top(); // (1)
			s1.pop();       // (1)
			s2.push(top);   // (1)
			if (top->left != NULL) { // 左
				s1.push(top->left);
			}
			if (top->right != NULL) { // 右
				s1.push(top->right);
			}
		}
		while (!s2.empty()) {
			top = s2.top();
			ans.push_back(top->val);
			s2.pop();
		}
		return ans;
	}
};

从第13、16行可知,对于堆栈1,我们先压了左后压了右,但是从第8行来看,根是最先压的,看起来不符合左右根的压栈顺序,但是请注意,代码(1)部分在先于13、16行弹栈了,然后马上压到堆栈2了,这样的效果不就是根节点在堆栈1的栈顶,然后被压到了堆栈2的底部了吗。所以和上图是统一的。
本代码提交AC,用时0MS。
定睛一看,这居然是道hard题。。。

LeetCode Binary Tree Preorder Traversal

LeetCode Binary Tree Preorder Traversal
Given a binary tree, return the preorder traversal of its nodes' values.
For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [1,2,3].
Note: Recursive solution is trivial, could you do it iteratively?


这一题要实现二叉树的前序遍历,序遍历的顺序是:左右。
首先献上妇孺皆知的递归解法:

class Solution {
public:
	void work(vector<int>& ans, TreeNode* root) {
		if (root == NULL)return;
		ans.push_back(root->val);
		work(ans, root->left);
		work(ans, root->right);
	}
	vector<int> preorderTraversal(TreeNode* root) {
		vector<int> ans;
		work(ans, root);
		return ans;
	}
};

本代码提交AC,用时3MS。和LeetCode Binary Tree Inorder Traversal一样,本题也要实现前序遍历的迭代算法。迭代的思路同样是用堆栈来实现:首先把当前根节点压栈,然后注意,因为前序遍历是先访问左子树,后访问右子树,所以我们压栈的时候,要先压右子树,再压左子树,这样弹栈的时候才能符合前序遍历的要求。除此之外,我觉得实现起来比中序遍历要简单。
迭代版本的完整代码如下:

class Solution {
public:
	vector<int> preorderTraversal(TreeNode* root) {
		vector<int> ans;
		if (root == NULL)return ans;
		stack<TreeNode*> tree;
		tree.push(root);
		TreeNode* top;
		while (!tree.empty()) {
			top = tree.top();
			ans.push_back(top->val);
			tree.pop();
			if (top->right != NULL) { // 先压栈右子树
				tree.push(top->right);
			}
			if (top->left != NULL) { // 再压栈左子树
				tree.push(top->left);
			}
		}
		return ans;
	}
};

本代码提交AC,用时也是3MS。

LeetCode Binary Tree Inorder Traversal

LeetCode Binary Tree Inorder Traversal
Given a binary tree, return the inorder traversal of its nodes' values.
For example:
Given binary tree [1,null,2,3],

   1
    \
     2
    /
   3

return [1,3,2].
Note: Recursive solution is trivial, could you do it iteratively?


本题要实现二叉树的中序遍历。这个题应该是很基本的二叉树的遍历题,本科学数据结构对这个是基本要求。不过本科学的是中文教材,只知道前序、中序、后序,不知道对应的英文是什么,WIKI上的Tree traversal图解还是很通俗易懂的:前序(Pre-order),中序(In-order),后序(Post-order)和层次遍历(Level-order)。
前序、中序和后序的区别很容易记,只要记住他们的前、中、后分别是访问根节点的顺序。比如前序顺序是先访问根节点,然后依次访问左右孩子节点。序:左右;序:左右;序:左右
本题要实现二叉树的中序遍历,如上所述,先访问左子树,然后访问根节点,最后访问右子树。用递归的方法非常简洁直观。递归的完整代码如下:

class Solution {
public:
	void work(vector<int>& ans, TreeNode* root) {
		if (root == NULL)return;
		work(ans, root->left); // 左
		ans.push_back(root->val); // 根
		work(ans, root->right); // 右
	}
	vector<int> inorderTraversal(TreeNode* root) {
		vector<int> ans;
		work(ans, root);
		return ans;
	}
};

本代码提交AC,用时0MS。
但是Note问能不能用迭代实现以下呢?当然可以,所以可以用递归实现的算法肯定都可以用迭代的方法实现,只是有时候迭代写起来更麻烦。
我的思路是肯定要首先找到树的最左下角的叶子节点,这个节点是最先被访问的,然后访问根节点,最后访问右子树。访问右子树的时候,又是重复之前的操作,首先找到右子树中的最左下角的叶子节点,访问它,然后访问根节点,最后又访问其右子树。
上述过程需要在访问完左孩子之后再访问根节点,但是树中节点的指向是单向的,只能由根访问到孩子,不能由孩子回溯到根。我们不可能在找孩子的同时保存该孩子的父亲节点,这样太麻烦了。于是我想到了用堆栈,在找最左下角的叶子节点的时候,顺便把经过的祖先节点压到堆栈中,当访问完孩子节点后,弹栈,此时的栈顶节点就是父亲节点了。如果父节点有右子树,则进入右子树,重复之前的过程(找右子树的最左下角叶子)。
迭代法的完整代码如下:

class Solution {
public:
	void putAllLeft(TreeNode* root, stack<TreeNode*>& tree) {
		while (root != NULL) {
			tree.push(root);
			root = root->left;
		}
	}
	vector<int> inorderTraversal(TreeNode* root) {
		vector<int> ans;
		stack<TreeNode*> tree;
		putAllLeft(root, tree); // 找最左边的叶子节点
		TreeNode *top;
		while (!tree.empty()) {
			top = tree.top();
			ans.push_back(top->val); // 访问左(根)节点
			tree.pop();
			putAllLeft(top->right, tree); // 访问右节点
		}
		return ans;
	}
};

本代码提交AC,用时0MS。
调试的时候可以使用我之前写过的由数组生成二叉树的函数,挺方便的。