算法总结
1.数组
数组理论基础
数组是非常基础的数据结构，在面试中，考察数组的题目一般在思维上都不难，主要是考察对代码的掌控能力
也就是说，想法很简单，但实现起来 可能就不是那么回事了。
首先要知道数组在内存中的存储方式，这样才能真正理解数组相关的面试题
数组是存放在连续内存空间上的相同类型数据的集合。
数组可以方便的通过下标索引的方式获取到下标下对应的数据。
举一个字符数组的例子，如图所示：
需要两点注意的是
数组下标都是从0开始的。
数组内存空间的地址是连续的
正是因为数组的在内存空间的地址是连续的，所以我们在删除或者增添元素的时候，就难免要移动其他元素的地址。
例如删除下标为3的元素，需要对下标为3的元素后面的所有元素都要做移动操作，如图所示：
而且大家如果使用C++的话，要注意vector 和 array的区别，vector的底层实现是array，严格来讲vector是容器，不是数组。
数组的元素是不能删的，只能覆盖。
那么二维数组直接上图，大家应该就知道怎么回事了
那么二维数组在内存的空间地址是连续的么？
不同编程语言的内存管理是不一样的，在C++中二维数组是连续分布的。
所以可以看出在C++中二维数组在地址空间上是连续的。
像Java是没有指针的，同时也不对程序员暴露其元素的地址，寻址操作完全交给虚拟机。
所以看不到每个元素的地址情况，这里我以Java为例，也做一个实验。
public static void test_arr() {
int[][] arr = {{1, 2, 3}, {3, 4, 5}, {6, 7, 8}, {9,9,9}};
System.out.println(arr[0]);
System.out.println(arr[1]);
System.out.println(arr[2]);
System.out.println(arr[3]);
}输出的地址为：
[I@7852e922
[I@4e25154f
[I@70dea4e
[I@5c647e05这里的数值也是16进制，这不是真正的地址，而是经过处理过后的数值了，我们也可以看出，二维数组的每一行头结点的地址是没有规则的，更谈不上连续。
所以Java的二维数组可能是如下排列的方式：
代码随想录题目
1.1二分查找:https://www.programmercarl.com/0704.%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.html
1.2移除元素:https://www.programmercarl.com/0027.%E7%A7%BB%E9%99%A4%E5%85%83%E7%B4%A0.html
1.5螺旋矩阵:https://www.programmercarl.com/0059.%E8%9E%BA%E6%97%8B%E7%9F%A9%E9%98%B5II.html
1.1 二分查找
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4 示例 2:
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1 提示：
你可以假设 nums 中的所有元素是不重复的。
n 将在 [1, 10000]之间。
nums 的每个元素都将在 [-9999, 9999]之间。
class Solution {
public static int search(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
if(target< nums[0]||target>nums[nums.length-1]){
return -1;
}
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
}else {
return mid;
}
}
return -1;
}
}1.2 移除元素
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并**原地**修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例 1: 给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。 你不需要考虑数组中超出新长度后面的元素。
示例 2: 给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。
**你不需要考虑数组中超出新长度后面的元素。**
class Solution {
public static int removeElement(int[] nums, int val) {
// 快指针fast：寻找新数组的元素 ，新数组就是不含有目标元素的数组
//慢指针slow：指向更新 新数组下标的位置
int slow = 0;
for (int fast = 0; fast < nums.length; fast++) {
if (nums[fast] != val) {
nums[slow] = nums[fast];
slow++;
}
}
return slow;
}
}1.3 长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。
示例：
输入：s = 7, num(https://www.programmercarl.com/0027.移除元素.html#算法公开课)s = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
提示：
1 <= target <= 10^9
1<= nums.length <= 10^5
1 <= nums[i] <= 10^5
方法一 暴力破解
import java.util.ArrayList;
public class Main {
public static void main(String[] args) {
int[] nums = {2,3,1,2,4,3};
System.out.println(minSubArrayLen(7,nums));
}
public static int minSubArrayLen(int target, int[] nums) {
int sum=0;
int result=Integer.MAX_VALUE;//保证result最大
int sub=0;
for (int i = 0; i < nums.length; i++) {
sum=0;//注意细节 i++后sum要清零
for(int j=i;j < nums.length;j++){
sum+=nums[j];
if(sum>=target){
sub=j-i+1;
result=Math.min(result,sub);
break;
}
}
}
return result== Integer.MAX_VALUE ? 0 : result;
}
}
方法二 滑动窗口
import java.util.ArrayList;
public class Main {
public static void main(String[] args) {
int[] nums = {2,3,1,2,4,3};
System.out.println(minSubArrayLen(7,nums));
}
public static int minSubArrayLen(int target, int[] nums) {
int left =0;
int sum= 0;
int result = Integer.MAX_VALUE;
for(int right =0;right<nums.length;right++){
sum=sum+nums[right];
while (sum>=target){
result=Math.min(result,right-left+1);
sum=sum-nums[left++];
}
}
return result == Integer.MAX_VALUE ? 0:result;
}
}1.4 螺旋矩阵II
给定一个正整数 n，生成一个包含 1 到 n^2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。
示例:
输入: 3 输出: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ]class Solution {
public int[][] generateMatrix(int n) {
int loop = 0; // 控制循环次数
int[][] res = new int[n][n];
int start = 0; // 每次循环的开始点(start, start)
int count = 1; // 定义填充数字
int i, j;
while (loop++ < n / 2) { // 判断边界后，loop从1开始
// 模拟上侧从左到右
for (j = start; j < n - loop; j++) {
res[start][j] = count++;
}
// 模拟右侧从上到下
for (i = start; i < n - loop; i++) {
res[i][j] = count++;
}
// 模拟下侧从右到左
for (; j >= loop; j--) {
res[i][j] = count++;
}
// 模拟左侧从下到上
for (; i >= loop; i--) {
res[i][j] = count++;
}
start++;
}
if (n % 2 == 1) {
res[start][start] = count;
}
return res;
}
}自己遇到的题目
1.1 找规律
题目中会给你一个整数数组 `num`，`num=[1,2,2,3,3,3.....]`，然后题目中会给你一个整数 `k`，现在请你找出 `num` 的规律，并编写代码计算数组的前 `k` 项和为多少？
输入格式 一个整数`k`。
输出格式 一个整数。
输入输出样例1输入`5`输出 `11`
输入输出样例2输入 `10`输出 `30`package org.example;
import java.util.*;
import java.util.Scanner;
public class BankRate {
public static void main(String[] args) {
Scanner sc =new Scanner(System.in);
int k = sc.nextInt();
int sum = 0; // 存储前k项的和
int currentNum = 1; // 当前要添加的数字
int count = 0; // 已添加的项数
// 计算前k项和
while (count < k) {
for (int i = 0; i < currentNum; i++) {
sum += currentNum; // 累加当前数字
count++; // 增加已处理的项数
// 检查是否已经达到k项
if (count == k) {
break;
}
}
currentNum++; // 移动到下一个数字
}
// 输出前k项和
System.out.println(sum);
}
}1.2 数组的排列方式
小叶同学最近正在学习数组。在做题的时候，他发现了一道关于数组的题，却没有办法做出来，想让你帮他一下。
题目中首先会给你一个整数 `n`，代表 `1` 到 `n` 之间的数字，你可以无限使用 `1` 到 `n` 之间的数字。然后题目中会给你一个整数 `k`，需要你从这 `n` 个数字中取出 `k` 个数字，并按顺序排列起来，但是相邻的数字不能相同，小叶同学想知道这样有多少种排列方法，现在请你帮小叶编写代码，算出结果并输出。（结果对 `1000000007` 取模）
输入格式一行两个整数，`n` 和 `k`。
输出格式 一个整数。
输入输出样例1输入 2 2输出2
输入输出样例2输入1 5输出 `5`import java.util.Scanner;
public class Main {
private static final long MOD = 1000000007; // 定义常量MOD为固定值1000000007
public static void main(String[] args) {
Scanner sc = new Scanner(System.in); // 使用Scanner类从键盘获取输入
int n = sc.nextInt(); // 读取整数n
int m = sc.nextInt(); // 读取整数m
long[] dp = new long[m + 1];
dp[1] = m;
for (int i = 2; i <= m; i++) {
dp[i] = dp[i-1] * (m - i+1) % MOD; // 更新dp[i]
}
System.out.println(dp[m]); // 输出结果
}
}1.3 数组求最值
岳岳经过不断的努力终于加上n 个学弟学妹的微信，以至于现在每天每个学弟学妹都会问a 个问题现在岳岳想找到一个星期内问问题最频繁的学妹(就是排除学弟) 然后请她吃饭作为奖励，请你设计一个程序计算出来
输入
第一行 一个整数 n 表示学弟学妹的总个数
第二行 n 个整数，分别表示第i 名学生的性别。 0 表示为学妹，1 表示为学弟(1≤i ≤n )
接下来七行 每行有n 个整数ai ，每个数字表示第i 名学生当天问的问题数量
输出
一个整数 ans 表示问题最频繁的学妹的编号
测试点数据规模与约定
对于100%的测试点，保证有唯一答案
对于100%的测试点，保证1<n <5，0<ai <10
样例输入
3
0 0 1
2 3 9
1 3 9
4 3 9
2 3 9
1 3 9
2 3 9
0 2 1
样例输出
2
提示
样例中第三个同学问问题是最频繁的但是他不是学妹，所以输出2表示第二个学妹//一维数组解法
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int max = 0;
int ans = 0;
//判断是否需要比较
boolean[] peop = new boolean[n];
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
peop[i] = sc.nextInt()==0;//如果输入等于0，将true值赋给peop
//如果输入不等于0，则表达式的结果为false，将该值赋给peop
}
//统计每人问题的次数
for (int i = 0; i < 7; i++) {
for (int j = 0; j < n; j++) {
arr[j] += sc.nextInt();
}
}
//找到最大值，输出
for (int i = 0; i < n; i++) {
if(peop[i]){
if(arr[i]>max){
max = arr[i];
ans = i;
}
}
System.out.println(ans+1);
}
}//二维数组解法
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int max = 0;
int ans = 0;
// 判断学生性别
boolean[] isSister = new boolean[n];
for (int i = 0; i < n; i++) {
isSister[i] = sc.nextInt() == 0;
}
// 统计每人问题的次数
int[][] questions = new int[7][n];
for (int i = 0; i < 7; i++) {
for (int j = 0; j < n; j++) {
questions[i][j] = sc.nextInt();
}
}
// 找到问题提问最频繁的学妹
for (int i = 0; i < n; i++) {
if (isSister[i]) {
int totalQuestions = 0;
for (int j = 0; j < 7; j++) {
totalQuestions += questions[j][i];
}
if (totalQuestions > max) {
max = totalQuestions;
ans = i + 1; // 学妹的编号是从1开始的
}
}
}
System.out.println(ans);
}
}2.链表
链表理论基础
什么是链表，链表是一种通过指针串联在一起的线性结构，每一个节点由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向null（空指针的意思）。
链表的入口节点称为链表的头结点也就是head。
如图所示： 
链表的类型 接下来说一下链表的几种类型:
单链表
刚刚说的就是单链表。
双链表
单链表中的指针域只能指向节点的下一个节点。
双链表：每一个节点有两个指针域，一个指向下一个节点，一个指向上一个节点。
双链表 既可以向前查询也可以向后查询。
如图所示： 
循环链表
循环链表，顾名思义，就是链表首尾相连。
循环链表可以用来解决约瑟夫环问题。
链表的存储方式
了解完链表的类型，再来说一说链表在内存中的存储方式。
数组是在内存中是连续分布的，但是链表在内存中可不是连续分布的。
链表是通过指针域的指针链接在内存中各个节点。
所以链表中的节点在内存中不是连续分布的 ，而是散乱分布在内存中的某地址上，分配机制取决于操作系统的内存管理。
如图所示：
这个链表起始节点为2， 终止节点为7， 各个节点分布在内存的不同地址空间上，通过指针串联在一起。
链表的操作
删除节点
删除D节点，如图所示：
只要将C节点的next指针 指向E节点就可以了。
那有同学说了，D节点不是依然存留在内存里么？只不过是没有在这个链表里而已。
是这样的，所以在C++里最好是再手动释放这个D节点，释放这块内存。
其他语言例如Java、Python，就有自己的内存回收机制，就不用自己手动释放了。
添加节点
如图所示：
可以看出链表的增添和删除都是O(1)操作，也不会影响到其他节点。
但是要注意，要是删除第五个节点，需要从头节点查找到第四个节点通过next指针进行删除操作，查找的时间复杂度是O(n)。
性能分析
再把链表的特性和数组的特性进行一个对比，如图所示：
数组在定义的时候，长度就是固定的，如果想改动数组的长度，就需要重新定义一个新的数组。
链表的长度可以是不固定的，并且可以动态增删， 适合数据量不固定，频繁增删，较少查询的场景。
代码随想录题目
2.1移除链表元素:https://www.programmercarl.com/0203.%E7%A7%BB%E9%99%A4%E9%93%BE%E8%A1%A8%E5%85%83%E7%B4%A0.html
2.2设计链表:https://www.programmercarl.com/0707.%E8%AE%BE%E8%AE%A1%E9%93%BE%E8%A1%A8.html
2.3翻转链表:https://www.programmercarl.com/0206.%E7%BF%BB%E8%BD%AC%E9%93%BE%E8%A1%A8.html
2.5删除链表的倒数第N个节点:https://www.programmercarl.com/0019.%E5%88%A0%E9%99%A4%E9%93%BE%E8%A1%A8%E7%9A%84%E5%80%92%E6%95%B0%E7%AC%ACN%E4%B8%AA%E8%8A%82%E7%82%B9.html
2.7环形链表https://www.programmercarl.com/0142.%E7%8E%AF%E5%BD%A2%E9%93%BE%E8%A1%A8II.html
自己遇到的题目
3.哈希表
哈希表理论基础
哈希表
首先什么是 哈希表，哈希表（英文名字为Hash table，国内也有一些算法书籍翻译为散列表，大家看到这两个名称知道都是指hash table就可以了）。
哈希表是根据关键码的值而直接进行访问的数据结构。
这么这官方的解释可能有点懵，其实直白来讲其实数组就是一张哈希表。
哈希表中关键码就是数组的索引下标，然后通过下标直接访问数组中的元素，如下图所示：
那么哈希表能解决什么问题呢，一般哈希表都是用来快速判断一个元素是否出现集合里。
例如要查询一个名字是否在这所学校里。
要枚举的话时间复杂度是O(n)，但如果使用哈希表的话， 只需要O(1)就可以做到。
我们只需要初始化把这所学校里学生的名字都存在哈希表里，在查询的时候通过索引直接就可以知道这位同学在不在这所学校里了。
将学生姓名映射到哈希表上就涉及到了hash function ，也就是哈希函数。
哈希函数
哈希函数，把学生的姓名直接映射为哈希表上的索引，然后就可以通过查询索引下标快速知道这位同学是否在这所学校里了。
哈希函数如下图所示，通过hashCode把名字转化为数值，一般hashcode是通过特定编码方式，可以将其他数据格式转化为不同的数值，这样就把学生名字映射为哈希表上的索引数字了。
如果hashCode得到的数值大于 哈希表的大小了，也就是大于tableSize了，怎么办呢？
此时为了保证映射出来的索引数值都落在哈希表上，我们会在再次对数值做一个取模的操作，就要我们就保证了学生姓名一定可以映射到哈希表上了。
此时问题又来了，哈希表我们刚刚说过，就是一个数组。
如果学生的数量大于哈希表的大小怎么办，此时就算哈希函数计算的再均匀，也避免不了会有几位学生的名字同时映射到哈希表 同一个索引下标的位置。
接下来哈希碰撞登场
哈希碰撞
如图所示，小李和小王都映射到了索引下标 1 的位置，这一现象叫做哈希碰撞。
一般哈希碰撞有两种解决方法， 拉链法和线性探测法。
拉链法
刚刚小李和小王在索引1的位置发生了冲突，发生冲突的元素都被存储在链表中。 这样我们就可以通过索引找到小李和小王了
（数据规模是dataSize， 哈希表的大小为tableSize）
其实拉链法就是要选择适当的哈希表的大小，这样既不会因为数组空值而浪费大量内存，也不会因为链表太长而在查找上浪费太多时间。
线性探测法
使用线性探测法，一定要保证tableSize大于dataSize。 我们需要依靠哈希表中的空位来解决碰撞问题。
例如冲突的位置，放了小李，那么就向下找一个空位放置小王的信息。所以要求tableSize一定要大于dataSize ，要不然哈希表上就没有空置的位置来存放 冲突的数据了。如图所示：
其实关于哈希碰撞还有非常多的细节，感兴趣的同学可以再好好研究一下，这里我就不再赘述了。
常见的三种哈希结构
当我们想使用哈希法来解决问题的时候，我们一般会选择如下三种数据结构。
数组
set （集合）
map(映射)
这里数组就没啥可说的了，我们来看一下set。
在C++中，set 和 map 分别提供以下三种数据结构，其底层实现以及优劣如下表所示：
std::unordered_set底层实现为哈希表，std::set 和std::multiset 的底层实现是红黑树，红黑树是一种平衡二叉搜索树，所以key值是有序的，但key不可以修改，改动key值会导致整棵树的错乱，所以只能删除和增加。
std::unordered_map 底层实现为哈希表，std::map 和std::multimap 的底层实现是红黑树。同理，std::map 和std::multimap 的key也是有序的（这个问题也经常作为面试题，考察对语言容器底层的理解）。
当我们要使用集合来解决哈希问题的时候，优先使用unordered_set，因为它的查询和增删效率是最优的，如果需要集合是有序的，那么就用set，如果要求不仅有序还要有重复数据的话，那么就用multiset。
那么再来看一下map ，在map 是一个key value 的数据结构，map中，对key是有限制，对value没有限制的，因为key的存储方式使用红黑树实现的。
其他语言例如：java里的HashMap ，TreeMap 都是一样的原理。可以灵活贯通。
虽然std::set、std::multiset 的底层实现是红黑树，不是哈希表，std::set、std::multiset 使用红黑树来索引和存储，不过给我们的使用方式，还是哈希法的使用方式，即key和value。所以使用这些数据结构来解决映射问题的方法，我们依然称之为哈希法。 map也是一样的道理。
这里在说一下，一些C++的经典书籍上 例如STL源码剖析，说到了hash_set hash_map，这个与unordered_set，unordered_map又有什么关系呢？
实际上功能都是一样一样的， 但是unordered_set在C++11的时候被引入标准库了，而hash_set并没有，所以建议还是使用unordered_set比较好，这就好比一个是官方认证的，hash_set，hash_map 是C++11标准之前民间高手自发造的轮子。
总结
总结一下，当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法。
但是哈希法也是牺牲了空间换取了时间，因为我们要使用额外的数组，set或者是map来存放数据，才能实现快速的查找。
代码随想录题目
3.3快乐数:https://www.programmercarl.com/0202.%E5%BF%AB%E4%B9%90%E6%95%B0.html#%E6%80%9D%E8%B7%AF
3.4两数之和:https://www.programmercarl.com/0001.%E4%B8%A4%E6%95%B0%E4%B9%8B%E5%92%8C.html
3.5四数相加II:https://www.programmercarl.com/0454.%E5%9B%9B%E6%95%B0%E7%9B%B8%E5%8A%A0II.html
3.6赎金信:https://www.programmercarl.com/0383.%E8%B5%8E%E9%87%91%E4%BF%A1.html#%E6%80%9D%E8%B7%AF
3.7三数之和:https://www.programmercarl.com/0015.%E4%B8%89%E6%95%B0%E4%B9%8B%E5%92%8C.html
3.8四数之和:https://www.programmercarl.com/0018.%E5%9B%9B%E6%95%B0%E4%B9%8B%E5%92%8C.html
3.1 有效的字母异位词
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
示例 1: 输入: s = "anagram", t = "nagaram" 输出: true
示例 2: 输入: s = "rat", t = "car" 输出: false
**说明:** 你可以假设字符串只包含小写字母。import java.util.ArrayList;
public class Main {
public static void main(String[] args) {
String s = "nl";
String t = "cx";
System.out.println(isAnagram(s,t));
}
public static boolean isAnagram(String s, String t) {
int hx []=new int [26];
for (int i = 0; i < s.length(); i++) {
hx[s.charAt(i)-'a']++;
}
for (int j = 0; j < t.length(); j++) {
hx[t.charAt(j)-'a']--;
}
for (int i = 0; i < 26; i++) { //要循环26次 或用增强型for循环
if(hx[i]!=0){
return false;
}
}
return true;
}
}3.2两个数组的交集
题意：给定两个数组，编写一个函数来计算它们的交集。
说明： 输出结果中的每个元素一定是唯一的。 我们可以不考虑输出结果的顺序
//使用hashset
import java.util.HashSet;
import java.util.Set;
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) {
return new int[0];
}
Set<Integer> set1 = new HashSet<>();
Set<Integer> resSet = new HashSet<>();
//遍历数组1
for (int i : nums1) {
set1.add(i);
}
//遍历数组2的过程中判断哈希表中是否存在该元素
for (int i : nums2) {
if (set1.contains(i)) {
resSet.add(i);
}
}
//方法1：将结果集合转为数组
return resSet.stream().mapToInt(x -> x).toArray();
//方法2：另外申请一个数组存放setRes中的元素,最后返回数组
int[] arr = new int[resSet.size()];
int j = 0;
for(int i : resSet){
arr[j++] = i;
}
return arr;
}
}
//使用hash数组
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
int[] hash1 = new int[1002];
int[] hash2 = new int[1002];
for(int i : nums1)
hash1[i]++;
for(int i : nums2)
hash2[i]++;
List<Integer> resList = new ArrayList<>();
for(int i = 0; i < 1002; i++)
if(hash1[i] > 0 && hash2[i] > 0)
resList.add(i);
int index = 0;
int res[] = new int[resList.size()];
for(int i : resList)
res[index++] = i;
return res;
}
}3.3 快乐数
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。如果 可以变为 1，那么这个数就是快乐数。
如果 n 是快乐数就返回 True ；不是，则返回 False 。
**示例：**
输入：19
输出：true
解释：
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1class Solution {
public boolean isHappy(int n) {
Set<Integer> record = new HashSet<>();
while (n != 1 && !record.contains(n)) {
record.add(n);
n = getNextNumber(n);
}
return n == 1;
}
private int getNextNumber(int n) {//得到下一个数字
int res = 0;
while (n > 0) {
int temp = n % 10;
res += temp * temp;
n = n / 10;
}
return res;
}
}3.3两数之和
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
**示例:**
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]//暴力
import java.util.Arrays;
public class TwoSum {
public static int[] twoSum(int[] nums, int target) {
int[] result = new int[2];
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] == target) {
result[0] = i;
result[1] = j;
break;
}
}
}
return result;
}
public static void main(String[] args) {
int[] nums = {2, 7, 11, 15};
int target = 9;
int[] result = twoSum(nums, target);
System.out.println(Arrays.toString(result));
}
}
//哈希法
public int[] twoSum(int[] nums, int target) {
int[] res = new int[2];
if(nums == null || nums.length == 0){
return res;
}
Map<Integer, Integer> map = new HashMap<>();
for(int i = 0; i < nums.length; i++){
int temp = target - nums[i]; // 遍历当前元素，并在map中寻找是否有匹配的key
if(map.containsKey(temp)){
res[1] = i;
res[0] = map.get(temp);
break;
}
map.put(nums[i], i); // 如果没找到匹配对，就把访问过的元素和下标加入到map中
}
return res;
}3.4 四数相加2
给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。
为了使问题简单化，所有的 A, B, C, D 具有相同的长度 N，且 0 ≤ N ≤ 500 。所有整数的范围在 -2^28 到 2^28 - 1 之间，最终结果不会超过 2^31 - 1 。
**例如:**
输入:
- A = [ 1, 2]
- B = [-2,-1]
- C = [-1, 2]
- D = [ 0, 2]
输出:
2
**解释:**
两个元组如下:
1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0class Solution {
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
int res = 0;
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
//统计两个数组中的元素之和，同时统计出现的次数，放入map
for (int i : nums1) {
for (int j : nums2) {
int sum = i + j;
map.put(sum, map.getOrDefault(sum, 0) + 1);//如果键对应的值不存在,则返回0
}
}
//统计剩余的两个元素的和，在map中找是否存在相加为0的情况，同时记录次数
for (int i : nums3) {
for (int j : nums4) {
res += map.getOrDefault(0 - i - j, 0);
}
}
return res;
}
}
//首先定义 map，key放a和b两数之和，value 放a和b两数之和出现的次数。
//遍历大A和大B数组，统计两个数组元素之和，和出现的次数，放到map中。
//定义int变量res，用来统计 a+b+c+d = 0 出现的次数。
//在遍历大C和大D数组，找到如果 0-(c+d) 在map中出现过的话，就用count把map中key对应的value也就是出现次数统计出来。
//最后返回统计值 count 就可以了3.5 赎金信
给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串，判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成。如果可以构成，返回 true ；否则返回 false。
(题目说明：为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思。杂志字符串中的每个字符只能在赎金信字符串中使用一次。)
**注意：**
你可以假设两个字符串均只含有小写字母。
canConstruct("a", "b") -> false
canConstruct("aa", "ab") -> false
canConstruct("aa", "aab") -> true//暴力算法
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
StringBuilder sb = new StringBuilder(ransomNote);
for (int i = 0; i < magazine.length(); i++) {
for (int j = 0; j < sb.length(); j++) {
if (magazine.charAt(i) == sb.charAt(j)) {
sb.deleteCharAt(j);
break;
}
}
}
return sb.length() == 0;
}
}
//哈希法
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
// shortcut
if (ransomNote.length() > magazine.length()) {
return false;
}
// 定义一个哈希映射数组
int[] record = new int[26];
// 遍历
for(char c : magazine.toCharArray()){
record[c - 'a'] += 1;
}
for(char c : ransomNote.toCharArray()){
record[c - 'a'] -= 1;
}
// 如果数组中存在负数，说明ransomNote字符串总存在magazine中没有的字符
for(int i : record){
if(i < 0){
return false;
}
}
return true;
}
}3.6 三数之和
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
注意： 答案中不可以包含重复的三元组。
示例：
给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为： [ [-1, 0, 1], [-1, -1, 2] ]//双指针
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);
// 找出a + b + c = 0
// a = nums[i], b = nums[left], c = nums[right]
for (int i = 0; i < nums.length; i++) {
// 排序之后如果第一个元素已经大于零，那么无论如何组合都不可能凑成三元组，直接返回结果就可以了
if (nums[i] > 0) {
return result;
}
if (i > 0 && nums[i] == nums[i - 1]) { // 去重a
continue;
}
int left = i + 1;
int right = nums.length - 1;
while (right > left) {
int sum = nums[i] + nums[left] + nums[right];
if (sum > 0) {
right--;
} else if (sum < 0) {
left++;
} else {
result.add(Arrays.asList(nums[i], nums[left], nums[right]));
// 去重逻辑应该放在找到一个三元组之后，对b 和 c去重
while (right > left && nums[right] == nums[right - 1]) right--;
while (right > left && nums[left] == nums[left + 1]) left++;
right--;
left++;
}
}
}
return result;
}
}3.7 四数之和
题意：给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
注意：
答案中不可以包含重复的四元组。
示例： 给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。 满足要求的四元组集合为： [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);
for (int i = 0; i < nums.length; i++) {
// nums[i] > target 直接返回, 剪枝操作
if (nums[i] > 0 && nums[i] > target) {
return result;
}
if (i > 0 && nums[i - 1] == nums[i]) { // 对nums[i]去重
continue;
}
for (int j = i + 1; j < nums.length; j++) {
if (j > i + 1 && nums[j - 1] == nums[j]) { // 对nums[j]去重
continue;
}
int left = j + 1;
int right = nums.length - 1;
while (right > left) {
// nums[k] + nums[i] + nums[left] + nums[right] > target int会溢出
long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
if (sum > target) {
right--;
} else if (sum < target) {
left++;
} else {
result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
// 对nums[left]和nums[right]去重
while (right > left && nums[right] == nums[right - 1]) right--;
while (right > left && nums[left] == nums[left + 1]) left++;
left++;
right--;
}
}
}
}
return result;
}
}自己遇到的题目
3.1卡牌游戏
题目描述
阿岳在玩卡片拼接游戏，游戏规则如下:
每次会给你n张卡片，每张卡片上都会有一个字符，你需要将所有不重复的卡片按照ASCLL进行从大到小的排序，
得到的是无重复有序的字符串
输入
一个字符串s 表示所有的卡片
输出
一个有序且不重复的字符串
测试点数据规模与约定
对于100%的测试点，保证s 中所有的字符都是小写字母，且0≤s.length() ≤105
样例输入
aabcc
样例输出
cba//方法一 哈希表
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
char[] c = sc.nextLine().toCharArray();
//arr数组记录每个字母是否出现
boolean[] arr = new boolean[26];
for(char temp : c){
arr[temp - 'a'] = true;// arr[temp - 97] = true;
}
//从后往前输出字符串出现的字母
for (int i = 25; i >= 0; i--) {
if(arr[i]){
System.out.print((char)(97+i));
}
}
}
}4.字符串
字符串理论基础
代码随想录题目
4.2反转字符串II:https://www.programmercarl.com/0541.%E5%8F%8D%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2II.html
4.3 替换数字:https://www.programmercarl.com/kama54.%E6%9B%BF%E6%8D%A2%E6%95%B0%E5%AD%97.html
4.5右旋字符串:https://www.programmercarl.com/kama55.%E5%8F%B3%E6%97%8B%E5%AD%97%E7%AC%A6%E4%B8%B2.html
4.6实现 strStr():https://www.programmercarl.com/0028.%E5%AE%9E%E7%8E%B0strStr.html
4.1 反转字符串
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。
示例 1：
输入：["h","e","l","l","o"]
输出：["o","l","l","e","h"]
示例 2：
输入：["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]class Solution {
public void reverseString(char[] s) {
for(int i=0,j=s.length-1;i<j;i++,j--){
char temp;
temp = s[i];
s[i]=s[j];
s[j]= temp;
}
}
}
class Solution {
public void reverseString(char[] s) {
int l = 0;
int r = s.length - 1;
while (l < r) {
s[l] ^= s[r]; //构造 a ^ b 的结果，并放在 a 中
s[r] ^= s[l]; //将 a ^ b 这一结果再 ^ b ，存入b中，此时 b = a, a = a ^ b
s[l] ^= s[r]; //a ^ b 的结果再 ^ a ，存入 a 中，此时 b = a, a = b 完成交换
l++;
r--;
}
}
}
// 第二种方法用temp来交换数值更多人容易理解些
class Solution {
public void reverseString(char[] s) {
int l = 0;
int r = s.length - 1;
while(l < r){
char temp = s[l];
s[l] = s[r];
s[r] = temp;
l++;
r--;
}
}
}4.2 反转字符串II
给定一个字符串 s 和一个整数 k，从字符串开头算起, 每计数至 2k 个字符，就反转这 2k 个字符中的前 k 个字符。
如果剩余字符少于 k 个，则将剩余字符全部反转。
如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。
示例:
输入: s = "abcdefg", k = 2
输出: "bacdfeg"//解法一
class Solution {
public String reverseStr(String s, int k) {
StringBuffer res = new StringBuffer();
int length = s.length();
int start = 0;
while (start < length) {
// 找到k处和2k处
StringBuffer temp = new StringBuffer();
// 与length进行判断，如果大于length了，那就将其置为length
int firstK = (start + k > length) ? length : start + k;
int secondK = (start + (2 * k) > length) ? length : start + (2 * k);
//无论start所处位置，至少会反转一次
temp.append(s.substring(start, firstK));
res.append(temp.reverse());
// 如果firstK到secondK之间有元素，这些元素直接放入res里即可。
if (firstK < secondK) { //此时剩余长度一定大于k。
res.append(s.substring(firstK, secondK));
}
start += (2 * k);
}
return res.toString();
}
}
//解法二（似乎更容易理解点）
//题目的意思其实概括为 每隔2k个反转前k个，尾数不够k个时候全部反转
class Solution {
public String reverseStr(String s, int k) {
char[] ch = s.toCharArray();
for(int i = 0; i < ch.length; i += 2 * k){
int start = i;
//这里是判断尾数够不够k个来取决end指针的位置
int end = Math.min(ch.length - 1, start + k - 1);
//用异或运算反转
while(start < end){
ch[start] ^= ch[end];
ch[end] ^= ch[start];
ch[start] ^= ch[end];
start++;
end--;
}
}
return new String(ch);
}
}
// 解法二还可以用temp来交换数值，会的人更多些
class Solution {
public String reverseStr(String s, int k) {
char[] ch = s.toCharArray();
for(int i = 0;i < ch.length;i += 2 * k){
int start = i;
// 判断尾数够不够k个来取决end指针的位置
int end = Math.min(ch.length - 1,start + k - 1);
while(start < end){
char temp = ch[start];
ch[start] = ch[end];
ch[end] = temp;
start++;
end--;
}
}
return new String(ch);
}
}
// 解法3
class Solution {
public String reverseStr(String s, int k) {
char[] ch = s.toCharArray();
// 1. 每隔 2k 个字符的前 k 个字符进行反转
for (int i = 0; i< ch.length; i += 2 * k) {
// 2. 剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符
if (i + k <= ch.length) {
reverse(ch, i, i + k -1);
continue;
}
// 3. 剩余字符少于 k 个，则将剩余字符全部反转
reverse(ch, i, ch.length - 1);
}
return new String(ch);
}
// 定义翻转函数
public void reverse(char[] ch, int i, int j) {
for (; i < j; i++, j--) {
char temp = ch[i];
ch[i] = ch[j];
ch[j] = temp;
}
}
}4.3 实现 strStr()
实现 strStr() 函数。
给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。
示例 1: 输入: haystack = "hello", needle = "ll" 输出: 2
示例 2: 输入: haystack = "aaaaa", needle = "bba" 输出: -1
说明: 当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。 对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。//kmp算法
文本串 a a b a a b a a f
模式串 a a b a a f
前缀表 0 1 0 1 2 0
next数组 -1 0 1 0 1 2
next数组 -1 0 -1 0 1 -1
前缀表：记录下表i之前（包括）i的字符串中，有多大长度相等的前缀后缀
前缀：指不包含最后一个字符的所有以第一个字符开头的连续子串
后缀： 指不包含第一个字符的所有以最后一个字符结尾的连续子串
最长相等前后缀：前缀和后缀相等长度的最大值
a:0 前 0 后 0 0
aa:1 前 a 后 a 1
aab:0 前 a aa 后 b ab 1
aaba:1 前 a aa aab 后 a ba aba 1
aabaa:2 前 a aa aab aaba 后 a aa baa abaa 2
aabaaf:0 前 a aa aab aaba aabaa 后 f af aaf baaf abaaf 0
class Solution {
/**
* 基于窗口滑动的算法
* <p>
* 时间复杂度：O(m*n)
* 空间复杂度：O(1)
* 注：n为haystack的长度，m为needle的长度
*/
public int strStr(String haystack, String needle) {
int m = needle.length();
// 当 needle 是空字符串时我们应当返回 0
if (m == 0) {
return 0;
}
int n = haystack.length();
if (n < m) {
return -1;
}
int i = 0;
int j = 0;
while (i < n - m + 1) {
// 找到首字母相等
while (i < n && haystack.charAt(i) != needle.charAt(j)) {
i++;
}
if (i == n) {// 没有首字母相等的
return -1;
}
// 遍历后续字符，判断是否相等
i++;
j++;
while (i < n && j < m && haystack.charAt(i) == needle.charAt(j)) {
i++;
j++;
}
if (j == m) {// 找到
return i - j;
} else {// 未找到
i -= j - 1;
j = 0;
}
}
return -1;
}
}
// 方法一
class Solution {
public void getNext(int[] next, String s){
int j = -1;
next[0] = j;
for (int i = 1; i < s.length(); i++){
while(j >= 0 && s.charAt(i) != s.charAt(j+1)){
j=next[j];
}
if(s.charAt(i) == s.charAt(j+1)){
j++;
}
next[i] = j;
}
}
public int strStr(String haystack, String needle) {
if(needle.length()==0){
return 0;
}
int[] next = new int[needle.length()];
getNext(next, needle);
int j = -1;
for(int i = 0; i < haystack.length(); i++){
while(j>=0 && haystack.charAt(i) != needle.charAt(j+1)){
j = next[j];
}
if(haystack.charAt(i) == needle.charAt(j+1)){
j++;
}
if(j == needle.length()-1){
return (i-needle.length()+1);
}
}
return -1;
}
}
class Solution {
//前缀表（不减一）Java实现
public int strStr(String haystack, String needle) {
if (needle.length() == 0) return 0;
int[] next = new int[needle.length()];
getNext(next, needle);
int j = 0;
for (int i = 0; i < haystack.length(); i++) {
while (j > 0 && needle.charAt(j) != haystack.charAt(i))
j = next[j - 1];
if (needle.charAt(j) == haystack.charAt(i))
j++;
if (j == needle.length())
return i - needle.length() + 1;
}
return -1;
}
private void getNext(int[] next, String s) {
int j = 0;
next[0] = 0;
for (int i = 1; i < s.length(); i++) {
while (j > 0 && s.charAt(j) != s.charAt(i))
j = next[j - 1];
if (s.charAt(j) == s.charAt(i))
j++;
next[i] = j;
}
}
}4.4 重复的子字符串
给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。
示例 1:
输入: "abab"
输出: True
解释: 可由子字符串 "ab" 重复两次构成。
示例 2:
输入: "aba"
输出: False
示例 3:
输入: "abcabcabcabc"
输出: True
解释: 可由子字符串 "abc" 重复四次构成。 (或者子字符串 "abcabc" 重复两次构成。)//暴力法
public class Solution {
public boolean repeatedSubstringPattern(String s) {
int len = s.length();
for (int i = 1; i <= len / 2; i++) {
if (len % i == 0) {
String subStr = s.substring(0, i);
StringBuilder sb = new StringBuilder();
for (int j = 0; j < len / i; j++) {
sb.append(subStr);
}
if (sb.toString().equals(s)) {
return true;
}
}
}
return false;
}
}
//kmp法
class Solution {
public boolean repeatedSubstringPattern(String s) {
if (s.equals("")) return false;
int len = s.length();
// 原串加个空格(哨兵)，使下标从1开始，这样j从0开始，也不用初始化了
s = " " + s;
char[] chars = s.toCharArray();
int[] next = new int[len + 1];
// 构造 next 数组过程，j从0开始(空格)，i从2开始
for (int i = 2, j = 0; i <= len; i++) {
// 匹配不成功，j回到前一位置 next 数组所对应的值
while (j > 0 && chars[i] != chars[j + 1]) j = next[j];
// 匹配成功，j往后移
if (chars[i] == chars[j + 1]) j++;
// 更新 next 数组的值
next[i] = j;
}
// 最后判断是否是重复的子字符串，这里 next[len] 即代表next数组末尾的值
if (next[len] > 0 && len % (len - next[len]) == 0) {
return true;
}
return false;
}
}
//移动匹配
public class Solution {
public boolean repeatedSubstringPattern(String s) {
String concatenated = s + s;
return concatenated.substring(1, concatenated.length() - 1).contains(s);//要刨除 s + s 的首字符和尾字符，这样避免在s+s中搜索出原来的s，我们要搜索的是中间拼接出来的s
}
}自己遇到的题目
4.1 判断密码
在一个新的软件上注册账号时，填写密码时，网站通常都有一个标准，以防止你的密码设置的太简单。现在想请你编写代码，完成这个功能。
题目中会给你一个字符串 `s` 代表新建立的密码，密码需要符合两个条件才算合格：首先，密码长度要大于等于六；其次，密码中需要包含大写字母，小写字母和数字。
现在请你编写代码，判断用户注册的新密码是否合格，如果合格，则返回 `True`，否则返回 `False`。
输入格式** 一个字符串 `s`。
*输出格式** `True` 或 `False`。
输入输出样例1**输入** `abc`**输出** `False`
输入输出样例2 输入** `abcA12`**输出** `True`package org.example;
import java.util.Scanner;
public class BankRate {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str = sc.next();
int if_len = 0;
int if_num = 0;
int if_ABC = 0;
int if_abc = 0;
char[] charArray;
charArray = str.toCharArray();
if(str.length()>=6){
if_len++;
}
for (int i = 0; i < charArray.length; i++) {
if(charArray[i]<='9'&&charArray[i]>='0'){
if_num++;
}
if(charArray[i]<='z'&&charArray[i]>='a'){
if_abc++;
}
if (charArray[i]<='Z'&&charArray[i]>='A'){
if_ABC++;
}
}
if(if_len==1&&if_num>0&&if_abc>0&&if_ABC>0){
System.out.println("True");
}else{
System.out.println("False");
}
}
}4.2找字符串
经过前两次的失败，小明终于在他喜欢的女孩子面前不结巴。所以他鼓起勇气尝试了第三次表白，题目中会给你一个字符串 `s`，请你找到 `s` 中小明说了多少次 `love`？如果没有找到，请输出表白失败，现在请你编写代码计算并输出结果。
输入格式 一个字符串 `s`。
输出格式 一个整数。
输入输出样例1输入 `lov`输出 `表白失败`
输入输出样例2输入 `lllovell`输出** `1`import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String s = scanner.nextLine();
int count = 0;
int index = 0;
while ((index = s.indexOf("love", index)) != -1) {
count++;
index += 4; // 跳过找到的 "love"
}
if (count == 0) {
System.out.println("表白失败");
} else {
System.out.println(count);
}
}
}4.3最长子串
题目中会给你两个字符串 `s1` 和 `s2`。定义他们子串的方式是在某一个字符串 `s` 中删除一些元素（可以删除零个元素），剩下的元素就是 `s` 的子串。如 `s="abcd"`，删除 `c` 后，`abd` 就是他的子串之一。
其次，`s1` 的子串不能是 `s2` 的子串。`s2` 的子串不能是 `s1` 的子串。现在请你编写代码计算 `s1` 和 `s2` 所有子串中，最长的子串的长度。
第一行，一个字符串 `s1`。 第二行，一个字符串 `s2`。
输出格式一个整数。
输入输出样例1输入 abc|abc输出-1
输入输出样例2输入 zbc|abc输出 3import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in =new Scanner(System.in);
String str1=in.next();
String str2=in.next();
if (str1.equals(str2)){
System.out.println(-1);
return;
}
int max=Math.max(str1.length(),str2.length());
System.out.println(max);
}
}4.4 回文时钟
小爱同学最近特别迷恋回文字符串。以至于他看时间都想找到回文字符串，现在题目中会给你一个时间字符串 `s`（形式如 `HH:MM` 24 小时制）请你找到这一个时刻之前的一个回文时间和之后的一个回文时间并输出。
如 `s=01:00`，之前的一个回文时间为 `00:00`,之后的一个回文时间为 `01:10`。但输出输出不含前导 `0`。故输出 `0:0,1:10`。
现在请你编写代码，完成上述操作。
输入格式 一个字符串 `s`。
输出格式 第一行，一个字符串代表之前的一个回文时间。 第二行，一个字符串代表之后的一个回文时间。
输入输出样例
输入 `01:00`
输出 `0:0` `1:10`
输入输出样例2
输入 `05:25`
输出 `4:40` `5:50`import java.util.Scanner;
public class Main {
public static int abc(int a, int b) { // Function to check if the time is palindromic
int t = 0;
if (a / 10 == b % 10 && a % 10 == b / 10)
t = 1;
return t;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String input = sc.nextLine();
int x, y, m, n;
x = Integer.parseInt(input.substring(0, 2));
y = Integer.parseInt(input.substring(3, 5));
int z = x * 60 + y;
// Search for the nearest palindromic time before the given time
for (int i = z - 1; i >= 0; i--) {
m = i / 60;
n = i % 60;
if (abc(m, n) == 1) {
System.out.println(m + ":" + n);
break;
}
}
// Search for the nearest palindromic time after the given time
for (int i = z + 1; i < 1440; i++) {
m = i / 60;
n = i % 60;
if (abc(m, n) == 1) {
System.out.println(m + ":" + n);
break;
}
}
}
}4.5 字符串时间处理
小艾现在想统计他每次做作业会花多长时间，所以他记录了开始写作业和写完作业的时间，想让你帮他计算一下花了多少秒。
题目中会给你两个时间，时间格式为 `xdayHH:MM:SS`，现在请你编写代码，帮小艾计算他写作业花了多少秒？
输入格式两行，每行一个时间。
输出格式 一个整数。
输入输出样例1输入1day03:00:12 1day04:00:12 输出 3600
输入输出样例2输入123day15:00:01 19999day15:00:00 输出 1717286399import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// Read the two times as strings
String startTime = scanner.nextLine();
String endTime = scanner.nextLine();
// Parse the strings and calculate the duration in seconds
long durationInSeconds = calculateDurationInSeconds(startTime, endTime);
// Output the duration in seconds
System.out.println(durationInSeconds);
scanner.close();
}
private static long calculateDurationInSeconds(String start, String end) {
// Extract the day, hours, minutes, and seconds from the start time
int startDay = Integer.parseInt(start.substring(0, start.indexOf("day")));
int startHour = Integer.parseInt(start.substring(start.indexOf("day") + 3, start.indexOf(":")));
int startMinute = Integer.parseInt(start.substring(start.indexOf(":") + 1, start.lastIndexOf(":")));
int startSecond = Integer.parseInt(start.substring(start.lastIndexOf(":") + 1));
// Extract the day, hours, minutes, and seconds from the end time
int endDay = Integer.parseInt(end.substring(0, end.indexOf("day")));
int endHour = Integer.parseInt(end.substring(end.indexOf("day") + 3, end.indexOf(":")));
int endMinute = Integer.parseInt(end.substring(end.indexOf(":") + 1, end.lastIndexOf(":")));
int endSecond = Integer.parseInt(end.substring(end.lastIndexOf(":") + 1));
// Convert everything to seconds
long startInSeconds = (long)startDay * 86400 + startHour * 3600 + startMinute * 60 + startSecond;
long endInSeconds = (long)endDay * 86400 + endHour * 3600 + endMinute * 60 + endSecond;
// Calculate the duration in seconds
return endInSeconds - startInSeconds;
}
}4.6 只有ab组成的字符串
现在题目中会给你一个字符串 `s`，请你判断该字符串是否由若干个 `ab` 组成的。其中，如果 `ab` 顺序不对或者没有组成完整的 `ab` 或者出现了其他元素，`s` 都不算由 `ab` 组成。在请你编写代码并判断 `s` 是否只由 `ab` 组成。如果是，则返回 `True`，否则返回 `False`。
输入格式 一个字符串 `s`。
输出格式 `True` 或 `False`。
输入输出样例1输入 `ab`输出 `True`
输入输出样例2输入 `aba`输 `False`private static boolean is MadeOfAB(String s){
if(s.length()%2!=0){
return false;
}
for(int i =0;i<length();i+=2){
if(s.chatAt(i)!=a||s.chatAt(i+1)!='b'){
return false;
}
}
return true;
}4.7比较字符串
有一天，阿岳的信息安全老师布置了一个作业，要求编写一个程序，比较两个相同进制（2进制~16进制）的数值大小。从键盘上输入两个正确（数码符合当前进制）的相同进制的数值字符串（不带正负号，没有小数点），比较大小，输出“>”，“<”或者"="。注意：设计的算法与具体的进制无关。阿岳一看到这个题目，就觉得很有趣，直接上手做起来。
**输入**
第一行 一个字符串*Sa* 表示参与比较的第一个字符串
第一行 一个字符串*Sb* 表示参与比较的第二个字符串
**输出**
一个字符 表示比较的结果("<"、">"或"=")
**测试点数据规模与约定**
对于100%的测试点，保证0<*Sa.length* ,*Sb.length* <100
样例输入
123
1234
样例输出
<使用ASCII比较即可
import java.util.*;
public class q1538 {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
cmp(sc.next(),sc.next());
}
public static void cmp(String s1,String s2) {
boolean flag=false;
if(s1.length()>s2.length()) System.out.println(">");
else if(s1.length()<s2.length()) System.out.println("<");
else {
for(int i=0;i<s1.length();i++) {
if(s1.charAt(i)>s2.charAt(i)) {
System.out.println(">");
return;
}
else if(s1.charAt(i)<s2.charAt(i)) {
System.out.println("<");
return;
}
}
System.out.println("=");
return;
}
}
}4.8 矩形的数目
给你一个二维数组 `nums` ，其中 `nums[i]=[li,wi]` 表示第 `i` 个矩形的长度为 `li` 、宽度为 `wi` 。
如果存在 `k` 同时满足 `k≤li` 和 `k≤wi` ，就可以将第 `i` 个矩形切成边长为 `k` 的正方形。例如，矩形 `[5,7]` 可以切成边长最大为 `5` 的正方形。
设 `maxLen` 为可以从矩形数组 `nums` 切分得到的最大正方形的边长。
请你计算有多少个矩形能够切出边长为 `maxLen` 的正方形，并返回矩形数目 。
#### 输入输出格式
**输入格式** 一行二维整型数组。
**输出格式** 一行整数。
#### 输入输出样例
**输入** `[[2,3],[3,7],[4,3],[3,7]]` **输出** `3` **解释** `[[2,3],[3,7],[4,3],[3,7]]`中，`[3,7],[4,3],[3,7]`三个矩形都可以切出边长最大为 `3` 的正方形,因此输出 `3`。
#### 说明提示
- `1≤nums.length≤1000`
- `nums[i].length=2`
- `1≤li,wi≤109`
- `li\\=wi`package org.example;
import java.util.ArrayList;
import java.util.List;
public class Main1 {
public static void main(String[] args) {
String input = "[[2,3],[3,7],[4,3],[3,7]]"; // 替换为你的输入字符串
// 解析输入的字符串为二维数组
int[][] nums = parseInput(input);
int result = countMaxLenSquares(nums);
System.out.println("能切出最大正方形边长的矩形数量为：" + result);
}
public static int[][] parseInput(String input) {
// 去除字符串中的非数字字符和方括号
input = input.replaceAll("[^0-9,]", "");
String[] parts = input.split(",");
int[][] nums = new int[parts.length / 2][2];
for (int i = 0; i < parts.length; i += 2) {
nums[i / 2][0] = Integer.parseInt(parts[i]);
nums[i / 2][1] = Integer.parseInt(parts[i + 1]);
}
return nums;
}
public static int countMaxLenSquares(int[][] rectangles) {
int maxLen = 0;
for (int[] rect : rectangles) {
maxLen = Math.max(maxLen, Math.min(rect[0], rect[1]));
}
int count = 0;
for (int[] rect : rectangles) {
if (Math.min(rect[0], rect[1]) >= maxLen) {
count++;
}
}
return count;
}
}4.9 坐标轴移动
给定一个初始坐标[0,0],初始方向向东，当输入.时移动一个单位，当输入<时逆时针旋转90度，当输入>时顺时针旋转90度
输入：给出字符串，例如..><><
输出：坐标import java.util.*;
public class Main {
public static void main(String[] args) {
//=======begin=======
Scanner sc =new Scanner(System.in);
String s = sc.next();
int temp=0;
int [] result ={0,0};
for(int i=0;i<s.length();i++){
if(s.charAt(i)=='.'){
result= ld(result,temp);
}else if(s.charAt(i)=='>'){
temp=(temp-90)%360;
}else if(s.charAt(i)=='<'){
temp=(temp+90)%360;
}
}
System.out.println(Arrays.toString(result));
}
public static int []ld(int s[],int temp){
if(temp==90||temp==-270){
s[1]=s[1]+1;
}else if(temp==180||temp==-180){
s[0]=s[0]-1;
}else if(temp==270||temp==-90){
s[1]=s[1]-1;
}else if(temp==0){
s[0]=s[0]+1;
}
return s;
}
//========end========
}5.0 注册账号密码限制
为了更好地保护用户账户安全，很多网站对用户注册账号时输入的密码作出如下限制：
1.密码长度至少为8位；
2.大写字母、小写字母、数字、特殊符号（@、#、！、%、*、$、～等），以上四种至少包含两种。
请编写一个方法用于判断用户注册时输入的密码是否符合条件及强弱程度，具体判断依据如下：密码长度小于8则判定为不符合要求并输出“NG”；密码长度大于等于8时，若只包含一种符号，则判定为不符合要求并输出“NG”，若包含2种符号，则判定为中等强度并输出“MG”，若包含3种符号，则判定为强并输出“VG”，若包含全部4种字符为极强并输出“EG”。
输入说明：一个用户输入的密码字符串，可能存在大写字母、小写字母、数字、特殊符号，长度为n(0<=n<=1000)
输出说明：判断结果，若不符合条件，则输出“NG”；符合要求且强度中等，则输出MG，强则输出VG，极强则输出EG。
输入样例1: 12345678910
输入样例2: wer123Qpublic class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String str = scanner.next();
int len = str.length();
if (len < 8) {
System.out.println("NG");
} else {
HashSet<Integer> record = new HashSet<>();//HashSet不重复
for (int i = 0; i < len; i++) {
char c = str.charAt(i);
if (c >= 'A' && c <= 'Z') {
record.add(1);
} else if (c >= 'a' && c <= 'z') {
record.add(2);
} else if (c >= '0' && c <= '9') {
record.add(3);
} else {
record.add(4);
}
if (record.size() == 1) {
System.out.println("NG");
} else if (record.size() == 2) {
System.out.println("MG");
} else if (record.size() == 3) {
System.out.println("VG");
} else {
System.out.println("EG");
}
}
}
}
}5.1 判断回文数1
输入一个正整数 n，判断其是否为回文数，若是回文数则输出 true，否则输出 false。
测试输入：
12345
预期输出：
false
测试输入：
12321
预期输出：
trueimport java.util.Scanner;
public class Palindrome {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String num = scanner.nextLine();
Boolean flag = true;
for (int i = 0, j = num.length() - 1; i < j; i++, j--) {
if (num.charAt(i) != num.charAt(j)) {
flag=false;
}
}
if(flag){
System.out.println(flag);
}else{
System.out.println(flag);
}
}
}5.2 判断回文数2
小虎突然发现有些正整数的形状像一座“山”，比如123565321、145541，
它们左右对称（回文）且数位上的数字先单调不减，后单调不增。
小虎 数了很久也没有数完，他想让你告诉他在区间[2023,20232023] 中有多少个数的形状像一座“山”。
提示
只需输出答案即可public class Main {
public static void main(String[] args) {
int ans = 0;
for (int i = 2023; i < 20232024; i++) {
if(judge(i+""))ans++;
}
System.out.println(ans);
}
public static boolean judge(String s){
int n = s.length();
//判断是否回文
for (int i = 0; i < n/2; i++) {
if(s.charAt(i)!=s.charAt(n-i-1))return false;
}
//判断数位的数字是否符合要求
for (int i = 0; i < n/2; i++) {
if(s.charAt(i)>s.charAt(i+1))return false;
}
return true;
}
}5.3 卡牌游戏
题目描述
阿岳在玩卡片拼接游戏，游戏规则如下:
每次会给你n张卡片，每张卡片上都会有一个字符，你需要将所有不重复的卡片按照ASCLL进行从大到小的排序，
得到的是无重复有序的字符串
输入
一个字符串s 表示所有的卡片
输出
一个有序且不重复的字符串
测试点数据规模与约定
对于100%的测试点，保证s 中所有的字符都是小写字母，且0≤s.length() ≤105
样例输入
aabcc
样例输出
cba//方法一 哈希表
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
char[] c = sc.nextLine().toCharArray();
//arr数组记录每个字母是否出现
boolean[] arr = new boolean[26];
for(char temp : c){
arr[temp - 'a'] = true;// arr[temp - 97] = true;
}
//从后往前输出字符串出现的字母
for (int i = 25; i >= 0; i--) {
if(arr[i]){
System.out.print((char)(97+i));
}
}
}
}
//方法二 HashSet(基于哈希表实现)
import java.util.*;
public class CardSorting {
public static String sortUniqueChars(String s) {
HashSet<Character> set = new HashSet<>();//
// 将字符添加到 HashSet 去除重复
for (char c : s.toCharArray()) {
set.add(c);
}
// 转换成有序的字符数组
Character[] uniqueChars = set.toArray(new Character[0]);//new Character[0] 是为了告诉 Java 应该创建一个 Character 类型的数组，以便将 HashSet 中的元素复制到这个数组中。
Arrays.sort(uniqueChars, Collections.reverseOrder());
// 构建最终的字符串
StringBuilder result = new StringBuilder();
for (char c : uniqueChars) {
result.append(c);
}
return result.toString();
}
public static void main(String[] args) {
Scanner sc =new Scanner(System.in);
String s = sc.nextLine();
String sortedUniqueChars = sortUniqueChars(s);
System.out.println(sortedUniqueChars);
}
}
// 方法三 TreeSet(基于红黑树)
import java.util.*;
public class CardSorting {
public static String sortUniqueChars(String s) {
TreeSet<Character> set = new TreeSet<>(Collections.reverseOrder());//TreeSet 是一个基于红黑树的实现，它可以对元素进行排序，并且不允许重复元素存在,通过传递 Collections.reverseOrder() 给 TreeSet 的构造函数，会创建一个按照自然顺序的逆序排序的 TreeSet 对象，即元素将按照 ASCII 码值从大到小的顺序排序。
for (char c : s.toCharArray()) {
set.add(c);
}
StringBuilder result = new StringBuilder();
for (char c : set) {
result.append(c);
}
return result.toString();
}
public static void main(String[] args) {
String s = sc.nextLine();
String sortedUniqueChars = sortUniqueChars(s);
System.out.println(sortedUniqueChars);
}
}
//方法四 HashSet去重，对ArraysList排序
import java.util.*;
public class CardSorting {
public static String sortUniqueChars(String s) {
HashSet<Character> set = new HashSet<>();
// 将字符添加到 HashSet 去除重复
for (char c : s.toCharArray()) {
set.add(c);
}
// 将 HashSet 转换成 ArrayList
ArrayList<Character> list = new ArrayList<>(set);
// 对 ArrayList 中的元素进行排序
Collections.sort(list, Collections.reverseOrder());//Arrays.sort() 方法用于对数组进行排序，而不是用于对集合（如 ArrayList）进行排序。因此，不能直接使用 Arrays.sort() 来对 ArrayList 进行排序。
// 构建最终的字符串
StringBuilder result = new StringBuilder();
for (char c : list) {
result.append(c);
}
return result.toString();
}
public static void main(String[] args) {
String s = sc.nextLine();
String sortedUniqueChars = sortUniqueChars(s);
System.out.println(sortedUniqueChars);
}
}5.4 字符串编码问题
小明发明了一种给由全大写字母组成的字符串编码的方法。
对于每一个大写字母，小明将它转换成它在 26 个英文字母中序号，即 A → 1, B → 2, … Z →26。
这样一个字符串就能被转化成一个数字序列：比如 ABCXYZ → 123242526。
现在给定一个转换后的数字序列，小明想还原出原本的字符串。
当然这样的还原有可能存在多个符合条件的字符串。
小明希望找出其中字典序最大的字符串。
输入格式：
一个数字序列。
输出格式:
一个只包含大写字母的字符串，代表答案。
样例输入:
123242526
样例输出：
LCXYZ
评测用例规模与约定：
对于 20% 的评测用例，输入的长度不超过 20。
对于所有评测用例，输入的长度不超过 200000。public class Solution {
public static char[] arr = {
'0',
'A', 'B', 'C', 'D', 'E', 'F', 'G',
'H', 'I', 'J', 'K', 'L', 'M', 'N',
'O', 'P', 'Q', 'R', 'S', 'T', 'U',
'V', 'W', 'X', 'Y', 'Z'
};
public static void main(String[] args) {
String str = new Scanner(System.in).nextLine();
StringBuilder res = new StringBuilder();
for (int i = 0; i < str.length(); i++) {
if (i + 1 < str.length()) {
int x = (str.charAt(i) - '0') * 10 + (str.charAt(i + 1) - '0');
//char charAt(int index)返回指定索引处的 char 值。
if (x <= 26) {
res.append(arr[x]);//
i++;
} else {
res.append(arr[str.charAt(i) - '0']);
}
} else {
res.append(arr[str.charAt(i) - '0']);
}
}
System.out.println(res);
}
}5.5 重复字符串问题
题目描述
如果一个字符串 S 恰好可以由某个字符串重复 K 次得到，我们就称 S 是 K 次重复字符串。例如 abcabcabc 可以看作是 abc 重复 3 次得到，所以 abcabcabc 是 3 次重复字符串。
同理 aaaaaa 既是 2 次重复字符串、又是 3 次重复字符串和 6次重复字符串。
现在给定一个字符串 S，请你计算最少要修改其中几个字符，可以使 S 变为一个 K 次字符串？
输入格式：
输入第一行包含一个整数 K。
第二行包含一个只含小写字母的字符串 S。
其中，1 ≤ K ≤ 10^5, 1 ≤ |S| ≤ 10^5。其中∣S∣ 表示 S 的 长度。
输出格式：
输出一个整数代表答案。如果 S 无法修改成 K 次重复字符串，输出 −1。
样例输入：
2
aabbaa思路:
1、如果字符串长度不能等分，直接返回false;
2、将字符串等分后，遍历每个子字符串：将所有子字符串中从第一位字符开始对应位置上出现次数最多的字符求出来，让后将其它对应位置上的字符修改成该出现次数最多的字符。
例如（K=4，字符串S：abbabccbaaaa，将字符串等分成abb abc cba aaa，将各个字串对齐
abb
abc
cba
aaa
第一字符位置：a出现3次，c出现1次，c修改为a；
第二个字符位置：b出现3次，a出现1次，a修改为b
第三个字符位置：b出现1次，c出现1次，a出现2次，将b，c修改为a；最终结果是：
aba aba aba aba，共修改4次；
）
import java.util.Arrays;
import java.util.Scanner;
public class Main {
static int[] cnt=new int[26];
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int k=sc.nextInt();
char[] s = sc.next().toCharArray();
int n=s.length;
if (n%k!=0){
System.out.println(-1);
return;
}
int ans=0;
int t=n/k;
//将字符串等分
for (int i=0;i<t;i++){
Arrays.fill(cnt,0);
for (int j=i;j<n;j+=t){
cnt[s[j]-'a']++;
}
int max=0;
for (int j=0;j<26;j++){
max=Math.max(max,cnt[j]);
}
ans+=k-max;
}
System.out.println(ans);
}
}5.6 不同子串
一个字符串的非空子串是指字符串中长度至少为1的连续的一段字符组成的串。例如，字符串aaab有非空子串a，b，aa，ab，aaa，aab，aaab，一共7个。 注意在计算时，只算本质不同的串的个数。
请问，字符串0100110001010001有多少个不同的非空子串？【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。import java.util.*;
/*
第十届第二题：不同字串
*/
public class 不同字串{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.nextLine();
//0100110001010001
Set set = new HashSet(); //HashSet是一个不允许有重复元素的集合。
int n = 1;
while (n <= s.length()){
for (int i = n;i <= s.length();i++){
String s1 = s.substring(i-n, i);
set.add(s1);
}
n++;
}
System.out.println(set.size());
}
}5.双指针法
双指针法理论基础
双指针法（快慢指针法）： 通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。
定义快慢指针
快指针：寻找新数组的元素 ，新数组就是不含有目标元素的数组
慢指针：指向更新 新数组下标的位置
删除过程如下：
代码随想录题目
自己遇到的题目
6.栈与队列
栈与队列理论基础
代码随想录题目
6.1 有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1:
输入: "()"
输出: true
示例 2:
输入: "()[]{}"
输出: true
示例 3:
输入: "(]"
输出: false
示例 4:
输入: "([)]"
输出: false
示例 5:
输入: "{[]}"
输出: trueclass Solution {
public boolean isValid(String s) {
Deque<Character> deque = new LinkedList<>();
char ch;
for (int i = 0; i < s.length(); i++) {
ch = s.charAt(i);
//碰到左括号，就把相应的右括号入栈
if (ch == '(') {
deque.push(')');
}else if (ch == '{') {
deque.push('}');
}else if (ch == '[') {
deque.push(']');
} else if (deque.isEmpty() || deque.peek() != ch) {
return false;
}else {//如果是右括号判断是否和栈顶元素匹配
deque.pop();
}
}
//最后判断栈中元素是否匹配
return deque.isEmpty();
}
//在匹配左括号的时候，右括号先入栈，就只需要比较当前元素和栈顶相不相等就可以了，比左括号先入栈代码实现要简单的多了6.2 删除字符串中的所有相邻重复项
给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
在 S 上反复执行重复项删除操作，直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
示例：
输入："abbaca"
输出："ca"
解释：例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。
提示：
1 <= S.length <= 20000
S 仅由小写英文字母组成。class Solution {
public String removeDuplicates(String S) {
//ArrayDeque会比LinkedList在除了删除元素这一点外会快一点
//参考：https://stackoverflow.com/questions/6163166/why-is-arraydeque-better-than-linkedlist
ArrayDeque<Character> deque = new ArrayDeque<>();
char ch;
for (int i = 0; i < S.length(); i++) {
ch = S.charAt(i);
if (deque.isEmpty() || deque.peek() != ch) {
deque.push(ch);
} else {
deque.pop();
}
}
String str = "";
//剩余的元素即为不重复的元素
while (!deque.isEmpty()) {
str = deque.pop() + str;
}
return str;
}
}
//拿字符串直接作为栈，省去了栈还要转为字符串的操作。
class Solution {
public String removeDuplicates(String s) {
// 将 res 当做栈
// 也可以用 StringBuilder 来修改字符串，速度更快
// StringBuilder res = new StringBuilder();
StringBuffer res = new StringBuffer();
// top为 res 的长度
int top = -1;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
// 当 top > 0,即栈中有字符时，当前字符如果和栈中字符相等，弹出栈顶字符，同时 top--
if (top >= 0 && res.charAt(top) == c) {
res.deleteCharAt(top);
top--;
// 否则，将该字符 入栈，同时top++
} else {
res.append(c);
top++;
}
}
return res.toString();
}
}
//双指针法
class Solution {
public String removeDuplicates(String s) {
char[] ch = s.toCharArray();
int fast = 0;
int slow = 0;
while(fast < s.length()){
// 直接用fast指针覆盖slow指针的值
ch[slow] = ch[fast];
// 遇到前后相同值的，就跳过，即slow指针后退一步，下次循环就可以直接被覆盖掉了
if(slow > 0 && ch[slow] == ch[slow - 1]){
slow--;
}else{
slow++;
}
fast++;
}
return new String(ch,0,slow);
}
}6.3 逆波兰表达式求值
根据 逆波兰表示法，求表达式的值。
有效的运算符包括 + , - , * , / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
说明：
整数除法只保留整数部分。 给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
示例 1：
输入: ["2", "1", "+", "3", " * "]
输出: 9
解释: 该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
示例 2：
输入: ["4", "13", "5", "/", "+"]
输出: 6
解释: 该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6
示例 3：
输入: ["10", "6", "9", "3", "+", "-11", " * ", "/", " * ", "17", "+", "5", "+"]
输出: 22
解释:该算式转化为常见的中缀算术表达式为：
((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22
逆波兰表达式：是一种后缀表达式，所谓后缀就是指运算符写在后面。
平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。
逆波兰表达式主要有以下两个优点：
去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
适合用栈操作运算：遇到数字则入栈；遇到运算符则取出栈顶两个数字进行计算，并将结果压入栈中class Solution {
public int evalRPN(String[] tokens) {
Deque<Integer> stack = new LinkedList();
for (String s : tokens) {
if ("+".equals(s)) { // leetcode 内置jdk的问题，不能使用==判断字符串是否相等
stack.push(stack.pop() + stack.pop()); // 注意 - 和/ 需要特殊处理
} else if ("-".equals(s)) {
stack.push(-stack.pop() + stack.pop());
} else if ("*".equals(s)) {
stack.push(stack.pop() * stack.pop());
} else if ("/".equals(s)) {
int temp1 = stack.pop();
int temp2 = stack.pop();
stack.push(temp2 / temp1);
} else {
stack.push(Integer.valueOf(s));
}
}
return stack.pop();
}
}自己遇到的题目
7.二叉树
二叉树理论基础
代码随想录题目
自己遇到的题目
8.回溯算法(递归)
回溯理论基础
题目分类
什么是回溯法
回溯法也可以叫做回溯搜索法，它是一种搜索的方式。
在二叉树系列中，我们已经不止一次，提到了回溯，例如二叉树：以为使用了递归，其实还隐藏着回溯 (opens new window)。
回溯是递归的副产品，只要有递归就会有回溯。
所以以下讲解中，回溯函数也就是递归函数，指的都是一个函数。
回溯法的效率
回溯法的性能如何呢，这里要和大家说清楚了，虽然回溯法很难，很不好理解，但是回溯法并不是什么高效的算法。
因为回溯的本质是穷举，穷举所有可能，然后选出我们想要的答案，如果想让回溯法高效一些，可以加一些剪枝的操作，但也改不了回溯法就是穷举的本质。
那么既然回溯法并不高效为什么还要用它呢？
因为没得选，一些问题能暴力搜出来就不错了，撑死了再剪枝一下，还没有更高效的解法。
此时大家应该好奇了，都什么问题，这么牛逼，只能暴力搜索。
回溯法解决的问题
回溯法，一般可以解决如下几种问题：
组合问题：N个数里面按一定规则找出k个数的集合
切割问题：一个字符串按一定规则有几种切割方式
子集问题：一个N个数的集合里有多少符合条件的子集
排列问题：N个数按一定规则全排列，有几种排列方式
棋盘问题：N皇后，解数独等等
相信大家看着这些之后会发现，每个问题，都不简单！
另外，会有一些同学可能分不清什么是组合，什么是排列？
组合是不强调元素顺序的，排列是强调元素顺序。
例如：{1, 2} 和 {2, 1} 在组合上，就是一个集合，因为不强调顺序，而要是排列的话，{1, 2} 和 {2, 1} 就是两个集合了。
记住组合无序，排列有序，就可以了。
如何理解回溯法
回溯法解决的问题都可以抽象为树形结构，是的，我指的是所有回溯法的问题都可以抽象为树形结构！
因为回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度，都构成的树的深度。
递归就要有终止条件，所以必然是一棵高度有限的树（N叉树）。
这块可能初学者还不太理解，后面的回溯算法解决的所有题目中，我都会强调这一点并画图举相应的例子，现在有一个印象就行。
回溯法模板
这里给出Carl总结的回溯算法模板。
在讲二叉树的递归 (opens new window)中我们说了递归三部曲，这里我再给大家列出回溯三部曲。
回溯函数模板返回值以及参数
在回溯算法中，我的习惯是函数起名字为backtracking，这个起名大家随意。
回溯算法中函数返回值一般为void。
再来看一下参数，因为回溯算法需要的参数可不像二叉树递归的时候那么容易一次性确定下来，所以一般是先写逻辑，然后需要什么参数，就填什么参数。
但后面的回溯题目的讲解中，为了方便大家理解，我在一开始就帮大家把参数确定下来。
回溯函数伪代码如下：
void backtracking(参数)1
回溯函数终止条件
既然是树形结构，那么我们在讲解二叉树的递归 (opens new window)的时候，就知道遍历树形结构一定要有终止条件。
所以回溯也有要终止条件。
什么时候达到了终止条件，树中就可以看出，一般来说搜到叶子节点了，也就找到了满足条件的一条答案，把这个答案存放起来，并结束本层递归。
所以回溯函数终止条件伪代码如下：
if (终止条件) {
存放结果;
return;
}回溯搜索的遍历过程
在上面我们提到了，回溯法一般是在集合中递归搜索，集合的大小构成了树的宽度，递归的深度构成的树的深度。
如图：
注意图中，我特意举例集合大小和孩子的数量是相等的！
回溯函数遍历过程伪代码如下：
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
处理节点;
backtracking(路径，选择列表); // 递归
回溯，撤销处理结果
}for循环就是遍历集合区间，可以理解一个节点有多少个孩子，这个for循环就执行多少次。
backtracking这里自己调用自己，实现递归。
大家可以从图中看出for循环可以理解是横向遍历，backtracking（递归）就是纵向遍历，这样就把这棵树全遍历完了，一般来说，搜索叶子节点就是找的其中一个结果了。
分析完过程，回溯算法模板框架如下：
void backtracking(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
处理节点;
backtracking(路径，选择列表); // 递归
回溯，撤销处理结果
}
}这份模板很重要，后面做回溯法的题目都靠它了！
如果从来没有学过回溯算法的录友们，看到这里会有点懵，后面开始讲解具体题目的时候就会好一些了，已经做过回溯法题目的录友，看到这里应该会感同身受了。
代码随想录题目
https://www.programmercarl.com/0077.%E7%BB%84%E5%90%88.html
8.1 组合
给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。
示例: 输入: n = 4, k = 2 输出: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]class Solution {
List<List<Integer>> result = new ArrayList<>();//用ArrayList实现List
LinkedList<Integer> path = new LinkedList<>();
public List<List<Integer>> combine(int n, int k) {
backtracking(n,k,1);
return result;//注意要返回最终结果
}
public void backtracking(int n,int k,int startIndex){
if(path.size()==k){
result.add(new ArrayList<>(path));//path
return;
}
for(int i = startIndex;i<=n-(k-path.size()+1);i++){//int i = startIndex i<=n-(k-path.size()+1)
path.add(i);//i
backtracking(n,k,i+1);//i+1
path.removeLast();//removeLast
}
}
}8.2 组合总和3
找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
说明：
所有数字都是正整数。
解集不能包含重复的组合。
示例 1: 输入: k = 3, n = 7 输出: [[1,2,4]]
示例 2: 输入: k = 3, n = 9 输出: [[1,2,6], [1,3,5], [2,3,4]]class Solution {
List<List<Integer>> result = new ArrayList<>();
LinkedList<Integer> path = new LinkedList<>();
public List<List<Integer>> combinationSum3(int k, int n) {
backTracking(n, k, 1, 0);
return result;
}
private void backTracking(int targetSum, int k, int startIndex, int sum) {
// 减枝
if (sum > targetSum) {
return;
}
if (path.size() == k) {
if (sum == targetSum) result.add(new ArrayList<>(path));
return;
}
// 减枝 9 - (k - path.size()) + 1
for (int i = startIndex; i <= 9 - (k - path.size()) + 1; i++) {
path.add(i);
sum += i;
backTracking(targetSum, k, i + 1, sum);
//回溯
path.removeLast();
//回溯
sum -= i;
}
}
}
// 上面剪枝 i <= 9 - (k - path.size()) + 1; 如果还是不清楚
// 也可以改为 if (path.size() > k) return; 执行效率上是一样的
class Solution {
LinkedList<Integer> path = new LinkedList<>();
List<List<Integer>> ans = new ArrayList<>();
public List<List<Integer>> combinationSum3(int k, int n) {
build(k, n, 1, 0);
return ans;
}
private void build(int k, int n, int startIndex, int sum) {
if (sum > n) return;
if (path.size() > k) return;
if (sum == n && path.size() == k) {
ans.add(new ArrayList<>(path));
return;
}
for(int i = startIndex; i <= 9; i++) {
path.add(i);
sum += i;
build(k, n, i + 1, sum);
sum -= i;
path.removeLast();
}
}
}8.3 电话号码的字母组合
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例:
输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
说明：尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序
class Solution {
//设置全局列表存储最后的结果
List<String> list = new ArrayList<>();
public List<String> letterCombinations(String digits) {
if (digits == null || digits.length() == 0) {
return list;
}
//初始对应所有的数字，为了直接对应2-9，新增了两个无效的字符串""
String[] numString = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
//迭代处理
backTracking(digits, numString, 0);
return list;
}
//每次迭代获取一个字符串，所以会设计大量的字符串拼接，所以这里选择更为高效的 StringBuild
StringBuilder temp = new StringBuilder();
//比如digits如果为"23",num 为0，则str表示2对应的 abc
public void backTracking(String digits, String[] numString, int num) {
//遍历全部一次记录一次得到的字符串
if (num == digits.length()) {
list.add(temp.toString());
return;
}
//str 表示当前num对应的字符串
String str = numString[digits.charAt(num) - '0'];
for (int i = 0; i < str.length(); i++) {
temp.append(str.charAt(i));
//c
backTracking(digits, numString, num + 1);
//剔除末尾的继续尝试
temp.deleteCharAt(temp.length() - 1);
}
}
}8.4 组合总和
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明：
所有数字（包括 target）都是正整数。
解集不能包含重复的组合。
示例 1：
输入：candidates = [2,3,6,7], target = 7,
所求解集为： [ [7], [2,2,3] ]
示例 2：
输入：candidates = [2,3,5], target = 8,
所求解集为： [ [2,2,2,2], [2,3,3], [3,5] ]// 剪枝优化
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> res = new ArrayList<>();
Arrays.sort(candidates); // 先进行排序
backtracking(res, new ArrayList<>(), candidates, target, 0, 0);
return res;
}
public void backtracking(List<List<Integer>> res, List<Integer> path, int[] candidates, int target, int sum, int idx) {
// 找到了数字和为 target 的组合
if (sum == target) {
res.add(new ArrayList<>(path));
return;
}
for (int i = idx; i < candidates.length; i++) {
// 如果 sum + candidates[i] > target 就终止遍历
if (sum + candidates[i] > target) break;
path.add(candidates[i]);
backtracking(res, path, candidates, target, sum + candidates[i], i);
path.remove(path.size() - 1); // 回溯，移除路径 path 最后一个元素
}
}
}8.5 组合总和2
给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
说明： 所有数字（包括目标数）都是正整数。解集不能包含重复的组合。
示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
示例 2:
输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
[1,2,2],
[5]
]class Solution {
LinkedList<Integer> path = new LinkedList<>();
List<List<Integer>> ans = new ArrayList<>();
boolean[] used;
int sum = 0;
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
used = new boolean[candidates.length];
// 加标志数组，用来辅助判断同层节点是否已经遍历
Arrays.fill(used, false);
// 为了将重复的数字都放到一起，所以先进行排序
Arrays.sort(candidates);
backTracking(candidates, target, 0);
return ans;
}
private void backTracking(int[] candidates, int target, int startIndex) {
if (sum == target) {
ans.add(new ArrayList(path));
}
for (int i = startIndex; i < candidates.length; i++) {
if (sum + candidates[i] > target) {
break;
}
// 出现重复节点，同层的第一个节点已经被访问过，所以直接跳过
if (i > 0 && candidates[i] == candidates[i - 1] && !used[i - 1]) {
continue;
}
used[i] = true;
sum += candidates[i];
path.add(candidates[i]);
// 每个节点仅能选择一次，所以从下一位开始
backTracking(candidates, target, i + 1);
used[i] = false;
sum -= candidates[i];
path.removeLast();
}
}
}
不使用标记数组
class Solution {
List<List<Integer>> res = new ArrayList<>();
LinkedList<Integer> path = new LinkedList<>();
int sum = 0;
public List<List<Integer>> combinationSum2( int[] candidates, int target ) {
//为了将重复的数字都放到一起，所以先进行排序
Arrays.sort( candidates );
backTracking( candidates, target, 0 );
return res;
}
private void backTracking( int[] candidates, int target, int start ) {
if ( sum == target ) {
res.add( new ArrayList<>( path ) );
return;
}
for ( int i = start; i < candidates.length && sum + candidates[i] <= target; i++ ) {
//正确剔除重复解的办法
//跳过同一树层使用过的元素
if ( i > start && candidates[i] == candidates[i - 1] ) {
continue;
}
sum += candidates[i];
path.add( candidates[i] );
// i+1 代表当前组内元素只选取一次
backTracking( candidates, target, i + 1 );
int temp = path.getLast();
sum -= temp;
path.removeLast();
}
}
}8.6 分割回文串
给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
返回 s 所有可能的分割方案。
示例: 输入: "aab" 输出: [ ["aa","b"], ["a","a","b"] ]class Solution {
List<List<String>> lists = new ArrayList<>();
Deque<String> deque = new LinkedList<>();
public List<List<String>> partition(String s) {
backTracking(s, 0);
return lists;
}
private void backTracking(String s, int startIndex) {
//如果起始位置大于s的大小，说明找到了一组分割方案
if (startIndex >= s.length()) {
lists.add(new ArrayList(deque));
return;
}
for (int i = startIndex; i < s.length(); i++) {
//如果是回文子串，则记录
if (isPalindrome(s, startIndex, i)) {
String str = s.substring(startIndex, i + 1);
deque.addLast(str);
} else {
continue;
}
//起始位置后移，保证不重复
backTracking(s, i + 1);
deque.removeLast();
}
}
//判断是否是回文串
private boolean isPalindrome(String s, int startIndex, int end) {
for (int i = startIndex, j = end; i < j; i++, j--) {
if (s.charAt(i) != s.charAt(j)) {
return false;
}
}
return true;
}
}8.7 子集问题
给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例: 输入: nums = [1,2,3] 输出: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]class Solution {
List<List<Integer>> result = new ArrayList<>();// 存放符合条件结果的集合
LinkedList<Integer> path = new LinkedList<>();// 用来存放符合条件结果
public List<List<Integer>> subsets(int[] nums) {
subsetsHelper(nums, 0);
return result;
}
private void subsetsHelper(int[] nums, int startIndex){
result.add(new ArrayList<>(path));//「遍历这个树的时候，把所有节点都记录下来，就是要求的子集集合」。
if (startIndex >= nums.length){ //终止条件可不加
return;
}
for (int i = startIndex; i < nums.length; i++){
path.add(nums[i]);
subsetsHelper(nums, i + 1);
path.removeLast();
}
}
}8.8 递增子序列
给定一个整型数组, 你的任务是找到所有该数组的递增子序列，递增子序列的长度至少是2。
示例:
输入: [4, 6, 7, 7]
输出: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]
说明:
给定数组的长度不会超过15。
数组中的整数范围是 [-100,100]。
给定数组中可能包含重复数字，相等的数字应该被视为递增的一种情况。class Solution {
List<List<Integer>> result = new ArrayList<>();
List<Integer> path = new ArrayList<>();
public List<List<Integer>> findSubsequences(int[] nums) {
backTracking(nums, 0);
return result;
}
private void backTracking(int[] nums, int startIndex){
if(path.size() >= 2)
result.add(new ArrayList<>(path));
HashSet<Integer> hs = new HashSet<>();
for(int i = startIndex; i < nums.length; i++){
if(!path.isEmpty() && path.get(path.size() -1 ) > nums[i] || hs.contains(nums[i]))
continue;
hs.add(nums[i]);
path.add(nums[i]);
backTracking(nums, i + 1);
path.remove(path.size() - 1);
}
}
}8.9 全排列
给定一个 没有重复 数字的序列，返回其所有可能的全排列。
示例:
输入: [1,2,3]
输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]class Solution {
List<List<Integer>> result = new ArrayList<>();// 存放符合条件结果的集合
LinkedList<Integer> path = new LinkedList<>();// 用来存放符合条件结果
boolean[] used;
public List<List<Integer>> permute(int[] nums) {
if (nums.length == 0){
return result;
}
used = new boolean[nums.length];
permuteHelper(nums);
return result;
}
private void permuteHelper(int[] nums){
if (path.size() == nums.length){
result.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < nums.length; i++){
if (used[i]){
continue;
}
used[i] = true;
path.add(nums[i]);
permuteHelper(nums);
path.removeLast();
used[i] = false;
}
}
}自己遇到的题目
9.贪心算法
贪心理论基础
题目分类大纲如下：
什么是贪心
贪心的本质是选择每一阶段的局部最优，从而达到全局最优。
这么说有点抽象，来举一个例子：
例如，有一堆钞票，你可以拿走十张，如果想达到最大的金额，你要怎么拿？
指定每次拿最大的，最终结果就是拿走最大数额的钱。
每次拿最大的就是局部最优，最后拿走最大数额的钱就是推出全局最优。
再举一个例子如果是 有一堆盒子，你有一个背包体积为n，如何把背包尽可能装满，如果还每次选最大的盒子，就不行了。这时候就需要动态规划。动态规划的问题在下一个系列会详细讲解。
贪心的套路（什么时候用贪心）
很多同学做贪心的题目的时候，想不出来是贪心，想知道有没有什么套路可以一看就看出来是贪心。
说实话贪心算法并没有固定的套路。
所以唯一的难点就是如何通过局部最优，推出整体最优。
那么如何能看出局部最优是否能推出整体最优呢？有没有什么固定策略或者套路呢？
不好意思，也没有！ 靠自己手动模拟，如果模拟可行，就可以试一试贪心策略，如果不可行，可能需要动态规划。
有同学问了如何验证可不可以用贪心算法呢？
最好用的策略就是举反例，如果想不到反例，那么就试一试贪心吧。
可有有同学认为手动模拟，举例子得出的结论不靠谱，想要严格的数学证明。
一般数学证明有如下两种方法：
数学归纳法
反证法
看教课书上讲解贪心可以是一堆公式，估计大家连看都不想看，所以数学证明就不在我要讲解的范围内了，大家感兴趣可以自行查找资料。
面试中基本不会让面试者现场证明贪心的合理性，代码写出来跑过测试用例即可，或者自己能自圆其说理由就行了。
举一个不太恰当的例子：我要用一下1+1 = 2，但我要先证明1+1 为什么等于2。严谨是严谨了，但没必要。
虽然这个例子很极端，但可以表达这么个意思：刷题或者面试的时候，手动模拟一下感觉可以局部最优推出整体最优，而且想不到反例，那么就试一试贪心。
例如刚刚举的拿钞票的例子，就是模拟一下每次拿做大的，最后就能拿到最多的钱，这还要数学证明的话，其实就不在算法面试的范围内了，可以看看专业的数学书籍！
所以这也是为什么很多同学通过（accept）了贪心的题目，但都不知道自己用了贪心算法，因为贪心有时候就是常识性的推导，所以会认为本应该就这么做！
那么刷题的时候什么时候真的需要数学推导呢？
例如这道题目：链表：环找到了，那入口呢？ (opens new window)，这道题不用数学推导一下，就找不出环的起始位置，想试一下就不知道怎么试，这种题目确实需要数学简单推导一下。
贪心一般解题步骤
贪心算法一般分为如下四步：
将问题分解为若干个子问题
找出适合的贪心策略
求解每一个子问题的最优解
将局部最优解堆叠成全局最优解
这个四步其实过于理论化了，我们平时在做贪心类的题目 很难去按照这四步去思考，真是有点“鸡肋”。
做题的时候，只要想清楚 局部最优 是什么，如果推导出全局最优，其实就够了。
总结
本篇给出了什么是贪心以及大家关心的贪心算法固定套路。
不好意思了，贪心没有套路，说白了就是常识性推导加上举反例。
最后给出贪心的一般解题步骤，大家可以发现这个解题步骤也是比较抽象的，不像是二叉树，回溯算法，给出了那么具体的解题套路和模板。
代码随想录题目
https://www.programmercarl.com/0455.%E5%88%86%E5%8F%91%E9%A5%BC%E5%B9%B2.html
9.1 分发饼干
假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。
对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。
示例 1:
输入: g = [1,2,3], s = [1,1]
输出: 1 解释:你有三个孩子和两块小饼干，3 个孩子的胃口值分别是：1,2,3。虽然你有两块小饼干，由于他们的尺寸都是 1，你只能让胃口值是 1 的孩子满足。所以你应该输出 1。
示例 2:
输入: g = [1,2], s = [1,2,3]
输出: 2
解释:你有两个孩子和三块小饼干，2 个孩子的胃口值分别是 1,2。你拥有的饼干数量和尺寸都足以让所有孩子满足。所以你应该输出 2.
提示：
1 <= g.length <= 3 * 10^4
0 <= s.length <= 3 * 10^4
1 <= g[i], s[j] <= 2^31 - 1// 贪心暴力
class Solution {
public int findContentChildren(int[] g, int[] s) {
Arrays.sort(g);
Arrays.sort(s);
int res=0;
for(int i=g.length-1;i>=0;i--){
for(int j=s.length-1;j>=0;j--){
if(s[j]==0)
continue;
if(s[j]>=g[i]){
s[j]=0;
res++;
break;
}
}
}
return res;
}
}
//贪心优化
class Solution {
// 思路2：优先考虑胃口，先喂饱大胃口
public int findContentChildren(int[] g, int[] s) {
Arrays.sort(g);
Arrays.sort(s);
int count = 0;
int start = s.length - 1;
// 遍历胃口
for (int index = g.length - 1; index >= 0; index--) {//必须先遍历胃口
if(start >= 0 && g[index] <= s[start]) {
start--;
count++;
}
}
return count;
}
}9.2 摆动序列
如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的话）可能是正数或负数。少于两个元素的序列也是摆动序列。
例如， [1,7,4,9,2,5] 是一个摆动序列，因为差值 (6,-3,5,-7,3) 是正负交替出现的。相反, [1,4,7,2,5] 和 [1,7,4,5,5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。
给定一个整数序列，返回作为摆动序列的最长子序列的长度。 通过从原始序列中删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。
示例 1:
输入: [1,7,4,9,2,5]
输出: 6
解释: 整个序列均为摆动序列。
示例 2:
输入: [1,17,5,10,13,15,10,5,16,8]
输出: 7
解释: 这个序列包含几个长度为 7 摆动序列，其中一个可为[1,17,10,13,10,16,8]。
示例 3:
输入: [1,2,3,4,5,6,7,8,9]
输出: 2//贪心
class Solution {
public static int wiggleMaxLength(int[] nums) {
if(nums.length<=1)return nums.length;
//当前差值
int pre = 0;
//上一个差值
int cur = 0;
int result =1;
for(int i=0;i<nums.length-1;i++) {
cur=nums[i+1]-nums[i];
//如果当前差值和上一个差值为一正一负
//等于0的情况表示初始时的preDiff
if((pre<=0&&cur>0)||(pre>=0&&cur<0)) {
result++;
pre=cur;
}
}
return result;
}
}
// DP
class Solution {
public int wiggleMaxLength(int[] nums) {
// 0 i 作为波峰的最大长度
// 1 i 作为波谷的最大长度
int dp[][] = new int[nums.length][2];
dp[0][0] = dp[0][1] = 1;
for (int i = 1; i < nums.length; i++){
//i 自己可以成为波峰或者波谷
dp[i][0] = dp[i][1] = 1;
for (int j = 0; j < i; j++){
if (nums[j] > nums[i]){
// i 是波谷
dp[i][1] = Math.max(dp[i][1], dp[j][0] + 1);
}
if (nums[j] < nums[i]){
// i 是波峰
dp[i][0] = Math.max(dp[i][0], dp[j][1] + 1);
}
}
}
return Math.max(dp[nums.length - 1][0], dp[nums.length - 1][1]);
}
}9.3 最大子序和
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6//暴力法
class Solution {
public static int maxSubArray(int[] nums) {
int max = Integer.MIN_VALUE;
for (int i = 0; i < nums.length; i++) {
int sum = 0;
for (int j = i; j < nums.length; j++) {
sum = sum + nums[j];
max = max>sum ? max: sum;
}
}
return max;
}
}
//贪心
class Solution {
public int maxSubArray(int[] nums) {
if (nums.length == 1){
return nums[0];
}
int sum = Integer.MIN_VALUE;
int count = 0;
for (int i = 0; i < nums.length; i++){
count += nums[i];
sum = Math.max(sum, count); // 取区间累计的最大值（相当于不断确定最大子序终止位置）
if (count <= 0){
count = 0; // 相当于重置最大子序起始位置，因为遇到负数一定是拉低总和
}
}
return sum;
}
}9.4 买卖股票的最佳时机 II
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4。随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
示例 2:
输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
示例 3:
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
提示：
1 <= prices.length <= 3 * 10 ^ 4
0 <= prices[i] <= 10 ^ 4// 贪心思路
class Solution {
public int maxProfit(int[] prices) {
int result = 0;
for (int i = 1; i < prices.length; i++) {
result += Math.max(prices[i] - prices[i - 1], 0);//只收集正利润
}
return result;
}
}9.5 跳跃游戏
给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个位置。
示例 1:
输入: [2,3,1,1,4]
输出: true
解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。
示例 2:
输入: [3,2,1,0,4]
输出: false
解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。//贪心
public static boolean canJump(int[] nums) {
int range =0;
if(nums.length==1)return true;
for(int i=0;i<=range;i++) {//在覆盖范围里遍历
range=Math.max(range, i+nums[i]);
if(range>=nums.length-1) return true;
}
return false;
}
9.6 跳跃游戏 II
给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
示例:
输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
说明: 假设你总是可以到达数组的最后一个位置// 版本一
class Solution {
public int jump(int[] nums) {
if (nums == null || nums.length == 0 || nums.length == 1) {
return 0;
}
//记录跳跃的次数
int count=0;
//当前的覆盖最大区域
int curDistance = 0;
//最大的覆盖区域
int maxDistance = 0;
for (int i = 0; i < nums.length; i++) {
//在可覆盖区域内更新最大的覆盖区域
maxDistance = Math.max(maxDistance,i+nums[i]);
//说明当前一步，再跳一步就到达了末尾
if (maxDistance>=nums.length-1){
count++;
break;
}
//走到当前覆盖的最大区域时，更新下一步可达的最大区域
if (i==curDistance){
curDistance = maxDistance;
count++;
}
}
return count;
}
}
// 版本二
class Solution {
public int jump(int[] nums) {
int result = 0;
// 当前覆盖的最远距离下标
int end = 0;
// 下一步覆盖的最远距离下标
int temp = 0;
for (int i = 0; i <= end && end < nums.length - 1; ++i) {
temp = Math.max(temp, i + nums[i]);
// 可达位置的改变次数就是跳跃次数
if (i == end) {
end = temp;
result++;
}
}
return result;
}
}9.7 K次取反后最大化的数组和
给定一个整数数组 A，我们只能用以下方法修改该数组：我们选择某个索引 i 并将 A[i] 替换为 -A[i]，然后总共重复这个过程 K 次。（我们可以多次选择同一个索引 i。）
以这种方式修改数组后，返回数组可能的最大和。
示例 1：
输入：A = [4,2,3], K = 1
输出：5
解释：选择索引 (1,) ，然后 A 变为 [4,-2,3]。
示例 2：
输入：A = [3,-1,0,2], K = 3
输出：6
解释：选择索引 (1, 2, 2) ，然后 A 变为 [3,1,0,2]。
示例 3：
输入：A = [2,-3,-1,5,-4], K = 2
输出：13
解释：选择索引 (1, 4) ，然后 A 变为 [2,3,-1,5,4]。
提示：
1 <= A.length <= 10000
1 <= K <= 10000
-100 <= A[i] <= 100给定一个整数数组 A，我们只能用以下方法修改该数组：我们选择某个索引 i 并将 A[i] 替换为 -A[i]，然后总共重复这个过程 K 次。（我们可以多次选择同一个索引 i。）
以这种方式修改数组后，返回数组可能的最大和。
示例 1：
输入：A = [4,2,3], K = 1
输出：5
解释：选择索引 (1,) ，然后 A 变为 [4,-2,3]。
示例 2：
输入：A = [3,-1,0,2], K = 3
输出：6
解释：选择索引 (1, 2, 2) ，然后 A 变为 [3,1,0,2]。
示例 3：
输入：A = [2,-3,-1,5,-4], K = 2
输出：13
解释：选择索引 (1, 4) ，然后 A 变为 [2,3,-1,5,4]。
提示：
1 <= A.length <= 10000
1 <= K <= 10000
-100 <= A[i] <= 100//贪心1
class Solution {
public static int largestSumAfterKNegations(int[] nums1, int K) {
// 将数组按照绝对值大小从大到小排序，注意要按照绝对值的大小
Integer newNums[] = Arrays.stream(nums1).boxed().toArray(Integer[]::new);
Arrays.sort(newNums, (x, y) -> { return (Math.abs(y)) - (Math.abs(x)); });
int[] nums = Arrays.stream(newNums).mapToInt(Integer::valueOf).toArray();
int len = nums.length;
for (int i = 0; i < len; i++) {
// 从前向后遍历，遇到负数将其变为正数，同时K--
if (nums[i] < 0 && K > 0) {
nums[i] = -nums[i];
K--;
}
}
// 如果K还大于0，那么反复转变数值最小的元素，将K用完
if (K % 2 == 1)
nums[len - 1] = -nums[len - 1];
return Arrays.stream(nums).sum();
}
}
//贪心2
class Solution {
public int largestSumAfterKNegations(int[] nums, int K) {
// 将数组按照绝对值大小从大到小排序，注意要按照绝对值的大小
nums = IntStream.of(nums)
.boxed()
.sorted((o1, o2) -> Math.abs(o2) - Math.abs(o1))
.mapToInt(Integer::intValue).toArray();
int len = nums.length;
for (int i = 0; i < len; i++) {
//从前向后遍历，遇到负数将其变为正数，同时K--
if (nums[i] < 0 && K > 0) {
nums[i] = -nums[i];
K--;
}
}
// 如果K还大于0，那么反复转变数值最小的元素，将K用完
if (K % 2 == 1) nums[len - 1] = -nums[len - 1];
return Arrays.stream(nums).sum();
}
}9.8 加油站
在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。
如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。
说明:
如果题目有解，该答案即为唯一答案。
输入数组均为非空数组，且长度相同。
输入数组中的元素均为非负数。
示例 1: 输入:
gas = [1,2,3,4,5]
cost = [3,4,5,1,2]
输出: 3 解释:
从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油
开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油
开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油
开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油
开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。
因此，3 可为起始索引。
示例 2: 输入:
gas = [2,3,4]
cost = [3,4,3]
输出: -1
解释: 你不能从 0 号或 1 号加油站出发，因为没有足够的汽油可以让你行驶到下一个加油站。我们从 2 号加油站出发，可以获得 4 升汽油。 此时油箱有 = 0 + 4 = 4 升汽油。开往 0 号加油站，此时油箱有 4 - 3 + 2 = 3 升汽油。开往 1 号加油站，此时油箱有 3 - 3 + 3 = 3 升汽油。你无法返回 2 号加油站，因为返程需要消耗 4 升汽油，但是你的油箱只有 3 升汽油。因此，无论怎样，你都不可能绕环路行驶一周。// 解法1 暴力
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
for (int i = 0; i < cost.length; i++) {
int rest = gas[i] - cost[i]; // 记录剩余油量
int index = (i + 1) % cost.length;
while (rest > 0 && index != i) { // 模拟以i为起点行驶一圈（如果有rest==0，那么答案就不唯一了）
rest += gas[index] - cost[index];
index = (index + 1) % cost.length;
}
// 如果以i为起点跑一圈，剩余油量>=0，返回该起始位置
if (rest >= 0 && index == i) return i;
}
return -1;
}
}
// 解法2 贪心
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int curSum = 0;
int totalSum = 0;
int index = 0;
for (int i = 0; i < gas.length; i++) {
curSum += gas[i] - cost[i];
totalSum += gas[i] - cost[i];
if (curSum < 0) {
index = (i + 1) % gas.length ;
curSum = 0;
}
}
if (totalSum < 0) return -1;
return index;
}
}9.9 分发糖果
老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。
你需要按照以下要求，帮助老师给这些孩子分发糖果：
每个孩子至少分配到 1 个糖果。
相邻的孩子中，评分高的孩子必须获得更多的糖果。
那么这样下来，老师至少需要准备多少颗糖果呢？
示例 1:
输入: [1,0,2]
输出: 5
解释: 你可以分别给这三个孩子分发 2、1、2 颗糖果。
示例 2:
输入: [1,2,2]
输出: 4
解释: 你可以分别给这三个孩子分发 1、2、1 颗糖果。第三个孩子只得到 1 颗糖果，这已满足上述两个条件。class Solution {
/**
分两个阶段
1、起点下标1 从左往右，只要 右边 比 左边 大，右边的糖果=左边 + 1
2、起点下标 ratings.length - 2 从右往左， 只要左边 比 右边 大，此时 左边的糖果应该 取本身的糖果数（符合比它左边大） 和 右边糖果数 + 1 二者的最大值，这样才符合 它比它左边的大，也比它右边大
*/
public int candy(int[] ratings) {
int len = ratings.length;
int[] candyVec = new int[len];
candyVec[0] = 1;
for (int i = 1; i < len; i++) {
candyVec[i] = (ratings[i] > ratings[i - 1]) ? candyVec[i - 1] + 1 : 1;
}
for (int i = len - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1]) {
candyVec[i] = Math.max(candyVec[i], candyVec[i + 1] + 1);
}
}
int ans = 0;
for (int num : candyVec) {
ans += num;
}
return ans;
}
}9.10 柠檬水找零
在柠檬水摊上，每一杯柠檬水的售价为 5 美元。
顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。
每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。
注意，一开始你手头没有任何零钱。
如果你能给每位顾客正确找零，返回 true ，否则返回 false 。
示例 1：
输入：[5,5,5,10,20]
输出：true
解释：
前 3 位顾客那里，我们按顺序收取 3 张 5 美元的钞票。
第 4 位顾客那里，我们收取一张 10 美元的钞票，并返还 5 美元。
第 5 位顾客那里，我们找还一张 10 美元的钞票和一张 5 美元的钞票。
由于所有客户都得到了正确的找零，所以我们输出 true。
示例 2：
输入：[5,5,10]
输出：true
示例 3：
输入：[10,10]
输出：false
示例 4：
输入：[5,5,10,10,20]
输出：false
解释：
前 2 位顾客那里，我们按顺序收取 2 张 5 美元的钞票。
对于接下来的 2 位顾客，我们收取一张 10 美元的钞票，然后返还 5 美元。
对于最后一位顾客，我们无法退回 15 美元，因为我们现在只有两张 10 美元的钞票。
由于不是每位顾客都得到了正确的找零，所以答案是 false。
提示：
0 <= bills.length <= 10000
bills[i] 不是 5 就是 10 或是 20//方法1
class Solution {
public boolean lemonadeChange(int[] bills) {
int five = 0;
int ten = 0;
for (int i = 0; i < bills.length; i++) {
if (bills[i] == 5) {
five++;
} else if (bills[i] == 10) {
five--;
ten++;
} else if (bills[i] == 20) {
if (ten > 0) {
ten--;
five--;
} else {
five -= 3;
}
}
if (five < 0 || ten < 0) return false;
}
return true;
}
}
//方法二 自己写的
public static boolean lemonadeChange(int[] bills) {
int wu=0;
int shi=0;
int erShi=0;
for(int i=0;i<bills.length;i++) {
if(bills[i]==5) {
wu++;
}
if(bills[i]==10) {
if(wu>0) {
wu--;
shi++;
}else {
return false;
}
}
if(bills[i]==20) {
if(shi>0) {
shi--;
if(wu>0) {
wu--;
erShi++;
}else {
return false;
}
}else if(wu>=3){
wu=wu-3;
erShi++;
}else {
return false;
}
}
}
return true;
}9.11 根据身高重建队列
假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。
请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。
示例 1：
输入：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
输出：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
解释：
编号为 0 的人身高为 5 ，没有身高更高或者相同的人排在他前面。
编号为 1 的人身高为 7 ，没有身高更高或者相同的人排在他前面。
编号为 2 的人身高为 5 ，有 2 个身高更高或者相同的人排在他前面，即编号为 0 和 1 的人。
编号为 3 的人身高为 6 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
编号为 4 的人身高为 4 ，有 4 个身高更高或者相同的人排在他前面，即编号为 0、1、2、3 的人。
编号为 5 的人身高为 7 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新构造后的队列。
示例 2：
输入：people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]]
输出：[[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]
提示：
1 <= people.length <= 2000
0 <= hi <= 10^6
0 <= ki < people.length
题目数据确保队列可以被重建class Solution {
public int[][] reconstructQueue(int[][] people) {
// 身高从大到小排（身高相同k小的站前面）
//int[][] people不用是Integer类型的
Arrays.sort(people, (a, b) -> {
if (a[0] == b[0]) return a[1] - b[1]; // a - b 是升序排列，故在a[0] == b[0]的狀況下，會根據k值升序排列
return b[0] - a[0]; //b - a 是降序排列，在a[0] != b[0]，的狀況會根據h值降序排列
});
LinkedList<int[]> que = new LinkedList<>();
for (int[] p : people) {
que.add(p[1],p); //Linkedlist.add(index, value)，會將value插入到指定index裡。
}
return que.toArray(new int[people.length][]);
}
}9.12 用最少数量的箭引爆气球
在二维空间中有许多球形的气球。对于每个气球，提供的输入是水平方向上，气球直径的开始和结束坐标。由于它是水平的，所以纵坐标并不重要，因此只要知道开始和结束的横坐标就足够了。开始坐标总是小于结束坐标。
一支弓箭可以沿着 x 轴从不同点完全垂直地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足 xstart ≤ x ≤ xend，则该气球会被引爆。可以射出的弓箭的数量没有限制。 弓箭一旦被射出之后，可以无限地前进。我们想找到使得所有气球全部被引爆，所需的弓箭的最小数量。
给你一个数组 points ，其中 points [i] = [xstart,xend] ，返回引爆所有气球所必须射出的最小弓箭数。
示例 1：
输入：points = [[10,16],[2,8],[1,6],[7,12]]
输出：2
解释：对于该样例，x = 6 可以射爆 [2,8],[1,6] 两个气球，以及 x = 11 射爆另外两个气球
示例 2：
输入：points = [[1,2],[3,4],[5,6],[7,8]]
输出：4
示例 3：
输入：points = [[1,2],[2,3],[3,4],[4,5]]
输出：2
示例 4：
输入：points = [[1,2]]
输出：1
示例 5：
输入：points = [[2,3],[2,3]]
输出：1
提示：
0 <= points.length <= 10^4
points[i].length == 2
-2^31 <= xstart < xend <= 2^31 - 1/**
* 时间复杂度 : O(NlogN) 排序需要 O(NlogN) 的复杂度
* 空间复杂度 : O(logN) java所使用的内置函数用的是快速排序需要 logN 的空间
*/
class Solution {
public int findMinArrowShots(int[][] points) {
// 根据气球直径的开始坐标从小到大排序
// 使用Integer内置比较方法，不会溢出
Arrays.sort(points, (a, b) -> Integer.compare(a[0], b[0]));
int count = 1; // points 不为空至少需要一支箭
for (int i = 1; i < points.length; i++) {
if (points[i][0] > points[i - 1][1]) { // 气球i和气球i-1不挨着，注意这里不是>=
count++; // 需要一支箭
} else { // 气球i和气球i-1挨着
points[i][1] = Math.min(points[i][1], points[i - 1][1]); // 更新重叠气球最小右边界
}
}
return count;
}
}9.13 无重叠区间
给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。
注意: 可以认为区间的终点总是大于它的起点。 区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。
示例 1:
输入: [ [1,2], [2,3], [3,4], [1,3] ]
输出: 1
解释: 移除 [1,3] 后，剩下的区间没有重叠。
示例 2:
输入: [ [1,2], [1,2], [1,2] ]
输出: 2
解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。
示例 3:
输入: [ [1,2], [2,3] ]
输出: 0
解释: 你不需要移除任何区间，因为它们已经是无重叠的了。class Solution {
public int eraseOverlapIntervals(int[][] intervals) {
// 根据气球直径的开始坐标从小到大排序
// 使用Integer内置比较方法，不会溢出
Arrays.sort(intervals, (a,b)-> {
return Integer.compare(a[0],b[0]);
});
// points 不为空至少需要一支箭
int count = 1;
for(int i = 1;i < intervals.length;i++){
if(intervals[i][0] < intervals[i-1][1]){
intervals[i][1] = Math.min(intervals[i - 1][1], intervals[i][1]);
continue;
}else{
count++;
}
}
return intervals.length - count;//总个数减去重叠区间的个数就是需要移除的个数
}
}class Solution {
public List<Integer> partitionLabels(String S) {
List<Integer> list = new LinkedList<>();
int[] edge = new int[26];
char[] chars = S.toCharArray();
for (int i = 0; i < chars.length; i++) {
edge[chars[i] - 'a'] = i;
}
int idx = 0;
int last = -1;
for (int i = 0; i < chars.length; i++) {
idx = Math.max(idx,edge[chars[i] - 'a']);
if (i == idx) {
list.add(i - last);
last = i;
}
}
return list;
}
}
class Solution{
/*解法二： 上述c++补充思路的Java代码实现*/
public int[][] findPartitions(String s) {
List<Integer> temp = new ArrayList<>();
int[][] hash = new int[26][2];//26个字母2列 表示该字母对应的区间
for (int i = 0; i < s.length(); i++) {
//更新字符c对应的位置i
char c = s.charAt(i);
if (hash[c - 'a'][0] == 0) hash[c - 'a'][0] = i;
hash[c - 'a'][1] = i;
//第一个元素区别对待一下
hash[s.charAt(0) - 'a'][0] = 0;
}
List<List<Integer>> h = new LinkedList<>();
//组装区间
for (int i = 0; i < 26; i++) {
//if (hash[i][0] != hash[i][1]) {
temp.clear();
temp.add(hash[i][0]);
temp.add(hash[i][1]);
//System.out.println(temp);
h.add(new ArrayList<>(temp));
// }
}
// System.out.println(h);
// System.out.println(h.size());
int[][] res = new int[h.size()][2];
for (int i = 0; i < h.size(); i++) {
List<Integer> list = h.get(i);
res[i][0] = list.get(0);
res[i][1] = list.get(1);
}
return res;
}
public List<Integer> partitionLabels(String s) {
int[][] partitions = findPartitions(s);
List<Integer> res = new ArrayList<>();
Arrays.sort(partitions, (o1, o2) -> Integer.compare(o1[0], o2[0]));
int right = partitions[0][1];
int left = 0;
for (int i = 0; i < partitions.length; i++) {
if (partitions[i][0] > right) {
//左边界大于右边界即可纪委一次分割
res.add(right - left + 1);
left = partitions[i][0];
}
right = Math.max(right, partitions[i][1]);
}
//最右端
res.add(right - left + 1);
return res;
}
}9.14 划分字母区间
字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。
示例：
输入：S = "ababcbacadefegdehijhklij"
输出：[9,7,8] 解释： 划分结果为 "ababcbaca", "defegde", "hijhklij"。 每个字母最多出现在一个片段中。 像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。
提示：
S的长度在[1, 500]之间。
S只包含小写字母 'a' 到 'z' class Solution {
public List<Integer> partitionLabels(String S) {
List<Integer> list = new LinkedList<>();
int[] edge = new int[26];
char[] chars = S.toCharArray();
for (int i = 0; i < chars.length; i++) {
edge[chars[i] - 'a'] = i;
}
int idx = 0;
int last = -1;
for (int i = 0; i < chars.length; i++) {
idx = Math.max(idx,edge[chars[i] - 'a']);
if (i == idx) {
list.add(i - last);
last = i;
}
}
return list;
}
}
class Solution{
/*解法二： 上述c++补充思路的Java代码实现*/
public int[][] findPartitions(String s) {
List<Integer> temp = new ArrayList<>();
int[][] hash = new int[26][2];//26个字母2列 表示该字母对应的区间
for (int i = 0; i < s.length(); i++) {
//更新字符c对应的位置i
char c = s.charAt(i);
if (hash[c - 'a'][0] == 0) hash[c - 'a'][0] = i;
hash[c - 'a'][1] = i;
//第一个元素区别对待一下
hash[s.charAt(0) - 'a'][0] = 0;
}
List<List<Integer>> h = new LinkedList<>();
//组装区间
for (int i = 0; i < 26; i++) {
//if (hash[i][0] != hash[i][1]) {
temp.clear();
temp.add(hash[i][0]);
temp.add(hash[i][1]);
//System.out.println(temp);
h.add(new ArrayList<>(temp));
// }
}
// System.out.println(h);
// System.out.println(h.size());
int[][] res = new int[h.size()][2];
for (int i = 0; i < h.size(); i++) {
List<Integer> list = h.get(i);
res[i][0] = list.get(0);
res[i][1] = list.get(1);
}
return res;
}
public List<Integer> partitionLabels(String s) {
int[][] partitions = findPartitions(s);
List<Integer> res = new ArrayList<>();
Arrays.sort(partitions, (o1, o2) -> Integer.compare(o1[0], o2[0]));
int right = partitions[0][1];
int left = 0;
for (int i = 0; i < partitions.length; i++) {
if (partitions[i][0] > right) {
//左边界大于右边界即可纪委一次分割
res.add(right - left + 1);
left = partitions[i][0];
}
right = Math.max(right, partitions[i][1]);
}
//最右端
res.add(right - left + 1);
return res;
}
}9.15 合并区间
给出一个区间的集合，请合并所有重叠的区间。
示例 1:
输入: intervals = [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2:
输入: intervals = [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。
注意：输入类型已于2019年4月15日更改。 请重置默认代码定义以获取新方法签名。/**
时间复杂度 ： O(NlogN) 排序需要O(NlogN)
空间复杂度 ： O(logN) java 的内置排序是快速排序 需要 O(logN)空间
*/
class Solution {
public int[][] merge(int[][] intervals) {
List<int[]> res = new LinkedList<>();
//按照左边界排序
Arrays.sort(intervals, (x, y) -> Integer.compare(x[0], y[0]));
//initial start 是最小左边界
int start = intervals[0][0];
int rightmostRightBound = intervals[0][1];
for (int i = 1; i < intervals.length; i++) {
//如果左边界大于最大右边界
if (intervals[i][0] > rightmostRightBound) {
//加入区间 并且更新start
res.add(new int[]{start, rightmostRightBound});
start = intervals[i][0];
rightmostRightBound = intervals[i][1];
} else {
//更新最大右边界
rightmostRightBound = Math.max(rightmostRightBound, intervals[i][1]);
}
}
res.add(new int[]{start, rightmostRightBound});
return res.toArray(new int[res.size()][]);
}
}
// 版本2
class Solution {
public int[][] merge(int[][] intervals) {
LinkedList<int[]> res = new LinkedList<>();
Arrays.sort(intervals, (o1, o2) -> Integer.compare(o1[0], o2[0]));
res.add(intervals[0]);
for (int i = 1; i < intervals.length; i++) {
if (intervals[i][0] <= res.getLast()[1]) {
int start = res.getLast()[0];
int end = Math.max(intervals[i][1], res.getLast()[1]);
res.removeLast();
res.add(new int[]{start, end});
}
else {
res.add(intervals[i]);
}
}
return res.toArray(new int[res.size()][]);
}
}9.16 单调递增的数字
给定一个非负整数 N，找出小于或等于 N 的最大的整数，同时这个整数需要满足其各个位数上的数字是单调递增。
（当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。）
示例 1:
输入: N = 10
输出: 9
示例 2:
输入: N = 1234
输出: 1234
示例 3:
输入: N = 332
输出: 299
说明: N 是在 [0, 10^9] 范围内的一个整数。版本1
class Solution {
public int monotoneIncreasingDigits(int N) {
String[] strings = (N + "").split("");
int start = strings.length;
for (int i = strings.length - 1; i > 0; i--) {
if (Integer.parseInt(strings[i]) < Integer.parseInt(strings[i - 1])) {
strings[i - 1] = (Integer.parseInt(strings[i - 1]) - 1) + "";
start = i;
}
}
for (int i = start; i < strings.length; i++) {
strings[i] = "9";
}
return Integer.parseInt(String.join("",strings));
}
}
java版本1中创建了String数组，多次使用Integer.parseInt了方法，这导致不管是耗时还是空间占用都非常高，用时12ms，下面提供一个版本在char数组上原地修改，用时1ms的版本
版本2
class Solution {
public int monotoneIncreasingDigits(int n) {
String s = String.valueOf(n);
char[] chars = s.toCharArray();
int start = s.length();
for (int i = s.length() - 2; i >= 0; i--) {
if (chars[i] > chars[i + 1]) {
chars[i]--;
start = i+1;
}
}
for (int i = start; i < s.length(); i++) {
chars[i] = '9';
}
return Integer.parseInt(String.valueOf(chars));
}
}自己遇到的题目
9.1 花花快长大
阿岳的女朋友很喜欢花！
为次阿岳亲自种了一个花园，每天都会去浇水，每朵花都有一个长度，浇水后长度会增高1。
其中花园里有n朵花，阿岳会每天挑选n-1朵花浇水，最少多少天所有的花会一样长?
输入
第一行 一个整数n 表示花的个数
第二行 n 个整数ai 表示每朵花的初始长度 (0≤i ＜n )
输出
一个整数 表示使所有元素相等的最小操作次数
测试点数据规模与约定
对于100%的测试点，保证0<n <104，0≤ai <104
样例输入
3
1 2 3
样例输出
3
提示
样例数据中，每次操作增加2个元素的值 ，最少操作3次
[1,2,3] => [2,3,3] => [3,4,3] => [4,4,4]
数学思维能力是学习数学的核心能力,逆向思维是数学思维中一个重要表现形式,在数学基础知识和解题方法中发挥着不可替代的作用.import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] arr = new int[n];
int ans = 0;
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
Arrays.sort(arr); // 对数组进行排序
int min = arr[0]; // 直接取排序后的数组的第一个元素即为最小值
// 每浇一次，就能使最小值与没被浇的差-1
//[1,2,3] => [2,3,3] => [3,4,3] => [4,4,4]
for (int num : arr) {
ans += num - min;
}
System.out.println(ans);
}
}
//这个问题可以通过数学的思维进行解决，特别是在寻找最优解的情况下。一个关键点是，阿岳每天都浇水，只选择 n-1 朵花进行浇水。这意味着每次选择的 n-1 朵花中，必定有一朵花每天都不会浇水。考虑到这一点，我们可以找出这 n 朵花中最小的长度作为基准值，然后通过浇水来增加其他花朵的长度，使它们和基准值相等。最小操作次数即为所有花长度与基准值的差值之和。9.2 除草
题目描述
阿岳一共种了n块地，为了让地的产量更高，阿岳每天都会去地里除草(除草后仍会长草)，
由于一些原因阿岳一天只能除一块地的草，n 天后阿岳将所有地都除了一遍草，但每块地草
的生长速度vi 不同，n 天后所有草的长度总和的最小值是多少呢？
测试点数据规模
对于100%的测试点，保证 0<n <1000 1<vi <1000
输入
第一行输入一个整数n(表示地的块数)
第二行n个数(表示杂草的生长速度)
输出
n天后所有草的长度总和
样例输入
3
1 3 2
样例输出
4
提示
第一天：除第一块地的草，总长度0+3+2=5
第二天：除第三块地的草，总长度1+6+0=7
第三天：除第二块地的草，总长度2+0+2=4import java.util.Arrays;
import java.util.Scanner;
//岳神除草
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int arr[]=new int [n];
for(int i=0;i<n;i++) {
arr[i]=sc.nextInt();
}
Arrays.sort(arr);//根据规律，长得越快，放到最后除
int sum=0;
for(int i=0;i<n;i++) {
sum+=Arrays.stream(arr).sum()-arr[i]*(i+1);
}
//Arrays.stream(arr)求数组总和
System.out.println(sum);
}
}9.3 排队买票
小伊同学在暑假的时候来到电影院打工。正巧赶上电影院，一部新的电影要上映。题目中会给你一个整数数组 num 代表排队买票的人付的钱。来排队买票的人都只会拿出一张 25，50 或 100 元的钞票购买电影票。电影票的价格是 25 元，小伊同学刚开始手里没有初始金钱，现在请你帮小伊同学编写代码，判断一下她是否可以正常的给这 n 个人售票并找零？
输入格式一个整数数组。 输出格式 True或False。 输入输出样例1输入25输出True 输入输出样例2输入50 25输出False
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] bills = new int[n];
for (int i = 0; i < n; i++) {
bills[i] = scanner.nextInt();
}
boolean result = canSellTickets(n, bills);
System.out.println(result ? "True" : "False");
}
public static boolean canSellTickets(int n, int[] bills) {
int k = 0;
int j = 0;
for (int i = 0; i < n; i++) {
int l = bills[i];
if (l == 25) {
k += 1;//如果是25手中持有的25加一
} else if (l == 50) {
k -= 1;//如果是50块钱，需要找回25，所以手中的钱减一
} else if (l == 100) {
k -= 3;//同理，可得100是减三
}
if (k < 0) {
return false;//如果k小于零证明手中已经没有钱了，直接退出循环
}
j++;
}
return j >= n;
}
}9.4 数组跳跃
题目描述
小岳岳在抖音发布了一条视频，视频中他问道：“我这一生如履薄冰，你说我能走到对岸吗？”
现输入一个非负整数数组 nums ，小岳岳最初位于数组的第一个下标，数组中的每个元素代表小岳岳在该位置可以向前跳跃的最大长度。请你判断小岳岳是否能够走到对岸（到达最后一个下标），如果可以，输出 true ；否则，输出 false 。
输入
一个字符串 形式为一串以","隔开的整数ai 表示数组nums
输出
一个布尔值(true或false) 表示能否到达最后一个下标
测试点数据规模与约定
对于100%的测试点，保证0<nums.length <10，0≤ai <5
样例输入
2,3,1,1,4
样例输出
true
提示
nums = [2,3,1,1,4] 结果为true 解释： 可以先跳 1 步，从下标 0 到达下标 1,
然后再从下标 1 跳 3 步到达最后一个下标。import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println(judge(sc.nextLine().split(",")));
}
public static boolean judge(String[] s){
int len = 0;//记录能够跳到的最远位置。
int n = s.length-1;
for (int i = 0; i < n&&i<=len; i++) {//
len = Math.max(len,i+Integer.parseInt(s[i]));//将其设置为当前位置能够到达的最远位置
// [2,3,1,1,4]
// [0,1,2,3,4]下标
//len= max(0,0+2);
//len= max(2,1+3);
//len= max(4,2+1);
//len= max(4,3+1);
//len= max(4,4+4);
if(len >= n)break; // 8>5 如果 len 已经可以到达最后一个位置，就提前结束循环，因为已经满足条件了。
}
return len >= n; // 8 > 5
}
}
//i < n: 这个条件确保循环索引 i 不会超出数组的长度。因为数组的索引是从 0 开始的，所以当 i 达到 n（数组长度）时，就超出了数组的范围，遍历也就不再需要了。
//i <= len: 这个条件是基于贪心算法的思想。它确保只在当前已知能够到达的范围内进行遍历。len 记录了当前能够到达的最远位置，因此只有当当前的索引 i 在这个范围内时，才继续进行遍历。如果 i 超出了当前能够到达的范围 len，就没有必要再继续遍历了，因为已经无法到达后面的位置了9.5 摆动序列
如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的话）可能是正数或负数。少于两个元素的序列也是摆动序列。
例如， [1,7,4,9,2,5] 是一个摆动序列，因为差值 (6,-3,5,-7,3) 是正负交替出现的。相反, [1,4,7,2,5] 和 [1,7,4,5,5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。
给定一个整数序列，返回作为摆动序列的最长子序列的长度。 通过从原始序列中删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。
示例 1:
输入: [1,7,4,9,2,5]
输出: 6
解释: 整个序列均为摆动序列。
示例 2:
输入: [1,17,5,10,13,15,10,5,16,8]
输出: 7
解释: 这个序列包含几个长度为 7 摆动序列，其中一个可为[1,17,10,13,10,16,8]。
示例 3:
输入: [1,2,3,4,5,6,7,8,9]
输出: 2//贪心算法
class Solution {
public int wiggleMaxLength(int[] nums) {
if (nums.length <= 1) {
return nums.length;
}
//当前差值
int curDiff = 0;
//上一个差值
int preDiff = 0;
int count = 1;
for (int i = 1; i < nums.length; i++) {
//得到当前差值
curDiff = nums[i] - nums[i - 1];
//如果当前差值和上一个差值为一正一负
//等于0的情况表示初始时的preDiff
if ((curDiff > 0 && preDiff <= 0) || (curDiff < 0 && preDiff >= 0)) {
count++;
preDiff = curDiff;// 摆动变化的时候，更新 prediff
}
}
return count;
}
}
//动态规划1
//动态规划210.动态规划
动态规划理论基础
动态规划刷题大纲
什么是动态规划
动态规划，英文：Dynamic Programming，简称DP，如果某一问题有很多重叠子问题，使用动态规划是最有效的。
所以动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的，
在关于贪心算法，你该了解这些！ (opens new window)中我举了一个背包问题的例子。
例如：有N件物品和一个最多能背重量为W 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
动态规划中dp[j]是由dp[j-weight[i]]推导出来的，然后取max(dp[j], dp[j - weight[i]] + value[i])。
但如果是贪心呢，每次拿物品选一个最大的或者最小的就完事了，和上一个状态没有关系。
所以贪心解决不了动态规划的问题。
其实大家也不用死扣动规和贪心的理论区别，后面做做题目自然就知道了。
而且很多讲解动态规划的文章都会讲最优子结构啊和重叠子问题啊这些，这些东西都是教科书的上定义，晦涩难懂而且不实用。
大家知道动规是由前一个状态推导出来的，而贪心是局部直接选最优的，对于刷题来说就够用了。
上述提到的背包问题，后序会详细讲解。
动态规划的解题步骤
做动规题目的时候，很多同学会陷入一个误区，就是以为把状态转移公式背下来，照葫芦画瓢改改，就开始写代码，甚至把题目AC之后，都不太清楚dp[i]表示的是什么。
这就是一种朦胧的状态，然后就把题给过了，遇到稍稍难一点的，可能直接就不会了，然后看题解，然后继续照葫芦画瓢陷入这种恶性循环中。
状态转移公式（递推公式）是很重要，但动规不仅仅只有递推公式。
对于动态规划问题，我将拆解为如下五步曲，这五步都搞清楚了，才能说把动态规划真的掌握了！
确定dp数组（dp table）以及下标的含义
确定递推公式
dp数组如何初始化
确定遍历顺序
举例推导dp数组
一些同学可能想为什么要先确定递推公式，然后在考虑初始化呢？
因为一些情况是递推公式决定了dp数组要如何初始化！
后面的讲解中我都是围绕着这五点来进行讲解。
可能刷过动态规划题目的同学可能都知道递推公式的重要性，感觉确定了递推公式这道题目就解出来了。
其实 确定递推公式 仅仅是解题里的一步而已！
一些同学知道递推公式，但搞不清楚dp数组应该如何初始化，或者正确的遍历顺序，以至于记下来公式，但写的程序怎么改都通过不了。
后序的讲解的大家就会慢慢感受到这五步的重要性了。
动态规划应该如何debug
相信动规的题目，很大部分同学都是这样做的。
看一下题解，感觉看懂了，然后照葫芦画瓢，如果能正好画对了，万事大吉，一旦要是没通过，就怎么改都通过不了，对 dp数组的初始化，递推公式，遍历顺序，处于一种黑盒的理解状态。
写动规题目，代码出问题很正常！
找问题的最好方式就是把dp数组打印出来，看看究竟是不是按照自己思路推导的！
一些同学对于dp的学习是黑盒的状态，就是不清楚dp数组的含义，不懂为什么这么初始化，递推公式背下来了，遍历顺序靠习惯就是这么写的，然后一鼓作气写出代码，如果代码能通过万事大吉，通过不了的话就凭感觉改一改。
这是一个很不好的习惯！
做动规的题目，写代码之前一定要把状态转移在dp数组的上具体情况模拟一遍，心中有数，确定最后推出的是想要的结果。
然后再写代码，如果代码没通过就打印dp数组，看看是不是和自己预先推导的哪里不一样。
如果打印出来和自己预先模拟推导是一样的，那么就是自己的递归公式、初始化或者遍历顺序有问题了。
如果和自己预先模拟推导的不一样，那么就是代码实现细节有问题。
这样才是一个完整的思考过程，而不是一旦代码出问题，就毫无头绪的东改改西改改，最后过不了，或者说是稀里糊涂的过了。
这也是我为什么在动规五步曲里强调推导dp数组的重要性。
举个例子哈：在「代码随想录」刷题小分队微信群里，一些录友可能代码通过不了，会把代码抛到讨论群里问：我这里代码都已经和题解一模一样了，为什么通过不了呢？
发出这样的问题之前，其实可以自己先思考这三个问题：
这道题目我举例推导状态转移公式了么？
我打印dp数组的日志了么？
打印出来了dp数组和我想的一样么？
如果这灵魂三问自己都做到了，基本上这道题目也就解决了，或者更清晰的知道自己究竟是哪一点不明白，是状态转移不明白，还是实现代码不知道该怎么写，还是不理解遍历dp数组的顺序。
然后在问问题，目的性就很强了，群里的小伙伴也可以快速知道提问者的疑惑了。
注意这里不是说不让大家问问题哈， 而是说问问题之前要有自己的思考，问题要问到点子上！
大家工作之后就会发现，特别是大厂，问问题是一个专业活，是的，问问题也要体现出专业！
如果问同事很不专业的问题，同事们会懒的回答，领导也会认为你缺乏思考能力，这对职场发展是很不利的。
所以大家在刷题的时候，就锻炼自己养成专业提问的好习惯。
总结
这一篇是动态规划的整体概述，讲解了什么是动态规划，动态规划的解题步骤，以及如何debug。
动态规划是一个很大的领域，今天这一篇讲解的内容是整个动态规划系列中都会使用到的一些理论基础。
在后序讲解中针对某一具体问题，还会讲解其对应的理论基础，例如背包问题中的01背包，leetcode上的题目都是01背包的应用，而没有纯01背包的问题，那么就需要在把对应的理论知识讲解一下。
大家会发现，我讲解的理论基础并不是教科书上各种动态规划的定义，错综复杂的公式。
这里理论基础篇已经是非常偏实用的了，每个知识点都是在解题实战中非常有用的内容，大家要重视起来哈。
今天我们开始新的征程了，你准备好了么？
代码随想录题目
https://www.programmercarl.com/0509.%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0.html
10.1 斐波那契数
斐波那契数，通常用 F(n) 表示，形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是： F(0) = 0，F(1) = 1 F(n) = F(n - 1) + F(n - 2)，其中 n > 1 给你n ，请计算 F(n) 。0 1 1 2 3 5 8 13
class Solution {
public int fib(int n) {
if (n < 2) return n;
int a = 0, b = 1, c = 0;
for (int i = 1; i < n; i++) {
c = a + b;
a = b;
b = c;
}
return c;
}
}
//非压缩状态的版本
class Solution {
public int fib(int n) {
if (n <= 1) return n;
int[] dp = new int[n + 1];
dp[0] = 0;
dp[1] = 1;
for (int index = 2; index <= n; index++){
dp[index] = dp[index - 1] + dp[index - 2];
}
return dp[n];
}
}10.2 爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例 1：
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1 阶 + 1 阶
2 阶
示例 2：
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1 阶 + 1 阶 + 1 阶
1 阶 + 2 阶
2 阶 + 1 阶// 常规方式
public int climbStairs(int n) {
int[] dp = new int[n + 1];
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
// 用变量记录代替数组
class Solution {
public int climbStairs(int n) {
if(n <= 2) return n;
int a = 1, b = 2, sum = 0;
for(int i = 3; i <= n; i++){
sum = a + b; // f(i - 1) + f(i - 2)
a = b; // 记录f(i - 1)，即下一轮的f(i - 2)
b = sum; // 记录f(i)，即下一轮的f(i - 1)
}
return b;
}
}10.4 用最小花费爬楼梯
旧题目描述：
数组的每个下标作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值 cost[i]（下标从 0 开始）。
每当你爬上一个阶梯你都要花费对应的体力值，一旦支付了相应的体力值，你就可以选择向上爬一个阶梯或者爬两个阶梯。
请你找出达到楼层顶部的最低花费。在开始时，你可以选择从下标为 0 或 1 的元素作为初始阶梯。
示例 1：
输入：cost = [10, 15, 20]
输出：15
解释：最低花费是从 cost[1] 开始，然后走两步即可到阶梯顶，一共花费 15 。
示例 2：
输入：cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
输出：6
解释：最低花费方式是从 cost[0] 开始，逐个经过那些 1 ，跳过 cost[3] ，一共花费 6 。
提示：
cost 的长度范围是 [2, 1000]。
cost[i] 将会是一个整型数据，范围为 [0, 999] 。// 方式一：第一步不支付费用
class Solution {
public int minCostClimbingStairs(int[] cost) {
int len = cost.length;
int[] dp = new int[len + 1];
// 从下标为 0 或下标为 1 的台阶开始，因此支付费用为0
dp[0] = 0;
dp[1] = 0;
// 计算到达每一层台阶的最小费用
for (int i = 2; i <= len; i++) {
dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
}
return dp[len];
}
}
// 方式二：第一步支付费用
class Solution {
public int minCostClimbingStairs(int[] cost) {
int[] dp = new int[cost.length];
dp[0] = cost[0];
dp[1] = cost[1];
for (int i = 2; i < cost.length; i++) {
dp[i] = Math.min(dp[i - 1], dp[i - 2]) + cost[i];
}
//最后一步，如果是由倒数第二步爬，则最后一步的体力花费可以不用算
return Math.min(dp[cost.length - 1], dp[cost.length - 2]);
}
}10.5 不同路径
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
输入：m = 3, n = 7
输出：28
示例 2：
输入：m = 2, n = 3
输出：3
解释： 从左上角开始，总共有 3 条路径可以到达右下角。
向右 -> 向右 -> 向下
向右 -> 向下 -> 向右
向下 -> 向右 -> 向右
示例 3：
输入：m = 7, n = 3
输出：28
示例 4：
输入：m = 3, n = 3
输出：6
提示：
1 <= m, n <= 100
题目数据保证答案小于等于 2 * 10^9 /**
* 1. 确定dp数组下标含义 dp[i][j] 到每一个坐标可能的路径种类
* 2. 递推公式 dp[i][j] = dp[i-1][j] dp[i][j-1]
* 3. 初始化 dp[i][0]=1 dp[0][i]=1 初始化横竖就可
* 4. 遍历顺序 一行一行遍历
* 5. 推导结果 。。。。。。。。
*
* @param m
* @param n
* @return
*/
public static int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
//初始化
for (int i = 0; i < m; i++) {
dp[i][0] = 1;
}
for (int i = 0; i < n; i++) {
dp[0][i] = 1;
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = dp[i-1][j]+dp[i][j-1];
}
}
return dp[m-1][n-1];
}10.6 不同路径2
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网格中的障碍物和空位置分别用 1 和 0 来表示。
示例 1：
输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2 解释：
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
向右 -> 向右 -> 向下 -> 向下
向下 -> 向下 -> 向右 -> 向右
示例 2：
输入：obstacleGrid = [[0,1],[0,0]]
输出：1
提示：
m == obstacleGrid.length
n == obstacleGrid[i].length
1 <= m, n <= 100
obstacleGrid[i][j] 为 0 或 1class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
int[][] dp = new int[m][n];
//如果在起点或终点出现了障碍，直接返回0
if (obstacleGrid[m - 1][n - 1] == 1 || obstacleGrid[0][0] == 1) {
return 0;
}
for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) {
dp[i][0] = 1;
}
for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) {
dp[0][j] = 1;
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = (obstacleGrid[i][j] == 0) ? dp[i - 1][j] + dp[i][j - 1] : 0;
// (i, j)如果就是障碍的话应该就保持初始状态（初始状态为0）
}
}
return dp[m - 1][n - 1];
}
}
// 空间优化版本
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
int[] dp = new int[n];
for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) {
dp[j] = 1;
}
for (int i = 1; i < m; i++) {
for (int j = 0; j < n; j++) {
if (obstacleGrid[i][j] == 1) {
dp[j] = 0;
} else if (j != 0) {
dp[j] += dp[j - 1];
}
}
}
return dp[n - 1];
}
}10.7 整数拆分
给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
示例 1:
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。
示例 2:
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
说明: 你可以假设 n 不小于 2 且不大于 58。class Solution {
public int integerBreak(int n) {
//dp[i] 为正整数 i 拆分后的结果的最大乘积
int[] dp = new int[n+1];
dp[2] = 1;
for(int i = 3; i <= n; i++) {
for(int j = 1; j <= i-j; j++) {
// 这里的 j 其实最大值为 i-j,再大只不过是重复而已，
//并且，在本题中，我们分析 dp[0], dp[1]都是无意义的，
//j 最大到 i-j,就不会用到 dp[0]与dp[1]
dp[i] = Math.max(dp[i], Math.max(j*(i-j), j*dp[i-j]));
// j * (i - j) 是单纯的把整数 i 拆分为两个数 也就是 i,i-j ，再相乘
//而j * dp[i - j]是将 i 拆分成两个以及两个以上的个数,再相乘。
}
}
return dp[n];
}
}
class Solution {
public:
int integerBreak(int n) {
if (n == 2) return 1;
if (n == 3) return 2;
if (n == 4) return 4;
int result = 1;
while (n > 4) {
result *= 3;
n -= 3;
}
result *= n;
return result;
}
};
//本题也可以用贪心，每次拆成n个3，如果剩下是4，则保留4，然后相乘，但是这个结论需要数学证明其合理性！10.8 0-1背包
题目描述
小明是一位科学家，他需要参加一场重要的国际科学大会，以展示自己的最新研究成果。他需要带一些研究材料，但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实验样本等等，它们各自占据不同的空间，并且具有不同的价值。
小明的行李空间为 N，问小明应该如何抉择，才能携带最大价值的研究材料，每种研究材料只能选择一次，并且只有选与不选两种选择，不能进行切割。
输入描述
第一行包含两个正整数，第一个整数 M 代表研究材料的种类，第二个正整数 N，代表小明的行李空间。
第二行包含 M 个正整数，代表每种研究材料的所占空间。
第三行包含 M 个正整数，代表每种研究材料的价值。
输出描述
输出一个整数，代表小明能够携带的研究材料的最大价值。
输入示例
6 1
2 2 3 1 5 2
2 3 1 5 4 3
输出示例
5
提示信息
小明能够携带 6 种研究材料，但是行李空间只有 1，而占用空间为 1 的研究材料价值为 5，所以最终答案输出 5。
数据范围：
1 <= N <= 5000
1 <= M <= 5000
研究材料占用空间和价值都小于等于 1000public class BagProblem {
public static void main(String[] args) {
int[] weight = {1,3,4};
int[] value = {15,20,30};
int bagSize = 4;
testWeightBagProblem(weight,value,bagSize);
}
/**
* 动态规划获得结果
* @param weight 物品的重量
* @param value 物品的价值
* @param bagSize 背包的容量
*/
public static void testWeightBagProblem(int[] weight, int[] value, int bagSize){
// 创建dp数组
int goods = weight.length; // 获取物品的数量
int[][] dp = new int[goods][bagSize + 1];
// 初始化dp数组
// 创建数组后，其中默认的值就是0
for (int j = weight[0]; j <= bagSize; j++) {
dp[0][j] = value[0];
}
// 填充dp数组
for (int i = 1; i < weight.length; i++) {
for (int j = 1; j <= bagSize; j++) {
if (j < weight[i]) {
/**
* 当前背包的容量都没有当前物品i大的时候，是不放物品i的
* 那么前i-1个物品能放下的最大价值就是当前情况的最大价值
*/
dp[i][j] = dp[i-1][j];
} else {
/**
* 当前背包的容量可以放下物品i
* 那么此时分两种情况：
* 1、不放物品i
* 2、放物品i
* 比较这两种情况下，哪种背包中物品的最大价值最大
*/
dp[i][j] = Math.max(dp[i-1][j] , dp[i-1][j-weight[i]] + value[i]);
}
}
}
// 打印dp数组
for (int i = 0; i < goods; i++) {
for (int j = 0; j <= bagSize; j++) {
System.out.print(dp[i][j] + "\t");
}
System.out.println("\n");
}
}
}
import java.util.Arrays;
public class BagProblem {
public static void main(String[] args) {
int[] weight = {1,3,4};
int[] value = {15,20,30};
int bagSize = 4;
testWeightBagProblem(weight,value,bagSize);
}
/**
* 初始化 dp 数组做了简化(给物品增加冗余维)。这样初始化dp数组，默认全为0即可。
* dp[i][j] 表示从下标为[0 - i-1]的物品里任意取，放进容量为j的背包，价值总和最大是多少。
* 其实是模仿背包重量从 0 开始，背包容量 j 为 0 的话，即dp[i][0]，无论是选取哪些物品，背包价值总和一定为 0。
* 可选物品也可以从无开始，也就是没有物品可选，即dp[0][j]，这样无论背包容量为多少，背包价值总和一定为 0。
* @param weight 物品的重量
* @param value 物品的价值
* @param bagSize 背包的容量
*/
public static void testWeightBagProblem(int[] weight, int[] value, int bagSize){
// 创建dp数组
int goods = weight.length; // 获取物品的数量
int[][] dp = new int[goods + 1][bagSize + 1]; // 给物品增加冗余维，i = 0 表示没有物品可选
// 初始化dp数组，默认全为0即可
// 填充dp数组
for (int i = 1; i <= goods; i++) {
for (int j = 1; j <= bagSize; j++) {
if (j < weight[i - 1]) { // i - 1 对应物品 i
/**
* 当前背包的容量都没有当前物品i大的时候，是不放物品i的
* 那么前i-1个物品能放下的最大价值就是当前情况的最大价值
*/
dp[i][j] = dp[i - 1][j];
} else {
/**
* 当前背包的容量可以放下物品i
* 那么此时分两种情况：
* 1、不放物品i
* 2、放物品i
* 比较这两种情况下，哪种背包中物品的最大价值最大
*/
dp[i][j] = Math.max(dp[i - 1][j] , dp[i - 1][j - weight[i - 1]] + value[i - 1]); // i - 1 对应物品 i
}
}
}
// 打印dp数组
for(int[] arr : dp){
System.out.println(Arrays.toString(arr));
}
}
}10.9 01背包理论基础（滚动数组）
小明是一位科学家，他需要参加一场重要的国际科学大会，以展示自己的最新研究成果。他需要带一些研究材料，但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实验样本等等，它们各自占据不同的空间，并且具有不同的价值。
小明的行李空间为 N，问小明应该如何抉择，才能携带最大价值的研究材料，每种研究材料只能选择一次，并且只有选与不选两种选择，不能进行切割。
输入描述
第一行包含两个正整数，第一个整数 M 代表研究材料的种类，第二个正整数 N，代表小明的行李空间。
第二行包含 M 个正整数，代表每种研究材料的所占空间。
第三行包含 M 个正整数，代表每种研究材料的价值。
输出描述
输出一个整数，代表小明能够携带的研究材料的最大价值。
输入示例
6 1
2 2 3 1 5 2
2 3 1 5 4 3
输出示例
5
提示信息
小明能够携带 6 种研究材料，但是行李空间只有 1，而占用空间为 1 的研究材料价值为 5，所以最终答案输出 5。
数据范围：
1 <= N <= 5000
1 <= M <= 5000
研究材料占用空间和价值都小于等于 1000 public static void main(String[] args) {
int[] weight = {1, 3, 4};
int[] value = {15, 20, 30};
int bagWight = 4;
testWeightBagProblem(weight, value, bagWight);
}
public static void testWeightBagProblem(int[] weight, int[] value, int bagWeight){
int wLen = weight.length;
//定义dp数组：dp[j]表示背包容量为j时，能获得的最大价值
int[] dp = new int[bagWeight + 1];
//遍历顺序：先遍历物品，再遍历背包容量
for (int i = 0; i < wLen; i++){
for (int j = bagWeight; j >= weight[i]; j--){
//倒序遍历是为了保证物品i只被放入一次！。但如果一旦正序遍历了，那么物品0就会被重复加入多次！
dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
}
}
//打印dp数组
for (int j = 0; j <= bagWeight; j++){
System.out.print(dp[j] + " ");
}
}10.10 分割等和子集
题目难易：中等
给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
注意: 每个数组中的元素不会超过 100 数组的大小不会超过 200
示例 1:
输入: [1, 5, 11, 5]
输出: true
解释: 数组可以分割成 [1, 5, 5] 和 [11].
示例 2:
输入: [1, 2, 3, 5]
输出: false
解释: 数组不能分割成两个元素和相等的子集.
提示：
1 <= nums.length <= 200
1 <= nums[i] <= 100class Solution {
public boolean canPartition(int[] nums) {
if(nums == null || nums.length == 0) return false;
int n = nums.length;
int sum = 0;
for(int num : nums) {
sum += num;
}
//总和为奇数，不能平分
if(sum % 2 != 0) return false;
int target = sum / 2;
int[] dp = new int[target + 1];
for(int i = 0; i < n; i++) {
for(int j = target; j >= nums[i]; j--) {
//物品 i 的重量是 nums[i]，其价值也是 nums[i]
dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
}
//剪枝一下，每一次完成內層的for-loop，立即檢查是否dp[target] == target，優化時間複雜度（26ms -> 20ms）
if(dp[target] == target)
return true;
}
return dp[target] == target;
}
}
二维数组版本（易于理解）：
public class Solution {
public static void main(String[] args) {
int num[] = {1,5,11,5};
canPartition(num);
}
public static boolean canPartition(int[] nums) {
int len = nums.length;
// 题目已经说非空数组，可以不做非空判断
int sum = 0;
for (int num : nums) {
sum += num;
}
// 特判：如果是奇数，就不符合要求
if ((sum %2 ) != 0) {
return false;
}
int target = sum / 2; //目标背包容量
// 创建二维状态数组，行：物品索引，列：容量（包括 0）
/*
dp[i][j]表示从数组的 [0, i] 这个子区间内挑选一些正整数
每个数只能用一次，使得这些数的和恰好等于 j。
*/
boolean[][] dp = new boolean[len][target + 1];
// 先填表格第 0 行，第 1 个数只能让容积为它自己的背包恰好装满 （这里的dp[][]数组的含义就是“恰好”，所以就算容积比它大的也不要）
if (nums[0] <= target) {
dp[0][nums[0]] = true;
}
// 再填表格后面几行
//外层遍历物品
for (int i = 1; i < len; i++) {
//内层遍历背包
for (int j = 0; j <= target; j++) {
// 直接从上一行先把结果抄下来，然后再修正
dp[i][j] = dp[i - 1][j];
//如果某个物品单独的重量恰好就等于背包的重量，那么也是满足dp数组的定义的
if (nums[i] == j) {
dp[i][j] = true;
continue;
}
//如果某个物品的重量小于j，那就可以看该物品是否放入背包
//dp[i - 1][j]表示该物品不放入背包，如果在 [0, i - 1] 这个子区间内已经有一部分元素，使得它们的和为 j ，那么 dp[i][j] = true；
//dp[i - 1][j - nums[i]]表示该物品放入背包。如果在 [0, i - 1] 这个子区间内就得找到一部分元素，使得它们的和为 j - nums[i]。
if (nums[i] < j) {
dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]];
}
}
}
for (int i = 0; i < len; i++) {
for (int j = 0; j <= target; j++) {
System.out.print(dp[i][j]+" ");
}
System.out.println();
}
return dp[len - 1][target];
}
}
//dp数组的打印结果
false true false false false false false false false false false false
false true false false false true true false false false false false
false true false false false true true false false false false true
false true false false false true true false false false true true 10.1 最后一块石头的重量II
有一堆石头，每块石头的重量都是正整数。
每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
如果 x == y，那么两块石头都会被完全粉碎；
如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
最后，最多只会剩下一块石头。返回此石头最小的可能重量。如果没有石头剩下，就返回 0。
示例：
输入：[2,7,4,1,8,1]
输出：1
解释：
组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]，
组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]，
组合 2 和 1，得到 1，所以数组转化为 [1,1,1]，
组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。
提示：
1 <= stones.length <= 30
1 <= stones[i] <= 1000class Solution {
public int lastStoneWeightII(int[] stones) {
int sum = 0;
for (int i : stones) {
sum += i;
}
int target = sum >> 1;
//初始化dp数组
int[] dp = new int[target + 1];
for (int i = 0; i < stones.length; i++) {
//采用倒序
for (int j = target; j >= stones[i]; j--) {
//两种情况，要么放，要么不放
dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
}
}
return sum - 2 * dp[target];
}
}10.2 目标和
难度：中等
给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。
返回可以使最终数组和为目标数 S 的所有添加符号的方法数。
示例：
输入：nums: [1, 1, 1, 1, 1], S: 3
输出：5
解释：
-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3
一共有5种方法让最终目标和为3。
提示：
数组非空，且长度不会超过 20 。
初始的数组的和不会超过 1000 。
保证返回的最终结果能被 32 位整数存下。class Solution {
public int findTargetSumWays(int[] nums, int target) {
int sum = 0;
for (int i = 0; i < nums.length; i++) sum += nums[i];
//如果target过大 sum将无法满足
if ( target < 0 && sum < -target) return 0;
if ((target + sum) % 2 != 0) return 0;
int size = (target + sum) / 2;
if(size < 0) size = -size;
int[] dp = new int[size + 1];
dp[0] = 1;
for (int i = 0; i < nums.length; i++) {
for (int j = size; j >= nums[i]; j--) {
dp[j] += dp[j - nums[i]];
}
}
return dp[size];
}
}10.3 一和零 ***
给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
请你找出并返回 strs 的最大子集的大小，该子集中 最多 有 m 个 0 和 n 个 1 。
如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。
示例 1：
输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
输出：4
解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。 其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。
示例 2：
输入：strs = ["10", "0", "1"], m = 1, n = 1
输出：2
解释：最大的子集是 {"0", "1"} ，所以答案是 2 。
提示：
1 <= strs.length <= 600
1 <= strs[i].length <= 100
strs[i] 仅由 '0' 和 '1' 组成
1 <= m, n <= 100class Solution {
public int findMaxForm(String[] strs, int m, int n) {
//dp[i][j]表示i个0和j个1时的最大子集
int[][] dp = new int[m + 1][n + 1];
int oneNum, zeroNum;
for (String str : strs) {
oneNum = 0;
zeroNum = 0;
for (char ch : str.toCharArray()) {
if (ch == '0') {
zeroNum++;
} else {
oneNum++;
}
}
//倒序遍历
for (int i = m; i >= zeroNum; i--) {
for (int j = n; j >= oneNum; j--) {
dp[i][j] = Math.max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
}
}
}
return dp[m][n];
}
}10.4 完全背包
小明是一位科学家，他需要参加一场重要的国际科学大会，以展示自己的最新研究成果。他需要带一些研究材料，但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实验样本等等，它们各自占据不同的重量，并且具有不同的价值。
小明的行李箱所能承担的总重量为 N，问小明应该如何抉择，才能携带最大价值的研究材料，每种研究材料可以选择无数次，并且可以重复选择。
输入描述
第一行包含两个整数，N，V，分别表示研究材料的种类和行李空间
接下来包含 N 行，每行两个整数 wi 和 vi，代表第 i 种研究材料的重量和价值
输出描述
输出一个整数，表示最大价值。
输入示例
4 5
1 2
2 4
3 4
4 5
输出示例
10
提示信息
第一种材料选择五次，可以达到最大值。
数据范围：
1 <= N <= 10000;
1 <= V <= 10000;
1 <= wi, vi <= 10^9.//先遍历物品，再遍历背包
private static void testCompletePack(){
int[] weight = {1, 3, 4};
int[] value = {15, 20, 30};
int bagWeight = 4;
int[] dp = new int[bagWeight + 1];
for (int i = 0; i < weight.length; i++){ // 遍历物品
for (int j = weight[i]; j <= bagWeight; j++){ // 遍历背包容量
dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
}
}
for (int maxValue : dp){
System.out.println(maxValue + " ");
}
}
//先遍历背包，再遍历物品
private static void testCompletePackAnotherWay(){
int[] weight = {1, 3, 4};
int[] value = {15, 20, 30};
int bagWeight = 4;
int[] dp = new int[bagWeight + 1];
for (int i = 1; i <= bagWeight; i++){ // 遍历背包容量
for (int j = 0; j < weight.length; j++){ // 遍历物品
if (i - weight[j] >= 0){
dp[i] = Math.max(dp[i], dp[i - weight[j]] + value[j]);
}
}
}
for (int maxValue : dp){
System.out.println(maxValue + " ");
}
}10.5 零钱兑换II
给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
示例 1:
输入: amount = 5, coins = [1, 2, 5]
输出: 4
解释: 有四种方式可以凑成总金额:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
示例 2:
输入: amount = 3, coins = [2]
输出: 0
解释: 只用面额2的硬币不能凑成总金额3。
示例 3:
输入: amount = 10, coins = [10]
输出: 1
注意，你可以假设：
0 <= amount (总金额) <= 5000
1 <= coin (硬币面额) <= 5000
硬币种类不超过 500 种
结果符合 32 位符号整数class Solution {
public int change(int amount, int[] coins) {
//递推表达式
int[] dp = new int[amount + 1];
//初始化dp数组，表示金额为0时只有一种情况，也就是什么都不装
dp[0] = 1;
for (int i = 0; i < coins.length; i++) {
for (int j = coins[i]; j <= amount; j++) {
dp[j] += dp[j - coins[i]];
}
}
return dp[amount];
}
}
物品 背包 组合
背包 物品 排列
0-1背包
滚动数组 遍历顺序 物品背包倒序
完全背包
滚动数组 遍历顺序 物品背包或背包物品正序 10.6 组合总和
给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。
示例:
nums = [1, 2, 3]
target = 4
所有可能的组合为： (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1)
请注意，顺序不同的序列被视作不同的组合。
因此输出为 7。class Solution {
public int combinationSum4(int[] nums, int target) {
// 创建一个长度为target+1的数组dp，用于存储组合的个数
int[] dp = new int[target + 1];
dp[0] = 1; // 初始化dp[0]为1，表示和为0的组合只有一种方式，即不选择任何数字
// 外层循环遍历目标和的范围
for (int i = 0; i <= target; i++) {
// 内层循环遍历数组nums中的每个数字
for (int j = 0; j < nums.length; j++) {
// 当目标和大于等于当前数字时，计算组合的个数
if (i >= nums[j]) {
dp[i] += dp[i - nums[j]];
}
}
}
// 返回目标和的组合个数
return dp[target];
}
}10.7 爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬至多m (1 <= m < n)个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
输入描述
输入共一行，包含两个正整数，分别表示n, m
输出描述
输出一个整数，表示爬到楼顶的方法数。
输入示例
3 2
输出示例
3
提示信息
数据范围：
1 <= m < n <= 32;
当 m = 2，n = 3 时，n = 3 这表示一共有三个台阶，m = 2 代表你每次可以爬一个台阶或者两个台阶。
此时你有三种方法可以爬到楼顶。
1 阶 + 1 阶 + 1 阶段
1 阶 + 2 阶
2 阶 + 1 阶import java.util.Scanner;
class climbStairs{
public static void main(String [] args){
Scanner sc = new Scanner(System.in);
int m, n;
while (sc.hasNextInt()) {
// 从键盘输入参数，中间用空格隔开
n = sc.nextInt();
m = sc.nextInt();
// 求排列问题，先遍历背包再遍历物品
int[] dp = new int[n + 1];
dp[0] = 1;
for (int j = 1; j <= n; j++) {
for (int i = 1; i <= m; i++) {
if (j - i >= 0) dp[j] += dp[j - i];//确保只有在当前步数 j 大于等于单次爬升的步数 i 时，才会将之前的方式数量加到当前步数的方式数量上，以避免计算无效的方式数量
}
}
System.out.println(dp[n]);
}
}
}10.8 零钱兑换
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
你可以认为每种硬币的数量是无限的。
示例 1：
输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1
示例 2：
输入：coins = [2], amount = 3
输出：-1
示例 3：
输入：coins = [1], amount = 0
输出：0
示例 4：
输入：coins = [1], amount = 1
输出：1
示例 5：
输入：coins = [1], amount = 2
输出：2
提示：
1 <= coins.length <= 12
1 <= coins[i] <= 2^31 - 1
0 <= amount <= 10^4class Solution {
public int coinChange(int[] coins, int amount) {
int max = Integer.MAX_VALUE;
int[] dp = new int[amount + 1];
//初始化dp数组为最大值
for (int j = 0; j < dp.length; j++) {
dp[j] = max;
}
//当金额为0时需要的硬币数目为0
dp[0] = 0;
for (int i = 0; i < coins.length; i++) {
//正序遍历：完全背包每个硬币可以选择多次
for (int j = coins[i]; j <= amount; j++) {
//只有dp[j-coins[i]]不是初始最大值时，该位才有选择的必要
if (dp[j - coins[i]] != max) {
//选择硬币数目最小的情况
dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
}
}
}
return dp[amount] == max ? -1 : dp[amount];
}
}10.9 完全平方数
给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
给你一个整数 n ，返回和为 n 的完全平方数的 最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
示例 1：
输入：n = 12
输出：3
解释：12 = 4 + 4 + 4
示例 2：
输入：n = 13
输出：2
解释：13 = 4 + 9
提示：
1 <= n <= 10^4class Solution {
// 版本一，先遍历物品, 再遍历背包
public int numSquares(int n) {
int max = Integer.MAX_VALUE;
int[] dp = new int[n + 1];
//初始化
for (int j = 0; j <= n; j++) {
dp[j] = max;
}
//如果不想要寫for-loop填充數組的話，也可以用JAVA內建的Arrays.fill()函數。
//Arrays.fill(dp, Integer.MAX_VALUE);
//当和为0时，组合的个数为0
dp[0] = 0;
// 遍历物品
for (int i = 1; i * i <= n; i++) {
// 遍历背包
for (int j = i * i; j <= n; j++) {
//if (dp[j - i * i] != max) {
dp[j] = Math.min(dp[j], dp[j - i * i] + 1);
//}
//不需要這個if statement，因爲在完全平方數這一題不會有"湊不成"的狀況發生（ 一定可以用"1"來組成任何一個n），故comment掉這個if statement。
}
}
return dp[n];
}
}
class Solution {
// 版本二， 先遍历背包, 再遍历物品
public int numSquares(int n) {
int max = Integer.MAX_VALUE;
int[] dp = new int[n + 1];
// 初始化
for (int j = 0; j <= n; j++) {
dp[j] = max;
}
// 当和为0时，组合的个数为0
dp[0] = 0;
// 遍历背包
for (int j = 1; j <= n; j++) {
// 遍历物品
for (int i = 1; i * i <= j; i++) {
dp[j] = Math.min(dp[j], dp[j - i * i] + 1);
}
}
return dp[n];
}
}10.10 打家劫舍
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例 1：
输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。
示例 2：
输入：[2,7,9,3,1]
输出：12 解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。 偷窃到的最高金额 = 2 + 9 + 1 = 12 。
提示：
0 <= nums.length <= 100
0 <= nums[i] <= 400// 动态规划
class Solution {
public int rob(int[] nums) {
if (nums == null || nums.length == 0) return 0;
if (nums.length == 1) return nums[0];
int[] dp = new int[nums.length];
dp[0] = nums[0];
dp[1] = Math.max(dp[0], nums[1]);
for (int i = 2; i < nums.length; i++) {
dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
}
return dp[nums.length - 1];
}
}10.11 最长上升子序列
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 1：
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
示例 2：
输入：nums = [0,1,0,3,2,3]
输出：4
示例 3：
输入：nums = [7,7,7,7,7,7,7]
输出：1
提示：
1 <= nums.length <= 2500
-10^4 <= nums[i] <= 104class Solution {
public int lengthOfLIS(int[] nums) {
int[] dp = new int[nums.length];
int res = 0;
Arrays.fill(dp, 1);
for (int i = 1; i < dp.length; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
res = Math.max(res, dp[i]);
}
}
return res;
}
}10.12 最长连续递增序列
给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。
连续递增的子序列 可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。
示例 1：
输入：nums = [1,3,5,4,7]
输出：3
解释：最长连续递增序列是 [1,3,5], 长度为3。尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为 5 和 7 在原数组里被 4 隔开。
示例 2：
输入：nums = [2,2,2,2,2]
输出：1
解释：最长连续递增序列是 [2], 长度为1。
提示：
0 <= nums.length <= 10^4
-10^9 <= nums[i] <= 10^9/**
* 1.dp[i] 代表当前下标最大连续值
* 2.递推公式 if（nums[i+1]>nums[i]） dp[i+1] = dp[i]+1
* 3.初始化 都为1
* 4.遍历方向，从其那往后
* 5.结果推导 。。。。
* @param nums
* @return
*/
public static int findLengthOfLCIS(int[] nums) {
int[] dp = new int[nums.length];
for (int i = 0; i < dp.length; i++) {
dp[i] = 1;
}
int res = 1;
//可以注意到，這邊的 i 是從 0 開始，所以會出現和卡哥的C++ code有差異的地方，在一些地方會看到有 i + 1 的偏移。
for (int i = 0; i < nums.length - 1; i++) {
if (nums[i + 1] > nums[i]) {
dp[i + 1] = dp[i] + 1;
}
res = res > dp[i + 1] ? res : dp[i + 1];
}
return res;
}
贪心法：
public static int findLengthOfLCIS(int[] nums) {
if (nums.length == 0) return 0;
int res = 1; // 连续子序列最少也是1
int count = 1;
for (int i = 0; i < nums.length - 1; i++) {
if (nums[i + 1] > nums[i]) { // 连续记录
count++;
} else { // 不连续，count从头开始
count = 1;
}
if (count > res) res = count;
}
return res;
}10.13 最长重复子数组
给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。
示例：
输入：
A: [1,2,3,2,1]
B: [3,2,1,4,7]
输出：3
解释：长度最长的公共子数组是 [3, 2, 1] 。
提示：
1 <= len(A), len(B) <= 1000
0 <= A[i], B[i] < 100//暴力
class Solution {
public int findLength(int[] A, int[] B) {
int maxLength = 0;
for (int i = 0; i < A.length; i++) {
for (int j = 0; j < B.length; j++) {
int length = 0;
int k = i;
int l = j;
while (k < A.length && l < B.length && A[k] == B[l]) {
length++;
k++;
l++;
}
maxLength = Math.max(maxLength, length);
}
}
return maxLength;
}
}
//该解法使用两个嵌套循环遍历数组 A 和数组 B 的所有可能的子数组。对于每一对子数组，使用两个指针 k 和 l 分别指向数组 A 和数组 B 的当前位置，然后同时向后比较元素，直到元素不相等或者到达数组的末尾。在比较的过程中记录相等元素的个数，即公共子数组的长度。然后，通过比较得到的长度与当前的最大长度进行比较，并更新最大长度
10.14 最长公共子序列
给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。
若这两个字符串没有公共子序列，则返回 0。
示例 1:
输入：text1 = "abcde", text2 = "ace"
输出：3
解释：最长公共子序列是 "ace"，它的长度为 3。
示例 2:
输入：text1 = "abc", text2 = "abc"
输出：3
解释：最长公共子序列是 "abc"，它的长度为 3。
示例 3:
输入：text1 = "abc", text2 = "def"
输出：0
解释：两个字符串没有公共子序列，返回 0。
提示:
1 <= text1.length <= 1000
1 <= text2.length <= 1000 输入的字符串只含有小写英文字符。/*
二维dp数组
*/
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
// char[] char1 = text1.toCharArray();
// char[] char2 = text2.toCharArray();
// 可以在一開始的時候就先把text1, text2 轉成char[]，之後就不需要有這麼多爲了處理字串的調整
// 就可以和卡哥的code更一致
int[][] dp = new int[text1.length() + 1][text2.length() + 1]; // 先对dp数组做初始化操作
for (int i = 1 ; i <= text1.length() ; i++) {
char char1 = text1.charAt(i - 1);
for (int j = 1; j <= text2.length(); j++) {
char char2 = text2.charAt(j - 1);
if (char1 == char2) { // 开始列出状态转移方程
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[text1.length()][text2.length()];
}
}
//暴力
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
return longestCommonSubsequence(text1, text2, text1.length(), text2.length());
}
private int longestCommonSubsequence(String text1, String text2, int m, int n) {
if (m == 0 || n == 0)
return 0;
if (text1.charAt(m - 1) == text2.charAt(n - 1))
return 1 + longestCommonSubsequence(text1, text2, m - 1, n - 1);
return Math.max(longestCommonSubsequence(text1, text2, m - 1, n),
longestCommonSubsequence(text1, text2, m, n - 1));
}
}10.15 不相交的线
我们在两条独立的水平线上按给定的顺序写下 A 和 B 中的整数。
现在，我们可以绘制一些连接两个数字 A[i] 和 B[j] 的直线，只要 A[i] == B[j]，且我们绘制的直线不与任何其他连线（非水平线）相交。
以这种方法绘制线条，并返回我们可以绘制的最大连线数。 class Solution {
public int maxUncrossedLines(int[] nums1, int[] nums2) {
int len1 = nums1.length;
int len2 = nums2.length;
int[][] dp = new int[len1 + 1][len2 + 1];
for (int i = 1; i <= len1; i++) {
for (int j = 1; j <= len2; j++) {
if (nums1[i - 1] == nums2[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 dp[len1][len2];
}
}10.16 最大子序和
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6 public static int maxSubArray(int[] nums) {
if (nums.length == 0) {
return 0;
}
int res = nums[0];
int[] dp = new int[nums.length];
dp[0] = nums[0];
for (int i = 1; i < nums.length; i++) {
dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
res = res > dp[i] ? res : dp[i];
}
return res;
}10.17 判断子序列
给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
示例 1：
输入：s = "abc", t = "ahbgdc"
输出：true
示例 2：
输入：s = "axc", t = "ahbgdc"
输出：false
提示：
0 <= s.length <= 100
0 <= t.length <= 10^4
两个字符串都只由小写字符组成。//暴力
class Solution {
public boolean isSubsequence(String s, String t) {
int m = s.length();
int n = t.length();
int i = 0, j = 0;
while (i < m && j < n) {
if (s.charAt(i) == t.charAt(j)) {
i++;
}
j++;
}
return i == m;
}
}10.18 两个字符串的删除操作
给定两个单词 word1 和 word2，找到使得 word1 和 word2 相同所需的最小步数，每步可以删除任意一个字符串中的一个字符。
示例：
输入: "sea", "eat"
输出: 2
解释: 第一步将"sea"变为"ea"，第二步将"eat"变为"ea"递归暴力
class Solution {
public int minDistance(String word1, String word2) {
return minDistance(word1, word2, word1.length(), word2.length());
}
private int minDistance(String word1, String word2, int m, int n) {
if (m == 0) {
return n;
}
if (n == 0) {
return m;
}
if (word1.charAt(m - 1) == word2.charAt(n - 1)) {
return minDistance(word1, word2, m - 1, n - 1);
}
int deleteWord1 = minDistance(word1, word2, m - 1, n) + 1;
int deleteWord2 = minDistance(word1, word2, m, n - 1) + 1;
return Math.min(deleteWord1, deleteWord2);
}
}
//dp
class Solution {
public int minDistance(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 - dp[len1][len2] * 2;
}
}10.19 编辑距离
给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
插入一个字符
删除一个字符
替换一个字符
示例 1：
输入：word1 = "horse", word2 = "ros"
输出：3
解释： horse -> rorse (将 'h' 替换为 'r') rorse -> rose (删除 'r') rose -> ros (删除 'e')
示例 2：
输入：word1 = "intention", word2 = "execution"
输出：5
解释： intention -> inention (删除 't') inention -> enention (将 'i' 替换为 'e') enention -> exention (将 'n' 替换为 'x') exention -> exection (将 'n' 替换为 'c') exection -> execution (插入 'u')
提示：
0 <= word1.length, word2.length <= 500
word1 和 word2 由小写英文字母组成class Solution {
public int minDistance(String word1, String word2) {
return minDistance(word1, word2, word1.length() - 1, word2.length() - 1);
}
private int minDistance(String word1, String word2, int i, int j) {
// 如果有一个单词为空，则需要执行另一个单词的长度次插入或删除操作
if (i < 0) {
return j + 1;
}
if (j < 0) {
return i + 1;
}
// 如果两个字符相等，则继续比较下一个字符
if (word1.charAt(i) == word2.charAt(j)) {
return minDistance(word1, word2, i - 1, j - 1);
}
// 否则，尝试插入、删除、替换操作，并返回最小操作数
int insert = minDistance(word1, word2, i, j - 1) + 1;
int delete = minDistance(word1, word2, i - 1, j) + 1;
int replace = minDistance(word1, word2, i - 1, j - 1) + 1;
return Math.min(Math.min(insert, delete), replace);
}
}
public int minDistance(String word1, String word2) {
int m = word1.length();
int n = word2.length();
int[][] dp = new int[m + 1][n + 1];
// 初始化
for (int i = 1; i <= m; i++) {
dp[i][0] = i;
}
for (int j = 1; j <= n; j++) {
dp[0][j] = j;
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
// 因为dp数组有效位从1开始
// 所以当前遍历到的字符串的位置为i-1 | j-1
if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i][j - 1]), dp[i - 1][j]) + 1;
}
}
}
return dp[m][n];
}10.20 回文子串
给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
示例 1：
输入："abc"
输出：3
解释：三个回文子串: "a", "b", "c"
示例 2：
输入："aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"
提示：输入的字符串长度不会超过 1000 。//暴力1
import java.util.*;
import java.util.stream.IntStream;
import java.math.BigInteger;
public class Main {
public static void main(String[] args) {
String string="aaa";
System.out.println(countSubstrings(string));
}
public static int countSubstrings(String s) {
int count=0;
for(int i=0;i<s.length();i++){
for(int j=i;j<s.length();j++){
String s1=s.substring(i,j+1);
if(ifHw(s1)) {
count++;
}
}
}
return count;
}
public static boolean ifHw(String s) {
StringBuffer s1 =new StringBuffer(s);
if(s1.reverse().toString().equals(s)) {
return true;
}
return false;
}
}
//暴力2
class Solution {
public int countSubstrings(String s) {
int count = 0;
int n = s.length();
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
if (isPalindrome(s, i, j)) {
count++;
}
}
}
return count;
}
private boolean isPalindrome(String s, int start, int end) {
while (start < end) {
if (s.charAt(start) != s.charAt(end)) {
return false;
}
start++;
end--;
}
return true;
}
}
//dp
class Solution {
public int countSubstrings(String s) {
char[] chars = s.toCharArray();
int len = chars.length;
boolean[][] dp = new boolean[len][len];
int result = 0;
for (int i = len - 1; i >= 0; i--) {
for (int j = i; j < len; j++) {
if (chars[i] == chars[j]) {
if (j - i <= 1) { // 情况一 和 情况二
result++;
dp[i][j] = true;
} else if (dp[i + 1][j - 1]) { //情况三
result++;
dp[i][j] = true;
}
}
}
}
return result;
}
}10.21 最长回文子序列
给定一个字符串 s ，找到其中最长的回文子序列，并返回该序列的长度。可以假设 s 的最大长度为 1000 。
示例 1: 输入: "bbbab" 输出: 4 一个可能的最长回文子序列为 "bbbb"。
示例 2: 输入:"cbbd" 输出: 2 一个可能的最长回文子序列为 "bb"。
提示：
1 <= s.length <= 1000
s 只包含小写英文字母public class Solution {
public int longestPalindromeSubseq(String s) {
int len = s.length();
int[][] dp = new int[len + 1][len + 1];
for (int i = len - 1; i >= 0; i--) { // 从后往前遍历 保证情况不漏
dp[i][i] = 1; // 初始化
for (int j = i + 1; j < len; j++) {
if (s.charAt(i) == s.charAt(j)) {
dp[i][j] = dp[i + 1][j - 1] + 2;
} else {
dp[i][j] = Math.max(dp[i + 1][j], Math.max(dp[i][j], dp[i][j - 1]));
}
}
}
return dp[0][len - 1];
}
}
//递归暴力
class Solution {
public int longestPalindromeSubseq(String s) {
return longestPalindromeSubseqHelper(s, 0, s.length() - 1);
}
private int longestPalindromeSubseqHelper(String s, int start, int end) {
if (start == end) {
return 1; // 单个字符是回文子序列，长度为1
}
if (start > end) {
return 0; // 空字符串，回文子序列长度为0
}
if (s.charAt(start) == s.charAt(end)) {
return longestPalindromeSubseqHelper(s, start + 1, end - 1) + 2; // 头尾字符相等，长度加2
} else {
int option1 = longestPalindromeSubseqHelper(s, start + 1, end); // 舍弃开头字符
int option2 = longestPalindromeSubseqHelper(s, start, end - 1); // 舍弃末尾字符
return Math.max(option1, option2); // 返回两种选择中的较大值
}
}
}自己遇到的题目
10.2 买口罩（0-1背包）
某药店为了回馈顾客，拿出7个品牌的口罩做特价限购活动：A品牌是3个装2元，B品牌是3个装3元，C品牌是4个装2元，D品牌是5个装3元，E品牌是4个装5元，F品牌是1个装2元，G品牌是2个装2元，每个品牌只能买一包。小涵拿N元钱去药店买特价口罩，小涵最多能买多少个口罩？
注意：通过手算直接输出结果视作无效作答。输入说明：钱数N元（0＜＝N＜＝100）。
输出说明：能买到的口罩最大数量。输入样例1：10
输入样例2：25 输出样例1：15 输出样例2：22public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[][] nums = new int[][]{
{2, 3},
{3, 3},
{2, 4},
{3, 5},
{5, 4},
{2, 1},
{2, 2},
};
int[] record = new int[n + 1];
for (int i = 0; i < nums.length; i++) {//遍历口罩品牌
for (int j = n; j >= nums[i][0]; j--) {//从当前钱数n开始向前遍历，更新record数组
record[j] = Math.max(record[j], record[j - nums[i][0]] + nums[i][1]);//这行代码更新了record数组中不同价格下能购买的最大口罩数量。它利用状态转移方程来更新record数组，保留了在当前价格下能购买的最大口罩数量。
}
}
System.out.println(record[n]);
}
}
10.3 摆动序列
如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的话）可能是正数或负数。少于两个元素的序列也是摆动序列。
例如， [1,7,4,9,2,5] 是一个摆动序列，因为差值 (6,-3,5,-7,3) 是正负交替出现的。相反, [1,4,7,2,5] 和 [1,7,4,5,5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。
给定一个整数序列，返回作为摆动序列的最长子序列的长度。 通过从原始序列中删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。
示例 1:
输入: [1,7,4,9,2,5]
输出: 6
解释: 整个序列均为摆动序列。
示例 2:
输入: [1,17,5,10,13,15,10,5,16,8]
输出: 7
解释: 这个序列包含几个长度为 7 摆动序列，其中一个可为[1,17,10,13,10,16,8]。
示例 3:
输入: [1,2,3,4,5,6,7,8,9]
输出: 2//动态规划1
public int wiggleMaxLength(int[] nums) {
if (nums.length < 2) {
return nums.length;
}
int up = 1;
int down = 1;
for (int i = 1; i < nums.length; i++) {
if (nums[i] > nums[i - 1]) {
up = down + 1;
} else if (nums[i] < nums[i - 1]) {
down = up + 1;
}
}
return Math.max(up, down);
}
//动态规划2
class Solution {
public int wiggleMaxLength(int[] nums) {
// 0 i 作为波峰的最大长度
// 1 i 作为波谷的最大长度
int dp[][] = new int[nums.length][2];
dp[0][0] = dp[0][1] = 1;
for (int i = 1; i < nums.length; i++){
//i 自己可以成为波峰或者波谷
dp[i][0] = dp[i][1] = 1;
for (int j = 0; j < i; j++){
if (nums[j] > nums[i]){
// i 是波谷
dp[i][1] = Math.max(dp[i][1], dp[j][0] + 1);
}
if (nums[j] < nums[i]){
// i 是波峰
dp[i][0] = Math.max(dp[i][0], dp[j][1] + 1);
}
}
}
return Math.max(dp[nums.length - 1][0], dp[nums.length - 1][1]);
}
}
//贪心算法11.单调栈
单调栈理论基础
代码随想录题目
自己遇到的题目
12.图论
图论理论基础
代码随想录题目
自己遇到的题目
13.暴力破解
给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。
示例：
输入：
A: [1,2,3,2,1]
B: [3,2,1,4,7]
输出：3
解释：长度最长的公共子数组是 [3, 2, 1] 。
提示：
1 <= len(A), len(B) <= 1000
0 <= A[i], B[i] < 100
#算法公开课public class Solution {
public int findLength(int[] A, int[] B) {
int maxLength = 0;
for (int i = 0; i < A.length; i++) {
for (int j = 0; j < B.length; j++) {
int length = 0;
int a = i, b = j;
while (a < A.length && b < B.length && A[a] == B[b]) {
length++;
a++;
b++;
}
maxLength = Math.max(maxLength, length);
}
}
return maxLength;
}
public static void main(String[] args) {
int[] A = {1, 2, 3, 2, 1};
int[] B = {3, 2, 1, 4, 7};
Solution solution = new Solution();
int maxLength = solution.findLength(A, B);
System.out.println(maxLength);
}
}
//暴力的解法 只需要先两层for循环确定两个数组起始位置，然后再来一个循环可以是for或者while，来从两个起始位置开始比较，取得重复子数组的长度。14.排序算法
十大排序算法超全大综合，动图演示，你真的值得拥有！ - 力扣（LeetCode）
14.1 数位排序
题目描述
小蓝对一个数的数位之和很感兴趣，今天他要按照数位之和给数排序。当两个数各个数位之和不同时，将数位和较小的排在前面，当数位之和相等时，将数值小的排在前面。
例如，2022 排在 409 前面，因为 2022 的数位之和是 6，小于 409 的数位之和 13。
又如，6 排在 2022 前面，因为它们的数位之和相同，而 6 小于 2022。
给定正整数n，m，请问对 1 到 n 采用这种方法排序时，排在第 m 个的元素是多少？
输入格式：
输入第一行包含一个正整数 n。
第二行包含一个正整数 m。
输出格式：
输出一行包含一个整数，表示答案。
样例输入：
样例输出：
提示：
1 到 13 的排序为：1, 10, 2, 11, 3, 12, 4, 13, 5, 6, 7, 8, 9。第 5 个数为 3。
对于 30% 的评测用例，1 ≤ m ≤ n ≤ 300。
对于 50% 的评测用例，1 ≤ m ≤ n ≤ 1000。
对于所有评测用例，1 ≤ m ≤ n ≤ 106。解题思路：首先先创建一个计数器数组C，该数组用来统计原数组中每个元素在查询过程中被计算的次数。计算次数最多的位置就可以用来存放最大的数据，这样，重新排序后，得到的和就最大。
1）先创建数组C，统计数组中所有元素在查询过程中被计算求和的次数；
2）计算排序前的和；
3）将计数器数组中的数以及对应的数组的数从小到大排序，计算求和；
4）计算排序前后差值；
import java.util.Arrays;
import java.util.Scanner;
public class Main_G {
static int[]arr;
static int[][]arr_m;
static int[]count;
public static void main(String[] args) {
Scanner scan=new Scanner(System.in);
//输入
int N=scan.nextInt();
arr=new int[N];
for (int i = 0; i < N; i++) {
arr[i]=scan.nextInt();
}
int M=scan.nextInt();
arr_m=new int[M][2];
for (int i = 0; i < M; i++) {
arr_m[i][0]=scan.nextInt();
arr_m[i][1]=scan.nextInt();
}
//1）count纪录元素被加次数
count=new int[N];
for (int i = 0; i < M; i++) {
for (int j = arr_m[i][0]-1; j <=arr_m[i][1]-1 ; j++) {
count[j]++;
}
}
//排序前的和
int sum1=SUM(arr,count);
//对arr与count分别进行排序
Arrays.sort(arr);
Arrays.sort(count);
//排序后的和
int sum2=SUM(arr,count);
//输出结果
System.out.println(sum2-sum1);
}
public static int SUM(int []arr, int[] count){
int sum=0;
for (int i = 0; i < arr.length; i++) {
sum+=arr[i]*count[i];
}
return sum;
}
}15.数学和传统问题
15.1孔融让梨
孔融让梨一直是中国古代故事中谦逊的榜样。今天孔融又拿到了一些梨，他决定分给他的兄弟们，由于孔融很谦逊，他必须保证分给他兄弟的梨比自己的梨多。题目中会给你一行两个整数 `n` 和 `k` 代表，孔融要分给 `n` 个兄弟和他手里有 `k` 个梨。现在请你编写代码帮孔融计算，他最多能吃到多少个梨。
输入格式 一行两个整数 `n` 和 `k`。
输出格式 一个整数。
输入输出样例 输入 `5 10 输出 `0import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner scn=new Scanner(System.in);
int n=scn.nextInt(),k=scn.nextInt();
if(k%(n+1)>=n)//如果均分后的数量能够再给他每个兄弟分一个,则能得到k/(n+1)
System.out.print(k/(n+1));
else//否则为k/(n+1)-1个
System.out.print(k/(n+1)-1);
}
}15.2 擂台赛
小艾和他的两个朋友决定来一场羽毛球擂台赛。他们的编号分别是 `1,2,3`，一号和二号先单挑赢的人留在场上，输的人换另外一个在场下的人上场继续比。
现在题目中会给你一个整数数组 `num`，代表的是在擂台上同学的序号，现在请你编写代码判断 `num` 当中的序列是否合法。如果合法，则返回 `True`，否则返回 `False`。
输入格式 第一行，一行整数代表 `num`。
输出格式 `True` 或 `False`。
输入输出样例1输 入1 2 3输出 False
输入输出样例2输入 2 3 1输出 Trueimport java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
boolean flag = true;
int[] a = {1, 2};
while (n-- > 0) {
int x = scanner.nextInt();
if (x == a[0]) {
a[1] = 6 - a[0] - a[1];//2位置换另一个上
} else if (x == a[1]) {
a[0] = 6 - a[0] - a[1];//1位置换另一个上
} else {
flag = false;
}
}
if (flag) {
System.out.println("True");
} else {
System.out.println("False");
}
}
}15.3 数组的排列方式
小叶同学最近正在学习数组。在做题的时候，他发现了一道关于数组的题，却没有办法做出来，想让你帮他一下。
题目中首先会给你一个整数 `n`，代表 `1` 到 `n` 之间的数字，你可以无限使用 `1` 到 `n` 之间的数字。然后题目中会给你一个整数 `k`，需要你从这 `n` 个数字中取出 `k` 个数字，并按顺序排列起来，但是相邻的数字不能相同，小叶同学想知道这样有多少种排列方法，现在请你帮小叶编写代码，算出结果并输出。（结果对 `1000000007` 取模）
输入格式一行两个整数，`n` 和 `k`。
输出格式 一个整数。
输入输出样例1输入 2 2输出2
输入输出样例2输入1 5输出 `5`import java.util.Scanner;
public class Main {
private static final long MOD = 1000000007; // 定义常量MOD为固定值1000000007
public static void main(String[] args) {
Scanner sc = new Scanner(System.in); // 使用Scanner类从键盘获取输入
int n = sc.nextInt(); // 读取整数n
int m = sc.nextInt(); // 读取整数m
long[] dp = new long[m + 1];
dp[1] = m;
for (int i = 2; i <= m; i++) {
dp[i] = dp[i-1] * (m+i - 1) % MOD; // 更新dp[i]
}
System.out.println(dp[m]); // 输出结果
}
}15.4 小熊吃水果
小熊采摘回来了三种水果，他决定每天吃两个不同种类的水果各一个。在题目中会给你三个整数 `a,b,c`，分别代表三种水果的数量，现在请你编写代码，帮小熊算一下他最多能吃多少天？
输入格式 一行三个整数 `a,b,c`。
输出格式 一个整数。
输入输出样例1输入 `1 1 1输出`1
输入输出样例2输入 `5 6 8`输出 `9`package org.example;
import java.util.Arrays;
import java.util.Scanner;
import java.lang.Math;
public class BankRate {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int []arr = new int[3];
for (int i = 0; i < 3; i++) {
arr[i] = sc.nextInt();
}
Arrays.sort(arr);
int days = 0;
while (arr[1] > 0 && arr[2] > 0) {
arr[1]--;
arr[2]--;
Arrays.sort(arr);//总是从吃的最多的两种水果吃
days++;
}
System.out.println(days);
}
}
15.5数位组合之八
本关任务：函数 `fun` 的功能是：将两个两位数的正整数 `a、b` 合并形成一个整数放在 `c` 中。合并的方式是：将 `a` 数的十位和个位数依次放在 `c` 数的十位和千位上，`b` 数的十位和个位数依次放在 `c`数的百位和个位上。输入格式
整数 `a、b`。
输出格式
计算得到的结果`c`。
输入输出样例
输入1
45 12
输出1
5142import java.util.Scanner;
public class Main {
public static void main(String[] args) {
int a,b;
long c = 0l;
Scanner input = new Scanner(System.in);
a = input.nextInt();
b = input.nextInt();
c=fun(a,b,c);
System.out.println(c);
}
public static long fun(int a,int b,long c) {
int a1,a2,a3,a4;
a1 = a%10;//获取数的个位
a2 = a/10%10;//获取数的十位
a3 = b%10;
a4 = b/10%10;
c =(long) (a1*1000+a4*100+a2*10+a3);
return c;
}
} 15.6 判断质数
public boolean judgePrime(int num){
boolean flag=true;
if(num==1||(num)%2==0&&num!=2){
flag=false;
}else{
for(int j=3;j<Math.sqrt(num);j+=2){
if(num%j==0){
flag=false;
break;
}
}
}
return flag;
}15.7进制转换
将一个十进制数*n* 转换为26进制
用abcd....z表示0123...25(每位数字都用小写英文字母表示)
对于100%的测试点，保证0<*n* <1000
输入一个十进制数*n*
输出一个字符串*s* 表示用字符表示的26进制数
样例输入
26
样例输出
ba
26转换为26进制为10
1、0分别对应b、a
如：28为bc方法一
public static String decimalTo26Base(int n) {
StringBuilder sb = new StringBuilder();
while (n > 0) {
int remainder = (n - 1) % 26; // 计算余数 n,开头为a=0 n-1开头,开头为a=1
sb.insert(0, (char) ('a' + remainder)); // 将余数对应的字符插入到字符串的开头
n = (n - 1) / 26; // 更新n为商
}
return sb.toString();
}方法二
String result = "";
while (n > 0) {
int remainder = (n - 1) % 26; // 计算余数
result = (char) ('a' + remainder) + result; // 将余数对应的字符插入到结果字符串的开头
n = (n - 1) / 26; // 更新n为商
}方法三
Integer.toString(int i,int radix) //i为要转化的数,radix为要转换的进制15.6整数反转
public static int getRreverse(int x){
int res=0;
while(x!=0){
int temp=x%10;
res=res*10+temp;
x/=10
}
return res
}
//132
//temp=132%10=2 res=0=0+2 x=13
//temp=13%10=3 res=2*10+3 x=1
//temp=1%10=1 res=23*10+1 x=015.7取七去四
要求输出1∼n内含有7或者7的倍数的数字，但不含有4或者4的倍数的个数，例如（17，27，70，71…）。阿岳一看到这个题目，就觉得很兴奋，他觉得这是老师给他的一个挑战，也是一个展示自己才华的机会。
**输入**
一个整数 *n*
**输出**
一个整数 表示不大于*n* 的与7有关的数字但与4无关的个数。
**测试点数据规模与约定**
对于 100% 的数据，保证1≤*n*≤30000 。
样例输入
40
样例输出
6
提示
如 40 以内与 7 有关但与 4 无关的数为 7，17，21，27，35，37 共 6 个。import java.util.*;
public class q1539 {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int cnt=0;
for(int i=1;i<=n;i++) if(check(i)) cnt++;
System.out.println(cnt);
}
public static boolean check(int i) {
int t=i;
boolean flag7=false;
while(i!=0) {
if(i%10==4) return false;
if(i%10==7) flag7=true;
i=i/10;
}
return (t%7==0||flag7)&&t%4!=0;
}
}15.8 求距离
要求给出一个1−>n 的排列，然后有一次机会可以交换两个数的位置，求交换后最小值和最大值之间的最大距离是多少
**输入**
第一行 一个整数*n* 表示排列的元素个数
第二行 *n* 个整数 表示这个排列的顺序
**输出**
一个整数 表示最小值与最大值之间的最大距离
**测试点数据规模与约定**
对于100%的测试点，保证 1<*n* ≤100
样例输入
5
4 5 1 3 2
样例输出
3找到最大和最小的位置比较距离两端的差值
import java.util.*;
public class q1541 {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int[] arr=new int[n];
for(int i=0;i<n;i++) arr[i]=sc.nextInt();
int max=0,p=-1,min=110,q=-1;
for(int i=0;i<n;i++) {
if(max<arr[i]) {
max=arr[i];
p=i;
}
if(min>arr[i]) {
min=arr[i];
q=i;
}
}
int l=Math.min(p,q);
int r=Math.max(p,q);
System.out.println(Math.max(r, n-l-1));
}
}15.9 二进制与位运算
给你一个整数 *n* ，对于 0 <= *i* <= *n* 中的每个 *i* ，计算其二进制表示中 1 的个数 ，并按字符串形式输出一个长度为 *n + 1* 的数组作为答案。
**输入**
一个整数*n*
**输出**
一个字符串 表示答案数组
**测试点数据规模与约定**
对于100%的测试点，保证0<*n* <105
样例输入
2
样例输出
[0, 1, 1]//位运算x>>1等价于x=x/2
import java.util.*;
public class q1542 {
public static void main(String[] args) {
Scanner sc =new Scanner(System.in);
int n=sc.nextInt();
int[] ans=new int[n+1];
for(int i=0;i<=n;i++) ans[i]=bits(i);
System.out.println(Arrays.toString(ans));
}
public static int bits(int x) {
int cnt=0;
while(x!=0) {
if((x&1)==1)cnt++;
x/=2;
}
return cnt;
}
}15.10 第一重要极限
小岳是工科大一新生，正在学习高等数学里的"第一重要极限”，小岳突然心血来潮，想通过计算机程序求出形如:lim(x±∞) sin6x /2x的极限值
请你帮帮小岳，设计一个程序求出此极限
结果保留两位小数
输入
第一行 一个整数n 表示公式的数量
接下来n行 每行有两个字符串sinax bx 用单个空格分隔
输出
输出共有n行
每行包含一个保留两位的小数
测试点数据规模与约定
对于50%的测试点，保证a 、b 均为整数且a ,b >0
对于100%的测试点，保证公式有解且非±∞
样例输入
2
sin6x 2x
sin4x 2x
样例输出
3.00
2.00import java.util.*;
public class q1544 {
public static int value(String s) {
int ans=0;
int p=0;
if(s.charAt(0)=='s') p=3;
while(p<s.length()&&s.charAt(p)<='9'&&s.charAt(p)>='0') {
ans=ans*10+(int)(s.charAt(p)-'0');
p++;
}
if(ans==0) return 1;
return ans;
}
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
String s1,s2;
int n;
n=sc.nextInt();
while(n--!=0){
s1=sc.next();
s2=sc.next();
System.out.printf("%.2f\n",1.0*value(s1)/value(s2));
}
}
}
15.11 判断是否为素数
public boolean judgePrime(int num){
boolean flag=true;
if(num==1||(num)%2==0&&num!=2){
flag=false;
}else{
for(int j=3;j<Math.sqrt(num);j+=2){
if(num%j==0){
flag=false;
break;
}
}
}
return flag;
}15.12 a与b之间的素数
输入 2 个正整数 a 和 b，输出 a 与 b 范围内的所有素数。
测试输入：
1
25
预期输出：
1 2 3 5 7 11 13 17 19 23 package org.example;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int a = sc.nextInt();
int b = sc.nextInt();
for (int i = a; i <= b; i++) {
boolean c = true;
for (int j = 2; j <= i / 2; j++) {
if (i % j == 0 || i == j) {
c = false;
break;
}
}
if (c) {
System.out.print(i + " ");
}
}
}
}15.13 出去玩喽
题目描述
周末了，阿岳出去玩，从学校到曹魏古城还是坐校门口的公交车划算。
共有n 站路，阿岳刚上车时车上有m 个人，每到一站都有x 个人上车，y 个人下车，问这一路上公车上最多有多少人。
输入
第一行 两个整数n ，m 分别表示站点个数(不包括起点站)和初始人数
接下来n 行 每行有两个整数x，y 分别表示第i 个站点上车的人数与下车的人数(0<i ≤n )
输出
一个整数 表示公交车上最多的人数
测试点数据规模与约定
对于100%的测试点，保证0<n ≤20，0≤m ,x ,y ≤10
样例输入
2 3
5 2
3 5
样例输出
6
提示
阿岳和司机不是人//方法1
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int num = sc.nextInt();
int max = 0;
for (int i = 0; i < n; i++) {
max = Math.max(max,num);//先更新max,防止出错
num += sc.nextInt();
num -= sc.nextInt();
}
System.out.println(max);
}
}
//方法1 改进
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); // 站点个数
int m = sc.nextInt(); // 初始人数
int maxPassengers = m; // 最多乘客数
for (int i = 0; i < n; i++) {
int x = sc.nextInt(); // 上车人数
int y = sc.nextInt(); // 下车人数
m = m - y + x; // 更新当前乘客数
maxPassengers = Math.max(maxPassengers, m); // 更新最多乘客数
}
System.out.println(maxPassengers);
}
}
//方法2
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[][] arr = new int[n][2];
int max = m;
for (int i = 0; i < n; i++) {
arr[i][0] = sc.nextInt();
arr[i][1] = sc.nextInt();
}
for (int i = 0; i < n; i++) {
m = m + arr[i][0] - arr[i][1];
max = Math.max(max, m);
}
System.out.println(max);
}
}15.4 前n项和与积
数学是任何工科的基础，因此，扎实的数学功底至关重要。很多算法都体现着数学思维，请你们仔细感悟。
现在给你n个数据a1，a2，a3，a4，a5，an，请你求出他们的前n项和与前n项积
共一行包含n个数据0<=n<=10,用空格分开每个数据aj，0<=ai<=100
第一行输出s1,s2,s3,sn的值，第二行输出前n项积
输入数据
1 2 7
输出数据
1 3 10
1 2 14package org.example;
import java.util.Scanner;
import java.util.Scanner;
public class Main{
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 读取n个数
String[] inputs = scanner.nextLine().split(" ");
int n = inputs.length;
// 将字符串数组转换为整数数组
int[] nums = new int[n];
for (int i = 0; i < n; i++) {
nums[i] = Integer.parseInt(inputs[i]);
}
// 计算前n项和
int sum = 0;
for (int i = 0; i < n; i++) {
sum += nums[i];
System.out.print(sum + " ");
}
System.out.println();
// 计算前n项积
int product = 1;
for (int i = 0; i < n; i++) {
product *= nums[i];
System.out.print(product + " ");
}
}
}import java.util.Scanner;
import java.util.ArrayList;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
ArrayList<Integer> list = new ArrayList<>();
int sum = 0;
int mul = 1;
while (scanner.hasNextInt()) {
int temp = scanner.nextInt();
if (temp == -1) {
break; // 如果输入-1，则结束输入
}
list.add(temp);
}
for (int a : list) {
sum += a;
System.out.print(sum + " ");
}
System.out.println();
for (int b : list) {
mul *= b;
System.out.print(mul + " ");
}
}
}
// IntelliJ IDEA的控制台不支持直接输入结束标记以表示输入的结束15.5 求阶乘
import java.math.BigInteger;
import java.util.ArrayList;
public class doFactorial {
public static void main(String[] args) {
int number=5;
System.out.println("方法一算得"+number+"的阶乘为："+Wayone(number));
System.out.println("方法二算得"+number+"的阶乘为："+Waytwo(number));
System.out.println("方法三算得"+number+"的阶乘为："+Waythree(number));
System.out.println("方法四算得"+number+"的阶乘为："+Wayfour(number));//方法四可以传入一个较大得number值
}
/**
* 普通的循环方法求阶乘
* @param num
* @return
*/
public static int Wayone(int num) {
int sum=1;
if(num<0) {
throw new IllegalArgumentException("需要计算的参数必须为正数！");//抛出不合理参数异常
}
for(int i=1;i<=num;i++) {
sum*=i;
}
return sum;
}
/**
* 运用递归算法求阶乘
* @param num
* @return
*/
public static int Waytwo(int num) {
int sum=1;
if(num<0) {
throw new IllegalArgumentException("需要计算的参数必须为正数！");//抛出不合理参数异常
}
if(num==1) {
return 1;//跳出循环
}else {
sum=num*Waytwo(num-1);//递归
return sum;
}
}
/**
* 数组添加计算阶乘
* @param num
* @return
*/
public static long Waythree(int num) {
long []arr=new long[21];
arr[0]=1;
int last=0;
if(num>=arr.length) {
throw new IllegalArgumentException("传入的值太大了！");//抛出不合理参数异常
}
if(num<0) {
throw new IllegalArgumentException("需要计算的参数必须为正数！");//抛出不合理参数异常
}
while(last<num) {
arr[last+1]=arr[last]*(last+1);
last++;
}
return arr[num];
}
/**
* 用BigInteger类计算阶乘1
* @param num
* @return
*/
public static synchronized BigInteger Wayfour(int num) {
ArrayList list=new ArrayList();
list.add(BigInteger.valueOf(1));
for(int i=list.size();i<=num;i++) {
BigInteger lastfact=(BigInteger) list.get(i-1);
BigInteger nextfact=lastfact.multiply(BigInteger.valueOf(i));
list.add(nextfact);
}
return (BigInteger) list.get(num);
}
/**
* 用BigInteger类计算阶乘2
* @param num
* @return
*/
public static BigInteger wayfive(int num) {
BigInteger temp = new BigInteger("1");
BigInteger temp1=new BigInteger("1");
BigInteger temp2=new BigInteger("1");
for (int j = 1; j <=num ; j++) {
temp = temp.multiply(temp1);
temp1=temp1.add(temp2);
}
return temp；
}15.6 求阶乘和(蓝桥杯2023javaB组第1题)
A、阶乘求和
【问题描述】
令 S = 1! + 2! + 3! + ... + 202320232023! ，求 S 的末尾 9 位数字。
提示：答案首位不为 0 。import java.math.BigInteger;
public class Main {
public static void main(String[] args) {
BigInteger temp = new BigInteger("1");
BigInteger temp1 =new BigInteger("1");
BigInteger temp2 =new BigInteger("1");
BigInteger sum = new BigInteger("0");
for (int j = 1; j <=60 ; j++) {
temp = temp.multiply(temp1);
temp1=temp1.add(temp2);
sum=sum.add(temp);//这样不用每次计算每个数的阶乘
}
System.out.println(sum.remainder(new BigInteger("1000000000")));
}
}
当加到40多的阶乘时，这个阶乘和后面的9位数就不会发生改变了。
420940313
15.7 幸运数字(蓝桥杯2023javaB组第2题)
【问题描述】
哈沙德数是指在某个固定的进位制当中，可以被各位数字之和整除的正整 数。例如 126 是十进制下的一个哈沙德数，因为 (126) 10 mod (1+2+6) = 0 ； 126 也是八进制下的哈沙德数，因为 (126) 10 = (176) 8 ， (126) 10 mod (1 + 7 + 6) = 0 ； 同时 126 也是 16 进制下的哈沙德数，因为 (126) 10 = (7 e ) 16 ， (126) 10 mod (7 + e ) = 0 。小蓝认为，如果一个整数在二进制、八进制、十进制、十六进制下均为 哈沙德数，那么这个数字就是幸运数字，第 1 至第 10 个幸运数字的十进制表示 为：1 , 2 , 4 , 6 , 8 , 40 , 48 , 72 , 120 , 126 . . . 。现在他想知道第 2023 个幸运数 字是多少？你只需要告诉小蓝这个整数的十进制表示即可。//方法一
public class {
public static void main(String[] args) {
int j=0;
for (int i=1;i<10000000;i++){
if (BaseConversion(i)){
j++;
if (j==2023){
System.out.println(i);//215040
break;
}
}
}
}
public static boolean BaseConversion(int n){
//十进制
int sum=0;
int x=n;
while (x!=0){
sum+=(x%10);
x/=10;
}
if (n%sum!=0)
return false;
//二进制
sum=0;
x=n;
while (x!=0){
sum+=(x%2);
x/=2;
}
if (n%sum!=0)
return false;
//八进制
sum=0;
x=n;
while (x!=0){
sum+=(x%8);
x/=8;
}
if (n%sum!=0)
return false;
//十六进制
int[] arr={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
sum=0;
x=n;
while (x!=0){
sum+=(arr[x%16]);
x/=16;
}
if (n%sum!=0)
return false;
return true;
}
}
//方法二 自己写的，可以通过
import java.math.BigInteger;
public class Main {
public static void main(String[] args) {
int i = 1;
int j = 0;
while (true) {
if (ifhsd(i)) {
j++;
}
if (j == 2023) {
System.out.println(i);
break;
}
i++;
}
}
public static boolean ifhsd(int a) {
Integer A = new Integer(a);
char A1[] = Integer.toString(A, 2).toCharArray();
int sum1 = 0;
for (int i = 0; i < A1.length; i++) {
if ('0' < A1[i] && A1[i] <= '9') {
sum1 = sum1 + (int) (A1[i]-'0');
}
}
Integer B = new Integer(a);
char A2[] = Integer.toString(B, 8).toCharArray();
int sum2 = 0;
for (int i = 0; i < A2.length; i++) {
sum2 = sum2 + (int) (A2[i]-'0');
}
Integer C = new Integer(a);
char A3[] = Integer.toString(C, 10).toCharArray();
int sum3 = 0;
for (int i = 0; i < A3.length; i++) {
sum3 = sum3 + (int) (A3[i]-'0');
}
Integer D = new Integer(a);
char A4[] = Integer.toString(D, 16).toCharArray();
int sum4 = 0;
for (int i = 0; i < A4.length; i++) {
if ('0' < A4[i] && A4[i] <= '9') {
sum4 = sum4 + (int) (A4[i]-'0');
} else if ('a' <= A4[i] && A4[i] <= 'z') {
sum4 = sum4 + 10 + (A4[i] - 'a');
}
}
if (sum1 != 0 && sum2 != 0 && sum3 != 0 && sum4 != 0 && a % sum1 == 0 && a % sum2 == 0 && a % sum3 == 0
&& a % sum4 == 0) {
return true;
} else {
return false;
}
}
}
//方法三
public class 试题B_幸运数字 {
//求一个数字字符串的数位之和
public static int getSum(String s) {
int sum=0;
for(int i=0;i<s.length();i++) {
if(s.charAt(i)>='a'&&s.charAt(i)<='f') //如果是a-f
sum+=s.charAt(i)-'a'+10;
else //如果是数字
sum+=s.charAt(i)-'0';
}
return sum;
}
public static void main(String[] args) {
int count=0;
for(int i=1;i<1000000;i++) {
String a2=Integer.toBinaryString(i); //转为二进制
String a8=Integer.toOctalString(i); //转为八进制
String a16=Integer.toHexString(i); //转为十六进制
if(i%getSum(a2)==0&&i%getSum(a8)==0&&i%getSum(a16)==0&&i%getSum(""+i)==0) {
count++;
if(count==2023) {
System.out.println("第 2023 个幸运数字是:"+i);
break;
}
}
}
}
}15.8 大数取绝对值
//方法一
import java.util.*;
import java.math.BigInteger;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String s = scanner.next();
BigInteger bigInteger =new BigInteger(s);
if(s.contains("-")) {
System.out.println(bigInteger.negate());
}else {
System.out.println(bigInteger);
}
}
}
//方法二
import java.util.*;
import java.math.BigInteger;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String s = ""+scanner.next();
if(s.contains("-")) {
System.out.println(s.substring(1,s.length()-1));
}else {
System.out.println(s);
}
}
}
//方法三
import java.util.*;
import java.math.BigInteger;
public class Main {
public static void main(String[] args) {
System.out.println(new Scanner(System.in).nextBigInteger().abs());
}
}15.9 星期计算
【问题描述】
已知今天是星期六，请问20^22天后是星期几？注意用数字 1 到 7 表示星期一到星期日。
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。//BigInteger暴力法1
import java.math.BigInteger;
public class A {
public static void main(String[] args) {
//因为是结果填空题，不需要考虑运行时间，直接用BigInteger类
//这里BigInteger的构造方法只允许传字符串
BigInteger bi = new BigInteger("20");
//20的22次的计算结果
BigInteger res = new BigInteger("1");
for(int i = 0;i < 22;i++) { //乘以22次
//BigInteger是一个类 加减乘除和取模等运算是调用BigInteger的方法
res = res.multiply(bi);
//这里确保答案准确可一将每次*20后的结果输出
System.out.println(i+1 + "次方的结果： "+res.toString());
}
System.out.println("==================");
System.out.println(res.toString());
System.out.println("==================");
BigInteger mo = new BigInteger("7");
//一周7天 将res%7
res = res.remainder(mo);
//计算出是1 然后在周六的基础上+1 这道题的答案就是7
System.out.println(res.toString());
}
}
//BigInteger暴力法2
import java.math.BigInteger;
public class Main {
public static void main(String[] args) {
BigInteger bigInteger = BigInteger.valueOf(20).pow(22).mod(BigInteger.valueOf(7));
int result = (6 + bigInteger.intValue()) % 7;
System.out.println(result == 0 ? 7 : result);
}
}
方法二：另外一般这种 “特别大的数 ”取模运算 有普通公式
即：一般取模方式： 乘积后%取模
防止溢出： (ab)%p = ((a%p)(b%p))%p
对应这道题就是 ( (20%7)* (20%7)* (20%7)*... (20%7)* (20%7) ) % 7 = (6*6*6*...6*6)%7
转化为6的22次方模7 -->在将6*6=36看作公式的a
可得( (36%7)* (36%7)* (36%7)*... (36%7)* (36%7) ) % 7 = 1的11次方模7 最终就是 1
然后在周六的基础上+1 这道题的答案就是7
补充：取模运算
(a + b) % p = (a%p + b%p) %p
(a - b) % p = ((a%p - b%p) + p) %p
(a * b) % p = (a%p)*(b%p) %p15.10 最少刷题数问题
小蓝老师教的编程课有N名学生，编号依次是1．．．N。第i号学生这学期刷题的数量是Ai。
对于每一名学生，请你计算他至少还要再刷多少道题，才能使得全班刷题比他多的学生数不 超过刷题比他少的学生数。【输入格式】
第一行包含一个正整数N。
第二行包含N个整数：A1，A2，A3，．．．，AN．【输出格式】
输出N个整数，依次表示第1．．．N号学生分别至少还要再刷多少道题。【样例输入】
5
12 10 15 20 6
【样例输出】
0 3 0 0 7
【评测用例规模与约定】
对于30％的数据，1≤N≤1000，0≤Ai≤1000．
对于100％的数据，1≤N≤100000，0≤Ai≤100000//分情况考虑：奇数情况下，超过中间值才能满足全班刷题比他多的学生数不超过刷题比他少的学生数；偶数情况下需要等于中间偏大的值就可以满足条件。
public static void Java_B_D() {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int[] nums = new int[n];
int[] count = new int[n];
for (int i = 0; i < nums.length; i++) {
// 输入的一个数组，并把这个数组复制下来
nums[i] = scan.nextInt();
count[i] = nums[i];
}
// 对数组排一下序方便找到较中间的那个数
Arrays.sort(count);
// 找到中间的索引
int index = 0;
// 分情况讨论值
if (n % 2 == 0) {
index = n / 2 + 1;
} else {
index = n / 2;
}
// 找到中间值
int middle = count[index];
for (int i = 0; i < n; i++) {
// 判断得到最终结果
if (nums[i] < middle) {
System.out.print(middle - nums[i] + 1);
System.out.print(" ");
} else {
System.out.print(0);
System.out.print(" ");
}
}
}15.11 求阶乘问题
满足N！的末尾恰好有K个0的最小的N是多少？如果这样的N不存在输出—1。
【输入格式】 一个整数K。 【输出格式】 一个整数代表答案。 【样例输入】 2 【样例输出】 10public static void Java_B_E() {
Scanner sc = new Scanner(System.in);
long k = sc.nextLong();
long count; // 含有5的个数 也是阶乘后0的个数
long a = 5; // 直接从5的阶乘(120)开始判断
while (true) {
long tempA = a;
count = 0;
while (tempA > 0) {
tempA /= 5;
count += tempA;
}
if (count < k) {
a += 5;
} else if (count == k) {
System.out.println(a);
break;
} else {
System.out.println(-1);
break;
}
}
}设计一个算法，算出 n 阶乘有多少个尾随零。力扣面试题16.05阶乘尾数/**
* 解题思路：
* 1、那么 n 过大时，从 1 遍历到 n, 那么会超时,因此我们修改下规律
*
* n! = 1 * 2 * 3 * 4 * (1 * 5) * ... * (2 * 5) * ... * (3 * 5) ...
* 我们发现，
* 每隔 5 个数就会出现 一个 5，因此我们只需要通过 n / 5 来计算存在存在多少个 5 个数，那么就对应的存在多少个 5
* 但是，我们也会发现
* 每隔 25 个数会出现 一个 25， 而 25 存在 两个 5，我们上面只计算了 25 的一个 5，因此我们需要 n / 25 来计算存在多少个 25，加上它遗漏的 5
* 同时，我们还会发现
* 每隔 125 个数会出现一个 125，而 125 存在 三个 5，我们上面只计算了 125 的两个 5，因此我们需要 n / 125 来计算存在多少个 125，加上它遗漏的 5
* ...
*
* 因此我们 count = n / 5 + n / 25 + n / 125 + ...
* 最终分母可能过大溢出，上面的式子可以进行转换
*
* count = n / 5 + n / 5 / 5 + n / 5 / 5 / 5 + ...
* 因此，我们这样进行循环
* n /= 5;
* count += n;
* 这样，第一次加上的就是 每隔 5 个数的 5 的个数，第二次加上的就是 每隔 25 个数的 5 的个数 ...
class Solution {
public int trailingZeroes(int n) {
int count = 0;
while(n >= 5){
n /= 5;
count += n;
}
return count;
}
}