1、无重复字符的最长子串

使用HashMap记录字符上次出现的位置，用pre记录最近重复字符出现的位置，则i(当前位置)-pre就是当前字符最长无重复字符的长度，取最大的就是字符串的最长无重复字符的长度

    public int lengthOfLongestSubstring(String str) {
        if (str == null || str.length() < 1)
            return 0;

        // 记录字符上次出现的位置
        HashMap<Character, Integer> map = new HashMap<>();
        int max = 0;
        // 最近出现重复字符的位置
        int pre = -1;

        for (int i = 0, strLen = str.length(); i < strLen; i++) {
            Character ch = str.charAt(i);
            Integer index = map.get(ch);
            if (index != null)
                pre = Math.max(pre, index);
            max = Math.max(max, i - pre);
            map.put(ch, i);
        }

        return max;
    }

2、简化路径

以 Unix 风格给出一个文件的绝对路径，你需要简化它。或者换句话说，将其转换为规范路径。

class Solution {
    public String simplifyPath(String path) {
        String[] pathArr = path.split("/");
        LinkedList<String> stack = new LinkedList<>();
        for(String s: pathArr){
            if("..".equals(s)){
                if(!stack.isEmpty()) stack.removeLast();
            }
            else if(".".equals(s)||"".equals(s)){}
            else stack.addLast(s);
        }
        if(stack.isEmpty()) return "/";
        StringBuilder sb = new StringBuilder();
        for(String s: stack){
            sb.append('/');
            sb.append(s);
        }
        return sb.toString();
    }
}

3、复原IP地址

给一个由数字组成的字符串。求出其可能恢复为的所有IP地址。

Input: "25525511135"
Output: ["255.255.11.135", "255.255.111.35"]

基本模板：

int check(参数)
{
    if(满足条件)
        return 1;
    return 0;
}

void dfs(int step)
{
        判断边界
        {
            相应操作
        }
        尝试每一种可能
        {
               满足check条件
               标记
               继续下一步dfs(step+1)
               恢复初始状态（回溯的时候要用到）
        }
} 

    /**
     * 回溯法
     * 要判断0<=value<=255且不能出现021这种情况
     * @param s
     */
    public static List<String> restoreIpAddresses(String s) {
        // write your code here
        List<String> result = new ArrayList<>();
        if(s.length()<4||s.length()>12)
            return result;

        dfs(s,new ArrayList<>(),result,0);
        return result;
    }

    private static void dfs(String s,  List<String> list, List<String> result, int index) {
        //list中已存在4段数字字符串了，进入最终处理环节
        if(list.size()==4){
            if(index!=s.length()){
                return;
            }
            StringBuilder ipAddress = new StringBuilder();
            for(String tmp:list){
                ipAddress.append(tmp);
                ipAddress.append(".");
            }
            ipAddress = ipAddress.deleteCharAt(ipAddress.length()-1);
            result.add(ipAddress.toString());
        }
        //以index为起点向后取数字，不超过s的长度而且最多取3个
        for(int i = index;i<s.length()&&i<index+3;i++){
            String tmp = s.substring(index,i+1);
            if(isVaildNumber(tmp)){
                list.add(tmp);
                dfs(s,list,res,i+1);
                list.remove(list.size()-1);
            }
        }

    }
    private static boolean isVaildNumber(String s){
        if (s.charAt(0) == '0')
            return s.equals("0");       // to eliminate cases like "00", "10"
        int digit = Integer.valueOf(s);
        return digit >= 0 && digit <= 255;
    }

4、三数之和

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。

Example:

Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]

我们只需要遍历前面的负数和0，也就是>0的我们统统不要了。我们需要拿到第一个负数。拿到第一个负数后，我们只需要再拿到后面两个数，与之相加=0即可。后面两个数我们用两个指针来表示，j和k，一个是从左边往右边走，一个是从最右边往前走。

