本文共 12946 字，大约阅读时间需要 43 分钟。

目录

1.前序遍历非递归实现

public List
   
     preorderTraversal(TreeNode root) {        // write your code here                List
    
      res = new ArrayList<>();                if(root == null) return res;                 Stack
     
       stack = new Stack<>();         stack.push(root);                while(!stack.isEmpty()){                      TreeNode tr = stack.pop();                        res.add(tr.val);                        if(tr.right!=null) stack.push(tr.right);                     if(tr.left !=null) stack.push(tr.left);                    }                              return res;             }
     
    
   

2.中序遍历非递归实现

public ArrayList
   
     inorderTraversal(TreeNode root) {        Stack
    
      stack = new Stack
     
      ();        ArrayList
      
        result = new ArrayList
       
        ();        TreeNode curt = root;        while (curt != null || !stack.empty()) {            while (curt != null) {                stack.push(curt);                curt = curt.left;            }            curt = stack.pop();            result.add(curt.val);            curt = curt.right;        }        return result;    }
       
      
     
    
   

3.后序遍历非递归实现

public ArrayList
   
     postorderTraversal(TreeNode root) {              Stack
    
      stack = new Stack
     
      ();        ArrayList
      
        results = new ArrayList
       
        ();                  if(root==null) return results;        stack.push(root);        while (!stack.empty()) {            TreeNode curNode = stack.pop();            results.add(curNode.val);            if (curNode.left != null) {                stack.push(curNode.left);            }            if (curNode.right != null) {                stack.push(curNode.right);            }        }                // 2. Reverse the results        Collections.reverse(results);                return results;    }
       
      
     
    
   

4.恢复旋转排序数组

public void recoverRotatedSortedArray(List
   
     nums) {        // write your code here        if(nums.size()>1){            int min = Integer.MAX_VALUE;            int minindex = 0;            //1.找最小            for(int i=0;i
    
      nums, int start, int end) {                int temp;                for(int i=0;i<(end-start+1)/2;i++ ){            temp = nums.get(start+i);            nums.set(start+i,nums.get(end - i));            nums.set(end - i, temp);                    }            }
    
   

5.第k大的数

int target;    public int findKthLargest(int[] nums, int k) {        target=k;        return quick(nums,0,nums.length-1);    }public int quick(int[] nums, int left,int right){        int l=left;        int r=right;        int privot = nums[(left+right)/2];        while(l
   
    privot){                r--;            }            if(l>=r){                break;            }            int temp = nums[l];            nums[l]=nums[r];            nums[r]=temp;            if(nums[l]==privot){                r--;            }            if(nums[r]==privot){                l++;            }        }        if(l==r){            if(l==nums.length-target) return privot;            l++;            r--;        }        if(nums.length-target<=r&&left<=r){            if (r==nums.length-target) return nums[r];            return quick(nums,left,r);        }        if(nums.length-target>=l&&l<=right){            if (l==nums.length-target) return nums[l];            return quick(nums,l,right);        }        return 0;    }
   

6.前k大的数

public void heapSort(int[] nums) {        buildHeap1(nums);        int subLen = nums.length ;        for (int i = nums.length-1; i >0; i--) {            swap(nums, 0, i);            subLen--;            if(subLen==3)return;            adjust(nums,0,subLen);        }    }public void buildHeap1(int[] nums){        for (int i =  nums.length/2 ; i >= 0; i--) {            adjust(nums, i, nums.length);        }    } public void swap(int[] nums, int i, int j){            int temp = nums[i];            nums[i] = nums[j];            nums[j] = temp;        }private void adjust(int[] nums, int i, int subLen) {        int left=2*i+1;        int right=2*i+2;        int largest=i;        if (left < subLen && nums[left] < nums[largest]) {            largest = left;        }        if (right < subLen && nums[right] < nums[largest]) {            largest = right;        }        if (largest != i) {            swap(nums, i, largest);            adjust(nums, largest, subLen);        }    }

7.k数之和

