高频面试算法

发表于 2020-03-01 更新于 2024-03-24 分类于数据结构与算法阅读次数：本文字数： 52k 阅读时长 ≈ 47 分钟

排序问题
栈和队列
矩阵
链表
二叉树
布隆过滤器
- URL筛选
  - 要求
一致性哈希
- 问题
- 解决办法
岛问题
并查集
前缀树
贪心算法
递归&动态规划

来源《程序员代码面试指南》左程云著

排序问题

小和问题

在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和。求一个数组
的小和。

例子：
[1,3,4,2,5]
1左边比1小的数， 没有；
3左边比3小的数， 1；
4左边比4小的数， 1、 3；
2左边比2小的数， 1；
5左边比5小的数， 1、 3、 4、 2；
所以小和为1+1+3+1+1+3+4+2=16

题解：

利用归并排序，在merge的时候计算有几个数比它小。因为分区两边都将是有序的，当左边分组元素小于右边分组元素，将会有 (r - p2 + 1) * arr[p1] 个小数。r为最右边边界，p2为右边分组元素下标，arr[p1] 为左边分组元素，相加则为产生的小和。

因为整体将趋于有序，而且每次merge之后元素都将归入左边，所有之后不会重复计算小和。

public static int smallSum(int[] arr) {
	if (arr == null || arr.length < 2) {
		return 0;
	}
	return mergeSort(arr, 0, arr.length - 1);
}
public static int mergeSort(int[] arr, int l, int r) {
	if (l == r) {
		return 0;
	}
	int mid = l + ((r - l) >> 1);
	return mergeSort(arr, l, mid) + mergeSort(arr, mid + 1, r) + merge(arr, l, mid, r);
}
public static int merge(int[] arr, int l, int m, int r) {
	int[] help = new int[r - l + 1];
	int i = 0;
	int p1 = l;
	int p2 = m + 1;
	int res = 0;
	while (p1 <= m && p2 <= r) {
	    //计算小和
		res += arr[p1] < arr[p2] ? (r - p2 + 1) * arr[p1] : 0;
		help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
	}
	while (p1 <= m) {
		help[i++] = arr[p1++];
	}
	while (p2 <= r) {
		help[i++] = arr[p2++];
	}
	for (i = 0; i < help.length; i++) {
		arr[l + i] = help[i];
	}
	return res;
}

逆序对问题

在一个数组中，左边的数如果比右边的数大，则折两个数构成一个逆序对，请打印所有逆序
对。

题解：

与上题解题思路一致。将计算小和改为判断 arr[p1] > arr[p2] 如果是，则打印 arr[p1], arr[p2]即可。

相邻两数的最大差值

给定一个数组，求如果排序之后，相邻两数的最大差值。

要求时间复杂度O(N),且要求不能用非基于比较的排序。

题解：

使用桶排序的概念，在此基础上进行优化。

遍历给定的数组，找到数组中的最大值、最小值(最大值等于最小值时说明，数组中数据都一样，返回 0 ),用于计算桶id。
准备n+1 个桶，对于每个桶中的元素设定三个标志位。是否有数据 hasNum、最大值 maxs、最小值 mins。
再次遍历标志位。第0 个桶一定非空，且为最小值。从第一个桶开始遍历，找到每个非空桶(hasNum[i] 为 true)，非空桶的最小值与它前边最近的非空桶的最大值作差，与全局变量res作比较。遍历结束之后将得到最大的差值。

public static int maxGap(int[] nums) {
	if (nums == null || nums.length < 2) {
		return 0;
	}
	int len = nums.length;
	int min = Integer.MAX_VALUE;
	int max = Integer.MIN_VALUE;
	for (int i = 0; i < len; i++) {
		min = Math.min(min, nums[i]);
		max = Math.max(max, nums[i]);
	}
	// 如果最小值等于最大值，则数组中只有相同的数，最大差值为 0.
	if (min == max) {
		return 0;
	}
	
	// 计算每个桶中的三个标志位。
	boolean[] hasNum = new boolean[len + 1];
	int[] maxs = new int[len + 1];
	int[] mins = new int[len + 1];
	int bid = 0;
	for (int i = 0; i < len; i++) {
		bid = bucket(nums[i], len, min, max);
		mins[bid] = hasNum[bid] ? Math.min(mins[bid], nums[i]) : nums
		maxs[bid] = hasNum[bid] ? Math.max(maxs[bid], nums[i]) : nums
		hasNum[bid] = true;
	}
	
	// 从第一个桶开始。寻找不为空的桶，它的最小值和它之前最近的桶的最大值的差值，
	// 与全局变量res进行比较，遍历完则找到最大差值。
	int res = 0;
	int lastMax = maxs[0];
	int i = 1;
	for (; i <= len; i++) {
		if (hasNum[i]) {
			res = Math.max(res, mins[i] - lastMax);
			lastMax = maxs[i];
		}
	}
	return res;
}
// 最小值将存在0号桶，最大值将存在length号桶。
public static int bucket(long num, long len, long min, long max) {
	return (int) ((num - min) * len / (max - min));
}

栈和队列

数组实现固定大小的队列和栈

package com.jelly.algorithm.array;
public class Array2QueueStack {
    public static void main(String[] args) {
        // 数组实现队列 测试
        AQueue aQueue = new AQueue(3);
        aQueue.offer(1);
        aQueue.offer(2);
        aQueue.offer(3);
        aQueue.offer(4);
        System.out.println(aQueue.poll());
        aQueue.offer(5);
        System.out.println(aQueue.peek());
        // 数组实现栈 测试
        AStack aStack = new AStack(3);
        aStack.push(1);
        aStack.push(2);
        aStack.push(3);
        aStack.push(4);
        System.out.println(aStack.pop());
        aStack.push(5);
        System.out.println(aStack.peek());
    }
}
/**
 * 数组实现大小固定的队列。
 * <p>
 * arr：存储队列中的数据。
 * size：记录队列中有多少数据了。
 * start：记录出队列的位置。每次出start位置上的数据。
 * end：记录入队列的位置。每次入队列存入end的位置。
 */
class AQueue {
    private int[] arr;
    private int size;
    private int start;
    private int end;
    public AQueue(int initSize) {
        this.arr = new int[initSize];
        this.size = 0;
        this.start = 0;
        this.end = 0;
    }
    public boolean offer(Integer n) {
        if (size == arr.length) {
            System.out.println("queue is full!");
            return false;
        }
        size++;
        arr[end] = n;
        end = end == arr.length - 1 ? 0 : end + 1;
        return true;
    }
    public Integer poll() {
        if (size == 0) {
            System.out.println("queue is empty!");
            return null;
        }
        size--;
        int tmp = arr[start];
        start = start == arr.length - 1 ? 0 : start + 1;
        return tmp;
    }
    public Integer peek() {
        if (size == 0) {
            System.out.println("queue is empty!");
            return null;
        }
        return arr[start];
    }
}
/**
 * 数组实现大小固定的栈。
 * <p>
 * arr：存储栈中的数据。
 * size：栈中存储多少数据。
 */
class AStack {
    private int[] arr;
    private int size;
    public AStack(int initSize) {
        this.arr = new int[initSize];
    }
    public boolean push(Integer n) {
        if (size == arr.length) {
            System.out.println("stack is full!");
            return false;
        }
        arr[size++] = n;
        return true;
    }
    public Integer pop() {
        if (size == 0) {
            System.out.println("stack is empty!");
            return null;
        }
        return arr[--size];
    }
    public Integer peek() {
        if (size == 0) {
            System.out.println("stack is empty!");
            return null;
        }
        return arr[size - 1];
    }
}

实现返回栈中最小元素

实现一个特殊的栈，在实现栈的基本功能的基础上，再实现返
回栈中最小元素的操作。

要求

pop、 push、 getMin操作的时间复杂度都是O(1)。
设计的栈类型可以使用现成的栈结构。

package com.jelly.algorithm.array;
import java.util.Stack;
public class GetMinStack {
    public static void main(String[] args) {
        MyStack myStack = new MyStack();
        myStack.push(5);
        myStack.push(1);
        System.out.println(myStack.getMin());
        System.out.println(myStack.pop());
        myStack.push(3);
        myStack.push(8);
        System.out.println(myStack.getMin());
    }
}
/**
 * 可以返回栈中最小元素的栈。
 * <p>
 * pop、 push、 getMin操作的时间复杂度都是O(1)
 */
class MyStack {
    private Stack<Integer> stackData;
    private Stack<Integer> stackMin;
    public MyStack() {
        this.stackData = new Stack<>();
        this.stackMin = new Stack<>();
    }
    public void push(Integer n) {
        // 最小值栈中没有数据直接进栈。
        // 栈中有数据判断插入数据n 是否小于当前栈中最小值，小则插入n，否则再次插入栈中最小值 
        if (stackMin.isEmpty()) {
            stackMin.push(n);
        } else if (n <= getMin()) {
            stackMin.push(n);
        } else {
            stackMin.push(getMin());
        }
        stackData.push(n);
    }
    public Integer pop() {
        if (stackData.isEmpty()) {
            System.out.println("stack is empty!");
            return null;
        }
        // 弹栈时，数据栈和最小值栈同时弹出。
        stackMin.pop();
        return stackData.pop();
    }
    public Integer getMin() {
        if (stackMin.isEmpty()) {
            System.out.println("stack is empty!!");
            return null;
        }
        return stackMin.peek();
    }
}

