小小林熬夜学编程

这个屌丝很懒，什么也没留下！

热门标签

算法刷题java_java 算法刷题

作者：小小林熬夜学编程 | 2024-04-27 04:27:33

踩

java 算法刷题

一、基础运算

Queue priorityQueue = new PriorityQueue<>();
PriorityQueue<Map.entry<Integer, Integer>> pg = new PriorityQueue((a,b) -> a.getValue() - b.getValue());
PriorityQueue<int[]> queue = new PriorityQueue<int[]>(new Comparator<int[]> () {
public int compare(int[] m, int[] n) {
return m[1] - n[1];
}
});
Queue priorityQueueReverse = new PriorityQueue<>(Collections.reverseOrder());
Queue priorityQueueReverse2 = new PriorityQueue<>((a, b) -> b-a);
Queue queue = new LinkedList<>();
queue.add(1);
Integer poll = queue.poll();

    TreeMap<Integer, String> treeMap = new TreeMap<>();
    //从小到大
    Map.Entry<Integer, String> integerStringEntry = treeMap.pollFirstEntry();
    //从大到小
    Map.Entry<Integer, String> integerStringEntry1 = treeMap.pollLastEntry();
    Stack<Integer> stack = new Stack<>();
1
2
3
4
5
6

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
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

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
2
3
4
5
6
7
8
9
10
11
12
13

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
2
3
4
5
6
7
8
9
10
11
12
13
14

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

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
2
3
4
5
6
7
8
9

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
2
3
4
5
6
7
8
9

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

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

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

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
2
3
4
5
6
7
8
9
10
11
12
13
14

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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
2
3
4
5
6
7
8
9
10
11
12

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
2
3
4
5
6
7
8
9
10
11
12
13
14

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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
2
3
4
5
6
7
8
9
10
11
12
13

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

1.18 是否是3的n次方

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

1
2
3
4
5
6
7
8
9
10

二、数组

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

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

1
2
3
4
5
6
7
8
9
10

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

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

1
2
3
4
5
6
7
8
9
10

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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

1
2
3
4
5
6
7
8
9
10
11

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

三、树

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

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

1
2
3
4
5
6
7

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

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

1
2
3
4
5
6
7
8
9

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

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

1
2
3
4
5
6
7
8
9

四、栈

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

五、队列

六、链表

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

1
2
3
4
5
6
7
8
9
10
11
12
13

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

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

1
2
3
4
5
6
7
8
9
10
11
12

七、图

八、堆与优先级队列

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


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

九、排序与搜索

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

十一、字符串

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小小林熬夜学编程/article/detail/494770

算法刷题java_java 算法 刷题