前两天搬家，然后断了两天没学习啊，有点小内疚啊，争取这周补回6道题。开始刷题了啊。
课程表2
题目：现在你总共有 n 门课需要选，记为 0 到 n-1。在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]给定课程总量以及它们的先决条件，返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回一种就可以了。如果不可能完成所有课程，返回一个空数组。
示例 1:
输入: 2, [[1,0]]
输出: [0,1]
解释: 总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。
示例 2:
输入: 4, [[1,0],[2,0],[3,1],[3,2]]
输出: [0,1,2,3] or [0,2,1,3]
解释: 总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。
因此，一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。
说明:
输入的先决条件是由边缘列表表示的图形，而不是邻接矩阵。详情请参见图的表示法。
你可以假定输入的先决条件中没有重复的边。
提示:
这个问题相当于查找一个循环是否存在于有向图中。如果存在循环，则不存在拓扑排序，因此不可能选取所有课程进行学习。
通过 DFS 进行拓扑排序 - 一个关于Coursera的精彩视频教程（21分钟），介绍拓扑排序的基本概念。
拓扑排序也可以通过 BFS 完成。
思路：又想起被课程表1支配的恐惧了啊，不是没思路，是死去活来的麻烦啊，但是单纯从题目的角度来说这个题是不难的啊，毕竟感觉就是课程1 的栈中的每一个元素取出来存结果集啊，不过当时的自己只是用脑补来实现的，现在这个给出提示拓扑排序，有时间我要去百度瞅瞅这个拓扑排序是啥啊。
好了，我先把这个题做出来了，第一版的解法性能就那样，是课程表1的修改版：
class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
//如果都能学完肯定是这么多课程
int[] res = new int[numCourses];
int[] lock = new int[numCourses];
for(int[] i : prerequisites){
//课程有一个锁则值+1
lock[i[0]]++;
}
Stack<Integer> stack = new Stack<Integer>();
for(int i = 0;i<lock.length;i++){
//这个课程的锁为0则可以直接学习，所以加入栈
if(lock[i]==0) stack.push(i);
}
int idx = 0;
while(!stack.isEmpty()){
int s = stack.pop();
res[idx] = s; //将这个解锁的课程存到结果集
idx++;
for(int i = 0;i<prerequisites.length;i++){
//先决条件已经解锁
if(prerequisites[i][1]==s){
lock[prerequisites[i][0]]--;
if(lock[prerequisites[i][0]]==0){
//这个课程已经没有锁了说明可以学习了
stack.push(prerequisites[i][0]);
}
}
}
}
return idx == numCourses?res:new int[0];
}
}
我还记得这个做法就是我的第一做法，本来性能也不咋地，至于课程1性能好的的做法是用的链表。然后判断有环没环，不过这个是要放入顺序的，我不知道要怎么改动才能实现，所以我就不献丑啦，直接去膜拜大佬的代码咯：
class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
return prepareDfs(numCourses,prerequisites);
}
int count = 0;
int res[] = null;
public int[] prepareDfs(int numCourses,int prerequisites[][]){
int visit[] = new int[numCourses];
List<Integer> lists[] = new ArrayList[numCourses];
for(int i = 0;i<numCourses;i++){
lists[i] = new ArrayList<>();
}
res = new int[numCourses];
for(int a[]:prerequisites){
lists[a[0]].add(a[1]);
}
for(int i = 0;i<numCourses;i++){
if(!dfs(i,lists,visit)){
return new int[0];
}
}
return res;
}
public boolean dfs(int i,List<Integer> lists[],int visit[]){
if(visit[i] == 1){
return false;
}
if(visit[i] == -1){
return true;
}
visit[i] = 1;
for(int a = 0;a<lists[i].size();a++){
if(!dfs(lists[i].get(a),lists,visit) ){
return false;
}
}
visit[i] = -1;
res[count++] = i;
return true;
}
}
额，一看就会，一写就废系列。
刚刚题目上提到了拓扑排序，所以 打算去百度好好瞅瞅这个拓扑排序是什么。百度回来了，我觉得知识没有多到需要单独记录，所以在这里列个小标题大概整理了一下拓扑排序。
拓扑排序
对一个有向无环图G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边<u,v>∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。
上面是百度百科对拓扑排序的定义。其实我觉得只看文字叙述比较不好理解，所以我用自己的方式来理解这句话。
什么是有向？我这里认为是一个事件的执行方向。
打个比方：刷牙，洗脸这两件事，是没有方向的，毕竟先刷牙也行，先洗脸也行。
再打个比方：种种子，长出芽。这两件事是有方向的，肯定是先要种下种子，然后才能长出芽来。不可能先长芽，再种种子。
什么是无环？就是事件的发展要顺序执行，不能有环。
首先要明确，环是首尾相连的闭环。而不是分支。也不是合并。我为什么要这么说呢？用两个图来表示：
图1，非环
如图，这个不要以为关系图中有闭合空间就是环了，其实这个不是环，因为在红色圈圈的地方，是两个先决条件，这块其实应该挺好理解的，红色圈圈这块是先决条件的合并。但是我一开始没太懂，是看了一会儿才明白的，决定是不是环不在于图形的“线”，而在于“线”的箭头指向。比如下图就是一个环。
图2，环
AOV网
一个较大的工程往往被划分成许多子工程，我们把这些子工程称作活动(activity)。在整个工程中，有些子工程(活动)必须在其它有关子工程完成之后才能开始，也就是说，一个子工程的开始是以它的所有前序子工程的结束为先决条件的，但有些子工程没有先决条件，可以安排在任何时间开始。为了形象地反映出整个工程中各个子工程(活动)之间的先后关系，可用一个有向图来表示，顶点代表活动，有向边代表活动的先后关系，即有向边的起点的活动是终点活动的前序活动，只有当起点活动完成之后，其终点活动才能进行。通常，我们把这种顶点表示活动、边表示活动间先后关系的有向图称做顶点活动网(Activity On Vertex network)，简称AOV网。
一个AOV网应该是一个有向无环图，即不应该带有回路，因为若带有回路，则回路上的所有活动都无法进行。
在AOV网中，若不存在回路，则所有活动可排列成一个线性序列，使得每个活动的所有前驱活动都排在该活动的前面，我们把此序列叫做拓扑序列(Topological order)，由AOV网构造拓扑序列的过程叫做拓扑排序(Topological sort)。AOV网的拓扑序列不是唯一的，满足上述定义的任一线性序列都称作它的拓扑序列。
由AOV网构造出拓扑序列的实际意义是：如果按照拓扑序列中的顶点次序，在开始每一项活动时，能够保证它的所有前驱活动都已完成，从而使整个工程顺序进行，不会出现冲突的情况。
拓扑排序执行顺序
由AOV网构造拓扑序列的拓扑排序算法主要是循环执行以下两步，直到不存在入度为0的顶点为止。
(1) 选择一个入度为0的顶点并输出之；
(2) 从网中删除此顶点及所有出边；
image
循环结束后，若输出的顶点数小于网中的顶点数，则输出“有回路”信息，否则输出的顶点序列就是一种拓扑序列。
总结
首先拓扑排序不是类似于冒泡排序，插入排序，堆排序，快速排序这种只是排序方法。而是一种将满足条件（有向无环）的数据用关系图的形式表达出来。课程表1,2都是可能满足了条件，也可能不满足条件。课程表1要做的是判断满不满足条件（true/false），而课程表2是判断满不满足条件后，还要输出执行顺序，也就是拓扑序列。
关于拓扑排序的总结就差不多这样，其实这个不是很难，而且变化应该也不是很大，甚至我都觉得这个也像是一种数据结构了。反正这个就这样，继续往下做题了。
添加与搜索单词
题目：设计一个支持以下两种操作的数据结构：
void addWord(word)
bool search(word)
search(word) 可以搜索文字或正则表达式字符串，字符串只包含字母 . 或 a-z 。 . 可以表示任何一个字母。
示例:
addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true
说明:
你可以假设所有单词都是由小写字母 a-z 组成的。
思路：这个题让我想到了前缀树啊，不过应该是不一样的，毕竟前缀树只能搜索前缀，所以结果是一个字母一个字母的分词，这个可以模糊匹配，不过我看都是a-z的字母组成，感觉应该还是和分词什么的有关，其实之前前缀树的思路是可行的，但是.XX的处理就要全遍历，我先试试吧。不行再说。
emmmmm...实现了，前缀树的修修改改，我直接贴代码：
class WordDictionary {
TreeNode t = new TreeNode();
/** Initialize your data structure here. */
public WordDictionary() {
}
/** Adds a word into the data structure. */
public void addWord(String word) {
TreeNode cur = t;
for(char c : word.toCharArray()){
int idx = c-'a';
if(cur.next[idx]==null){
cur.next[idx] = new TreeNode();
}
cur = cur.next[idx];
}
cur.isEnd = true;
}
/** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
public boolean search(String word) {
return searchReg(word,t);
}
public boolean searchReg(String s,TreeNode cur){
char[] c = s.toCharArray();
for(int i = 0;i<c.length;i++){
if(c[i] == '.'){//特殊处理
for(int j = 0;j<26;j++){
TreeNode temp = cur.next[j];
if(temp==null) continue;
if(searchReg(s.substring(i+1),temp)) return true;
}
return false;
}else{
if(cur.next[c[i]-'a']==null) return false;
cur = cur.next[c[i]-'a'];
}
}
return cur.isEnd;
}
}
class TreeNode{
boolean isEnd;
TreeNode[] next = new TreeNode[26];
}
/**
* Your WordDictionary object will be instantiated and called as such:
* WordDictionary obj = new WordDictionary();
* obj.addWord(word);
* boolean param_2 = obj.search(word);
*/
然后这个代码性能又不行，我怀疑是测试案例太小的事。毕竟如果仅仅是一些单词测试，map性能可能好一点，毕竟如果是通配符则一层26个，两层2626，三层2626*26，，，啧啧，反正我去看看性能排行第一的代码吧。
class WordDictionary {
class TrieNode {
public TrieNode[] children = new TrieNode[26];
public String item = "";
}
private TrieNode root = new TrieNode();
public void addWord(String word) {
TrieNode node = root;
for (char c : word.toCharArray()) {
if (node.children[c - 'a'] == null) {
node.children[c - 'a'] = new TrieNode();
}
node = node.children[c - 'a'];
}
node.item = word;
}
public boolean search(String word) {
return match(word.toCharArray(), 0, root);
}
private boolean match(char[] chs, int k, TrieNode node) {
if (k == chs.length) return !node.item.equals("");
if (chs[k] != '.') {
return node.children[chs[k] - 'a'] != null && match(chs, k + 1, node.children[chs[k] - 'a']);
} else {
for (int i = 0; i < node.children.length; i++) {
if (node.children[i] != null) {
if (match(chs, k + 1, node.children[i])) {
return true;
}
}
}
}
return false;
}
}
/**
* Your WordDictionary object will be instantiated and called as such:
* WordDictionary obj = new WordDictionary();
* obj.addWord(word);
* boolean param_2 = obj.search(word);
*/
大同小异吧，这种题真的，我觉得是对耐心和细节的历练，，，然后我的重复提交好几次，一样的代码性能有质的不同，最少50ms，最大119ms，从排名第十到第七十多。。。反正就这样吧，我也不想调优了，直接下一题了。
打家劫舍2
题目：你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
示例 1:
输入: [2,3,2]
输出: 3
解释: 你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
示例 2:
输入: [1,2,3,1]
输出: 4
解释: 你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
偷窃到的最高金额 = 1 + 3 = 4 。
思路：典型动归，甚至我在专门学dp的时候这个题还是个范例，我直接去写了，这个其实还是很简单的，和之前的打家劫舍1比好像区别只是首尾相连。我暂时的思路是从第一个开始到倒数第二个的最大。和从第二个开始到最后一个的最大，取较大值。我去实现了。
好了，思路没问题，两次dp计算，性能超过百分百，我直接贴代码：
class Solution {
public int rob(int[] nums) {
if(nums.length==0) return 0;
if(nums.length==1) return nums[0];
if(nums.length==2) return Math.max(nums[0],nums[1]);
int[] p = new int[nums.length];
p[0] = 0;
p[1] = nums[0];
for(int i = 1;i<nums.length-1;i++) {
p[i+1] = Math.max(p[i], p[i-1]+nums[i]);
}
int[] pp = new int[nums.length+1];
pp[0] = 0;
pp[1] = nums[1];
for(int i = 2;i<nums.length;i++) {
pp[i] = Math.max(pp[i-1], pp[i-2]+nums[i]);
}
return Math.max(p[nums.length-1],pp[nums.length-1]);
}
}
因为dp 的题一个特点就是懂的一看差不多就懂，不懂的不是一句两句能说明白的，所以建议这块不太好的去看动归的讲解视频，别硬做题，然后我这道题就过了。
数组中的第K个最大元素
题目：在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
示例 1:
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4
说明:
你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。
思路：这个题没设置限制条件，所以我做着有点没底，毕竟我不知道排序，然后取倒数第k个元素，有什么不对。但是这是中等难度。。啧啧，我先做出来，再想优化什么的吧。对了，补充一句，我觉得这个题用快排很合适。我用快排试试。
果然快排是正解，本来我想取第k的位置的元素为标准值，后来发现没啥用，还是换成了中间元素。然后根据前后的个数和k比，可以缩小需要排队的范围。我直接贴代码：
class Solution {
public int findKthLargest(int[] nums, int k) {
return quickSort(nums, 0, nums.length-1, k);
}
private int quickSort(int[] nums, int l, int r, int k){
if (l >= r) return nums[l];
int i = l-1, j = r+1, pivot = nums[l+r>>1];
while (i < j){
do i++; while (nums[i] > pivot);
do j--; while (nums[j] < pivot);
if (i < j){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
if (j >= k-1) return quickSort(nums, l, j, k);
return quickSort(nums, j+1, r, k);
}
}
然后这个性能已经超过百分之九十九的人了，所以我也不看题解了，这个题就这样过了。
今天的笔记就到这里，如果稍微帮到你了记得点个喜欢点个关注，也祝大家工作顺顺利利！生活健健康康！
网友评论