如何仅用队列结构实现栈结构？

见下题

如何仅用栈结构实现队列结构？

package com.jelly.algorithm.stack;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
public class StackAndQueueConvert {
    public static void main(String[] args) {
        // 栈实现队列，应打印 1,2
        Stack2Queue stack2Queue = new Stack2Queue();
        stack2Queue.offer(1);
        stack2Queue.offer(2);
        stack2Queue.offer(3);
        System.out.println(stack2Queue.poll());
        stack2Queue.offer(4);
        stack2Queue.offer(5);
        System.out.println(stack2Queue.peek());
        System.out.println("----------------------");
        // 队列实现栈，应打印 3,5
        Queue2Stack queue2Stack = new Queue2Stack();
        queue2Stack.push(1);
        queue2Stack.push(2);
        queue2Stack.push(3);
        System.out.println(queue2Stack.pop());
        queue2Stack.push(4);
        queue2Stack.push(5);
        System.out.println(queue2Stack.peek());
    }
}
/**
 * 两个栈实现队列
 * <p>
 * 入队列栈中数据倒入出队列栈中的数据时，要保证出队列栈中无数据。
 */
class Stack2Queue {
    private Stack<Integer> in;
    private Stack<Integer> out;
    public Stack2Queue() {
        this.in = new Stack<>();
        this.out = new Stack<>();
    }
    public void offer(Integer n) {
        in.push(n);
    }
    public Integer poll() {
        if (out.empty() && in.empty()) {
            System.out.println("queue is empty!");
            return null;
        } else if (out.empty()) {
            while (!in.empty()) {
                out.push(in.pop());
            }
        }
        return out.pop();
    }
    public Integer peek() {
        if (out.empty() && in.empty()) {
            System.out.println("queue is empty!");
            return null;
        } else if (out.empty()) {
            while (!in.empty()) {
                out.push(in.pop());
            }
        }
        return out.peek();
    }
}
/**
 * 两个队列实现栈
 * <p>
 * 入栈直接放入stack这个队列中。
 * 每次出栈，将n-1个数据通过help队列保存，返回第n个数据，然后改变help、stack指针 即可。
 */
class Queue2Stack {
    private Queue<Integer> stack;
    private Queue<Integer> help;
    public Queue2Stack() {
        this.stack = new LinkedList<>();
        this.help = new LinkedList<>();
    }
    public void push(Integer n) {
        stack.offer(n);
    }
    public Integer pop() {
        if (stack.isEmpty()) {
            System.out.println("stack is empty!");
            return null;
        }
        while (stack.size() > 1) {
            help.offer(stack.poll());
        }
        int res = stack.poll();
        swap();
        return res;
    }
    private void swap() {
        Queue<Integer> tmp = help;
        help = stack;
        stack = tmp;
    }
    public Integer peek() {
        if (stack.isEmpty()) {
            System.out.println("stack is empty!");
            return null;
        }
        while (stack.size() > 1) {
            help.offer(stack.poll());
        }
        int res = stack.poll();
        // peek 不删除，需加上res
        help.offer(res);
        swap();
        return res;
    }
}

猫狗队列

public class Pet {
    private String type;
    public Pet(String type) {
        this.type = type;
    }
    public String getPetType() {
        return this.type;
    }
}
public class Dog extends Pet {
    public Dog() {
        super("dog");
    }
}
public class Cat extends Pet {
    public Cat() {
        super("cat");
    }
}

实现一种狗猫队列的结构，

要求

用户可以调用add方法将cat类或dog类的实例放入队列中；
用户可以调用pollAll方法，将队列中所有的实例按照进队列的先后顺序依次弹出；
用户可以调用pollDog方法，将队列中dog类的实例按照进队列的先后顺序依次弹出；
用户可以调用pollCat方法，将队列中cat类的实例按照进队列的先后顺序依次弹出；
用户可以调用isEmpty方法，检查队列中是
否还有dog或cat的实例；
用户可以调用isDogEmpty方法，检查队列中是否有dog类的实例；
用户可以调用isCatEmpty方法，检查队列中是否有cat类的实例。

package com.jelly.algorithm.queue;
import java.util.LinkedList;
import java.util.Queue;
public class CatDogQueue {
    private Queue<PetEntity> catQ;
    private Queue<PetEntity> dogQ;
    private Long count;
    public CatDogQueue() {
        this.catQ = new LinkedList<>();
        this.dogQ = new LinkedList<>();
        this.count = 0L;
    }
    public boolean add(Pet pet) {
        if (pet.getPetType().equals("cat")) {
            catQ.add(new PetEntity(pet, this.count++));
            return true;
        } else if (pet.getPetType().equals("dog")) {
            dogQ.add(new PetEntity(pet, this.count++));
            return true;
        } else {
            throw new IllegalArgumentException("NOT cat or dog!");
        }
    }
    public Pet pollAll() {
        if (!catQ.isEmpty() && !dogQ.isEmpty()) {
            if (catQ.peek().getCount() < dogQ.peek().getCount()) {
                return catQ.poll().getPet();
            } else {
                return dogQ.poll().getPet();
            }
        } else if (!catQ.isEmpty()) {
            return catQ.poll().getPet();
        } else if (!dogQ.isEmpty()) {
            return dogQ.poll().getPet();
        } else {
            throw new RuntimeException("queue is empty!");
        }
    }
    public Cat pollCat() {
        if (catQ.isEmpty()) {
            throw new RuntimeException("queue is empty!");
        }
        return (Cat) catQ.poll().getPet();
    }
    public Dog pollDog() {
        if (dogQ.isEmpty()) {
            throw new RuntimeException("queue is empty!");
        }
        return (Dog) dogQ.poll().getPet();
    }
    public boolean isEmpty() {
        return catQ.isEmpty() && dogQ.isEmpty();
    }
    public boolean isCatQueueEmpty() {
        return catQ.isEmpty();
    }
    public boolean isDogQueueEmpty() {
        return dogQ.isEmpty();
    }
    
    public static void main(String[] args) {
        CatDogQueue test = new CatDogQueue();
        Pet dog1 = new Dog();
        Pet cat1 = new Cat();
        Pet dog2 = new Dog();
        Pet cat2 = new Cat();
        Pet dog3 = new Dog();
        Pet cat3 = new Cat();
        test.add(dog1);
        test.add(cat1);
        test.add(dog2);
        test.add(cat2);
        test.add(dog3);
        test.add(cat3);
        test.add(dog1);
        test.add(cat1);
        test.add(dog2);
        test.add(cat2);
        test.add(dog3);
        test.add(cat3);
        test.add(dog1);
        test.add(cat1);
        test.add(dog2);
        test.add(cat2);
        test.add(dog3);
        test.add(cat3);
        while (!test.isDogQueueEmpty()) {
            System.out.println(test.pollDog().getPetType());
        }
        while (!test.isEmpty()) {
            System.out.println(test.pollAll().getPetType());
        }
    }
}
class Pet {
    private String type;
    public Pet(String type) {
        this.type = type;
    }
    public String getPetType() {
        return this.type;
    }
}
class Dog extends Pet {
    public Dog() {
        super("dog");
    }
}
class Cat extends Pet {
    public Cat() {
        super("cat");
    }
}
class PetEntity {
    private Pet pet;
    private Long count;
    public PetEntity(Pet pet, Long count) {
        this.pet = pet;
        this.count = count;
    }
    public Pet getPet() {
        return pet;
    }
    public Long getCount() {
        return count;
    }
}

矩阵

转圈打印矩阵

给定一个整型矩阵matrix，请按照转圈的方式打印它。

例如：
1   2   3   4
5   6   7   8
9  10  11  12
13 14  15  16 
打印结果为： 
1，2，3，4，8，12，16，15，14，13，9，5，6，7，11，10

要求

额外空间复杂度为O(1)。

package com.jelly.algorithm.matrix;
public class RotateMatrix {
    public static void main(String[] args) {
        int[][] matrix = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}, {13, 14, 15, 16}};
        int[][] matrix1 = {{3, 4, 5, 8, 0}};
        rotate(matrix);
    }
    /**
     * 旋转打印
     * 每次层数减一，像剥洋葱一样，一次一层。
     *
     * @param matrix 矩阵
     */
    public static void spiralOrderPrint(int[][] matrix) {
        int ar = 0;
        int ac = 0;
        int br = matrix.length - 1;
        int bc = matrix[0].length - 1;
        while (ar <= br && ac <= bc) {
            printEdge(matrix, ar++, ac++, br--, bc--);
        }
    }
    /**
     * 顺时针打印矩阵的环
     *
     * @param matrix 待打印的矩阵
     * @param ar     左上角行数
     * @param ac     左上角列数
     * @param br     右下角行数
     * @param bc     右下角列数
     */
    private static void printEdge(int[][] matrix, int ar, int ac, int br, int bc) {
        if (ar == br) {
            // 只有一行
            for (int i = ac; i <= bc; i++) {
                System.out.print(matrix[ar][i] + " ");
            }
        } else if (ac == bc) {
            // 只有一列
            for (int i = ar; i <= br; i++) {
                System.out.print(matrix[i][ac] + " ");
            }
        } else {
            int curR = ar;
            int curC = ac;
            while (curC < bc) {
                System.out.print(matrix[curR][curC++] + " ");
            }
            while (curR < br) {
                System.out.print(matrix[curR++][curC] + " ");
            }
            while (curC > ac) {
                System.out.print(matrix[curR][curC--] + " ");
            }
            while (curR > ar) {
                System.out.print(matrix[curR--][curC] + " ");
            }
        }
    }
}

