遞歸

反轉(zhuǎn)字符串

這個(gè)以前實(shí)現(xiàn)過县好， 這次試用遞歸的方式實(shí)現(xiàn)晾咪。

func reverseString(s []byte)  {
    helper(0 , len(s) -1 , s)
}

func helper(start int , end int , s []byte) {
    if end < start {
        return
    }
    
    s[start] , s[end] = s[end] ,s[start]
    
    helper(start+1 , end-1 , s)
}

兩兩交換鏈表中的節(jié)點(diǎn)

不知道如何試用遞歸來完成炬守。不過會在以后的補(bǔ)充鳍置。

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func swapPairs(head *ListNode) *ListNode {
    if head == nil {
        return head
    }
    
    current := head
    next := head.Next
    
    for current != nil && next != nil {
        current.Val , next.Val = next.Val , current.Val
        
        current = next.Next
        
        if current == nil || next.Next == nil {
            break
        } else {
            next = current.Next
        }
    }
    
    return head
}

斐波那契數(shù)列

func fib(N int) int {
    if N == 0 {
        return 0
    }
    if N == 1 {
        return 1
    }
    return fib(N-1) + fib(N-2)
}

爬樓梯

func climbStairs(n int) int {
    if n < 2 {
        return 1
    }
    tmp := []int{1, 2}
    for i := 2; i < n; i++ {
        tmp = append(tmp, tmp[i-1]+tmp[i-2])
    }
    return tmp[n-1]
}

二叉樹的最大深度

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    l := maxDepth(root.Left)
    r := maxDepth(root.Right)
    return max(l, r) + 1
}
func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}

Pow()

func myPow(x float64, n int) float64 {
    if x == 0 {
        return 0
    }
    result := calPow(x, n)
    if n < 0 {
        result = 1 / result
    }
    return result
}
 
func calPow(x float64, n int) float64 {
    if n == 0 {
        return 1
    }
    if n == 1 {
        return x
    }
 
    // 向右移動一位
    result := calPow(x, n>>1)
    result *= result
 
    // 如果n是奇數(shù)
    if n&1 == 1 {
        result *= x
    }
 
    return result
}

第K個(gè)語法符號

用C++ 更簡單

class Solution {
public:
    int kthGrammar(int N, int K) {
        int res = 0;
        while (K > 1) {
            K = (K % 2 == 1) ? K + 1 : K / 2;
            res ^= 1;
        }
        return res;
    }
};

不同的二叉搜索樹 II

class Solution {
public:
    vector<TreeNode *> generateTrees(int n) {
        if (n == 0) return {};
        return *generateTreesDFS(1, n);
    }
    vector<TreeNode*> *generateTreesDFS(int start, int end) {
        vector<TreeNode*> *subTree = new vector<TreeNode*>();
        if (start > end) subTree->push_back(NULL);
        else {
            for (int i = start; i <= end; ++i) {
                vector<TreeNode*> *leftSubTree = generateTreesDFS(start, i - 1);
                vector<TreeNode*> *rightSubTree = generateTreesDFS(i + 1, end);
                for (int j = 0; j < leftSubTree->size(); ++j) {
                    for (int k = 0; k < rightSubTree->size(); ++k) {
                        TreeNode *node = new TreeNode(i);
                        node->left = (*leftSubTree)[j];
                        node->right = (*rightSubTree)[k];
                        subTree->push_back(node);
                    }
                }
            }
        }
        return subTree;
    }
};