说明：题目来源网络，由于本人水平有限，代码可能存在错误，欢迎指正
文章目录
- 笔试题
- 1. 排序算法
- 冒泡排序
- 选择排序
- 插入排序
- 归并排序
- 快速排序
- 堆排序
- 2. LeetCode
- 2.1 字符串
- :star:比较版本号
- 2.2 双指针
- :star:通配符匹配
- 有序数组的 Two Sum
- 两数平方和
- 反转字符串中的元音
- 回文串判断
- :star:最长回文子串
- 归并两个有序数组
- 判断链表是否有环
- :star:最长子序列
- :star:三数之和
- :star:[ 调整数组顺序使奇数位于偶数前面](https://leetcode-cn.com/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof/)
- 2.3 排序
- :star:topk问题
- 出现频率最多的k个元素
- 按颜色进行排序
- 2.4 贪心
- 分配饼干
- 不重叠的区间
- 投飞镖刺破气球
- 根据身高和序号重组队列
- :star:买卖股票最大的收益
- :star:买卖股票的最大收益2
- :star:判断是否为子序列
- 2.5 滑动窗口
- :star:无重复字符的最长子串
- :star:最小覆盖子串
- 2.6 二分查找
- :star:实现sqrt
- 大于给定元素的最小元素
- 有序数组中的单一元素
- :star:搜索旋转排序数组
- :star:寻找旋转数组的最小数字
- :star:在排序数组中查找元素的第一个和最后一个位置
- 2.7 BFS
- 计算在网络中从原点到特定点的最短路径
- 2.8 DFS
- 查找最大连通面积
- 2.9 Backtracking
- :star:复原IP地址
- 数字的排列组合
- :star:组合总和
- :star: 子集
- 3.0 动态规划
- :star:[最长重复子数组](https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/)
- 爬楼梯
- 强盗抢劫
- 矩阵的最小路径和
- 矩阵的路径数
- :star:最大子序和
- :star:最长公共子序列
- :star:最长递增子序列
- 划分数组为和相等的两部分
- 删除字符串的字符是他们相等
- :star:接雨水
- :star:硬币兑换
- 3.1 数学
- :star:用rand7()实现rand10()
- 二进制相加
- :star:字符串相加
- 数组中出现次数多于一半的元素
- 3.2 链表
- :star:删除链表重复元素
- :star:删除链表重复元素2
- 找出两个链表的交点
- 链表反转
- :star:归并两个有序链表
- 链表求和
- :star:K个一组翻转链表
- :star:环形链表2
- :star: 链表的倒数第k个节点
- :star: 反转链表2
- :star:合并K个有序链表
- :star:判断回文链表
- :star:重排链表
- 3.3 栈
- 实现计算器
- 用栈实现队列
- 用队列实现栈
- :star:括号匹配
- :star:基本计算器
- 3.4 队列
- :star:[滑动窗口最大值](https://leetcode-cn.com/problems/sliding-window-maximum/)
- 3.5 数组
- :star:缺失的第一个正数
- :star:[搜索二维矩阵 II](https://leetcode-cn.com/problems/search-a-2d-matrix-ii/)
- :star:[下一个排列](https://leetcode-cn.com/problems/next-permutation/)
- :star:多数元素
- :star:合并区间
- :star:移动字符串的 全部*号到左侧
- :star:螺旋矩阵
- :star:旋转图像
- 3.6 位运算
- 现在有一个数组，里面有一个数出现了奇数次，剩下的数出现偶数次，怎么找出这个数？
- 3.7 二叉树
- :star:验证二叉搜索树
- :star:判断对称二叉树
- :star:翻转二叉树
- :star:二叉树的层次遍历
- :star:二叉树的锯齿形打印
- :star:二叉树的最近公共祖先
- :star:二叉树的中序遍历
- :star:先序遍历非递归
- :star:后续遍历非递归
- :star:二叉树的最大深度
- :star:判断平衡二叉树
- :star:二叉树的最大路径和
- :star:路径总和2
- :star:从前序遍历和中序遍历构造二叉树
- :star:二叉树的直径
- :star:[求根节点到叶节点数字之和](https://leetcode-cn.com/problems/sum-root-to-leaf-numbers/)
- :star:路径总和2
- :star:从前序遍历和中序遍历构造二叉树
- :star:二叉树的直径
- :star:[求根节点到叶节点数字之和](https://leetcode-cn.com/problems/sum-root-to-leaf-numbers/)
- 最后：保姆级的Java教程和项目推荐
字节：链接
存在n+1个房间，每个房间依次为房间1 2 3…i，每个房间都存在一个传送门，i房间的传送门可以把人传送到房间pi(1<=pi<=i),现在路人甲从房间1开始出发(当前房间1即第一次访问)，每次移动他有两种移动策略：
A. 如果访问过当前房间 i 偶数次，那么下一次移动到房间i+1；
B. 如果访问过当前房间 i 奇数次，那么移动到房间pi；
现在路人甲想知道移动到房间n+1一共需要多少次移动；
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] strategy = new int[n + 1];
for(int i = 1; i <= n; i++){
strategy[i] = scanner.nextInt();
}
System.out.println(step(n, strategy));
}
private static long step(int n, int[] strategy){
//思路：到达i时，i前面的所有房间必定访问了偶数次
long[] dp = new long[n + 2];//存储第一次到房间i所需步数
dp[1] = 0;
if(n == 1)return 1;
long mod = 1000000007;
for(int i = 2; i <= n + 1; i++){
//dp[i] = dp[i-1] + dp[i-1] + 1 - dp[p[i-1]] + 1
dp[i] = (2*dp[i - 1])%mod - dp[strategy[i - 1]] + 2;
}
return dp[n + 1]%mod;
}
}
1. 排序算法
冒泡排序
沉石法，大的往后交换。
优化：外循环每次判断上次是否发生交换，如果没交换可以提前结束排序。
public class BubbleSort {
public static void main(String[] args) {
int[] arr = new int[]{2, 5, 3, 9, 1};
sort(arr);
for (int i : arr) {
System.out.println(i);
}
}
public static void sort(int[] arr){
int len = arr.length;
for (int i = 0; i < len; i++) {
//0-4
for(int j = 0; j < len - i - 1; j++){//注意这里的len - i - 1
if(arr[j] > arr[j + 1]){
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
}
选择排序
**从数组中选择最小元素，将它与数组的第一个元素交换位置。再从数组剩下的元素中选择出最小的元素，将它与数组 的第二个元素交换位置。**不断进行这样的 *** 作，直到将整个数组排序。 选择排序需要 ~N2 /2 次比较和 ~N 次交换，它的运行时间与输入无关，这个特点使得它对一个已经排序的数组也需要 这么多的比较和交换 *** 作
public class SelectSort {
public static void main(String[] args) {
int[] arr = new int[]{2, 5, 3, 9, 1};
sort(arr);
for (int i : arr) {
System.out.println(i);
}
}
private static void sort(int[] arr){
int len = arr.length;
for(int i = 0; i < len; i++){
int min = i;
for(int j = i + 1; j < len; j++){
if(arr[min] > arr[j]){
min = j;
}
}
swap(arr, min, i);
}
}
private static void swap(int[] arr, int i, int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
插入排序
每次都将当前元素插入到左侧已经排序的数组中，使得插入之后左侧数组依然有序。对于数组 {3, 5, 2, 4, 1}，它具有以下逆序：(3, 2), (3, 1), (5, 2), (5, 4), (5, 1), (2, 1), (4, 1)，插入排序每次只能交换相邻 元素，令逆序数量减少 1，因此插入排序需要交换的次数为逆序数量。
public class InserSort {
public static void main(String[] args) {
int[] arr = new int[]{2, 5, 3, 9, 1};
sort(arr);
for (int i : arr) {
System.out.println(i);
}
}
private static void sort(int[] arr){
int len = arr.length;
for(int i = 1; i < len; i++){//从第1个往前插
for(int j = i; j > 0; j--){
if(arr[j] < arr[j - 1]){
swap(arr, j, j - 1);
}else{
break;
}
}
}
}
private static void swap(int[] arr, int i, int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
归并排序
- 思路：使用递归分别排好左右两侧顺序，再使用merge合并，将排好序的help数组拷贝进原数组对应位置
- 思想：分治
public class MergeSort {
public static void main(String[] args) {
int[] arr = new int[]{2, 5, 3, 9, 1};
sort(arr, 0, arr.length - 1);
for (int i : arr) {
System.out.println(i);
}
}
private static void sort(int[] arr, int low, int high){
if(low == high) return;
int mid = low + (high - low)/2;
sort(arr, low, mid);
sort(arr, mid + 1, high);
merge(arr, low, mid, high);
}
private static void merge(int[] arr, int left, int mid, int right){
int[] temp = new int[right - left + 1];
int p1 = left;//左侧数组起点
int p2 = mid + 1;//右侧数组起点
int i = 0; //temp下标
//简单的双指针遍历
while(p1 <= mid && p2 <= right){
temp[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
}
//剩余部分:两个之一
while(p1 <= mid){
temp[i++] = arr[p1++];
}
while(p2 <= right){
temp[i++] = arr[p2++];
}
//拷贝回去
for(int j = 0; j < temp.length; j++){
arr[left + j] = temp[j];
}
}
}
快速排序
- 经典快排
public class ClassicQuickSort {
public static void main(String[] args) {
int[] arr = new int[]{2, 5, 3, 9, 1};
sort(arr, 0, arr.length - 1);
for (int i : arr) {
System.out.println(i);
}
}
private static void sort(int[] arr, int l, int r){
if(l < r){
int p = partition(arr, l, r);
sort(arr, l, p - 1);
sort(arr, p + 1, r);
}
}
private static int partition(int[] arr, int l, int r){
int less = l - 1;
while(l < r){
if(arr[l] < arr[r]){
swap(arr, ++less, l++);
}else{
l++;
}
}
swap(arr, less + 1, r);
return less + 1;
}
private static void swap(int[] arr, int i, int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
- 随机快排 + 荷兰国旗三向切分partition优化
public class QuickSort {
public static void main(String[] args) {
int[] arr = new int[]{2, 5, 3, 9, 1};
sort(arr, 0, arr.length - 1);
for (int i : arr) {
System.out.println(i);
}
}
private static void sort(int[] arr, int left, int right){
if(left >= right) return;//靠，这里很关键，必须判断大小，不然下面返回的less、more可能会越界
int x = left + (int) (Math.random() * (right - left + 1));
swap(arr, x, right);
int[] p = partition(arr, left, right);
sort(arr, left, p[0]);
sort(arr, p[1], right);
}
private static int[] partition(int[] arr, int left, int right){
int less = left - 1;
int more = right;//为什么是right，因为right是不遍历的下标，最后要交换
while(left < more){
if(arr[left] < arr[right]){
swap(arr, ++less, left++);
}else if( arr[left] > arr[right]){
swap(arr, --more, left);
}else{
left++;
}
}
swap(arr, more, right);
return new int[]{less, more + 1};
}
private static void swap(int[] arr, int i, int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
堆排序
Min-heap: 父节点的值小于或等于子节点的值；
Max-heap: 父节点的值大于或等于子节点的值；
- 创建一个堆 H[0……n-1]；
- 创建一个大根堆
- 堆顶和堆尾交换：即每次把最大值放在最后
- 重复第三步骤
多种实现方式：个人觉得下面方式最为简单
注意：建立大根堆、小根堆有两种方式，第一种叫heapInsert，称为上浮，时间复杂度为o(nlogn)，第二种为heapify，即下沉，时间复杂度为O(n)，建议用heapify,因为
public class HeapSort {
public static void main(String[] args) {
int[] arr = new int[]{2, 5, 3, 9, 1};
buildMaxHeap(arr);
for(int i = arr.length - 1; i > 0; i--){
swap(arr, i, 0);
heapify(arr, 0, i);//注意这里的heapSize
}
for (int i : arr) {
System.out.println(i);
}
}
private static void buildMaxHeap(int[] arr){
// int len = arr.length;
// for(int i = 0; i < len; i++){//heapInsert：向上调整
// while(arr[i] > arr[(i - 1) / 2]){
// swap(arr, i, (i - 1) / 2);
// i = (i - 1) / 2;
// }
// }
for(int i = arr.length/2; i >= 0; i--){
heapify(arr, i, arr.length);
}
}
private static void heapify(int[] arr, int i, int heapSize){
// int l = i * 2 + 1;
// while(l < heapSize){//非递归实现
// int large = l + 1 <= heapSize && arr[l] > arr[l + 1] ? l : l + 1;
// large = arr[large] > arr[i] ? large : i;
// if(large == i) break;//自己最大，退出
// swap(arr, large, i);
// i = large; //新node
// l = i * 2 + 1; //新左儿子
// }
int l = i * 2 + 1, r = i * 2 + 2, largest = i; //l:左孩子，r：右孩子，i:父节点
if (l < heapSize && arr[l] > arr[largest]) {
largest = l; //先与左孩子比较
}
if (r < heapSize && arr[r] > arr[largest]) {
largest = r;//再与右孩子比较
}
if (largest != i) {//如果孩子节点更大，交换
swap(arr, i, largest);
heapify(arr, largest, heapSize); //递归调整下一个子树
}
}
private static void swap(int[] arr, int i, int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
2. LeetCode
2.1 字符串
⭐️比较版本号
给你两个版本号 version1 和 version2 ，请你比较它们。
版本号由一个或多个修订号组成，各修订号由一个 ‘.’ 连接。每个修订号由 多位数字 组成，可能包含 前导零 。每个版本号至少包含一个字符。修订号从左到右编号，下标从 0 开始，最左边的修订号下标为 0 ，下一个修订号下标为 1 ，以此类推。例如，2.5.33 和 0.1 都是有效的版本号。
比较版本号时，请按从左到右的顺序依次比较它们的修订号。比较修订号时，只需比较 忽略任何前导零后的整数值 。也就是说，修订号 1 和修订号 001 相等 。如果版本号没有指定某个下标处的修订号，则该修订号视为 0 。例如，版本 1.0 小于版本 1.1 ，因为它们下标为 0 的修订号相同，而下标为 1 的修订号分别为 0 和 1 ，0 < 1 。
返回规则如下：
如果 version1 > version2 返回 1，
如果 version1 < version2 返回 -1，
除此之外返回 0。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/compare-version-numbers
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
法一：借助split方法
class Solution {
public int compareVersion(String version1, String version2) {
String[] v1 = version1.split("\.");
String[] v2 = version2.split("\.");
int len1 = v1.length;
int len2 = v2.length;
int i = 0;
while(i < len1 && i < len2){
int num1 = Integer.parseInt(v1[i]);
int num2 = Integer.parseInt(v2[i]);
if(num1 == num2){
i++;
}else if(num1 > num2){
return 1;
}else{
return -1;
}
}
while(i < len2){
if(Integer.parseInt(v2[i]) != 0){
return -1;
}
i++;
}
while(i < len1){
if(Integer.parseInt(v1[i]) != 0){
return 1;
}
i++;
}
return 0;
}
}
法二：不使用split
class Solution {
public int compareVersion(String version1, String version2) {
int i = 0, j = 0;
int v1Len = version1.length(), v2Len = version2.length();
while (i < v1Len || j < v2Len) {
int a = 0, b = 0;
while (i < v1Len && version1.charAt(i) != '.') {
a = a * 10 + version1.charAt(i) - '0';
i++;
}
while (j < v2Len && version2.charAt(j) != '.') {
b = b * 10 + version2.charAt(j) - '0';
j++;
}
if (a > b) {
return 1;
} else if (a < b) {
return -1;
}
i++;
j++;
}
return 0;
}
}
2.2 双指针
⭐️通配符匹配
class Solution {
public boolean isMatch(String s, String p) {
if (p==null||p.isEmpty())return s==null||s.isEmpty();
int i=0,j=0, istart=-1, jstart=-1,slen=s.length(),plen=p.length();
//判断s的所有字符是否匹配
while (i-1){
//不匹配且有*时，用*去抵消，并记录下一个*的匹配位置
istart++;
i=istart;
j=jstart+1;
}else {
return false;
}
}
//s中的字符都判断完毕，此时需要p为空或者p中只剩下星号的时候，才能成功匹配。
//如果p中剩余的都是*，则可以移除剩余的*
//说明：在将s匹配完的情况下，如果j能够到达末尾，说明匹配是成功的
while (j
有序数组的 Two Sum
- 题目描述：在有序数组中找出两个数，使它们的和为 target。
public class TwoSum {
//题目描述：在有序数组中找出两个数，使它们的和为 target。
public static void main(String[] args) {
int[] arr = new int[]{1, 3, 5, 6};
int[] ans = solution(arr, 8);
for (int i : ans) {
System.out.println(arr[i]);
}
}
private static int[] solution(int[] arr, int target){
int len = arr.length;
int l = 0, r = len - 1;
while(l < r){
if(arr[l] + arr[r] > target){
r--;
}else if(arr[l] + arr[r] < target){
l++;
}else{
break;
}
}
return new int[]{l, r};
}
}
两数平方和
- 题目描述：判断一个数是否为两个数的平方和。
public class SumOfSquare{
// 题目描述：判断一个数是否为两个数的平方和。
public static void main(String[] args) {
int a = 4;
int b = 5;
int c = 3;
System.out.println(solution(a));
System.out.println(solution(b));
System.out.println(solution(c));
}
private static boolean solution(int num){
int i = 0;
// int j = num/2;
int j = (int) Math.sqrt(num);
while(i <= j){
if(i * i + j * j == num){
return true;
}else if(i * i + j * j > num){
j--;
}else{
i++;
}
}
return false;
}
}
反转字符串中的元音
- 使用双指针指向待反转的两个元音字符，一个指针从头向尾遍历，一个指针从尾到头遍历。
import java.util.Arrays;
import java.util.Set;
import java.util.HashSet;
public class ReverseVowelOfString {
//编写一个函数，该函数将字符串作为输入，并且仅反转字符串的元音。
public static void main(String[] args) {
String str1 = solution("hello");
String str2 = solution("leetcode");
System.out.println(str1);
System.out.println(str2);
}
public static String solution(String str){
Set set = new HashSet<>(
Arrays.asList('a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U')
);
int l = 0;
int r = str.length() - 1;
char[] ans = new char[str.length()];
while(l <= r){
Character L = Character.valueOf(str.charAt(l));
Character R = Character.valueOf(str.charAt(r));
if(!set.contains(L)){
ans[l++] = L;
}else if(!set.contains(R)){
ans[r--] = R;
}else{ //(set.contains(L) && set.contains(R))
ans[l++] = R;
ans[r--] = L;
}
}
return new String(ans);
}
}
回文串判断
- 题目描述：可以删除一个字符，判断是否能构成回文字符串。
public class ValidPalindrome {
//题目描述：可以删除一个字符，判断是否能构成回文字符串。
public static void main(String[] args) {
String str1 = "abba";
String str2 = "abab";
String str3 = "abbc";
System.out.println(check1(str1));
System.out.println(check1(str2));
System.out.println(check1(str3));
}
//可以删除情况
public static boolean check1(String str) {
int l = 0, r = str.length() - 1;
while( l < r){
if(str.charAt(l) != str.charAt(r)){
return check2(str, l + 1, r) || check2(str, l, r - 1);
}
l++;
r--;
}
return true;
}
//不能删除情况
private static boolean check2(String str, int l, int r){
while(l < r){
if(str.charAt(l) != str.charAt(r)){
return false;
}
l++;
r--;
}
return true;
}
}
⭐️最长回文子串
- 理解题意
- 题目给定一个字符串
- 需要我们找到这个字符串中的最长回文串
- 回文串：正着读和反着读都一样的字符串
- 整体思路
- 我根据回文串的一个核心思想来解题：从中心点往两边扩散，来寻找回文串，这种方向相当于穷举每一个点为中心点
- 如果回文串是奇数时，比如 “bab” ，它的中心点就只有一个 “a”，所以从 “a” 开始向两边扩散
- 如果回文串是偶数时，比如 “baab”，它的中心点有两个 “aa”，所以从 “aa” 开始向两边扩散
- 编写一个辅助函数来寻找回文串，当中心点确定了之后调用辅助函数，直接返回找到的回文串
- 将每次找到的回文串与之前的做对比，谁长就留谁
public class LongestPalindrome {
public static void main(String[] args) {
String str = "abbbaccabba";
System.out.println(solution(str));//bbaccabb
}
private static String solution(String str){
if(str == null || "".equals(str))return "";
String res = "";
for(int i = 0; i < str.length(); i++){
String s1 = find(str, i, i);//奇数
String s2 = find(str, i, i + 1);//偶数
res = res.length() > s1.length() ? res : s1;
res = res.length() > s2.length() ? res : s2;
}
return res;
}
// 查找回文串
private static String find(String s, int l, int r){
while(l >= 0 && r < s.length()){
if(s.charAt(l) == s.charAt(r)){
l--;
r++;
}else{
break;
}
}
return s.substring(l + 1, r);//注意substring是小写
}
}
归并两个有序数组
- 题目描述：把归并结果存到第一个数组上。
public class MergeSortedArray {
//归并有序数组,把归并结果存到第一个数组上
//注意：这题要求不使用额外空间，为了方便，从后面开始遍历，不需要交换
public static void main(String[] args) {
int[] arr1 = new int[]{1, 3 ,5, 6, 0, 0};
int[] arr2 = new int[]{2, 4};
solution(arr1, arr2);
for (int i : arr1) {
System.out.println(i);
}
}
private static void solution(int[] arr1, int[] arr2){
int i = arr1.length - 1;
int j = arr2.length - 1;
int k = i - j - 1; //arr1的真实size - 1
while(j >= 0 && k >= 0){
if(arr1[k] < arr2[j]){
arr1[i--] = arr2[j--];
}else{
arr1[i--] = arr1[k--];
}
}
}
}
判断链表是否有环
public class linkedListCycle{
//题目：判断链表是否存在环
//思路：看是否存在环
static class Node{
Integer val;
Node next;
Node(Integer val){
this.val = val;
}
}
//快慢指针
public static void main(String[] args) {
int[] arr = new int[]{1, 2 ,3, 4, 5, 6};
Node head = new Node(1);
Node p = head;
Node p2 = new Node(0);
Node tail = new Node(0);
for(int i = 1; i < arr.length; i++){//尾插法
Node temp = new Node(arr[i]);
p.next = temp;
p = p.next;
if(arr[i] == 2){
p2 = temp;
}
if(arr[i] == 6){
tail = temp;
}
}
//tail.next = p2; //加环
System.out.println(check(head));
}
private static boolean check(Node head){
Node p1 = head;
Node p2 = p1.next;
while(p2 != null && p2.next != null){
if(p1.val == p2.val){
return true;
}else{
p1 = p1.next;
p2 = p2.next.next;
}
}
return false;
}
}
⭐️最长子序列
- 题目描述：删除 s 中的一些字符，使得它构成字符串列表 d 中的一个字符串，找出能构成的最长字符串。如果有多个 相同长度的结果，返回字典序的最小字符串。
所谓的子序列就是在原来序列中找出一部分组成的序列。如：dabdbf的最长递增子序列是:abdf
public class FindLongestWord {
//题目描述：删除 s 中的一些字符，
//使得它构成字符串列表 d 中的一个字符串，找出能构成的最长字符串。如果有多个
//相同长度的结果，返回字典序的最小字符串。
//题解：通过删除字符串 s 中的一个字符能得到字符串 t，
//可以认为 t 是 s 的子序列，我们可以使用双指针来判断一个字符串
//是否为另一个字符串的子序列。
public static void main(String[] args) {
String s = "abpcpleaf";
String[] d = new String[]{"ale", "apple", "bleaf", "monkey", "plea"};
System.out.println(solution(s, d));
}
private static String solution(String s, String[] d){
int len = d.length;
String longMinSub = ""; //最长最小字典序子串
for(int i = 0; i < len; i++){
if(isSubStr(s, d[i])){
String temp = d[i];
int len1 = longMinSub.length();
int len2 = temp.length();
if(len1 < len2){
longMinSub = temp;
}else if(len1 == len2){
if(longMinSub.compareTo(temp) > 0){
longMinSub = temp;
}
}
}
}
return longMinSub;
}
private static boolean isSubStr(String s, String target){
//双指针法：判断 target 是否是 s 的子序列
int i = 0, j = 0;
while(i < s.length() && j < target.length()){
if(s.charAt(i) == target.charAt(j)){
j++; //j匹配上才++
}
i++; //i不管是否匹配都要++
}
return j == target.length();
}
}
⭐️三数之和
题目描述：找数组中三个数相加等于零的
时间复杂度O(n^2)
import java.util.*;
public class ThreeAdd {
// 三数相加
public static void main(String[] args) {
int[] arr = {-1,0,1,2,-1,4};
List> ans = solution(arr);
Iterator> iterator = ans.iterator();
while(iterator.hasNext()){
List list = iterator.next();
Iterator temp = list.iterator();
while(temp.hasNext()){
System.out.print(temp.next() + " ");
}
System.err.println();
}
}
private static List> solution(int[] arr){
// 算法：排序+双指针,O(n^2)
if(arr == null || arr.length == 0)return null;
int len = arr.length;
Arrays.sort(arr);
List> ans = new ArrayList<>();
for(int i = 0; i < len - 2; i++){ //注意 len - 2即可
if(i > 0 && arr[i] == arr[i - 1]) continue; //相等的元素跳过
int target = - arr[i]; // a + b == target
int left = i + 1, right = len - 1;
while(left < right){
if(arr[left] + arr[right] == target){
ans.add(Arrays.asList(arr[i], arr[left], arr[right]));
left++;
right--;
while(left < right && arr[left] == arr[left - 1])left++;//相等的元素跳过
while(left < right && arr[right] == arr[right + 1])right--;//相等的元素跳过
}else if(arr[left] + arr[right] > target){
right--;
}else{
left++;
}
}
}
return ans;
}
}
//-1 -1 2
//-1 0 1
⭐️ 调整数组顺序使奇数位于偶数前面
class Solution {
public int[] exchange(int[] nums) {
int left = 0; //left遇到偶数停下来
int right = nums.length - 1; //right遇到奇数停下来
while(left < right){
if(nums[left] % 2 == 1){
left++;
continue;//继续
}
if(nums[right] % 2 == 0){
right--;
continue;//继续
}
swap(nums, left++, right--);//交换
}
return nums;
}
public void swap(int[] arr, int i, int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
2.3 排序
⭐️topk问题
- 题目描述：找到第 k 大的元素。
堆排法，时间复杂度 O(NlogK)，空间复杂度 O(K)。
- topk （前k大）用小根堆，维护堆大小不超过 k 即可。每次压入堆前和堆顶元素比较，如果比堆顶元素还小，直接扔掉，否则压入堆。检查堆大小是否超过 k，如果超过，d出堆顶。复杂度是 nlogk
- 避免使用大根堆，因为你得把所有元素压入堆，复杂度是 nlogn，而且还浪费内存。如果是海量元素，那就挂了。
法一：大根堆实现（不建议）
public class FindTopK {
public static void main(String[] args) {
int[] arr = new int[]{3, 2, 1, 5 ,6 ,4};
int k = 2;
System.out.println(find(arr, k));
}
private static int find(int[] arr, int k){
//法1：用大根堆实现topk
int len = arr.length;
buildMaxHeap(arr);
while(k-- > 1){
swap(arr, 0, len - 1);
heapify(arr, 0, len - 1);
len--;
}
return arr[0];
}
private static void buildMaxHeap(int[] arr){
int len = arr.length;
for(int i = len/2; i >= 0; i--){
heapify(arr, i, len);
}
}
private static void heapify(int[] arr, int index, int heapSize){
int l = 2 * index + 1;
int largeIdx = index;
if(l < heapSize && arr[largeIdx] < arr[l]){
largeIdx = l;
}
if(l + 1 < heapSize && arr[largeIdx] < arr[l + 1]){
largeIdx = l + 1;
}
if(largeIdx != index){//需要交换才递归
swap(arr, largeIdx, index);
heapify(arr, largeIdx, heapSize);
}
}
private static void swap(int[] arr, int i, int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
法二：小根堆实现
package com.tosang.java;
import java.util.Arrays;
public class TopK {
public static void main(String[] args) {
int[] arr = new int[]{3,2,7,8,10,4};
System.out.println(solution(arr, 2));
}
public static int solution(int[] arr, int k){
//小根堆：大小为K
//1. 先对k个元素建立小根堆
for(int i = k / 2; i >= 0; i--){
heapify(arr, i, k);
}
//2.判断后续元素与堆顶的大小关系
for(int i = k; i < arr.length; i++){
if(arr[i] > arr[0]){
//3. 与堆顶交换
swap(arr, 0, i);
heapify(arr, 0, k);
}
}
return arr[0];
}
public static void heapify(int[] arr, int index, int heapSize){
int left = 2 * index + 1;
int right = 2 * index + 2;
int min = index;
if(left < heapSize && arr[index] > arr[left]){
min = left;
}
if(right < heapSize && arr[min] > arr[right]){
min = right;
}
if(min != index){
swap(arr, min, index);
heapify(arr, min, heapSize);
}
}
public static void swap(int[] arr, int a, int b){
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
}
法三：快排快速选择法，时间复杂度 O(N)，空间复杂度 O(1)
public class FindTopK2 {
//随机快排+三向切分partition版本
public static void main(String[] args) {
int[] arr = new int[]{3, 2, 1, 5 ,6 ,4};
System.out.println(quickSort(arr, 0, arr.length - 1, 1));
System.out.println(quickSort(arr, 0, arr.length - 1, 2));
System.out.println(quickSort(arr, 0, arr.length - 1, 3));
System.out.println(quickSort(arr, 0, arr.length - 1, 4));
System.out.println(quickSort(arr, 0, arr.length - 1, 5));
System.out.println(quickSort(arr, 0, arr.length - 1, 6));
}
private static int quickSort(int[] arr, int l, int r, int k){
int idx = l + (int)Math.random() * (r - l + 1);
swap(arr, idx, r);
int index = partition(arr, l, r);
if(index < arr.length - k){
return quickSort(arr, index + 1, r, k);
}else if(index > arr.length - k){
return quickSort(arr, l, index - 1, k);
}else{
return arr[index];
}
}
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 more;
}
private static void swap(int[] arr, int i, int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
出现频率最多的k个元素
- 思路：和topk原理一样，只不过多一个hash表来将频率转为个数。
注意：
- topk （前k大）用小根堆，维护堆大小不超过 k 即可。每次压入堆前和堆顶元素比较，如果比堆顶元素还小，直接扔掉，否则压入堆。检查堆大小是否超过 k，如果超过，d出堆顶。复杂度是 nlogk
- 避免使用大根堆，因为你得把所有元素压入堆，复杂度是 nlogn，而且还浪费内存。如果是海量元素，那就挂了。
[注意]
- 求前 k 大，用小根堆，求前 k 小，用大根堆。
import java.util.*;
public class TopKFrequent {//小根堆
public static void main(String[] args) {
int[] nums = new int[]{1, 1, 2, 2, 3};
int k = 2;
int[] ans = topKFrequent(nums, k);
for (int i : ans) {
System.out.println(i);
}
}
public static int[] topKFrequent(int[] nums, int k) {
Map occurrences = new HashMap();
for (int num : nums) {
occurrences.put(num, occurrences.getOrDefault(num, 0) + 1);
}
//技巧：int[] 的第一个元素代表数组的值，第二个元素代表了该值出现的次数
PriorityQueue queue = new PriorityQueue(new Comparator() {
public int compare(int[] m, int[] n) {
return m[1] - n[1];
}
});
for (Map.Entry entry : occurrences.entrySet()) {
int num = entry.getKey(), count = entry.getValue();
if (queue.size() == k) {
if (queue.peek()[1] < count) {
queue.poll();
queue.offer(new int[]{num, count});
}
} else {
queue.offer(new int[]{num, count});
}
}
int[] ret = new int[k];
for (int i = 0; i < k; ++i) {
ret[i] = queue.poll()[0];
}
return ret;
}
}
按颜色进行排序
- 题目描述：只有 0/1/2 三种颜色。
public class SortColor {
//荷兰国旗问题
public static void main(String[] args) {
int[] arr = new int[]{1, 2, 2, 1, 0, 0};
sort(arr);
for (int i : arr) {
System.out.println(i);
}
}
private static void sort(int[] arr){
int less = -1;
int more = arr.length;
int index = 0;
while(index < more){
if(arr[index] == 0){
swap(arr, ++less, index++);
}else if(arr[index] == 2){
swap(arr, --more, index);
}else{
index++;
}
}
}
private static void swap(int[] arr, int i ,int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
2.4 贪心
分配饼干
- 题目描述：每个孩子都有一个满足度，每个饼干都有一个大小，只有饼干的大小大于等于一个孩子的满足度，该孩子 才会获得满足。求解最多可以获得满足的孩子数量。
import java.util.*;
public class FindContentChildren {
public static void main(String[] args) {
int[] g = new int[]{1, 2};
int[] s = new int[]{1, 2, 3};
System.out.println(solution(g, s));
}
public static int solution(int[] g, int[] s) {
//贪心法，先排序后从小到大比较
Arrays.sort(g);
Arrays.sort(s);
int i = 0, j = 0;
int count = 0;
while(i < g.length && j < s.length){
if(s[j] >= g[i]){//满足
i++;
j++;
count++;
}else{
j++; //不满足，饼干++
}
}
return count;
}
}
不重叠的区间
- 给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。
- 注意：这题也可以按照左边界排序，不过遍历时必须从右往左。
import java.util.Arrays;
import java.util.Comparator;
public class EraseOverlapIntervals {
//题目描述：计算让一组区间不重叠所需要移除的区间个数。
public static void main(String[] args) {
int[][] arr = {{1, 2}, {2, 3}, {3, 4}, {1, 3}};
int[][] arr1 = {{1, 2}, {1, 2}, {1, 2}};
System.out.println(eraseOverlapIntervals(arr));
System.out.println(eraseOverlapIntervals(arr1));
}
public static int eraseOverlapIntervals(int[][] intervals) {
//按区间的结尾进行排序，每次选择结尾最小，并且和前一个区间不重叠的区间。
if (intervals.length == 0) {
return 0;
}
Arrays.sort(intervals, new Comparator(){
public int compare(int [] a1,int [] a2) {
return a1[1] - a2[1]; //右边界升序排列
}
});
int count = 1; //注意：目标是找到最多能组成的不重叠区间个数
int end = intervals[0][1];
for (int i = 0; i < intervals.length; i++) {
if (intervals[i][0] < end) {//每次选择最小的右边界和下一个左边界比较
continue;
}
end = intervals[i][1]; //不重叠，获得一个新的区间右边界
count++; //区间++
}
return intervals.length - count;
}
}
投飞镖刺破气球
思路：
- 先对右边界排序。
- 每次选择上一个重合区间的最小右边界和下一个区间的左边界比较，因为两个区间重合意味着一定是最小的右边界重合，故end每次选最小右边界以保证留给后面的区间的空间越大，那么后面能够选择的区间 个数也就越大。
import java.util.Arrays;
import java.util.Comparator;
public class FindMinArrowShots {
//题目描述：用最少数量的箭引爆气球
//寻找不重叠区间个数
public static void main(String[] args) {
int[][] points = new int[][]{{1, 2}, {2, 3}, {3, 4}, {4 ,5}};
System.out.println(solution(points));
}
private static int solution(int[][] points){
if(points.length == 0){
return 0;
}
int len = points.length;
Arrays.sort(points, new Comparator(){
@Override
public int compare(int[] arr1, int[] arr2){
return arr1[1] - arr2[1];
}
});
int count = 1;
int end = points[0][1];
for(int i = 1; i < len; i++){
if(points[i][0] <= end){
continue;
}
count++;
end = points[i][1];
}
return count;
}
}
根据身高和序号重组队列
- 题目描述：一个学生用两个分量 (h, k) 描述，h 表示身高，k 表示排在前面的有 k 个学生的身高比他高或者和他一样 高。
- 思路：在高的人前面插入矮的人不会影响原队列，但如果插入更高的人会影响原队列，故需要按身高降序，按k升序。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class QueueReconstruction {
// 题目描述：一个学生用两个分量 (h, k) 描述，h 表示身高，k 表示排在前面的有 k 个学生的身高比他高或者和他一样高。
public static void main(String[] args) {
int[][] arr = new int[][]{{7, 0}, {4, 4}, {7, 1}, {5, 0}, {6, 1}, {5, 2}};
int[][] ans = solution(arr);
for (int[] is : ans) {
System.out.println("[" + is[0] + "," + is[1] + "]");
}
}
private static int[][] solution(int[][] arr){
if(arr == null || arr.length == 0){
return new int[0][0];
}
Arrays.sort(arr, (a, b) -> a[0] == b[0] ? a[1] - b[1] : b[0] - a[0]);
List queue = new ArrayList<>();
for(int[] i : arr){
queue.add(i[1], i);
}
return queue.toArray(new int[queue.size()][]);
}
}
⭐️买卖股票最大的收益
-
题目描述：一次股票交易包含买入和卖出，只进行一次交易，求最大收益。
-
这题既可以用贪心，也可以用DP，思路一致，dp只不过用dp数组替换下面的max即可
public class MaxProfit {
//买卖股票的最佳时机
public static void main(String[] args) {
int[] arr = new int[]{7, 1, 5, 3, 6, 4};
int[] arr1 = new int[]{7, 6, 4, 3, 2, 1};
System.out.println(solution(arr));
System.out.println(solution(arr1));
}
private static int solution(int[] arr){
if(arr == null || arr.length <= 1){
return 0;
}
int min = arr[0];
int max = 0;
for(int i = 1; i < arr.length; i++){
if(arr[i] < min){
min = arr[i];
}else{
max = max > arr[i] - min ? max : arr[i] - min;
}
}
return max;
}
}
⭐️买卖股票的最大收益2
-
题目：允许多次买卖股票，求最大收益
-
题解：可以用贪心、dp，贪心每次买跌买涨，dp需要维护两个dp数组，分别为持有股票的收益和不持有股票的收益。
public class MaxProfit2 {
public static void main(String[] args) {
int[] prices = new int[]{7, 1, 5, 3, 6, 4};
int[] prices1 = new int[]{1, 2, 3, 4, 5};
System.out.println(solution1(prices));
System.out.println(solution1(prices1));
System.out.println(solution2(prices));
System.out.println(solution2(prices1));
}
private static int solution1(int[] arr){
// 贪心算法：买跌卖涨
int ans = 0;
if(arr == null || arr.length <= 1){
return 0;
}
for(int i = 1; i < arr.length; i++){
if(arr[i] > arr[i - 1]){//可以买入
ans += arr[i] - arr[i - 1];
}
}
return ans;
}
private static int solution2(int[] arr){
// 动态规划
if(arr == null || arr.length <= 1){
return 0;
}
int[][] dp = new int[arr.length][2];
dp[0][0] = 0; //不持股票
dp[0][1] = -arr[0]; //持有股票
for(int i = 1; i < arr.length; i++){
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + arr[i]);//max(昨天也没持有，昨天持有+今天卖了)
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - arr[i]);
}
return dp[arr.length - 1][0];
}
}
⭐️判断是否为子序列
public class IsSubSequence {
public static void main(String[] args) {
String s = "abc";
String t = "ahbgdc";
System.out.println(check(s, t));
}
private static boolean check(String s, String t){
int slen = s.length();
int tlen = t.length();
int i = 0, j = 0;
while(i < slen && j < tlen){
if(s.charAt(i) == t.charAt(j)){
i++;
j++;
}else{
j++;
}
}
return i == slen;
}
}
2.5 滑动窗口
⭐️无重复字符的最长子串
- 注意时间复杂度是 O(n)
class Solution {
public int lengthOfLongestSubstring(String s) {
if(s == null || s.length() == 0)return 0;
int len = s.length();
Set set = new HashSet<>();
int l = 0, r = 0; //滑动窗口区间
int ans = 0;
while(r < len){
while(set.contains(s.charAt(r))){//
set.remove(s.charAt(l++));
}
ans = Math.max(ans, r - l + 1);
set.add(s.charAt(r++));
}
return ans;
}
}
⭐️最小覆盖子串
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
示例：
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
class Solution {
public String minWindow(String s, String t) {
Map window = new HashMap(); // 用来记录窗口中的字符和数量
Map need = new HashMap(); // 需要凑齐的字符和数量
// 构建need字符集
for (int i = 0; i < t.length(); i++) {
char needChar = t.charAt(i);
need.put(needChar,need.getOrDefault(needChar,0)+1);
}
int left = 0,right = 0,valid = 0;
// valid是用来记录窗口中满足need要求的字符和数量的数目，比如need中要求字符a数量为2，如果window中的a字符的数量等于了2，valid就＋1，反之-1
int len = Integer.MAX_VALUE; // 记录最小字串的长度
int start = 0; // 记录最小字串的起始位置
while(right < s.length()){
char addChar = s.charAt(right); // 即将要加入window的字符
window.put(addChar,window.getOrDefault(addChar,0) + 1);
right++;
// 如果加入的字符是need中要求的字符，并且数量已经达到了need要求的数量，则valid+1
// 这里和下面都有个坑，window.get(addChar)和need.get(addChar)返回的都是对象，最好用.equals()方法比较大小
if(need.containsKey(addChar) && window.get(addChar).equals(need.get(addChar))){
valid++;
}
// 当window中记录的字符和数量满足了need中要求的字符和数量，考虑缩窗口
while(valid == need.size()){
// 先判断当前的最小覆盖字串是否比之前的最小覆盖字串短
if(right - left < len){ // 注意，这里上面已经对right实施了++操作，所以这里的长度不是right - left + 1
len = right - left ;
start = left; // 如果最短，则记录下该最小覆盖字串的起始位置
}
char removeChar = s.charAt(left);
// 开始缩减窗口，left右移，如果要从window删除的字符正好是need中需要的并且，数目也等于need中需要的数目，则删减后，该该字符要求的数量
// 显然不满足need要求的数量，所以valid要-1；
if(need.containsKey(removeChar) && window.get(removeChar).equals(need.get(removeChar))){
valid--;
}
window.put(removeChar,window.get(removeChar) - 1);
left++;
}
}
// 如果最小覆盖字串的长度相对于定义时没变，则t不包含s中所有的字符，返回"",如果长度改变过，说明存在这样的最小覆盖字串，直接输出。
return len == Integer.MAX_VALUE?"":s.substring(start,start+len);
}
}
2.6 二分查找
讲解：https://blog.csdn.net/zxzxzx0119/article/details/82670761
二分法一定要注意边界问题！！
- l < r：此时，循环退出条件为 l == r ，而由于 mid =（r + l）/ 2取的中的靠左位置，即mid可能 == l，而如果 l此时的更新方式为：l = mid将导致死循环。
- 解决办法为mid取中点靠右：mid = (r + l + 1) / 2
- 注意1：当 l 更新方式为 l = mid + 1时，不会死循环。
- 注意2：这种写法，退出时 l == r
- l <= r：退出条件为 l > r，即实际上退出时 r != l。
⭐️实现sqrt
- 注意事项：
- 使用除法，避免大数运算。
- 返回r，因为 l <= r 循环退出时，l > r，即r是小的那个，符合sqrt取整的要求。
public class Sqrt {
// 二分法实现sqrt
public static void main(String[] args) {
System.out.println(solution(4));
System.out.println(solution(8));
}
private static int solution(int num){
if(num <= 1){
return num;
}
int l = 1, r = num;
while(l <= r){
int mid = l + (r - l) / 2;
int temp = num / mid;
if(temp == mid){
return mid;
}else if(mid < temp){
l = mid + 1;
}else{
r = mid - 1;
}
}
return r;
}
}
大于给定元素的最小元素
- 题 目描述：给定一个有序的字符数组 letters 和一个字符 target，要求找出 letters 中大于 target 的最小字符，如果 找不到就返回第 1 个字符。
public class FindSmallestLetter {
public static void main(String[] args) {
char[] ch = new char[]{'c', 'f', 'j'};
char target1 = 'd';
char target2 = 'k';
System.out.println(solution(ch, target1));
System.out.println(solution(ch, target2));
}
private static char solution(char[] letters, char target){
int len = letters.length;
int l = 0, r = len - 1;
while(l <= r){
int mid = l + (r - l) / 2;
if(letters[mid] > target){
r = mid - 1;
}else{
l = mid + 1;
}
}
return l < len ? letters[l] : letters[0];
}
}
//法二：
class Solution {
public char nextGreatestLetter(char[] letters, char target) {
int lo = 0, hi = letters.length;
while (lo < hi) {
int mi = lo + (hi - lo) / 2;
if (letters[mi] <= target) lo = mi + 1;
else hi = mi;
}
return letters[lo % letters.length];
}
}
有序数组中的单一元素
- 题目：给定一个只包含整数的有序数组，每个元素都会出现两次，唯有一个数只会出现一次，找出这个数。
public class SingleNonDuplicate {
public static void main(String[] args) {
int[] arr = new int[]{1, 1, 2, 3, 3, 4, 4, 8, 8};
int[] arr1 = new int[]{3, 3, 7, 7, 10, 11, 11};
System.out.println(solution(arr));
System.out.println(solution(arr1));
}
private static int solution(int[] arr){
if(arr == null || arr.length == 0){
return -1;
}
int l = 0, r = arr.length - 1;
while(l < r){ //注意不能==，因为r=mid赋值可能导致死循环
int mid = l + (r - l) / 2;
if(mid % 2 == 1){//如果为奇数，则改为判断前一个（偶数）
mid--;
}
if(arr[mid] == arr[mid + 1]){
l = mid + 2;
}else{
r = mid;
}
}
return arr[l]; // l和r都可以
}
}
⭐️搜索旋转排序数组
class Solution {
public int search(int[] nums, int target) {
//要求logn，必然二分
if(nums == null || nums.length == 0)return -1;
int l = 0;
int r = nums.length - 1;
while(l <= r){
int mid = l + (r - l) / 2;
if(nums[mid] == target) return mid;
if(nums[l] < nums[mid]){//左侧有序
if(target < nums[l] || target > nums[mid]){//小于最小边界，或大于最大边界
l = mid + 1;
}else{
r = mid - 1;
}
}else{//右侧有序
if(target < nums[mid] || target > nums[r]){
//小于最小边界，或大于最大边界
r = mid - 1;
}else{
l = mid + 1;
}
}
}
return -1;
}
}
⭐️寻找旋转数组的最小数字
https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array/
public class FindRotateMin {
public static void main(String[] args) {
int[] arr = new int[]{1, 2, 3, 4, 5};
int[] arr1 = new int[]{3, 4, 5, 1, 2};
System.out.println(solution(arr));
System.out.println(solution(arr1));
}
// 必然是二分法:最小值必然在右侧区域
//因此每次比较mid和最右边的大小确定mid当前处于哪个区间。
private static int solution(int[] arr){
int l = 0, r = arr.length - 1;
while(l < r){
int mid = l + (r - l) / 2;
if(arr[mid] <= arr[r]){
r = mid;
}else{
l = mid + 1;
}
}
return arr[r];
}
}
⭐️在排序数组中查找元素的第一个和最后一个位置
- 题目描述：给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]。
public class SearchRange {
public static void main(String[] args) {
int[] arr = new int[]{5, 7, 7, 8, 8, 10};
System.out.println(solution(arr, 8));
// System.out.println(solution(arr, 6));
}
private static int[] solution(int[] arr, int target){
int[] ans = new int[]{-1, -1};
if(arr == null || arr.length == 0){
return ans;
}
int L = binarySearch(arr, target);
int R = binarySearch(arr, target + 1) - 1;
if(L == -1){
return ans;
}else{
ans[0] = L;
ans[1] = R;
return ans;
}
}
private static int binarySearch(int[] arr, int target){
int l = 0, r = arr.length - 1;
while(l < r){
int mid = l + (r - l) / 2;
if(arr[mid] < target){
l = mid + 1;
}else{
r = mid;
}
}
System.out.println(l);
return arr[l] == target ? l : -1;
}
}
法二：分情况讨论法
class Solution {
public int[] searchRange(int[] nums, int target) {
// 二分查找
int[] arr = new int[2];
arr[0] = binarySearchLeft(nums, target);
arr[1] = binarySearchRight(nums, target);
return arr;
}
private int binarySearchLeft(int[] nums, int target){
int left = 0;
int right = nums.length - 1;
while(left <= right){
int mid = left + (right - left) / 2;
if(nums[mid] > target){
right = mid - 1;
}else if(nums[mid] < target){
left = mid + 1;
}else{
if(mid == 0 || nums[mid - 1] != target){
return mid;
}else{
right = mid - 1;
}
}
}
return -1;
}
private int binarySearchRight(int[] nums, int target){
int left = 0;
int right = nums.length - 1;
while(left <= right){
int mid = left + (right - left) / 2;
if(nums[mid] > target){
right = mid - 1;
}else if(nums[mid] < target){
left = mid + 1;
}else{
if(mid == nums.length - 1 || nums[mid + 1] != target){
return mid;
}else{
left = mid + 1;
}
}
}
return -1;
}
}
2.7 BFS
每一层遍历的节点都与根节点距离相同。设 di 表示第 i 个节点与根节点的距离，推导出一个结论：对于先遍历的节点 i 与后遍历的节点 j，有 di <= dj。利用这个结论，可以求解最短路径等 最优解 问题：第一次遍历到目的节点，其所经 过的路径为最短路径。应该注意的是，使用 BFS 只能求解无权图的最短路径，无权图是指从一个节点到另一个节点 的代价都记为 1。
在程序实现 BFS 时需要考虑以下问题：
- 队列：用来存储每一轮遍历得到的节点；
- 标记：对于遍历过的节点，应该将它标记，防止重复遍历。
计算在网络中从原点到特定点的最短路径
- 题目描述：1 表示可以经过某个位置，求解从 (0, 0) 位置到 (tr, tc) 位置的最短路径长度。
import java.util.ArrayDeque;
import java.util.Queue;
public class MinPathLength {
// bfs典型题
public static void main(String[] args) {
int[][] arr = {{1, 1, 0, 1}, {1, 0, 1, 0}, {1, 1, 1, 1}, {1, 0, 1, 1}};
System.out.println(solution(arr, 3, 3));
}
private static int solution(int[][] arr, int ti, int tj){
int[][] direction = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int row = arr.length;
int col = arr[0].length;
int len = 0;
boolean[][] visited = new boolean[row][col];
Queue queue = new ArrayDeque<>();
queue.offer(new int[]{0, 0});
while(!queue.isEmpty()){
int size = queue.size(); //注意queue每次存放的是下一次可以遍历的相同距离的点
len++; //queue不为空可以++
while(size-- > 0){
int[] temp = queue.poll();
int i = temp[0], j = temp[1];
visited[i][j] = true;
for(int[] d : direction){
int ii = i + d[0];
int jj = j + d[1];
if(ii < 0 || ii >= row || jj < 0 || jj >= col || arr[ii][jj] == 0 ||visited[ii][jj]){
continue;
}
if(ii == ti && jj == tj){
return len;
}
queue.offer(new int[]{ii, jj});
}
}
}
return -1;
}
}
2.8 DFS
广度优先搜索一层一层遍历，每一层得到的所有新节点，要用队列存储起来以备下一层遍历的时候再遍历。 而深度优先搜索在得到一个新节点时立即对新节点进行遍历：从节点 0 出发开始遍历，得到到新节点 6 时，立马对 新节点 6 进行遍历，得到新节点 4；如此反复以这种方式遍历新节点，直到没有新节点了，此时返回。返回到根节点 0 的情况是，继续对根节点 0 进行遍历，得到新节点 2，然后继续以上步骤。 从一个节点出发，使用 DFS 对一个图进行遍历时，能够遍历到的节点都是从初始节点可达的，DFS 常用来求解这种 可达性 问题。
在程序实现 DFS 时需要考虑以下问题：
- 栈：用栈来保存当前节点信息，当遍历新节点返回时能够继续遍历当前节点。可以使用递归栈。
- 标记：和 BFS 一样同样需要对已经遍历过的节点进行标记。
查找最大连通面积
public class MaxAreaOfIsland {
// 查找最大连通面积
public static void main(String[] args) {
}
private static int solution(int[][] arr){
if(arr == null || arr.length == 0){
return 0;
}
int maxArea = 0;
int row = arr.length;
int col = arr[0].length;
for(int i = 0; i < row; i++){
for(int j = 0; j < col; j++){
maxArea = Math.max(maxArea, dfs(arr, i, j, row, col));
}
}
}
private static int dfs(int[][] arr, int i, int j, int row, int col){
if(i < 0 || i>= row || j < 0 || j >= col || arr[i][j] == 0){
return 0;
}
arr[i][j] = 0;
return 1 + dfs(arr, i - 1, j, row, col)
+ dfs(arr, i + 1, j, row, col)
+ dfs(arr, i, j - 1, row, col)
+ dfs(arr, i, j + 1, row, col);
}
}
⭐️矩阵中的连通区域分量数目/岛屿数量
public class NumOfIsland {
// 连通分量数目
public static void main(String[] args) {
int[][] arr = {
{1,1,0,0,0},
{1,1,0,0,0},
{0,0,1,0,0},
{0,0,0,1,1}
};
System.out.println(solution(arr));
}
private static int solution(int[][] arr){
// 把遍历过的区域标记为0，下次直接跳过
if(arr == null || arr.length == 0) return 0;
int row = arr.length;
int col = arr[0].length;
int count = 0;
for(int i = 0; i < row; i++){
for(int j = 0; j < col; j++){
if(arr[i][j] != 0){
count++;
dfs(arr, i, j, row, col);
}
}
}
return count;
}
private static void dfs(int[][] arr, int i, int j, int row, int col){
if(i < 0 || i >= row || j < 0 || j >= col || arr[i][j] <= 0){
return ;
}
arr[i][j] = 0;
dfs(arr, i - 1, j, row, col);
dfs(arr, i + 1, j, row, col);
dfs(arr, i, j - 1, row, col);
dfs(arr, i, j + 1, row, col);
}
}
2.9 Backtracking
Backtracking（回溯）属于 DFS。
- 普通 DFS 主要用在 可达性问题 ，这种问题只需要执行到特点的位置然后返回即可。
- 而 Backtracking 主要用于求解 排列组合 问题，例如有 { ‘a’,‘b’,‘c’ } 三个字符，求解所有由这三个字符排列得到 的字符串，这种问题在执行到特定的位置返回之后还会继续执行求解过程。
因为 Backtracking 不是立即返回，而要继续求解，因此在程序实现时，需要注意对元素的标记问题：
- 在访问一个新元素进入新的递归调用时，需要将新元素标记为已经访问，这样才能在继续递归调用时不用重复 访问该元素；
- 但是在递归返回时，需要将元素标记为未访问，因为只需要保证在一个递归链中不同时访问一个元素，可以访 问已经访问过但是不在当前递归链中的元素。
技巧：回溯法的模板很好记，但是何时用start变量，何时用visited数组呢？ 当为组合问题，即[a, b]与[b, a]等价，用start变量，当为排列问题，即[a, b]与[b, a]不等价，用visited数组
⭐️复原IP地址
给定一个只包含数字的字符串，用以表示一个 IP 地址，返回所有可能从 s 获得的 有效 IP 地址 。你可以按任何顺序返回答案。
有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 ‘.’ 分隔。
例如：“0.1.2.201” 和 “192.168.1.1” 是 有效 IP 地址，但是 “0.011.255.245”、“192.168.1.312” 和 “192.168@1.1” 是 无效 IP 地址。
class Solution {
static final int SEG_COUNT = 4; //分4段
List ans = new ArrayList();
int[] segments = new int[SEG_COUNT]; //存放4个整数
public List restoreIpAddresses(String s) {
segments = new int[SEG_COUNT];
dfs(s, 0, 0);
return ans;
}
// segId代表第几段，segStart代表每段的开始下标
public void dfs(String s, int segId, int segStart) {
// 如果找到了 4 段 IP 地址并且遍历完了字符串，那么就是一种答案
if (segId == SEG_COUNT) {
if (segStart == s.length()) {
StringBuffer ipAddr = new StringBuffer();
for (int i = 0; i < SEG_COUNT; ++i) {
ipAddr.append(segments[i]);
if (i != SEG_COUNT - 1) { //中间加点
ipAddr.append('.');
}
}
ans.add(ipAddr.toString());
}
return;
}
// 如果还没有找到 4 段 IP 地址就已经遍历完了字符串，那么提前回溯
if (segStart == s.length()) {
return;
}
// 由于不能有前导零，如果当前数字为 0，那么这一段 IP 地址只能为 0，即0必须单独划分区间
if (s.charAt(segStart) == '0') {
segments[segId] = 0;
dfs(s, segId + 1, segStart + 1);
}
// 一般情况，枚举每一种可能性并递归
int addr = 0;
for (int segEnd = segStart; segEnd < s.length(); ++segEnd) {
addr = addr * 10 + (s.charAt(segEnd) - '0');
if (addr > 0 && addr <= 0xFF) { //0xFF == 255
segments[segId] = addr;
dfs(s, segId + 1, segEnd + 1);
} else {
break;
}
}
}
}
数字的排列组合
题目描述：给定一个数组，给出数组元素的所有排列组合
package com.tosang.java;
import java.util.ArrayList;
import java.util.List;
public class Permute {
public static void main(String[] args) {
int[] arr = {1,2,3};
List> solution = solution(arr);
solution.forEach((List temp) -> {
temp.forEach(System.out::print);
System.out.println();
});
}
public static List> solution(int[] nums){
List> ans = new ArrayList<>();
List temp = new ArrayList<>();
boolean[] visited = new boolean[nums.length];
dfs(nums, temp, ans, visited);
return ans;
}
// 回溯法
public static void dfs(int[] nums, List temp, List> ans, boolean[] visited){
if(temp.size() == nums.length){
ans.add(new ArrayList<>(temp));
return;
}
for(int i = 0; i < nums.length; i++){
if(!visited[i]){
temp.add(nums[i]);
visited[i] = true;
dfs(nums, temp, ans, visited);
// 还原现场
visited[i] = false;
temp.remove(temp.size() - 1);
}
}
}
}
⭐️组合总和
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明：
所有数字（包括 target）都是正整数。
解集不能包含重复的组合。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/combination-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
技巧说明：回溯法的关键是for循环里面的内容，这里列举两种情况：
- 求全排列：意味着数组每次都要从0下标遍历，故for(int i = 0)
- 求和为目标值：从当前下标继续走，故for(int i = index)
此外，理解回溯的含义：当前dfs遍历完成了，不管其是否满足条件，我需要回到上一步以跳过上一步，尝试下一步dfs。
class Solution {
public List> combinationSum(int[] candidates, int target) {
List> res = new ArrayList<>();
Arrays.sort(candidates);
//System.out.println(candidates);
backtrack(candidates, target, res, 0, new ArrayList());
return res;
}
private void backtrack(int[] candidates, int target, List> res, int i, ArrayList tmp_list) {
if (target < 0) return;
if (target == 0) {
res.add(new ArrayList<>(tmp_list));
return;
}
for (int start = i; start < candidates.length; start++) {
tmp_list.add(candidates[start]);
backtrack(candidates, target - candidates[start], res, start, tmp_list);
tmp_list.remove(tmp_list.size() - 1);
}
}
}
⭐️ 子集
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
class Solution {
public List> subsets(int[] nums) {
// 回溯法
List> ans = new ArrayList<>();
List temp = new ArrayList<>();
dfs(nums, 0, temp, ans);
return ans;
}
private void dfs(int[] nums, int index, List temp, List> ans){
ans.add(new ArrayList<>(temp));
for(int i = index; i < nums.length; i++){
temp.add(nums[i]);
dfs(nums, i + 1, temp, ans);
temp.remove(temp.size() - 1);
}
}
}
3.0 动态规划
⭐️最长重复子数组
给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。
class Solution {
public int findLength(int[] nums1, int[] nums2) {
//dp[i][j]代表以下标 i-1, j-1结尾的公共子数组。
int[][] dp = new int[nums1.length + 1][nums2.length + 1];
int res = 0;
for (int i = 1; i < dp.length; i++) {
for (int j = 1; j < dp[i].length; j++) {
if (nums1[i - 1] == nums2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
res = Math.max(res, dp[i][j]);
} else {
dp[i][j] = 0;
}
}
}
return res;
}
}
爬楼梯
public class ClimbingStairs {
public static void main(String[] args) {
System.out.println(solution(1));
System.out.println(solution(2));
System.out.println(solution(3));
System.out.println(solution(4));
System.out.println(solution(5));
}
private static int solution(int n){
if(n == 1)return 1;
int[] dp = new int[n];
dp[0] = 1;
dp[1] = 2;
for(int i = 2; i < n; i++){
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n - 1];
}
}
强盗抢劫
- 题目描述：抢劫一排住户，但是不能抢邻近的住户，求最大抢劫量。
public class Rob {
public static void main(String[] args) {
int[] arr1 = {1, 2, 3, 1};
int[] arr2 = {2, 7, 9, 3, 1};
System.out.println(solution(arr1));
System.out.println(solution(arr2));
}
private static int solution(int[] arr){
if(arr == null || arr.length == 0)return 0;
if(arr.length == 1)return arr[0];
int[] dp = new int[arr.length];
dp[0] = arr[0];
dp[1] = Math.max(dp[0], dp[1]);
for(int i = 2; i < arr.length; i++){
dp[i] = Math.max(dp[i - 1], dp[i - 2] + arr[i]);
}
return dp[arr.length - 1];
}
}
矩阵的最小路径和
public class MinPathSum {
public static void main(String[] args) {
int[][] arr = {
{1,3,1}
,{1,5,1}
,{4,2,1}};
System.out.println(solution(arr));
}
private static int solution(int[][] arr){
if(arr == null || arr.length == 0) return 0;
int row = arr.length;
int col = arr[0].length;
int[][] dp = new int[row][col];
for(int i = 0; i < row; i++){
for(int j = 0; j < row; j++){
if(i == 0 && j== 0){
dp[0][0] = arr[0][0];
}
else if(i == 0 && j != 0){
dp[i][j] = dp[i][j - 1] + arr[i][j];
}
else if(j == 0 && i != 0){
dp[i][j] = dp[i - 1][j] + arr[i][j];
}else{
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + arr[i][j];
}
}
}
return dp[row - 1][col - 1];
}
}
矩阵的路径数
public class UniquePath {
public static void main(String[] args) {
System.out.println(solution(3, 3));
System.out.println(solution(2, 2));
System.out.println(solution(1, 1));
}
private static int solution(int row, int col){
if(row <= 0 || col <= 0)return 0;
int[][] dp = new int[row][col];
for(int i = 0; i < row; i++){
for(int j = 0; j < col; j++){
if(i == 0 && j == 0){
dp[i][j] = 1;
}else if(i == 0 && j != 0){
dp[i][j] = dp[i][j - 1];
}else if(j == 0 && i !=0){
dp[i][j] = dp[i - 1][j];
}else{
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
}
return dp[row - 1][col - 1];
}
}
⭐️最大子序和
题目描述：给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
class Solution {
public int maxSubArray(int[] nums) {
int max = nums[0];
int len = nums.length;
if(len == 1)return nums[0];
int[] dp = new int[len]; //代表包含当前下标i的最大子序列和
dp[0] = nums[0];
for(int i = 1; i < len; i++){
dp[i] = Math.max(dp[i- 1] + nums[i], nums[i]);
max = dp[i] > max ? dp[i] : max;
}
return max;
}
}
⭐️最长公共子序列
注意区别子序列和子串
对于两个子序列 S1 和 S2，找出它们最长的公共子序列。
public class LengthOfLCS {
public static void main(String[] args) {
int[] s1 = {1, 3, 4, 5, 6, 7, 7, 8};
int[] s2 = {3, 5, 7, 4, 8, 6, 7, 8, 2};
int[] s3 = {3, 5};
int[] s4 = {3};
System.out.println(solution(s1, s2));
System.out.println(solution(s1, s3));
System.out.println(solution(s1, s4));
}
private static int solution(int[] s1, int[] s2){
if(s1.length == 0 || s2.length == 0)return 0;
int[][] dp = new int[s1.length][s2.length]; //dp[i][j]对应s1的i，s2的j
for(int i = 0; i < s1.length; i++){
for(int j = 0; j < s2.length; j++){
if(i == 0 && j == 0){
dp[i][j] = s1[i] == s2[j] ? 1 : 0;
}else if(i == 0 && j != 0){
dp[i][j] = s1[i] == s2[j] ? 1 : dp[i][j - 1];
}else if(j == 0 && i != 0){
dp[i][j] = s1[i] == s2[j] ? 1 : dp[i - 1][j];
}else{
dp[i][j] = s1[i] == s2[j] ? dp[i - 1][j - 1] + 1 : Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[s1.length - 1][s2.length - 1];
}
}
⭐️最长递增子序列
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
public class LengthOfLIS {
public static void main(String[] args) {
int[] arr1 = {10, 9, 2, 5, 3, 7, 101, 18};
int[] arr2 = {0, 1, 0, 3, 2, 3};
int[] arr3 = {7, 7, 7, 7, 7, 7, 7};
System.out.println(solution(arr1));
System.out.println(solution(arr2));
System.out.println(solution(arr3));
}
private static int solution(int[] arr){
if(arr == null || arr.length == 0)return 0;
int len = arr.length;
int[] dp = new int[len];
// dp[j] 代表 nums[0…j] 中以j结尾的最长上升子序列，所以不一定是最大值
int ans = 0;
dp[0] = 1;
for(int i = 1; i < len; i++){
dp[i] = 1;
for(int j = 0; j < i; j++){
if(arr[i] > arr[j]){
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
ans = Math.max(ans, dp[i]);
}
return ans;
}
}
划分数组为和相等的两部分
class Solution {
public boolean canPartition(int[] nums) {
// 01背包问题：
// 可选数量为N = nums.length，背包最大容量为：w = sum / 2，
// 这题和一般01背包的区别是，这里不要求价值最大，而是恰好装满，因此dp数组存放背包的当前体积即可。
int sum = 0;
for(int num : nums){ // 计算和
sum += num;
}
if(sum % 2 != 0){
return false;//除不尽，说明总和一定不能分成两份
}
int len = nums.length;
int W = sum / 2;
int[][] dp = new int[len + 1][W + 1]; //dp[i][j]，i是当前背包的件数，j是当前背包的体积
for(int i = 1; i <= len; i++){ //注意题目说只包含正整数，所以j从1开始
int w = nums[i - 1];
for(int j = 1; j <= W; j++){
if(j >= w){ //背包容量装得下当前数字
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w] + w);
}else{
dp[i][j] = dp[i - 1][j];
}
if(dp[i][j] == W){
return true;
}
}
}
return false;
}
}
删除字符串的字符是他们相等
public class MinDIstance {
public static void mian(String[] args){
String word1 = "sea";
String word2 = "eat";
System.out.println(solution(word1, word2));
}
private static int solution(String word1, String word2){
int len1 = word1.length();
int len2 = word2.length();
int[][] dp = new int[len1 + 1][len2 + 1];
for(int i = 1; i <= len1; i++){
for(int j = 1; j <= len2; j++){
if(word1.charAt(i - 1) == word2.charAt(j - 1)){
dp[i][j] = dp[i - 1][j - 1] + 1;
}else{
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return len1 + len2 - 2 * dp[len1][len2];
}
}
⭐️接雨水
首先用两个数组，max_left [i] 代表第 i 列左边最高的墙的高度，max_right[i] 代表第 i 列右边最高的墙的高度。（一定要注意下，第 i 列左（右）边最高的墙，是不包括自身的，和 leetcode 上边的讲的有些不同）
对于 max_left我们其实可以这样求。
max_left [i] = Max(max_left [i-1],height[i-1])。它前边的墙的左边的最高高度和它前边的墙的高度选一个较大的，就是当前列左边最高的墙了。
对于 max_right我们可以这样求。
max_right[i] = Max(max_right[i+1],height[i+1]) 。它后边的墙的右边的最高高度和它后边的墙的高度选一个较大的，就是当前列右边最高的墙了。
这样，我们再利用解法二的算法，就不用在 for 循环里每次重新遍历一次求 max_left 和 max_right 了。
作者：windliang
链接：https://leetcode-cn.com/problems/trapping-rain-water/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-w-8/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
public class Trap {
public static void main(String[] args) {
int[] arr = {4,2,0,3,2,5};
System.out.println(solution(arr));//9
}
private static int solution(int[] arr){
if(arr == null || arr.length == 0)return 0;
int len = arr.length;
int[] lMax = new int[len];//存储i左侧最大值
int[] rMax = new int[len];//存储i右侧最大值
lMax[0] = 0;
rMax[len - 1] = 0;
for(int i = 1; i < len; i++){
lMax[i] = Math.max(lMax[i - 1], arr[i - 1]);
}
for(int i = len - 2; i >= 0; i--){
rMax[i] = Math.max(rMax[i + 1], arr[i + 1]);
}
int count = 0;
for(int i = 1; i < len - 1; i++){
// 因为0和len - 1必然没有水，故可以跳过
int min = Math.min(lMax[i], rMax[i]);
if(arr[i] < min){
count += min - arr[i];
}
}
return count;
}
}
⭐️硬币兑换
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
你可以认为每种硬币的数量是无限的。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/coin-change
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];// dp[i] 代表总金额为i时，最少的硬币数
Arrays.fill(dp, amount + 1);// 初始填充最大值
dp[0] = 0; //一定要初始化，因为0比较特殊，金额为0，不需要硬币
for(int i = 1; i <= amount; i++){
for(int j = 0; j < coins.length; j++){
int value = coins[j];// 面值
if(i >= value){
dp[i] = Math.min(dp[i], dp[i - value] + 1);//遍历所有面值，找最小值
}
}
}
return dp[amount] != amount + 1 ? dp[amount] : -1;
}
}
3.1 数学
⭐️用rand7()实现rand10()
只要记得这个公式：if a in [0，x], 那么 a * Y + randY() 能等概率的生成 1到X*Y之间的随机数
原理：
a * y = [0, 6] * 7 ，即{0，7，14，21，28，35，42}
randy = {1,2,3,4,5,6,7}
所以有：
p{ a * Y + randY() == 1}=1/49
p{ a * Y + randY() == 2}=1/49
…
p{ a * Y + randY() == 10}=1/49
p{ a * Y + randY() == 49}=1/49
方法一：
根据上面的算法，我们可以得到以下最简单的实现，即不断生成随机数，直到数字是【1,10】区间以内的，返回即可
class Solution extends Solbase {
public int rand10() {
int num = 0;
do{
num = (rand7() - 1)*7 + rand7();
}while(num > 10);
return num;
}
}
方法二：
注意到上面的算法存在一个问题：我们的函数会得到 1～49之间的数，而我们只想得到 1～10之间的数，这一部分占的比例太少了，简而言之，这样效率太低，太慢，可能要 while循环很多次。我们最后完全可以利用 1～40 之间的数来得到 1～10之间的数。
class Solution extends Solbase {
public int rand10() {
int num = 0;
while(true){
num = (rand7() - 1)*7 + rand7();
if(num > 40){
continue;
}
return num % 10 + 1;
}
}
}
二进制相加
import jdk.internal.jshell.tool.resources.l10n;
public class AddBinary {
public static void main(String[] args) {
String num1 = "11";
String num2 = "1";
System.out.println(solution(num1, num2));
}
private static String solution(String num1, String num2){
int m = num1.length() - 1, n = num2.length() - 1;
int carry = 0; //表示进位
StringBuilder sb = new StringBuilder();
while(carry == 1 || m >= 0 || n >= 0){ //注意一定要判断 == 1,因为最高位可能会进1
if(m >= 0 && num1.charAt(m--) == '1'){
carry++;
}
if(n >= 0 && num2.charAt(n--) == '1'){
carry++;
}
sb.append(carry % 2); //保留余数
carry /= 2; //进位
}
return sb.reverse().toString(); }
}
⭐️字符串相加
public class AddString {
public static void main(String[] args) {
String num1 = "111111";
String num2 = "999999";
System.out.println(solution(num1, num2));
}
private static String solution(String num1, String num2){
int m = num1.length() - 1;
int n = num2.length() - 1;
int carry = 0;//进位
StringBuilder sb = new StringBuilder();
while(carry >= 1 || m >= 0 || n >= 0){
int x = 0, y = 0;
if(m >= 0){
x = num1.charAt(m--) - '0';
}
if(n >= 0){
y = num2.charAt(n--) - '0';
}
sb.append((x + y + carry) % 10);
carry = (x + y + carry) / 10;
}
return sb.reverse().toString();
}
}
注意上面两题的思路基本一致
数组中出现次数多于一半的元素
public class MajorElement {
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5, 2, 2, 2, 2};
int[] arr1 = {3, 3, 3, 3, 3, 2, 2, 2, 2};
System.out.println(solution(arr));
System.out.println(solution(arr1));
}
private static int solution(int[] arr){
// 摩尔投票法
int len = arr.length;
if(len <= 0)return -1;
if(len == 1)return arr[0];
int cnt = 0;
int ans = arr[0];
for(int i = 0; i < len; i++){
if(cnt == 0){
// ans被抵消了
ans = arr[i];
}
cnt = ans == arr[i] ? cnt + 1 : cnt - 1;
}
return ans;
}
}
3.2 链表
⭐️删除链表重复元素
遍历法：
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if(head == null)return head;
ListNode p1 = head;
while(p1 != null && p1.next != null){
if(p1.next.val == p1.val){
ListNode temp = p1.next;
p1.next = p1.next.next;
temp = null;
}else{
p1 = p1.next;
}
}
return head;
}
}
递归法：
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if (head == null) {
return null;
}
if (head.next == null) {
return head;
}
if (head.val == head.next.val) {
head = deleteDuplicates(head.next);
} else {
head.next = deleteDuplicates(head.next);
}
return head;
}
}
⭐️删除链表重复元素2
与1区别：这题要求删除重复元素，并且不保留重复元素
迭代法：
class Solution {
public ListNode deleteDuplicates(ListNode head) {
ListNode dummy = new ListNode(0, head);
ListNode prev = dummy, curr, next;
while ((curr = prev.next) != null && (next = curr.next) != null) {
if (next.val != curr.val) {
prev = prev.next;
continue;
}
while (next != null && next.val == curr.val) next = next.next;
prev.next = next;
}
return dummy.next;
}
}
递归法：
class Solution {
public ListNode deleteDuplicates(ListNode head) {
//baseCase
if (head == null || head.next == null) {
return head;
}
ListNode next = head.next;
//如果是这种情况
// 1 --> 1 --> 1 --> 2 --> 3
// head next
//1.则需要移动next直到出现与当前head.value不相等的情况（含null）
//2.并且此时的head已经不能要了，因为已经head是重复的节点
//--------------else-------------
// 1 --> 2 --> 3
// head next
//3.如果没有出现1的情况，则递归返回的节点就作为head的子节点
if (head.val == next.val) {
//1
while (next != null && head.val == next.val) {
next = next.next;
}
//2
head = deleteDuplicates(next);
} else {
//3
head.next = deleteDuplicates(next);
}
return head;
}
}
找出两个链表的交点
注意使用静态内部类创建链表。
public class GetInterSectionNode {
static class Node{
int val;
Node next;
Node(int val){
this.val = val;
}
Node(int val, Node next){
this.val = val;
this.next = next;
}
}
public static void main(String[] args) {
Node list1 = new Node(4);
Node list2 = new Node(5);
int[] arr = {1, 8, 4, 5};
int[] arr1 = {0, 1, 2};
Node p1 = list1;
Node p2 = list2;
Node pp = list1;
for(int num : arr){
Node temp = new Node(num);
p1.next = temp;
p1 = p1.next;
if(num == 8){
pp = p1;
}
}
for(int num : arr1){
Node temp = new Node(num);
p2.next = temp;
p2 = p2.next;
}
p2.next = pp;
System.out.println(solution(list1, list2).val);
}
private static Node solution(Node list1, Node list2){
Node p1 = list1;
Node p2 = list2;
while(p1.next != p2.next){
if(p1.next == null){
p1 = list2;
p2 = p2.next;
}
if(p2.next == null){
p2 = list1;
p1 = p1.next;
}else{
p1 = p1.next;
p2 = p2.next;
}
}
return p1.next;
}
}
链表反转
- 头插法
- 递归法
讲解：https://leetcode-cn.com/problems/reverse-linked-list/solution/fan-zhuan-lian-biao-by-leetcode-solution-d1k2/
public class ReverselinkedList {
static class Node{
int val;
Node next;
Node(int val){
this.val = val;
}
Node(int val, Node next){
this.val = val;
this.next = next;
}
}
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5};
Node list = new Node(0);
Node p = list;
for(int n : arr){
Node temp = new Node(n);
p.next = temp;
p = p.next;
}
// Node ans = solution(list);
Node ans = solution2(list);
while(ans != null){
System.out.print(ans.val + " ");
ans = ans.next;
}
}
private static Node solution(Node list){
// 头插法
Node head = new Node(-1);
Node p = list;
while(p != null){
Node temp = p.next; //注意记录下一个节点
p.next = head.next;
head.next = p;
p = temp;
}
return head.next;
}
private static Node solution2(Node list){
// 递归法
if(list == null || list.next == null){
return list;
}
Node temp = list.next;
Node newHead = solution2(list.next);
temp.next = list;
list.next = null;
return newHead;
}
}
⭐️归并两个有序链表
public class MergeTwoList {
static class ListNode{
int val;
ListNode next;
ListNode(int val){
this.val = val;
}
}
public static void main(String[] args) {
int[] arr1 = {1,2,3,4};
int[] arr2 = {2,3,4,5};
ListNode l1 = new ListNode(0);
ListNode l2 = new ListNode(0);
ListNode p1 = l1;
ListNode p2 = l2;
for(int num : arr1){
ListNode temp = new ListNode(num);
p1.next = temp;
p1 = p1.next;
}
for(int num : arr2){
ListNode temp = new ListNode(num);
p2.next = temp;
p2 = p2.next;
}
ListNode ans = solution(l1.next, l2.next);
while(ans != null){
System.out.println(ans.val);
ans = ans.next;
}
}
private static ListNode solution(ListNode l1, ListNode l2){
ListNode p1 = l1;
ListNode p2 = l2;
ListNode head = new ListNode(0);
ListNode curr = head;
while(p1 != null && p2 != null){
if(p1.val <= p2.val){
curr.next = p1;
p1 = p1.next;
}else{
curr.next = p2;
p2 = p2.next;
}
curr = curr.next;
}
curr.next = p1 == null ? p2 : p1;
return head.next;
}
}
注意这题有一个递归写法：
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) return l2;
if (l2 == null) return l1;
ListNode res = l1.val < l2.val ? l1 : l2;
res.next = mergeTwoLists(res.next, l1.val >= l2.val ? l1 : l2);
return res;
}
链表求和
Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 8 -> 0 -> 7
题目要求：不能修改原始链表。
import java.util.*;
public class AddTwoNumber{
static class Node{
int val;
Node next;
Node(int val){
this.val = val;
}
}
public static void main(String[] args) {
int[] arr1 = {7 , 2, 4, 3};
int[] arr2 = {5 , 6, 4};
Node list1 = new Node(7);
Node list2 = new Node(5);
Node p1 = list1;
Node p2 = list2;
for(int i = 1; i < arr1.length; i++){
Node temp = new Node(arr1[i]);
p1.next = temp;
p1 = p1.next;
}
for(int i = 1; i < arr2.length; i++){
Node temp = new Node(arr2[i]);
p2.next = temp;
p2 = p2.next;
}
Node ans = add(list1, list2);
while(ans != null){
System.out.println(ans.val);
ans = ans.next;
}
}
private static Node add(Node list1, Node list2){
Stack stack1 = buildStack(list1);
Stack stack2 = buildStack(list2);
Node head = new Node(-1);
int carry = 0; //进位
while(!stack1.isEmpty() || !stack2.isEmpty() || carry != 0){
int x = stack1.isEmpty() ? 0 : stack1.pop();
int y = stack2.isEmpty() ? 0 : stack2.pop();
int sum = x + y + carry;
Node temp = new Node(sum % 10);
temp.next = head.next;
head.next = temp;
carry = sum / 10;
}
return head.next;
}
private static Stack buildStack(Node list){
Stack stack = new Stack<>();
while(list != null){
stack.push(list.val);
list = list.next;
}
return stack;
}
}
⭐️K个一组翻转链表
-
题目描述：给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序
-
注意：翻转一个链表并不难，过程可以参考「206. 反转链表」。但是对于一个子链表，除了翻转其本身之外，还需要将子链表的头部与上一个子链表连接，以及子链表的尾部与下一个子链表连接。
注意下面最关键的链表逆转方式
public class ReverseKGroup {
static class ListNode{
int val;
ListNode next;
ListNode(int val){
this.val = val;
}
}
public static void main(String[] args) {
int[] arr = {1,2,3,4,5,6,7,8,9,10,11};
int k = 3;
ListNode head = new ListNode(0);
ListNode p = head;
for(int i = 0; i < arr.length; i++){
ListNode temp = new ListNode(arr[i]);
p.next = temp;
p = p.next;
}
ListNode ans = solution(head.next, k);
while(ans != null){
System.out.println(ans.val);
ans = ans.next;
}
}
private static ListNode solution(ListNode head, int k){
ListNode newHead = new ListNode(0); //头指针
ListNode pre = newHead; //前驱
ListNode curr = head; //当前
newHead.next = head;
int len = 0;
while(head != null){
head = head.next;
len++;
}
head = newHead.next; //复位
for(int i = 0; i < len / k; i++){
for(int j = 0; j < k - 1; j++){
// 循环 k - 1次即可
//注意：这里的链表逆转方式类似于插入排序，每次把curr后面节点的插入到最前面，这样保证curr的位置始终没变，方便
ListNode next = curr.next;
curr.next = next.next;
next.next = pre.next;
pre.next = next;
}
pre = curr;
curr = pre.next;
}
return newHead.next;
}
}
⭐️环形链表2
题目描述：给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
思路：
-
首先根据快慢指针判断有无环。
-
对于有环的情况，设head -到环入口距离 == a, 环的长度 == b：
fast 走的步数是slow步数的 2 倍，即f=2s；（解析： fast 每轮走 2 步）
fast 比 slow多走了n 个环的长度，即 f = s + nb （ 解析： 双指针都走过 aa 步，然后在环内绕圈直到重合，重合时 fast 比 slow 多走 环的长度整数倍 ）；
以上两式相减得：s = nb
即slow再走 a步长就可以到达环的入口。
public class DetectCycle {
static class ListNode{
int val;
ListNode next;
ListNode(int val){
this.val = val;
}
}
public static void main(String[] args) {
int[] arr = {1,2,3,4,5,6,7,8,9};
ListNode h = new ListNode(0);
ListNode p = h, cycle = new ListNode(-1);
for(int num : arr){
ListNode temp = new ListNode(num);
p.next = temp;
p = p.next;
if(num == 5){
cycle = temp;
}
}
p.next = cycle; //建环
System.out.println(solution(h.next).val);
}
private static ListNode solution(ListNode head){
boolean hasCycle = false;
ListNode p1 = head, p2 = head; //快慢指针
while(p1 != null && p2.next != null){
p1 = p1.next;
p2 = p2.next.next;
if(p1.val == p2.val){
hasCycle = true;
break;
}
}
if(hasCycle){
ListNode p3 = head;
while(p1.val != p3.val){
p1 = p1.next;
p3 = p3.next;
}
return p3;
}else{
return null;
}
}
}
⭐️ 链表的倒数第k个节点
双指针法
class Solution {
public ListNode getKthFromEnd(ListNode head, int k) {
ListNode p1 = head;
ListNode p2 = head;
while(k > 0 && p2 != null){
p2 = p2.next;
k--;
}
if(k > 0){
return null;
}
while(p2 != null){
p1 = p1.next;
p2 = p2.next;
}
return p1;
}
}
⭐️ 反转链表2
题目：给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-linked-list-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
public ListNode reverseBetween(ListNode head, int m, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode pre = dummy;
for(int i = 1; i < m; i++){
pre = pre.next;
}
head = pre.next;
for(int i = m; i < n; i++){
ListNode nex = head.next;
head.next = nex.next;
nex.next = pre.next;
pre.next = nex;
}
return dummy.next;
}
}
⭐️合并K个有序链表
有两种算法：分治和最小堆，二者的时间复杂度都是 n*KlogK，n是一条链表的长度，K是链表的数量
分治法：
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
return merge(lists, 0, lists.length - 1);
}
public ListNode merge(ListNode[] lists, int l, int r) {
//二路归并
if (l == r) {
return lists[l];
}
if (l > r) {
return null;
}
int mid = (l + r) >> 1;
ListNode l1 = merge(lists, l, mid);
ListNode l2 = merge(lists, mid + 1, r);
return mergeTwoLists(l1, l2);
}
public ListNode mergeTwoLists(ListNode a, ListNode b) {
if (a == null || b == null) {
return a != null ? a : b;
}
ListNode head = new ListNode(0);
ListNode tail = head, aPtr = a, bPtr = b;
while (aPtr != null && bPtr != null) {
if (aPtr.val < bPtr.val) {
tail.next = aPtr;
aPtr = aPtr.next;
} else {
tail.next = bPtr;
bPtr = bPtr.next;
}
tail = tail.next;
}
tail.next = (aPtr != null ? aPtr : bPtr);
return head.next;
}
}
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/merge-k-sorted-lists/solution/he-bing-kge-pai-xu-lian-biao-by-leetcode-solutio-2/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
最小堆：
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists.length == 0) {
return null;
}
ListNode dummyHead = new ListNode(0);
ListNode curr = dummyHead;
PriorityQueue pq = new PriorityQueue<>(new Comparator() {
@Override
public int compare(ListNode o1, ListNode o2) {
return o1.val - o2.val;
}
});
for (ListNode list : lists) {
if (list == null) {
continue;
}
pq.add(list);
}
while (!pq.isEmpty()) {
ListNode nextNode = pq.poll();
curr.next = nextNode;
curr = curr.next;
if (nextNode.next != null) {
pq.add(nextNode.next);
}
}
return dummyHead.next;
}
}
⭐️判断回文链表
这题要求时间复杂度 o(n)，空间复杂度 o(1)，用栈可能不满足要求
关于反转链表的递归解法讲解参看：https://leetcode-cn.com/problems/reverse-linked-list/solution/shi-pin-jiang-jie-die-dai-he-di-gui-hen-hswxy/
方法一：栈
class Solution {
public boolean isPalindrome(ListNode head) {
linkedList stack = new linkedList();
ListNode tmp = head;
while(tmp != null){
stack.push(tmp.val);
tmp = tmp.next;
}
ListNode tmp2 = head;
while(tmp2 != null){
if(tmp2.val != stack.pop()){
return false;
}
tmp2 = tmp2.next;
}
return true;
}
}
作者：LeetcodeFrom20210207
链接：https://leetcode-cn.com/problems/palindrome-linked-list/solution/234-hui-wen-lian-biao-by-leetcodefrom202-xorb/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
方法二：
class Solution {
public boolean isPalindrome(ListNode head) {
// 要实现 O(n) 的时间复杂度和 O(1) 的空间复杂度，需要翻转后半部分
if (head == null || head.next == null) {
return true;
}
ListNode fast = head;
ListNode slow = head;
// 根据快慢指针，找到链表的中点
while(fast.next != null && fast.next.next != null) {
fast = fast.next.next;
slow = slow.next;
}
slow = reverse(slow.next);
while(slow != null) {
if (head.val != slow.val) {
return false;
}
head = head.next;
slow = slow.next;
}
return true;
}
private ListNode reverse(ListNode head){
if (head == null || head.next == null) {//注意这里的推出条件，一定要写head.next == null
return head;
}
ListNode newHead = reverse(head.next);//这里将head.next后面的元素都反转
head.next.next = head;//形成环
head.next = null;//反转成功
return newHead;//返回新的头节点
}
}
⭐️重排链表
定一个单链表 L：L0→L1→…→Ln-1→Ln ，
将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reorder-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
public void reorderList(ListNode head) {
ListNode p1 = head;
ListNode fast = p1;
ListNode slow = fast;
if(fast == null)return;
//快慢指针找到中点
while(fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
}
//递归翻转后半部分
ListNode p2 = reverse(slow);
//将翻转后的后半部分插入原链表
while(p2 != null){
ListNode temp = p2.next;
p2.next = p1.next;
p1.next = p2;
p1 = p1.next.next;
p2 = temp;
}
//断链
p1.next = null;
}
public ListNode reverse(ListNode head){
if(head == null || head.next == null){
return head;
}
ListNode temp = head.next;
ListNode newHead = reverse(head.next);
temp.next = head;
head.next = null;
return newHead;
}
}
3.3 栈
实现计算器
用栈实现队列
- 入栈只进stack1
- 出栈只出stack2，若stack2为空，先从stack1全部拿到stack2，再出栈一个stack2
import java.util.ArrayDeque;
import java.util.Deque;
public class StackToQueue {
Deque in = new ArrayDeque<>();
Deque out = new ArrayDeque<>();
public static void main(String[] args) {
StackToQueue queue = new StackToQueue();
queue.add(1);
queue.add(2);
queue.add(3);
System.out.println(queue.get());
System.out.println(queue.get());
System.out.println(queue.get());
}
private void add(int val){
in.push(val);
}
private int get(){
inToOut();
return out.pop();
}
private void inToOut(){
if(out.isEmpty()){
while(!in.isEmpty()){
out.push(in.pop());
}
}
}
}
用队列实现栈
- 加入元素时，把新元素之前的元素放到队尾
import java.util.ArrayDeque;
import java.util.Queue;
public class QueueToStack {
Queue queue= new ArrayDeque<>();
public static void main(String[] args) {
QueueToStack stack = new QueueToStack();
stack.push(1);
stack.push(2);
stack.push(3);
System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println(stack.pop());
}
public void push(int val){
queue.offer(val);
int size = queue.size();
while(size-- > 1){
queue.offer(queue.poll());
}
}
public int pop(){
return queue.poll();
}
}
⭐️括号匹配
补充：为什么要用Deque替代Stack
Vector不行是因为效率不太行，很多方法都用了synchronized修饰，虽然线程安，因此继承Vector的Stack也存在效率问题，故不推荐使用。
再一个原因是Deque双端队列可以实现多种数据结构，完全可以模拟成栈的结构。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-bpNgPAyO-1638356641861)(D:MD笔记typora-pic2020053121015811.png)]
class Solution {
public boolean isValid(String s) {
if(s.isEmpty())
return true;
Deque stack=new ArrayDeque<>();
for(char c:s.toCharArray()){
if(c=='(')
stack.push(')');
else if(c=='{')
stack.push('}');
else if(c=='[')
stack.push(']');
else if(stack.empty()||c!=stack.pop())
return false;
}
return stack.empty();
}
}
⭐️基本计算器
给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
class Solution {
public int calculate(String s) {
Stack stack = new Stack();
// sign 代表正负
int sign = 1, res = 0;
int length = s.length();
for (int i = 0; i < length; i++) {
char ch = s.charAt(i);
if (Character.isDigit(ch)) {
int cur = ch - '0';
while (i + 1 < length && Character.isDigit(s.charAt(i + 1)))
cur = cur * 10 + s.charAt(++i) - '0';
res = res + sign * cur;
} else if (ch == '+') {
sign = 1;
} else if (ch == '-') {
sign = -1;
} else if (ch == '(') {
stack.push(res);
res = 0;
stack.push(sign);
sign = 1;
} else if (ch == ')') {
res = stack.pop() * res + stack.pop();
}
}
return res;
}
}
3.4 队列
⭐️滑动窗口最大值
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值【即每个窗口的最大值组成的数组】。
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int len = nums.length;
if (len == 0) {
return nums;
}
int[] arr = new int[len - k + 1];
int arr_index = 0;
//我们需要维护一个单调递增的双向队列
Deque deque = new linkedList<>();
//先将第一个窗口的值按照规则入队
for (int i = 0; i < k; i++) {
while (!deque.isEmpty() && deque.peekLast() < nums[i]) {
deque.removeLast();
}
deque.offerLast(nums[i]);
}
//存到数组里，队头元素
arr[arr_index++] = deque.peekFirst();
//移动窗口
for (int j = k; j < len; j++) {
//对应咱们的红色情况，则是窗口的前一个元素等于队头元素
if (nums[j - k] == deque.peekFirst()) {
deque.removeFirst();
}
while (!deque.isEmpty() && deque.peekLast() < nums[j]) {
deque.removeLast();
}
deque.offerLast(nums[j]);
arr[arr_index++] = deque.peekFirst();
}
return arr;
}
}
3.5 数组
⭐️缺失的第一个正数
给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
public class Solution {
public int firstMissingPositive(int[] nums) {
int len = nums.length;
for (int i = 0; i < len; i++) {
while (nums[i] > 0 && nums[i] <= len && nums[nums[i] - 1] != nums[i]) {
//自建哈希表i-->i+1
// 满足在指定范围内、并且没有放在正确的位置上，才交换
// 例如：数值 3 应该放在索引 2 的位置上
// 理解nums[nums[i] - 1] != nums[i]：相当于i下标的元素和待交换下标 nums[i] - 1的元素如果一样，那已经满足哈希函数规则了，不用交换。
swap(nums, nums[i] - 1, i);
}
}
// [1, -1, 3, 4]
for (int i = 0; i < len; i++) {
if (nums[i] != i + 1) {
return i + 1;
}
}
// 都正确则返回数组长度 + 1
return len + 1;
}
private void swap(int[] nums, int index1, int index2) {
int temp = nums[index1];
nums[index1] = nums[index2];
nums[index2] = temp;
}
}
⭐️搜索二维矩阵 II
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
每行的元素从左到右升序排列。
每列的元素从上到下升序排列。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/search-a-2d-matrix-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
// 时间复杂度 O(m + n)
// 算法：把左上角或者右下角看作一个二叉查找树。
if(matrix == null || matrix.length == 0)return false;
int m = 0, n = matrix[0].length - 1;
while(m < matrix.length && n >= 0){
if(matrix[m][n] == target){
return true;
}else if(matrix[m][n] < target){
m = m + 1;
}else{
n = n - 1;
}
}
return false;
}
}
⭐️下一个排列
实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
必须 原地 修改，只允许使用额外常数空间。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/next-permutation
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
public void nextPermutation(int[] nums) {
//字典序算法：https://www.cnblogs.com/darklights/p/5285598.html
//其算法思路其实很简单：
//1.从后往前遍历，从这个序列中从右至左找第一个左邻小于右邻的数
//2.此时必然要从后面换一个比当前数大的最小数到当前位置（再次从右往左）
//3.换好以后，新的序列还不是最小的大值，要对之后的数升序排序。
//--------------------------------查找
int small = -1; //要交换的较小值下标
int len = nums.length;
for(int i = len - 1; i > 0; i--){
// 如果找不到，则所有排列求解完成，如果找得到则说明排列未完成。
if(nums[i] > nums[i - 1]){
small = i - 1;
break;
}
}
int big = 0; //要交换的较大值下标
for(int i = len - 1; i >= 0 && small >= 0; i--){
if(nums[i] > nums[small]){
big = i;
break;
}
}
if(small == -1) {
//说明已经最大了，不能再找了
quickSort(nums, small + 1, len - 1);
}else{
//---------------------------------交换
int temp = nums[small];
nums[small] = nums[big];
nums[big] = temp;
//----------------------------------交换后，重新排序，使用随机快排
quickSort(nums, small + 1, len - 1);
}
}
void quickSort(int[] arr, int L, int R){
if(L < R){
swap(arr, L + (int)(Math.random()*(R - L + 1)), R); //这里有一点疑惑，为什么随机数包含R？
int[] p = partion(arr, L, R);
quickSort(arr, L, p[0] - 1);
quickSort(arr, p[1] + 1, R);
}
}
int[] partion(int[] arr, int L, int R){
int less = L - 1;
int more = R; //注意为什么是R，因为R不参与partion，它存储的是基准元素
while(L < more){
if(arr[L] < arr[R]) swap(arr, ++less, L++);// 注意为什么是L++，其实因为L必然是==R的数了，不需要判断，画个图描述: <<<>>>>>> R
else if(arr[L] > arr[R]) swap(arr, --more, L);//注意这里为什么是L，因为交换后的数不一定是等于R的需要再判断一次,L到R之间是未知的
else L++;
}
swap(arr, more , R);
return new int[]{less + 1, more}; //[less + 1, more]是中间的等于R的数
}
void swap(int[] arr, int a, int b){
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
}
⭐️多数元素
给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/majority-element
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
//摩尔投票法
int res = 0, count = 0;
for(int i = 0; i < nums.length; i ++){
if(count == 0){
//票数为0更换目标
res = nums[i];
count++;
}else{
if(res == nums[i]){
count++;
}else{
count--;
}
}
}
return res;
}
}
}
⭐️合并区间
题目：以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-intervals
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
public int[][] merge(int[][] intervals) {
if (intervals.length == 0) {
return new int[0][2];
}
Arrays.sort(intervals, new Comparator() {//按照区间左边界排序
public int compare(int[] interval1, int[] interval2) {
return interval1[0] - interval2[0];
}
});
List merged = new ArrayList();
for (int i = 0; i < intervals.length; ++i) {
int L = intervals[i][0], R = intervals[i][1];
if (merged.size() == 0 || merged.get(merged.size() - 1)[1] < L) {
merged.add(new int[]{L, R});//mergedL小于当前L
} else {
merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], R);
}
}
//注意：这里的用new int[0]只是为了指定函数的形参数，最终返回的int[]的长度是由你的list存 //储内容的长度决定了。new int[0]就是起一个模板的作用，指定了返回数组的类型，0是为了节省空间，因为它只是为了说明返回的类型
return merged.toArray(new int[0][]);
}
}
⭐️移动字符串的 全部*号到左侧
public class MoveStar {
public static void main(String[] args) {
String str = "*abcd*efg*h";
System.out.println(solution(str));
}
private static String solution(String str){
char[] ch = str.toCharArray();
int idx = ch.length - 1;
for(int i = ch.length - 1; i >=0; i--){
if(ch[i] != '*'){
ch[idx--] = ch[i];
}
}
while(idx >= 0){//注意--不能加在while循环上，因为while循环进入循环体时，idx已经--,会越界
ch[idx--] = '*';
}
return new String(ch);
}
}
⭐️螺旋矩阵
题目：给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
思路：
- 按照每一层遍历，注意先完整遍历一行和一列，保证特殊情况：只有一行或一列时能够遍历。
- 再判断是否有两层及其以上，来添加剩下两边。
package com.tosang.java;
import java.util.ArrayList;
import java.util.List;
public class spiralOrder {
public static void main(String[] args) {
int[][] arr = {
{1,2,3},
{4,5,6},
{7,8,9}
};
List solution = solution(arr);
solution.forEach(System.out::print);
}
public static List solution(int[][] matrix){
ArrayList list = new ArrayList<>();
if(matrix == null || matrix.length == 0 || matrix[0].length == 0){
return list;
}
int row = matrix.length;
int col = matrix[0].length;
int top = 0, bottom = row - 1;
int left = 0, right = col - 1;
while(top <= bottom && left <= right){
for(int i = left; i <= right; i++){
list.add(matrix[top][i]);
}
for (int j = top + 1; j <= bottom; j++){
list.add(matrix[j][right]);
}
// 如果有两行两列以上。
if(left < right && top < bottom){
for(int i = right - 1; i >= left + 1; i--){
list.add(matrix[bottom][i]);
}
for (int j = bottom; j >= top + 1; j--){
list.add(matrix[j][left]);
}
}
left++;
right--;
top++;
bottom--;
}
return list;
}
}
⭐️旋转图像
给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。要求原地旋转
class Solution {
public void rotate(int[][] matrix) {
// 先转置，然后镜像对称
for(int i = 0; i < matrix.length; i++){
for(int j = 0; j < i; j++){ // 注意为啥是 j < i， 因为求的是转置
// 转置
int temp = matrix[j][i];
matrix[j][i] = matrix[i][j];
matrix[i][j] = temp;
}
}
for(int i = 0; i < matrix.length; i++){
// 镜像对称
for(int j = 0; j < matrix[0].length / 2; j++){
int temp = matrix[i][j];
matrix[i][j] = matrix[i][matrix[0].length - j - 1];
matrix[i][matrix[0].length - j - 1] = temp;
}
}
}
}
3.6 位运算
现在有一个数组，里面有一个数出现了奇数次，剩下的数出现偶数次，怎么找出这个数？
public class OddAndEven {
// 有1个出现奇数和n-1个出现偶数次的数，找出出现奇数次的那个数
public static void main(String[] args) {
int[] arr = {1,1,2,2,3,3,3};
System.out.println(solution(arr));
}
private static int solution(int[] arr){
int ans = 0;
for(int num : arr){
ans ^= num;
}
return ans;
}
}
3.7 二叉树
⭐️验证二叉搜索树
给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/validate-binary-search-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
long last = Long.MIN_VALUE;
public boolean isValidBST(TreeNode root) {
// 中序遍历优化，可以提前退出
return inOrder(root);
}
public boolean inOrder(TreeNode root){
// 中序遍历，看是否为升序
if(root == null) return true;
if(!inOrder(root.left)){
return false;
};
if(last >= root.val){
return false;
}
last = root.val;
if(!inOrder(root.right)){
return false;
};
return true;
}
}
⭐️判断对称二叉树
递归法
class Solution {
public boolean isSymmetric(TreeNode root) {
if(root == null)return true;
return compare(root.left, root.right);
}
boolean compare(TreeNode t1, TreeNode t2){
if(t1 == null && t2 == null) return true;
if(t1 == null || t2 == null || t1.val != t2.val) return false;
return compare(t1.left, t2.right) && compare(t1.right, t2.left);
}
}
迭代法
class Solution {
public boolean isSymmetric(TreeNode root) {
if (root == null) {
return true;
}
Queue queue = new linkedList<>();
queue.offer(root.left);
queue.offer(root.right);
while (!queue.isEmpty()) {
TreeNode node1 = queue.poll();
TreeNode node2 = queue.poll();
if (node1 == null && node2 == null) {
continue;
}
if (node1 == null || node2 == null || node1.val != node2.val) {
return false;
}
queue.offer(node1.left);
queue.offer(node2.right);
queue.offer(node1.right);
queue.offer(node2.left);
}
return true;
}
}
⭐️翻转二叉树
class Solution {
public TreeNode invertTree(TreeNode root) {
if(root == null){
return root;
}
TreeNode right = root.right;
root.right = invertTree(root.left);
root.left = invertTree(right);
return root;
}
}
⭐️二叉树的层次遍历
- 注意包含两个步骤：用数组建立二叉树 + 二叉树层次遍历。
import java.util.*;
public class levelOrder {
static class TreeNode{
int val;
TreeNode left;
TreeNode right;
TreeNode(int val){
this.val = val;
}
}
public static void main(String[] args) {
int[] arr = {3, 9, 20, -1, -1, 15, 7};//-1代表null
TreeNode root = buildTree(arr, 0);
List> ans = solution(root);
Iterator> iterator = ans.iterator();
while(iterator.hasNext()){
Iterator ite = iterator.next().iterator();
while(ite.hasNext()){
System.out.print(ite.next() + " ");
}
System.out.println();
}
}
private static TreeNode buildTree(int[] arr, int index){
// 根据数组建立二叉树
if(index >= arr.length){
return null;
}
if(arr[index] == -1){
return null;
}
TreeNode ans = new TreeNode(arr[index]);
ans.left = buildTree(arr, index * 2 + 1);
ans.right = buildTree(arr, index * 2 + 2);
return ans;
}
private static List> solution(TreeNode root){
// 层次遍历
List> ans = new ArrayList<>();
Queue queue = new linkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
int size = queue.size();
List temp = new ArrayList<>();
while(size > 0){
TreeNode tempNode = queue.poll();
temp.add(tempNode.val);
if(tempNode.left != null){
queue.offer(tempNode.left);
}
if(tempNode.right != null){
queue.offer(tempNode.right);
}
size--;
}
ans.add(temp);
}
return ans;
}
}
⭐️二叉树的锯齿形打印
思路：和层次遍历类似，不过多一个flag来控制list的添加顺序。
class Solution {
public List> zigzagLevelOrder(TreeNode root) {
if (root == null) {
return new ArrayList<>();
}
boolean flag = true;
Queue queue = new linkedList<>();
List> res = new ArrayList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
linkedList list = new linkedList<>();
while (size > 0) {
TreeNode node = queue.poll();
if (flag) {
list.add(node.val);
} else {
list.addFirst(node.val);
}
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
size--;
}
res.add(list);
flag = !flag;
}
return res;
}
}
⭐️二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。
思路：采用后序遍历
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null || root == p || root == q) return root;
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if(left == null && right == null) return null; // 1.情况1：子树找不到p/q
if(left == null) return right; // 3.情况3，左子树没有p/q，右子树有
if(right == null) return left; // 4.情况4，右子树没有p/q，左子树有
return root; // 2. if(left != null and right != null)
}
}
⭐️二叉树的中序遍历
递归 + 非递归
注意：以下三种树的遍历采用同一种模板，思路清晰。
class Solution {
//递归法
List list = new ArrayList<>();
public List inorderTraversal(TreeNode root) {
if(root != null){
if(root.left != null)inorderTraversal(root.left);
list.add(root.val);
if(root.right != null)inorderTraversal(root.right);
}
return list;
}
}
class Solution {
public List inOrderTraversal(TreeNode root) {
//非递归算法
Deque stack = new ArrayDeque<>();
List list = new ArrayList<>();
while (root != null || !stack.isEmpty()) {
if (root!=null){
//先往左走到头
stack.push(root);
root = root.left;
}else {
//出栈，保存数据，往右走
root = stack.pop();
list.add(root.val);//后添加
root = root.right;
}
}
return list;
}
}
⭐️先序遍历非递归
class Solution {
public List preOrderTraversal(TreeNode root) {
//非递归算法
Deque stack = new ArrayDeque<>();
List list = new ArrayList<>();
while (root != null || !stack.isEmpty()) {
if (root!=null){
//先往左走到头
list.add(root.val) //先添加
stack.push(root);
root = root.left;
}else {
//出栈，保存数据，往右走
root = stack.pop();
root = root.right;
}
}
return list;
}
}
⭐️后续遍历非递归
思路：后续遍历非递归直接写比较困难，但是可以有下面的骚 *** 作实现
- 根据先序遍历是：根 - 左 - 右 的顺序，将list的添加顺序逆转（从头添加，而不是尾部），那么list包含的顺序必然是：右 - 左 - 根。
- 在1的基础上，我们只需要改变下遍历顺序即可，即先遍历右走到头，再去遍历左，便有了：左 - 右 - 根。
class Solution {
public List postOrderTraversal(TreeNode root) {
//非递归算法
Deque stack = new ArrayDeque<>();
List list = new ArrayList<>();
while (root != null || !stack.isEmpty()) {
if (root!=null){
//先往右走到头
list.addFirst(root.val)//注意加到表头，不是表尾
stack.push(root);
root = root.right;
}else {
//出栈，保存数据，往右走
root = stack.pop();
root = root.left;
}
}
return list;
}
}
⭐️二叉树的最大深度
class Solution {
public int maxDepth(TreeNode root) {
//考虑递归
if(root == null) return 0;
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
}
⭐️判断平衡二叉树
class Solution {
public boolean isBalanced(TreeNode root) {
return height(root) != -1;
}
public int height(TreeNode root){
// 递归退出条件
if(root == null){
return 0;
}
// 单步 *** 作
int l = height(root.left); //为正数或0时表示树高，为负数是表示不平衡
int r = height(root.right);
//返回值
if(l >= 0 && r >= 0 && Math.abs(l - r) <= 1){
return Math.max(l, r) + 1;
}else{
return -1;
}
}
}
⭐️二叉树的最大路径和
路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ，返回其 最大路径和 。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-maximum-path-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
int maxSum = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
dfs(root);
return maxSum;
}
private int dfs(TreeNode root){
// 有点像后序遍历
if(root == null) return 0;
int left = dfs(root.left);
int right = dfs(root.right);
int oneSidePath = root.val + Math.max(left, right); //单边最大路径
maxSum = Math.max(maxSum, left + root.val + right);
// 由于root.val可能为负值，所以要判断
return oneSidePath > 0 ? oneSidePath : 0;
}
}
⭐️路径总和2
题目：给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
class Solution {
public List> pathSum(TreeNode root, int targetSum) {
List> list = new ArrayList<>();
List temp = new ArrayList<>();
dfs(list, temp, root, targetSum, 0);
return list;
}
private void dfs(List list, List temp, TreeNode root, int targetSum, int sum){
// 回溯法
if(root == null){
return ;
}
if(root.left == null && root.right == null && root.val + sum == targetSum){
temp.add(root.val);
list.add(new ArrayList<>(temp));
temp.remove(temp.size() - 1);
return;
}
// 需要注意：这里不能剪枝，即判断root.val + sum > targetSum就直接停止
//因为：节点值可能为负数，后面还可能等于targetSum
temp.add(root.val);
dfs(list, temp, root.left, targetSum, sum + root.val);
dfs(list, temp, root.right, targetSum, sum + root.val);
temp.remove(temp.size() - 1);
}
}
⭐️从前序遍历和中序遍历构造二叉树
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
return buildTree(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
}
//l1,r1;l2,r2分别表示在两个数组的左右边界
public TreeNode buildTree(int[] preorder, int l1, int r1, int[] inorder, int l2, int r2){
if(l1 > r1)return null;
int rootVal = preorder[l1]; //根节点
TreeNode root = new TreeNode(rootVal);//加入
int index = l2; //使用根节点在中序遍历中划分左右子树,即中序遍历root的下标
while(index < r2 && inorder[index] != rootVal){
// 遍历，寻找inorder中根节点的下标
index++; //
}
root.left = buildTree(preorder, l1 + 1, l1 + (index - l2), inorder, l2, index - 1);
root.right = buildTree(preorder, l1 + (index -l2) + 1, r1, inorder, index + 1, r2);
return root;
}
}
⭐️二叉树的直径
题目：给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
class Solution {
int max = 0;
public int diameterOfBinaryTree(TreeNode root) {
if(root == null){
return 0;
}
dfs(root);
return max;
}
private int dfs(TreeNode root){
if(root.left == null && root.right == null){
return 0;
}
int left = root.left == null ? 0 : dfs(root.left) + 1;
int right = root.right == null ? 0 : dfs(root.right) + 1;
max = Math.max(max, left + right);
return Math.max(left, right);
}
}
⭐️求根节点到叶节点数字之和
给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。
每条从根节点到叶节点的路径都代表一个数字：
例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。
计算从根节点到叶节点生成的 所有数字之和 。
叶节点 是指没有子节点的节点。
public int sumNumbers(TreeNode root) {
return helper(root, 0);
}
public int helper(TreeNode root, int i){
if (root == null) return 0;
int temp = i * 10 + root.val;
if (root.left == null && root.right == null)
return temp;
return helper(root.left, temp) + helper(root.right, temp);
}
⭐️路径总和2
题目：给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
class Solution {
public List> pathSum(TreeNode root, int targetSum) {
List> list = new ArrayList<>();
List temp = new ArrayList<>();
dfs(list, temp, root, targetSum, 0);
return list;
}
private void dfs(List list, List temp, TreeNode root, int targetSum, int sum){
// 回溯法
if(root == null){
return ;
}
if(root.left == null && root.right == null && root.val + sum == targetSum){
temp.add(root.val);
list.add(new ArrayList<>(temp));
temp.remove(temp.size() - 1);
return;
}
// 需要注意：这里不能剪枝，即判断root.val + sum > targetSum就直接停止
//因为：节点值可能为负数，后面还可能等于targetSum
temp.add(root.val);
dfs(list, temp, root.left, targetSum, sum + root.val);
dfs(list, temp, root.right, targetSum, sum + root.val);
temp.remove(temp.size() - 1);
}
}
⭐️从前序遍历和中序遍历构造二叉树
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
return buildTree(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
}
//l1,r1;l2,r2分别表示在两个数组的左右边界
public TreeNode buildTree(int[] preorder, int l1, int r1, int[] inorder, int l2, int r2){
if(l1 > r1)return null;
int rootVal = preorder[l1]; //根节点
TreeNode root = new TreeNode(rootVal);//加入
int index = l2; //使用根节点在中序遍历中划分左右子树,即中序遍历root的下标
while(index < r2 && inorder[index] != rootVal){
// 遍历，寻找inorder中根节点的下标
index++; //
}
root.left = buildTree(preorder, l1 + 1, l1 + (index - l2), inorder, l2, index - 1);
root.right = buildTree(preorder, l1 + (index -l2) + 1, r1, inorder, index + 1, r2);
return root;
}
}
⭐️二叉树的直径
题目：给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
class Solution {
int max = 0;
public int diameterOfBinaryTree(TreeNode root) {
if(root == null){
return 0;
}
dfs(root);
return max;
}
private int dfs(TreeNode root){
if(root.left == null && root.right == null){
return 0;
}
int left = root.left == null ? 0 : dfs(root.left) + 1;
int right = root.right == null ? 0 : dfs(root.right) + 1;
max = Math.max(max, left + right);
return Math.max(left, right);
}
}
⭐️求根节点到叶节点数字之和
给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。
每条从根节点到叶节点的路径都代表一个数字：
例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。
计算从根节点到叶节点生成的 所有数字之和 。
叶节点 是指没有子节点的节点。
public int sumNumbers(TreeNode root) {
return helper(root, 0);
}
public int helper(TreeNode root, int i){
if (root == null) return 0;
int temp = i * 10 + root.val;
if (root.left == null && root.right == null)
return temp;
return helper(root.left, temp) + helper(root.right, temp);
}
最后：保姆级的Java教程和项目推荐
趋势投资Spring Cloud项目
前端练手项目，模仿天猫前端
JAVA WEB J2EE 练手项目，模仿天猫整站
JAVA 桌面软件练手项目，一本糊涂账
JAVA 自学网站
JAVA 练习题
Hibernate 教程
Struts 教程
SSH整合教程
Mybatis 教程
Spring MVC 教程
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）