[数据结构与算法]递归的一些练习题（自学版附带灵魂画师图解）

先浅尝一个汉诺塔

public class Solution{

  public static void main(String args[]){
    hanoi(2, 'A', 'B', 'C');

  }

  public static void hanoi(int n, char a, char b, char c) {
    if (n == 1) {
      System.out.println("第1块从"+ a + "到"+ c);
    }else {
      hanoi(n-1, a, c, b);
      System.out.println("第"+n+"块从"+ a + "到"+ c);
      hanoi(n-1, b, a, c);
    }
  }
}

合并两个有序链表

题目

/**
 * 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 mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null) {
            return list2;
        }else if(list2 == null) {
            return list1;
        }else if(list1.val <= list2.val){
        // 这里其实就是一个概括性的步骤，我们并不去仔细想调用自身又干了什么
        // 概括性的步骤意思就是： 如果我当前l1的值小于l2的值，那说明当前
        //l1一定是在l1剩下的和整个l2完成合并之前

            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        }else{
            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }

    }
}

移除链表元素

题目

/**
 * 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 removeElements(ListNode head, int val) {
        if (head == null) {
            return null;
        }
        else if (head.val == val && head.next == null) {
            return null;
        }else if(head.val == val && head.next != null) {
            return removeElements(head.next, val);
        }
        else{
            head.next = removeElements(head.next, val);
            return 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;
        }
        else {
            ListNode cur = reverseList(head.next);
            head.next.next = head;
            head.next = null;
            return cur;
        }

    }
}

2 的幂

题目

class Solution {
    public boolean isPowerOfTwo(int n) {
        if(n == 0){
            return false;
        }else if (n == 1){
            return true;
        }else if (n % 2 == 0 && isPowerOfTwo(n/2)) {   
                return true;
        }else {
            return false;
        }

    }
}

3 的幂

题目

class Solution {
    public boolean isPowerOfThree(int n) {
        if(n == 0 || n == 2) {
            return false;
        }else if (n == 1) {
            return true;
        } else if (n % 3 == 0 && isPowerOfThree(n/3)) {   
                return true;
        }else {
            return false;
        }

    }
}

4 的幂

题目

class Solution {
    public boolean isPowerOfFour(int n) {
        // 方法一，除到底
    //     while(n != 0 && n % 4 == 0) {
    //         n = n / 4;
    //     }
    //     return n == 1;

    // 方法二， 递归
    if (n < 4 && n != 1) {
        // 0 1 2 3
        return false;
    }else if (n == 1) {
        return true;
    }else if(n % 4 == 0 && isPowerOfFour(n/4)){
        return true;
    }else{
        return false;
    }
    }
    
}

反转字符串

题目

class Solution {
    char t = 0;
    public void reverseString(char[] s) {
          reverse(s, 0, s.length - 1);
        }

    public void reverse(char[] s,int begin,int end) {
        if (end - begin >= 1) {
            // 交换首位
            t = s[end];
            s[end] = s[begin];
            s[begin] = t;
            reverse(s, begin+1, end - 1);
        }else {
            return;
        }
        }
    
}