func threeSum(_ nums: [Int]) -> [[Int]] {
    var MutNums: [Int] = nums
    var newNums: [Int] = []
    var haha:[[Int]] = []
    // 1.排序 对于MutNums[i]来说，我们只需要负数和0，因为三个数之和为0，一定是有一个数为负数的，当然除去三个数都为0的情况。所以，我们取非正数。
    MutNums.sort()
    for i in 0..<MutNums.count {
        if (MutNums[i] > 0) {
            break;
        }
        // 如果两个数字相同，我们直接跳到下一个循环。
        if (i > 0 && MutNums[i] == MutNums[i-1]) {
            continue
        }
        let target = 0 - MutNums[i];
        var j = i+1, k = MutNums.count - 1
        while j < k {
            // 2.找到后面的两个与MutNums[i]对应的数字
            if (MutNums[j] + MutNums[k] == target) {
                newNums.append(MutNums[i])
                newNums.append(MutNums[j])
                newNums.append(MutNums[k])
                haha.append(newNums)
                newNums.removeAll()
                // 如果两个数字相同，我们直接跳到下一个循环。
                while j < k && MutNums[j] == MutNums[j+1] {
                    j = j + 1
                }
                // 如果两个数字相同，我们直接跳到下一个循环。
                while j < k && MutNums[k] == MutNums[k-1] {
                    k = k - 1
                }
                // 否则就往中间靠拢
                j = j + 1;k = k - 1
            }else if (MutNums[j] + MutNums[k] < target) {
                // 如果后面两数相加小于target，说明左边还得往右移
                j = j + 1
            }else {
                // 如果后面两数相加大于target，说明右边就要往左移
                k = k - 1
            }
        }
    }
    return haha
}

5、岛屿的最大面积

给定一个包含了一些 0 和 1的非空二维数组 grid , 一个 岛屿 是由四个方向 (水平或垂直) 的 1 (代表土地) 构成的组合。你可以假设二维矩阵的四个边缘都被水包围着。

找到给定的二维数组中最大的岛屿面积。

public int maxAreaOfIsland(int[][] grid) {
    if(grid.length == 0 || grid[0].length == 0){
        return 0;    
    }
    int m = grid.length, n = grid[0].length;
    int max = 0;
    int[] count = new int[1];
    for(int i = 0; i < m; i++){
        for(int j = 0; j < n; j++){
            if(grid[i][j] == 1){
                count[0] = 0;
                dfs(grid, i, j, m, n, count);       
                max = Math.max(count[0], max);
            }
        }
    }
    return max;
}

private void dfs(int[][] grid, int i, int j, int m, int n, int[] count){
    if(i < 0 || j < 0 || i>= m || j >= n || grid[i][j] != 1){
        return;    
    }
    //marked visited;
    grid[i][j] = -1;
    count[0]++;
    dfs(grid, i + 1, j, m, n, count);
    dfs(grid, i - 1, j, m, n, count);
    dfs(grid, i, j + 1, m, n, count);
    dfs(grid, i, j - 1, m, n, count);
}

6、搜索旋转排序数组

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。

你可以假设数组中不存在重复的元素。

这题说的旋转，实际上就是左右整体互换，也就导致出现了两个递增序列。