旋转正方形矩阵

给定一个整型正方形矩阵matrix，请把该矩阵调整成
顺时针旋转90度的样子。

要求

额外空间复杂度为O(1)。

package com.jelly.algorithm.matrix;
/**
 * 旋转正方形矩阵
 */
public class RotateMatrix {
    public static void main(String[] args) {
        int[][] matrix = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}, {13, 14, 15, 16}};
        printMatrix(matrix);
        rotate(matrix);
        System.out.println("=======================");
        printMatrix(matrix);
    }
    /**
     * 顺时针旋转矩阵
     *
     * @param matrix 矩阵
     */
    private static void rotate(int[][] matrix) {
        int ar = 0;
        int ac = 0;
        int br = matrix.length - 1;
        int bc = matrix[0].length - 1;
        while (ar < br) {
            rotateEdge(matrix, ar++, ac++, br--, bc--);
        }
    }
    /**
     * 转动矩阵边缘
     *
     * @param matrix 待转动的矩阵
     * @param ar     矩阵左上角行。
     * @param ac     矩阵左上角列。
     * @param br     矩阵右下角行。
     * @param bc     矩阵右下角列。
     */
    private static void rotateEdge(int[][] matrix, int ar, int ac, int br, int bc) {
        int times = bc - ac;
        int tmp = 0;
        for (int i = 0; i < times; i++) {
            tmp = matrix[ar][ac + i];
            matrix[ar][ac + i] = matrix[br - i][ac];
            matrix[br - i][ac] = matrix[br][bc - i];
            matrix[br][bc - i] = matrix[ar + i][bc];
            matrix[ar + i][bc] = tmp;
        }
    }
    /**
     * 打印矩阵当前状态
     *
     * @param matrix 矩阵
     */
    public static void printMatrix(int[][] matrix) {
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                System.out.print(matrix[i][j] + " ");
            }
            System.out.println();
        }
    }
}

反转单向和双向链表

分别实现反转单向链表和反转双向链表的函数。

要求

如果链表长度为N，时间复杂度要求为O(N)，额外空间复杂度要求为O(1)

public static class Node {                 
    public int value;                      
    public Node next;                      
                                           
    public Node(int data) {                
        this.value = data;                 
    }                                      
}                                          
                                           
public static Node reverseList(Node head) {
    Node pre = null;                       
    Node next = null;                      
    while (head != null) {                 
        next = head.next;                  
        head.next = pre;                   
        pre = head;                        
        head = next;                       
    }                                      
    return pre;                            
}

“之” 字形打印矩阵

给定一个矩阵matrix，按照“之” 字形的方式打印这
个矩阵，

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

“之” 字形打印的结果为： 1， 2， 5， 9， 6， 3， 4， 7， 10， 11，8， 12

要求

额外空间复杂度为O(1)

package com.jelly.algorithm.matrix;
public class PrintMatrixZig {
    public static void printMatrixZigZag(int[][] matrix) {
        int ar = 0, ac = 0;
        int br = 0, bc = 0;
        int endR = matrix.length - 1;
        int endC = matrix[0].length - 1;
        boolean fromUp = false;
        while (br <= endR) {
            printSlash(matrix, ar, ac, br, bc, fromUp);
            // 下面四个顺序很重要，修改判断条件的操作放在后边
            ac = ar == endR ? ac + 1 : ac;
            ar = ar == endR ? ar : ar + 1;
            br = bc == endC ? br + 1 : br;
            bc = bc == endC ? bc : bc + 1;
            fromUp = !fromUp;
        }
    }
    /**
     * 打印斜线
     *
     * @param matrix 二维数组
     * @param ar     a点横坐标
     * @param ac     a点纵坐标
     * @param br     b点横坐标
     * @param bc     b点纵坐标
     * @param f      是否为从上到下
     */
    private static void printSlash(int[][] matrix, int ar, int ac, int br, int bc, boolean f) {
        if (f) {
            while (ar >= br) {
                System.out.print(matrix[br++][bc--] + " ");
            }
        } else {
            while (ar >= br) {
                System.out.print(matrix[ar--][ac++] + " ");
            }
        }
    }
    public static void main(String[] args) {
        int[][] matrix = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}, {13, 14, 15, 16}};
        printMatrixZigZag(matrix);
    }
}

在行列都排好序的矩阵中找数

给定一个有N*M的整型矩阵matrix和一个整数K，
matrix的每一行和每一列都是排好序的。实现一个函数，判断K
是否在matrix中。

例如： 0 1 2 5 2 3 4 7 4
4 4 8 5 7 7 9 如果K为7，返回true；如果K为6，返回false。

要求

时间复杂度为O(N+M)，额外空间复杂度为O(1)。

package com.jelly.algorithm.matrix;
public class FindNumInSortedMatrix {
    public static void main(String[] args) {
        int[][] matrix = new int[][]{{0, 1, 2, 3, 4, 5, 6},// 0
                {10, 12, 13, 15, 16, 17, 18},// 1
                {23, 24, 25, 26, 27, 28, 29},// 2
                {44, 45, 46, 47, 48, 49, 50},// 3
                {65, 66, 67, 68, 69, 70, 71},// 4
                {96, 97, 98, 99, 100, 111, 122},// 5
                {166, 176, 186, 187, 190, 195, 200},// 6
                {233, 243, 321, 341, 356, 370, 380} // 7
        };
        int K = 233;
        System.out.println(isContains(matrix, K));
    }
    /**
     * 查找思路，从右上角进行查找
     *
     * @param matrix 矩阵
     * @param k      查找的key
     * @return Boolean
     */
    private static boolean isContains(int[][] matrix, int k) {
        int r = 0;
        int c = matrix[0].length - 1;
        // 行要小于矩阵的行数。列要大于-1.
        while (r < matrix.length && c > -1) {
            if (matrix[r][c] == k) {
                return true;
            } else if (matrix[r][c] > k) {
                c--;
            } else {
                r++;
            }
        }
        return false;
    }
}

链表

打印两个有序链表的公共节点

给定两个有序链表的头指针head1和head2，打印两
链表的公共节点

package com.jelly.algorithm.list.s;
import com.jelly.algorithm.list.ListNode;
/**
 * 打印两个有序链表的公共节点
 */
public class PrintCommonPart {
    public static void printCommonPart(ListNode head1, ListNode head2) {
        while (head1 != null && head2 != null) {
            if (head1.val < head2.val) {
                head1 = head1.next;
            } else if (head1.val > head2.val) {
                head2 = head2.next;
            } else {
                System.out.print(head1.val + " ");
                head1 = head1.next;
                head2 = head2.next;
            }
        }
    }
    private static void printLinkedList(ListNode node) {
        System.out.println("node: ");
        while (node != null) {
            System.out.print(node.val + " ");
            node = node.next;
        }
        System.out.println();
    }
    public static void main(String[] args) {
        ListNode node1 = new ListNode(2);
        node1.next = new ListNode(3);
        node1.next.next = new ListNode(5);
        node1.next.next.next = new ListNode(6);
        ListNode node2 = new ListNode(1);
        node2.next = new ListNode(2);
        node2.next.next = new ListNode(5);
        node2.next.next.next = new ListNode(7);
        node2.next.next.next.next = new ListNode(8);
        printLinkedList(node1);
        printLinkedList(node2);
        printCommonPart(node1, node2);
    }
}

判断一个链表是否为回文结构

给定一个链表的头节点head，请判断该链表是否为回文结构。

例如：

1->2->1， 返回true。 
1->2->2->1，返回true。
15->6->15， 返回true。 
1->2->3， 返回false。

进阶：如果链表长度为N，时间复杂度达到O(N)，额外空间复杂度达到O(1)。

package com.jelly.algorithm.list.s;
import com.jelly.algorithm.list.ListNode;
import java.util.Stack;
/**
 * @version V1.0
 * @program: study-leetcode
 * @description: 判断链表是否为回文链表
 * @date: 2019-10-27 14:35
 **/
