回文串
9. 回文数
给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。
回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
- 例如，
121是回文，而123不是。
示例 1：
输入：x = 121
输出：true
示例 2：
输入：x = -121
输出：false
解释：从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
示例 3：
输入：x = 10
输出：false
解释：从右向左读, 为 01 。因此它不是一个回文数。
- 如果是负数则一定不是回文数，直接返回 false
- 如果是正数，则将其倒序数值计算出来，然后比较和原数值是否相等
- 如果是回文数则相等返回 true，如果不是则不相等 false
- 比如 123 的倒序 321，不相等；121 的倒序 121，相等
class Solution {
public boolean isPalindrome(int x) {
if(x < 0) return false;
String s = x + "";
StringBuilder sb = new StringBuilder(s);
return sb.reverse().toString().equals(s);
}
}
class Solution {
public boolean isPalindrome(int x) {
if(x < 0){
return false;
}
int reverse = 0; // 存储翻转后数字
int num = x;
while(num > 0){
int last_num = num % 10;
num = num / 10;
reverse = reverse * 10 + last_num;
}
return reverse == x;
}
}
最小的回文数
现给你一个正整数N，请你找到比N大的最小的那个回文数P。
样例输入
44
3
175
样例输出
55
4
181
866. 回文素数
求出大于或等于 N 的最小回文素数。
回顾一下，如果一个数大于 1，且其因数只有 1 和它自身，那么这个数是素数。
例如，2，3，5，7，11 以及 13 是素数。
回顾一下，如果一个数从左往右读与从右往左读是一样的，那么这个数是回文数。例如，12321 是回文数。
示例 1：
输入：6
输出：7
示例 2：
输入：8
输出：11
示例 3：
输入：13
输出：101
564. 寻找最近的回文数 - 力扣（Leetcode）
125. 验证回文串
如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。
字母和数字都属于字母数字字符。
给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 。
示例 1：
输入: s = "A man, a plan, a canal: Panama"
输出：true
解释："amanaplanacanalpanama" 是回文串。
示例 2：
输入：s = "race a car"
输出：false
解释："raceacar" 不是回文串。
示例 3：
输入：s = " "
输出：true
解释：在移除非字母数字字符之后，s 是一个空字符串 "" 。
由于空字符串正着反着读都一样，所以是回文串。
Character.isLetterOrDigit(int codePoint) 确定指定字符是字母还是数字。如果 isLetter(codePoint) 或 isDigit(codePoint) 对字符返回 true，则认为该字符是字母或数字。
// 两端向中心的双指针算法
class Solution {
public boolean isPalindrome(String s) {
if(s == "" || s.length() == 0){
return true;
}
StringBuilder sb = new StringBuilder();
for(int i = 0; i < s.length(); i++){
char c = s.charAt(i);
if(Character.isLetterOrDigit(c)) {
sb.append(Character.toLowerCase(c));
}
}
s = sb.toString();
int left = 0;
int right = s.length() - 1;
while(left < right){
if(s.charAt(left) != s.charAt(right)){
return false;
}
left++;
right--;
}
return true;
}
}
680. 验证回文串 II
给你一个字符串 s，最多 可以从中删除一个字符。
请你判断 s 是否能成为回文字符串：如果能，返回 true ；否则，返回 false 。
示例 1：
输入：s = "aba"
输出：true
示例 2：
输入：s = "abca"
输出：true
解释：你可以删除字符 'c' 。
示例 3：
输入：s = "abc"
输出：false
class Solution {
public boolean validPalindrome(String s) {
int left = 0;
int right = s.length() - 1;
while(left < right){
if(s.charAt(left) != s.charAt(right)){
return isPalindrome(s, left + 1, right)|| isPalindrome(s, left, right - 1);
}
left++;
right--;
}
return true;
}
public boolean isPalindrome(String s, int left, int right) {
while(left < right){
if(s.charAt(left) != s.charAt(right)){
return false;
}
left++;
right--;
}
return true;
}
}
美团3.18-笔试-回文串
现在小美获得了一个字符串。小美想要使得这个字符串是回文串。小美找到了你。你可以将字符串中至多两个位置改为任意小写英文字符 ’a’ - ‘z’。你的任务是帮助小美在当前制约下，获得字典序最小的回文字符串。
数据保证能在题目限制下形成回文字符串。
输入描述
一行，一个字符串。字符串中仅由小写英文字符构成。
保证字符串不会是空字符串。
字符串长度介于 [ 1 , 100000 ] 之间。
输出描述
一行，一个在题目条件限制下所可以获得的字典序最小的回文字符串。
样例输入: acca
样例输出: aaaa
(26条消息) 美团笔试-3.18_犬兄的海角的博客-CSDN博客
5. 最长回文子串
给你一个字符串 s，找到 s 中最长的回文子串。
如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
亚信安全2024提前批：最长回文子字符串
求最长回文子字符串 （多组回文长度相同则返回第一组），双指针实现
输入：s = “sjdaiwasdesdsfsdsedsaw1h3u238dsahji1”
输出：”wasdesdsfsdsedsaw”
示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd"
输出："bb"
方法一：动态规划
回文天然具有「状态转移」性质：一个长度大于 2 的回文去掉头尾字符以后，剩下的部分依然是回文。反之，不是回文。「动态规划」的方法根据这样的性质得到。
dp[i][j] 表示：子串 s[i..j] 是否为回文子串，这里子串 s[i..j] 定义为左闭右闭区间，即可以取到 s[i] 和 s[j]。
根据头尾字符是否相等，需要分类讨论：
dp[i][j] = (s[i] == s[j]) and (j - i < 3 || dp[i + 1][j - 1])
- 当只有一个字符时，比如 a 自然是一个回文串。
- 当有两个字符时，首尾相等，则必是一个回文串。
- 当有三个字符时，首尾相等，则必是一个回文串。
- 当有三个以上字符时，去掉首尾再判断剩下串是否是回文
class Solution {
public String longestPalindrome(String s) {
int n = s.length();
// dp[i][j] 表示：子串 s[i..j] 是否为回文子串
boolean[][] dp = new boolean[n][n];
//记录回文长度和起始位置
int maxLen = 1;
int begin = 0;
for (int j = 0; j < n; j++) {
for (int i = 0; i <= j; i++) {
//dp[i][j] = (s.charAt(i) == s.charAt(j)) && (j - i < 3 || dp[i + 1][j - 1]);
if (s.charAt(i) == s.charAt(j) && (j - i < 3 || dp[i + 1][j - 1])) {
dp[i][j] = true;
}
//计算最长回文串,只要 dp[i][j] == true 成立，就表示子串 s[i..j] 是回文
//对比所有的回文串，取出长度最大的，回文串的起始位置
if(dp[i][j] && j - i + 1 > maxLen){
maxLen = j - i + 1;
begin = i;
}
}
}
return s.substring(begin, begin+maxLen);
}
}
class Solution {
public String longestPalindrome(String s) {
int n = s.length();
if(n < 2) {
return s;
}
boolean[][] dp = new boolean[n][n];
char[] charArr = s.toCharArray();
// 初始化：所有长度为 1 的子串都是回文串
for(int i = 0; i < n; i++){
dp[i][i] = true;
}
//记录回文长度和起始位置
int maxLen = 1;
int begin = 0;
// 枚举子串长度
for(int j = 1; j < n; j++){
for(int i = 0; i < j; i++){
if(charArr[i] == charArr[j]){
//首尾相等且长度为2的是回文
if(j - i < 3){
dp[i][j] = true;
} else{
//首尾相等且长度大于2的，去掉首尾再判断
dp[i][j] = dp[i + 1][j - 1];
}
} else{
//首尾不等的串不是回文
dp[i][j] = false;
}
//计算最长回文串,只要 dp[i][j] == true 成立，就表示子串 s[i..j] 是回文
//对比所有的回文串，取出长度最大的，回文串的起始位置
if(dp[i][j] && j - i + 1 > maxLen){
maxLen = j - i + 1;
begin = i;
}
}
}
return s.substring(begin, begin+maxLen);
}
}
方法二：中心扩散法
找回文串的难点在于，回文串的的长度可能是奇数也可能是偶数，解决该问题的核心是从中心向两端扩散的双指针技巧。
如果回文串的长度为奇数，则它有一个中心字符；如果回文串的长度为偶数，则可以认为它有两个中心字符。所以我们可以先实现这样一个函数：
// 在 s 中寻找以 s[l] 和 s[r] 为中心的最长回文串
String palindrome(String s, int l, int r) {
// 防止索引越界
while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
// 双指针，向两边展开
l--;
r++;
}
// 返回以 s[l] 和 s[r] 为中心的最长回文串
return s.substring(l + 1, r);
}
如果输入相同的 l 和 r，就相当于寻找长度为奇数的回文串，
如果输入相邻的 l 和 r，则相当于寻找长度为偶数的回文串。
那么回到最长回文串的问题，解法的大致思路就是：
String longestPalindrome(String s) {
String res = "";
for (int i = 0; i < s.length(); i++) {
// 以 s[i] 为中心的最长回文子串
String s1 = palindrome(s, i, i);
// 以 s[i] 和 s[i+1] 为中心的最长回文子串
String s2 = palindrome(s, i, i + 1);
// res = longest(res, s1, s2)
res = res.length() > s1.length() ? res : s1;
res = res.length() > s2.length() ? res : s2;
}
return res;
}
最终代码
class Solution {
public String longestPalindrome(String s) {
String res = "";
for (int i = 0; i < s.length(); i++) {
// 以 s[i] 为中心的最长回文子串
String s1 = palindrome(s, i, i);
// 以 s[i] 和 s[i+1] 为中心的最长回文子串
String s2 = palindrome(s, i, i + 1);
// res = longest(res, s1, s2)
res = res.length() > s1.length() ? res : s1;
res = res.length() > s2.length() ? res : s2;
}
return res;
}
// 在 s 中寻找以 s[l] 和 s[r] 为中心的最长回文串
String palindrome(String s, int l, int r) {
// 防止索引越界
while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
// 向两边展开
l--;
r++;
}
// 返回以 s[l] 和 s[r] 为中心的最长回文串
return s.substring(l + 1, r);
}
}
647. 回文子串
给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
示例 1：
输入：s = "abc"
输出：3
解释：三个回文子串: "a", "b", "c"
示例 2：
输入：s = "aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"
方法一：动态规划
class Solution {
public int countSubstrings(String s) {
int n = s.length();
boolean[][] dp = new boolean[n][n];
int count = 0;
for(int j = 0; j < n; j++){
for(int i = 0; i <= j; i++){
if(s.charAt(i) == s.charAt(j) && (j - i < 3 || dp[i + 1][j - 1])){
dp[i][j] = true;
count++;
}
}
}
return count;
}
}
方法二：中心扩散法
class Solution {
public int countSubstrings(String s) {
int a = 0;
int b = 0;
for(int i = 0; i < s.length(); i++){
//奇数中心点
a += parlinDrome(s, i, i);
//偶数中心点
b += parlinDrome(s, i, i+1);
}
return a+b;
}
public int parlinDrome(String s, int l, int r){
int count = 0;
while(l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)){
l--;
r++;
count++;
}
return count;
}
}
// 中心点有 2 * len - 1 个，分别是 len 个单字符和 len - 1 个双字符。
class Solution {
public int countSubstrings(String s) {
int ans = 0;
for (int center = 0; center < 2 * s.length() - 1; center++) {
int left = center / 2;
int right = left + center % 2;
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
ans++;
left--;
right++;
}
}
return ans;
}
}
516. 最长回文子序列
给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
示例 1：
输入：s = "bbbab"
输出：4
解释：一个可能的最长回文子序列为 "bbbb" 。
示例 2：
输入：s = "cbbd"
输出：2
解释：一个可能的最长回文子序列为 "bb" 。
dp[i][j] 表示 子串 s[i..j] ，最长的回文序列长度是多少。
- 如果 s 的第 i 个字符和第 j 个字符相同的话
dp[i][j] = dp[i + 1][j - 1] + 2
- 如果 s 的第 i 个字符和第 j 个字符不同的话
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
然后注意遍历顺序，i 从最后一个字符开始往前遍历，j 从 i + 1 开始往后遍历，这样可以保证每个子问题都已经算好了。
初始化dp[i][i] = 1 单个字符的最长回文序列是 1 ，结果dp[0][n - 1]
class Solution {
public int longestPalindromeSubseq(String s) {
int n = s.length();
// dp 数组全部初始化为 0
int[][] dp = new int[n][n];
// base case
for (int i = 0; i < n; i++) {
dp[i][i] = 1;
}
// 反着遍历保证正确的状态转移
for (int i = n - 1; i >= 0; i--) {
for (int j = i + 1; j < n; 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], dp[i][j - 1]);
}
}
}
// 整个 s 的最长回文子串长度
return dp[0][n - 1];
}
}
// 降维dp
class Solution {
public int longestPalindromeSubseq(String s) {
int n = s.length();
int[] dp = new int[n];
for (int i = 0; i < n; i++){
dp[i] = 1;
}
for (int i = n - 1; i >= 0; i--) {
int pre = 0;
for (int j = i + 1; j < n; j++) {
int temp = dp[j];
if (s.charAt(i) == s.charAt(j)){
dp[j] = pre + 2;
}
else {
dp[j] = Math.max(dp[j], dp[j - 1]);
}
pre = temp;
}
}
return dp[n - 1];
}
}
约瑟夫环
剑指 Offer 62. 圆圈中最后剩下的数字
0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字。
例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。
示例 1：
输入: n = 5, m = 3
输出: 3
示例 2：
输入: n = 10, m = 17
输出: 2
这个问题是以弗拉维奥·约瑟夫命名的，称为“约瑟夫环”问题，可使用 动态规划 解决。
最容易想到的方法是：构建一个长度为 n 的链表，各节点值为对应的顺序索引；每轮删除第 m 个节点，直至链表长度为 1 时结束，返回最后剩余节点的值即可。模拟法需要循环删除 n−1 轮，每轮在链表中寻找删除节点需要 m 次访问操作（链表线性遍历），因此总体时间复杂度为 O(nm) 。根据题目给定的 m,n 取值范围，可知此时间复杂度是不可接受的。
动态规划解法
设 f(n,m) 表示在 n 个数字(0～n-1)中不断删除第 m 个数字最后剩下的数字。删除一个数字后剩下了 n-1 个数字，那么再次删除就是在 n-1 个数字中删除第 m 个数字，可以表示为 f(n-1,m)。
但实际上直接这么表示是不对的。因为f(n,m)表示的是从区间[0~n-1]不断进行删除操作，被删除的元素是k=(m-1)%n，而下一次删除时，起点是 k+1（即m%n） ，区间不再满足上述要求，因此从第二步不断删除的结果可以表示为f'(n-1,m)。则有：f(n,m) = f'(n-1,m)
现在就要想办法找到 f'(n-1,m)和f(n- 1, m)之间的关系。则二者操作的区间表示如下:
f'(n-1,m)表示序列: k+1 k+2 k+3 ... n-1 0 1 ... k-1
f(n-1,m) 表示序列: 0 1 2 ... n-k-2 n-k-1 n-k ... n-2
由此推出 f'(n-1,m)=(f(n-1,m)+k+1)%n
化简：
因为
f'(n-1,m)=(f(n-1,m)+k+1)%n
k+1= m%n
f(n,m) = f'(n-1,m)
所以
f(n-1,m)=[f(n-1,m)+m]%n
由此可知 f(n,m) 可由 f(n-1,m) 得到，f(n-1,m) 可由 f(n-2,m) 得到，……，f(2,m) 可由 f(1,m) 得到；因此，若给定 f(1,m) 的值，就可以递推至任意 f(n,m) 。而 f(1,m) = 0 恒成立。得到如下递归关系：
动态规划解析：
状态定义： 设「i,m问题」的解为 dp[i]；
转移方程： 通过以下公式可从 dp[i−1] 递推得到 dp[i] = (dp[i−1] + m) % i；
初始状态：「1,m 问题」的解恒为 0 ，即 dp[1] = 0；
返回值： 返回「n,m 问题」的解 dp[n] ；
class Solution {
public int lastRemaining(int n, int m) {
int dp[] = new int[n+1];
dp[1] = 0;
for(int i = 2; i <= n; i++){
dp[i] = (dp[i-1] + m) % i;
}
return dp[n];
}
}
//优化
//根据状态转移方程的递推特性，无需建立状态列表 dp ，而使用一个变量 x 执行状态转移即可。
class Solution {
public int lastRemaining(int n, int m) {
int x = 0;
for (int i = 2; i <= n; i++) {
x = (x + m) % i;
}
return x;
}
}
1823. 找出游戏的获胜者
共有 n 名小伙伴一起做游戏。小伙伴们围成一圈，按 顺时针顺序 从 1 到 n 编号。确切地说，从第 i 名小伙伴顺时针移动一位会到达第 (i+1) 名小伙伴的位置，其中 1 <= i < n ，从第 n 名小伙伴顺时针移动一位会回到第 1 名小伙伴的位置。
游戏遵循如下规则：
- 从第
1名小伙伴所在位置 开始 。 - 沿着顺时针方向数
k名小伙伴，计数时需要 包含 起始时的那位小伙伴。逐个绕圈进行计数，一些小伙伴可能会被数过不止一次。 - 你数到的最后一名小伙伴需要离开圈子，并视作输掉游戏。
- 如果圈子中仍然有不止一名小伙伴，从刚刚输掉的小伙伴的 顺时针下一位 小伙伴 开始，回到步骤
2继续执行。 - 否则，圈子中最后一名小伙伴赢得游戏。
给你参与游戏的小伙伴总数 n ，和一个整数 k ，返回游戏的获胜者。
亚信安全2024提前批：约瑟夫环
n个人围成一圈，第一个人从1开始报数，报m的将被杀掉，下一个人接着从1开始报，如此反复，最后剩下一个，求最后胜利者。
示例 1：
输入：n = 10, k = 3
输出：4
1 2 3 4 5 6 7 8 9 10
1 2 4 5 6 7 8 9 10
1 2 4 5 7 8 9 10
1 2 4 5 7 8 10
1 4 5 7 8 10
1 4 5 8 10
4 5 8 10
4 5 10
4 10
4
示例 2：
输入：n = 6, k = 5
输出：1
1 2 3 4 5 6
1 2 3 4 6
1 2 3 6
1 2 3
1 3
1
剑指 Offer 62. 圆圈中最后剩下的数字是：从0～n中，选取第m位淘汰（删除后从下一个数字开始计数）
例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。
本题是从1～n，选取第m位淘汰（删除后从下一个数字开始计数）
例如，1、2、3、4、5这5个数字组成一个圆圈，从数字1开始每次删除第3个数字，则删除的前4个数字依次是3、1、5、2，因此最后剩下的数字是4。
2、0、4、1 剩下的数字是3
3、1、5、2 剩下的数字是4
每次删除的数都比之前题大一位，所以只需要在剑指 Offer 62. 圆圈中最后剩下的数字的结果上+1即可
class Solution {
public int findTheWinner(int n, int k) {
int[] dp = new int[n+1];
dp[1] = 0;
for(int i = 2; i <= n; i++){
dp[i] = (dp[i-1] + k) % i;
}
return dp[n] + 1;
}
}
自幂数（超完全数变数）
对于一个正整数而言，长度是n，如果它的各位上的数字的n次方之和正好等于它本身，那么一个n位自然数等于自身各个数位上数字的n次幂之和，则称此数为自幂数（超完全数变数）
例如 153 = 1^3 + 5^3 + 3^3
一位自幂数：独身数: 1，2，3，4，5，6，7，8，9
两位自幂数：没有
三位自幂数：水仙花数：153，370，371，407
四位自幂数：四叶玫瑰数：1634，8208，9474
五位自幂数：五角星数：54748，92727，93084
六位自幂数：六合数：548834
七位自幂数：北斗七星数：1741725，4210818，9800817，9926315
八位自幂数：八仙数：24678050，24678051，88593477
九位自幂数：九九重阳数
十位自幂数：十全十美数
// 输入一个数 求10~该数之间所有的 自幂数 倒序输出
import java.util.Scanner;
public class Demo{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int num = sc.nextInt();
for (int i = num; i > 10; i--) {
int count = 0; //记录位数
int tmp = i; //定义一个临时变量等于i,避免后面要判断与i相等时i的值改变
//求位数
while(tmp != 0){
tmp /= 10;
count++;
}
int sum = 0;
tmp = i;
while(tmp != 0){
sum += Math.pow(tmp % 10, count);
tmp /= 10; //去掉最后一位
}
if(sum == i){
System.out.println(i);
}
}
}
}
数学
进位操作：2. 两数相加
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例 1：
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.
示例 2：
输入：l1 = [0], l2 = [0]
输出：[0]
示例 3：
输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]
双指针法
这道题主要考察链表双指针技巧和加法运算过程中对进位的处理。注意这个 carry 变量的处理，在我们手动模拟加法过程的时候会经常用到。代码中还用到一个链表的算法题中是很常见的「虚拟头结点」技巧，也就是 dummy 节点。
我们同时遍历两个链表，逐位计算它们的和，并与当前位置的进位值相加。
具体而言，如果当前两个链表处相应位置的数字为 n1，n2，进位值为 carry，则它们的和为 n1+n2+carry；其中，答案链表处相应位置的数字为 (n1+n2+carry) % 10，而新的进位值为 ⌊(n1+n2+carry)/10⌋。
此外，如果链表遍历结束后，有 carry > 0，还需要在答案链表的后面附加一个节点，节点的值为 carry。
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
// 在两条链表上的指针
ListNode p1 = l1, p2 = l2;
// 虚拟头结点（构建新链表时的常用技巧）
ListNode dummy = new ListNode(-1);
// 指针 p 负责构建新链表
ListNode p = dummy;
// 记录进位
int carry = 0;
// 开始执行加法，两条链表走完且没有进位时才能结束循环
while (p1 != null || p2 != null) {
// 先加上上次的进位
int val = carry;
if (p1 != null) {
val += p1.val;
p1 = p1.next;
}
if (p2 != null) {
val += p2.val;
p2 = p2.next;
}
// 处理进位情况
carry = val / 10;
val = val % 10;
// 构建新节点
p.next = new ListNode(val);
p = p.next;
}
//还有进位
if (carry > 0) {
p.next = new ListNode(carry);
}
// 返回结果链表的头结点（去除虚拟头结点）
return dummy.next;
}
}
进位操作：415. 字符串相加
给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和并同样以字符串形式返回。
你不能使用任何內建的用于处理大整数的库（比如 BigInteger）， 也不能直接将输入的字符串转换为整数形式。
示例 1：
输入：num1 = "11", num2 = "123"
输出："134"
示例 2：
输入：num1 = "456", num2 = "77"
输出："533"
示例 3：
输入：num1 = "0", num2 = "0"
输出："0"
- 算法流程： 设定
i，j两指针分别指向num1，num2尾部，模拟人工加法；- 计算进位： 计算
carry = tmp // 10，代表当前位相加是否产生进位； - 添加当前位： 计算
tmp = n1 + n2 + carry，并将当前位tmp % 10添加至res头部； - 索引溢出处理： 当指针
i或j走过数字首部后，给n1，n2赋值为 0，相当于给num1，num2中长度较短的数字前面填 0，以便后续计算。 - 当遍历完
num1，num2后跳出循环，并根据carry值决定是否在头部添加进位 1，最终返回res即可。
- 计算进位： 计算
- 复杂度分析：
- 时间复杂度 O(max(M,N)))：其中 M，N 为num1 和 num2长度；
- 空间复杂度 O(1)：指针与变量使用常数大小空间。
char 转 int ：字符的ASCII码值减去0的ASCII码值等于数值本身。 即num1.charAt(i) - '0'
class Solution {
public String addStrings(String num1, String num2) {
StringBuilder res = new StringBuilder("");
int i = num1.length() - 1, j = num2.length() - 1, carry = 0;
while(i >= 0 || j >= 0){
int n1 = i >= 0 ? num1.charAt(i) - '0' : 0;
int n2 = j >= 0 ? num2.charAt(j) - '0' : 0;
int tmp = n1 + n2 + carry;
carry = tmp / 10; //进位
res.append(tmp % 10);
i--; j--;
}
if(carry == 1) res.append(1);
return res.reverse().toString();
}
}
排列组合：357. 统计各位数字都不同的数字个数
给你一个整数 n ，统计并返回各位数字都不同的数字 x 的个数，其中 0 <= x < 10^n 。
示例 1：
输入：n = 2
输出：91
解释：答案应为除去 11、22、33、44、55、66、77、88、99 外，在 0 ≤ x < 100 范围内的所有数字。
示例 2：
输入：n = 0
输出：1
首先考虑两种边界情况：
当 n=0时，0 ≤ x < 10 ，x 只有 1 种选择，即 0。
当 n=1 时，0 ≤ x < 10，x 有 10 种选择，即 0∼9。
当 n=2 时，0 ≤ x < 100，x 的选择可以由两部分构成：
只有一位数的 x 和有两位数的 x。只有一位数的 x 可以由上述的边界情况计算。
有两位数的 x 可以由组合数学进行计算：第一位的选择有 9 种，即 1∼9，第二位的选择也有 9 种，即 0∼9 中除去第一位的选择。
更一般地，含有 d （2≤d≤10）位数的各位数字都不同的数字 x 的个数可以由公式 9×A9d−1 计算。再加上含有小于 d 位数的各位数字都不同的数字 x 的个数，即可得到答案。
class Solution {
public int countNumbersWithUniqueDigits(int n) {
if (n == 0) {
return 1;
}
if (n == 1) {
return 10;
}
int res = 10, cur = 9;
for (int i = 0; i < n - 1; i++) {
// n = 2 ：9*9 + 10
// n = 3 ：9*9*8 + 91
cur *= 9 - i;
res += cur;
}
return res;
}
}
括号问题
如何解决括号相关的问题 :: labuladong的算法小抄
22. 括号生成-DFS
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：
输入：n = 1
输出：["()"]
有关括号问题，你只要记住以下性质，思路就很容易想出来：
1、一个「合法」括号组合的左括号数量一定等于右括号数量。
2、对于一个「合法」的括号字符串组合 p，必然对于任何 0 <= i < len(p) 都有：子串 p[0..i] 中左括号的数量都大于或等于右括号的数量。
class Solution {
List<String> res = new ArrayList<>();
public List<String> generateParenthesis(int n) {
dfs(n, n, "");
return res;
}
private void dfs(int left, int right, String curStr) {
if (left == 0 && right == 0) { // 左右括号都不剩余了，递归终止
res.add(curStr);
return;
}
if (left > 0) { // 如果左括号还剩余的话，可以拼接左括号
dfs(left - 1, right, curStr + "(");
}
if (right > left) { // 如果右括号剩余多于左括号剩余的话，可以拼接右括号
dfs(left, right - 1, curStr + ")");
}
}
}
class Solution {
private List<String> res = new ArrayList<>();
public List<String> generateParenthesis(int n) {
StringBuilder cur = new StringBuilder();
dfs(cur, n, n);
return res;
}
private void dfs(StringBuilder cur, int left, int right) {
if(left > right) return; // 若左括号剩下的多，说明不合法
if(left < 0 || right < 0) return; // 数量小于 0 肯定是不合法的
if(left == 0 && right == 0) { // 当所有括号都恰好用完时，得到一个合法的括号组合
res.add(cur.toString());
return;
}
// 尝试放一个左括号
cur.append("(");
dfs(cur, left-1, right);
cur.deleteCharAt(cur.length()-1); // 撤消选择
// 尝试放一个右括号
cur.append(")");
dfs(cur, left, right-1);
cur.deleteCharAt(cur.length()-1); // 撤消选择
}
}
20. 有效的括号-栈
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
示例 1：
输入：s = "()"
输出：true
示例 2：
输入：s = "()[]{}"
输出：true
示例 3：
输入：s = "(]"
输出：false
栈是一种先进后出的数据结构，处理括号问题的时候尤其有用。
遇到左括号就入栈，遇到右括号就去栈中寻找最近的左括号，看是否匹配。
class Solution {
public boolean isValid(String s) {
int n = s.length();
// 如果s的长度为奇数，一定不符合要求
if (n % 2 == 1) return false;
Map<Character, Character> map = new HashMap<Character, Character>() {{
put(')', '(');
put(']', '[');
put('}', '{');
}};
Deque<Character> stack = new LinkedList<>();
for(int i = 0; i < n; i++){
//遇到右括号则将对应左括号出栈
if(map.containsKey(s.charAt(i))){
// 去栈中寻找最近的左括号，看是否匹配。
if (!stack.isEmpty() && stack.peek() == map.get(s.charAt(i))) {
// 匹配上就出栈
stack.pop();
} else {
// 没匹配上
return false;
}
} else {
stack.push(s.charAt(i)); //遇到左括号直接入栈
}
}
return stack.isEmpty();
}
}
// 不使用 Map
class Solution {
public boolean isValid(String str) {
Stack<Character> stack = new Stack<>();
for (char c : str.toCharArray()) {
// 字符 c 是左括号入栈
if (c == '(' || c == '{' || c == '['){
stack.push(c);
}
else {
// 字符 c 是右括号，寻找最近的左括号，看是否匹配。
if (!stack.isEmpty() && rev(c) == stack.peek()){
stack.pop();
} else {
// 和最近的左括号不匹配
return false;
}
}
}
// 是否所有的左括号都被匹配了
return stack.isEmpty();
}
char rev(char c) {
if (c == '}') return '{';
if (c == ')') return '(';
return '[';
}
}
301. 删除无效的括号
921. 使括号有效的最少添加
只有满足下面几点之一，括号字符串才是有效的：
- 它是一个空字符串，或者
- 它可以被写成
AB（A与B连接）, 其中A和B都是有效字符串，或者 - 它可以被写作
(A)，其中A是有效字符串。
给定一个括号字符串 s ，在每一次操作中，你都可以在字符串的任何位置插入一个括号
- 例如，如果
s = "())"，你可以插入一个开始括号为"(())"或"()()"。
返回 为使结果字符串 s 有效而必须添加的最少括号数。
示例 1：
输入：s = "())"
输出：1
示例 2：
输入：s = "((("
输出：3
class Solution {
public int minAddToMakeValid(String s) {
// res 记录插入次数
int res = 0;
// need 变量记录右括号的需求量
int need = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
// 对右括号的需求 + 1
need++;
}
if (s.charAt(i) == ')') {
// 对右括号的需求 - 1
need--;
if (need == -1) {
need = 0;
// 需插入一个左括号
res++;
}
}
}
// 插入剩余所需的右括号
return res + need;
}
}
//栈实现
class Solution {
public int minAddToMakeValid(String s) {
int res = 0;
Stack<Character> stack = new Stack<>();
for (char c : s.toCharArray()) {
if (c == '(') {
stack.push(c);
} else {
if (!stack.isEmpty()) {
stack.pop();
} else {
res++; // 没有配对的左括号，插入一个
}
}
}
// 插入的右括号数量 + 多余的左括号数量
return res + stack.size();
}
}
1541. 平衡括号字符串的最少插入次数
给你一个括号字符串 s ，它只包含字符 '(' 和 ')' 。一个括号字符串被称为平衡的当它满足：
- 任何左括号
'('必须对应两个连续的右括号'))'。 - 左括号
'('必须在对应的连续两个右括号'))'之前。
比方说 "())"， "())(())))" 和 "(())())))" 都是平衡的， ")()"， "()))" 和 "(()))" 都是不平衡的。
你可以在任意位置插入字符 ‘(‘ 和 ‘)’ 使字符串平衡。
请你返回让 s 平衡的最少插入次数。
示例 1：
输入：s = "(()))"
输出：1
解释：第二个左括号有与之匹配的两个右括号，但是第一个左括号只有一个右括号。我们需要在字符串结尾额外增加一个 ')' 使字符串变成平衡字符串 "(())))" 。
示例 2：
输入：s = "())"
输出：0
解释：字符串已经平衡了。
示例 3：
输入：s = "))())("
输出：3
解释：添加 '(' 去匹配最开头的 '))' ，然后添加 '))' 去匹配最后一个 '(' 。
示例 4：
输入：s = "(((((("
输出：12
解释：添加 12 个 ')' 得到平衡字符串。
示例 5：
输入：s = ")))))))"
输出：5
解释：在字符串开头添加 4 个 '(' 并在结尾添加 1 个 ')' ，字符串变成平衡字符串 "(((())))))))" 。
class Solution {
public int minInsertions(String s) {
// res 记录插入次数
int res = 0;
// need 变量记录右括号的需求量
int need = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
need += 2;
if (need % 2 == 1) { // 若对右括号的需求量为奇数
res++; // 插入一个右括号
need--;// 对右括号的需求减一
}
}
if (s.charAt(i) == ')') {
need--;
if (need == -1) { // 说明右括号太多了
res++; // 需要插入一个左括号
need = 1; // 同时，对右括号的需求变为 1
}
}
}
// 插入剩余所需的右括号
return res + need;
}
}
32. 最长有效括号-动规
给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
示例 1：
输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"
示例 2：
输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"
示例 3：
输入：s = ""
输出：0
判断括号串是否合法的算法如下：
Deque<Integer> stk = new ArrayDeque<>();
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
// 遇到左括号，记录索引
stk.push(i);
} else {
// 遇到右括号
if (!stk.isEmpty()) {
// 配对的左括号对应索引，[leftIndex, i] 是一个合法括号子串
int leftIndex = stk.pop();
// 这个合法括号子串的长度
int len = i - leftIndex + 1;
} else {
// 没有配对的左括号
}
}
}
但如果多个合法括号子串连在一起，会形成一个更长的合法括号子串，而上述算法无法适配这种情况。
所以需要一个 dp 数组，记录 leftIndex 相邻合法括号子串的长度，才能得出题目想要的正确结果。
class Solution {
public int longestValidParentheses(String s) {
Deque<Integer> stack = new ArrayDeque<>();
// dp[i] 的定义：记录以 s[i-1] 结尾的最长合法括号子串长度
int[] dp = new int[s.length() + 1];
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
stack.push(i); // 遇到左括号，入栈对应索引
dp[i + 1] = 0; // 左括号不可能是合法括号子串的结尾
} else {
if (!stack.isEmpty()) { // 遇到右括号
// 配对的左括号对应索引，[leftIndex, i] 是一个合法括号子串
int leftIndex = stack.pop();
// 以这个右括号结尾的最长子串长度
int len = i - leftIndex + 1 + dp[leftIndex];
dp[i + 1] = len;
} else {
// 没有配对的左括号
dp[i + 1] = 0;
}
}
}
// 计算最长子串的长度
int res = 0;
for (int i = 0; i < dp.length; i++) {
res = Math.max(res, dp[i]);
}
return res;
}
}
比较
❶Comparable
Comparable是排序接口。若一个类实现了Comparable接口，就意味着该类支持排序。实现了Comparable接口的类的对象的列表或数组可以通过
Collections.sort或Arrays.sort进行自动排序。
// 该接口定义如下：
package java.lang;
import java.util.*;
public interface Comparable<T> {
public int compareTo(T o);
}
此接口只有一个方法compareTo，比较当前对象与指定对象的顺序，如果该对象小于、等于或大于指定对象，则分别返回负数、零或正数。
现在我们假设一个Person类，代码如下：
public class Person{
String name;
int age;
public Person(String name, int age){
this.name = name;
this.age = age;
}
public String getName(){
return name;
}
public int getAge(){
return age;
}
}
现在有两个Person类的对象，我们如何来比较二者的大小呢？我们可以通过让Person实现Comparable接口：
public class Person implements Comparable<Person>{
String name;
int age;
public Person(String name, int age){
this.name = name;
this.age = age;
}
public String getName(){
return name;
}
public int getAge(){
return age;
}
@Override
public int compareTo(Person p){
return this.age - p.getAge();
}
public static void main(String[] args){
Person[] people = new Person[]{new Person("小明", 20),new Person("小红", 10)};
Arrays.sort(people);
}
}
❷Comparator
Comparator是比较接口，我们如果需要控制某个类的次序，而该类本身不支持排序(即没有实现Comparable接口)，那么我们就可以建立一个“该类的比较器”来进行排序，这个“比较器”只需要实现Comparator接口即可。
// 该接口定义如下：
package java.util;
public interface Comparator<T>
{
int compare(T o1, T o2);
boolean equals(Object obj);
}
若一个类要实现Comparator接口：它一定要实现
compare()函数，但可不实现equals()函数。compare(T o1, T o2)是“比较o1和o2的大小”。- 返回“负数”，意味着“o1比o2小”
- 返回“零”，意味着“o1等于o2”
- 返回“正数”，意味着“o1大于o2”
现在假如上面的Person类没有实现Comparable接口，该如何比较大小呢？我们可以新建一个类，让其实现Comparator接口，从而构造一个“比较器”。
public class PersonCompartor implements Comparator<Person>{
@Override
public int compare(Person o1, Person o2){
return o1.getAge() - o2.getAge();
}
}
现在我们就可以利用这个比较器来对其进行排序：
public class Test{
public static void main(String[] args){
Person[] people=new Person[]{new Person("小明", 20),new Person("小红", 10)};
Arrays.sort(people,new PersonCompartor());
}
}
//写法2
public class Test2{
public static void main(String[] args){
Person[] people=new Person[]{new Person("小明", 20),new Person("小红", 10)};
Arrays.sort(people,new Comparator<Person>(){
public int compare(Person o1, Person o2){
return o1.getAge() - o2.getAge();
}
});
}
}
❸Comparable和Comparator区别
Comparable是排序接口，若一个类实现了Comparable接口，就意味着“该类支持排序”。
Comparator是比较器，我们若需要控制某个类的次序，可以建立一个“该类的比较器”来进行排序。
Comparable相当于“内部比较器”，而Comparator相当于“外部比较器”。
- java.lang.Comparable：在类定义的时候，可以实现的接口，里面有compareTo这个方法需要实现
- java.util.Comparator：是挽救的比较接口，需要单独定义一个比较类，里面有compare比较方法。
两种方法各有优劣， 用Comparable简单， 只要实现Comparable接口的对象直接就成为一个可以比较的对象，但是需要修改源代码。 用Comparator的好处是不需要修改源代码， 而是另外实现一个比较器， 当某个自定义的对象需要作比较的时候，把比较器和对象一起传递过去就可以比大小了， 并且在Comparator 里面用户可以自己实现复杂的可以通用的逻辑，使其可以匹配一些比较简单的对象，那样就可以节省很多重复劳动了。
交换元素
普通方法
private void swap(int[] a, int i, int j) {
int tmp = a[i]
a[i] = a[j]
a[j] = tmp
System.out.println("swap:" + a[j] + " <-> " + a[i]);
}
异或方法
private void swap(int[] a, int i, int j) {
if (i == j){return;}//关键 两个一样的数异或结果为0
a[i] = a[i] ^ a[j];
a[j] = a[i] ^ a[j];
a[i] = a[i] ^ a[j];
System.out.println("swap:" + a[j] + " <-> " + a[i]);
}
KMP算法
KMP 算法是一个快速查找匹配串的算法，它的作用是：如何快速在「原字符串」中找到「匹配字符串」。
暴力查找复杂度是 O(m∗n)，KMP 算法的复杂度为 O(m+n)，其中m为原字符串长度，m为匹配字符串长度
【自用数据结构】王道4.2.4 串的模式匹配 KMP算法+求Next数组(手算)+求Nextval数组(手算)
28. 找出字符串中第一个匹配项的下标 - 力扣（Leetcode）
class Solution {
public static int strStr(String haystack, String needle) {
int n = haystack.length(), m = needle.length();
if (m == 0) return 0;
// 1.构建 next 数组
int[] next = new int[m]; //next[0]=0
for (int i = 1, j = 0; i < m; i++) {
// 匹配不成功的话，j = next(j-1)
while (j > 0 && needle.charAt(i) != needle.charAt(j)) {
j = next[j - 1];
}
// 匹配成功的话，j++
if (needle.charAt(i) == needle.charAt(j)) {
j++;
}
// 更新 next[i]
next[i] = j;
}
// 2.匹配过程
for (int i = 0, j = 0; i < n; i++) {
// 匹配不成功 j = next(j-1)
while (j > 0 && haystack.charAt(i) != needle.charAt(j)) {
j = next[j - 1];
}
// 匹配成功的话，j++
if (haystack.charAt(i) == needle.charAt(j)) {
j++;
}
if (j == m) {
return i - m + 1;
}
}
return -1;
}
}
❤️Sponsor
您的支持是我不断前进的动力，如果您恰巧财力雄厚，又感觉本文对您有所帮助的话，可以考虑打赏一下本文，用以维持本博客的运营费用，拒绝白嫖，从你我做起！🥰🥰🥰
| 支付宝支付 | 微信支付 |
 |
 |
