算法刷题java

柔情只为你懂 2022-09-04 06:42 212阅读 0赞

## 一、基础运算 ##

### 1.1 pow 计算x的n次幂 ###

private static int simpleN(int i, int n) {
        int res = 1;
        int absN = Math.abs (n);
        while(absN > 0){
            res *= i;
            absN--;
        }
        return n > 0 ? res : 1 / res;
    }
    public static double powFast(double x, int n){
            double res = 1;
            long N = Math.abs(n);
            double target = x;
            while(N > 0){
                if((N & 1) == 1){
                    res *= target;
                }
                target *= target;
                N = N >> 1;
            }
            return res;
        }

### 1.2 交换两个数字 ###

int[] datas = {1,10,5,4,6,8,2,7,3};
    swap(datas, 5 ,2);
    public static void swap(int[] datas, int i, int j){
        datas[i] = datas[i] ^ datas[j];
        datas[j] = datas[i] ^ datas[j];
        datas[i] = datas[i] ^ datas[j];
    }
    
    public static void swap(int[] datas, int i, int j){
        datas[i] = datas[i] + datas[j];
        datas[j] = datas[i] - datas[j];
        datas[i] = datas[i] - datas[j];
    }

### 1.3 斐波那契列 ###

/*  
     *  (1)斐波那契列 输入一个整数n，请输出斐波那契列的第n项
     *  f(n) = f(n-1)+f(n-2), n > 1 n = 1 f(n) = 1 f(0) = 0
     *  0 1 1 2 3 5 8 13 21 34 55 89
     */
     public static int getIndexRev(int n){
         if(n == 0){
         	return 0;
         } else if(n == 1 || n == 2){
         	return 1;
         } else {
         	return getIndexRev(n - 1) + getIndexRev(n - 2);
         }
     }

### 1.4 唯一摩尔斯密码词 ###

public static void main(String[] args) {
    	String[] words = {"ab", "cd", "de"};
        System.out.println(uniqueMorseRepeat(words));
    }
    
    public static int uniqueMorseRepeat(String[] words){
      String[] codes = {".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."};
      TreeSet<String> treeSet = new TreeSet<>();
      for (String word : words) {
      	StringBuilder sb = new StringBuilder();
        for(int i = 0; i < word.length(); i++){
        	sb.append(codes[word.charAt(i) - 'a']);
        }
        treeSet.add(sb.toString());
      }
      return treeSet.size();
    }

### 1.5 LRUCache ###

import java.util.HashMap;
    
    public class LRUCache {
        static class Node{
            Node next;
            Node prev;
            int key;
            int val;
    
            public Node(){}
            public Node(int key, int val){
                this.key = key;
                this.val = val;
            }
        }
    
        HashMap<Integer, Node> map;
        Node head;
        Node tail;
        int capacity;
        int count;
    
        public LRUCache(int capacity){
            this.capacity = capacity;
            map = new HashMap<>();
            head = new Node();
            tail = new Node();
            head.next = tail;
            tail.prev = head;
        }
    
        public int get(int key){
            if(map.containsKey(key)){
                Node node = map.get(key);
                remove(node);
                insert(node);
                return map.get(key).val;
            }
            return -1;
        }
    
        public void insert(Node node){
            Node next = head.next;
            head.next = node;
            node.next = next;
            node.prev = head;
            next.prev = node;
            map.put(node.key, node);
            count++;
            if(count > capacity){
                remove(tail.prev);
            }
        }
    
        public void remove(Node node){
            if(count > 0){
                Node prev = node.prev;
                Node next = node.next;
                prev.next = next;
                next.prev = prev;
                node.prev = null;
                node.next = null;
                map.remove(node.key);
            }
        }
        public void put(int key, int value){
            if(map.containsKey(key)){
                Node node = map.get(key);
                node.val = value;
                remove(node);
                insert(node);
            } else {
                Node node = new Node(key, value);
                insert(node);
            }
        }
    }

### 1.6 数字转二进制有多少个1 ###

int num = 12;
    int sum = 0;
    while(num > 0){
        if(num & 1 == 1){
            sum++;
        }
        num = num >> 1;
    }
    System.out.println(sum);

### 1.6 数组的中位数 ###

public double findMedian(){
    	int n = data.size();
    	//判断奇数偶数
    	if((n & 1) == 1){
    		return data.get(n / 2);
    	} else {
    		return (data.get(n/2 -1) + data.get(n / 2)) / 2.0;
    	}
    }

### 1.7 异或运算–获取数组中唯一单数字 ###

int[] nums = {1,2,2,1,3};
            int result = 0;
            for (int num : nums) {
                result ^= num;
            }
            System.out.println(nums);

### 1.8 分糖果 ###

