Combinations {代码...} 回溯法 复杂度 时间复杂度最坏情况O(n!)空间栈一样O(n!) 代码 {代码...}

与i不同的是有重复的数字， 例如[1,2(1)] [1,2(2)]情况相同， 递归过程中每次新选取的可以是和递归数组相同的，（比如nums是[1，2，2，2］ 当前递归栈是［1，2（1）］ 新加入的［1，2(1), 2(2)]是合法的） 但是后面的元素就不能相同了（［1, 2(1), 2(3)]就不合法 因为重复了）。新选取的元素在递归栈里就是每次当i取inde...

Given a digit string, return all possible letter combinations that thenumber could represent. A mapping of digit to letters (just like on the telephone buttons) isgiven below. Input:Digit string "23" Output: ["ad", "ae", "af", "bd", "be", "bf","cd", "ce", "cf"].

Given n pairs of parentheses, write a function to generate allcombinations of well-formed parentheses. For example, given n = 3, a solution set is: "((()))", "(()())", "(())()", "()(())", "()()()"

Given a string S and a string T, count the number of distinctsubsequences of T in S. A subsequence of a string is a new string which is formed from theoriginal string by deleting some (can be none) of the characterswithout disturbing the relative positions of the remaining characters.(ie, "ACE" i...

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1and s2. For example, Given: s1 = "aabcc", s2 = "dbbca", When s3 = "aadbbcbcac", return true. When s3 = "aadbbbaccc", returnfalse.

Triangle {代码...} 动态规划 思路 自底向上求解, {代码...} 复杂度 时间O(n^2) 空间O(n^2) 代码 {代码...} 一维动态规划 思路 维护一个长度为n的数组, 每次只更新当前数组 复杂度 时间O(n^2) 空间O(n) 代码 {代码...}

A message containing letters from A-Z is being encoded to numbersusing the following mapping: 'A' -> 1 'B' -> 2 ... 'Z' -> 26 Given an encoded message containingdigits, determine the total number of ways to decode it. For example, Given encoded message "12", it could be decoded as "AB"(1...

state: f[i] 表示爬到第i个楼梯的所有方法的和function： f[i] = f[i-1] + f[i-2] //因为每次走一步或者两步， 所以f[i]的方法就是它一步前和两步前方法加和initial： f[0] = 0; f[1] = 1end : return f[n]

Given a m x n grid filled with non-negative numbers, find a path fromtop left to bottom right which minimizes the sum of all numbers alongits path. Note: You can only move either down or right at any point in time.

A robot is located at the top-left corner of a m x n grid (marked'Start' in the diagram below). The robot can only move either down or right at any point in time. Therobot is trying to reach the bottom-right corner of the grid (marked'Finish' in the diagram below). How many possible unique paths ...

Find the contiguous subarray within an array (containing at least onenumber) which has the largest product. For example, given the array [2,3,-2,4], the contiguous subarray [2,3]has the largest product = 6.

Find the contiguous subarray within an array (containing at least onenumber) which has the largest sum. For example, given the array [−2,1,−3,4,−1,2,1,−5,4], the contiguoussubarray [4,−1,2,1] has the largest sum = 6.

Sqrt(x) Implement int sqrt(int x). Compute and return the square root of x. 二分法 思路 一个数x的平方根m满足mm <= x < (m+1)(m+1)用二分法查找m的值 复杂度 时间O(logn) 空间O(1) 代码 {代码...} Pow(x, n) 递归法 复杂度 时间O(logn) 空间栈O(logn) 代码 {代码...}

A peak element is an element that is greater than its neighbors. Given an input array where num[i] ≠ num[i+1], find a peak element andreturn its index. The array may contain multiple peaks, in that case return the index toany one of the peaks is fine. You may imagine that num[-1] = num[n] = -∞. F...

Suppose a sorted array is rotated at some pivot unknown to youbeforehand. (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2). Find the minimum element.

Search a 2D Matrix {代码...} 二分法 思路 把matrix看成一个m*n的数组, 那么如果把数组一字排开就是正常的有序数组二分搜索了. 复杂度 时间 O(logMN) 空间 O(1) 代码 {代码...} Search a 2D Matrix II {代码...} 遍历法 说明 从左下角开始遍历, 如果大于当前就往右走, 小于就往上走 复杂度 时间 O(M + N) 空间O(1) 代码...

Suppose a sorted array is rotated at some pivot unknown to youbeforehand. (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2). You are given a target value to search. If found in the array returnits index, otherwise return -1. You may assume no duplicate exists in the array.

Given a sorted array of integers, find the starting and endingposition of a given target value. Your algorithm's runtime complexity must be in the order of O(log n). If the target is not found in the array, return [-1, -1]. For example, Given [5, 7, 7, 8, 8, 10] and target value 8, return [3,4].

Recover Binary Search Tree Two elements of a binary search tree (BST) are swapped by mistake. 递归法 思路 这道题是要求恢复一颗有两个元素调换错了的二叉查找树。中序遍历BST 然后找到逆序。有两种情况需要考虑: 两个错位的节点是相邻的父子树关系, 那么找到第一个先序遍历逆序的两个节点 两个错位的节点不是父子...

Given a binary tree, determine if it is a valid binary search tree(BST). Assume a BST is defined as follows: The left subtree of a node contains only nodes with keys less than thenode's key. The right subtree of a node contains only nodes with keysgreater than the node's key. Both the left and ri...

There are a total of n courses you have to take, labeled from 0 to n -1. Some courses may have prerequisites, for example to take course 0 youhave to first take course 1, which is expressed as a pair: [0,1] Given the total number of courses and a list of prerequisite pairs, isit possible for you ...

Given an directed graph, a topological order of the graph nodes isdefined as follow: For each directed edge A -> B in graph, A must before B in the orderlist. The first node in the order can be any node in the graph with nonodes direct to it. Find any topological order for the given graph.

{代码...} 递归法 思路 相当于一次先序遍历, 将先访问的点存储在数组里, 下一个访问的节点为之前访问的点的右子树 复杂度 时间O(n)。空间上是栈的大小，O(logn) 代码 {代码...} 非递归解法 思路 对于一个节点我们把右子树入栈, 左子树放在右边. 如果左子树没有了我们就把栈内最近的节点拿出来作为节点的右子树 复杂度 时...

{代码...} 广度优先搜索法 思路 用一个hashmap将原节点和复制的节点映射起来, 因为hashmap的存在 可以不用记录visited, 因为凡是便利过的都在map中 复杂度 一次便利时间O(n) 空间O(n) 代码 {代码...} 深度优先搜索 复杂度 时间O(n) 空间O(n) 代码 {代码...}

JavaBean JavaBean规范 JavaBean是一个公共的类 JavaBean有一个不带参数的构造函数 JavaBean通过setXXX方法设置属性，并且通过getXXX方法获取属性 属性私有 {代码...} jsp访问javaBean 和普通java类使用相同 1. 导入javaBean类 {代码...} 2. 声明javaBean对象 {代码...} 3. 访问对象 {代码...} useBean动作 {代码...} ja...

Populating Next Right Pointers in Each Node {代码...} 广度优先搜索 思路 相当于层序遍历BST, 只是除了每层的最后一个节点其他节点都要给一个next指针指向队列里的下一个节点. 此方法I &II都适用 复杂度 时间O(n) 空间O(n) 代码 public void connect(TreeLinkNode root) { {代码...} 递归解法 思路 node的left ch...

时间复杂度：最坏O（n^2） 当划分不均匀时候 逆序and排好序都是最坏情况最好O（n） 当划分均匀partition的时间复杂度: O（n）一共需要logn次partition

所以这道题可以用递归的方法解决。通过先序遍历找到第一个点作为根节点，在中序遍历中找到根节点并记录index。此处用hashmap来存储, key为中序遍历节点值 value为index因为中序遍历中根节点左边为左子树，所以可以记录左子树的长度并在先序遍历中依据这个长度找到左子树的区间，用同样方法可以找到右子树的区间。递归的...

数组的中点为根, 然后递归中点为界限的左边和右边的数组. 递归的写法跟常规稍有不同，就是要把根root先new出来，然后它的左节点接到递归左边部分的返回值，右节点接到递归右边部分的返回值，最后将root返回回去。这个模板在树的构造中非常有用.