leetcode算法笔记（持续更新）

5. Longest palindromic substring(最长回文子串)：中心扩展算法
11. Container With Most Water（盛最多水的容器）：双指针法
15. 3sum（找到数组中的三个数的下标使得其a+b+c=0）：双指针法（先对数组排序，然后去除重复元素，和题11一样，在数组前后各设置一个指针，然后根据条件移动）
17. Letter Combinations of a Phone Number(电话号码字母组合)：哈希表、递归调用
19. Remove Nth Node From End of List（删除链表中倒数第N个节点）：双指针法（先让两个指针分别指向头结点，然后令第一个指针first前进N，再令两个指针同时前进直至first为null）
55. jump game(跳跃游戏)：动态规划（自底向上）

class Solution {
    public boolean canJump(int[] nums) {
        int len = nums.length;
        if(len < 2)
            return true;
        int[] dp = new int[len];
        dp[len - 1] = 1;
        for(int i = len - 2; i >= 0; i--){
            int furthestIndex = Math.min(i + nums[i], len - 1); //跳过之后最远的坐标
            //如果nums[i]=0,则这个循环不会发生
            for(int j = i + 1; j <= furthestIndex; j++){    
                if(dp[j] == 1){
                    dp[i] = 1;
                    break;
                }
            }
        }
        return dp[0] == 1;
    }
}

94. Binary Tree Inorder Traversal(二叉树的非递归中序遍历)：栈（a.创建一个栈，根节点入栈；b.栈非空，则栈顶节点的非空左节点相继进栈；c.弹出栈顶节点并将该弹出的节点的非空右节点入栈；d.重复bc步骤）

 import java.util.LinkedList;
 import java.util.ArrayList;
 class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        LinkedList<TreeNode> stack = new LinkedList<>();
        List<Integer> list = new ArrayList<>();
        if(root == null)
            return list;
        stack.push(root);
        while(!stack.isEmpty())
        {
            while(stack.peek() != null)
                stack.push(stack.peek().left);
            stack.pop();    //移除栈顶的空节点
            if(!stack.isEmpty())
            {
                TreeNode node = stack.pop();
                list.add(node.val);
                stack.push(node.right);
            }
        }
        return list;
    }
}

105. Construct Binary Tree from Preorder and Inorder Traversal(从前序与中序遍历序列构造二叉树):递归

return solve(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
public TreeNode slove(int[] preorder, int begin1, int end1, int[] inorder, int begin2, int end2)
{}

106. (非hot100)Construct Binary Tree from Inorder and Postorder Traversal(从二叉树的中序和后序遍历序列构造一棵二叉树)：递归

return solve(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
public TreeNode slove(int[] inorder, int begin1, int end1, int[] postorder, begin2, int end2)
{}

140.Word-Break-ii(单词拆分)：DFS(只是实现了一个DFS方法，实际上用的是递归？)