//int[] ratings = new int[]{1,5,4,6,2,7,3}
    //0-1表示索引0的孩子评分1，1-5表示索引1的孩子评分5，两个孩子评分高的分更糖果，一共最少分多少个
    public static int candy(int[] ratings){
            if(ratings == null || ratings.length == 0){
                return 0;
            }
            int n = ratings.length;
            int[] d = new int[n];
            d[0] = 1;
            for(int i = 1; i < n; i++){
                if(ratings[i] > ratings[i - 1]){
                    d[i] = d[i - 1] + 1;
                } else {
                    d[i] = 1;
                }
            }
            int sum = d[n-1];
            for(int i = n -2; i >= 0; i--){
                if(ratings[i] > ratings[i + 1]){
                    d[i] = Math.max(d[i], d[i + 1] + 1);
                }
                sum += d[i];
            }
            return sum;
    }

### 1.9 爬楼梯 ###

public static int climstairsRecursive(int n){
    	if(n < 2) return 1;
    	return climstairsRecursive(n - 1) + climstairsRecursive(n - 2);
    }
    
    public static int climstairsIterator(int n){
    	int first = 1;
    	int second = 2;
    	for(int i = 1; i < n; i++){
    		int third = first + second;
    		first = second;
    		second = third;
    	}
    }

### 1.10 水桶面积 ###

public int maxWater(int[] height){
            int max = 0;
            int i = 0;
            int j = height.length - 1;
            while(i < j){
                int cur = Math.min(height[i], height[j]) * (j - i);
                max = Math.max(max, cur);
                if(height[i] < height[j]){
                    ++i;
                } else {
                    j--;
                }
            }
            return max;
        }

### 1.11 洗牌 ###

public static void swap(int[] nums, int i, int j){
    	int temp = nums[i];
    	nums[i] = nums[j];
    	nums[j] = nums[i];
    }
    public static int[] shuffer(int[] nums){
    	for(int i = nums.length - 1; i > 0; i--){
    		int j = random.nextInt(i + 1);
    		swap(nums, i, j);
    	}
    	return nums;
    }

### 1.12 冒泡排序 ###

空间：O(1)
    时间：O(n ^ 2)
    public static void sort(int[] nums){
            boolean hasChange = true;
            for(int i = 0; i < nums.length - 1; i++){
                hasChange = false;
                for(int j = 0; j < nums.length - 1 - i; j++){
                    if(nums[j] > nums[i + 1]){
                        swap(nums, j, j + 1);
                        hasChange = true;
                    }
                }
            }
        }

### 1.13 快速排序 ###

private static void doQuickSort(int[] datas, int low, int high){
            if(low < high){
                int priority = partition(datas, low, high);
                doQuickSort(datas, 0, priority);
                doQuickSort(datas, priority + 1, high);
            }
        }
    
        private static int partition(int[] datas, int low, int high) {
            int priority = datas[low];
            while(low < high) {
                while(low < high && datas[high] >= priority){
                    high--;
                }
                datas[low] = datas[high];
                while(low < high && datas[low] <= priority) {
                    low++;
                }
                datas[high] = datas[low];
            }
            datas[low] = priority;
            return low;
        }

### 1.14 插入排序 ###

空间：O(1)
    时间：O(n ^ 2)
    //从i开始，插入到它们前面
    public static void insertSort(int[] nums){
            for(int i = 1; i < nums.length; i++) {
                if(nums[i] < nums[i - 1]){
                    int temp = nums[i];
                    int j  = i - 1;
                    for(; j >= 0 && nums[j] > temp; j--){
                        nums[j + 1] = nums[j];
                    }
                    nums[j + 1] = temp;
                }
            }
        }

### 1.15 选择排序 ###

public static void selectSort(int[] nums){
            for(int i = 0; i < nums.length - 1; i++){
                int minIndex = i;
                for(int j = i + 1; j < nums.length; j++){
                    if(nums[j] < nums[minIndex]){
                        minIndex = j;
                    }
                }
                if(minIndex != i){
                    swap(nums, i, minIndex);
                }
            }
        }

### 1.16 归并排序 ###

public static void guibingSort(int[] nums){
            doGuiBingSort(nums, 0 , nums.length - 1);
        }
    
        public static void doGuiBingSort(int[] nums, int low, int high){
            if(low < high){
                int mid = low + (high - low) / 2;
                doGuiBingSort(nums, low, mid);
                doGuiBingSort(nums, mid + 1, high);
                merge(nums, low, mid, high);
            }
        }
    
        private static void merge(int[] nums, int low, int mid, int high) {
            int[] copy = nums.clone();
            int k = low, i = low, j = mid + 1;
            while(k <= high){
                if(i > mid){
                    nums[k++] = copy[j++];
                } else if(j > high){
                    nums[k++] = copy[i++];
                } else if(copy[j] < copy[i]){
                    nums[k++] = copy[j++];
                } else {
                    nums[k++] = copy[i++];
                }
            }
        }