public int search(int[] A, int target) {
    int lo = 0;
    int hi = A.length - 1;
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        if (A[mid] == target) return mid;
        
        if (A[lo] <= A[mid]) {
            if (target >= A[lo] && target < A[mid]) {
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        } else {
            if (target > A[mid] && target <= A[hi]) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
    }
    return A[lo] == target ? lo : -1;
}

7、朋友圈

班上有 N 名学生。其中有些人是朋友，有些则不是。他们的友谊具有是传递性。如果已知 A 是 B 的朋友，B 是 C 的朋友，那么我们可以认为 A 也是 C 的朋友。所谓的朋友圈，是指所有朋友的集合。
给定一个 N * N 的矩阵 M，表示班级中学生之间的朋友关系。如果M[i][j] = 1，表示已知第 i 个和 j 个学生互为朋友关系，否则为不知道。你必须输出所有学生中的已知的朋友圈总数。

Example:

示例1：
输入:
[[1,1,0],
[1,1,0],
[0,0,1]]
输出: 2
说明：已知学生0和学生1互为朋友，他们在一个朋友圈。
第2个学生自己在一个朋友圈。所以返回2。
示例2：
输入:
[[1,1,0],
[1,1,1],
[0,1,1]]
输出: 1
说明：已知学生0和学生1互为朋友，学生1和学生2互为朋友，所以学生0和学生2也是朋友，所以他们三个在一个朋友圈，返回1。

class UnionFind{
    int[] f;
    public UnionFind(int size){
        f = new int[size];
        for(int i = 0; i < size; i++){
            f[i] = i;
        }
    }
    public int find(int x){
        if (f[x] != x){
            f[x] = find(f[x]);
        }
        return f[x];
    }
    public void unite(int x, int y){
        int fx = find(x);
        int fy = find(y);
        f[f[y]] = fx;
    }    
}
class Solution {
    public int findCircleNum(int[][] M) {
        if (M.length == 0 || M[0].length == 0) return 0;
        int row = M.length, column = M[0].length;
        UnionFind uf = new UnionFind(row);
        Set<Integer> set = new HashSet<Integer>();
        for (int i = 0; i < row; i++){
            for(int j = i + 1; j < column; j ++){
                if (M[i][j] == 1){
                    uf.unite(i,j);
                }
            }
        }
        for(int i=0; i<row; i++){
            uf.f[i] = uf.find(i);
            set.add(uf.f[i]);
        }
        return set.size();
        
    }
}

8、接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

1. 遍历整个数组，找最高点
2. 从左向右遍历至最高点坐标，求积水
3. 从右向左遍历至最高点坐标，求积水

时间复杂度为O(n)，以及常数空间复杂度。

 public int trap(int[] height) {
        if(height.length<=2){
            return 0;
        }
        int maxIndex=0, maxValue = 0;
        int res = 0;
        for(int i=0;i<height.length;i++){
            if(height[i]>=maxValue){
                maxValue = height[i];
                maxIndex = i;
            }
        }

        int curRoot = height[0];
        for(int i =0;i<maxIndex;i++){
            if(curRoot<height[i]){
                curRoot = height[i];
            }else{
                res += curRoot-height[i];
            }
        }
        curRoot = height[height.length-1];
        for(int i=height.length-1;i>maxIndex;i--){
            if(curRoot<height[i]){
                curRoot = height[i];
            }else{
                res += curRoot-height[i];
            }
        }

        return res;
    }

9、反转链表

public ListNode reverseList(ListNode head) {
    /* iterative solution */
    ListNode newHead = null;
    while (head != null) {
        ListNode next = head.next;
        head.next = newHead;
        newHead = head;
        head = next;
    }
    return newHead;
}

10、两数相加

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    int carry = 0;
    ListNode p, dummy = new ListNode(0);
    p = dummy;
    while (l1 != null || l2 != null || carry != 0) {
        if (l1 != null) {
            carry += l1.val;
            l1 = l1.next;
        }
        if (l2 != null) {
            carry += l2.val;
            l2 = l2.next;
        }
        p.next = new ListNode(carry%10);
        carry /= 10;
        p = p.next;
    }
    return dummy.next;
}

11、合并两个有序链表

public ListNode mergeTwoLists(ListNode l1, ListNode l2){
        if(l1 == null) return l2;
        if(l2 == null) return l1;
        if(l1.val < l2.val){
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else{
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
}

12、合并K个排序链表

1.k个有序的链表，根据我们之前做的那道题，应该采用两两合并，也就是累加法，最后合并到一起去
2.两个链表的长度可能不一样，我们需要考虑补全的问题。

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode res = new ListNode(0);  //设置结果
        if(lists == null || lists.length < 0){
            return null;
        }else if(lists.length == 1){
            return lists[0];
        }else if(lists.length == 2){
            mergeTwoLists(lists[0],lists[1]);
        }else{
            res = mergeTwoLists(lists[0],lists[1]);
            for(int i = 2; i < lists.length;i++){
                mergeTwoLists(res,lists[i]);
            }
        }
        return res;
    }
     
    public ListNode mergeTwoLists(ListNode l1,ListNode l2){
        ListNode res = new ListNode(0);
        ListNode tmp = res;
         
        while(l1 != null && l2 != null){
            if(l1.val < l2.val){
                tmp.next = l1;
                l1 = l1.next;
            }else{
                tmp.next = l2;
                l2 = l2.next;
            }
            tmp = tmp.next;
        }
        //后面是为了补全的，因为链表的长度可能不一样
        if(l1 != null){
            tmp.next = l1;
        }else{
            tmp.next = l2;
        }
        return res.next;
    }
}

用优先队列