public class IsPalindrome {
    // need n extra space
    public static boolean isPalindrome1(ListNode head) {
        Stack<ListNode> stack = new Stack<ListNode>();
        ListNode cur = head;
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }
        while (head != null) {
            if (head.val != stack.pop().val) {
                return false;
            }
            head = head.next;
        }
        return true;
    }
    // need n/2 extra space
    public static boolean isPalindrome2(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }
        ListNode right = head.next;
        ListNode cur = head;
        while (cur.next != null && cur.next.next != null) {
            right = right.next;
            cur = cur.next.next;
        }
        Stack<ListNode> stack = new Stack<ListNode>();
        while (right != null) {
            stack.push(right);
            right = right.next;
        }
        while (!stack.isEmpty()) {
            if (head.val != stack.pop().val) {
                return false;
            }
            head = head.next;
        }
        return true;
    }
    // need O(1) extra space
    public static boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }
        // find mid. n1 point mid after loop
        ListNode n1 = head;
        ListNode n2 = head;
        while (n2.next != null && n2.next.next != null) { // find mid ListNode
            n1 = n1.next;
            n2 = n2.next.next;
        }
        n2 = n1.next; // n2 -> right part first ListNode
        n1.next = null; // mid.next -> null
        // reverse second half
        ListNode n3 = null;
        while (n2 != null) {
            n3 = n2.next;
            n2.next = n1;
            n1 = n2;
            n2 = n3;
        }
        n3 = n1; // n3 -> save last ListNode
        n2 = head;// n2 -> left first ListNode
        // check palindrome
        boolean res = true;
        while (n1 != null && n2 != null) {
            if (n1.val != n2.val) {
                res = false;
                break;
            }
            n1 = n1.next; // left to mid
            n2 = n2.next; // right to mid
        }
        n1 = n3.next;
        n3.next = null;
        // recover list
        while (n1 != null) {
            n2 = n1.next;
            n1.next = n3;
            n3 = n1;
            n1 = n2;
        }
        return res;
    }
    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(3);
        ListNode node6 = new ListNode(2);
        ListNode node7 = new ListNode(1);
        head.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node6;
        node6.next = node7;
        System.out.println(isPalindrome(head));
    }
}

将单向链表按某值划分成左边小、中间相等、右边大的形式

给定一个单向链表的头节点head，节点的值类型是整型，再给定一个整数pivot。

实现一个调整链表的函数，将链表调整为左部分都是值小于 pivot的节点，中间部分都是值等于pivot的节点，右部分都是值大于 pivot的节点。
除这个要求外，对调整后的节点顺序没有更多的要求。

例如： 
链表 9->0->4->5->1， pivot=3。 
调整后链表可以是 1->0->4->9->5，
也可以是0->1->9->5->4。

总之，满足左部分都是小于3的节点，中间部分都是等于3的节点（本例中这个部
分为空），右部分都是大于3的节点即可。对某部分内部的节点顺序不做要求。

进阶：在原问题的要求之上再增加如下两个要求。
在左、中、右三个部分的内部也做顺序要求，要求每部分里的节点从左到右的
顺序与原链表中节点的先后次序一致。例如：链表9->0->4->5->1， pivot=3。
调整后的链表是0->1->9->4->5。在满足原问题要求的同时，左部分节点从左到
右为0、 1。在原链表中也是先出现0，后出现1；中间部分在本例中为空，不再
讨论；右部分节点从左到右为9、 4、 5。在原链表中也是先出现9，然后出现4，
最后出现5。
如果链表长度为N，时间复杂度请达到O(N)，额外空间复杂度请达到O(1)

public static ListNode listPartition2(ListNode head, int pivot) {
    ListNode sH = null; // small head                            
    ListNode sT = null; // small tail                            
    ListNode eH = null; // equal head                            
    ListNode eT = null; // equal tail                            
    ListNode bH = null; // big head                              
    ListNode bT = null; // big tail                              
    ListNode next; // save next node                             
                                                                 
    while (head != null) {                                       
        next = head.next;                                        
        //释放                                                     
        head.next = null;                                        
        if (head.val < pivot) {                                  
            if (sH == null) {                                    
                sH = head;                                       
                sT = head;                                       
            } else {                                             
                sT.next = head;                                  
                sT = head;                                       
            }                                                    
        } else if (head.val > pivot) {                           
            if (eH == null) {                                    
                eH = head;                                       
                eT = head;                                       
            } else {                                             
                eT.next = head;                                  
                eT = head;                                       
            }                                                    
        } else {                                                 
            if (bH == null) {                                    
                bH = head;                                       
                bT = head;                                       
            } else {                                             
                bT.next = head;                                  
                bT = head;                                       
            }                                                    
        }                                                        
        head = next;                                             
    }                                                            
    // small and equal reconnect                                 
    if (sT != null) {                                            
        sT.next = eH;                                            
        eT = eT == null ? sT : eT;                               
    }                                                            
    // all reconnect                                             
    if (eT != null) {                                            
        eT.next = bH;                                            
    }                                                            
    return sH != null ? sH : eH != null ? eH : bH;               
}

复制含有随机指针节点的链表

一种特殊的链表节点类描述如下：

public class Node { 
    public int value; 
    public Node next; 
    public Node rand;
    public Node(int data) { 
        this.value = data; 
    }
}

Node类中的value是节点值,next指针和正常单链表中next指针的意义一样，都指向下一个节点，rand指针是Node类中新增的指针,这个指针可能指向链表中的任意一个节点，也可能指向null。

给定一个由Node节点类型组成的无环单链表的头节点head，请实现一个函数完成这个链表中所有结构的复制，并返回复制的新链表的头节点。

进阶：不使用额外的数据结构，只用有限几个变量，且在时间复杂度为O(N)内完成原问题要实现的函数

package com.jelly.algorithm.list.m;
import java.util.HashMap;
public class CopyListWithRandom {
    public static class Node {
        public int value;
        public Node next;
        public Node rand;
        public Node(int data) {
            this.value = data;
        }
    }
    /**
     * 将节点拷贝到map中，利用map获取源节点的next、rand指针。
     *
     * @param head 头节点
     */
    public static Node copyListWithRand1(Node head) {
        HashMap<Node, Node> map = new HashMap<Node, Node>();
        Node cur = head;
        while (cur != null) {
            map.put(cur, new Node(cur.value));
            cur = cur.next;
        }
        cur = head;
        while (cur != null) {
            map.get(cur).next = map.get(cur.next);
            map.get(cur).rand = map.get(cur.rand);
            cur = cur.next;
        }
        return map.get(head);
    }
    /**
     * 节点的下一个为其next，让后将所有的拷贝节点提取出来
     *
     * @param head 头指针
     */
    public static Node copyListWithRand2(Node head) {
        if (head == null) {
            return null;
        }
        Node cur = head;
        // copy next
        Node next;
        while (cur != null) {
            next = cur.next;
            cur.next = new Node(cur.value);
            cur.next.next = next;
            cur = next;
        }
        // copy rand
        cur = head;
        while (cur != null) {
            next = cur.next.next;
            cur.next.rand = cur.rand == null ? null : cur.rand.next;
            cur = next;
        }
        // split
        Node res = head.next;
        Node curCopy;
        cur = head;
        while (cur != null) {
            next = cur.next.next;
            curCopy = cur.next;
            cur.next = next;
            curCopy.next = next != null ? next.next : null;
            cur = next;
        }
        return res;
    }
    public static void printRandLinkedList(Node head) {
        Node cur = head;
        System.out.print("order: ");
        while (cur != null) {
            System.out.print(cur.value + " ");
            cur = cur.next;
        }
        System.out.println();
        cur = head;
        System.out.print("rand:  ");
        while (cur != null) {
            System.out.print(cur.rand == null ? "- " : cur.rand.value + " ");
            cur = cur.next;
        }
        System.out.println();
    }
    public static void main(String[] args) {
        Node head = null;
        Node res1 = null;
        Node res2 = null;
        head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);
        head.next.next.next = new Node(4);
        head.next.next.next.next = new Node(5);
        head.next.next.next.next.next = new Node(6);
        head.rand = head.next.next.next.next.next; // 1 -> 6
        head.next.rand = head.next.next.next.next.next; // 2 -> 6
        head.next.next.rand = head.next.next.next.next; // 3 -> 5
        head.next.next.next.rand = head.next.next; // 4 -> 3
        head.next.next.next.next.rand = null; // 5 -> null
        head.next.next.next.next.next.rand = head.next.next.next; // 6 -> 4
        System.out.println("head");
        printRandLinkedList(head);
        System.out.println("Rand1");
        res1 = copyListWithRand1(head);
        printRandLinkedList(res1);
        System.out.println("Rand2");
        res2 = copyListWithRand2(head);
        printRandLinkedList(res2);
        System.out.println("head");
        printRandLinkedList(head);
    }
}

两个单链表相交的一系列问题

单链表可能有环，也可能无环。给定两个单链表的头节点 head1和head2，这两个链表可能相交，也可能不相交。

请实现一个函数，

如果两个链表相交，请返回相交的第一个节点；
如果不相交，返回null 即可。

要求：如果链表1 的长度为N，链表2的长度为M，时间复杂度请达到 O(N+M)，额外空间复杂度请达到O(1)

可能情况

package com.jelly.algorithm.list.m;
import com.jelly.algorithm.list.ListNode;
/**
 * 寻找两个链表交点
 */