### 1.17 二分搜索 ###

public static int doBinarySort(int[] nums, int target){
            if(nums == null){
                return -1;
            } else {
                int low = 0;
                int high = nums.length - 1;
                while(low <= high){
                    int mid = low + (high - low) / 2;
                    if(target < nums[mid]) {
                        high = mid - 1;
                    } else if(target > nums[mid]){
                        low = mid + 1;
                    } else {
                        return mid;
                    }
                }
            }
            return -1;
        }

### 1.18 是否是3的n次方 ###

public static boolean check(int n) {
            if (n <= 0){
                return false;
            }
            while(n % 3 == 0){
                n /= 3;
            }
            return n == 1;
        }

## 二、数组 ##

### 2.1 求数组两数之和为给定数的两数下标 ###

public static void main(String[] args) {
            int[] nums = {1,5,2,6,3,8,7,4,9};
            int[] twoSum = twoSum(nums, 11);
        }
    
        private static int[] twoSum(int[] nums, int target) {
            HashMap<Integer, Integer> hashMap = new HashMap();
            for(int i = 0; i < nums.length; i++){
                int num = target - nums[i];
                if(hashMap.containsKey(num)){
                    return new int[]{hashMap.get(num).intValue(), i};
                }
                hashMap.put(nums[i], i);
            }
            return null;
        }

### 2.2 有序数组找到目标和的两个索引下标 ###

public int[] getTwoNumSumToGivenValue(int[] numbers, int target){
      int i = 0, j = numbers.length - 1;
      while(i < j){
        if(numbers[i] + numbers[j] > target) --j;
        if(numbers[i] + numbers[j] < target) i++;
        else return newInt[]{i,j};
      }
      return newInt[]{-1, -1};
    }

### 2.3 求中位数 ###

public static List<Integer> data = new ArrayList<>();
    
        public void addNum(int num){
            int idx = data.size() - 1;
            while(idx >=0 && data.get(idx) > num) {
                idx--;
            }
            data.add(idx + 1, num);
        }
    
        public double findMedian(){
            if((data.size() & 1) == 1){
                return data.get(data.size() / 2);
            } else {
                return ((data.get(data.size()  / 2 - 1) + data.get(data.size() / 2)) / 2.0);
            }
        }

### 2.4 二维数组中找到目标值(从上到下，从左到右递增) ###

public int[] searchIn2DArray(int[][] matrix, int target){
            if(matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0
                || target < matrix[0][0]
                || target > matrix[matrix.length - 1][matrix[0].length - 1]){
                return new int[]{-1, -1};
            }
            int m = matrix.length;
            int n = matrix[0].length;
            int i = 0;
            int j =  n - 1;
            while(i < m && j >= 0){
                if(matrix[i][j] > target){
                    j--;
                } else if(matrix[i][j] < target){
                    i++;
                } else {
                    return new int[]{i, j};
                }
            }
            return new int[]{-1, -1};
    }

### 2.5 合并两个从小到大排序的数组 ###

public void mergeTwoSortedArray(int[] nums1, int m, int[] nums2, int n){
            int i = m -1;
            int j = n - 1;
            int k = m + n -1;
            while(i >= 0 && j >= 0){
                if(nums2[j] > nums1[i]){
                    nums1[k--] = nums2[j--];
                } else {
                    nums1[k--] = nums1[i--];
                }
            }
            while(j >= 0){
                nums1[k--] = nums2[j--];
            }
        }

### 2.6 求一组数组中相邻数最大和 ###

public static int maxSubArr(int[] nums) {
            int max = Integer.MIN_VALUE;
            int cur = 0;
            for(int i = 0; i < nums.length; i++){
                cur = cur <= 0 ? nums[i] : (cur + nums[i]);
                max = Math.max(max, cur);
            }
            return max;
        }

### 2.7 将数组中的0移动至最后面，其他数组保持原有顺序 ###

public static void move2ZerosAssign(int[] nums){
            if(nums == null || nums.length < 1){
                return ;
            }
            int cur =0;
            for(int fast = 0; fast < nums.length; fast++){
                if(nums[fast] != 0){
                    nums[cur] = nums[fast];
                    cur++;
                }
            }
            for(;cur < nums.length; cur++){
                nums[cur] = 0;
            }
        }

### 2.8 从矩阵一端走到另一端，有障碍物 ###

public int uniquePathWithObstacles(int[][] grid){
            int m = grid.length;
            int n = grid[0].length;
            int[][] d = new int[m][n];
            d[0][0] = grid[0][0] == 1 ? 0 : 1;
            for(int i = 1; i < m; i++){
                d[i][0] = grid[i][0] == 1 ? 0 : 1;
            }
            for(int j = 1; j < n; j ++){
                d[0][j] = grid[j][0] == 1 ? 0 : 1;
            }
            for(int i = 1; i < m; i++){
                for(int j = 1; j < n; j++){
                    d[i][j] = grid[i][j] == 1 ? 0 : d[i-1][j] + d[i][j-1];
                }
            }
            return d[m-1][n-1];
        }