public class Solution {
    public ListNode mergeKLists(List<ListNode> lists) {
        if (lists==null||lists.size()==0) return null;
        
        PriorityQueue<ListNode> queue= new PriorityQueue<ListNode>(lists.size(),new Comparator<ListNode>(){
            @Override
            public int compare(ListNode o1,ListNode o2){
                if (o1.val<o2.val)
                    return -1;
                else if (o1.val==o2.val)
                    return 0;
                else 
                    return 1;
            }
        });
        
        ListNode dummy = new ListNode(0);
        ListNode tail=dummy;
        
        for (ListNode node:lists)
            if (node!=null)
                queue.add(node);
            
        while (!queue.isEmpty()){
            tail.next=queue.poll();
            tail=tail.next;
            
            if (tail.next!=null)
                queue.add(tail.next);
        }
        return dummy.next;
    }
}

13、买卖股票的最佳时机

买卖股票的最佳时机

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。

示例 1:

输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。** **

示例 2:

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

public int maxProfit(int[] prices) {
            int ans=0;
            if(prices.length==0)
            {
                return ans;
            }
            int bought=prices[0];                                
            for(int i=1;i<prices.length;i++)
            {
                if(prices[i]>bought)
                {
                    if(ans<(prices[i]-bought))
                    {
                        ans=prices[i]-bought;
                    }
                }
                else
                {
                    bought=prices[i];
                }
            }
     return ans;
}

14、买卖股票的最佳时机 II

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。设计一个算法来计算所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票），必须在再次购买前出售掉之前的股票。

从最小值开始买入，只要到最大值可以直接卖出，接下来最低点买入，同样下次最大再卖出，这是一种典型的贪心思想，局部最优达到全局最优。

public int maxProfit(int[] prices) {
    int profit = 0, i = 0;
    while (i < prices.length) {
        // find next local minimum
        while (i < prices.length-1 && prices[i+1] <= prices[i]) i++;
        int min = prices[i++]; // need increment to avoid infinite loop for "[1]"
        // find next local maximum
        while (i < prices.length-1 && prices[i+1] >= prices[i]) i++;
        profit += i < prices.length ? prices[i++] - min : 0;
    }
    return profit;
}

15、最大子序和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

第一种用了DP

令状态 dp[i] 表示以 A[i] 作为末尾的连续序列的最大和（这里是说 A[i] 必须作为连续序列的末尾）

public int maxSubArray(int[] nums) {
       int n = nums.length;
        int[] dp = new int[n];
        dp[0] = nums[0];
        int max = dp[0];

        for (int i = 1; i < n; i++) {
            dp[i] = Math.max(nums[i] + dp[i - 1], nums[i]);
            max = Math.max(max, dp[i]);

        }
        return max;
}

第二种分治

 public int Subarray(int[] A,int left, int right){
        if(left == right){return A[left];}
        int mid = left + (right - left) / 2;
        int leftSum = Subarray(A,left,mid);// left part 
        int rightSum = Subarray(A,mid+1,right);//right part
        int crossSum = crossSubarray(A,left,right);// cross part
        if(leftSum >= rightSum && leftSum >= crossSum){// left part is max
            return leftSum;
        }
        if(rightSum >= leftSum && rightSum >= crossSum){// right part is max
            return rightSum;
        }
        return crossSum; // cross part is max
    }
    public int crossSubarray(int[] A,int left,int right){
        int leftSum = Integer.MIN_VALUE;
        int rightSum = Integer.MIN_VALUE;
        int sum = 0;
        int mid = left + (right - left) / 2;
        for(int i = mid; i >= left ; i--){
            sum = sum + A[i];
            if(leftSum < sum){
                leftSum = sum;
            }
        }
        sum = 0;
        for(int j = mid + 1; j <= right; j++){
            sum = sum + A[j];
            if(rightSum < sum){
                rightSum = sum;
            }
        }
        return leftSum + rightSum;
    }

16、最小栈

设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。

class MinStack {
    int min = Integer.MAX_VALUE;
    Stack<Integer> stack = new Stack<Integer>();
    public void push(int x) {
        // only push the old minimum value when the current 
        // minimum value changes after pushing the new value x
        if(x <= min){          
            stack.push(min);
            min=x;
        }
        stack.push(x);
    }

    public void pop() {
        // if pop operation could result in the changing of the current minimum value, 
        // pop twice and change the current minimum value to the last minimum value.
        if(stack.pop() == min) min=stack.pop();
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return min;
    }
}

17、LRU缓存机制

