ARTS 第36周：最大二叉树算法、RESTful API最佳实践、递归与分布式系统

#coding#arts
目录

Algorithm

package org.nocoder.leetcode.solution;

import org.nocoder.leetcode.solution.common.TreeNode;

/**
 * 654.Maximum Binary Tree
 * Given an integer array with no duplicates.
 * A maximum tree building on this array is defined as follow:
 *
 * The root is the maximum number in the array.
 * The left subtree is the maximum tree constructed from left part subarray divided by the maximum number.
 * The right subtree is the maximum tree constructed from right part subarray divided by the maximum number.
 * Construct the maximum tree by the given array and output the root node of this tree.
 *
 * Example 1:
 * Input: [3,2,1,6,0,5]
 * Output: return the tree root node representing the following tree:
 *
 *       6
 *     /   \
 *    3     5
 *     \    /
 *      2  0
 *        \
 *         1
 * Note:
 * The size of the given array will be in the range [1,1000].
 * @author jason
 * @date 2019/4/7.
 */
public class MaximumBinaryTree {
    public static void main(String[] args) {
        int[] arr = new int[]{3, 2, 1, 6, 0, 5};
        TreeNode treeNode = constructMaximumBinaryTree(arr);
        treeNode.print();
    }

    public static TreeNode constructMaximumBinaryTree(int[] nums) {
        return construct(nums, 0, nums.length);
    }
    public static TreeNode construct(int[] nums, int l, int r) {
        if (l == r) {
            return null;
        }
        int max_i = max(nums, l, r);
        TreeNode root = new TreeNode(nums[max_i]);
        root.left = construct(nums, l, max_i);
        root.right = construct(nums, max_i + 1, r);
        return root;
    }
    public static int max(int[] nums, int l, int r) {
        int max_i = l;
        for (int i = l; i < r; i++) {
            if (nums[max_i] < nums[i]) {
                max_i = i;
            }
        }
        return max_i;
    }
}

Review

10 best practices for better restfull api

Tip

递归和调用栈

最近在读《算法图解》，真的非常易读非常有意思，第三章讲递归，图文并茂描述的浅显易懂，把章节中的内容写了笔记，整理一下，作为本周的Tip吧。

递归

假设我们需要找一把钥匙，钥匙在一个大盒子里，这个盒子里有盒子，盒子里的盒子有有盒子，钥匙就在某个盒子里。

以下是使用递归方法寻找钥匙的伪代码：

def look_for_key(box):
    for item in box:
        if item.is_a_box():
            look_for_box()
        elif item.is_key(item):
            print "found the key"

递归只是让解决方案更清晰，并没有性能上的优势。Leigh Caldwell在Stack Overflow 上说过一句话：“如果使用循环，程序的性能可能更高；如果使用递归，程序可能更容易理解。如何选择要看什么对你来说更重要。”

编写递归方法时，必须告诉它何时停止递归，所以，每个递归函数都有两部分，基线条件和递归条件。递归条件是指函数调用自己，而基线条件是指函数不在调用自己，从而避免形成无线循环。在上面的找钥匙的例子中，item.is_a_box()就是递归条件，item.is_key(item)就是基线条件。

调用栈

def greet(name):
    print "hello " + name
    greet2(name)
    bye()
    
def greet2(name):
    print "how are you " + name
    
def bye():
    print "bye"

假设我们调用greet(“jason”)，看看调用这个方法的具体情况

这个栈用于存储多个函数的变量，称为调用栈

参考文献：《算法图解》

Share

分布式系统的技术栈

评论区