### 2.9 爬完楼梯最小消耗 ###

//给出一个每一层的消耗例如int[] cost = {1,2,3,4}
    //爬到1层消耗1，爬到2层不管是从0-2还是1-2消耗都是2，这里最小消耗是4(1-3,3完了之后走2步就上完楼了)
    public static int minCostClimbingStairs(int[] cost){
            if(cost == null || cost.length == 0){
                return 0;
            }
            if(cost.length == 1){
                return cost[0];
            }
            int n = cost.length;
            int[] d = new int[n];
            d[0] = cost[0];
            d[1] = cost[1];
            for(int i = 2; i < n; i++){
                d[i] = Math.min(d[i-1], d[i-2]) + cost[i];
            }
            return Math.min(d[n-2], d[n-1]);
    }

### 2.10 数组中出现次数最多的数 ###

public static int geMax(int[] nums){
            Map<Integer, Integer> map = new HashMap<>();
            int maxNum = 0;
            int maxCount = 0;
            for(int i = 0; i < nums.length; i++){
                int newCnt = map.getOrDefault(nums[i], 0) + 1;
                map.put(nums[i], newCnt);
                if(newCnt > maxCount){
                    maxCount = newCnt;
                    maxNum = nums[i];
                }
            }
            return maxCount;
        }

### 2.11 缺失的数字 ###

//缺失的数字，数字从0到n连续排列，去除一个，放到数组中找出来
        public static int getInt(int[] nums){
            int n = nums.length;
            int result = 0;
            //(0,1,3)==> 0^0 1^1 2^3 ==>2^3^3==>2
            for(int i = 0; i < nums.length; i++){
                result = result ^ i ^ nums[i];
            }
            return result ^ n;
        }

### 2.12 数组全排列 ###

void permuteRec(List<Integer> nums, int start, List<List<Integer>> result){
            if(start == nums.size()){
                result.add(new ArrayList(nums));
            } else {
                for(int i = start; i < nums.size(); i++){
                    Collections.swap(nums, i, start);
                    permuteRec(nums, start + 1, result);
                    Collections.swap(nums, i, start);
                }
            }
        }
    
        public List<List<Integer>> permute(int[] nums){
            if(nums == null || nums.length == 0){
                return new ArrayList<>();
            }
            List<List<Integer>> result = new ArrayList<>();
            List<Integer> list = new ArrayList<>();
            for (int num : nums) {
                list.add(num);
            }
            permuteRec(list, 0, result);
            return result;
        }

### 2.13 数组区间合并(给几个没有重叠的区间列表，加入新的区间，若区间有重叠，那么合并) ###

public int[][] insertByMerge(int[][] intervals, int[] newInterval){
            int[][] temp = new int[intervals.length + 1][2];
            int size = 0;
            int p = 0;
            for(; p < intervals.length && intervals[p][0] < newInterval[0]; ++p){
                temp[size++] = intervals[p];
            }
            if(size == 0 || temp[size - 1][1] < newInterval[0]){
                temp[size++] = newInterval;
            } else {
                temp[size - 1][1] = Math.max(temp[size - 1][1], newInterval[1]);
            }
            for(;p < intervals.length; p++){
                if(temp[size - 1][1] < intervals[p][0]){
                    temp[size++] = intervals[p];
                } else {
                    temp[size - 1][1] = Math.max(temp[size - 1][1], intervals[p][1]);
                }
            }
            return Arrays.copyOf(temp, size);
     }

## 三、树 ##

### 3.1 判断一棵树是否是二分搜索树 ###

public boolean isBst(){
    	ArrayList<E> keys = new ArrayList();
    	inOrder(root, keys):
    	for(int i = 1; i < keys.size(); i++){
    		if(keys.get(i - 1).compareTo(keys.get(i)) > 0){
    			return false;
    		}
    	}
    	return true;
    }
    
    public void inOrder(Node root, List keys){
    	if(root == null){
    		return;
    	}
    	inOrder(node.left, keys);
    	keys.add(node.key);
    	inOrder(node.right, keys);
    }

### 3.2 两个树是否一致 ###

public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p==null&&q==null) return true;
        if( (p==null&&q!=null)||(q==null&&p!=null) ) return false;
        if(p.val!=q.val) return false;
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }

### 3.3 判断二叉树是否对称(左节点和右节点一致) ###