18、寻找两个有序数组的中位数

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int index1 = 0;
    int index2 = 0;
    int med1 = 0;
    int med2 = 0;
    for (int i=0; i<=(nums1.length+nums2.length)/2; i++) {
        med1 = med2;
        if (index1 == nums1.length) {
            med2 = nums2[index2];
            index2++;
        } else if (index2 == nums2.length) {
            med2 = nums1[index1];
            index1++;
        } else if (nums1[index1] < nums2[index2] ) {
            med2 = nums1[index1];
            index1++;
        }  else {
            med2 = nums2[index2];
            index2++;
        }
    }

    // the median is the average of two numbers
    if ((nums1.length+nums2.length)%2 == 0) {
        return (float)(med1+med2)/2;
    }

    return med2;
}

19、最长回文子串

Example 1:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

Input: "cbbd"
Output: "bb"

动态规划解决需要大问题转换成小问题，因此可以将求n…m是否为回文字符串，缩小成当n=m时n+1…m-1是否为回文串。

所以可以设置状态db[n][m] 值为1表示为回文，0为否。
转换公式：
db[n][m]=db[n+1][m-1],s[n]=s[m] else 0 ,s[n]!=s[m]

class Solution {
    public String longestPalindrome(String s) {
         if("".equals(s)){
            return "";
        }
        int len = s.length();
        if(len==1){
            return s;
        }
        int sLength=1;
        int start = 0;
        int[][] db = new int[len][len];
        for(int i=0;i<len;i++){//定义初始化状态
            db[i][i]=1;
            if(i<len-1&&s.charAt(i)==s.charAt(i+1)){
                db[i][i+1] = 1;
                sLength=2;
                start = i;
            }
        }
        for(int i=3;i<=len;i++){
            for(int j=0;j+i-1<len;j++){
                int end = j+i-1;
                if(s.charAt(j)==s.charAt(end)){
                    db[j][end]=db[j+1][end-1];
                   if(db[j][end]==1){
                       start=j;
                       sLength = i;
                   }
                }
            }
        }
       return s.substring(start,start+sLength);
    }
}

20、合并两个有序数组

public class SortTwoArray {
    public int[] sort(int[] a,int[] b){
        int[] c = new int[a.length+b.length];
        int i=0,j=0,k = 0;
        while (i<a.length&&j<b.length){
            if(a[i]>=b[j]){
                c[k++] = b[j++];
            }else {
                c[k++] = a[i++];
            }
        }
     
        while (j<b.length){
            c[k++] = b[j++];
        }
        while (i<a.length){
            c[k++] = a[i++];
        }
        return c;
    }

}

21、整数反转

给定一个 32 位有符号整数，将整数中的数字进行反转。

示例 1:

输入: 123
输出: 321

示例 2:

输入: -123
输出: -321

示例 3:

输入: 120
输出: 21

public int rever(int x){
        long r = 0;
        while(x != 0){
            r = r*10 + x%10; 
            x /= 10;
        }
        if(r >= Integer.MIN_VALUE && r <= Integer.MAX_VALUE)
            return (int)r;
        else
            return 0;
    }

22、排序链表

public class Solution {
  
  public ListNode sortList(ListNode head) {
    if (head == null || head.next == null)
      return head;
        
    // step 1. cut the list to two halves
    ListNode prev = null, slow = head, fast = head;
    
    while (fast != null && fast.next != null) {
      prev = slow;
      slow = slow.next;
      fast = fast.next.next;
    }
    
    prev.next = null;
    
    // step 2. sort each half
    ListNode l1 = sortList(head);
    ListNode l2 = sortList(slow);
    
    // step 3. merge l1 and l2
    return merge(l1, l2);
  }
  
  ListNode merge(ListNode l1, ListNode l2) {
    ListNode l = new ListNode(0), p = l;
    
    while (l1 != null && l2 != null) {
      if (l1.val < l2.val) {
        p.next = l1;
        l1 = l1.next;
      } else {
        p.next = l2;
        l2 = l2.next;
      }
      p = p.next;
    }
    
    if (l1 != null)
      p.next = l1;
    
    if (l2 != null)
      p.next = l2;
    
    return l.next;
  }

}

23、子集

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

回溯

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> list = new ArrayList();
        Arrays.sort(nums);
        backtrack(list,new ArrayList<>(),nums,0);
        return list;
    }
    private void backtrack(List<List<Integer>>list,List<Integer>tempList,int []nums,int start){
        list.add(new ArrayList<>(tempList));
        for(int i = start;i<nums.length;i++){
            tempList.add(nums[i]);
            backtrack(list,tempList,nums,i+1);
            tempList.remove(tempList.size()-1);
        }
    }
}

