单词拆分
题目：给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
说明：
拆分时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。
示例 1：
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。
示例 2：
输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
注意你可以重复使用字典中的单词。
示例 3：
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false
思路：这道题看似简单，越想越难。首先这个可能性很多。我觉得用递归不错。首先最主要的是把list换成set。利用set的contains判断是否有可拆分的串。然后把给定的字符串抛出去可拆分的串剩下的递归，如过能拆到字符串为null说明是true。注意下从头开始可拆分的串就不是一定的，把所有可能的分支都要走一遍。目前思路就这样，暂时决定暴力法解题。我去代码实现下看看。
class Solution {
HashSet ar = new HashSet<String>();
public boolean wordBreak(String s, List<String> wordDict) {
Set<String> set = new HashSet<String>(wordDict);
return dfs(s,set);
}
public boolean dfs(String s,Set<String> set){
//当字符串长度为0或者剩余的字符串直接出现在字典则直接返回true
if(s.length()==0 || set.contains(s)) return true;
for(int i = 1; i<s.length();i++){
String s1 = s.substring(0,i);
if(set.contains(s1) && dfs(s.substring(i),set)){
return true;
}
}
return false;
}
}
首先暴力法写出来了，其次提交没通过，因为超时。然后三十几个测试案例我过了29个，我决定代码逻辑是没问题。但是这么暴力有点问题。
然后这个性能的话，只能照着这个思路调优啦。其实之前在做的时候我是有点思路的，我看了超时的测试案例，是都是aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
这样一个串，每个a都走一遍，想想都可怕。。。所以我要看看这块要怎么调整。
这个题我放弃了，改了n次，次次超时，后来看了题解，差不多的代码，百分之八十相同的思路。人家过了，我超时了，脑壳痛。
我直接上人家的代码把：
public class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
return word_Break(s, new HashSet(wordDict), 0, new Boolean[s.length()]);
}
public boolean word_Break(String s, Set<String> wordDict, int start, Boolean[] memo) {
if (start == s.length()) {
return true;
}
if (memo[start] != null) {
return memo[start];
}
for (int end = start + 1; end <= s.length(); end++) {
if (wordDict.contains(s.substring(start, end)) && word_Break(s, wordDict, end, memo)) {
return memo[start] = true;
}
}
return memo[start] = false;
}
}
是我刚刚思路的进化版，他加了个boolean来记忆到某个位置是不是已经可以做中断位。如果是改为true。不是则是false。
这里要注意一点，他用的Boolean。默认值是null，true和false都是后赋值的，所以这里不等于null则返回值本身是比我用boolean好的多的操作。
然后剩下的逻辑就很简单了，因为我最开始用数字截取的办法，所以是不能这么做的，只能定一个开始的下标start常量了。
然后我还看了下这个题有人用dp做出来了，我再去研究研究动规怎么写。
我直接贴代码（我是参考题解背着默写的，哈）：
public class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
Set<String> wordDictSet=new HashSet(wordDict);
boolean[] dp = new boolean[s.length() + 1];
dp[0] = true;
for (int i = 1; i <= s.length(); i++) {
for (int j = 0; j < i; j++) {
if (dp[j] && wordDictSet.contains(s.substring(j, i))) {
dp[i] = true;
break;
}
}
}
return dp[s.length()];
}
}
首先这是很精巧的思路，也是用boolean数组辅助判断的。再次重申这句话，动态规划就是记录中间过程的递归。
然后是双层循环，外层循环的第i个元素之前是不是可以被分词。
首先照着代码理逻辑:
这里设置dp[0]是true。当这个要拆分的串是空串肯定可以被拆分。
然后往下递归，dp[下标]是为了表示到某下标为止，之前的是可以正好被拆分的。
比如 canam ;如果可以拆成ca.na，c,an,a无论怎么拆，但是有一点是固定的，就是在第二个a的之前都是可以正常拆分的，我们只要知道在这之后的是不是可以正常拆分。
然后因为截取字符串包前不包后，所以虽然是判断到了substring（j,i），但是我们得到的结果是i前面那个元素的结果。
这里的boolean下标和实际字符串的下标是多了1的。
然后这个题就简单了啊。只要确定到了某位置，这个为止是可以正好拆分的就设置前一个boolean值true。最后我们只要判断最后一个字符的+1的布尔值是正是负就行了。
反正动规其实就是这么个特点，乍一眼看很懵，但是只要思路理清楚了，就很简单了。这个题就到这里了。下一题了。
环形链表2
题目：给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。说明：不允许修改给定的链表。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：tail connects to node index 1
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0
输出：tail connects to node index 0
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：no cycle
解释：链表中没有环。
进阶：
你是否可以不用额外空间解决此题？
题目截图
思路：好像做过类似的，我当时好像用的快慢指针还是啥来着？其实这个题用额外空间就很简单啦，每个节点放set，如果出现contains说明环了。并且第一个出现contains的节点就是环的头节点，但是！！现在不让用额外空间，应该还是用双指针。快慢指针只要有重合就说明有环，重点是环入口是什么。。我想想。
好了，琢磨半小时数学总算是理明白逻辑了，这里有一点：慢指针决定不可能跑完一整圈环。因为快指针是慢指针速度两倍，而环最少两个节点，所以节点越多说明快指针追上的越快。不过这个不重要，有这个意识就行了。然后到了画图的环节，这个比较复杂所以我决定手画。
草图
然后我觉得这个就可以明白了。。还有一个更草的解释：
红色线绿色线长度是一样的，虚线部分长度也是一样的，所以a和B不知道多少圈，反正和A的交点肯定会是入口
image.png
然后数学懂了代码就是分分钟的事，我直接贴代码了：
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode fast = head, slow = head;
while (true) {
if (fast == null || fast.next == null) return null;
fast = fast.next.next;
slow = slow.next;
if (fast == slow) break;
}
fast = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return fast;
}
}
下一题了直接。
重排链表
题目：给定一个单链表 L：L0→L1→…→Ln-1→Ln ，将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例 1:
给定链表 1->2->3->4, 重新排列为 1->4->2->3.
示例 2:
给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.
思路：这个题又不知道怎么混进来的，简单的离谱了啊。我打算都add进list。然后第一个的下一个是最后一个，最后一个变成第二个，第二个的下一个正数第二个，正数第二个就变成第三了，第三个的下一个倒数第二个，以此类推。我先去实现下看有什么坑。
做的过程中觉得list太麻烦了，我用了双端队列。直接贴代码:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public void reorderList(ListNode head) {
LinkedList<ListNode> queue = new LinkedList<>();
ListNode cur = head;
while (cur != null) {
queue.addLast(cur);
cur = cur.next;
}
while (!queue.isEmpty()) {
if (cur == null) {
cur = queue.pollFirst();
} else {
cur.next = queue.pollFirst();
cur = cur.next;
}
cur.next = queue.pollLast();
cur = cur.next;
}
if (cur != null) {
cur.next = null;
}
}
}
性能不咋地但是起码过了， 我也不知道坑在哪里，这个时候就需要去看评论了。
image.png
没话讲，我觉得简单是因为没读懂题目？呵~~~~
笑而不语。
然后这个大大的方法其实也不是很难懂，我就不明白不也是中间接next么？算了吧，我也贴出来大家可以看一下:
void reorderList(ListNode* head) {
if(head==NULL || head->next == NULL)
return;
//快慢指针分出两段
ListNode *slow = head,*fast = head;
while(fast->next && fast->next->next){
slow = slow->next;
fast = fast->next->next;
}
//后端反转
ListNode *needReverser = slow->next;
slow->next = NULL;
needReverser = reverse(needReverser);
//插入前端缝隙
ListNode *cur = head;
while(cur && needReverser){
ListNode *curSecond = needReverser;
needReverser = needReverser->next;
ListNode *nextCur = cur->next;
curSecond->next = cur->next;
cur->next = curSecond;
cur = nextCur;
}
}
ListNode *reverse(ListNode *head){
ListNode *p1 = NULL;
ListNode *p2 = head;
ListNode *p3 = p2;
while(p2){
p3 = p2->next;
p2->next = p1;
p1 = p2;
p2 = p3;
}
return p1;
}
今天的笔记就记到这里，很丧，本来是周四的学习笔记，现在写完凌晨十二点半了。。。主要是今天工作很忙，一点没空做，然后最开始的两道题还都比较麻烦，尤其是第二道题，数学思路就寻思了不到一个小时，哎~~~~如果稍微帮到你了记得点个喜欢点个关注，另外祝大家工作顺顺利利！生活健健康康！
网友评论