public class FindFirstIntersectNode {
    public static ListNode getIntersectNode(ListNode head1, ListNode head2) {
        if (head1 == null || head2 == null) {
            return null;
        }
        ListNode loop1 = getLoopNode(head1);
        ListNode loop2 = getLoopNode(head2);
        //both no loop
        if (loop1 == null && loop2 == null) {
            return noLoop(head1, head2);
        }
        //both has loop
        if (loop1 != null && loop2 != null) {
            return bothLoop(head1, loop1, head2, loop2);
        }
        //one has loop the other has no loop. don't intersect.
        return null;
    }
    /**
     * Get the entry node of the ring
     */
    public static ListNode getLoopNode(ListNode head) {
        if (head == null || head.next == null || head.next.next == null) {
            return null;
        }
        ListNode n1 = head.next; // n1 -> slow
        ListNode n2 = head.next.next; // n2 -> fast
        while (n1 != n2) {
            if (n2.next == null || n2.next.next == null) {
                return null;
            }
            n2 = n2.next.next;
            n1 = n1.next;
        }
        n2 = head; // n2 -> walk again from head
        while (n1 != n2) {
            n1 = n1.next;
            n2 = n2.next;
        }
        return n1;
    }
    /**
     * two no loop list
     */
    public static ListNode noLoop(ListNode head1, ListNode head2) {
        if (head1 == null || head2 == null) {
            return null;
        }
        ListNode cur1 = head1;
        ListNode cur2 = head2;
        int n = 0;
        while (cur1.next != null) {
            n++;
            cur1 = cur1.next;
        }
        while (cur2.next != null) {
            n--;
            cur2 = cur2.next;
        }
        // end different
        if (cur1 != cur2) {
            return null;
        }
        // cur1 is longer. 
        cur1 = n > 0 ? head1 : head2;
        cur2 = cur1 == head1 ? head2 : head1;
        n = Math.abs(n);
        while (n != 0) {
            n--;
            cur1 = cur1.next;
        }
        while (cur1 != cur2) {
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        return cur1;
    }
    /**
     * both has loop
     */
    public static ListNode bothLoop(ListNode head1, ListNode loop1, ListNode head2, ListNode loop2) {
        ListNode cur1 = null;
        ListNode cur2 = null;
        // 入口节点相同
        if (loop1 == loop2) {
            cur1 = head1;
            cur2 = head2;
            int n = 0;
            while (cur1 != loop1) {
                n++;
                cur1 = cur1.next;
            }
            while (cur2 != loop2) {
                n--;
                cur2 = cur2.next;
            }
            // cur1 is longer
            cur1 = n > 0 ? head1 : head2;
            cur2 = cur1 == head1 ? head2 : head1;
            n = Math.abs(n);
            while (n != 0) {
                n--;
                cur1 = cur1.next;
            }
            while (cur1 != cur2) {
                cur1 = cur1.next;
                cur2 = cur2.next;
            }
            return cur1;
        } else {
            //入口节点不同
            cur1 = loop1.next;
            while (cur1 != loop1) {
                if (cur1 == loop2) {
                    return loop1;
                }
                cur1 = cur1.next;
            }
            return null;
        }
    }
    public static void main(String[] args) {
        // 1->2->3->4->5->6->7->null
        ListNode head1 = new ListNode(1);
        head1.next = new ListNode(2);
        head1.next.next = new ListNode(3);
        head1.next.next.next = new ListNode(4);
        head1.next.next.next.next = new ListNode(5);
        head1.next.next.next.next.next = new ListNode(6);
        head1.next.next.next.next.next.next = new ListNode(7);
        // 0->9->8->6->7->null
        ListNode head2 = new ListNode(0);
        head2.next = new ListNode(9);
        head2.next.next = new ListNode(8);
        head2.next.next.next = head1.next.next.next.next.next; // 8->6
        System.out.println(getIntersectNode(head1, head2).val);
        // 1->2->3->4->5->6->7->4...
        head1 = new ListNode(1);
        head1.next = new ListNode(2);
        head1.next.next = new ListNode(3);
        head1.next.next.next = new ListNode(4);
        head1.next.next.next.next = new ListNode(5);
        head1.next.next.next.next.next = new ListNode(6);
        head1.next.next.next.next.next.next = new ListNode(7);
        head1.next.next.next.next.next.next = head1.next.next.next; // 7->4
        // 0->9->8->2...
        head2 = new ListNode(0);
        head2.next = new ListNode(9);
        head2.next.next = new ListNode(8);
        head2.next.next.next = head1.next; // 8->2
        System.out.println(getIntersectNode(head1, head2).val);
        // 0->9->8->6->4->5->6..
        head2 = new ListNode(0);
        head2.next = new ListNode(9);
        head2.next.next = new ListNode(8);
        head2.next.next.next = head1.next.next.next.next.next; // 8->6
        System.out.println(getIntersectNode(head1, head2).val);
    }
}

二叉树

在二叉树中找到一个节点的后继节点

现在有一种新的二叉树节点类型如下：

public class Node { 
    public int value; 
    public Node left;
    public Node right; 
    public Node parent;
    public Node(int data) { 
        this.value = data; 
    }
}

该结构比普通二叉树节点结构多了一个指向父节点的parent指针。

假设有一棵Node类型的节点组成的二叉树，树中每个节点的parent指针都正确地指向自己的父节点，头节点的parent指向null。只给一个在二叉树中的某个节点 node，请实现返回node的后继节点的函数。在二
叉树的中序遍历的序列中，node的下一个节点叫作node的后继节点.

中序遍历左、根、右

public static Node getSuccessorNode(Node node) {
	if (node == null) {
		return node;
	}
	//右节点不为空时，下一个节点为右节点的最左节点
	if (node.right != null) {
		return getLeftMost(node.right);
	} else {
	//右节点为空，当前是左子节点，返回其父节点，否则找到祖父节点返回
		Node parent = node.parent;
		while (parent != null && parent.left != node) {
			node = parent;
			parent = node.parent;
		}
		return parent;
	}
}
public static Node getLeftMost(Node node) {
	if (node == null) {
		return node;
	}
	while (node.left != null) {
		node = node.left;
	}
	return node;
}

判断一棵二叉树是否是平衡二叉树

// 检验是否是平衡树
public boolean isBalanced(TreeNode root) {
    return process(root) != -1;
}
private int process(TreeNode root) {
    if (root == null) {
        return 0;
    }
    int left = process(root.left);
    if (left == -1) {
        return -1;
    }
    int right = process(root.right);
    if (right == -1) {
        return -1;
    }
    return Math.abs(left - right) > 1 ? -1 : Math.max(left, right) + 1;
}

判断一棵树是否是搜索二叉树、

// 校验是否是平衡二叉搜索树.中序遍历，递增
public boolean isValidBST(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    middleOrder(root, res);
    for (int i = 1; i < res.size(); i++) {
        if (res.get(i - 1) > res.get(i)) {
            return false;
        }
    }
    return true;
}
private void middleOrder(TreeNode root, List<Integer> res) {
    if (root == null) {
        return;
    }
    middleOrder(root.left, res);
    res.add(root.val);
    middleOrder(root.right, res);
}

判断一棵树是否是完全二叉树

public static boolean isCBT(Node head) {
	if (head == null) {
		return true;
	}
	Queue<Node> queue = new LinkedList<Node>();
	boolean leaf = false;
	Node l = null;
	Node r = null;
	queue.offer(head);
	while (!queue.isEmpty()) {
		head = queue.poll();
		l = head.left;
		r = head.right;
		// leaf为true后，左右节点均为空
		// 左节点为空，右节点必须为空
		if ((leaf && (l != null || r != null)) || (l == null && r != null)) {
			return false;
		}
	    if (l != null) {
			queue.offer(l);
		}
		// 右节点为空，leaf标记为true
		if (r != null) {
			queue.offer(r);
		} else {
			leaf = true;
		}
	}
    return true;
}

已知一棵完全二叉树，求其节点的个数

要求：时间复杂度低于O(N)， N为这棵树的节点个数

public static int nodeNum(Node head) {
	if (head == null) {
		return 0;
	}
	return bs(head, 1, mostLeftLevel(head, 1));
}
public static int bs(Node node, int l, int h) {
    // leval 和 height相同时，返回1
	if (l == h) {
		return 1;
	}
	// 右子树高度和完全二叉树高度相等，说明，左树为满树
	// 2^(h-l) 个 + 右子树节点个数
	if (mostLeftLevel(node.right, l + 1) == h) {
		return (1 << (h - l)) + bs(node.right, l + 1, h);
	} else {
	    // 右树层数小1，+ 加上左子树节点个数 
		return (1 << (h - l - 1)) + bs(node.left, l + 1, h);
	}
}
public static int mostLeftLevel(Node node, int level) {
	while (node != null) {
		level++;
		node = node.left;
	}
	return level - 1;
}

折纸问题

请把一段纸条竖着放在桌子上，然后从纸条的下边向
上方对折1次，压出折痕后展开。此时折痕是凹下去的，即折痕
突起的方向指向纸条的背面。如果从纸条的下边向上方连续对折
2 次，压出折痕后展开，此时有三条折痕，从上到下依次是下折
痕、下折痕和上折痕。
给定一个输入参数N，代表纸条都从下边向上方连续对折N次，
请从上到下打印所有折痕的方向。例如： N=1时，打印： down
N=2时，打印： down down up

类似二叉树：

右、中、左的遍历顺序。
            下
        上      下
      上  下  上  下

public static void printAllFolds(int N) {
	printProcess(1, N, true);
}
public static void printProcess(int i, int N, boolean down) {
	if (i > N) {
		return;
	}
	printProcess(i + 1, N, true);
	System.out.println(down ? "down " : "up ");
	printProcess(i + 1, N, false);
}

布隆过滤器

bit数组大小：m= - n * ln(p) / (ln2)^2
n: 样本量
p: 0.0001 预期失误率
哈希函数个数：k = ln2 * m / n = 0.7 * m/n
真实失误率：（1-e^(-n*k/m) )^k