24、全排列

本题是回溯法的一个经典应用场景，思路很清晰，逻辑很简单，下面写几个注意点。

（1）在类的内部新建一个List<List<Integer>>型的变量listList，可以避免在递归过程中一直传递该变量。

（2）递归到底，往listList中新增元素时，注意需要new一个ArrayList，因为递归过程中传递的list由于回溯过程中变量的手动回溯过程，其指向的值是一直在变化的。我们需要记录的是递归到底时list中存放的是什么值。

public class Solution {
 
    List<List<Integer>> listList;
    
    public List<List<Integer>> permute(int[] nums) {
        listList = new ArrayList<>();
        permute(nums, new ArrayList<>());
        return listList;
    }
    
    //we put the possible array in list, we are going to find next number
    private void permute(int[] nums, List<Integer> list) {
        int n = nums.length;
        if(list.size() == n) {
            listList.add(new ArrayList<>(list));
            return;
        }
        for (int i = 0; i < n; i++) {
            if(list.contains(nums[i])) {
                continue;
            }
            list.add(nums[i]);
            permute(nums, list);
            list.remove(list.size() - 1);
        }
    }
}

25、实现二叉树中序遍历（不使用递归）

26、爬楼梯（斐波那契数列）

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

嗯嗯，上楼梯问题，兔子繁衍问题，都是斐波拉契数列，没啥好说的。

记住公式就行。
F(n) = F(n-1) + F(n-2)
其中
F(0) = 1，F(1) = 1

public class Solution {

public int climbStairs(int n) {
    if(n == 0 || n == 1 || n == 2){return n;}
    int[] mem = new int[n];
    mem[0] = 1;
    mem[1] = 2;
    for(int i = 2; i < n; i++){
        mem[i] = mem[i-1] + mem[i-2];
    }
    return mem[n-1];
}

27、滑动窗口的最大值

给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。

/**
用一个双端队列，队列第一个位置保存当前窗口的最大值，当窗口滑动一次
1.判断当前最大值是否过期
2.新增加的值从队尾开始比较，把所有比他小的值丢掉
*/
public class Solution {
   public ArrayList<Integer> maxInWindows(int [] num, int size)
    {
        ArrayList<Integer> res = new ArrayList<>();
        if(size == 0) return res;
        int begin; 
        ArrayDeque<Integer> q = new ArrayDeque<>();
        for(int i = 0; i < num.length; i++){
            begin = i - size + 1;
            if(q.isEmpty())
                q.add(i);
            else if(begin > q.peekFirst())
                q.pollFirst();
         
            while((!q.isEmpty()) && num[q.peekLast()] <= num[i])
                q.pollLast();
            q.add(i);  
            if(begin >= 0)
                res.add(num[q.peekFirst()]);
        }
        return res;
    }
}

28、判断单链表成环与否？

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while(slow!=null&&fast!=null&&fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
            if(slow==fast) {return true;}
        }
        return false;
    }

29、如何从一百万个数里面找到最小的一百个数，考虑算法的时间复杂度和空间复杂度

经常会遇到复杂问题不能简单地分解成几个子问题，而会分解出一系列的子问题。简单地采用把大问题分解成子问题，并综合子问题的解导出大问题的解的方法，问题求解耗时会按问题规模呈幂级数增加。

为了节约重复求相同子问题的时间，引入一个数组，不管它们是否对最终解有用，把所有子问题的解存于该数组中，这就是动态规划法所采用的基本方法。

两个字符串的最长公共子序列

动态规划，即为自顶向下分析，自底向上设计，此题按照如下设计方式：
（设序列分别为X={x1,x2,...,xm}，Y={y1,y2,...,yn}）
① 当Xm = Yn时，找出Xm-1和Yn-1的最长公共子序列，再加上Xm（即Yn）
② 当Xm ≠ Yn时，找出Xm-1和Yn的一个最长公共子序列，以及找出Xm和Yn-1的一个最长公共子序列，这两个公共子序列中较长者即为X和Y的最长公共子序列
我们可以用c[i][j]来记录Xi和Yj的最长公共子序列的长度，注意边界条件

最大值

    public static int findLCS(String A, int n, String B, int m) {
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                dp[i][j] = 0;
            }
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (A.charAt(i - 1) == B.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = dp[i - 1][j] > dp[i][j - 1] ? dp[i - 1][j] : dp[i][j - 1];
                }
            }
        }
        return dp[n][m];
    }   

