Skip to content

Latest commit

 

History

History
114 lines (92 loc) · 3.23 KB

递归思维.md

File metadata and controls

114 lines (92 loc) · 3.23 KB
Raw

递归

介绍

将大问题转化为小问题，通过递归依次解决各个小问题。

示例

334.反转字符串 reverse-string

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

输入：["h","e","l","l","o"] 输出：["o","l","l","e","h"]

思路：递归、交换都可以

var reverseString = function(s) { 
    reverse(s,0,s.length-1);
    return s;
};

var reverse = function(s, left, right){ //递归写法
    if(left >= right){
        return;
    }
    [s[left], s[right]] = [s[right],s[left]];
    reverse(s,left+1,right-1);
}
var reverseString = function(s) {
    let len = s.length;
    for (let i = 0; i < len >> 1; i++) {
        [s[i], s[len - 1 - i]] = [s[len - 1 - i], s[i]];
    }
};
24.两两交换链表中的节点 swap-nodes-in-pairs

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

输入：head = [1,2,3,4] 输出：[2,1,4,3]

function swapPairs(head: ListNode | null): ListNode | null {
    return helper(head)
};
function helper(head: ListNode | null): ListNode | null {
    if(head === null || head.next === null){
        return head
    }
    let headNext: ListNode = head.next.next
    let p: ListNode = head.next
    p.next = head
    head.next = helper(headNext)
    return p
}
95. 不同的二叉搜索树 II

给定一个整数 n，生成所有由 1 ... n 为节点所组成的 二叉搜索树 。

function generateTrees(n: number): Array<TreeNode | null> {
    if (n === 0) {
        return [null]
    }
    return generate(1, n)
};
function generate(start: number, end: number): Array<TreeNode | null> {
    if (start > end) {
        return [null]
    }
    const ans: TreeNode[] = []
    for (let i = start; i <= end; i++) {
        const left: TreeNode[] = generate(start, i - 1)
        const right: TreeNode[] = generate(i + 1, end)
        for (let j = 0; j < left.length; j++) {
            for (let k = 0; k < right.length; k++) {
                const root: TreeNode = new TreeNode(i)
                root.left = left[j]
                root.right = right[k]
                ans.push(root)
            }
        }
    }
    return ans
}
509. 斐波那契数
function fib(n: number): number {
    if (n === 0 || n === 1) {
        return n
    }
    return fib(n - 1) + fib(n - 2)
};

练习