// 递归法
        public boolean isSymmetric2(TreeNode root) {
            return root==null || func(root.left, root.right);
        }
    
        public static boolean func(TreeNode left, TreeNode right){
            if(left==null || right==null)
                return left == right;
            return (left.val==right.val) && func(left.left,right.right) && func(left.right,right.left);
        }
        //非递归
        public static boolean isSymmetricTreeIterative(TreeNode root){
            if(root == null){
                return true;
            }
            Queue<TreeNode> queue = new LinkedList<>();
            queue.add(root.left);
            queue.add(root.right);
            while(!queue.isEmpty()){
                TreeNode left = queue.poll();
                TreeNode right = queue.poll();
                if(left == null && right == null){
                    return true;
                } else if(left == null || right == null){
                    return false;
                } else {
                    if(left.val == right.val){
                        return true;
                    }
                    queue.add(left.left);
                    queue.add(right.right);
                    queue.add(left.right);
                    queue.add(right.left);
                }
            }
            return false;
        }

### 3.4 二叉树层次遍历 ###

public List<List<Integer>> levelOrder(TreeNode root) {
            Queue<TreeNode> qu = new LinkedList<>();
            List<List<Integer>> res = new ArrayList<>();
            if(root==null)
                return res;
            qu.add(root);
            while(!qu.isEmpty()){   //两个while
                int size = qu.size();
                List<Integer> temp = new ArrayList<>();
                while(size>0){
                    TreeNode tn = qu.remove();
                    if(tn!=null) {
                        if(tn.left!=null)
                            qu.add(tn.left);
                        if(tn.right!=null)
                            qu.add(tn.right);
                    }
                    temp.add(tn.val);
                    size--;
                }
                res.add(temp);
            }
            return res;
        }

### 3.5 二叉树最大/小深度 ###

public int maxDepth(TreeNode root) {
    	if(root==null) return 0;
    	return Math.max(maxDepth(root.left),maxDepth(root.right)) + 1;
    }
    public int minDepth(TreeNode root) {
    	if(root==null) return 0;
    	return Math.min(minDepth(root.left),minDepth(root.right)) + 1;
    }

### 3.6 是否是平很二叉树 ###

public static int getHeightAndCheck(TreeNode treeNode){
            if(treeNode == null) {
                return 0;
            }
            int left = getHeightAndCheck(treeNode.left);
            if(left == -1){
                return -1;
            }
            int right = getHeightAndCheck(treeNode.right);
            if(right == -1){
                return -1;
            }
            if(Math.abs(left - right) > 1) return -1;
            return Math.abs(left - right) + 1;
        }
    
        public static int maxDepthIterative(TreeNode treeNode){
            if(treeNode == null) return 0;
            Queue<TreeNode> q = new LinkedList()
            q.add(treeNode);
            int depth = 0;
            while(!q.isEmpty()){
                int size = q.size();
                for(int i = 0; i < size; i++){
                    TreeNode poll = q.poll();
                    if(poll.left != null){
                        q.add(poll.left);
                    } else if(poll.right != null){
                        q.add(poll.right);
                    }
                }
                ++depth;
            }
            return depth;
        }

### 3.7 反转二叉树 ###

public static TreeNode invertBinaryTreeIterative(TreeNode root){
            if(root == null) {
                return root;
            }
            Queue<TreeNode> q = new LinkedList<>();
            q.add(root);
            while(!q.isEmpty()){
                TreeNode poll = q.poll();
                TreeNode tmp = poll.left;
                poll.left = poll.right;
                poll.right = tmp;
                if(poll.left != null){
                    q.add(poll.left);
                }
                if(poll.right != null){
                    q.add(poll.right);
                }
            }
            return root;
        }

### 3.8 树的最小深度 ###

public static int minDepth(TreeNode root){
            if(root == null){
                return 0;
            }
            if(root.left == null && root.right == null) {
                return 1;
            }
            if(root.left == null){
                return minDepth(root.right) + 1;
            }
            if(root.right == null){
                return minDepth(root.left) + 1;
            }
            return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
        }

### 3.9 二叉树中和为给定值的路径 ###

public static void path(TreeNode root, int sum, List<Integer> elem, List<List<Integer>> result){
            if(root == null){
                return;
            }
            elem.add(root.val);
            if(root.left == null && root.right == null && root.val == sum){
                result.add(new ArrayList<>(elem));
            }
            path(root.left, sum - root.val, elem, result);
            path(root.right, sum - root.val, elem, result);
            elem.remove(elem.size() - 1);
    }
    
        public List<List<Integer>> pathSumRecursive(TreeNode root, int sum){
            List<List<Integer>> result = new ArrayList<>();
            List<Integer> elem = new ArrayList<>();
            path(root, sum, elem, result);
            return result;
        }

### 3.10 验证二叉树前序遍历是否是正确的 ###