class Solution {    public List
   
    
     > fourSum(int[] nums, int target) {        Arrays.sort(nums);        List
     
      
       > res = new ArrayList();        List
       
         list = new ArrayList();        helpFourSum(nums,0,list,res,target);        return res;    }    public boolean helpFourSum(int[] nums,int index,List
        
          list,List
         
          
           > res,int target){ if(list.size()==4){ if(target==0){ res.add(new ArrayList(list)); return true; }else if(target<0){ return true; }else{ return false; } } if(index
           
            0&&target
            
             nums[i-1]){ list.add(nums[i]); boolean flag=helpFourSum(nums,i+1,list,res,target-nums[i]); if(flag){ list.remove(list.size()-1); return false; } list.remove(list.size()-1); } } return false; }}
            
           
          
         
        
       
      
     
    
   

8.股票问题

public int maxProfit(int[] prices) {         int count = 1;        int[][][] dp = new int[prices.length][count+1][2];        if(prices.length==0) return 0;        for(int i=0;i
   
    0;j--){                if(i==0){                    dp[i][j][0] = 0;                                        dp[i][j][1] = -prices[i];                                      continue;                }                    dp[i][j][0]=Math.max(dp[i-1][j][0],dp[i-1][j][1]+prices[i]);                    dp[i][j][1]=Math.max(dp[i-1][j][1],dp[i-1][j-1][0]-prices[i]);                           }        }                     return dp[prices.length - 1][count][0];    }
   

9.一天冷冻期

public int maxProfit(int[] prices) {          int count = prices.length/2;        int[][][] dp = new int[prices.length][count+1][2];        if(prices.length==0) return 0;        for(int i=0;i
   
    0;j--){                if(i==0){                    dp[i][j][0] = 0;                           dp[i][j][1] = -prices[i];                                                 continue;                }                    dp[i][j][0]=Math.max(dp[i-1][j][0],dp[i-1][j][1]+prices[i]);                     if(i==1){                        dp[i][j][1]=Math.max(dp[i-1][j][1],-prices[i]);                       }else{                        dp[i][j][1]=Math.max(dp[i-1][j][1],dp[i-2][j-1][0]-prices[i]);                       }                                                                  }        }               return dp[prices.length - 1][count][0];    }
   

10.含手续费

public int maxProfit(int[] prices, int fee) {          int count = prices.length/2;        int[][][] dp = new int[prices.length][count+1][2];        if(prices.length==0) return 0;        for(int i=0;i
   
    0;j--){                if(i==0){                    dp[i][j][0] = 0;                           dp[i][j][1] = -prices[i]-fee;                                                 continue;                }                    dp[i][j][0]=Math.max(dp[i-1][j][0],dp[i-1][j][1]+prices[i]);                                         dp[i][j][1]=Math.max(dp[i-1][j][1],dp[i-1][j-1][0]-prices[i]-fee);                                   }        }               return dp[prices.length - 1][count][0];    }
   

11.二叉树的公共节点

public class Solution {    /*     * @param root: The root of the binary search tree.     * @param A: A TreeNode in a Binary.     * @param B: A TreeNode in a Binary.     * @return: Return the least common ancestor(LCA) of the two nodes.     */     public TreeNode lowestCommonAncestor(TreeNode root, TreeNode node1, TreeNode node2) {                 if(root == null || root==node1 || root==node2) return root;                 // if left have node1/node2,then return node1 or node2 ,or lca of the two       TreeNode left = lowestCommonAncestor(root.left,node1,node2);               // if left have node1/node2,then return node1 or node2 ,or lca of the two       TreeNode right = lowestCommonAncestor(root.right,node1,node2);              //if left and right all one return lca.        if (left != null && right != null) {            return root;        }                 //if left two or right two,null do not                if(left != null ){           return left;        }       if(right != null ){           return right;        }                     return null;                  }}

12.接雨水

public class Solution {    public int trap(int[] height) {        if (height == null) {            return 0;        }        Stack
   
