Conditions

We refer to a recursive function as tail-recursion when the recursive call is the last thing that function executes. Otherwise, it’s known as head-recursion.
Iteration will be more complicated and harder to understand compared to recursion, for example: traversing a binary tree.
DFS 图算法 => master theorem

Questions

21

 /**
 * 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) {
     // Base case: if either list is null, return the other list
     if (list1 == null) {
         return list2;
     } else if (list2 == null) {
         return list1;
     }

     // Recursive case: compare the values at the current nodes of both lists
     if (list1.val < list2.val) {
         // If the value in l1 is smaller, merge the rest of l1 with the remaining nodes in l2
         list1.next = mergeTwoLists(list1.next, list2);
         return list1;
     } else {
         // If the value in l2 is smaller, merge the rest of l2 with the remaining nodes in l1
         list2.next = mergeTwoLists(list1, list2.next);
         return list2;
     } 
     }
 }

203

 /**
 * 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) {
         // Base case: if the head of the list is null, return null
     if (head == null) {
         return null;
     }

     // Recursive case: remove the target value from the rest of the list
     head.next = removeElements(head.next, val);
     // If the value of the head node is equal to the target value, return the rest of the list
     if (head.val == val) {
         return head.next;
     } else {
         // Otherwise, return the head node
         return head;
     }
     }
 }

206

 /**
 * 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) {
     // Base case: if the list is empty or has only one node, return the head
     if (head == null || head.next == null) {
         return head;
     }

     // Recursive case: reverse the rest of the list and append the head to the end
     ListNode reversedList = reverseList(head.next);
     head.next.next = head;
     head.next = null;

     // Return the new head of the reversed list
     return reversedList;
     }
 }

509

 class Solution {
     public int fib(int n) {
         // Base case: if n is 0 or 1, return n
     if (n <= 1) {
         return n;
     }

     // Recursive case: compute the nth Fibonacci number as the sum of the previous two numbers
     return fib(n - 1) + fib(n - 2);
     }
 }

234

 class Solution {

     // Define a private ListNode variable named frontPointer
     // to keep track of the front node of the linked list
     private ListNode frontPointer;

     // Define a private boolean method named recursivelyCheck
     // that takes a ListNode parameter named currentNode as input
     private boolean recursivelyCheck(ListNode currentNode) {

         // If currentNode is not null
         if (currentNode != null) {

             // Recursively call recursivelyCheck on the next node and check if the returned value is false
             if (!recursivelyCheck(currentNode.next)) return false;

             // Check if the value of currentNode is equal to the value of the node pointed to by frontPointer
             if (currentNode.val != frontPointer.val) return false;

             // Move the frontPointer to the next node
             frontPointer = frontPointer.next;
         }

         // Return true to the caller
         return true;
     }

     // Define a public boolean method named isPalindrome that takes a ListNode parameter named head as input
     public boolean isPalindrome(ListNode head) {

         // Set frontPointer to head
         frontPointer = head;

         // Call the recursivelyCheck method with head as input and return the result
         return recursivelyCheck(head);
     }
 }

24

 /**
 * 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) {
     // Base case: return the given list if it is null or contains only one node
     if (head == null || head.next == null) {
         return head;
     }

     // Recursive case: swap the first two nodes in the list
     ListNode firstNode = head;
     ListNode secondNode = head.next;
     firstNode.next = swapPairs(secondNode.next);
     secondNode.next = firstNode;

     // Update the head of the list with the result of the recursive call
     head = secondNode;

     // Return the updated head of the list
     return head;
     }
 }

143

 /**
 * 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 void reorderList(ListNode head) {
         // Base case: return the given list if it is null or contains only one node
         if (head == null || head.next == null) {
             return;
         }

         // Find the midpoint of the list
         ListNode slow = head;
         ListNode fast = head;
         while (fast.next != null && fast.next.next != null) {
             slow = slow.next;
             fast = fast.next.next;
         }

         // Reverse the second half of the list
         ListNode secondHalf = reverseList(slow.next);
         slow.next = null;

         // Merge the first and second halves of the list
         mergeLists(head, secondHalf);
     }

     // Helper function to reverse a list
     private ListNode reverseList(ListNode head) {
         // Base case: return the given list if it is null or contains only one node
         if (head == null || head.next == null) {
             return head;
         }

         // Recursive case: reverse the rest of the list and append the current node to the end
         ListNode reversedList = reverseList(head.next);
         head.next.next = head;
         head.next = null;

         return reversedList;
     }

     // Helper function to merge two lists by alternating their nodes
     private void mergeLists(ListNode list1, ListNode list2) {
         while (list1 != null && list2 != null) {
             ListNode next1 = list1.next;
             ListNode next2 = list2.next;
             list1.next = list2;
             list2.next = next1;
             list1 = next1;
             list2 = next2;
         }
     }
 }

241

 class Solution {
     public List<Integer> diffWaysToCompute(String expression) {
         List<Integer> result = new ArrayList<Integer>();

         // Base case: if the expression is a single number, return it as a list
         if (expression.matches("\\d+")) {
             result.add(Integer.valueOf(expression));
             return result;
         }

         // Recursive case: split the expression by each operator and recursively evaluate
         for (int i = 0; i < expression.length(); i++) {
             char c = expression.charAt(i);
             if (c == '+' || c == '-' || c == '*') {
                 String leftExpression = expression.substring(0, i);
                 String rightExpression = expression.substring(i + 1);

                 // Recursively evaluate the left and right expressions
                 List<Integer> leftResult = diffWaysToCompute(leftExpression);
                 List<Integer> rightResult = diffWaysToCompute(rightExpression);

                 // Combine the left and right results using the operator
                 for (Integer left : leftResult) {
                     for (Integer right : rightResult) {
                         if (c == '+') {
                             result.add(left + right);
                         } else if (c == '-') {
                             result.add(left - right);
                         } else if (c == '*') {
                             result.add(left * right);
                         }
                     }
                 }
             }
         }

         // Return the final result
         return result;
     }
 }

779

 class Solution {
     public int kthGrammar(int n, int k) {
     // Base case: if n is 1, the only possible symbol is 0
     if (n == 1) {
         return 0;
     }

     // Recursive case: determine which half of the previous row the kth symbol belongs to
     int prevLength = (int) Math.pow(2, n - 2);
     if (k <= prevLength) {
         // The kth symbol is in the first half of the previous row
         return kthGrammar(n - 1, k);
     } else {
         // The kth symbol is in the second half of the previous row
         int complement = kthGrammar(n - 1, k - prevLength);
         // Flip the complement of the kth symbol in the previous row
         return complement == 0 ? 1 : 0;
     }
     }
 }

1265

 /**
 * // This is the ImmutableListNode's API interface.
 * // You should not implement it, or speculate about its implementation.
 * interface ImmutableListNode {
 *     public void printValue(); // print the value of this node.
 *     public ImmutableListNode getNext(); // return the next node.
 * };
 */

 class Solution {
     public void printLinkedListInReverse(ImmutableListNode head) {
         if (head == null) {
             return; // base case: return if the list is empty
         }
         printLinkedListInReverse(head.getNext()); // recursive call to print the next node in the list
         head.printValue(); // print the value of the current node after the recursive call
     }
 }