URL筛选

不安全网页的黑名单包含100亿个黑名单网页，每个网页的URL最多占用64B，现在要实现一个网页过滤系统，根据网页的URL判断该网页是否在黑名单上。

要求

允许一定的判断失误率
空间内存限制在30GB以内

如果是直接用哈希函数处理，肯定会长处空间限制，所以这里要用到的是布隆过滤器。

布隆过滤器实际上是一个位图bitMap，我们现在假设有一个长度为m的bit类型的数组，以及 k 个互相独立的优秀的哈希函数，且这k个哈希函数的输出域都大于或等于m。

我们将网页的URL作为k个哈希函数的输入对象进行哈希处理，分别得到 k 个值，这k个值中可能有相同的，但是值之间互相独立不关联的。我们将这k个值对m模运算，得到的 k 个值都在 0~m之间。最后将这 k 个值对应的bitMap的值置为1，当我们将所有的URL都处理完毕后，bitMap上的很多位都被置为了1。

当我们要查询一个URL是否在黑名单内时，我们先将这个URL进行哈希处理 ，因为有K个函数所以得到 k 个值。接着检查这 k 个值对应的bitMap 位是否为1，如果有一个不为 1，那么说明这个URL不在这个这里面，是安全的网站，如果对应的 bitMap 位的值都是 1 那么说明这个URL可能在这里面。说明可能是因为当URL的数量很多时，可能会出现不同URL哈希处理后得到相同的值，所以说是有可能在这里面。

一致性哈希

所有机器经过hash后，按照顺序排序。分担所有hash的数据。

新机器加入：新机器按照其hash分布到所有的hash环上，该点到下一点的数据拷贝到新机器上即可。

旧机器删除：删除该机器，该点管控数据，拷贝给他相邻节点。

问题

机器必须达到一定数量，否则数据可能分布严重不均。

解决办法

每个物理机增加一定数量的虚拟节点，均分整个hash环，根据虚拟节点的数量将数据划分给特定的宿主机存储。

岛问题

一个矩阵中只有0和1两种值，每个位置都可以和自己的上、下、左、右四个位置相连，如果有一片1连在一起，这个部分叫做一个岛，求一个矩阵中有多少个岛？
举例：
0 0 1 0 1 0 1 1 1 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0
这个矩阵中有三个岛

public static int countIslands(int[][] m) {
	if (m == null || m[0] == null) {
		return 0;
	}
	int N = m.length;
	int M = m[0].length;
	int res = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (m[i][j] == 1) {
				res++;
				infect(m, i, j, N, M);
			}
		}
	}
	return res;
}
public static void infect(int[][] m, int i, int j, int N, int M) {
	if (i < 0 || i >= N || j < 0 || j >= M || m[i][j] != 1) {
		return;
	}
	m[i][j] = 2;
	infect(m, i + 1, j, N, M);
	infect(m, i - 1, j, N, M);
	infect(m, i, j + 1, N, M);
	infect(m, i, j - 1, N, M);
}
public static void main(String[] args) {
	int[][] m1 = {  { 0, 0, 0, 0, 0, 0, 0, 0, 0 }, 
			        { 0, 1, 1, 1, 0, 1, 1, 1, 0 }, 
			        { 0, 1, 1, 1, 0, 0, 0, 1, 0 },
			        { 0, 1, 1, 0, 0, 0, 0, 0, 0 }, 
			        { 0, 0, 0, 0, 0, 1, 1, 0, 0 }, 
			        { 0, 0, 0, 0, 1, 1, 1, 0, 0 },
			        { 0, 0, 0, 0, 0, 0, 0, 0, 0 }, };
	System.out.println(countIslands(m1));
	int[][] m2 = {  { 0, 0, 0, 0, 0, 0, 0, 0, 0 }, 
					{ 0, 1, 1, 1, 1, 1, 1, 1, 0 }, 
					{ 0, 1, 1, 1, 0, 0, 0, 1, 0 },
					{ 0, 1, 1, 0, 0, 0, 1, 1, 0 }, 
					{ 0, 0, 0, 0, 0, 1, 1, 0, 0 }, 
					{ 0, 0, 0, 0, 1, 1, 1, 0, 0 },
					{ 0, 0, 0, 0, 0, 0, 0, 0, 0 }, };
	System.out.println(countIslands(m2));
}

并查集

一种结构，主要提供两种功能

两个集合是否属于一个集合
合并两个集合

public static class UnionFindSet {
	// k：当前节点，v：父节点
	public HashMap<Node, Node> fatherMap;
	// k：当前节点，v：当前节点所代表的集合中有多少其他节点
	public HashMap<Node, Integer> sizeMap;
    // 构造函数，必须一次给定所有的节点
	public UnionFindSet(List<Node> nodes) {
		makeSets(nodes);
	}
    // 初始化所有节点，初始化时所有节点指向自己，size为 1
	private void makeSets(List<Node> nodes) {
		fatherMap = new HashMap<Node, Node>();
		sizeMap = new HashMap<Node, Integer>();
		for (Node node : nodes) {
			fatherMap.put(node, node);
			sizeMap.put(node, 1);
		}
	}
    // 递归找到node的父节点
    // 然后并将查找路径上的节点，挂在代表节点下
	private Node findHead(Node node) {
		Node father = fatherMap.get(node);
		if (father != node) {
			father = findHead(father);
		}
		fatherMap.put(node, father);
		return father;
	}
	
	// 对外提供的方法，两个节点是否属于同一个集合
	public boolean isSameSet(Node a, Node b) {
		return findHead(a) == findHead(b);
	}
    // 合并两个集合，参数为两个集合的代表节点
	public void union(Node a, Node b) {
		if (a == null || b == null) {
			return;
		}
		Node aHead = findHead(a);
		Node bHead = findHead(b);
		if (aHead != bHead) {
			int aSetSize= sizeMap.get(aHead);
			int bSetSize = sizeMap.get(bHead);
			if (aSetSize <= bSetSize) {
				fatherMap.put(aHead, bHead);
				sizeMap.put(bHead, aSetSize + bSetSize);
			} else {
				fatherMap.put(bHead, aHead);
				sizeMap.put(aHead, aSetSize + bSetSize);
			}
		}
	}
}

前缀树

arr2中有哪些字符，是arr1中出现的？请打印

arr2中有哪些字符，是作为arr1中某个字符串前缀出现的？请打印

arr2中有哪些字符，是作为arr1中某个字符串前缀出现的？请打印 arr2中出现次数最大的前缀。

public static class TrieNode {
	public int path;
	public int end;
	public TrieNode[] nexts;
	public TrieNode() {
		path = 0;
		end = 0;
		nexts = new TrieNode[26];
	}
}
public static class Trie {
	private TrieNode root;
	public Trie() {
		root = new TrieNode();
	}
	public void insert(String word) {
		if (word == null) {
			return;
		}
		char[] chs = word.toCharArray();
		TrieNode node = root;
		int index = 0;
		for (int i = 0; i < chs.length; i++) {
			index = chs[i] - 'a';
			if (node.nexts[index] == null) {
				node.nexts[index] = new TrieNode();
			}
			node = node.nexts[index];
			node.path++;
		}
		node.end++;
	}
	public void delete(String word) {
		if (search(word) != 0) {
			char[] chs = word.toCharArray();
			TrieNode node = root;
			int index = 0;
			for (int i = 0; i < chs.length; i++) {
				index = chs[i] - 'a';
				if (--node.nexts[index].path == 0) {
					node.nexts[index] = null;
					return;
				}
				node = node.nexts[index];
			}
			node.end--;
		}
	}
	public int search(String word) {
		if (word == null) {
			return 0;
		}
		char[] chs = word.toCharArray();
		TrieNode node = root;
		int index = 0;
		for (int i = 0; i < chs.length; i++) {
			index = chs[i] - 'a';
			if (node.nexts[index] == null) {
				return 0;
			}
			node = node.nexts[index];
		}
		return node.end;
	}
	public int prefixNumber(String pre) {
		if (pre == null) {
			return 0;
		}
		char[] chs = pre.toCharArray();
		TrieNode node = root;
		int index = 0;
		for (int i = 0; i < chs.length; i++) {
			index = chs[i] - 'a';
			if (node.nexts[index] == null) {
				return 0;
			}
			node = node.nexts[index];
		}
		return node.path;
	}
}
public static void main(String[] args) {
	Trie trie = new Trie();
	System.out.println(trie.search("zuo"));
	trie.insert("zuo");
	System.out.println(trie.search("zuo"));
	trie.delete("zuo");
	System.out.println(trie.search("zuo"));
	trie.insert("zuo");
	trie.insert("zuo");
	trie.delete("zuo");
	System.out.println(trie.search("zuo"));
	trie.delete("zuo");
	System.out.println(trie.search("zuo"));
	trie.insert("zuoa");
	trie.insert("zuoac");
	trie.insert("zuoab");
	trie.insert("zuoad");
	trie.delete("zuoa");
	System.out.println(trie.search("zuoa"));
	System.out.println(trie.prefixNumber("zuo"));
}

