面试Tips

	业务为主	技巧为主
笔试	55%	45%	笔试需要淘汰率，更考察经验，笔试卷面分过 35/100
面试	30%	70%	技巧为主反而更考察基础（比如窗口最大值最小值、单调栈、动态规划斜率优化）

算法题模板

注意点：

子串、子数组必须连续，子序列必须连续

Master公式

简介
在编程中，递归是非常常见的一种算法，由于代码简洁而应用广泛，但递归相比顺序执行或循环程序，时间复杂度难以计算，而master公式就是用于计算递归程序的时间复杂度。

公式
T(N) = a * T(N / b) + O(N ^ d)

b：子过程的样本量
a：子过程的计算次数
O(N ^ d)：子结果合并的时间复杂度
满足如上公式的程序都可以根据master公式计算时间复杂度：

log(b，a) > d ：时间复杂度为O(N ^ log(b，a))
log(b，a) = d ：时间复杂度为O(N ^ d * log N)
log(b，a) < d ：时间复杂度为O(N ^ d)

对数器 & 比较器

对数器

public class Comparator {//生成随机数组public static int[] generateRandomArray(int maxSize, int maxValue) {int[] arr = new int[(int) ((maxSize + 1) * Math.random())];for (int i = 0; i < arr.length; i++) {arr[i] = (int) ((maxValue + 1) * Math.random() - (int) ((maxValue + 1) * Math.random()));}return arr;}public static int[] copyArray(int[] arr) {if (arr == null) return null;return Arrays.copyOf(arr, arr.length);}//判断两个数组是否完全相同public static boolean isEquals(int[] arr1, int[] arr2) {if (arr1 == null && arr2 == null) {return true;}if (arr1 == null || arr2 == null) {return false;}if (arr1.length != arr2.length) {return false;}for (int i = 0; i < arr1.length; i++) {if (arr1[i] != arr2[i]) {return false;}}return true;}public static void comparator(){int maxSize = 50;int maxValue = 100;int testTime = 1000;boolean success = true;for (int i = 0; i < testTime; i++) {int[] arr = generateRandomArray(maxSize, maxValue);int[] copy = copyArray(arr);Arrays.sort(copy);//TODO 待定排序策略if (! isEquals(arr, copy)) {success = false;break;}}System.out.println(success == true ? "perfect" : "totally wrong!!!");}public static void main(String[] args) {comparator();}
}

比较器：重载运算符

一些知识

Map.entrySet

java中Map存放的是许多个键值对的数据，而Map.Entry数据类型可以想象成Map中的一个键值对的数据,可以存放一个键与一个值，显然一个Map对象可以看成存储了多个Map.Entry的数据组

从Map中获取Map.Entry：
通过Map.entrySet()方法可以从指定的map对象中获取一个Set集合，集合中的元素是Map.Entry类型

//寻找数组的多数元素，出现次数>n/2
public int majorityElement(int[] nums) {Map<Integer, Integer> counts = countNums(nums);//相当于是声明了一个键值对的对象，用于存放map中众数的key-valueMap.Entry<Integer, Integer> majorityEntry = null;// map.entrySet  获得的是map中的每一个键值对 （将key-value看成时一个 Map.Entry对象）所构成的set集合//可以很方便的遍历同时获得key，valuefor (Map.Entry<Integer, Integer> entry : counts.entrySet()) {if (majorityEntry == null || entry.getValue() > majorityEntry.getValue()) {}}for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {if (majorityEntry == null || entry.getValue() > majorityEntry.getValue()) {majorityEntry = entry;}}return majorityEntry.getKey();
}
private Map<Integer, Integer> countNums(int[] nums) {Map<Integer, Integer> counts = new HashMap<Integer, Integer>();for (int num : nums) {if (! counts.containsKey(num)) {counts.put(num, 1);} else {counts.put(num, counts.get(num) + 1);}}return counts;
}

链表、二叉树

链表和二叉树定义本身还有递归，因此经常可以使用递归来解答。

Set

set.add();方法

语法 boolean add(E e)

返回值：如果Set集合中不包含要添加的对象，则添加对象并返回true；否则返回false。

参数：e是要添加到Set集合中的对象。

Map

map.put();方法

	public V put(K key, V value) {        如果key不存在，插入成功，返回null；如果key存在，返回之前对应的value。return putVal(hash(key), key, value, false, true);

map的key为基本数据类型时为值传递（拷贝一份），引用数据类型时为内存地址，8字节

常见排序

快排

可以将快排改造为小样本下使用插入排序，大样本下使用快排
Arrays.sort(); 方法基本数据类型使用快排，引用数据类型使用归并排序，保证稳定性

插入排序

public static void insertionSort(int[] arr) {if (arr == null || arr.length < 2) return;for (int i = 1; i < arr.length; i++) {for (int j = i - 1; j >= 0 && arr[j + 1] < arr[j]; j--) {swap(arr[j], arr[j + 1], arr);}}
}public static void swap(int i, int j, int[] arr) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;
}

归并排序

public static void process(int[] arr, int l, int r) {if (l == r) return;int mid = l + ((l - r) >> 1);process(arr, l, mid);process(arr, mid + 1, r);merge(arr, l, mid, r);}private static void merge(int[] arr, int l, int mid, int r) {int[] help = new int[l + r + 1];int i = 0;int p1 = l;int p2 = mid + 1;while (p1 <= mid && p2 <= r) {help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];}while (p1 <= mid) {help[i++] = arr[p1++];}while (p2 <= r) {help[i++] = arr[p2++];}for (int j = 0; j < help.length; j++) {arr[l + j] = help[j];}
}

快速排序

public static void quickSort(int[] arr) {if (arr == null || arr.length < 2) return;quickSort(arr, 0, arr.length - 1);
}private static void quickSort(int[] arr, int L, int R) {if (L < R) {swap(arr, L + (int) ((R - L + 1) * Math.random()), R);//划分区域int[] p = partition(arr, L, R);quickSort(arr, L, p[0] - 1);quickSort(arr, p[1] + 1, R);}
}private static int[] partition(int[] arr, int L, int R) {int less = L - 1;int more = R;while (L < more) {if (arr[L] < arr[R]) {swap(arr, ++ less, L++);} else if (arr[L] > arr[R]) {swap(arr, -- more, L);} else {L++;}}swap(arr, more, R);return new int[]{less + 1, more};
}private static void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;
}

堆排序

