课程表
题目：你这个学期必须选修 numCourse 门课程，记为 0 到 numCourse-1 。在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们：[0,1]给定课程总量以及它们的先决条件，请你判断是否可能完成所有课程的学习？
示例 1:
输入: 2, [[1,0]]
输出: true
解释: 总共有 2 门课程。学习课程 1 之前，你需要完成课程 0。所以这是可能的。
示例 2:
输入: 2, [[1,0],[0,1]]
输出: false
解释: 总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0；并且学习课程 0 之前，你还应先完成课程 1。这是不可能的。
提示：
- 输入的先决条件是由 边缘列表 表示的图形，而不是 邻接矩阵 。详情请参见图的表示法。
- 你可以假定输入的先决条件中没有重复的边。
1 <= numCourses <= 10^5
思路：以上都是题目。莫名感觉有点锁的意思。就看最后是不是死锁？但是还是有点区别的，我还没看测试案例，不过大概思路是肯定有一个课是不需要先决条件的，然后顺着往下，如果最后能走完就是true，不然就是false。我去实现下看看。
看的我眼花
哎，我可能审题有问题，现在才知道一个课程还能有两个先决条件，一个先决条件能用两次。。而且必须全部满足。然后我觉得从思路上说，需要记录每个钥匙能解几个锁。然后遍历看哪个数是没有锁的。然后从那里开始逐个解锁。如果到了无锁可解的时候、如果所有的锁都能被解开就是true，否则就是false。
说的挺简单，但是这么实现起来太麻烦了，我一开始是用map（key是要是，value是能解的所有锁）然后来回调试把自己都调懵了。最后还是用了数组代替下标的方式，一个个遍历吧，有一层锁解一层锁，最后全都解完了就是true，不然false。我直接贴代码了：
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
if(prerequisites.length==0) return true;
//下标 是锁 值是锁的个数
int[] ar = new int[numCourses];
for(int i = 0;i<prerequisites.length;i++){
ar[prerequisites[i][0]]++;
}
//存可以学的课程
Stack<Integer> stack = new Stack<Integer>();
//如果锁等于0说明没锁，直接可以学
for(int i=0;i<ar.length;i++){
if(ar[i]==0) stack.push(i);
}
int res = 0;
//可学的不空就一直学。没有可学的就看是不是都解锁了
while(!stack.isEmpty()){
int key = stack.pop();
for(int i = 0;i<prerequisites.length;i++){
//先决条件可解锁则这个也可以解锁
if(prerequisites[i][1] == key){
ar[prerequisites[i][0]]--;
res++;
//当锁为0说明可以学了，则添加到栈
if(ar[prerequisites[i][0]]==0) {
stack.push(prerequisites[i][0]);
}
}
}
}
System.out.println(res);
//所有课程都解锁则true，否则false
return res==prerequisites.length;
}
}
各种for循环，我写着写着都不自信了，还好最后通过了，就是性能贼差。但是我已经无力优化了，脑袋成了浆糊了，我直接去看性能排行第一的代码了。
好了，回来了，看只是勉强看懂，写是绝对写不出来的，起码现在的我差的远，哎，我贴出来大家瞻仰下：
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
if (prerequisites == null || prerequisites.length == 0) return true;
// 构建图
Node[] graph = new Node[numCourses];
for (int[] plan : prerequisites) {
// 头插法
graph[plan[0]] = new Node(plan[1], graph[plan[0]]);
}
// 判断是否存在环
int[] visited = new int[numCourses];
for (int i = 0; i < numCourses; i++) {
// 未遍历则遍历，如果存在环，则不符合要求
if(visited[i] != -1 && !isDAG(i, graph, visited)) {
return false;
}
// 遍历完成，以i出发不存在环路，置为访问且无环
visited[i] = -1;
}
return true;
}
private boolean isDAG(int start, Node[] graph, int[] visited) {
// 置为正在遍历
visited[start] = 1;
Node temp = graph[start];
while (temp != null) {
// 之前已经遍历过，无环
if (visited[temp.val] == -1) {
temp = temp.next;
continue;
}
// 存在环路
if(visited[temp.val] == 1 || !isDAG(temp.val, graph, visited)) return false;
// 遍历结束，置为已访问且无环
visited[temp.val] = -1;
temp = temp.next;
}
return true;
}
}
class Node {
int val;
Node next;
Node(int val) {
this.val = val;
}
Node(int val, Node next) {
this.val = val;
this.next = next;
}
}
这个逻辑怎么说呢，我是觉得很厉害，看了好久才看懂，我不知道算不算标记法？反正就是把先决条件和课程用链表的形式表示出来了，然后顺着链表的节点开始往下遍历，如果遍历到走不下去的地方则false。
这里的走不下去就是遇到环了，因为这个==1是在方法未执行完的值，当到某个节点递归递归递归最终发现递归到自己头上了，才是1。还有一种可能是钥匙在环里，虽然没到自己头上但是确定钥匙拿不到了也可以直接false。
这个题我看了评论，好像是一个新类型。最近有空会看看的，下一题了。
实现Trie前缀树
题目：实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。
示例:
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // 返回 true
trie.search("app"); // 返回 false
trie.startsWith("app"); // 返回 true
trie.insert("app");
trie.search("app"); // 返回 true
说明:
你可以假设所有的输入都是由小写字母 a-z 构成的。
保证所有输入均为非空字符串。
思路：这个题怎么说呢，我对题目还有一点不理解，插入苹果插入app后，trie是不是还包含苹果？我先去测试案例试试，然后再来实现，总体来说这种题都不难，就是怎么实现的优雅性能好是关键。
呵，我就说嘛，实现很简单，性能是关键，我先贴我的代码
class Trie {
StringBuffer sb = new StringBuffer();
/** Initialize your data structure here. */
public Trie() {
}
/** Inserts a word into the trie. */
public void insert(String word) {
sb.append("-"+word+"-");
}
/** Returns if the word is in the trie. */
public boolean search(String word) {
return sb.toString().contains("-"+word+"-");
}
/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
return sb.toString().contains("-"+prefix);
}
}
/**
* Your Trie object will be instantiated and called as such:
* Trie obj = new Trie();
* obj.insert(word);
* boolean param_2 = obj.search(word);
* boolean param_3 = obj.startsWith(prefix);
*/
不出意外的垃圾
好了好了，不闹了，咱们好好说这个题，首先题目是前缀树。所以这个题应该是树的数据结构。其实我有个大胆的想法：每一个单词的首字符是一个树的根节点，因为只有26个字母，最多就是26条树。然后每一个树除了当前value还有一个指针是下面的字母。如果下面的字母同样也是一棵树，可以继续往下找，如果找不到了说明没有了。这个判断前缀是很好算的吧（分词给的思路），然后全包含就是看走到最后有没有停止，最多加个分支，我去想想怎么实现。
绞尽脑汁写完了，然后性能还是上不来，我都快绝望了：
class Trie {
Trie[] next = new Trie[26];
boolean isEnd = false;
/** Initialize your data structure here. */
public Trie() {
}
/** Inserts a word into the trie. */
public void insert(String word) {
Trie t = this;
for(char c :word.toCharArray()){
if(t.next[c-'a'] == null) t.next[c-'a'] = new Trie();
t = t.next[c-'a'];
}
t.isEnd = true;
}
/** Returns if the word is in the trie. */
public boolean search(String word) {
Trie t = this;
for(char c : word.toCharArray()){
if(t.next[c-'a']==null) return false;
t = t.next[c-'a'];
}
return t.isEnd;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
Trie t = this;
for(char c : prefix.toCharArray()){
if(t.next[c-'a']==null) return false;
t = t.next[c-'a'];
}
return true;
}
}
/**
* Your Trie object will be instantiated and called as such:
* Trie obj = new Trie();
* obj.insert(word);
* boolean param_2 = obj.search(word);
* boolean param_3 = obj.startsWith(prefix);
*/
我去看看性能排行第一的代码是怎么写的吧。
- 神同步，但是我不知道为啥人家第一我第好几十。。。我贴下代码下一题了：
class Trie {
private class TrieNode {
private TrieNode[] next;
private boolean isEnd;
public TrieNode() {
next = new TrieNode[26];
isEnd = false;
}
}
private TrieNode root;
/** Initialize your data structure here. */
public Trie() {
root = new TrieNode();
}
/** Inserts a word into the trie. */
public void insert(String word) {
TrieNode tmp = root;
for (char c : word.toCharArray()) {
int n = c - 'a';
if (tmp.next[n] == null) tmp.next[n] = new TrieNode();
tmp = tmp.next[n];
}
tmp.isEnd = true;
}
/** Returns if the word is in the trie. */
public boolean search(String word) {
TrieNode tmp = root;
for (char c : word.toCharArray()) {
int n = c - 'a';
if (tmp.next[n] == null) return false;
tmp = tmp.next[n];
}
return tmp.isEnd;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
TrieNode tmp = root;
for (char c : prefix.toCharArray()) {
int n = c - 'a';
if (tmp.next[n] == null) return false;
tmp = tmp.next[n];
}
return true;
}
}
/**
* Your Trie object will be instantiated and called as such:
* Trie obj = new Trie();
* obj.insert(word);
* boolean param_2 = obj.search(word);
* boolean param_3 = obj.startsWith(prefix);
*/
长度最小的子数组
题目:给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组，返回 0。
示例:
输入: s = 7, nums = [2,3,1,2,4,3]
输出: 2
解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。
进阶:
如果你已经完成了O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。
思路：这个题怎么说呢，重点是NlogN吧，我觉得这个题出的有问题吧？完成O(n)再去完成O(n log n) ？恐怕占时间太少？我要是没记错n优于nlogn的吧，，反正我先按照我的想法实现了再说吧，最复杂也就n方，每个数作为起始数挨个加，取最短的那个。另外我觉得从一边开始，成为合格子数组了减去最开的那个，往后加。两边来回来去往后面移动。我去代码实现吧，叙述有点说不明白。
好了，做完了，性能还可以，这个题确实不难，我觉得我时间复杂度应该是n吧：
class Solution {
public int minSubArrayLen(int s, int[] nums) {
int min = s+1;
int n = 0;
int num = 0;
for(int i = 0;i<nums.length;i++){
n++;
num += nums[i];
while(num>=s){//目前n个已经完成目标，所以减去最前面的
min = Math.min(n,min);
num -= nums[i+1-n];//把第一个数值减去
n--;//总和中少了第一个，所以-1
}
}
return min>s?0:min;
}
}
性能超过百分之八十八，代码逻辑我觉得也挺清楚的，说实话我还是很好奇这个题怎么用O(n)完成的，我去看看性能排行第一的代码：
class Solution {
public int minSubArrayLen(int s, int[] nums) {
if(nums==null){
return 0;
}
int sum=0;
int length=nums.length+1;
int l=0,r=0;
while(r<nums.length){
sum=sum+nums[r++];//窗口大小不够 右端扩展
while(sum>=s){
//本次更新并试图更优
length=Math.min(length,r-l);
sum=sum-nums[l++];
}
}
if(length==nums.length+1){
return 0;
}
return length;
}
}
一样一样的思路，就是细节处理不太一样。额，好吧，比我的稍微好点。至于nlogn也就是二分之类的了，我就不做了。
今天的笔记就到这里，如果稍微帮到你了记得点个喜欢点个关注，也祝大家工作顺顺利利！生活健健康康！周末娱乐！
网友评论