【LeetCode】Day22-全排列

剑指 Offer 22. 链表中倒数第k个节点【简单】

数个数然后找倒数第k个的方法就不说了

介绍一下快慢指针，让快慢指针间隔k个结点，快指针到尾部的时候，慢指针就到目标结点了

class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode fast=head,slow=head;
        while(fast!=null&&k>0){
            fast=fast.next;
            k--;
        }
        while(fast!=null){
            fast=fast.next;
            slow=slow.next;
        }
        return slow;
    }
}

时间复杂度： O ( n ) O(n) O(n)

空间复杂度： O ( 1 ) O(1) O(1)

46. 全排列【中等】

大概是个经典回溯法的题吧

之前还是大二的算法与程序设计课讲过回溯法，现在早忘完了…题解中说到一句话：“树中的深度优先遍历就是大名鼎鼎的回溯算法”，趁着这道题来回顾一下吧

回溯法：一种通过探索所有可能的候选解来找出所有的解的算法。如果候选解被确认不是一个解（或者至少不是最后一个解），回溯算法会通过在上一步进行一些变化抛弃该解，即回溯并且再次尝试。如图所示：

说明：

每一个结点表示了求解全排列问题的不同的阶段使用深度优先遍历有「回头」的过程，在「回头」以后， 状态变量需要设置成为和先前一样 ，因此在回到上一层结点的过程中，需要撤销上一次的选择，这个操作称之为「状态重置」

需要的辅助变量：

index：表示当前要确定的是某个全排列中下标为 index 的那个数是多少used：初始化的时候都为 false 表示这些数还没有被选择，当我们选定一个数的时候，就将这个数组的相应位置设置为 true ，这样在考虑下一个位置的时候，就能够以 O(1) 的时间复杂度判断这个数是否被选择过

递归结束标志：排列的所有位置都遍历完了，即 index 到头的时候

class Solution {
    private List>res=new ArrayList<>();
    public List> permute(int[] nums) {
        int len=nums.length;
        if(len==0)
            return res;
        boolean[] used=new boolean[len];
        Listpath=new ArrayList<>();//记录每一种全排列情况
        dfs(nums,0,path,used);
        return res;
    }
    public void dfs(int[] nums,int index,Listpath,boolean[] used){
        if(index==nums.length){
            res.add(new ArrayList<>(path));//path指向的内存地址的内容在不断变化，而我们每次只需要添加path的一次快照，所以需要用new ArrayList(path), 否则最终res集合中的所有元素都是相同的。
            return;
        }
        for(int i=0;i 
p.s. 今天这题好难理解，看完题解脑袋还是晕晕的…
 
p.p.s 昨天本科同学来玩！于是又歇了一天，发现自己做题三周了，虽然没特意定休息日，但似乎每周都会歇一天，纯属巧合