贪心算法

切金条

一块金条切成两半，是需要花费和长度数值一样的铜板的。比如长度为20的金条，不管切成长度多大的两半，都要花费20个铜板。一群人想整分整块金条，怎么分最省铜板？例如,给定数组{10,20,30}，代表一共三个人，整块金条长度为 10+20+30=60. 金条要分成10,20,30三个部分。如果，先把长度60的金条分成10和50，花费60 再把长度50的金条分成20和30，花费50 一共花费110铜板。但是如果，先把长度60的金条分成30和30，花费60 再把长度30 金条分成10和20，花费30 一共花费90铜板。输入一个数组，返回分割的最小代价。

public static int lessMoney(int[] arr) {
		PriorityQueue<Integer> pQ = new PriorityQueue<>();
		for (int i = 0; i < arr.length; i++) {
			pQ.add(arr[i]);
		}
		int sum = 0;
		int cur = 0;
		while (pQ.size() > 1) {
			cur = pQ.poll() + pQ.poll();
			sum += cur;
			pQ.add(cur);
		}
		return sum;
	}

做项目(IPO)

输入：

参数1，正数数组costs
参数2，正数数组profits
参数3，正数k
参数4，正数m

costs[i]表示i号项目的花费 profits[i]表示i号项目在扣除花费之后还能挣到的钱(利润) k表示你不能并行、只能串行的最多做k个项目 m表示你初始的资金说明：你每做完一个项目，马上获得的收益，可以支持你去做下一个项目。输出：你最后获得的最大钱数。

构建两个堆：

按照花费构建小根堆，当花费小于当前所有资金时，进入按照收益构建的大根堆，每次大根堆中给的第一个。

public static class Node {
		public int p;
		public int c;
		public Node(int p, int c) {
			this.p = p;
			this.c = c;
		}
	}
	public static class MinCostComparator implements Comparator<Node> {
		@Override
		public int compare(Node o1, Node o2) {
			return o1.c - o2.c;
		}
	}
	public static class MaxProfitComparator implements Comparator<Node> {
		@Override
		public int compare(Node o1, Node o2) {
			return o2.p - o1.p;
		}
	}
	public static int findMaximizedCapital(int k, int W, int[] Profits, int[] Capital) {
		Node[] nodes = new Node[Profits.length];
		for (int i = 0; i < Profits.length; i++) {
			nodes[i] = new Node(Profits[i], Capital[i]);
		}
		PriorityQueue<Node> minCostQ = new PriorityQueue<>(new MinCostComparator());
		PriorityQueue<Node> maxProfitQ = new PriorityQueue<>(new MaxProfitComparator());
		for (int i = 0; i < nodes.length; i++) {
			minCostQ.add(nodes[i]);
		}
		for (int i = 0; i < k; i++) {
			while (!minCostQ.isEmpty() && minCostQ.peek().c <= W) {
				maxProfitQ.add(minCostQ.poll());
			}
			if (maxProfitQ.isEmpty()) {
				return W;
			}
			W += maxProfitQ.poll().p;
		}
		return W;
	}

一个数据流中，随时可以取得中位数

最低字典序

给定一个字符串类型的数组strs，找到一种拼接方式，使得把所有字符串拼起来之后形成的字符串具有最低的字典序。

注意：

不能直接按照字典序比较，如 ba、b 直接按照字典序比较 ba > b 拼接字符串 bba，但是bab更小。

public static class MyComparator implements Comparator<String> {
	@Override
	public int compare(String a, String b) {
	    // 直接按照字典序比较是错误的
		return (a + b).compareTo(b + a);
	}
}
public static String lowestString(String[] strs) {
	if (strs == null || strs.length == 0) {
		return "";
	}
	Arrays.sort(strs, new MyComparator());
	String res = "";
	for (int i = 0; i < strs.length; i++) {
		res += strs[i];
	}
	return res;
}
public static void main(String[] args) {
	String[] strs1 = { "jibw", "ji", "jp", "bw", "jibw" };
	System.out.println(lowestString(strs1));
	String[] strs2 = { "ba", "b" };
	System.out.println(lowestString(strs2));
}

宣讲会

一些项目要占用一个会议室宣讲，会议室不能同时容纳两个项目的宣讲。给你每一个项目开始的时间和结束的时间(给你一个数组，里面是一个个具体的项目)，你来安排宣讲的日程，要求会议室进行的宣讲的场次最多。返回这个最多的宣讲场次。

按照结束时间排序

public static class Program {
		public int start;
		public int end;
		public Program(int start, int end) {
			this.start = start;
			this.end = end;
		}
	}
	public static class ProgramComparator implements Comparator<Program> {
		@Override
		public int compare(Program o1, Program o2) {
			return o1.end - o2.end;
		}
	}
	public static int bestArrange(Program[] programs, int start) {
		Arrays.sort(programs, new ProgramComparator());
		int result = 0;
		for (int i = 0; i < programs.length; i++) {
			if (start <= programs[i].start) {
				result++;
				start = programs[i].end;
			}
		}
		return result;
	}

–

递归&动态规划

暴力递归：

把问题转化为规模缩小了的同类问题的子问题
有明确的不需要继续进行递归的条件(base case)
有当得到了子问题的结果之后的决策过程
不记录每一个子问题的解

动态规划

从暴力递归中来
将每一个子问题的解记录下来，避免重复计算
把暴力递归的过程，抽象成了状态表达
并且存在化简状态表达，使其更加简洁的可能

求n!的结果

n的阶乘依赖于 n-1 的阶乘， n-1 的阶乘依赖于 n-2 的阶乘……依赖 1 的阶乘。

于是，反过来，可以从 1 的阶乘计算到 n的阶乘

public static long getFactorial1(int n) {
	if (n == 1) {
		return 1L;
	}
	return (long) n * getFactorial1(n - 1);
}
public static long getFactorial2(int n) {
	long result = 1L;
	for (int i = 1; i <= n; i++) {
		result *= i;
	}
	return result;
}
public static void main(String[] args) {
	int n = 5;
    System.out.println(getFactorial1(n));
	System.out.println(getFactorial2(n));
}

汉诺塔问题

三个柱子。from、to、help

抽象问题：

将from 上的 n 个盘子中的 n-1 个移动到 help上
将from 剩余的第 n 个盘子移动到to上
将help 上的n-1 个盘子移动到to上

public static void hanoi(int n) {
	if (n > 0) {
		func(n, n, "left", "mid", "right");
	}
}
public static void func(int rest, int down, String from, String help, String to) {
	if (rest == 1) {
		System.out.println("move " + down + " from " + from + " to " + to);
	} else {
		func(rest - 1, down - 1, from, to, help);
		func(1, down, from, help, to);
		func(rest - 1, down - 1, help, from, to);
	}
}

打印全部子序列

打印一个字符串的全部子序列，包括空字符串

public static void printAllSubsquence(String str) {
	if(str == null|| "".equal(str)){
	    return;
	}
	process(str.toCharArray(), 0 ,"");
}
public static void process(char[] str, int i, String res){
    if(i == str.length){
        System.out.println(res);
        return;
    }
    // 决策：不加当前字符
    process(str, i+1, res);
    // 决策：加当前字符
    process(str, i+1, res+String.valueOf(str[i]));
}

打印全排列

打印一个字符串的全部排列

package com.jelly.algorithm.string;
import java.util.Arrays;
/**
 * 字符串的全排列
 */
public class AllPermutations {
    public static void printAllPermutations(String str) {
        if (str == null || "".equals(str)) {
            return;
        }
        process(str.toCharArray(), 0);
    }
    private static void process(char[] chs, int i) {
        if (i == chs.length) {
            System.out.println(String.valueOf(chs));
        }
        for (int j = i; j < chs.length; j++) {
            process(deepCopyAndSwap(chs, i, j), i + 1);
        }
    }
    private static char[] deepCopyAndSwap(char[] chs, int i, int j) {
        char[] res = Arrays.copyOf(chs, chs.length);
        char tmp = res[i];
        res[i] = res[j];
        res[j] = tmp;
        return res;
    }
    public static void main(String[] args) {
        printAllPermutations("abc");
    }
}

生牛问题

母牛每年生一只母牛，新出生的母牛成长三年后也能每年生一只母牛，假设不会死。求N年后，母牛的数量。

因为题中牛不会死，三年后可以生母牛。那么可以得到递推公式：

1 2	f(n) = f(n-1) + f(n-3) 今年牛数量 = 去年牛数量 + 三年前牛数量(它们将会生小牛)

public static int cowNumber1(int n) {
	if (n < 1) {
		return 0;
	}
	if (n == 1 || n == 2 || n == 3) {
		return n;
	}
	return cowNumber1(n - 1) + cowNumber1(n - 3);
}
public static int cowNumber2(int n) {
	if (n < 1) {
		return 0;
	}
	if (n == 1 || n == 2 || n == 3) {
		return n;
	}
	int res = 3;
	int pre = 2;
	int prepre = 1;
	int tmp1 = 0;
	int tmp2 = 0;
	for (int i = 4; i <= n; i++) {
		tmp1 = res;
		tmp2 = pre;
		
		res = res + prepre;
		
		pre = tmp1;
		prepre = tmp2;
	}
	return res;
}
public static void main(String[] args) {
	int n = 20;
	System.out.println(cowNumber1(n));
	System.out.println(cowNumber2(n));
}