public static boolean verify(int[] nums, int start, int end){
            if(start == end || start + 1 == end){
                return true;
            }
            int root = nums[start];
            int i = start + 1;
            while(i < end && nums[i] < root) {
                i++;
            }
            int mid = i ;
            while(i < end && nums[i] > root) {
                i++;
            }
            if(i == end){
                return verify(nums, start + 1, mid) && verify(nums, mid, end);
            } else {
                return false;
            }
        }
    
        public static boolean verifyPreOrder(int[] preOrder){
            if(preOrder == null){
                return false;
            }
            return verify(preOrder, 0, preOrder.length);
        }

### 3.11 搜索一个值是否在二分搜索中 ###

public TreeNode search(TreeNode root, int val){
    	if(root == null || root.val == val){return val;}
    	else if(root.val > val){
    		return search(root.left, val);
    	} else {
    		return search(root.right, val);
    	}
    }

## 四、栈 ##

### 4.1 排列组合"1234"(不重复数字) ###

private static List<String> concat(String str){
            List<String> list = new ArrayList();
            Stack<Character> stack = new Stack<>();
            if(str == null || str.length() < 1){
                return null;
            }
            toConcat(str.toCharArray(), str.length(), 0, stack, list);
            return list;
        }
    
        private static void toConcat(char[] chars, int count, int cur, Stack<Character> stack, List<String> list) {
            if(cur == count){
                StringBuilder sb = new StringBuilder();
                Iterator<Character> iterator = stack.iterator();
                while(iterator.hasNext()) {
                    sb.append(iterator.next());
                }
                list.add(sb.toString());
                return;
            }
            for(int i = 0; i < count; i++){
                if(stack.contains(chars[i])){
                    continue;
                }
                stack.push(chars[i]);
                toConcat(chars, count, cur + 1, stack, list);
                stack.pop();
            }
        }

### 4.2 括号匹配 ###

String s = "()[]{}";
    System.out.println(isValid(s));
    public static boolean isValid(String s){
    	Stack<Character> stack = new Stack();
        for(int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            if(c == '(' || c == '[' || c =='{'){
            	stack.push(c);
            } else {
                if(stack.isEmpty()){
                	return false;
                }
    			Character pop = stack.pop();
                if(c == ')' && pop !='('){
                	return false;
                }
                if(c == ']' && pop != '['){
                    return false;
                }
                if(c == '}' && pop != '{'){
                return false;
                }
        	}
        }
        return true;
    }

### 4.3 最小栈 ###

public class MinStack{
    	
    	Stack<Integer> stack;
    	Stack<Integer> minStack;
    	
    	public MinStack(){
    		stack = new Stack();
    		minStack = new MinStack();
    	}
    	
    	public void push(int x){
    		stack.push(x);
    		if(minStack.isEmpty() || x < minStack().peek()){
    			minStack.push(x);
    		} else {
    			minStack.push(minStack.peek());
    		}
    	}
    	
    	public void pop(){
    		stack.pop();
    		minStack.pop();
    	}
    	
    	public int top(){
    		return minStack.peek();
    	}
    	
    	public int getMin(){
    		return minStack.peek();
    	}
    }

### 4.4 带有min的最小栈 ###

private Stack<Integer> stack = new Stack();
        private Stack<Integer> minStack = new Stack<>();
    
        public void push(int x){
            stack.push(x);
            if(minStack.isEmpty() || minStack.peek() < x){
                minStack.push(x);
            }
        }
    
        public void pop(){
            if(stack.peek() == minStack.peek()){
                minStack.pop();
            }
            stack.pop();
        }
    
        public int top(){
            stack.peek();
        }
    
        public void getMin(){
            minStack.peek();
        }

### 4.5 栈实现队列 ###

public class StackQueue<E> {
    
        private Stack<E> in = new Stack();
        private Stack<E> out = new Stack();
    
        private void transferIfEmpty(){
            if(out.isEmpty()) {
                while(!in.isEmpty()){
                    out.push(in.pop());
                }
            }
        }
    
        public void push(E e){
            in.push(e);
        }
    
        public E pop(){
            transferIfEmpty();
            return out.pop();
        }
    
        public E peek(){
            transferIfEmpty();
            return out.peek();
        }
    
        public boolean empty(){
            return in.isEmpty() && out.isEmpty();
        }
    }

## 五、队列 ##

## 六、链表 ##

### 6.1 判断单链表是否为回文链表 ###

public static boolean isPalindromeUsingStack(ListNode<Integer> listNode){
            Stack<Integer> stack = new java.util.Stack();
            for(ListNode<Integer> p = listNode; p != null; p = p.next){
                stack.push(p.val);
            }
            for(ListNode p = listNode; p != null; p = p.next){
                if(p.val != stack.pop()){
                    return false;
                }
            }
            return true;
        }

### 6.2 合并两个链表，按照从小到大顺序排序 ###