public static void heapSort(int[] arr) {if (arr == null || arr.length < 2) return;//相当于一个个给元素，建立大根堆
//        for (int i = 0; i < arr.length; i++) {
//            heapInsert(arr, i);
//        }//相当于一股脑给出整个堆，然后从最右侧叶节点进行调整for (int i = arr.length - 1; i >= 0; i--) {heapify(arr, i, arr.length);}int heapSize = arr.length;//0位置数与最后一位的数(n-1)交换，并让heapSize减一，表示从堆中移除该元素(也意味着该元素已经处于了正确的位置上了)swap(arr, 0, -- heapSize);while (heapSize > 0) {heapify(arr, 0, heapSize);  //将新换上来的0位置的数不断地heapify至该去的位置swap(arr, 0, -- heapSize);}}//相当于建堆，不断的与其父比较向上移动public static void heapInsert(int[] arr, int index) {while (arr[index] > arr[(index - 1) / 2]) {swap(arr, index, (index - 1) / 2);index = (index - 1) / 2;}}//x在index位置，是否能往下移动public static void heapify(int[] arr, int index, int heapSize) {int left = 2 * index + 1;//意味着有孩子，有向下移动的可能性while (left < heapSize) {//选出较大的孩子int largest = left + 1 < heapSize && arr[left + 1] > arr[left]? left + 1 : left;//较大的孩子与父节点比较largest = arr[index] > arr[largest] ? index : largest;//当前的数已经最大了，不用向下移动。if (largest == index) {break;}swap(arr, index, largest);//来到大孩子原来位置index = largest;left = index * 2 + 1;}}private static void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}

堆的应用

/*** 中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。* [2,3,4]的中位数是 3* [2,3] 的中位数是 (2 + 3) / 2 = 2.5* 设计一个支持以下两种操作的数据结构：* void addNum(int num) - 从数据流中添加一个整数到数据结构中。* double findMedian() - 返回目前所有元素的中位数。*/
public class MedianFinder {private PriorityQueue<Integer> minQ;private PriorityQueue<Integer> maxQ;public MedianFinder() {//（默认）小根堆，用于存放大于中位数的数this.minQ = new PriorityQueue<>();//大根堆，用于存放小于等于中位数的数this.maxQ = new PriorityQueue<>((x, y) -> y - x);}//总是维持 0 <大根堆size-小根堆size <=1; 总量为奇数时，总是peek()大根堆堆顶元素即可public void addNum(int num) {//还没加过数 或者 当前的数小于大根堆堆顶，加入大根堆，此时的中位数将小于等于原来中位数，因此可能需要移动元素到小根堆。if (maxQ.isEmpty() || num <= maxQ.peek()) {maxQ.add(num);if (minQ.size() + 1 < maxQ.size()) {minQ.add(maxQ.poll());}} else {//当前的数大于小根堆堆顶，加入小根堆，此时的中位数将大于等于原来中位数，因此可能需要移动元素到大根堆。minQ.add(num);if (minQ.size() > maxQ.size()) {maxQ.add(minQ.poll());}}}public double findMedian() {if (maxQ.size() > minQ.size()) {return maxQ.peek();}return (maxQ.peek() + minQ.peek()) / 2.0;  //求平均值，除以2.0得到double类型结果}
}

数组习题

两数组中包含唯一（二）不同元素，可以考虑用异或来解

/*** 给定一个大小为 n 的数组nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 n/2 的元素。* 你可以假设数组是非空的，并且给定的数组总是存在多数元素。*/
public class leetcode169 {//map法//Map的value存出现次数 public int majorityElement1(int[] nums) {Map<Integer, Integer> counts = countNums(nums);//相当于是声明了一个键值对的对象，用于存放map中众数的key-valueMap.Entry<Integer, Integer> majorityEntry = null;// map.entrySet  获得的是map中的每一个键值对 （将key-value看成时一个 Map.Entry对象）所构成的set集合//可以很方便的遍历同时获得key，valuefor (Map.Entry<Integer, Integer> entry : counts.entrySet()) {if (majorityEntry == null || entry.getValue() > majorityEntry.getValue()) {}}for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {if (majorityEntry == null || entry.getValue() > majorityEntry.getValue()) {majorityEntry = entry;}}return majorityEntry.getKey();}private Map<Integer, Integer> countNums(int[] nums) {Map<Integer, Integer> counts = new HashMap<Integer, Integer>();for (int num : nums) {if (! counts.containsKey(num)) {counts.put(num, 1);} else {counts.put(num, counts.get(num) + 1);}}return counts;}//排序，中间位置的数一定时众数public int majorityElement2(int[] nums) {Arrays.sort(nums);return nums[nums.length / 2];}//二分法查找众数，因为众数数量多余一半，因此众数必在左右其中一侧也是众数public int majorityElement4(int[] nums) {return majorityElementRec(nums, 0, nums.length - 1);}private int majorityElementRec(int[] nums, int low, int high) {if (low == high) return nums[low]; //baseCaseint mid = low + (high - low) / 2;int left = majorityElementRec(nums, low, mid);int right = majorityElementRec(nums, mid + 1, high);if (left == right) return left;//左右区间众数不相同，统计众数出现次数并比较选出答案int leftCount = countInRange(nums, low, high, left);int rightCount = countInRange(nums, low, high, right);return leftCount > rightCount ? left : right;}private int countInRange(int[] nums, int low, int high, int num) {int count = 0;for (int i = low; i <= high; i++) {if (nums[i] == num) {count++;}}return count;}//投票法/*** 我们维护一个候选众数 candidate 和它出现的次数 count。初始时 candidate 可以为任意值，count 为 0；* 我们遍历数组 nums 中的所有元素，对于每个元素 x，在判断 x 之前，如果 count 的值为 0，我们先将 x 的值赋予 candidate，随后我们判断 x：* 如果 x 与 candidate 相等，那么计数器 count 的值增加 1；* 如果 x 与 candidate 不等，那么计数器 count 的值减少 1；*/public int majorityElement5(int[] nums) {Integer candidate = null;int count = 0;for (int num : nums) {//重新选出一个候选人来if (count == 0) {candidate = num;}count += candidate == num ? 1 : - 1;}return candidate;}
}/*** 给你一个整数数组nums 和一个整数k ，判断数组中是否存在两个 不同的索引i和j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。* 如果存在，返回 true ；否则，返回 false*/
public class leetcode219 {//mappublic boolean containsNearbyDuplicate1(int[] nums, int k) {Map<Integer, Integer> map = new HashMap<>();int n = nums.length;for (int i = 0; i < n; i++) {if (map.containsKey(nums[i]) && i - map.get(nums[i]) <= k) {return true;} else {map.put(nums[i], i);}}return false;}//滑动窗口法public boolean containsNearbyDuplicate(int[] nums, int k) {HashSet<Integer> set = new HashSet<>();int n = nums.length;for (int i = 0; i < n; i++) {if (i > k) {//每次移除窗口外的元素  [i-k,i] 为窗口大小  如果窗口内含有相同元素，返回true。set.remove(nums[i - k - 1]);}if (! set.add(nums[i])) {  //秀啊  set.add();如果添加成功，返回true 不走if内容。return true;}}return false;}
}/*** 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。* 请注意 ，必须在不复制数组的情况下原地对数组进行操作。*/
public class leetcode283 {public void moveZeroes1(int[] nums) {if (nums == null) return;int j = 0;//遇到不是0的数就复制到nums[j]中for (int i = 0; i < nums.length; i++) {if (nums[i] != 0) {//j相当与槽位，依次选出非0的填入，最后一个非零元素填入后，j++了，j此时指向了最后一个非零元素的后一位，因此最后要把从j开始的数改为零nums[j++] = nums[i];}}//一口气把非0后面的数字设为零for (int i = j; i < nums.length; i++) {nums[i] = 0;}}/*** 使用双指针，左指针指向当前已经处理好的序列的尾部，右指针指向待处理序列的头部。* 右指针不断向右移动，每次右指针指向非零数，则将左右指针对应的数交换，同时左指针右移。*                               类似于快排，把非0的数交换到右边，因为非零数只与0做交换，因此非零数相互间次序不变*/public void moveZeroes2(int[] nums) {int n = nums.length, l = 0, r = 0;while (r < n) {if (nums[r] != 0) {swap(nums, l, r);l++;}r++;}}private void swap(int[] nums, int l, int r) {int temp = nums[l];nums[l] = nums[r];nums[r] = temp;}
}

二分法查找

 /*** 范围查询规律* 初始化:*   int left = 0;*   int right = nums.length - 1;* 循环条件*   left <= right* 右边取值*   right = mid - 1* 左边取值*   left = mid + 1* 查询条件*   >= target值, 则 nums[mid] >= target时, 都减right = mid - 1*   >  target值, 则 nums[mid] >  target时, 都减right = mid - 1*   <= target值, 则 nums[mid] <= target时, 都加left = mid + 1*   <  target值, 则 nums[mid] <  target时, 都加left = mid + 1* 结果*   求大于(含等于), 返回left*   求小于(含等于), 返回right* 核心思想: 要找某个值, 则查找时遇到该值时, 当前指针(例如right指针)要错过它, 让另外一个指针(left指针)跨过他(体现在left <= right中的=号), 则找到了

在排序数组中查找元素的第一个和最后一个位置

class Solution {public int[] searchRange(int[] nums, int target) {int leftIdx = binarySearch(nums, target, true);  //true表示可以等于int rightIdx = binarySearch(nums, target, false) - 1;if (leftIdx <= rightIdx && rightIdx < nums.length && nums[leftIdx] == target && nums[rightIdx] == target) {return new int[]{leftIdx, rightIdx};} return new int[]{-1, -1};}public int binarySearch(int[] nums, int target, boolean lower) {int left = 0, right = nums.length - 1, ans = nums.length;while (left <= right) {  //令left=right=mid,左右相遇之后再走一步跳出循环int mid = (left + right) / 2;//等于时找最左边等于target元素，大于是找第一个大于target的元素if (nums[mid] > target || (lower && nums[mid] >= target)) {right = mid - 1;ans = mid;} else {left = mid + 1;}}return ans;}
}

二叉树

二叉树遍历（递归方法）

重点：递归序！！！每个节点都会到达三次，根据打印时机不同分为前中后序。

 private void inOrder(TreeNode root) {//1if (root == null) return;inOrder(root.left);//2System.out.println(root);//2inOrder(root.right);//3}private void preOrder(TreeNode root) {//1if (root == null) return;System.out.println(root);//1inOrder(root.left);//2inOrder(root.right);//3}private void postOrder(TreeNode root) {//1if (root == null) return;inOrder(root.left);//2inOrder(root.right);//3System.out.println(root);//3}

二叉树遍历（非递归方法）

重点：递归序！！！每个节点都会到达三次，根据打印时机不同分为前中后序。

先序遍历

将头节点压入栈中
从栈中弹出一个节点cur
打印（处理）cur
先压入cur右孩子，再压入cur左孩子
周而复始 2~4

后序遍历

相当于pre`（头右左），将打印改成压入到收集栈中，最后统一打印

将头节点压入栈中
从栈中弹出一个节点cur
压入收集栈中
先压入cur左孩子，再压入cur右孩子
周而复始 2~4
最后统一打印

中序遍历

将头节点压入栈中
先将左边界节点一路压入栈中
左边界到头后，弹出左边界最后节点
如果弹出节点有右孩子的话，周而复始2~4

宽度优先遍历

准备一个双端队列，并将头节点入队列
弹出队头节点并打印（处理），并将该节点左右孩子入队
周而复始 2~ 直至队列为空

层序遍历（特殊宽度优先遍历）

准备一个双端队列，并将头节点入队列
在while循环中记录队列元素个数n
弹出队头节点并打印（处理），并将该节点左右孩子入队
循环n次3~步骤
进入下一轮while循环
周而复始 2~4 直至队列为空

	//先序遍历private static void preOrderUnRecur(TreeNode head) {if (head != null) {Stack<TreeNode> stack = new Stack<>();stack.push(head);while (stack != null) {head = stack.pop();System.out.print(head.val + " ");if (head.right != null) {stack.push(head.right);}if (head.left != null) {stack.push(head.left);}}}}//后序遍历   在先序遍历基础上改造 打印改为压入收集栈中 先压左再压右  保证头右左顺序private static void postOrderUnRecur(TreeNode head) {if (head != null) {Stack<TreeNode> stack = new Stack<>();Stack<TreeNode> coll = new Stack<>();stack.push(head);while (! stack.isEmpty()) {head = stack.pop();coll.push(head);if (head.left != null) {stack.push(head.left);}if (head.right != null) {stack.push(head.right);}}while (! coll.isEmpty()) {System.out.print(coll.pop().val + " ");}}}//中序遍历  左头右（左头右(左头右(左头右(...)))）   //压入栈顺序为先头后左，弹出顺序为先左再头，而找右节点是在弹出打印操作之后发生，因此右节点最后弹出(相当于右树左边界后搞)。private static void inOrderUnRecur(TreeNode head) {if (head != null) {Stack<TreeNode> stack = new Stack<>();while (! stack.isEmpty() || head != null) {if (head != null) {stack.push(head);head = head.left;} else {head = stack.pop();System.out.println(head.val + " ");head = head.right;}}}}//宽度优先遍历private static void widthPrioritySearch(TreeNode head) {if (head == null) return;Queue<TreeNode> queue = new LinkedList<>();queue.add(head);while (! queue.isEmpty()) {TreeNode cur = queue.poll();System.out.println(cur);if (cur.left != null) {queue.add(cur.left);}if (cur.right != null) {queue.add(cur.right);}}}//宽度优先遍历，寻找最大层节点数；private static int searchMaxLevelNodes(TreeNode head) {if (head == null) return 0;Queue<TreeNode> queue = new LinkedList<>();queue.add(head);//key为当前节点cur，value为当前节点所在层数curNodeLevelMap<TreeNode, Integer> levelMap = new HashMap<>();levelMap.put(head, 1);int curLevel = 1;int curLevelNodes = 0;int max = Integer.MIN_VALUE;while (! queue.isEmpty()) {TreeNode cur = queue.poll();int curNodeLevel = levelMap.get(cur);if (curNodeLevel == curLevel) {curLevelNodes++;} else {//进入下一层，更新最大层节点数，层数++，当前层节点数重置为1max = Math.max(max, curLevelNodes);curLevel++;curLevelNodes = 1;}if (cur.left != null) {levelMap.put(cur.left, curNodeLevel + 1);queue.add(cur.left);}if (cur.right != null) {levelMap.put(cur.right, curNodeLevel + 1);queue.add(cur.right);}}return Math.max(max, curLevelNodes);}//层序遍历、并分层打印节点值public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> res = new ArrayList<>();Queue<TreeNode> queue = new ArrayDeque<>();if (root != null) {queue.add(root);}while (!queue.isEmpty()) {//记录当前层节点数int n = queue.size();List<Integer> level = new ArrayList<>();//循环n次，一口气弹出当前层所有节点，并将下一层所有节点全部入队列for (int i = 0; i < n; i++) { TreeNode node = queue.poll();level.add(node.val);if (node.left != null) {queue.add(node.left);}if (node.right != null) {queue.add(node.right);}}res.add(level);}return res;
}

二叉树常见题型

判断搜索二叉树

中序遍历并判断节点值是否满足升序

public class TreeCode {public static int preValue = Integer.MIN_VALUE;//递归  (推荐)public static boolean isBST(TreeNode head) {if (head == null) return true;boolean isLeftBst = isBST(head.left);if (! isLeftBst) {return false;}if (preValue >= head.val) {return false;} else {preValue = head.val;}return isBST(head.right);}//递归傻白甜public static boolean isBST2(TreeNode head) {List<Integer> inOrderList = new ArrayList<>();process(head, inOrderList);for (Integer nodeVal : inOrderList) {if (nodeVal <= preValue) {return false;} else {nodeVal = preValue;}}return true;}private static void process(TreeNode head, List<Integer> inOrderList) {if (head == null) return;process(head.left, inOrderList);inOrderList.add(head.val);process(head.right, inOrderList);}//非递归public static boolean isBST3(TreeNode head) {if (head != null) {Stack<TreeNode> stack = new Stack<>();int preValue = Integer.MIN_VALUE;while (stack != null || head != null) {if (head != null) {stack.push(head);head = head.left;} else {head = stack.pop();if (head.val <= preValue) {return false;} else {preValue = head.val;}head = head.right;}}}return true;}
}

判断完全二叉树

当前节点有右无左直接返回 false
在遇到非全节点（有一个孩子）后又遇到了非叶子节点返回false

//判断是否为完全二叉树public static boolean isCBT(TreeNode head) {if (head == null) {return true;}Queue<TreeNode> queue = new ArrayDeque<>();queue.add(head);boolean leaf = false;TreeNode l = null;TreeNode r = null;while (! queue.isEmpty()) {head = queue.poll();l = head.left;r = head.right;if (    //有右无左直接返回   或者  在遇到非全节点后又遇到了非叶子节点l == null && r != null || leaf && (l != null || r != null)) {return false;}if (l != null) {queue.add(l);}if (r != null) {queue.add(r);}//遇到非全节点标记为trueif (l == null || r == null) {leaf = true;}}return true;}

判断平衡二叉树

任一节点的两子树高度差不超过一·
递归套路：假设可以从其左树和右树上要信息定结构体（即需要子树返回的信息）

//判断是否为平衡二叉树
public static boolean isBalanced(TreeNode head) {  //主函数return process2(head).isBalanced;
}public static ReturnType process2(TreeNode x) {if (x == null) return new ReturnType(true, 0);  //base//递归地向左右树要信息ReturnType leftData = process2(x.left);ReturnType rightData = process2(x.right);//根据左右树信息加工出自己的信息，作为返回值。boolean isBalanced = leftData.isBalanced && rightData.isBalanced&& (Math.abs(leftData.height - rightData.height) < 2);int height = Math.max(leftData.height, rightData.height) + 1;return new ReturnType(isBalanced, height);
}
//返回值结构体，分析需要向左右树要哪些信息
public static class ReturnType {public boolean isBalanced;public int height;public ReturnType(boolean isBalanced, int height) {this.isBalanced = isBalanced;this.height = height;}
}
//判断搜索二叉树  递归方法
public static SearchReturnType process3(TreeNode x) {if (x == null) return null;SearchReturnType leftData = process3(x.left);SearchReturnType rightData = process3(x.right);int min = x.val;int max = x.val;if (leftData != null) {min = Math.min(min, leftData.min);max = Math.max(max, leftData.max);}if (rightData != null) {min = Math.min(min, rightData.min);max = Math.max(max, rightData.max);}boolean isBST = true;if (leftData != null && (! leftData.isBST || leftData.max >= x.val)) {isBST = false;}if (rightData != null && (! rightData.isBST || rightData.min <= x.val)) {isBST = false;}if (leftData != null && rightData != null) {}return new SearchReturnType(isBST, max, min);}public static class SearchReturnType {public boolean isBST;public int max;public int min;public SearchReturnType(boolean isBST, int max, int min) {this.isBST = isBST;this.max = max;this.min = min;}}
//判断满二叉树  递归方法   简单
public static boolean isFBT(TreeNode head) {if (head == null) return true;ReturnInfo returnInfo = process4(head);return ((1 << returnInfo.height) - 1) == returnInfo.nodes;}private static ReturnInfo process4(TreeNode x) {if (x == null) return new ReturnInfo(0, 0);ReturnInfo leftData = process4(x.left);ReturnInfo rightData = process4(x.right);int nodes = leftData.nodes + rightData.nodes + 1;int height = Math.max(leftData.height, rightData.height) + 1;return new ReturnInfo(nodes, height);}public static class ReturnInfo {public int nodes;public int height;public ReturnInfo(int nodes, int height) {this.nodes = nodes;this.height = height;}   }

二叉树习题

找最近公共祖先

//递归方法找公共祖先public static TreeNode lowestCommonAncestor(TreeNode head, TreeNode o1, TreeNode o2) {if (head == null || head == o1 || head == o2) {return head;}TreeNode left = lowestCommonAncestor(head.left, o1, o2);TreeNode right = lowestCommonAncestor(head.right, o1, o2);if (left != null && right != null) {return head;}return left != null ? left : right;
}//非递归方法，寻找两节点最低公共祖先
public static TreeNode lca(TreeNode head, TreeNode o1, TreeNode o2) {//用来存放当前节点的父节点Map<TreeNode, TreeNode> fatherMap = new HashMap<>();fatherMap.put(head, head);process(head, fatherMap);TreeNode cur1 = o1;HashSet<TreeNode> set = new HashSet<>();set.add(head);//当前节点不是头节点while (cur1 != fatherMap.get(cur1)) {//set中保存o1父路径set.add(cur1);cur1 = fatherMap.get(cur1);}TreeNode cur2 = o2;while (! set.contains(cur2)) {cur2 = fatherMap.get(cur2);}return cur2;
}
private static void process(TreeNode head, Map<TreeNode, TreeNode> fatherMap) {if (head == null) return;fatherMap.put(head.left, head);fatherMap.put(head.right, head);process(head.left, fatherMap);process(head.right, fatherMap);
}

微软面试题，打印折纸折痕

//从上至下打印折纸折痕凹凸情况
public static void printAllFolders(int N){printProcess(1,N,true);
}
//满二叉树
//i为当前节点层数，N为折纸次数即树的深度，down为true 凹 
private static void printProcess(int i, int N, boolean down) {//层数大于树深，直接返回if (i>N) return;//中序遍历printProcess(i+1, N, true);System.out.print(down?"凹":"凸");printProcess(i+1, N, false);
}

给你一个整数数组 nums ，其中元素已经按升序排列，请你将其转换为一棵高度平衡二叉搜索树。

public TreeNode sortedArrayToBST(int[] nums) {return dfs(nums, 0, nums.length - 1);
}
//因为要满足平衡树，因此要选中位值为头节点
//为满足搜索树，左子树的节点从mid左边找，右子树的节点从mid右边找
private TreeNode dfs(int[] nums, int l, int r) {if (l > r) return null;  //base  左边界大于右边界返回空int mid = l + ((r - l) >> 1);TreeNode head = new TreeNode(nums[mid]);//递归构建左右子树head.left = dfs(nums, l, mid - 1);head.right = dfs(nums, mid + 1, r);return head;
}

给定一个二叉树，找出其最小深度。（递归）
- 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

public int minDepth(TreeNode root) {if (root == null) return 0;//当前节点为叶子节点if (root.left == null && root.right == null) return 1;int l = minDepth(root.left);int r = minDepth(root.right);//当前节点只有一个孩子  l、r中必然有一个为0if (root.left == null || root.right == null) {return l + r + 1;}//两个孩子都在return Math.min(l, r) + 1;
}

给你一个二叉树的根节点 root ，按任意顺序，返回所有从根节点到叶子节点的路径。
- 递归方法！！！

public class leetcode257 {public List<String> binaryTreePaths(TreeNode root) {List<String> paths = new ArrayList<>();constructPaths(root, "", paths);return paths;}private void constructPaths(TreeNode root, String path, List<String> paths) {if (root != null) {StringBuilder pathSB = new StringBuilder(path);pathSB.append(Integer.toString(root.val));//当前节点为叶子节点if (root.left == null && root.right == null) {paths.add(pathSB.toString());} else {pathSB.append("->");constructPaths(root.left, pathSB.toString(), paths);constructPaths(root.right, pathSB.toString(), paths);}}}
}

给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。

public List<String> binaryTreePaths(TreeNode root) {List<String> paths = new ArrayList<>();constructPath(root, "", paths);return paths;
}private void constructPath(TreeNode root, String path, List<String> paths) {if (root != null) {StringBuilder pathSB = new StringBuilder(path);pathSB.append(Integer.toString(root.val));//叶子节点if (root.left == null && root.right == null) {paths.add(pathSB.toString());} else {pathSB.append("->");constructPath(root.left, pathSB.toString(), paths);constructPath(root.right, pathSB.toString(), paths);}}
}

给你一个二叉搜索树的根节点 root ，返回树中任意两不同节点值之间的最小差值。

public class leetcode530 {int ans, pre;public int getMinimumDifference(TreeNode root) {ans = Integer.MAX_VALUE;pre = - 1;dfs(root);return ans;}//中序遍历private void dfs(TreeNode x) {if (x == null) return;dfs(x.left);update(x.val);  //处理逻辑dfs(x.right);}private void update(int x) {//第一个节点if (pre == - 1) {pre = x;} else {ans = Math.min(x - pre, ans);pre = x;}}
}

给你一个二叉树的根节点 root ，计算并返回整个树的坡度。

/*** 给你一个二叉树的根节点 root ，计算并返回 整个树 的坡度 。* 一个树的 节点的坡度 定义即为，该节点左子树的节点之和和右子树节点之和的 差的绝对值 。如果没有左子树的话，左子树的节点之和为 0 ；没有右子树的话也是一样。空结点的坡度是 0 。* 整个树 的坡度就是其所有节点的坡度之和。*/
public class leetcode563 {public int findTilt(TreeNode root) {if (root == null) return 0;//返回 当前坡度+左子树坡度和+右子树坡度和return Math.abs(sum(root.left) - sum(root.right)) + findTilt(root.left) + findTilt(root.right);}public int sum(TreeNode x) {if (x == null) return 0;return sum(x.left) + sum(x.right) + x.val;}//坡度差之和int res;public int findTilt2(TreeNode root) {dfs(root);return res;}//dfs就是上面的sum方法，多了一步把每个节点的坡度差累加到res中。private int dfs(TreeNode x) {if (x == null) return 0;int sumLeft = dfs(x.left);int sumRight = dfs(x.right);//计算每个节点坡度，并累加res += Math.abs(sumLeft - sumRight);return sumLeft + sumRight + x.val;}
}

给定一棵二叉树，你需要计算它的直径长度。

/*** 给定一棵二叉树，你需要计算它的直径长度。  求长度，因此求出的节点个数最后要减 1* 一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。*/
public class leetcode543 {//两次递归public int diameterOfBinaryTree(TreeNode root) {return f(root) - 1;}public int f(TreeNode root) {if (root == null) return 0;//过头节点int max1 = dfs(root.left) + dfs(root.right) + 1;//不过头节点int max2 = Math.max(f(root.left), f(root.right));return Math.max(max1, max2);}//查看以x为头的树的高度private int dfs(TreeNode x) {if (x == null) return 0;return Math.max(dfs(x.left), dfs(x.right)) + 1;}//单次递归方法  （声明一个全局变量，用于记录最长路径节点数）int res;public int diameterOfBinaryTree2(TreeNode root) {res = 1;depth(root);return res - 1;}private int depth(TreeNode x) {if (x == null) return 0;int L = depth(x.left);int R = depth(x.right);res = Math.max(res, L + R + 1);   //过当前节点时该子树最大深度  遍历每个节点return Math.max(res, Math.max(L, R) + 1);}
}

给你两棵二叉树 root 和 subRoot 。

没有优化

 给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。
public boolean isSubtree(TreeNode r, TreeNode s) {return dfs(r, s);
}
private boolean dfs(TreeNode r, TreeNode s) {if (r == null) return false;return dfs(r.left, s) || dfs(r.right, s) || check(r, s);
}
//判断两课树是否相同
private boolean check(TreeNode r, TreeNode s) {if (r == null && s == null) return true;//只有一个为空，或者 两者值不相等if (r == null || s == null || r.val != s.val) return false;return check(r.left, s.left) && check(r.right, s.right);
}

树形DP套路

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-z3xlMV9h-1665219082163)(C:\Users\DFL\AppData\Roaming\Typora\typora-user-images\image-20221005201817946.png)]

位运算

/*** 输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 '1' 的个数* 算术右移 >> ：舍弃最低位，高位用符号位填补；						* 逻辑右移 >>> ：舍弃最低位，高位用 0 填补。					符号左边表示要移动的二进制数，符号右边表示要移动多少位。*/
public int hammingWeight1(int n) {int res = 0;while (n != 0) {res += n & 1;//逻辑右移n >>>= 1;}return res;
}public int hammingWeight2(int n) {int res = 0;while (n != 0) {++ res;//消除最右侧的1n &= (n - 1);}return res;}
/*** 给定两个有符号32位整数a和b，不能使用算术运算符，分别实现a和b的加、减、乘、除运算*/public static int add(int a, int b) {int sum = 0;while (b != 0) {    //当进位信息为0时，表示不用加了，无进位相加结果即为最终求和结果sum = a ^ b;  //sum记录无进位相加结果b = (a & b) << 1; //b记录进位信息a = sum;  //得到进位信息和无进位相加结果后，需要相加得到最终结果，因此继续上面操作}return sum;}public static int minus(int a, int b) {return add(a, negNum(b));}private static int negNum(int n) {return add(~ n, 1);  //一个数的相反数为，它自己取反后加1}public static int multi(int a, int b) {int res = 0;while (b != 0) {if ((b & 1) != 0) {  //b末尾为1就累加ares = add(res, a);}a <<= 1;b >>>= 1;  //左移右移保证了结果不变，每次把b中的1移到末尾，然后乘上a右移变大后的结果}return res;}private static boolean isNeg(int n) {return n < 0;}//  代码一直跑，有问题啊public static int div(int a, int b) {int x = isNeg(a) ? negNum(a) : a;int y = isNeg(b) ? negNum(b) : b;int res = 0;for (int i = 31; i > - 1; minus(i, 1)) {if ((x >> i) >= y) {  //y右移不安全，可能出现负数res |= (1 << i); //x右移前从左往右第一个1，肯定是原来另一个因子那个位置（1<<i）上有1，才让它能移动这么多位x = minus(x, y << i);  //让x等于减后的值继续循环}}//符号不同return isNeg(a) ^ isNeg(b) ? negNum(res) : res;}public static int divide(int a, int b) {if (b == 0) {throw new RuntimeException("divisor is 0");}if (a == Integer.MIN_VALUE && b == Integer.MIN_VALUE) {return 1;} else if (b == Integer.MAX_VALUE) {return 0;} else if (a == Integer.MIN_VALUE) {int res = div(add(a, 1), b);return add(res, div(minus(res, b), b));}return div(a, b);}

//交换
public static void sway(int[] arr,int i,int j){if(i!=j){//不能两个值指向同一地址arr[i]=arr[i]^arr[j];arr[j]=arr[i]^arr[j];//就是arr[i]^arr[j]^arr[j]就表示aarr[i]=arr[i]^arr[j];//表示arr[i]^arr[j]^arr[i]^arr[j]^arr[j]就是b}
}
// mostRightOne值在二进制位上的位次就是pos得最右第一个1的位置
int mostRightOne = pos & (~pos + 1); //消除二进制末尾的 1
pos & (pos-1)//整数二进制奇数位偶数位交换
private static int process(int pos) {int pre = 0xAAAAAAAA; // 1010 1010 1010 1010 1010 1010 1010 1010 int post = 0x55555555; // 0101 0101 0101 0101 0101 0101 0101 0101 pre &= pos;post &= pos;pre >>= 1;post <<= 1;return pos + post;}//给定一个整数数组，只有一个数出现了一次，其他数字均出现了三次，输出这一个只出现一次的数。
public static int twoSingleNum(int[] arr) {int[] bit = new int[32];// 每一位求和for (int a : arr) {int b = 1;for (int i = 31; i >= 0; --i) {if ((a & b) != 0) {// 为1就累加++bit[i];}b <<= 1;// 换位}}int res = 0;for (int i = 0; i < 32; ++i) {res = res << 1;res += (bit[i] % 3);// 取余数}return res;}*** 给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。* 输入:a = "11", b = "1"* 输出："100"*/
public class leetcode67 {public String addBinary(String a, String b) {//求出累加次数int maxLength = Math.max(a.length(), b.length());StringBuilder sb = new StringBuilder();int carry = 0;  //carry % 2 为本位数字，carry / 2 为下一位的进位for (int i = 0; i < maxLength; i++) {// i小于各自长度                从最后一位开始计算，carry += i < a.length() ? (a.charAt(a.length() - 1 - i) - '0') : 0;carry += i < b.length() ? (b.charAt(b.length() - 1 - i) - '0') : 0;//这里注意转化为字符，carry%2加上个'0';sb.append((char) (carry % 2 + '0'));//下一位的进位信息carry /= 2;}if (carry > 0) {sb.append('1');}sb.reverse();return sb.toString();}// public String toString(int radix)  radix默认十进制     //在线OJ(Online Judge)貌似不支持public static String addBinary2(String a, String b) {//将a、b由二进制转为十进制，然后调用toString(int radix)，将十进制数转为指定进制字符串return new BigInteger(a, 2).add(new BigInteger(b, 2)).toString(2);}
}/*** 给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。* 输入：n = 2* 输出：[0,1,1]* 解释：* 0 --> 0* 1 --> 1* 2 --> 10*/
public class leetcode338 {//1、朴素public int[] countBits(int n) {int[] bits = new int[n + 1];for (int i = 0; i <= n; i++) {bits[i] = countOnes(i);}return bits;}private int countOnes(int x) {int ones = 0;while (x > 0) {ones++;x &= (x - 1);  //消除最右侧的1}return ones;}//2、DP  右移后补上右移操作丢掉的最末尾的数public int[] countBits2(int n) {int[] bits = new int[n + 1];
//        bits[0] = 0;     也可以不设置，因为int数组每个元素默认初始化都是0for (int i = 1; i <= n; i++) {      //对于正整数 x，将其二进制表示右移一位，等价于将其二进制表示的最低位去掉bits[i] = bits[i >> 1] + (i & 1);   //先取出最后一位数，奇数为1，偶数为0，当前数1的个数等于该数右移后1的个数+移动前最末尾的数}return bits;}//3、DP  消除最右侧1后加 1public int[] countBits3(int n) {int[] bits = new int[n + 1];
//        bits[0] = 0;for (int i = 1; i <= n; i++) {bits[i] = bits[i & i - 1] + 1;  //i & i - 1 消除最末尾的1，然后在末尾处在加上1，保持与原来的数1的个数相同}return bits;}public static void main(String[] args) {int[] bits = new int[4];for (int i = 0; i < bits.length; i++) {System.out.println(bits[i]);}}
}
/*** 给定一个整数，写一个函数来判断它是否是 4 的幂次方。如果是，返回 true ；否则，返回 false 。*/public static boolean isPowerOfFour1(int n) {//n小于等于0 false ，n不是2的整数幂 false  二进制表示中  1在偶数位 falsereturn n > 0 && (n & (n - 1)) == 0 && (n & (0xAAAAAAAA)) == 0;}public static boolean isPowerOfFour2(int n) {//n小于等于0 false ，n不是2的整数幂 false  n^x % (n-1) 恒等于 1，相当与每个都n都%(n-1)然后相乘;return n > 0 && (n & (n - 1)) == 0 && n % 3 == 1;}/*** 不使用比较符号，选出两数较大值，运用了两互斥条件相加来完成if else操作*/
public static int getMax(int a, int b) {int c = a - b;int sa = sign(a);   //正数为1，负数为0  0、1起到了相加互斥的效果int sb = sign(b);int sc = sign(c);int difSab = sa ^ sb;  //相同为0，不同为1int sameSab = flip(difSab); //相同为1，不同为0//返回a的条件  ab符号不同 a>0返回a，ab符号相同 a-b>=0 返回aint returnA = difSab * sa + sameSab * sc;  //互斥，用加号    a>b返回 a  a大于0，sa才会为1，总的结果为1  c大于0，sc才会为1，总的结果为1 int returnB = flip(returnA);return a * returnA + b * returnB;}private static int flip(int x) {return x ^ 1;        //符号取反}private static int sign(int x) {return flip((x >> 31) & 1);  //正数为1，负数为0}

奇怪题

/*** 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。* 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。* 如果这个过程 结果为 1，那么这个数就是快乐数。*///本题关键点为 totalSum  不会越来越大  要么变为1 要么死循环
public class leetcode202 {public boolean isHappy(int n) {HashSet<Integer> seen = new HashSet<>();//没有变成 1 或者 没有进入死循环while (n != 1 && ! seen.contains(n)) {seen.add(n);n = getNext(n);}return n == 1;}private int getNext(int n) {int totalSum = 0;while (n != 0) {int d = n % 10;n /= 10;totalSum += d * d;}return totalSum;}//隐式链表   判断有环无环public boolean isHappy2(int n) {int slow = n;int fast = getNext(n);while (fast != 1 && fast != slow) {slow = getNext(n);fast = getNext(getNext(fast));}return fast == 1;}
}/*** 丑数 就是只包含质因数 2、3 和 5 的正整数。* 给你一个整数 n ，请你判断 n 是否为 丑数 。如果是，返回 true ；否则，返回 false 。*  丑数可以表示为2^a * 3^b * 5^c*/public boolean isUgly(int n) {if (n <= 0) return false;int[] factors = {2, 3, 5};for (int factor : factors) {//先一直除一个因数，如果一直能除尽，则n = 1,除不尽换另一个因数尝试，while (n % factor == 0) {n /= factor;}}return n == 1;}

链表

dummyNode

在头节点钱可以设置一个空节点dummyNode，这样就可以避免一些问题中的头节点特殊处理，比如在K个一组反转链表问题中：

但是对于第一个子链表，它的头节点 head 前面是没有节点 pre 的。太麻烦了！难道只能特判了吗？答案是否定的。没有条件，我们就创造条件；没有节点，我们就创建一个节点。我们新建一个节点，把它接到链表的头部，让它作为 pre 的初始值，这样 head 前面就有了一个节点，我们就可以避开链表头部的边界条件。这么做还有一个好处，下面我们会看到。

/*** 给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。*/
public class leetcode203 {//递归，先对头节点以外的元素进行删除操作public ListNode removeElements1(ListNode head, int val) {if (head == null) return null;//head 抓住其他节点删除操作后返回的新头head.next = removeElements1(head.next, val);//如果head值等于val，则移除headreturn head.val == val ? head.next : head;}public ListNode removeElements2(ListNode head, int val) {ListNode dummyNode = new ListNode(0);dummyNode.next = head;ListNode cur = dummyNode;while (cur.next != null) {if (cur.next.val == val) {//移除链表当前节点下一个元素cur.next = cur.next.next;} else {cur =cur.next;}}return dummyNode.next;}
}/*** 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。*/
public class leetcode206 {public ListNode reverseList1(ListNode head) {//记录前驱节点ListNode pre = null;ListNode cur = head;while (cur != null) {//记录后继节点ListNode next = cur.next;//此时可以放心修改cur.next指向cur.next = pre;//pre、cur 都向后移动pre = cur;cur = next;}return pre;}/*** A->B->C->D->E* after reversing* A->B->NULL  NULL<-B<-C<-D<-E  A、B之间构成双向链表*/public ListNode reverseList2(ListNode head) {if (head == null || head.next == null) return head; //baseCase//以B为头节点的链表反转后，A仍然持有B的引用 A.next = BListNode newHead = reverseList2(head.next);// 令 A<-Bhead.next.next = head;//令 NULL<-Ahead.next = null;return newHead;}
}/*** 给你链表的头节点 head ，每k个节点一组进行翻转，请你返回修改后的链表。* k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是k的整数倍，那么请将最后剩余的节点保持原有顺序。*/
public class leetcode25 {public ListNode reverseKGroup(ListNode head, int k) {ListNode hair = new ListNode(0);hair.next = head;ListNode pre = hair;  //pre指向子链表反转后的末尾位置，用于拼接后面的串//不足k个直接返回原先的头节点while (head != null) {ListNode tail = pre;  //每次从pre位置跑k步指向第k个节点位置for (int i = 0; i < k; i++) {tail = tail.next;if (tail == null) {return hair.next;}}ListNode next = tail.next;  //pre tail两个变量记录反转前子串头节点前一个位置、结尾位置，用于将反转后的子串拼接回原链表ListNode[] reverse = myReverse(head, tail);//反转后新头尾head = reverse[0];tail = reverse[1];//重新将子串拼接回链表pre.next = head;tail.next = next;pre = tail;  //下一组head = tail.next;}return hair.next;}private ListNode[] myReverse(ListNode head, ListNode tail) {ListNode pre = tail.next;  //反转后新的尾节点指向原来尾节点下一个ListNode cur = head;while (pre != tail) {  //当前节点cur来到了尾部ListNode next = cur.next;cur.next = pre;pre = cur;cur = next;}//                   新头  新尾return new ListNode[]{tail, head};}
}

字符串

经常地，可以创建一个长度26的字母频次统计数组，index为字母 -‘ a’，值为字母出现频次，也可以创建128的char[ ]数组。

/*** 给定两个字符串 s 和 t ，判断它们是否是同构的。 潜台词：字符是否一一映射。* example: egg add*  					一个map不能保证一一映射*/  //  两个mappublic boolean isIsomorphic(String s, String t) {Map<Character, Character> s2t = new HashMap<Character, Character>();Map<Character, Character> t2s = new HashMap<Character, Character>();int len = s.length();for (int i = 0; i < len; ++i) {char x = s.charAt(i), y = t.charAt(i);if ((s2t.containsKey(x) && s2t.get(x) != y) || (t2s.containsKey(y) && t2s.get(y) != x)) {return false;}s2t.put(x, y);t2s.put(y, x);}return true;}//通过indexOf();  判断元素第一次出现位置是否相同public boolean isIsomorphic2(String s, String t) {int n = s.length();for (int i = 0; i < n; i++) {//index Of();没有找到返回=1if (s.indexOf(s.charAt(i)) != t.indexOf(t.charAt(i))) {   //关键return false;}}return true;}/**								与上题解法2异曲同工          都是记录元素第一次出现的位置，在这个位置第一次确定了两个元素的映射关系
** 给定一种规律 pattern和一个字符串s，判断 s是否遵循相同的规律。  abba "cat dog dog cat"* 这里的遵循指完全匹配，例如，pattern里的每个字母和字符串s中的每个非空单词之间存在着双向连接的对应规律。* 		public V put(K key, V value) {       如果key不存在，插入成功，返回null；如果key存在，返回之前对应的value。* 			return putVal(hash(key), key, value, false, true);* }*/
public static boolean wordPattern(String pattern, String s) {String[] words = s.split(" ");if (words.length != pattern.length()) return false;//key 为元素，value为第一次出现是的数组下标HashMap<Object, Integer> map = new HashMap<>();for (Integer i = 0; i < pattern.length(); i++) {//如果key不存在，插入成功，返回null；如果key存在，返回之前对应的value。//value 为元素第一次出现时的数组下标if (map.put(pattern.charAt(i), i) != map.put(words[i], i)) {return false;}}return true;
} /*** 给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。* 如果可以，返回 true ；否则返回 false 。   其实就是判断 ransomNote是不是magazine的顺序打乱了的子串* magazine 中的每个字符只能在 ransomNote 中使用一次。*/public boolean canConstruct(String ransomNote, String magazine) {if (ransomNote.length() > magazine.length()) return false;//创建长度26的数组，用来统计magazine中每个字母出现的次数，下标为 字母-'a',值为出现次数int[] cnt = new int[26];//统计magizine中字母出现次数for (char c : magazine.toCharArray()) {cnt[c - 'a']++;}//如果ransomNote 中某一字母出现次数比magazine  直接falsefor (char c : ransomNote.toCharArray()) {cnt[c - 'a']--;if (cnt[c - 'a'] < 0) {return false;}}return true;}/*** 给定一个字符串 s ，找到 它的第一个不重复的字符，并返回它的索引 。如果不存在，则返回 -1 。*/
public int firstUniqChar(String s) {char[] dict = new char[26];//第一遍统计字母出现次数    loveleetcode221424411214for (int i = 0; i < s.length(); i++) {int index = s.charAt(i) - 'a';dict[index]++;}//第二遍 查字典 找出只出现一次的字母  还是按原来字符串顺序一个个查找，因此能保证找到第一个不重复的字符for (int i = 0; i < s.length(); i++) {int index = s.charAt(i) - 'a';if (dict[index] == 1) {return i;}}return - 1;}

贪心策略

最常用的就是堆、排序

/*
切割金条花费最少问题
*/
public static int lessMoney(int[] arr) {//小根堆PriorityQueue<Integer> pQ = new PriorityQueue<>();for (int i : arr) {pQ.add(i);}int cur = 0;int sum = 0;while (pQ.size() > 1) {//每次弹出两个做结合，将值放入小根堆中直至小根堆数量为1cur = pQ.poll()+ pQ.poll();sum +=cur;pQ.add(sum);}return sum;
}
/*** 从当前给定项目中挑选出一些使手中资金最大化。*/
public class IPO {public static class Node {public int profit;public int cost;public Node(int profit, int cost) {this.profit = profit;this.cost = cost;}}public static class MinCostComparator implements Comparator<Node> {@Overridepublic int compare(Node o1, Node o2) {return o1.cost - o2.cost;}}public static class MaxProfitComparator implements Comparator<Node> {@Overridepublic int compare(Node o1, Node o2) {return o2.profit - o1.profit;}}//k 进行k轮  w手中的资金 profit、capital每个项目的利润以及收益public static int findMaximizedCapital(int k, int w, int[] profit, int[] capital) {PriorityQueue<Node> minCostQ = new PriorityQueue<>(new MinCostComparator());PriorityQueue<Node> maxProfitQ = new PriorityQueue<>(new MaxProfitComparator());//将所有项目扔进由花费组织的小根堆for (int i = 0; i < profit.length; i++) {minCostQ.add(new Node(profit[i], capital[i]));for (int i = 0; i < k; i++) {//还有项目   并且  手中资金能够解锁项目while (! minCostQ.isEmpty() && minCostQ.peek().cost <= w) {maxProfitQ.add(minCostQ.poll());}//没项目能选了，提前返回if (maxProfitQ.isEmpty()) {return w;}w += maxProfitQ.poll().profit;}}return w;}
}
//也行，不过跑起来没上面性能好 使用了lambda表达式  可以简化代码
public static int findMaximizedCapital2(int k, int w, int[] profit, int[] capital) {int n = profit.length;int cur = 0;int[][] arr = new int[n][2];for (int i = 0; i < n; i++) {//第一个表示所需资金，第二个表示可获得收益arr[i][0] = capital[i];arr[i][1] = profit[i];}//lambda表达式传入比较器    根据所需资金排个序Arrays.sort(arr, (a, b) -> a[0] - b[0]);//由净利润组成的大根堆PriorityQueue<Integer> pq = new PriorityQueue<>((x, y) -> y - x);for (int i = 0; i < k; i++) {while (cur < n && arr[cur][0] <= w) {pq.add(arr[i][1]);cur++;}if (! pq.isEmpty()) {w += pq.poll();} else {break;}}return w;}

暴力递归

暴力递归就是尝试

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

返回值往往是0 ~ i - 1位置选择确定的情况下，i 位置如何选择返回其结果
在尝试的过程中找到可变参数形式最简单，可变参数个数最少的试法

/*** N皇后问题，没法做总体时间复杂度优化，可以做常数优化。* num1() res = 365596* cost time4244ms* num2() res = 365596* cost time180ms*/
public class NQueens {public static int num1(int n) {int[] record = new int[n];  //每一个值表示，在第i行皇后放在那一列return process1(0, record, n);}//record[0,1,2...,i-1]表示0-i-1行，皇后放在了那一列//i表示当前在第i行//n表示总共多少行多少列//返回值表示 摆完所有的皇后，合理摆法有多少种private static int process1(int i, int[] record, int n) {if (i == n) return 1;  //来到了终止行 （[0,n-1]）int res = 0;for (int j = 0; j < n; j++) { //当前在第i行，尝试所有的列//如果当前列可以摆，进行深度优先遍历，寻找下一行可选的摆法if (isValid(record, i, j)) {record[i] = j;res += process1(i + 1, record, n);}}return res;}private static boolean isValid(int[] record, int i, int j) {//遍历之前的行  看之前所摆的皇后与第i行皇后是否同列或共斜线for (int k = 0; k < i; k++) {if (record[k] == j || Math.abs(record[k] - j) == Math.abs(i - k)) {return false;}}return true;}//方法二：使用位运算public static int num2(int n) {if (n < 1 || n > 32) {return 0;}//限制可选范围  后n位是1，前面都是0  该步骤旨在将可供选择的列限制在指定范围内，后面与其他限制取 & 时 前面的0不造成影响int limit = n == 32 ? - 1 : (1 << n) - 1;  -1的二进制表示为32个1    (1 << n)注意时1左移，1放前边return process2(limit, 0, 0, 0);}//1地位置可以放皇后，0的位置不行。private static int process2(int limit,   //总的可选范围int colLim, //列限制int leftDiaLim,  //左对角线限制int rightDialim) {  //右对角线限制//base caseif (colLim == limit) return 1;  //列限制数量与可供选择列数量相同，该结果为一个合法的结果。int mostRightOne = 0;//当前可供选择的列   在总的可选范围上 排除其他限制int pos = limit & (~ (colLim | leftDiaLim | rightDialim));int res = 0;//还有位置可选时while (pos != 0) {mostRightOne = pos & (~ pos + 1);  //从最右侧1开始遍历pos -= mostRightOne;  //消除最右侧1，pos移到下一个1继续尝试res += process2(limit,colLim | mostRightOne,(leftDiaLim | mostRightOne) << 1,(rightDialim | mostRightOne) >>> 1);  //无符号右移 32皇后最高位为1 右移后最高位拿0来补 }return res;}public static void main(String[] args) {int n = 14;long start = System.currentTimeMillis();System.out.println(num1(n));long end = System.currentTimeMillis();System.out.println("cost time" + (end - start)+"ms");start = System.currentTimeMillis();System.out.println(num2(n));end = System.currentTimeMillis();System.out.println("cost time" + (end - start)+"ms");}
}
/*** Tower of HanoiMove 1 from 左 to 中Move 2 from 左 to 右Move 1 from 中 to 右Move 3 from 左 to 中Move 1 from 右 to 左Move 2 from 右 to 中Move 1 from 左 to 中*/
public static void hanoi(int n) {if (n > 0) {func(n, "左", "中", "右");   //从左移动到中}}//i为盘子编号，从上至下1~n      每次移动保证自己的底不违规private static void func(int i, String from, String to, String other) {if (i == 1) {System.out.println("Move 1 from " + from + " to " + to);} else {//先把第i-1个圆盘从from移动到other上去          //至于0~i-2个圆盘怎么移动由子过程决定func(i - 1, from, other, to);//再将最下面第i个圆盘移动到to位置System.out.println("Move " + i + " from " + from + " to " + to);//最后将第i-1个圆盘从other移动到to位置func(i - 1, other, to, from);}}
/*** 单词所有子序列*/
public static void printAllSubsequence1(String s) {char[] chars = s.toCharArray();List<String> list = new ArrayList<>();process1(chars, 0, list);System.out.println(list);}private static void process1(char[] str, int i, List<String> res) {if (i == str.length) {res.add(String.valueOf(str));}boolean[] isVisit = new boolean[26];for (int j = i; j < str.length; j++) {    //在i及后面位置选一个放到i位置，后面自由排列//      分支限界if (! isVisit[str[j] - 'a']) {isVisit[str[j] - 'a'] = true;   //去重swap(i, j, str);process1(str,i+1,res);swap(i, j, str);}}}private static void swap(int i, int j, char[] str) {char temp = str[i];str[i] = str[j];str[j] = temp;}public static void printAllSubsequence2(String s) {char[] chars = s.toCharArray();process2(chars, 0);}private static void process2(char[] str, int i) {if (i == str.length) {System.out.println(String.valueOf(str));  //String.valueOf();将其他类型变量转为字符串return;   //base case 别因为打印 忘了要return！！！}process2(str, i + 1);  //保留当前字母char temp = str[i];str[i] = 0;process2(str, i + 1);  //不保留当前字母str[i] = temp;}/*** 两个绝顶聪明的人，从左右两边拿牌，求获胜者最大值*/
public class CardsInLIne {public static int win1(int[] arr) {if (arr == null || arr.length == 0) return 0;//              玩家A先手                       玩家B先手return Math.max(f(arr, 0, arr.length - 1), s(arr, 0, arr.length - 1));}//先手函数      玩家Aprivate static int f(int[] arr, int l, int r) {if (l == r) return arr[l];// 选择后手函数中最大的   拿走左边的                 拿走右边的return Math.max(arr[l] + s(arr, l + 1, r), arr[r] + s(arr, l, r - 1));}//后手函数      玩家Bprivate static int s(int[] arr, int l, int r) {if (l == r) return 0;  //只剩一张牌，但因为自己是后手，因此没牌可拿了，返回0//轮到自己先手了，因为绝顶聪明，因此之前先手的人会让后手的人拿到最少return Math.min(f(arr, l + 1, r), f(arr, l, r - 1));}/*** 1和A对应，2和B对应，3和C对应* "111"  可以转换为AAA、AK、KA*/
public class NumToStr {public static int numToStr(String num) {char[] chs = num.toCharArray();return process(0, chs);}//返回值：此时来到i位置，i-1上做的决定所构成的结果private static int process(int i, char[] str) {if (i == str.length) return 1;  //之前做的决定 整体构成一个有效结果//之前做的决定导致在i位置上无法做决定，整体无效if (str[i] == '0') {return 0;}if (str[i] == '1') {//i位置单独转换int res = process(i + 1, str); //i+1可能等于数组长度，i+1=len 符合第一个ifif (i + 1 < str.length) {  //如果i+1小于len，那么i+2就有结果//i与i+1位置合并一起转换res += process(i + 2, str);}return res;}if (str[i] == '2') {//i位置单独转换int res = process(i + 1, str);//i与i+1位置合并一起转换,且0<str[i+1]<6时才合法if (i + 1 < str.length && str[i + 1] <= '6') {res += process(i + 2, str);}}//i位置数>=3,只能单独转化return process(i + 1, str);}//dp版本public static int dpWays(int num) {if (num < 1) return 0;char[] str = String.valueOf(num).toCharArray();int N = str.length;int[] dp = new int[N + 1];dp[N] = 1;          //从N位置出发有多少种可能性dp[N - 1] = str[N - 1] == '0' ? 0 : 1;for (int i = N - 2; i >= 0; i--) {		从后往前计算if (str[i] == '0') {dp[i] = 0;} else {dp[i] = dp[i + 1] +(((str[i] - '0') * 10 + str[i + 1] - '0') < 27 ? dp[i + 2] : 0);}}return dp[0];}//0~i-1位置确定的情况下，i位置如何选择/*** 给定两个长度都为N的数组weights和values，weights[i]和values[i]分别代表i号物品的重量和价值。* 给定一个正数bag，表示一个载重bag的袋子，你装的物品不能超过这个重量。返回你能装下最多的价值是多少?*/
public class MaxValue {public static int maxValue(int[] weights, int[] values, int bag) {return process1(0, 0, weights, values, bag);}//返回值：i...的货物自由选择，返回在该区间可以获得的最大价值private static int process1(int i, int alreadyWeights, int[] weights, int[] values, int bag) {if (alreadyWeights >= bag) return 0;if (i == values.length) return 0;return Math.max(//要该商品values[i] + process1(i + 1, alreadyWeights + weights[i], weights, values, bag),//不要该商品process1(i + 1, alreadyWeights, weights, values, bag));}public class leetcode39 {public static List<List<Integer>> combinationSum(int[] candidates, int target) {List<List<Integer>> res = new ArrayList<>();List<Integer> already = new ArrayList<>();dfs(0, already, res, candidates, target);return res;}/*** 给你一个 无重复元素 的整数数组candidates 和一个目标整数target，找出candidates中可以使数字和为目标数target的所有不同组合 ，并以列表形式返回。* 你可以按 任意顺序返回这些组合。* candidates 中的同一数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。*/public static List<List<Integer>> combinationSum(int[] candidates, int target) {List<List<Integer>> res = new ArrayList<>();List<Integer> already = new ArrayList<>();dfs(0, already, res, candidates, target);return res;}//already：已经组合的列表private static void dfs(int i, List<Integer> already, List<List<Integer>> res, int[] candidates, int target) {//超过了直接返回if (i == candidates.length) {return;}if (target == 0) {//      将already加入到新数组中  不能直接add(already),非基本类型传入的是引用，会在原列表上修改，因此要复制一份res.add(new ArrayList<Integer>(already));return;}//直接跳过dfs(i + 1, already, res, candidates, target);//选择当前值if (target >= candidates[i]) {already.add(candidates[i]);//重复利用，还停留在i位置dfs(i, already, res, candidates, target - candidates[i]);//加入后重新移除该元素，使该元素可重复使用already.remove(already.size() - 1);}}

动态规划 P17

暴力递归try -> 记忆化搜索（DP）-> 严格表结构(DP) -> 严格表精版(DP)
- 严格表结构 一定要画图！！！！！！！
  - 描述可变范围，暴力递归中有几个可变参数就是几维表
  - 标出需要计算的终止位置
  - 标出不用计算直接出答案的位置 base case，先把已知位置填好
  - 分析普通位置的依赖关系，并根据依赖关系、已知数据以及终止位置，得出填表策略，确定填表顺序
  - 顺序确定后，将递归调用返回结果改为填表
  - 注意填表过程中可能出现的越界问题
- 范围尝试的表，左下半区一律无效（即左边界不能大于右边界）、已知值base case一般为对角线
- 在进行斜率优化时，只需从表中数据找规律即可，没必要回溯原题意
- 可变参数越少越好（表的维度），单可变参数的维度（一个点（即一个整数是最好的）或一个数组等）
- [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-eWrnQmkk-1665219082164)(C:\Users\DFL\AppData\Roaming\Typora\typora-user-images\image-20221006183417888.png)]

/*** 机器人走路问题，暴力递归 vs 记忆化搜索*/
public class RobotWalk {//                          N个位置   结束    开始    走k步public static int robotWalk1(int N, int E, int S, int K) {return f1(N, E, S, K);}private static int f1(int N, int E, int cur, int rest) {if (rest == 0) {return cur == E ? 1 : 0;}if (cur == 1) {return f1(N, E, 2, rest - 1);}if (cur == N) {return f1(N, E, N - 1, rest - 1);}return f1(N, E, cur - 1, rest - 1) + f1(N, E, cur + 1, rest - 1);}//记忆化搜索public static int robotWalk2(int N, int E, int S, int K) {int[][] dp = new int[N + 1][K + 1];for (int i = 0; i <= N; i++) { //都要带等号，初始全部变成 -1for (int j = 0; j <= K; j++) {dp[i][j] = - 1;}}return f2(N, E, S, K, dp);}private static int f2(int N, int E, int cur, int rest, int[][] dp) {//判断是否有缓存,如果有 直接走缓存returnif (dp[cur][rest] != - 1) {  //-1意味着没计算过return dp[cur][rest];}//建缓存过程if (rest == 0) {       //没剩余步数了，到终点为1，否则为0dp[cur][rest] = cur == E ? 1 : 0;return dp[cur][rest];}//还有剩余步数rest>0if (cur == 1) {dp[cur][rest] = f2(N, E, 2, rest - 1, dp);} else if (cur == N) {dp[cur][rest] = f2(N, E, N - 1, rest - 1, dp);} else {dp[cur][rest] = f2(N, E, cur - 1, rest - 1, dp) + f2(N, E, cur + 1, rest - 1, dp);}return dp[cur][rest];}/*** 组成aim金额所需要的最少货币数量*/public class MinCoins {public static int minCoins1(int[] arr, int aim) {										//暴力递归return f1(arr, 0, aim);}//index。。。后面硬币自由选择，组成rest金额所需最少硬币数private static int f1(int[] arr, int index, int rest) {if (rest < 0) return - 1;   //没希望，之前决策就错了，无效解if (rest == 0) return 0; //够了，不用选了   return 0为有效解//rest>0// 没硬币，但还不够aimif (index == arr.length) return - 1;//还有硬币，且还不够aim金额int p1 = f1(arr, index + 1, rest);  //不选当前硬币int p2Next = f1(arr, index + 1, rest - arr[index]); //选当前硬币//其中一个有效if (p1 == - 1 && p2Next == - 1) return - 1;   //下一步选哪个都没戏，这一步就无效if (p1 == - 1) return p2Next + 1;if (p2Next == - 1) return p1;//都有效return Math.min(p1, p2Next + 1);}public static int minCoins2(int[] arr, int aim) {									//记忆化搜索int[][] dp = new int[arr.length + 1][aim + 1];for (int i = 0; i <= arr.length; i++) {for (int j = 0; j <= aim; j++) {dp[i][j] = - 2;  //-2表示没算过}}return f2(arr, 0, aim, dp);}//index。。。后面硬币自由选择，组成rest金额所需最少硬币数private static int f2(int[] arr, int index, int rest, int[][] dp) {//dp二维表中没有rest小于0的区域，这里用硬逻辑表示，二维表左侧的区域都是-1，中了无效区的缓存if (rest < 0) return - 1; //rest<0if (dp[index][rest] != - 2) {  //有缓存直接走缓存return dp[index][rest];}//构建缓存过程if (rest == 0) {    //rest=0dp[index][rest] = 0;} else if (index == arr.length) {  //rest > 0 index=Ndp[index][rest] = - 1;} else {   //rest>0 index<N//还有硬币，且 还不够aim金额int p1 = f2(arr, index + 1, rest, dp);  //不选当前硬币int p2Next = f2(arr, index + 1, rest - arr[index], dp); //选当前硬币//其中一个有效if (p1 == - 1 && p2Next == - 1) {dp[index][rest] = - 1;}   //下一步选哪个都没戏，这一步就无效else if (p1 == - 1) {dp[index][rest] = p2Next + 1;} else if (p2Next == - 1) {dp[index][rest] = p1;} else {//都有效dp[index][rest] = Math.min(p1, p2Next + 1);}}return dp[index][rest];}//动态规划  严格表依赖  初始化表、填表//row 为index  col为restpublic static int minCoins3(int[] arr, int aim) {									//严格表结构int N = arr.length;int[][] dp = new int[N + 1][aim + 1];//初始化边界过程for (int row = 0; row <= N; row++) {dp[row][0] = 0;  //每一行的0列为0}for (int col = 1; col <= aim; col++) { //从第一列开始最后一行的每一列为-1dp[N][col] = - 1;}//一般位置计算过程for (int index = N - 1; index >= 0; index--) {for (int rest = 1; rest <= aim; rest++) {int p1 = dp[index + 1][rest];int p2Next = - 1;  //越界则为-1if (rest - arr[index] >= 0) {p2Next = dp[index + 1][rest - arr[index]];}if (p1 == - 1 && p2Next == - 1) {dp[index][rest] = - 1;} else if (p1 == - 1) {dp[index][rest] = p2Next + 1;} else if (p2Next == - 1) {dp[index][rest] = p1;} else {dp[index][rest] = Math.min(p1, 1 + p2Next);}}}//0行return dp[0][aim];}
}/*** 规定步数马到达终点的方法数* 2549ms   暴力递归* -----------------------------------					三维表						* 0ms      严格表结构*/
public class ChineseChess {public static int horseWalk1(int K, int x, int y) {return process(K, x, y);}//从（0，0）位置要去往（x,y）位置，还需跳step步           要去往的地方//也可以这样想，从（x,y)位置跳往（0，0）位置public static int process(int step, int x, int y) {if (x < 0 || x > 8 || y < 0 || y > 9) {return 0;}if (step == 0) {  //剩余0步，如果要跳往的位置为（0，0）就是一种合理的方法return (x == 0 & y == 0) ? 1 : 0;}return + horseWalk1(step - 1, x - 1, y - 2)+ horseWalk1(step - 1, x - 1, y + 2)+ horseWalk1(step - 1, x - 2, y - 1)+ horseWalk1(step - 1, x - 2, y + 1)+ horseWalk1(step - 1, x + 1, y - 2)+ horseWalk1(step - 1, x + 1, y + 2)+ horseWalk1(step - 1, x + 2, y - 1)+ horseWalk1(step - 1, x + 2, y + 1);}public static int horseWalk2(int step, int x, int y) {if (x < 0 || x > 8 || y < 0 || y > 9 || step < 0) {return 0;}int[][][] dp = new int[step + 1][9][10];dp[0][0][0] = 1;//0层不管。只有原点是1，其余都是0（初始默认）for (int h = 1; h <= step; h++) {  //层for (int r = 0; r < 9; r++) {               //枚举所有可能性  同一层不存在依赖关系for (int c = 0; c < 10; c++) {dp[h][r][c] += getValue(dp, h - 1, r - 1, c - 2);       //getValue();防止越界dp[h][r][c] += getValue(dp, h - 1, r - 1, c + 2);dp[h][r][c] += getValue(dp, h - 1, r - 2, c - 1);dp[h][r][c] += getValue(dp, h - 1, r - 2, c + 1);dp[h][r][c] += getValue(dp, h - 1, r + 1, c - 2);dp[h][r][c] += getValue(dp, h - 1, r + 1, c + 2);dp[h][r][c] += getValue(dp, h - 1, r + 2, c - 1);dp[h][r][c] += getValue(dp, h - 1, r + 2, c + 1);}}}return dp[step][x][y];}private static int getValue(int[][][] dp, int h, int r, int c) {if (r < 0 || r > 8 || c < 0 || c > 9 ) {return 0;}return dp[h][r][c];}/*** 每个纸币自由选择，可重复选，aim金额找零的方法数* 3937256          暴力* 892ms* -----------------------------------* 3937256          严格表结构，枚举版* 3ms* -----------------------------------* 3937256          严格表结构，去枚举版、斜率优化，只和观察有关，不需要在意原题意，咱就做实在人* 0ms*/
public class CoinsWays {public static int way1(int[] arr, int aim) {return process1(arr, 0, aim);}private static int process1(int[] arr, int index, int rest) {if (index == arr.length) {return rest == 0 ? 1 : 0;}int ways = 0;//枚举每种面值纸币使用张数，但总金额不要超过rest  2元使用0、1、2、3、4。。。 5元使用0、1、2、3、4、5for (int zhang = 0; arr[index] * zhang <= rest; zhang++) {ways += process1(arr, index + 1, rest - arr[index] * zhang);  //前面面值搞定了后还剩rest - arr[index] * zhang钱要搞，继续枚举}return ways;}public static int way2(int[] arr, int aim) {if (arr == null || arr.length == 0) return 0;int N = arr.length;int[][] dp = new int[N + 1][aim + 1];dp[N][0] = 1;for (int index = N - 1; index >= 0; index--) {    //从下之上填表for (int rest = 0; rest <= aim; rest++) {int ways = 0;for (int zhang = 0; arr[index] * zhang <= rest; zhang++) {   //根据依赖关系填表ways += dp[index + 1][rest - arr[index] * zhang];  //前面面值搞定了后还剩rest - arr[index] * zhang钱要搞，继续枚举}dp[index][rest] = ways;  //当前层依赖它下一层的某些值}}return dp[0][aim];}//优化枚举行为  枚举行为中，当前位置依赖其下一行 rest - arr[index] * zhang（zhang++） 列的值 a+b+c+d+...// 但观察发现当前行rest-1*arr[index]位置的值是b+c+d得来的，因此当前格子的值就是其下一行同一列的值+同一行、当前列值减一个当前面值的列的值public static int way3(int[] arr, int aim) {if (arr == null || arr.length == 0) return 0;int N = arr.length;int[][] dp = new int[N + 1][aim + 1];dp[N][0] = 1;for (int index = N - 1; index >= 0; index--) {for (int rest = 0; rest <= aim; rest++) {dp[index][rest] = dp[index + 1][rest];//依赖下方的格子if (rest - arr[index] >= 0) {dp[index][rest] += dp[index][rest - arr[index]];  //以及当前行中，当前列值减一个当前面值的列}}}return dp[0][aim];}

基础提升

Manacher算法

回文半径数组可以帮助解决很多回文问题

/**												i’回文串小于R-i  i位置回文半径与i‘相等* 求最大回文子串长度				i在R内  i在R外   i’回文串大于R-i	 i位置回文半径等于R-i*												i’回文串等于R-i  i位置回文半径起码时R-i，从i位置可能需要扩*/
public static int maxLcpsLength(String s) {							if (s == null || s.length() == 0) return 0;char[] str = manacherString(s);int[] pArr = new int[str.length];  //和处理串长度相同int C = - 1; //中心int R = - 1; //R为回文右边界再往右的位置，最右的有效区域为R-1int max = Integer.MIN_VALUE;  //阔出来的最大值for (int i = 0; i < str.length; i++) {	//i至少的回文区域，先给pArr[i]//分i在R内，与i在R外      选回文半径较小的  pArr[i'],i到R的距离R-ipArr[i] = R > i ? Math.min(pArr[2 * C - i], R - i) : 1;  //i在R外，回文区域为自己//从需要验证的位置开始while (i + pArr[i] < str.length && i - pArr[i] > - 1) {//从至少的回文区域都尝试一步，看回文区域能不能变大if (str[i + pArr[i]] == str[i - pArr[i]]) {pArr[i]++;} else {break;}}//更新 R、Cif (i + pArr[i] > R) {R = i + pArr[i];C = i;}max = Math.max(max, pArr[i]);}return max - 1;  //处理后的字符串最大回文半径减1，就是原字符串的最大回文长度
}
//	accb		#a#c#c#b#   	因为在回文串长度为偶数时、回文中心线在两个数字中间，若从每个位置i出发往两边扩，会错过一些内容 accb  找不到cc
private static char[] manacherString(String str) {char[] charArr = str.toCharArray();char[] res = new char[2 * str.length() + 1];int index = 0;for (int i = 0; i < res.length; i++) {res[i] = (1 & i) == 0 ? '#' : charArr[index++];}return res;
}

滑动窗口

O(N)的平均时间复杂度下，动态生成窗口中最大值
使用双向队列

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-SjJfPaQE-1665219082164)(C:\Users\DFL\AppData\Roaming\Typora\typora-user-images\image-20221005191724095.png)]

单调栈

解决当前数左右两边离当前数最近的比当前数大的值
使用一个栈（存放的是数组下标），大数在下小数在上，从左往右遍历数组，遇到比栈顶元素大的数时，就依次弹出并生成信息，直至当前数可以放进去为止，每个弹出的数，左边离当前数最大的是它下面压着的数，右边离它最大的是使它们弹出的数即当前数。
若包含相同元素，栈中相同元素放入一个链表中（可以是LInkedList、ArrayList）

Morris遍历

时间复杂度O(N)，额外空间复杂度O(1)
Morris遍历无法到达同意节点
线索二叉树，使用空闲指针完成遍历，当前节点左树最右节点右指针指向当前节点cur。
先序遍历：如果一个节点只到达一次直接打印，到达两次第一次才打印
中序遍历：如果一个节点只到达一次直接打印，到达两次第二次才打印
后序遍历：如果一个节点能到达两次，第二次打印，然后逆序打印左树的右边界好复杂略。。。。。。

public static void morris(TreeNode head) {if (head == null) return;TreeNode cur = head;TreeNode mostRight = null;while (cur != null) {mostRight = cur.left;if (mostRight != null) {   //有左子树while (mostRight.right != null && mostRight.right != cur) {  //能够往右走且不回到当前节点mostRight = mostRight.right;  //循环结束到达cur左树最右节点}if (mostRight.right == null) {  //第一次来到curmostRight.right = cur;  //最右节点指针指向当前节点curcur = cur.left;  //cur向左孩子移动continue;  //继续进行循环} else {    //不是第一次来到当前节点，而是顺着左树最右指针来的  mostRight.right ==cur;mostRight.right = null; //将右指针还原回去}}cur = cur.right;  //当前树没有左子树，直接向右移动}
}
//先序
public static void morrisPre(TreeNode head) {if (head == null) return;TreeNode cur = head;TreeNode mostRight = null;while (cur != null) {mostRight = cur.left;if (mostRight != null) {   //有左子树while (mostRight.right != null && mostRight.right != cur) {  //能够往右走且不回到当前节点mostRight = mostRight.right;  //循环结束到达cur左树最右节点}if (mostRight.right == null) {  //第一次来到curSystem.out.println(cur.val);  //第一次来打印mostRight.right = cur;  //最右节点指针指向当前节点curcur = cur.left;  //cur向左孩子移动continue;  //继续进行循环} else {    //不是第一次来到当前节点，而是顺着左树最右指针来的  mostRight.right ==cur;mostRight.right = null; //将右指针还原回去}} else {System.out.println(cur.val);  //没有左子树直接打印}cur = cur.right;  //当前树没有左子树，直接向右移动}}
//中序public static void morrisIn(TreeNode head) {if (head == null) return;TreeNode cur = head;TreeNode mostRight = null;while (cur != null) {mostRight = cur.left;if (mostRight != null) {   //有左子树while (mostRight.right != null && mostRight.right != cur) {  //能够往右走且不回到当前节点mostRight = mostRight.right;  //循环结束到达cur左树最右节点}if (mostRight.right == null) {  //第一次来到curmostRight.right = cur;  //最右节点指针指向当前节点curcur = cur.left;  //cur向左孩子移动continue;  //继续进行循环} else {    //不是第一次来到当前节点，而是顺着左树最右指针来的  mostRight.right ==cur;mostRight.right = null; //将右指针还原回去}}System.out.println(cur.val);  //没有左树，或者第二次来到该节点打印cur = cur.right;  //当前树没有左子树，直接向右移动}}
//后序public static void morrisPost(TreeNode head) {if (head == null) return;TreeNode cur = head;TreeNode mostRight = null;while (cur != null) {mostRight = cur.left;if (mostRight != null) {   //有左子树while (mostRight.right != null && mostRight.right != cur) {  //能够往右走且不回到当前节点mostRight = mostRight.right;  //循环结束到达cur左树最右节点}if (mostRight.right == null) {  //第一次来到curmostRight.right = cur;  //最右节点指针指向当前节点curcur = cur.left;  //cur向左孩子移动continue;  //继续进行循环} else {    //不是第一次来到当前节点，而是顺着左树最右指针来的  mostRight.right ==cur;mostRight.right = null; //将右指针还原回去printEdge(cur.left);  //第二次来到这个节点，逆序打印左树右边界（相当与链表逆序过程）}}printEdge(head);    //跑完后单独打印整棵树的右边界cur = cur.right;  //当前树没有左子树，直接向右移动}}private static void printEdge(TreeNode left) {}//Morris中序遍历改造public static boolean isValidBST(TreeNode head) {if (head == null) return true;TreeNode cur = head;TreeNode mostRight = null;int preValue = Integer.MIN_VALUE;while (cur != null) {mostRight = cur.left;if (mostRight != null) {   //有左子树while (mostRight.right != null && mostRight.right != cur) {  //能够往右走且不回到当前节点mostRight = mostRight.right;  //循环结束到达cur左树最右节点}if (mostRight.right == null) {  //第一次来到curmostRight.right = cur;  //最右节点指针指向当前节点curcur = cur.left;  //cur向左孩子移动continue;  //继续进行循环} else {    //不是第一次来到当前节点，而是顺着左树最右指针来的  mostRight.right ==cur;mostRight.right = null; //将右指针还原回去}}
//            System.out.println(cur.val);  //没有左树，或者第二次来到该节点打印if (cur.val <= preValue) {return false;}preValue = cur.val;cur = cur.right;  //当前树没有左子树，直接向右移动}return true;}

有序表

log（N）时机复杂度

红黑树
AVL树
SB树
跳表

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-C9b6HZmj-1665219082165)(C:\Users\DFL\AppData\Roaming\Typora\typora-user-images\image-20221007004239373.png)]

不用大于24是因为，24是6、8最小公倍数，能用三个8号袋子装何必要用4个6号袋子装，比如剩27个，不管用哪个袋子装，最后都会剩3个，何必要用6号袋子，并且这个剩余3个苹果的情况在多使用3个8号袋子时也计算过了。

打表法YYDS

网上那些写数学题解的都是垃圾货色，都是打表看出规律后再想的数学解释，就是为了装逼，让你佩服他

/*** 牛羊每次吃4的整数幂的草，谁最后吃谁赢*/
public class Winner {public static String winner1(int n) {if (n < 5) {return (n == 0 || n == 2) ? "后手" : "先手";}int base = 1;  //先手决定吃的草while (base >= 0) {if (winner1(n - base).equals("后手")) {return "先手";}if (base > n / 4) {break;}base *= 4;}return "后手";}public static String winner2(int n) {if (n % 5 == 0 || (n - 2) % 5 == 0) {return "后手";}return "先手";}public static void main(String[] args) {for (int i = 0; i <= 50; i++) {
//            System.out.println(i + " : " + winner1(i));System.out.println(i + " : " + winner2(i));}}
}

提升班习题课

表格预处理
根据一个随机函数，返回另一个随机函数

/*** 给定一个函数f，可以1～5的数字等概率返回一个。请加工出1～7的数字等概率返回一个的函数g。* 给定一个函数f，可以a~b的数字等概率返回一个。请加工出c～d的数字等概率返回一个的函数g。* 给定一个函数f，以p概率返回0，以1-p概率返回1。请加工出等概率返回0和1的函数g*/
public class Random {//以1～5的数字等概率返回一个public static int f() {return 0;  //空实现}//0、1随机发生器public static int g01() {int res = 0;do {res = f();} while (res == 3);return res < 3 ? 0 : 1;}//准备3个二进制位public static int g17() {int res = 0;do {res = g01() << 2 + g01() << 1 + g01();  //随机返回0~6} while (res == 7);return res + 1;}//以13~21数字等概率返回一个public static int r() {return 0;  //空实现}//0、1随机发生器public static int r01() {int res = 0;do {res = r();} while (res == 21);return res < 17 ? 0 : 1;  //二分}//准备3个二进制位public static int g3059() {int res = 0;do {for (int i = 0; i < 5; i++) {res += (r() << i); //随机返回30~59  0~29}} while (res > 29);return res + 30;}//以p概率返回0，以1-p概率返回1。public static int fp() {  //调两次共四个结果 00、01、10、11  其中01、10为等概率事件return 0;   //空实现}public static int gp() {int res1 = - 1;int res2 = - 1;do {res1 = fp();res2 = fp();} while ((res1 ^ res2) == 0);return res1 == 0 ? 0 : 1;}
}

/*** 判断括号是否合法字符串		//变种题：求括号最大深度depth = 1()()  depth = 2(())  记录过程中count出现的最大值即可*/
public class LegalBracket {public static boolean checkBracket(String s) {if (s == null || s.length() == 0) return true;int count = 0;for (int i = 0; i < s.length(); i++) {      //左括号数量>=右括号数量 每个右括号都有左括号可配if (count < 0) return false;count = s.charAt(i) == '(' ? count + 1 : count - 1;}return count == 0;}
/*** 添加多少括号可以让字符串括号合法*/public static int addBracket(String s) {int count = 0;int ans = 0;for (int i = 0; i < s.length(); i++) {      //左括号数量>=右括号数量 每个右括号都有左括号可配if (s.charAt(i) == '(') {count++;} else {            //遇到了右括号，如果此时count==0，说明原来刚好够，所以加上现在这个后需要补一个括号，即ans++;if (count == 0) { //count不加了ans++;          //补个左括号} else {count--;}}}//count 含义 左括号有多少没对上，ans含义 左括号缺了几个return ans+count; // count>=0 ((((((()))  count = 4 ，ans = 0； ((())))))) count = 0，ans = 4；}
}/*** n个节点的二叉树数量所包含的结构种类个数*/public static int numsTres1(int n) {return process1(n);}private static int process1(int n) {if (n == 0) return 1;if (n == 1) return 1;if (n == 2) return 2;int res = 0;for (int leftNum = 0; leftNum <= n - 1; leftNum++) {int leftWays = process1(leftNum);int rightWays = process1(n - 1 - leftNum);res += leftWays * rightWays;}return res;}//dppublic static int numsTres2(int n) {if (n < 2) return 1;int[] dp = new int[n + 1]; //0~n;dp[0] = 1;  //0个节点，空树for (int i = 1; i <= n; i++) {  //枚举总的节点个数，0、1、2、3.。。。。n个数为多少for (int j = 0; j <= i-1; j++) {  //枚举左孩子数量dp[i] += dp[j] * dp[i - j - 1];}}return dp[n];}/*** 集合a、b 可以从任一集合中拿出一元素x放入另一个集合中，两个集合平均值都变大，进行此magic的操作次数最多*/
public class MagicOps {//  a、b平均值a'、b' 且 a'>b'  从a中拿 x满足 b'<x<a'且x在b中不存在  拿走满足条件的最小元素（吊车尾）public static int maxOps(int[] arr1, int[] arr2) {double sum1 = 0;for (int i = 0; i < arr1.length; i++) {sum1 += (double) arr1[i];}double sum2 = 0;for (int i = 0; i < arr2.length; i++) {sum2 += (double) arr2[i];}if (avg(sum1, arr1.length) == avg(sum2, arr2.length)) {return 0;}//平均值不相等int[] arrMore = null;int[] arrLess = null;double sumMore = 0;double sumLess = 0;if (avg(sum1, arr1.length) > avg(sum2, arr2.length)) {        //重定位,可以不用写一堆if-elsearrMore = arr1;sumMore = sum1;arrLess = arr2;sumLess = sum2;} else {arrMore = arr2;sumMore = sum2;arrLess = arr1;sumLess = sum1;}Arrays.sort(arrMore);  //依次选出大于平均值的最小值HashSet<Integer> setLess = new HashSet<>();  //登记一下，保证所加元素在小集合中没出现过，出现过将导致加入后小集合平均值不变for (int i : arrLess) {setLess.add(i);}int moreSize = arrMore.length;  //平均值大的集合还剩几个元素int leseSize = arrLess.length;  //平均值小的集合还剩几个元素int ops = 0; //操作了几次for (int i = 0; i < arrMore.length; i++) {double cur = (double) arrMore[i];if (cur < avg(sumMore, moreSize) && cur > avg(sumLess, leseSize)&& ! setLess.contains(cur)) {sumMore -= cur;moreSize--;sumLess += cur;leseSize++;setLess.add(arrMore[i]);  //set泛型为整型ops++;}}return ops;}private static double avg(double sum, int size) {return (double) (sum / size);}
}/*** 最长合法括号子串					leetcode32题，有难度，多画图。*/
public class LongestValidParentheses {//子串必须由当前字符结尾，最长有效长度是多少？  dp[i]含义public static int longestValidParentheses(String s) {if (s == null || s == "") return 0;char[] str = s.toCharArray();int[] dp = new int[s.length() + 1];int res = 0;int pre = 0;for (int i = 1; i < s.length(); i++) {      //i=0位置必是0，不用算if (str[i] == ')') {       //必须由右括号结尾才进行//    i前一个位置，根据该位置的值往前数dp[i-1]个长度（该位置算出的有效长度）pre = i - dp[i - 1] - 1;    //这个位置不是左括号就肯定是0（（ {）} { 这一坨为i-1结尾有效长度 }  ） 如果第一个大括号位置不是'(' 肯定会把第二个大括号有效长度变大if (pre >= 0 && str[pre] == '(') {//      起码是2这个长度，再加上dp[i-1]前面i-1位置算过的长度，//      还有可能更多 {（（））}（（）），后面大括号位置就是pre-1dp[i] = dp[i - 1] + 2 + (pre > 0 ? dp[pre - 1] : 0);}}res = Math.max(res, dp[i]);}return res;}
}/***使用一个辅助栈完成原始栈的排序：栈顶到栈底从大到小。*允许使用一个辅助栈，可以申请变量，但不能使用其他数据结构。*解题思路：辅助栈一直维持由上至下从小到大  ，最终结果由大到小*/
public class StackSort {public static void sort(Stack<Integer> stack) {Stack<Integer> help = new Stack<>();help.push(stack.pop());int cur = 0;while (! stack.isEmpty()) {cur = stack.pop();  //记住弹出这个值while (! help.isEmpty() && cur > help.peek()) {  //辅助栈一直维持由上至下从小到大stack.push(help.pop());}help.push(cur);     //弹够了，可以压入了}while (! help.isEmpty()) {stack.push(help.pop());}}

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-SpNbZx2x-1665219082165)(C:\Users\DFL\AppData\Roaming\Typora\typora-user-images\image-20221008153839135.png)]

数组矩阵调整问题

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ghqlTKzi-1665219082166)(C:\Users\DFL\AppData\Roaming\Typora\typora-user-images\image-20221008154247851.png)]

左上角下标、右上角下标，沿对角线向内移动，错过去时停止

螺旋打印矩阵

分组

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Aovu9IlQ-1665219082166)(C:\Users\DFL\AppData\Roaming\Typora\typora-user-images\image-20221008161002688.png)]
arrLess = arr2;
sumLess = sum2;
} else {
arrMore = arr2;
sumMore = sum2;
arrLess = arr1;
sumLess = sum1;
}
Arrays.sort(arrMore); //依次选出大于平均值的最小值
HashSet setLess = new HashSet<>(); //登记一下，保证所加元素在小集合中没出现过，出现过将导致加入后小集合平均值不变
for (int i : arrLess) {
setLess.add(i);
}
int moreSize = arrMore.length; //平均值大的集合还剩几个元素
int leseSize = arrLess.length; //平均值小的集合还剩几个元素
int ops = 0; //操作了几次
for (int i = 0; i < arrMore.length; i++) {
double cur = (double) arrMore[i];
if (cur < avg(sumMore, moreSize) && cur > avg(sumLess, leseSize)
&& ! setLess.contains(cur)) {
sumMore -= cur;
moreSize–;
sumLess += cur;
leseSize++;
setLess.add(arrMore[i]); //set泛型为整型
ops++;

        }}return ops;
}private static double avg(double sum, int size) {return (double) (sum / size);
}

}

/**

最长合法括号子串 leetcode32题，有难度，多画图。
*/
public class LongestValidParentheses {
//子串必须由当前字符结尾，最长有效长度是多少？ dp[i]含义
public static int longestValidParentheses(String s) {
if (s == null || s == “”) return 0;
char[] str = s.toCharArray();
int[] dp = new int[s.length() + 1];
int res = 0;
int pre = 0;
for (int i = 1; i < s.length(); i++) { //i=0位置必是0，不用算
if (str[i] == ‘)’) { //必须由右括号结尾才进行
// i前一个位置，根据该位置的值往前数dp[i-1]个长度（该位置算出的有效长度）
pre = i - dp[i - 1] - 1; //这个位置不是左括号就肯定是0（（ {）} { 这一坨为i-1结尾有效长度 } ）如果第一个大括号位置不是’(’ 肯定会把第二个大括号有效长度变大
if (pre >= 0 && str[pre] == ‘(’) {
// 起码是2这个长度，再加上dp[i-1]前面i-1位置算过的长度，
// 还有可能更多 {（（））}（（）），后面大括号位置就是pre-1
dp[i] = dp[i - 1] + 2 + (pre > 0 ? dp[pre - 1] : 0);
}
}
res = Math.max(res, dp[i]);
}
return res;
}
}

/**
*使用一个辅助栈完成原始栈的排序：栈顶到栈底从大到小。
*允许使用一个辅助栈，可以申请变量，但不能使用其他数据结构。
*解题思路：辅助栈一直维持由上至下从小到大，最终结果由大到小
*/
public class StackSort {
public static void sort(Stack stack) {
Stack help = new Stack<>();
help.push(stack.pop());
int cur = 0;
while (! stack.isEmpty()) {
cur = stack.pop(); //记住弹出这个值
while (! help.isEmpty() && cur > help.peek()) { //辅助栈一直维持由上至下从小到大
stack.push(help.pop());
}
help.push(cur); //弹够了，可以压入了
}
while (! help.isEmpty()) {
stack.push(help.pop());
}
}


[外链图片转存中...(img-SpNbZx2x-1665219082165)]### 数组矩阵调整问题[外链图片转存中...(img-ghqlTKzi-1665219082166)]左上角下标、右上角下标， 沿对角线向内移动，错过去时停止螺旋打印矩阵<img src="C:\Users\DFL\AppData\Roaming\Typora\typora-user-images\image-20221008155202857.png" alt="image-20221008155202857" style="zoom:50%;" />分组[外链图片转存中...(img-Aovu9IlQ-1665219082166)]

左程云算法题一些leetcode练习题总结