生牛问题(母牛只能活10年)

如果每只母牛只能活10年（先生后死），求N年后，母牛的数量。

1
2

f(n) = f(n-1) + f(n-3) - (f(n-10) - f(n-11))
今年牛数量  = 去年牛数量 + 三年前牛数量(它们将会生小牛) - 十年前出生的小牛(如果是第十年没生小牛就死亡，应减2倍 十年前出生小牛的量)

递归逆序栈

给你一个栈，请你逆序这个栈，不能申请额外的数据结构，只能使用递归函数。如何实现？

package com.jelly.algorithm.stack;
import java.util.Stack;
/**
 * 递归查找栈底元素弹出，然后入栈
 */
public class ReverseStackUsingRecursive {
    public static void reverse(Stack<Integer> stack) {
        if (stack == null || stack.isEmpty()) {
            return;
        }
        int last = getAndRemoveLast(stack);
        reverse(stack);
        stack.push(last);
    }
    private static int getAndRemoveLast(Stack<Integer> stack) {
        Integer pop = stack.pop();
        if (stack.isEmpty()) {
            return pop;
        } else {
            // 弹出的pop不是栈底元素，递归查找，并将pop重新入栈
            int last = getAndRemoveLast(stack);
            stack.push(pop);
            return last;
        }
    }
    public static void main(String[] args) {
        Stack<Integer> stack = initStack();
        reverse(stack);
        printStack(stack);
    }
    // 测试 初始化栈
    private static Stack<Integer> initStack() {
        Stack<Integer> stack = new Stack<>();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        return stack;
    }
    // 测试 打印栈
    private static void printStack(Stack<Integer> stack) {
        while (!stack.isEmpty()) {
            System.out.print(stack.pop() + " ");
        }
    }
}

最小路径

无后效性问题都可以改成动态规划

无后效性，当前选择对后边选择决策无关。当前可变参数确定，最后返回值是确定的。
给你一个二维数组，二维数组中的每个数都是正数，要求从左上角走到右下角，每一步只能向右或者向下。沿途经过的数字要累加起来。返回最小的路径和

public static int minPath1(int[][] matrix) {
	return process1(matrix, matrix.length - 1, matrix[0].length - 1);
}
// 递归版
public static int process1(int[][] matrix, int i, int j) {
	int res = matrix[i][j];
	if (i == 0 && j == 0) {
		return res;
	}
	if (i == 0 && j != 0) {
		return res + process1(matrix, i, j - 1);
	}
	if (i != 0 && j == 0) {
		return res + process1(matrix, i - 1, j);
	}
	return res + Math.min(process1(matrix, i, j - 1), process1(matrix, i - 1, j));
}
// 动态规划版
public static int minPath2(int[][] m) {
	if (m == null || m.length == 0 || m[0] == null || m[0].length == 0) {
		return 0;
	}
	int row = m.length;
	int col = m[0].length;
	int[][] dp = new int[row][col];
	dp[0][0] = m[0][0];
	for (int i = 1; i < row; i++) {
		dp[i][0] = dp[i - 1][0] + m[i][0];
	}
	for (int j = 1; j < col; j++) {
		dp[0][j] = dp[0][j - 1] + m[0][j];
	}
	for (int i = 1; i < row; i++) {
		for (int j = 1; j < col; j++) {
			dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + m[i][j];
		}
	}
	return dp[row - 1][col - 1];
}
	
// for test
public static int[][] generateRandomMatrix(int rowSize, int colSize) {
	if (rowSize < 0 || colSize < 0) {
		return null;
	}
	int[][] result = new int[rowSize][colSize];
	for (int i = 0; i != result.length; i++) {
		for (int j = 0; j != result[0].length; j++) {
			result[i][j] = (int) (Math.random() * 10);
		}
	}
	return result;
}
	
public static void main(String[] args) {
	int[][] m = { { 1, 3, 5, 9 }, { 8, 1, 3, 4 }, { 5, 0, 6, 1 }, { 8, 8, 4, 0 } };
	System.out.println(minPath1(m));
	System.out.println(minPath2(m));
	m = generateRandomMatrix(6, 7);
	System.out.println(minPath1(m));
	System.out.println(minPath2(m));
}

背包问题

给你一个数组arr，和一个整数aim。如果可以任意选择arr中的数字，能不能累加得到aim，返回true或者false

分析

每个位置 i 有要和不要两种选择；叶节点会看自己这里的结果是不是 aim，从而向父结点返回 true 或 false，父结点比较子节点的结果，有一个为 true 就一直返回 true，否则返回 false。

如上图所示：数组 arr = {3, 2, 5} ，aim = 7：

f(0, 0)：代表0位置处状态值为0的点；

f(2, 5)：代表2位置处状态值为5的点。

只要有叶节点的值等于 aim 的值，则会返回 true。

动态规划版图解：

public static boolean money1(int[] arr, int aim) {
	return process(arr, 0, 0, aim);
}
public static boolean process(int[] arr, int i, int sum, int aim) {
	if (sum == aim) {
		return true;
	}
	// sum != aim
	if (i == arr.length) {
		return false;
	}
	return process(arr, i + 1, sum, aim) || process(arr, i + 1, sum + arr[i], aim);
}
// 动态规划版
public static boolean money2(int[] arr, int aim) {
	boolean[][] dp = new boolean[arr.length + 1][aim + 1];
	for (int i = 0; i < dp.length; i++) {
		dp[i][aim] = true;
	}
	for (int i = arr.length - 1; i >= 0; i--) {
		for (int j = aim - 1; j >= 0; j--) {
			dp[i][j] = dp[i + 1][j];
			if (j + arr[i] <= aim) {
				dp[i][j] = dp[i][j] || dp[i + 1][j + arr[i]];
			}
		}
	}
	return dp[0][0];
}
public static void main(String[] args) {
	int[] arr = { 1, 4, 8 };
	int aim = 12;
	System.out.println(money1(arr, aim));
	System.out.println(money2(arr, aim));
}

商品价值

给定两个数组w和v，两个数组长度相等，w[i]表示第i件商品的重量，v[i]表示第i件商品的价值。再给定一个整数bag，要求你挑选商品的重量加起来一定不能超过bag，返回满足这个条件下，你能获得的最大价值。

public static int maxValue1(int[] c, int[] p, int bag) {
	return process1(c, p, 0, 0, bag);
}
public static int process1(int[] weights, int[] values, int i, int alreadyweight, int bag) {
	if (alreadyweight > bag) {
		return 0;
	}
	if (i == weights.length) {
		return 0;
	}
	return Math.max(
			process1(weights, values, i + 1, alreadyweight, bag),
			
			values[i] + process1(weights, values, i + 1, alreadyweight + weights[i], bag)
			);
}
public static int maxValue2(int[] c, int[] p, int bag) {
	int[][] dp = new int[c.length + 1][bag + 1];
	for (int i = c.length - 1; i >= 0; i--) {
		for (int j = bag; j >= 0; j--) {
			dp[i][j] = dp[i + 1][j];
			if (j + c[i] <= bag) {
				dp[i][j] = Math.max(dp[i][j], p[i] + dp[i + 1][j + c[i]]);
			}
		}
	}
	return dp[0][0];
}
public static void main(String[] args) {
	int[] c = { 3, 2, 4, 7 };
	int[] p = { 5, 6, 3, 19 };
	int bag = 11;
	System.out.println(maxValue1(c, p, bag));
	System.out.println(maxValue2(c, p, bag));
}

排序问题

小和问题

逆序对问题

相邻两数的最大差值

栈和队列

数组实现固定大小的队列和栈

实现返回栈中最小元素

要求

如何仅用队列结构实现栈结构？

如何仅用栈结构实现队列结构？

猫狗队列

要求

矩阵

转圈打印矩阵

要求

旋转正方形矩阵

要求

反转单向和双向链表

要求

“之” 字形打印矩阵

要求

在行列都排好序的矩阵中找数

要求

链表

打印两个有序链表的公共节点

判断一个链表是否为回文结构

将单向链表按某值划分成左边小、 中间相等、 右边大的形式

复制含有随机指针节点的链表

两个单链表相交的一系列问题

可能情况

二叉树

在二叉树中找到一个节点的后继节点

判断一棵二叉树是否是平衡二叉树

判断一棵树是否是搜索二叉树、

判断一棵树是否是完全二叉树

已知一棵完全二叉树， 求其节点的个数

折纸问题

布隆过滤器

URL筛选

要求

一致性哈希

问题

解决办法

岛问题

并查集

前缀树

贪心算法

切金条

做项目(IPO)

一个数据流中，随时可以取得中位数

最低字典序

宣讲会

递归&动态规划

求n!的结果

汉诺塔问题

打印全部子序列

打印全排列

生牛问题

生牛问题(母牛只能活10年)

递归逆序栈

最小路径

无后效性问题都可以改成动态规划

背包问题

分析

商品价值

将单向链表按某值划分成左边小、中间相等、右边大的形式

已知一棵完全二叉树，求其节点的个数