leetCode进阶算法题+解析（二十一）

单词拆分

题目：给定一个非空字符串 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;
        }
    }
}

性能不咋地但是起码过了，我也不知道坑在哪里，这个时候就需要去看评论了。