1545

 class Solution {
     public char findKthBit(int n, int k) {
         if (n == 1) {
         return '0';
     }
     int length = (int) Math.pow(2, n) - 1; // Calculate length of the current string
     if (k == length / 2 + 1) { // If k is the middle element, return 1
         return '1';
     } else if (k < length / 2 + 1) { // If k is in the first half, recursively search for k in the next string
         return findKthBit(n - 1, k);
     } else { // If k is in the second half, recursively search for the complement of k in the next string and invert it
         char complement = findKthBit(n - 1, length - k + 1);
         return complement == '0' ? '1' : '0';
     } 
     }
 }

1823

 class Solution {
     public int findTheWinner(int n, int k) {
     // Base case: if there is only one player, that player wins
     if (n == 1) {
         return 1;
     }

     // Recursive case: find the winner of a smaller game with n-1 players and k positions
     int winner = findTheWinner(n - 1, k);

     // Calculate the index of the next player to be eliminated
     int nextPlayer = (winner + k - 1) % n + 1;

     // Return the index of the winner
     return nextPlayer;
     }
 }

Conclusion

「少种的少收，多种的多收,捐款会鼓励作者多创作以及教会福音传播!!」

刷题(三)

Recursion 笔记整理

Conditions

Questions

21

203

206

509

234

24

143

241

779

1265

1545

1823

Conclusion

CATALOG

FEATURED TAGS