     stack = new Stack<>();        int ans = 0;        for (int i = 0; i < height.length; i++) {            while(!stack.isEmpty() && height[stack.peek()] < height[i]) {                int curIdx = stack.pop();                // 如果栈顶元素一直相等，那么全都pop出去，只留第一个。                while (!stack.isEmpty() && height[stack.peek()] == height[curIdx]) {                    stack.pop();                }                if (!stack.isEmpty()) {                    int stackTop = stack.peek();                    // stackTop此时指向的是此次接住的雨水的左边界的位置。右边界是当前的柱体，即i。                    // Math.min(height[stackTop], height[i]) 是左右柱子高度的min，减去height[curIdx]就是雨水的高度。                    // i - stackTop - 1 是雨水的宽度。                    ans += (Math.min(height[stackTop], height[i]) - height[curIdx]) * (i - stackTop - 1);                }            }            stack.add(i);        }        return ans;    }}
   

13.柱状图的最大面积

class Solution {    public int largestRectangleArea(int[] heights) {        int[] arr = new int[heights.length+2];         System.arraycopy(heights,0,arr,1,heights.length);        Stack
   
     stack = new Stack();        stack.push(0);        int max=0;        for(int i=1;i
    
     arr[i]){               int h=arr[stack.pop()];               max=Math.max(max,h*(i-stack.peek()-1));                       }            stack.push(i);        }              return max;    }}
    
   

14.map的迭代器

Iterator
   
    
     > iterator = map.entrySet().iterator();
    
   

15.矩阵顺时针打印

class Solution {    public List
   
     spiralOrder(int[][] matrix) {        List
    
      res = new ArrayList<>();        if(matrix == null || matrix.length == 0) return res;        int rowBegin = 0;        int rowEnd = matrix.length - 1;        int colBegin = 0;        int colEnd = matrix[0].length - 1;        while(rowBegin <= rowEnd && colBegin <= colEnd) {            // Traverse Right            for(int i = colBegin; i <= colEnd; ++i) {                res.add(matrix[rowBegin][i]);            }            rowBegin++;            // Traverse Down            for(int i = rowBegin; i <= rowEnd; ++i) {                res.add(matrix[i][colEnd]);            }            colEnd--;            // Traverse Left            if(rowBegin <= rowEnd) {                for(int i = colEnd; i >= colBegin; i--) {                    res.add(matrix[rowEnd][i]);                }                rowEnd--;            }            // Traver Up            if(colBegin <= colEnd) {                for(int i = rowEnd; i >= rowBegin; i--) {                    res.add(matrix[i][colBegin]);                }                colBegin++;            }        }        return res;    }}
    
   

16.最长公共子序列

17.最长公共子串

18.括号的有效长度

public class Solution {    public int longestValidParentheses(String s) {        int left = 0, right = 0, maxlength = 0;        for (int i = 0; i < s.length(); i++) {            if (s.charAt(i) == '(') {                left++;            } else {                right++;            }            if (left == right) {                maxlength = Math.max(maxlength, 2 * right);            } else if (right > left) {                left = right = 0;            }        }        left = right = 0;        for (int i = s.length() - 1; i >= 0; i--) {            if (s.charAt(i) == '(') {                left++;            } else {                right++;            }            if (left == right) {                maxlength = Math.max(maxlength, 2 * left);            } else if (left > right) {                left = right = 0;            }        }        return maxlength;    }}

 19.搜索旋转矩阵的目标值

class Solution {    public boolean search(int[] nums, int target) {        int left = 0;        int right = nums.length - 1;        while (left <= right) {            int mid = left + (right - left) / 2;            if (nums[mid] == target) return true;            if (nums[left] == nums[mid] && nums[mid] == nums[right]) {                left++;                right--;            } else if (nums[left] <= nums[mid]) {                if (nums[left] <= target && target < nums[mid]) right = mid - 1;                else left = mid + 1;            } else {                if (nums[mid] < target && target <= nums[right]) left = mid + 1;                else right = mid - 1;            }        }        return false;      }}

转载地址：http://yxnws.baihongyu.com/