public ListNode mergeTwoSortedList(ListNode<Integer> l1, ListNode<Integer> l2){
            ListNode dummy = new ListNode(0);
            ListNode p = dummy;
            while(l1 != null && l2 != null){
                if(l1.val < l2.val){
                    //1->2 p->1 l1 = 2
                    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 dummy.next;
        }

### 6.3 把序号奇数放到前面，偶数放到后边 ###

public ListNode<Integer> oddEventList(ListNode head){
            if(head == null || head.next == null || head.next.next == null){
                return head;
            }
            ListNode eventHead = head.next;
            ListNode odd = head;
            ListNode even = eventHead;
            while(even != null && even.next != null){
                odd.next = even.next;
                odd = odd.next;
                even.next = odd.next;
                even = even.next;
            }
            odd.next = eventHead;
            return head;
        }

### 6.4 链表反转 ###

public ListNode<Integer> reverseList(ListNode head){
         ListNode cur = head;
         ListNode pre = null;
         while(cur != null){
         ListNode next = cur.next;
         cur.next = pre;
         pre = cur;
         cur = next;
         }
         return pre;
    }

## 七、图 ##

## 八、堆与优先级队列 ##

### 8.1 求数组中第k大元素 ###

PriorityQueue<Integer> minHeap = new PriorityQueue<>(k, new Comparator<Integer>() {
                @Override
                public int compare(Integer o1, Integer o2) {
                    //从小到打排序
                    return o1 - o2;
                }
            });
            for(int i = 0; i < nums.length; i++){
                minHeap.add(nums[i]);
            }
            for(int i = 0; i < k - 1; i++){
                minHeap.poll();
            }
            return minHeap.poll();
    //===================================================================
    public int findKth(int[] nums, int k){
    	Queue<Integer> minHeap = new PriorityQueue<>();
    	for(int num: nums){
    		if(minHeap.size() < k){
    			minHeap.add(num);
    		} else if(num > minHeap.peek()) {
    			minHeap.poll();
    			minHeap.add(num);
    		}
    	}
    	return minHeap.peak();
    }

### 8.2 求中位数 ###

private static Queue<Integer> minHeap = new PriorityQueue();
     private static Queue<Integer> maxHeap = new PriorityQueue(Collections.reverseOrder());
    
        public void addNum(int num){
            minHeap.add(num);
            maxHeap.add(minHeap.poll());
            if(maxHeap.size() - minHeap.size() > 1){
                minHeap.add(maxHeap.poll());
            }
        }
    
        public double findMedian(){
            if(maxHeap.size() > minHeap.size()){
                return maxHeap.peek();
            } else {
                return (maxHeap.peek() + minHeap.peek()) / 2.0;
            }
        }

## 九、排序与搜索 ##

### 9.1 快速排序 ###

public static void main(String[] args) {
            int[] datas = {6,2,4,8,7,10,1,3,9};
            doQuickSort(datas, 0, datas.length - 1);
            System.out.println(JSON.toJSONString(datas));
        }
    
        private static void doQuickSort(int[] datas, int low, int high){
            if(low < high){
                int priority = partition(datas, low, high);
                doQuickSort(datas, 0, priority);
                doQuickSort(datas, priority + 1, high);
            }
        }
    
        private static int partition(int[] datas, int low, int high) {
            int priority = datas[low];
            while(low < high) {
                while(low < high && datas[high] >= priority){
                    high--;
                }
                datas[low] = datas[high];
                while(low < high && datas[low] <= priority) {
                    low++;
                }
                datas[high] = datas[low];
            }
            datas[low] = priority;
            return low;
        }

### 9.2 插入排序 ###

### 9.8 二分法搜索 ###

## 十、动态规划 ##

### 9.1爬楼梯 ###

f(n) = f(n-1) + f(n-2)
    f(1) = 1 f(2) = 2 f(3) = 3 f(4)=5
    public int climbStairs(int n){
    	if(n <= 3){
    		return n;
    	}
    	return climbStairs(n - 1) + climbStairs(n - 2);
    }
    
    int[] steps = new int[n+1];
    steps[1] = 1
    steps[2] = 2
    for(int i = 3; i <= n; i++){
       steps[i] = steps[i - 1] + steps[i - 2];
    }
    return steps[n];
    
    int[] steps = new int[3];
    steps[0] = 1
    steps[1] = 2
    for(int i = 2; i < n; i++){
       steps[i % 3] = steps[(i - 1) % 3] + steps[(i - 2) % 3];
    }
    return steps[(n - 1) % 3];

### 9.2 迷宫走法 ###

从迷宫一端走到另一端的走法
    public int unquePaths(int m, int n){
      if(m == 0 || n == 0){
        return 1;
      }
      int[][] path = new int[m][n];
      for(int i = 0; i < m; i++){
        path[i][0] = 1;
      }
      for(int j = 0; j < n; j++){
      	path[0][j] = 1;
      }
      for(int i = 1; i < m; i++){
      	for(int j = 1; j < n; j++){
      		path[i][j] = path[i - 1][j] = path[i][j-1];
      	}
      }
      return path[m - 1][n - 1];
    }

## 十一、字符串 ##

### 11.1 字符串反转 ###

public static String reverseWordAndChar(String s){
            if(s == null || s.length() == 0){
                return s;
            } else {
                String[] splitCharArr = s.split(" ");
                StringBuilder sb = new StringBuilder();
                for(int i = splitCharArr.length - 1; i >= 0; i--){
                    sb.append(reverseStr(splitCharArr[i]) + " ");
                }
                return sb.toString().trim();
            }
        }
    
        public static String reverseWord(String s){
            if(s == null || s.length() == 0){
                return s;
            } else {
                String[] splitCharArr = s.split(" ");
                StringBuilder sb = new StringBuilder();
                for(int i = splitCharArr.length - 1; i >= 0; i--){
                    sb.append(splitCharArr[i] + " ");
                }
                return sb.toString().trim();
            }
        }
    
        public static String reverseStr(String s){
            StringBuilder sb = new StringBuilder();
            for(int i = s.length() - 1; i >= 0; i--){
                sb.append(s.charAt(i));
            }
            return sb.toString();
        }

### 11.2 两个二进制字节字符串相加 ###

public static void main(String[] args) {
            String a = "1101";
            String b = "110";
            StringBuilder sb = new StringBuilder();
            int i = a.length() - 1;
            int j = b.length() - 1;
            int carry = 0;
            while( i >= 0 || j >= 0 || carry != 0){
                int sum = carry;
                if(j >= 0) {
                    sum += a.charAt(i--) - '0';
                }
                if(j >= 0) {
                    sum += b.charAt(j--) - '0';
                }
    //            sb.append(sum % 2);
                sb.append(sum & 1);
    //            carry = sum / 2;
                carry = sum >> 1;
            }
            System.out.println(sb.reverse().toString());
        }

### 11.3 一个字符串里有多少个回文字符串 ###

public static void count(String s, List<List<Integer>> res) {
            if (s == null || s.length() == 0) {
                return;
            }
            int n = s.length();
            int count = 0;
            boolean[][] visited = new boolean[n][n];
            for (int i = n - 1; i >= 0; i--) {
                for (int j = i; j < n; j++) {
                    if (i == j) {
                        visited[i][j] = true;
                    } else if (i + 1 == j) {
                        visited[i][j] = (s.charAt(i) == s.charAt(j));
                    } else {
                        visited[i][j] = (s.charAt(i) == s.charAt(j) && visited[i + 1][j - 1]);
                    }
                    if (visited[i][j]) {
                        count++;
                        List list = new ArrayList();
                        list.add(i);
                        list.add(j);
                        res.add(list);
                    }
                }
            }
        }
        
        public int countSubstrings(String s) {
            // 动态规划法
    	boolean[][] dp = new boolean[s.length()][s.length()];
    	int ans = 0;
    	ArrayList list = new ArrayList();
    	for (int j = 0; j < s.length(); j++) {
    		for (int i = 0; i <= j; i++) {
    			if (s.charAt(i) == s.charAt(j) && (j - i < 2 || dp[i + 1][j - 1])) {
    				dp[i][j] = true;
    				list.add(s.subString(i, j+1);
    				ans++;
    			}
    		}
    	}
    	list.sort((s1, s2) -> {return s1.length() - s2.length();})
    	return ans;
    }

### 11.4 一个字符串是否包含另一个字符串 ###

public static int strContainsStr(String s1,String s2){
            if(s1 != null && s2 != null){
                int j = 0;
                for (int i = 0; i < s1.length () - s2.length () + 1; i++){
                    for(j = 0; j < s2.length (); j++){
                        if(i+j < s1.length ()){
                            if(s1.charAt (i+j) != s2.charAt (j)){
                                break;
                            }
                        }
                    }
                    if(j == s2.length ()){
                        return 1;
                    }
                }
            }
            return -1;
        }	
        public static int contains(String s1, String s2){
            if(s1 == null || s2 == null || s1.length() == 0 || s2.length() == 0){
                return -1;
            }
            //abcd ab 最多遍历到2 4-2=2
            for(int i = 0; i <= s1.length() - s2.length(); i++){
                int j = 0;
                int k = i;
                for(; j < s2.length() && k < s1.length() && s1.charAt(k) == s2.charAt(j); j++, k++){
                    if(j == s2.length() - 1){
                        return i;
                    }
                }
            }
            return -1;
        }

### 11.5 一个字符串是否是回文字符串 ###

public static boolean isPalindromeString(int x){
            String str = String.valueOf(x);
            int i = 0;
            int j = str.length();
            while(i < j){
                if(str.charAt(i) != str.charAt(j)){
                    return false;
                }
                i++;
                j--;
            }
            return true;
        }