1、無重復(fù)字符的最長子串

使用HashMap記錄字符上次出現(xiàn)的位置隔嫡，用pre記錄最近重復(fù)字符出現(xiàn)的位置，則i(當(dāng)前位置)-pre就是當(dāng)前字符最長無重復(fù)字符的長度释树，取最大的就是字符串的最長無重復(fù)字符的長度

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

        // 記錄字符上次出現(xiàn)的位置
        HashMap<Character, Integer> map = new HashMap<>();
        int max = 0;
        // 最近出現(xiàn)重復(fù)字符的位置
        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 風(fēng)格給出一個文件的絕對路徑心墅，你需要簡化它枷遂∑崦叮或者換句話說湿蛔，將其轉(zhuǎn)換為規(guī)范路徑膀曾。

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、復(fù)原IP地址

給一個由數(shù)字組成的字符串阳啥。求出其可能恢復(fù)為的所有IP地址添谊。

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

基本模板：

int check(參數(shù))
{
    if(滿足條件)
        return 1;
    return 0;
}

void dfs(int step)
{
        判斷邊界
        {
            相應(yīng)操作
        }
        嘗試每一種可能
        {
               滿足check條件
               標(biāo)記
               繼續(xù)下一步dfs(step+1)
               恢復(fù)初始狀態(tài)（回溯的時候要用到）
        }
} 

    /**
     * 回溯法
     * 要判斷0<=value<=255且不能出現(xiàn)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段數(shù)字字符串了，進入最終處理環(huán)節(jié)
        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為起點向后取數(shù)字察迟，不超過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斩狱、三數(shù)之和

給定一個包含 n 個整數(shù)的數(shù)組 nums耳高，判斷 nums 中是否存在三個元素 a，b所踊，c 泌枪，使得 a + b + c = 0 ？找出所有滿足條件且不重復(fù)的三元組秕岛。
注意：答案中不可以包含重復(fù)的三元組碌燕。

Example:

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

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

我們只需要遍歷前面的負數(shù)和0，也就是>0的我們統(tǒng)統(tǒng)不要了瓣蛀。我們需要拿到第一個負數(shù)陆蟆。拿到第一個負數(shù)后，我們只需要再拿到后面兩個數(shù)惋增，與之相加=0即可叠殷。后面兩個數(shù)我們用兩個指針來表示，j和k诈皿，一個是從左邊往右邊走林束，一個是從最右邊往前走。

func threeSum(_ nums: [Int]) -> [[Int]] {
    var MutNums: [Int] = nums
    var newNums: [Int] = []
    var haha:[[Int]] = []
    // 1.排序 對于MutNums[i]來說稽亏，我們只需要負數(shù)和0壶冒，因為三個數(shù)之和為0，一定是有一個數(shù)為負數(shù)的截歉，當(dāng)然除去三個數(shù)都為0的情況胖腾。所以，我們?nèi)》钦龜?shù)瘪松。
    MutNums.sort()
    for i in 0..<MutNums.count {
        if (MutNums[i] > 0) {
            break;
        }
        // 如果兩個數(shù)字相同咸作，我們直接跳到下一個循環(huán)。
        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]對應(yīng)的數(shù)字
            if (MutNums[j] + MutNums[k] == target) {
                newNums.append(MutNums[i])
                newNums.append(MutNums[j])
                newNums.append(MutNums[k])
                haha.append(newNums)
                newNums.removeAll()
                // 如果兩個數(shù)字相同宵睦，我們直接跳到下一個循環(huán)记罚。
                while j < k && MutNums[j] == MutNums[j+1] {
                    j = j + 1
                }
                // 如果兩個數(shù)字相同，我們直接跳到下一個循環(huán)壳嚎。
                while j < k && MutNums[k] == MutNums[k-1] {
                    k = k - 1
                }
                // 否則就往中間靠攏
                j = j + 1;k = k - 1
            }else if (MutNums[j] + MutNums[k] < target) {
                // 如果后面兩數(shù)相加小于target桐智，說明左邊還得往右移
                j = j + 1
            }else {
                // 如果后面兩數(shù)相加大于target，說明右邊就要往左移
                k = k - 1
            }
        }
    }
    return haha
}

5烟馅、島嶼的最大面積

給定一個包含了一些 0 和 1的非空二維數(shù)組 grid , 一個 島嶼 是由四個方向 (水平或垂直) 的 1 (代表土地) 構(gòu)成的組合说庭。你可以假設(shè)二維矩陣的四個邊緣都被水包圍著。

找到給定的二維數(shù)組中最大的島嶼面積郑趁。

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口渔、搜索旋轉(zhuǎn)排序數(shù)組

假設(shè)按照升序排序的數(shù)組在預(yù)先未知的某個點上進行了旋轉(zhuǎn)。

( 例如穿撮，數(shù)組 [0,1,2,4,5,6,7] 可能變?yōu)?[4,5,6,7,0,1,2] )缺脉。

搜索一個給定的目標(biāo)值，如果數(shù)組中存在這個目標(biāo)值悦穿，則返回它的索引攻礼，否則返回 -1 。

你可以假設(shè)數(shù)組中不存在重復(fù)的元素栗柒。

這題說的旋轉(zhuǎn)礁扮，實際上就是左右整體互換，也就導(dǎo)致出現(xiàn)了兩個遞增序列瞬沦。

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 名學(xué)生。其中有些人是朋友逛钻，有些則不是僚焦。他們的友誼具有是傳遞性。如果已知 A 是 B 的朋友曙痘，B 是 C 的朋友芳悲，那么我們可以認為 A 也是 C 的朋友。所謂的朋友圈边坤，是指所有朋友的集合名扛。
給定一個 N * N 的矩陣 M，表示班級中學(xué)生之間的朋友關(guān)系茧痒。如果M[i][j] = 1肮韧，表示已知第 i 個和 j 個學(xué)生互為朋友關(guān)系，否則為不知道旺订。你必須輸出所有學(xué)生中的已知的朋友圈總數(shù)弄企。

Example:

示例1：
輸入:
[[1,1,0],
[1,1,0],
[0,0,1]]
輸出: 2
說明：已知學(xué)生0和學(xué)生1互為朋友，他們在一個朋友圈耸峭。
第2個學(xué)生自己在一個朋友圈桩蓉。所以返回2。
示例2：
輸入:
[[1,1,0],
[1,1,1],
[0,1,1]]
輸出: 1
說明：已知學(xué)生0和學(xué)生1互為朋友劳闹，學(xué)生1和學(xué)生2互為朋友院究，所以學(xué)生0和學(xué)生2也是朋友，所以他們?nèi)齻€在一個朋友圈本涕，返回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 個非負整數(shù)表示每個寬度為 1 的柱子的高度圖菩颖，計算按此排列的柱子样漆，下雨之后能接多少雨水。

1. 遍歷整個數(shù)組晦闰，找最高點
2. 從左向右遍歷至最高點坐標(biāo)放祟，求積水
3. 從右向左遍歷至最高點坐標(biāo)鳍怨，求積水

時間復(fù)雜度為O(n)，以及常數(shù)空間復(fù)雜度跪妥。

 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、反轉(zhuǎn)鏈表

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眉撵、兩數(shù)相加

給出兩個 非空 的鏈表用來表示兩個非負的整數(shù)侦香。其中，它們各自的位數(shù)是按照 逆序 的方式存儲的纽疟，并且它們的每個節(jié)點只能存儲 一位 數(shù)字罐韩。

如果，我們將這兩個數(shù)相加起來污朽，則會返回一個新的鏈表來表示它們的和散吵。

輸入：(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個有序的鏈表错蝴，根據(jù)我們之前做的那道題，應(yīng)該采用兩兩合并颓芭，也就是累加法顷锰，最后合并到一起去
2.兩個鏈表的長度可能不一樣，我們需要考慮補全的問題亡问。

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode res = new ListNode(0);  //設(shè)置結(jié)果
        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;
    }
}

用優(yōu)先隊列

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、買賣股票的最佳時機

買賣股票的最佳時機

給定一個數(shù)組州藕，它的第 i 個元素是一支給定股票第 i 天的價格束世。

如果你最多只允許完成一筆交易（即買入和賣出一支股票），設(shè)計一個算法來計算你所能獲取的最大利潤床玻。

示例 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

給定一個數(shù)組其屏，它的第 i 個元素是一支給定股票第 i 天的價格。設(shè)計一個算法來計算所能獲取的最大利潤缨该。你可以盡可能地完成更多的交易（多次買賣一支股票）偎行，必須在再次購買前出售掉之前的股票。

從最小值開始買入，只要到最大值可以直接賣出蛤袒，接下來最低點買入熄云，同樣下次最大再賣出，這是一種典型的貪心思想汗盘，局部最優(yōu)達到全局最優(yōu)皱碘。

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、最大子序和

給定一個整數(shù)數(shù)組 nums 隐孽，找到一個具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個元素），返回其最大和健蕊。

第一種用了DP

令狀態(tài) dp[i] 表示以 A[i] 作為末尾的連續(xù)序列的最大和（這里是說 A[i] 必須作為連續(xù)序列的末尾）

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菱阵、最小棧

設(shè)計一個支持 push，pop缩功，top 操作晴及，并能在常數(shù)時間內(nèi)檢索到最小元素的棧。

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虑稼、尋找兩個有序數(shù)組的中位數(shù)

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"

動態(tài)規(guī)劃解決需要大問題轉(zhuǎn)換成小問題蛛倦，因此可以將求n…m是否為回文字符串，縮小成當(dāng)n=m時n+1…m-1是否為回文串啦桌。

所以可以設(shè)置狀態(tài)db[n][m] 值為1表示為回文溯壶，0為否。
轉(zhuǎn)換公式：
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++){//定義初始化狀態(tà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甫男、合并兩個有序數(shù)組

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且改、整數(shù)反轉(zhuǎn)

給定一個 32 位有符號整數(shù)，將整數(shù)中的數(shù)字進行反轉(zhuǎn)板驳。

示例 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宪塔、子集

給定一組不含重復(fù)元素的整數(shù)數(shù)組 nums甘畅，返回該數(shù)組所有可能的子集（冪集）。

回溯

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席覆、全排列

本題是回溯法的一個經(jīng)典應(yīng)用場景直砂，思路很清晰菌仁，邏輯很簡單，下面寫幾個注意點静暂。

（1）在類的內(nèi)部新建一個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、實現(xiàn)二叉樹中序遍歷（不使用遞歸）

26鲫寄、爬樓梯（斐波那契數(shù)列）

假設(shè)你正在爬樓梯吉执。需要 n 階你才能到達樓頂。

每次你可以爬 1 或 2 個臺階地来。你有多少種不同的方法可以爬到樓頂呢戳玫？

注意：給定 n 是一個正整數(shù)。

嗯嗯未斑，上樓梯問題咕宿，兔子繁衍問題，都是斐波拉契數(shù)列蜡秽，沒啥好說的府阀。

記住公式就行。
F(n) = F(n-1) + F(n-2)
其中
F(0) = 1芽突，F(xiàn)(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试浙、滑動窗口的最大值

給定一個數(shù)組和滑動窗口的大小，找出所有滑動窗口里數(shù)值的最大值诉瓦。例如川队，如果輸入數(shù)組{2,3,4,2,6,2,5,1}及滑動窗口的大小3，那么一共存在6個滑動窗口睬澡，他們的最大值分別為{4,4,6,6,6,5}固额； 針對數(shù)組{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]}啄糙。

/**
用一個雙端隊列，隊列第一個位置保存當(dāng)前窗口的最大值云稚，當(dāng)窗口滑動一次
1.判斷當(dāng)前最大值是否過期
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、判斷單鏈表成環(huán)與否静陈？

/**
 * 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燕雁、如何從一百萬個數(shù)里面找到最小的一百個數(shù)诞丽，考慮算法的時間復(fù)雜度和空間復(fù)雜度

經(jīng)常會遇到復(fù)雜問題不能簡單地分解成幾個子問題，而會分解出一系列的子問題拐格。簡單地采用把大問題分解成子問題僧免，并綜合子問題的解導(dǎo)出大問題的解的方法，問題求解耗時會按問題規(guī)模呈冪級數(shù)增加捏浊。

為了節(jié)約重復(fù)求相同子問題的時間懂衩，引入一個數(shù)組，不管它們是否對最終解有用金踪，把所有子問題的解存于該數(shù)組中浊洞，這就是動態(tài)規(guī)劃法所采用的基本方法。

兩個字符串的最長公共子序列

動態(tài)規(guī)劃热康，即為自頂向下分析沛申，自底向上設(shè)計，此題按照如下設(shè)計方式：
（設(shè)序列分別為X={x1,x2,...,xm}姐军，Y={y1,y2,...,yn}）
① 當(dāng)Xm = Yn時，找出Xm-1和Yn-1的最長公共子序列尖淘，再加上Xm（即Yn）
② 當(dāng)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];
    }   

最長子序列

最長公共字串

遞歸實現(xiàn)：

  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;
    }

動態(tài)規(guī)劃:

    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;
    }

分治算法

分治法的設(shè)計思想是：將一個難以直接解決的大問題，分割成一些規(guī)模較小的相同問題趁桃，以便各個擊破辽话，分而治之。

分治策略是：對于一個規(guī)模為n的問題卫病，若該問題可以容易地解決（比如說規(guī)模n較杏推　）則直接解決，否則將其分解為k個規(guī)模較小的子問題蟀苛，這些子問題互相獨立且與原問題形式相同益咬，遞歸地解這些子問題，然后將各子問題的解合并得到原問題的解帜平。這種算法設(shè)計策略叫做分治法幽告。

分治法在每一層遞歸上都有三個步驟：

? step1 分解：將原問題分解為若干個規(guī)模較小，相互獨立裆甩，與原問題形式相同的子問題冗锁；

? step2 解決：若子問題規(guī)模較小而容易被解決則直接解，否則遞歸地解各個子問題

? step3 合并：將各個子問題的解合并為原問題的解嗤栓。

它的一般的算法設(shè)計模式如下：

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的規(guī)模冻河；n0為一閾值，表示當(dāng)問題P的規(guī)模不超過n0時，問題已容易直接解出芋绸，不必再繼續(xù)分解媒殉。ADHOC(P)是該分治法中的基本子算法，用于直接解小規(guī)模的問題P摔敛。因此廷蓉，當(dāng)P的規(guī)模不超過n0時直接用算法ADHOC(P)求解。算法MERGE(y1,y2,...,yk)是該分治法中的合并子算法马昙，用于將P的子問題P1 ,P2 ,...,Pk的相應(yīng)的解y1,y2,...,yk合并為P的解桃犬。

使用分治法求解的一些經(jīng)典問題

（1）二分搜索

（2）大整數(shù)乘法

（3）Strassen矩陣乘法

（4）棋盤覆蓋

（5）合并排序

（6）快速排序

（7）線性時間選擇

（8）最接近點對問題

（9）循環(huán)賽日程表

（10）漢諾塔

動態(tài)規(guī)劃算法

基本思想與分治法類似，也是將待求解的問題分解為若干個子問題（階段）行楞，按順序求解子階段攒暇，前一子問題的解，為后一子問題的求解提供了有用的信息子房。在求解任一子問題時形用，列出各種可能的局部解，通過決策保留那些有可能達到最優(yōu)的局部解证杭，丟棄其他局部解田度。依次解決各子問題，最后一個子問題就是初始問題的解解愤。

由于動態(tài)規(guī)劃解決的問題多數(shù)有重疊子問題這個特點镇饺，為減少重復(fù)計算，對每一個子問題只解一次送讲，將其不同階段的不同狀態(tài)保存在一個二維數(shù)組中奸笤。

與分治法最大的差別是：適合于用動態(tài)規(guī)劃法求解的問題，經(jīng)分解后得到的子問題往往不是互相獨立的（即下一個子階段的求解是建立在上一個子階段的解的基礎(chǔ)上哼鬓，進行進一步的求解）监右。

能采用動態(tài)規(guī)劃求解的問題的一般要具有3個性質(zhì)：

? (1) 最優(yōu)化原理：如果問題的最優(yōu)解所包含的子問題的解也是最優(yōu)的，就稱該問題具有最優(yōu)子結(jié)構(gòu)魄宏，即滿足最優(yōu)化原理秸侣。

? (2) 無后效性：某狀態(tài)以后的過程不會影響以前的狀態(tài)，只與當(dāng)前狀態(tài)有關(guān)宠互。

（3）有重疊子問題：即子問題之間是不獨立的味榛，一個子問題在下一階段決策中可能被多次使用到。（該性質(zhì)并不是動態(tài)規(guī)劃適用的必要條件予跌，但是如果沒有這條性質(zhì)搏色，動態(tài)規(guī)劃算法同其他算法相比就不具備優(yōu)勢）

使用動態(tài)規(guī)劃求解問題，最重要的就是確定動態(tài)規(guī)劃三要素：

? （1）問題的階段 （2）每個階段的狀態(tài)

? （3）從前一個階段轉(zhuǎn)化到后一個階段之間的遞推關(guān)系券册。

貪心算法

所謂貪心算法是指频轿，在對問題求解時垂涯，總是做出在當(dāng)前看來是最好的選擇。也就是說航邢，不從整體最優(yōu)上加以考慮耕赘，他所做出的僅是在某種意義上的局部最優(yōu)解。

? 貪心算法沒有固定的算法框架膳殷，算法設(shè)計的關(guān)鍵是貪心策略的選擇操骡。必須注意的是，貪心算法不是對所有問題都能得到整體最優(yōu)解赚窃，選擇的貪心策略必須具備無后效性册招，即某個狀態(tài)以后的過程不會影響以前的狀態(tài)，只與當(dāng)前狀態(tài)有關(guān)勒极。

貪心算法的基本思路：

? 1.建立數(shù)學(xué)模型來描述問題是掰。

? 2.把求解的問題分成若干個子問題。

? 3.對每一子問題求解辱匿，得到子問題的局部最優(yōu)解键痛。

? 4.把子問題的解局部最優(yōu)解合成原來解問題的一個解。

貪心策略適用的前提是：局部最優(yōu)策略能導(dǎo)致產(chǎn)生全局最優(yōu)解匾七。

回溯算法

回溯算法實際上一個類似枚舉的搜索嘗試過程散休，主要是在搜索嘗試過程中尋找問題的解，當(dāng)發(fā)現(xiàn)已不滿足求解條件時乐尊，就“回溯”返回，嘗試別的路徑划址。

回溯法是一種選優(yōu)搜索法扔嵌，按選優(yōu)條件向前搜索，以達到目標(biāo)夺颤。但當(dāng)探索到某一步時痢缎，發(fā)現(xiàn)原先選擇并不優(yōu)或達不到目標(biāo)，就退回一步重新選擇世澜，這種走不通就退回再走的技術(shù)為回溯法独旷，而滿足回溯條件的某個狀態(tài)的點稱為“回溯點”。

按照深度優(yōu)先搜索的策略寥裂，從根結(jié)點出發(fā)深度探索解空間樹嵌洼。當(dāng)探索到某一結(jié)點時，要先判斷該結(jié)點是否包含問題的解封恰，如果包含麻养，就從該結(jié)點出發(fā)繼續(xù)探索下去，如果該結(jié)點不包含問題的解诺舔，則逐層向其祖先結(jié)點回溯鳖昌。

用回溯法解題的一般步驟：

? （1）針對所給問題备畦，確定問題的解空間：

? 首先應(yīng)明確定義問題的解空間，問題的解空間應(yīng)至少包含問題的一個（最優(yōu)）解许昨。

? （2）確定結(jié)點的擴展搜索規(guī)則

? （3）以深度優(yōu)先方式搜索解空間懂盐，并在搜索過程中用剪枝函數(shù)避免無效搜索。