[数据结构与算法]力扣day15

117. 填充每个节点的下一个右侧节点指针 II

    public Node connect(Node root) {
        if (root == null)
            return root;
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int levelCount = queue.size();
            Node pre = null;
            for (int i = 0; i < levelCount; i++) {
                Node node = queue.poll();
                if (pre != null) {
                    pre.next = node;
                }
                pre = node;
                if (node.left != null)
                    queue.add(node.left);
                if (node.right != null)
                    queue.add(node.right);
            }
        }
        return root;
    }

572. 另一个树的子树

    public boolean isSubtree(TreeNode s, TreeNode t) {
        if (s == null && t == null)
            return true;
        if (s == null || t == null) return false;
        if (isEqual(s, t)) {  //直接比较节点，简略些
            return true;
        }
        return isSubtree(s.left, t) || isSubtree(s.right, t);
    }

    public boolean isEqual(TreeNode l, TreeNode r) {
        if (l == null && r == null) return true;
        if (l == null || r == null) return false;
        if (l.val == r.val) return isEqual(l.left, r.left) && isEqual(l.right, r.right);
        return false;
    }

59. 螺旋矩阵 II

   public int[][] generateMatrix(int n) {
        int[][] ans = new int[n][n];
        int t = 0, b = n - 1, l = 0, r = n - 1; //t为上边界；b为下边界；l为左边界；r为右边界
        int i = 1;  //记录每个位置的值
        while(i <= n * n) { //每个位置的值不可能超过n的平方
            for(int j = l; j <= r; j++) //从左遍历到右边
                ans[t][j] = i++;
            t++;
            for(int j = t; j <= b; j++) //从上到下
                ans[j][r] = i++;
            r--;
            for(int j = r; j >= l; j--) //从右到左
                ans[b][j] = i++;
            b--;
            for(int j = b; j >= t; j--) //从下到上
                ans[j][l] = i++;
            l++;
        }
        return ans;
    }

60.排列序列

本来用回溯结果超时
还是得看题解找规律

 public String getPermutation(int n, int k) {
        List<Integer> ans = new ArrayList<>();
        // 事先将 1 2 3 放入 ans
        for (int i = 1; i <= n; i++) {
            ans.add(i);
        }
        int[] fact = new int[n];
        // 第一组首元素一定是 1
        fact[0] = 1;
        // 求剩下元素在对于每个 i 情况下的阶乘 n!
        for (int i = 1; i < n; i++) {
            // 当 i 是 1，就是 1!
            // 当 i 是 2，就是 2!
            fact[i] = i * fact[i - 1];
        }
        // 转变为找下标是第 k - 1 的排列情况
        k = k - 1;
        StringBuilder sb = new StringBuilder();
        for (int i = n; i > 0; i--) {
            int index = k / fact[i - 1];
            // 去掉上一轮计算过的数，初始下一轮的 k
            k = k % fact[i - 1];
            // 找到的第一个数先加到 sb 后面
            sb.append(ans.get(index));
            // 然后再把原来位置上的这个数去除掉
            ans.remove(index);
        }
        return sb.toString();
    }

61.旋转链表

感觉双指针其实更好理解

    public ListNode rotateRight(ListNode head, int k) {
           if(head == null)
            return head;
        int len = 1;
        ListNode temp = head;
        //记录长度
        while(temp.next != null){
            temp = temp.next;
            len++;
        }
        //首尾相连
        temp.next = head;
        int node = (len - k % len);
        //找到新的头结点
        for(int i = 0;i < node;i++){
            temp = temp.next;
        }
        ListNode res = temp.next;
        temp.next = null;
        return res;
    }