递归

发表于 2024-03-18 更新于 2023-04-21 分类于 LeetCode 阅读次数：本文字数： 1.8k 阅读时长 ≈ 6 分钟

1.简单递归算法设计

1.1 斐波那契数

斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

1 2	F(0) = 0，F(1) = 1 F(n) = F(n - 1) + F(n - 2)，其中 n > 1

给定 n ，请计算 F(n) 。

思路

直观思路：递归求解，只需记录前一个元素和前前一个元素。

时间优化：矩阵快速幂。

动态规划

class Solution {
    public int fib(int n) {
        // a为前前一个数，b为前一个数
        int a=0,b=1,c=0;
        // 综合优化n=0和1的情况
        for(int i=0;i<n;i++){
            a=b;
            b=c;
            c=a+b;
        }
        return c;
    }
}

矩阵快速幂

class Solution {
    public int fib(int n) {
        if(n<2){
            return n;
        }
        int[][] res=new int[][]{{1,1},{1,0}};
        int[][] ans=quickPow(res,n-1);
        return ans[0][0];
    }
    // 矩阵快速幂
    public int[][] quickPow(int[][] p,int n){
        int[][] ret=new int[][]{{1,0},{0,1}};
        while(n>0){
            if((n&1)==1){
                ret=multiply(ret,p);
            }
            n>>=1;
            p=multiply(p,p);
        }
        return ret;
    }
    // 矩阵乘法
    public int[][] multiply(int[][] a,int[][] b){
        int[][] ans=new int[2][2];
        for(int i=0;i<2;i++){
            for(int j=0;j<2;j++){
                ans[i][j]=a[i][0]*b[0][j]+a[i][1]*b[1][j];
            }
        }
        return ans;
    }
}

1.2 Pow(x,n)

实现 pow(x, n) ，即计算 x 的整数 n 次幂函数（即，xn ）。

思路

矩阵快速幂，若指数为偶数，那么x*x；若为奇数，那么x*x*ans，最终ans即为所求

代码

class Solution {
    public double myPow(double x, int n) {
        double ans=1.0;
        // 判断指数正负
        long t=n;
        if(t<0){
            t=-t;
            x=1/x;
        }
        // 运算
        while(t>0){
            // 判断是否为奇数
            if((t&1)==1){
                ans*=x;
            }
            // 指数右移一位，表示除以2
            t>>=1;
            x*=x;
        }
        return ans;
    }
}

1.3 反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

思路

按照节点依次反转链表。

递归

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        // 遍历到最后一个节点直接返回
        if(head==null||head.next==null){
            return head;
        }
        // 新的头节点
        ListNode root=reverseList(head.next);
        // 当前节点的下一节点的下一节点指向当前节点
        // 即调换两者顺序
        head.next.next=head;
        // 尾节点指向null
        head.next=null;
        return root;
    }
}

迭代

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        // cur指向当前节点，pre指向前一节点
        ListNode cur=head,pre=null;
        while(cur!=null){
            ListNode next=cur.next;
            // 反转后，cur的下一节点即为前一节点pre
            cur.next=pre;
            // 对下一节点而言，pre即是当前节点
            pre=cur;
            // cur指向下一节点
            cur=next;
        }
        return pre;
    }
}

1.4 回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

思路

先找到前半部分链表的尾节点
反转后半部分链表
判断是否回文

代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head==null) return true;
        ListNode tail=findTail(head);
        ListNode reverseNode=reverse(tail.next);
        ListNode p=head;
        ListNode q=reverseNode;
        // 判断是否回文
        // 临界条件是q!=null，因为节点个数可能为奇数
        while(q!=null){
            if(p.val!=q.val){
                return false;
            }
            p=p.next;
            q=q.next;
        }
        return true;
    }
    // 快慢指针寻找尾节点
    public ListNode findTail(ListNode root){
        ListNode slow=root;
        ListNode fast=root;
        // fast比slow快一倍，fast指向null时，slow即指向中点
        while(fast.next!=null&&fast.next.next!=null){
            slow=slow.next;
            fast=fast.next.next;
        }
        return slow;
    }
    // 迭代反转链表
    public ListNode reverse(ListNode head){
        ListNode cur=head,pre=null;
        while(cur!=null){
            ListNode next=cur.next;
            cur.next=pre;
            pre=cur;
            cur=next;
        }
        return pre;
    }
}

1.5 两两交换链表中的节点

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

思路

递归模拟。

代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head==null||head.next==null){
            return head;
        }
        // 新的头节点为当前头节点的下一节点
        ListNode root=head.next;
        // 当前节点的下一节点即为后续已交换的头节点
        head.next=swapPairs(root.next);
        // 交换两个节点的位置
        root.next=head;
        return root;
    }
}

2. 复杂递归算法设计

2.1 螺旋矩阵 II

给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。

思路

按照题意进行模拟，注意四个方向。

代码

class Solution {
    public int[][] generateMatrix(int n) {
        int[][] cnt=new int[n][n];
        int left=0,right=n-1,top=0,bottom=n-1;
        int num=1;
        while(true){
            // 向右
            for(int i=left;i<=right;i++) cnt[top][i]=num++;
            // top+1，判断是否越界
            if(++top>bottom) break;
            // 向下
            for(int i=top;i<=bottom;i++) cnt[i][right]=num++;
            // right-1，判断是否越界
            if(--right<left) break;
            // 向左
            for(int i=right;i>=left;i--) cnt[bottom][i]=num++;
            // bottom-1，判断是否越界
            if(--bottom<top) break;
            // 向上
            for(int i=bottom;i>=top;i--) cnt[i][left]=num++;
            // left+1，判断是否越界
            // 开启新一轮循环
            if(++left>right) break;
        }
        return cnt;
    }
}

2.2 N 皇后

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

思路

经典回溯算法问题，n = 8 时便是著名的八皇后问题。

依次判断当前位置是否有效，以决定是否将当前位置加入棋盘中。

代码

class Solution {
    private List<List<String>> res=new ArrayList<>();
    private List<StringBuilder> tmp=new ArrayList<>();
    private int n;
    public List<List<String>> solveNQueens(int n) {
        this.n=n;
        for(int i=0;i<n;i++){
            // 初始化空棋盘
            StringBuilder cnt=new StringBuilder();
            for(int j=0;j<n;j++){
                cnt.append('.');
            }
            tmp.add(cnt);
        }
        backtrack(0);
        return res;
    }
    public void backtrack(int row){
        // row==n，说明出现了一种正确方案
        if(row==n){
            // StringBuilder与String转化
            List<String> hep=tmp.stream().map(s -> s.toString()).collect(Collectors.toList());
            res.add(hep);
            return;
        }
        for(int i=0;i<n;i++){
            // 判断当前位置是否有效
            if(!isValid(row,i)){
                continue;
            }
            // 回溯匹配
            tmp.get(row).setCharAt(i,'Q');
            backtrack(row+1);
            tmp.get(row).setCharAt(i,'.');
        }
    }
    public boolean isValid(int row,int col){
        // 判断左上角是否已有Queen
        for(int i=row-1,j=col-1;i>=0&&j>=0;i--,j--){
            if(tmp.get(i).charAt(j)=='Q'){
                return false;
            }
        }
        // 判断当前列是否已有Queen
        for(int i=row-1,j=col;i>=0;i--){
            if(tmp.get(i).charAt(j)=='Q'){
                return false;
            }
        }
        // 判断右上方是否已有Queen
        for(int i=row-1,j=col+1;i>=0&&j<n;j++,i--){
            if(tmp.get(i).charAt(j)=='Q'){
                return false;
            }
        }
        return true;
    }
}