最长子序列

最长公共字串

递归实现：

  public static String iQueryMaxCommString(String stringA, String stringB) {
        if(stringA==null || stringB==null){
            return null;
        }
        if(stringA.length()<1 || stringB.length()<1){
            return "";
        }
        if (stringA.contains(stringB)) {
            return stringB;
        }
        else if (stringB.length() == 1) {
            return "";
        }

        String leftSerach = iQueryMaxCommString(stringA, stringB.substring(0, stringB.length() - 1));
        String rightSerach = iQueryMaxCommString(stringA, stringB.substring(1, stringB.length()));
        return leftSerach.length() >= rightSerach.length() ? leftSerach : rightSerach;
    }

动态规划:

    private static int getCommonStrLength(String str1, String str2) {
        int len1 = str1.length();
        int len2 = str2.length();
        int[][] dp = new int[len1 + 1][len2 + 1];
        for (int i = 0; i <= len1; i++) {
            for (int j = 0; j <= len2; j++) {
                dp[i][j] = 0;
            }
        }
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = 0;
                }
            }
        }
        int max = 0;
        for (int i = 0; i <= len1; i++) {
            for (int j = 0; j <= len2; j++) {
                if (dp[i][j] > max) {
                    max = dp[i][j];
                }
            }
        }
        return max;
    }

分治算法

分治法的设计思想是：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

分治策略是：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。

分治法在每一层递归上都有三个步骤：

​ step1 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；

​ step2 解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题

​ step3 合并：将各个子问题的解合并为原问题的解。

它的一般的算法设计模式如下：

Divide-and-Conquer(P)

1. if |P|≤n0

2. then return(ADHOC(P))

3. 将P分解为较小的子问题 P1 ,P2 ,...,Pk

4. for i←1 to k

5. do yi ← Divide-and-Conquer(Pi) △ 递归解决Pi

6. T ← MERGE(y1,y2,...,yk) △ 合并子问题

7. return(T)

​ 其中|P|表示问题P的规模；n0为一阈值，表示当问题P的规模不超过n0时，问题已容易直接解出，不必再继续分解。ADHOC(P)是该分治法中的基本子算法，用于直接解小规模的问题P。因此，当P的规模不超过n0时直接用算法ADHOC(P)求解。算法MERGE(y1,y2,...,yk)是该分治法中的合并子算法，用于将P的子问题P1 ,P2 ,...,Pk的相应的解y1,y2,...,yk合并为P的解。

使用分治法求解的一些经典问题

（1）二分搜索

（2）大整数乘法

（3）Strassen矩阵乘法

（4）棋盘覆盖

（5）合并排序

（6）快速排序

（7）线性时间选择

（8）最接近点对问题

（9）循环赛日程表

（10）汉诺塔

动态规划算法

基本思想与分治法类似，也是将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。

由于动态规划解决的问题多数有重叠子问题这个特点，为减少重复计算，对每一个子问题只解一次，将其不同阶段的不同状态保存在一个二维数组中。

与分治法最大的差别是：适合于用动态规划法求解的问题，经分解后得到的子问题往往不是互相独立的（即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解）。

能采用动态规划求解的问题的一般要具有3个性质：

​ (1) 最优化原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。

​ (2) 无后效性：某状态以后的过程不会影响以前的状态，只与当前状态有关。

（3）有重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势）

使用动态规划求解问题，最重要的就是确定动态规划三要素：

​ （1）问题的阶段 （2）每个阶段的状态

​ （3）从前一个阶段转化到后一个阶段之间的递推关系。

贪心算法

所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。

​ 贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。必须注意的是，贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性，即某个状态以后的过程不会影响以前的状态，只与当前状态有关。

贪心算法的基本思路：

​ 1.建立数学模型来描述问题。

​ 2.把求解的问题分成若干个子问题。

​ 3.对每一子问题求解，得到子问题的局部最优解。

​ 4.把子问题的解局部最优解合成原来解问题的一个解。

贪心策略适用的前提是：局部最优策略能导致产生全局最优解。

回溯算法

回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。

回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。

按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。

用回溯法解题的一般步骤：

​ （1）针对所给问题，确定问题的解空间：

​ 首先应明确定义问题的解空间，问题的解空间应至少包含问题的一个（最优）解。

​ （2）确定结点的扩展搜索规则

​ （3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。