Daily coding practice 算法题 P2（2025.11.18 - 2025.11.30）
·
1. Z 字形变换
2025.11.18
将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：
P A H N A P L S I I G Y I R
之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。
请你实现这个将字符串进行指定行数变换的函数：
string convert(string s, int numRows);
示例 1：
输入：s = "PAYPALISHIRING", numRows = 3 输出："PAHNAPLSIIGYIR"
示例 2：
输入：s = "PAYPALISHIRING", numRows = 4 输出："PINALSIGYAHRPI" 解释： P I N A L S I G Y A H R P I
示例 3：
输入：s = "A", numRows = 1 输出："A"
提示：
1 <= s.length <= 1000s由英文字母（小写和大写）、','和'.'组成1 <= numRows <= 1000
/**
* @author Flora
* @date 2025/11/18 10:37
* @description
*/
public class Solution1118 {
// 关键变量：周期长度，交替变换步长（）
public String convertForTheBest(String s, int numRows) {
if(numRows==1) return s;
int n = s.length(), k = 0;
char[] arr = s.toCharArray();
char[] ans = new char[n];
int t = 2 * numRows - 2;
for (int i = 0; i < numRows; i++) {
int j = i, d = t - 2 * i;
while (j < n) {
ans[k++] = arr[j];
if(d==0){
d = t;
}
j += d;
d = t - d;
}
}
return new String(ans);
}
// 暴力解法 m2：尝试优化 m1，尽量一次循环内做完
public String convert(String s, int numRows) {
if (numRows == 1) {
return s;
}
// 一组单词 的 个数 ： numRows - 2 + numRows
int groupUnitNum = numRows - 2 + numRows;
// 一共几组
int groupNum = s.length() / groupUnitNum + 1;
StringBuilder sb = new StringBuilder();
for (int i = 0; i < numRows; i++) {
for (int j = 0; j < groupNum; j++) {
int index = i + j * groupUnitNum;
if (index < s.length()) {
sb.append(s.charAt(index));
}
// 中间行 都是 2个字符
if (i != 0 && i != numRows - 1) {
// int i2 = numRows - (i + 1);
index = i + 2 * (numRows - (i + 1)) + j * groupUnitNum;
if (index < s.length()) {
sb.append(s.charAt(index));
}
}
}
}
return sb.toString();
}
// 暴力解法 m1
public String convert1(String s, int numRows) {
if (numRows == 1) {
return s;
}
// 一组单词 的 个数 ： numRows - 2 + numRows
int groupUnitNum = numRows - 2 + numRows;
// 一共几组
int groupNum = s.length() / groupUnitNum + 1;
StringBuilder sb = new StringBuilder();
for (int i = 0; i < numRows; i++) {
if (i == 0 || i == numRows - 1) {
System.out.println("i = " + i);
StringBuilder row = getThisRow(i,
numRows, groupNum, groupUnitNum, s);
sb.append(row);
} else {
int i2 = i + 2 * (numRows - (i + 1) ); // numRows = 4 时， i = 2 时，i2 = 2 + 2 * (4 - (2 + 1) ) = 2 + 2 * 1 = 4；i = 1 时， i2 = 1 + 2 * (4 - (1 + 1) ) = 1 + 2 * 2 = 5
System.out.println("i = " + i + " , i2 = " + i2);
StringBuilder row = getThisRow(i, i2,
numRows, groupNum, groupUnitNum, s);
sb.append(row);
}
}
return sb.toString();
}
public StringBuilder getThisRow(int targetGroupUnitNum,
int numRows, int groupNum, int groupUnitNum, String s) { // 题目要求几行， 自己计算的有几组， 自己计算的一组有几个， 题目给的字符串
StringBuilder sb = new StringBuilder();
for (int i = 0; i < groupNum; i++) {
int index = targetGroupUnitNum + i * groupUnitNum;
if (index < s.length()) {
sb.append(s.charAt(index));
}
}
return sb;
}
public StringBuilder getThisRow(int targetGroupUnitNum, int targetGroupUnitNum2,
int numRows, int groupNum, int groupUnitNum, String s) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < groupNum; i++) {
int index = targetGroupUnitNum + i * groupUnitNum;
if (index < s.length()) {
sb.append(s.charAt(index));
}
index = targetGroupUnitNum2 + i * groupUnitNum;
if (index < s.length()) {
sb.append(s.charAt(index));
}
}
return sb;
}
public static void main(String[] args) {
Solution1118 s = new Solution1118();
System.out.println(s.convert("A", 1));
// String s1 = s.convert("PAYPALISHIRING", 3);
// System.out.println(s1);
// System.out.println(s1.equals("PAHNAPLSIIGYIR"));
}
}
Z字形变换算法深度对比分析
1. 最优算法 convertForTheBest
核心思路
数学规律+步长跳跃，利用Z字形变换的数学规律直接计算每个字符的位置。
算法原理
java
// 关键变量
int t = 2 * numRows - 2; // 周期长度
for (int i = 0; i < numRows; i++) {
int j = i, d = t - 2 * i; // 当前行起始位置和步长
while (j < n) {
ans[k++] = arr[j];
if(d==0) d = t; // 处理第一行和最后一行
j += d;
d = t - d; // 步长交替变化
}
}
示例分析 (numRows=4, s="PAYPALISHIRING")
text
周期长度 t = 2*4-2 = 6 行0: i=0, d=6 → 位置: 0,6,12 → "P", "I", "N" 行1: i=1, d=4 → 位置: 1,5,7,11,13 → "A", "L", "S", "I", "G" 行2: i=2, d=2 → 位置: 2,4,8,10 → "Y", "P", "I", "R" 行3: i=3, d=0→6 → 位置: 3,9 → "A", "H" 结果: "PINALSIGYAHRPI"
复杂度分析
-
时间复杂度: O(n) - 每个字符只访问一次
-
空间复杂度: O(n) - 两个字符数组
-
实际性能: 最优
2. 暴力解法2 convert
核心思路
分组计算+行列遍历，将字符串按周期分组，按行遍历计算每行的字符位置。
算法原理
java
int groupUnitNum = numRows - 2 + numRows; // 每组字符数 = 2*numRows-2
for (int i = 0; i < numRows; i++) {
boolean middle = (i != 0 && i != numRows - 1); // 是否中间行
for (int j = 0; j < groupNum; j++) {
int index = i + j * groupUnitNum; // 第一个字符位置
// 中间行有第二个字符
if (middle) {
index = i + 2 * (numRows - (i + 1)) + j * groupUnitNum;
}
}
}
复杂度分析
-
时间复杂度: O(n) - 但常数因子较大
-
空间复杂度: O(n) - StringBuilder
-
实际性能: 中等
3. 暴力解法1 convert1
核心思路
方法拆分+条件分支，将不同行的处理逻辑拆分成独立方法，逻辑更清晰但效率较低。
算法特点
-
首尾行和中间行分开处理
-
使用辅助方法
getThisRow提取每行字符 -
代码结构清晰但方法调用开销大
详细对比分析
性能对比
| 维度 | 最优算法 | 暴力解法2 | 暴力解法1 |
|---|---|---|---|
| 执行速度 | ⭐⭐⭐⭐⭐ | ⭐⭐⭐ | ⭐⭐ |
| 内存效率 | ⭐⭐⭐⭐⭐ | ⭐⭐⭐ | ⭐⭐ |
| 循环次数 | n次 | numRows×groupNum次 | numRows×groupNum次 |
| 计算复杂度 | 简单数学运算 | 复杂索引计算 | 最复杂 |
代码质量对比
| 维度 | 最优算法 | 暴力解法2 | 暴力解法1 |
|---|---|---|---|
| 可读性 | ⭐⭐ | ⭐⭐⭐ | ⭐⭐⭐⭐ |
| 可维护性 | ⭐⭐ | ⭐⭐⭐ | ⭐⭐⭐⭐ |
| 代码简洁性 | ⭐⭐⭐⭐ | ⭐⭐⭐ | ⭐⭐ |
| 调试难度 | 困难 | 中等 | 简单 |
算法思维对比
| 算法 | 思维方式 | 数学要求 | 创新性 |
|---|---|---|---|
| 最优算法 | 数学规律发现 | 高 | 创造性思维 |
| 暴力解法2 | 模拟过程优化 | 中 | 工程优化 |
| 暴力解法1 | 直接模拟过程 | 低 | 常规思维 |
核心数学原理
Z字形变换规律
对于numRows行的Z字形排列：
-
周期长度:
t = 2 × numRows - 2 -
首尾行: 每个周期只有1个字符
-
中间行: 每个周期有2个字符，位置关系为对称
最优算法的数学推导
java
// 第i行的字符位置计算： // 第一个字符: j = i // 步长变化: d = t - 2*i 和 d = t - d 交替 // 这实际上是在周期内对称位置的跳跃
改进建议
最优算法可读性优化版
java
public String convertOptimized(String s, int numRows) {
if (numRows == 1) return s;
char[] chars = s.toCharArray();
char[] result = new char[chars.length];
int resultIndex = 0;
int cycleLen = 2 * numRows - 2;
for (int row = 0; row < numRows; row++) {
int step1 = cycleLen - 2 * row;
int step2 = 2 * row;
int current = row;
while (current < chars.length) {
// 添加当前字符
result[resultIndex++] = chars[current];
// 计算下一个位置
if (step1 > 0 && step2 > 0) {
// 中间行：交替使用两个步长
current += (current == row) ? step1 : step2;
// 交换步长以便下次使用
int temp = step1;
step1 = step2;
step2 = temp;
} else {
// 首尾行：只有一种步长
current += cycleLen;
}
}
}
return new String(result);
}
暴力解法2的简化版
java
public String convertSimplified(String s, int numRows) {
if (numRows == 1) return s;
StringBuilder sb = new StringBuilder();
int cycle = 2 * numRows - 2;
int n = s.length();
for (int i = 0; i < numRows; i++) {
for (int j = 0; j + i < n; j += cycle) {
// 每组的第一个字符
sb.append(s.charAt(j + i));
// 中间行的第二个字符
if (i != 0 && i != numRows - 1 && j + cycle - i < n) {
sb.append(s.charAt(j + cycle - i));
}
}
}
return sb.toString();
}
总结
最优算法展现了数学思维在算法优化中的强大力量，通过发现并利用Z字形变换的数学规律，实现了最优的时间复杂度。
暴力解法2在可读性和性能之间取得了较好平衡，适合大多数工程场景。
暴力解法1虽然性能最差，但其模块化的设计思想值得学习，特别适合团队协作和代码维护。
推荐选择：
-
竞赛/面试：最优算法
-
生产环境：暴力解法2简化版
-
学习教学：暴力解法1（理解Z字形变换过程）
2.找出字符串中第一个匹配项的下标
2025.11.19
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。
示例 1：
输入：haystack = "sadbutsad", needle = "sad" 输出：0 解释："sad" 在下标 0 和 6 处匹配。 第一个匹配项的下标是 0 ，所以返回 0 。
示例 2：
输入：haystack = "leetcode", needle = "leeto" 输出：-1 解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。
提示：
1 <= haystack.length, needle.length <= 104haystack和needle仅由小写英文字符组成
/**
* @author Flora
* @date 2025/11/19 09:17
* @description
*/
public class Solution1119 {
public int strStrForTheBest(String haystack, String needle) {
if(haystack.contains(needle)){
return haystack.indexOf(needle);
}
return -1;
}
// 不用 indexOf 等， 手写
public int strStr(String haystack, String needle) {
char[] hay = haystack.toCharArray();
char[] need = needle.toCharArray();
int left = 0;
int right = need.length - 1;
for (int i = 0; i < hay.length; i++) {
if (i + right < hay.length && hay[i + left] == need[left] && hay[i + right] == need[right]) {
while (left <= right) {
if (hay[i + left] != need[left] || hay[i + right] != need[right]) break;
left++;
right--;
}
if (left > right) return i;
left = 0;
right = need.length - 1;
}
}
return -1;
}
public int strStr1(String haystack, String needle) {
int hayLen = haystack.length();
int needLen = needle.length();
for (int i = 0; i + needLen <= hayLen; i++) {
if (needle.equals(haystack.substring(i, i + needLen))) return i;
}
return -1;
}
public static void main(String[] args) {
Solution1119 solution = new Solution1119();
// System.out.println(solution.strStr("hello", "ll"));
System.out.println(solution.strStr("mississippi", "sipp"));
}
}
3.文本左右对齐
2025.11.20
给定一个单词数组 words 和一个长度 maxWidth ，重新排版单词，使其成为每行恰好有 maxWidth 个字符，且左右两端对齐的文本。
你应该使用 “贪心算法” 来放置给定的单词；也就是说，尽可能多地往每行中放置单词。必要时可用空格 ' ' 填充，使得每行恰好有 maxWidth 个字符。
要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。
文本的最后一行应为左对齐，且单词之间不插入额外的空格。
注意:
- 单词是指由非空格字符组成的字符序列。
- 每个单词的长度大于 0，小于等于 maxWidth。
- 输入单词数组
words至少包含一个单词。
示例 1:
输入: words = ["This", "is", "an", "example", "of", "text", "justification."], maxWidth = 16 输出: [ "This is an", "example of text", "justification. " ]
示例 2:
输入:words = ["What","must","be","acknowledgment","shall","be"], maxWidth = 16
输出:
[
"What must be",
"acknowledgment ",
"shall be "
]
解释: 注意最后一行的格式应为 "shall be " 而不是 "shall be",
因为最后一行应为左对齐，而不是左右两端对齐。
第二行同样为左对齐，这是因为这行只包含一个单词。
示例 3:
输入:words = ["Science","is","what","we","understand","well","enough","to","explain","to","a","computer.","Art","is","everything","else","we","do"]，maxWidth = 20 输出: [ "Science is what we", "understand well", "enough to explain to", "a computer. Art is", "everything else we", "do " ]
提示:
1 <= words.length <= 3001 <= words[i].length <= 20words[i]由小写英文字母和符号组成1 <= maxWidth <= 100words[i].length <= maxWidth
import java.util.ArrayList;
import java.util.List;
/**
* @author Flora
* @date 2025/11/20 09:07
* @description
*/
public class Solution1120 {
// 68. 文本左右对齐 -> 暴力解法 m2 -> 尝试优化 更好的处理，例如一次循环内做完所有事情
// 关键步骤：1.确定每行单词的个数，并记录每行单词的长度 2.判断空白格数量，并添加 3.判断最后一行特殊处理，左对齐即可，单词间只需要1个空白格，最后一个单词后面补全n个空白格知道maxWidth
/**
* 暴力解法（fullJustify）的步骤：
* 使用一个循环遍历每个单词，同时维护当前行的单词列表（temp）、当前行单词的总长度（currentLen）和当前行的StringBuilder（sb）。
* 对于每个单词，检查当前行加上这个单词（考虑单词间的空格）是否超过maxWidth。如果没有，则加入当前行。
* 当当前行不能再加下一个单词时（或者遇到最后一个单词），开始构造当前行的字符串。
* 构造字符串时，分两种情况：最后一行和非最后一行。
* 非最后一行（两端对齐）：
* - 如果只有一个单词，左对齐，后面补空格。
* - 如果有多个单词，计算平均每个间隔需要多少空格（spacesBetweenWords）和多余的空格（extraSpaces），然后从左到右分配多余的空格。
* 最后一行（左对齐）：
* - 单词之间只有一个空格，末尾用空格填充至maxWidth。
* @param words
* @param maxWidth
* @return
*/
public List<String> fullJustify(String[] words, int maxWidth) {
List<String> res = new ArrayList<>();
int wordLen = words.length;
// 当前行结果字符串
StringBuilder sb = new StringBuilder();
// 当前行单词
List<String> temp = new ArrayList<>();
// 当前行单词长度（<= maxWidth）
int currentLen = 0;
for (int j = 0; j < wordLen; j++) {
// 空白格数量
int space = currentLen != 0 ? temp.size() : 0;
if (currentLen + words[j].length() + space <= maxWidth) {
// 统一收集单词，而不是分别处理第一个和后续单词
temp.add(words[j]);
currentLen += words[j].length();
if (j == wordLen - 1 || currentLen + words[j+1].length() + temp.size() > maxWidth) {
// 放满这一行单词了 或 已到达最后一个单词，构造结果字符串
int currentWordSize = temp.size();
if (!(j == wordLen - 1)) {
// 不是最后一行，选择两端对齐（ 剩余行内距离 / 需要分给几个单词间隔填充空白格）
int spacesBetweenWords = currentWordSize > 1 ? (maxWidth - currentLen) / (currentWordSize - 1) : (maxWidth - currentLen); // 要么尽量平均分配单词间空白格，要么全给他
int extraSpaces = currentWordSize > 1 ? (maxWidth - currentLen) % (currentWordSize - 1) : 0;
for (int k = 0; k < currentWordSize; k++) {
sb.append(temp.get(k));
// 在每个单词后面，填充单词间空白格。最后一个单词后面没有空白格
if (currentWordSize == 1 || k != currentWordSize - 1) {
// spaceCount 空白格数量
int spaceCount = spacesBetweenWords;
if (extraSpaces != 0) {
spaceCount += 1;
extraSpaces--;
}
for (int h = 0; h < spaceCount; h++) {
sb.append(" ");
}
}
}
} else {
// 最后一行，选择左对齐
for (int k = 0; k < currentWordSize; k++) {
sb.append(temp.get(k));
if (k != currentWordSize - 1) {
sb.append(" ");
} else {
int cha = maxWidth - currentLen;
// 空白格数量
if (currentLen != 0) cha -= temp.size() - 1;
for (int h = 0; h < cha; h++) {
sb.append(" ");
}
}
}
}
res.add(String.valueOf(sb));
sb = new StringBuilder();
temp = new ArrayList<>();
currentLen = 0;
}
}
}
return res;
}
/**
* 最优解法（fullJustifyForTheBest）的步骤：
* 使用两个指针i和j，i指向当前行的第一个单词，j从i开始向后移动，直到当前行不能再加下一个单词。
* 计算当前行的单词数量（wordCount）和总空格数（totalSpaces = maxWidth - 当前行单词总长度）。
* 分两种情况构造行：
* 最后一行或只有一个单词的行：左对齐，单词之间一个空格，行末用空格填充。
* 其他行（两端对齐）：计算单词之间的空格数（spacesBetweenWords）和额外需要分配的空格数（extraSpaces），然后从左到右将额外空格分配到前几个间隔中。
* @param words
* @param maxWidth
* @return
*/
public List<String> fullJustifyForTheBest(String[] words, int maxWidth) {
List<String> result = new ArrayList<>();
int n = words.length;
int i = 0;
// 遍历所有单词，按行处理文本对齐
while (i < n) {
// 确定当前行可以容纳的单词范围 [i, j)
int j = i;
int currentLength = 0;
// 找出当前行最多能放多少个单词
while (j < n && currentLength + words[j].length() + (j - i) <= maxWidth) {
currentLength += words[j].length();
j++;
}
// 计算当前行的单词数量和需要添加的空格总数
int wordCount = j - i;
int totalSpaces = maxWidth - currentLength;
// 构建当前行的字符串
StringBuilder sb = new StringBuilder();
// 处理最后一行或只有一个单词的情况（左对齐）
if (j == n || wordCount == 1) {
// 添加单词，单词间用一个空格分隔
for (int k = i; k < j; k++) {
sb.append(words[k]);
// 如果不是最后一个单词，则添加一个空格
if (k < j - 1) {
sb.append(" ");
totalSpaces--; // 减少一个空格数
}
}
// 在行尾添加剩余的空格
while (totalSpaces > 0) {
sb.append(" ");
totalSpaces--;
}
} else {
// 处理中间行（两端对齐）
// 计算单词间的平均空格数和需要额外分配的空格数
int spacesBetweenWords = totalSpaces / (wordCount - 1);
int extraSpaces = totalSpaces % (wordCount - 1);
// 添加单词并在单词间添加适当数量的空格
for (int k = i; k < j; k++) {
sb.append(words[k]);
// 如果不是最后一个单词，则在其后添加空格
if (k < j - 1) {
// 计算需要添加的空格数，前extraSpaces个间隔需要多加一个空格
int spacesToAdd = spacesBetweenWords + (k - i < extraSpaces ? 1 : 0);
for (int s = 0; s < spacesToAdd; s++) {
sb.append(" ");
}
}
}
}
// 将构建好的行添加到结果列表中
result.add(sb.toString());
i = j; // 移动到下一行的第一个单词
}
return result;
}
// 对m1的优化
public List<String> fullJustify2(String[] words, int maxWidth) {
List<String> res = new ArrayList<>();
boolean lastRow = false;
for (int i = 0; i < words.length; ) {
StringBuilder sb = new StringBuilder();
// 当前行单词
List<String> temp = new ArrayList<>();
// 当前行单词长度（<= maxWidth）
int currentLen = 0;
// 循环放单词
for (int j = i; j < words.length; j++) {
if (currentLen == 0 && words[j].length() <= maxWidth) {
// 每次增加单词，都判断是否走到最后一个单词，最后一个单词一定在最后一行
if (j == words.length - 1) lastRow = true;
temp.add(words[j]);
// 更新当前行单词长度
currentLen += words[j].length();
} else if (currentLen != 0 && currentLen + 1 + words[j].length() <= maxWidth) {
if (j == words.length - 1) lastRow = true;
temp.add(words[j]);
currentLen += (1 + words[j].length());
} else {
// 放满这一行单词了，则跳出循环
break;
}
}
// 构造结果字符串
if (!lastRow) {
int currentWordSize = temp.size();
// 单词数量>=3，单词间空白格的数量不一定相等； 单词数量==2，结果 = 单词＋剩余行内距离+单词； 单词数量==1，结果 = 单词＋剩余行内距离
if (currentWordSize >= 3) {
/**
* 计算这两个值的逻辑说明：
*
* 商： Quotient
* 余数： Remainder
* （被除数） divided by （除数） gives （商） with a remainder of （余数）.
*
* (currentWordSize - 1) = 行内有几个单词间隔
* (currentLen - (currentWordSize - 1)) = 单词长度之和（不含空白格）
* (maxWidth - (currentLen - (currentWordSize - 1))) = 剩余行内距离（需要分给几个单词间隔填充空白格）
* (maxWidth - (currentLen - (currentWordSize - 1))) / (currentWordSize - 1) = 单词间空白格数量（至少）
* 余数不为0时，优先从左边的单词间隙开始，多填充一个空白格
*/
// 商 和 余数。余数不为0时，优先从左边的单词间隙开始填充；商是至少要填充的空白格数量
int spacesBetweenWords = (maxWidth - (currentLen - (currentWordSize - 1))) / (currentWordSize - 1);
int extraSpaces = (maxWidth - (currentLen - (currentWordSize - 1))) % (currentWordSize - 1);
for (int k = 0; k < currentWordSize; k++) {
sb.append(temp.get(k));
// 在每个单词后面，填充单词间空白格。最后一个单词后面没有空白格
if (k != currentWordSize - 1) {
// spaceCount 空白格数量
int spaceCount = spacesBetweenWords;
if (extraSpaces != 0) {
spaceCount += 1;
extraSpaces--;
}
for (int h = 0; h < spaceCount; h++) {
sb.append(" ");
}
}
}
} else if (currentWordSize == 2) {
// 单词数量==2，结果 = 单词＋剩余行内距离+单词；
sb.append(temp.get(0));
int cha = maxWidth - temp.get(0).length() - temp.get(1).length();
for (int k = 0; k < cha; k++) {
sb.append(" ");
}
sb.append(temp.get(1));
} else {
// 单词数量==1，结果 = 单词＋剩余行内距离
sb.append(temp.get(0));
int cha = maxWidth - temp.get(0).length();
for (int k = 0; k < cha; k++) {
sb.append(" ");
}
}
} else {
// 最后一行
for (int k = 0; k < temp.size(); k++) {
sb.append(temp.get(k));
if (k != temp.size() - 1) {
sb.append(" ");
} else {
int cha = maxWidth - currentLen;
for (int h = 0; h < cha; h++) {
sb.append(" ");
}
}
}
}
res.add(String.valueOf(sb));
i += temp.size();
}
return res;
}
// 暴力解法 m1
public List<String> fullJustify1(String[] words, int maxWidth) {
List<String> res = new ArrayList<>();
boolean lastRow = false;
for (int i = 0; i < words.length; i++) {
List<String> temp = new ArrayList<>();
int currentLen = 0;
if (words[i].length() <= maxWidth) {
if (i == words.length - 1) lastRow = true;
temp.add(words[i]);
currentLen += words[i].length();
}
for (int j = i + 1; j < words.length; j++) {
if (currentLen + 1 + words[j].length() <= maxWidth) {
if (j == words.length - 1) lastRow = true;
temp.add(words[j]);
currentLen += (1 + words[j].length());
} else {
StringBuilder sb = new StringBuilder();
if (lastRow) {
for (int k = 0; k < temp.size(); k++) {
sb.append(temp.get(k));
if (k != temp.size() - 1) {
sb.append(" ");
currentLen++;
} else {
int cha = maxWidth - currentLen;
for (int h = 0; h < cha; h++) {
sb.append(" ");
currentLen++;
}
}
}
} else {
int currentWordSize = temp.size();
if (temp.size() >= 3) {
int spacesBetweenWords = (maxWidth - (currentLen - (currentWordSize - 1))) / (currentWordSize - 1);
int extraSpaces = (maxWidth - (currentLen - (currentWordSize - 1))) % (currentWordSize - 1);
// if (extraSpaces != 0) {
// spacesBetweenWords += 1;
// }
currentLen = 0;
for (int k = 0; k < temp.size(); k++) {
sb.append(temp.get(k));
currentLen += temp.get(k).length();
if (k != temp.size() - 1) {
int spaceCount = spacesBetweenWords;
if (extraSpaces != 0) {
spaceCount += 1;
extraSpaces--;
}
for (int h = 0; h < spaceCount; h++) {
sb.append(" ");
currentLen++;
}
}
}
} else if (temp.size() == 2) {
sb.append(temp.get(0));
int cha = maxWidth - temp.get(0).length() - temp.get(1).length();
for (int k = 0; k < cha; k++) {
sb.append(" ");
}
sb.append(temp.get(1));
} else {
sb.append(temp.get(0));
int cha = maxWidth - currentLen;
for (int k = 0; k < cha; k++) {
sb.append(" ");
}
}
}
res.add(String.valueOf(sb));
i += temp.size() - 1;
break;
}
}
if (lastRow) {
StringBuilder sb = new StringBuilder();
if (lastRow) {
currentLen = 0;
for (int k = 0; k < temp.size(); k++) {
sb.append(temp.get(k));
currentLen += temp.get(k).length();
if (k != temp.size() - 1) {
sb.append(" ");
currentLen++;
} else {
int cha = maxWidth - currentLen;
for (int h = 0; h < cha; h++) {
sb.append(" ");
currentLen++;
}
}
}
}
res.add(String.valueOf(sb));
break;
}
}
return res;
}
public static void main(String[] args) {
Solution1120 solution = new Solution1120();
System.out.println(solution.fullJustifyForTheBest(new String[]{"This", "is", "an", "example", "of", "text", "justification."}, 16));
// System.out.println(solution.fullJustify(new String[]{"What","must","be","acknowledgment","shall","be"}, 16));
// System.out.println(solution.fullJustify(new String[]{"Science","is","what","we","understand","well","enough","to","explain","to","a","computer.","Art","is","everything","else","we","do"}, 20));
// System.out.println(solution.fullJustify(new String[]{"ask","not","what","your","country","can","do","for","you","ask","what","you","can","do","for","your","country"}, 16));
}
}
通过对比这两个文本两端对齐算法，我可以清楚地看到暴力解法和最优解法在代码结构、可读性和效率上的显著差异。
核心差异分析
1. 代码结构与可读性
暴力解法问题：
java
// 复杂的嵌套条件判断
if (currentLen + words[j].length() + space <= maxWidth) {
if (j == wordLen - 1 || currentLen + words[j+1].length() + temp.size() > maxWidth) {
if (!(j == wordLen - 1)) {
// 更多嵌套...
}
}
}
最优解法优势：
java
// 清晰的层次结构
while (i < n) {
// 1. 确定当前行单词范围
// 2. 构建当前行
if (最后一行条件) {
// 左对齐逻辑
} else {
// 两端对齐逻辑
}
}
2. 算法逻辑复杂度
| 方面 | 暴力解法 | 最优解法 |
|---|---|---|
| 指针管理 | 单指针+复杂条件 | 双指针(i,j)清晰定位 |
| 边界处理 | 多处重复判断 | 统一在循环开始处理 |
| 空格计算 | 分散在多处 | 集中计算，逻辑清晰 |
3. 性能对比
暴力解法的时间复杂度： O(n × maxWidth)
-
每个单词可能被多次处理
-
字符串拼接效率较低
最优解法的时间复杂度： O(n)
-
每个单词只处理一次（）
-
字符串构建更高效
关键优化点
1. 双指针策略
java
// 最优解法的核心优势
int i = 0;
while (i < n) {
int j = i; // j探索当前行结束位置
// ... 确定当前行范围
i = j; // 移动到下一行开始
}
2. 统一的空格分配逻辑
java
// 清晰的空间计算 int spacesBetweenWords = totalSpaces / (wordCount - 1); int extraSpaces = totalSpaces % (wordCount - 1); // 均匀分配额外空格 int spacesToAdd = spacesBetweenWords + (k - i < extraSpaces ? 1 : 0);
3. 简化的边界条件处理
java
// 统一处理最后一行和单单词行
if (j == n || wordCount == 1) {
// 左对齐逻辑
} else {
// 两端对齐逻辑
}
实际测试建议
对于这类文本对齐问题，建议：
-
测试用例应包括：
-
常规多行文本
-
包含长单词的情况
-
最后一行特殊情况
-
单单词行边界情况
-
-
性能测试：
-
大规模单词数组
-
不同maxWidth值
-
极端情况（如所有单词长度相同）
-
总结
最优解法在以下几个方面显著优于暴力解法：
-
可读性：逻辑分层清晰，易于理解和维护
-
可维护性：修改空格分配策略或对齐规则更容易
-
性能：时间复杂度更低，处理大规模数据更高效
-
健壮性：边界条件处理更完善
在实际工程中，最优解法的双指针策略和清晰的责任分离是值得学习和借鉴的设计模式。
4.验证回文串
2025.11.21
如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。
字母和数字都属于字母数字字符。
给你一个字符串 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 是一个空字符串 "" 。 由于空字符串正着反着读都一样，所以是回文串。
提示：
1 <= s.length <= 2 * 105s仅由可打印的 ASCII 字符组成
/**
* @author Flora
* @date 2025/11/21 09:12
* @description
*/
public class Solution1121 {
private char getChar(char c) {
if (c >= 'A' && c <= 'Z') {
return (char) (c - 'A' + 'a');
}
if (c >= 'a' && c <= 'z') {
return c;
}
if (c >= '0' && c <= '9') {
return c;
}
return (char) 0;
}
public boolean isPalindromeForTheBest(String s) {
int l = 0, r = s.length() - 1;
while (true) {
char lc = (char) 0, rc = (char) 0;
while (l < s.length() && (lc = getChar(s.charAt(l))) == 0) {
l++;
}
while (r >= 0 && (rc = getChar(s.charAt(r))) == 0) {
r--;
}
if (l >= r) {
return true;
}
if (lc != rc) {
return false;
}
l++;
r--;
}
}
// 暴力解法 m2 尝试优化
public boolean isPalindrome(String s) {
char[] charArray = s.toCharArray();
int left = 0;
int right = s.length() - 1;
while (left < right) {
char c = charArray[left];
if (!Character.isLetterOrDigit(c)) {
left++;
continue;
}
char c1 = charArray[right];
if (!Character.isLetterOrDigit(c1)) {
right--;
continue;
}
if (Character.toLowerCase(c) != Character.toLowerCase(c1)) {
return false;
}
left++;
right--;
}
return true;
}
// 暴力解法 m1
public boolean isPalindrome1(String s) {
char[] chars = new char[s.length()];
int index = 0;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
boolean letterOrDigit = Character.isLetterOrDigit(c);
if (letterOrDigit) {
chars[index] = Character.toLowerCase(c);
index++;
}
}
int left = 0;
int right = index - 1;
while (left < right) {
if (chars[left] != chars[right]) {
return false;
}
left++;
right--;
}
return true;
}
public static void main(String[] args) {
Solution1121 solution = new Solution1121();
System.out.println(solution.isPalindrome("A man, a plan, a canal: Panama"));
}
}
对这两个回文判断方法进行对比分析：
代码结构对比
最优解法 (isPalindromeForTheBest)
java
private char getChar(char c) {
if (c >= 'A' && c <= 'Z') return (char)(c - 'A' + 'a'); // 大写转小写
if (c >= 'a' && c <= 'z') return c; // 小写字母保持不变
if (c >= '0' && c <= '9') return c; // 数字保持不变
return (char)0; // 非字母数字返回0
}
public boolean isPalindromeForTheBest(String s) {
int l = 0, r = s.length() - 1;
while (true) {
char lc = (char)0, rc = (char)0;
// 找到左边第一个有效字符
while (l < s.length() && (lc = getChar(s.charAt(l))) == 0) l++;
// 找到右边第一个有效字符
while (r >= 0 && (rc = getChar(s.charAt(r))) == 0) r--;
if (l >= r) return true; // 指针相遇，是回文
if (lc != rc) return false; // 字符不匹配，不是回文
l++; r--; // 移动指针
}
}
暴力解法 (isPalindrome)
java
public boolean isPalindrome(String s) {
char[] charArray = s.toCharArray();
int left = 0, right = s.length() - 1;
while (left < right) {
// 跳过左边无效字符
if (!Character.isLetterOrDigit(charArray[left])) {
left++;
continue;
}
// 跳过右边无效字符
if (!Character.isLetterOrDigit(charArray[right])) {
right--;
continue;
}
// 比较字符（转换为小写）
if (Character.toLowerCase(charArray[left]) != Character.toLowerCase(charArray[right])) {
return false;
}
left++;
right--;
}
return true;
}
性能分析
时间复杂度
-
两种方法都是 O(n)，其中 n 是字符串长度
-
每个字符最多被访问一次
空间复杂度
-
最优解法：O(1) - 只使用指针变量
-
暴力解法：O(n) - 需要
toCharArray()创建字符数组
关键差异分析
1. 字符处理方式
最优解法：
-
自定义
getChar()函数，一次性完成字符验证和大小写转换 -
使用 ASCII 值直接计算，避免方法调用开销
-
非字母数字返回
(char)0作为标记
暴力解法：
-
使用
Character.isLetterOrDigit()和Character.toLowerCase() -
标准库方法调用有额外开销
-
需要多次方法调用
2. 指针移动策略
最优解法：
-
在内部循环中直接跳过所有无效字符
-
每次找到一对有效字符进行比较
-
逻辑更紧凑
暴力解法：
-
在外部循环中逐个跳过无效字符
-
使用
continue语句，逻辑相对分散
3. 内存使用
最优解法：
-
直接操作原字符串，不创建额外数组
-
内存效率更高
暴力解法：
-
创建字符数组副本，增加内存开销
优化建议
最优解法的进一步优化：
java
public boolean isPalindromeOptimized(String s) {
int l = 0, r = s.length() - 1;
while (l < r) {
char lc = s.charAt(l);
char rc = s.charAt(r);
// 跳过左边无效字符
if (!isAlphanumeric(lc)) {
l++;
continue;
}
// 跳过右边无效字符
if (!isAlphanumeric(rc)) {
r--;
continue;
}
// 比较（转换为小写）
if (toLower(lc) != toLower(rc)) return false;
l++;
r--;
}
return true;
}
private boolean isAlphanumeric(char c) {
return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9');
}
private char toLower(char c) {
return (c >= 'A' && c <= 'Z') ? (char)(c + 32) : c;
}
总结
最优解法确实更优，主要体现在：
-
内存效率更高 - O(1) vs O(n)
-
减少方法调用 - 自定义函数避免标准库开销
-
逻辑更紧凑 - 内部循环直接处理字符验证和转换
暴力解法的优势：
-
可读性更好 - 使用标准库方法，意图明确
-
Unicode支持 -
Character类方法支持更广泛的字符集
在实际应用中，如果处理的是纯ASCII文本且性能要求高，最优解法是更好的选择。如果需要更好的可读性和Unicode支持，暴力解法也是可以接受的。
5.判断子序列
2025.11.22
给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
进阶：
如果有大量输入的 S，称作 S1, S2, ... , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？
致谢：
特别感谢 @pbrother 添加此问题并且创建所有测试用例。
示例 1：
输入：s = "abc", t = "ahbgdc" 输出：true
示例 2：
输入：s = "axc", t = "ahbgdc" 输出：false
提示：
0 <= s.length <= 1000 <= t.length <= 10^4- 两个字符串都只由小写字符组成。
public class Solution1122 {
public boolean isSubsequenceForTheBest(String s, String t) {
if(t.length() < s.length()) {
return false;
}
int i = 0;
char[] sArray = s.toCharArray();
char[] lArray = t.toCharArray();
int index = 0;
for(int j = 0; j<sArray.length;){
if(i >= lArray.length) {
break;
}
if(lArray[i] == sArray[j]) {
i++;
j++;
index++;
}else{
i++;
}
}
return index == sArray.length;
}
// 判断 s 是否为 t 的子序列
public boolean isSubsequence(String s, String t) {
int sIndex = 0;
int tIndex = 0;
while (sIndex < s.length() && tIndex < t.length()) {
if (s.charAt(sIndex) == t.charAt(tIndex)) {
sIndex++;
tIndex++;
} else {
tIndex++;
}
}
return sIndex == s.length();
}
public static void main(String[] args) {
System.out.println(new Solution1122().isSubsequence("abc", "ahbgdc"));
}
}
6.两数之和 II - 输入有序数组
2025.11.23
给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。
以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。
你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。
你所设计的解决方案必须只使用常量级的额外空间。
示例 1：
输入：numbers = [2,7,11,15], target = 9 输出：[1,2] 解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
示例 2：
输入：numbers = [2,3,4], target = 6 输出：[1,3] 解释：2 与 4 之和等于目标数 6 。因此 index1 = 1, index2 = 3 。返回 [1, 3] 。
示例 3：
输入：numbers = [-1,0], target = -1 输出：[1,2] 解释：-1 与 0 之和等于目标数 -1 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
提示：
2 <= numbers.length <= 3 * 104-1000 <= numbers[i] <= 1000numbers按 非递减顺序 排列-1000 <= target <= 1000- 仅存在一个有效答案
import java.util.Arrays;
public class Solution1123 {
public int[] twoSumForTheBest(int[] numbers, int target) {
int left = 0;
int right = numbers.length - 1;
while (left < right) {
if (numbers[left] + numbers[right] == target) {
return new int[] { left + 1, right + 1 };
} else if (numbers[left] + numbers[right] < target) {
left++;
} else {
right--;
}
}
throw new IllegalArgumentException("No Two Sum solution");
}
private int binarySearch(int[] array, int target, int start) {
int left = start;
int right = array.length - 1;
while (left < right) {
int mid = (left + right) / 2;
if (array[mid] < target) {
left = mid + 1;
} else {
right = mid;
}
}
return (left == right && array[left] == target) ? left : -1;
}
// 关键 在于numbers是递增的数组
public int[] twoSum(int[] numbers, int target) {
int left = 0;
int right = numbers.length - 1;
while (left < right) {
int sum = numbers[left] + numbers[right];
if (sum > target)
right--;
else if (sum < target)
left++;
else
return new int[]{left + 1, right + 1};
}
return new int[]{-1, -1};
}
public int[] twoSum2(int[] numbers, int target) {
for (int i = 0; i < numbers.length; i++) {
for (int j = i+1; j < numbers.length; j++) {
int sum = numbers[i] + numbers[j];
if (sum == target) {
return new int[]{i + 1, j + 1};
}
}
}
return new int[]{-1, -1};
}
public static void main(String[] args) {
System.out.println(Arrays.toString(new Solution1123().twoSum(new int[]{2, 7, 11, 15}, 9)));
}
}
7.盛最多水的容器
2025.11.24
提示
给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明：你不能倾斜容器。
示例 1：
输入：[1,8,6,2,5,4,8,3,7] 输出：49 解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
示例 2：
输入：height = [1,1] 输出：1
提示：
n == height.length2 <= n <= 1050 <= height[i] <= 104
public class Solution1124 {
/**
* 使用双指针法计算最大容器面积
* 该方法通过从数组两端向中间移动指针的方式，跳过所有不可能产生更大面积的情况
*
* @param height 表示各个位置高度的整数数组
* @return 返回能容纳最多水的容器面积
*/
public int maxAreaForTheBest(int[] height) {
int left = 0;
int right = height.length - 1;
int res = 0;
while(left < right) {
// 计算当前容器的高度(取两边较短的一边)
int h = Math.min(height[left], height[right]);
// 计算当前容器的面积
int area = h * (right - left);
// 更新最大面积
res = Math.max(res, area);
// 移动左指针，跳过所有高度小于等于当前高度的位置
while(left < right && height[left] <= h) {
left ++;
}
// 移动右指针，跳过所有高度小于等于当前高度的位置
while(left < right && height[right] <= h) {
right --;
}
}
return res;
}
/**
* 使用标准双指针法计算最大容器面积
* 每次移动较短边的指针，因为这样才有可能获得更大的面积
*
* @param height 表示各个位置高度的整数数组
* @return 返回能容纳最多水的容器面积
*/
public int maxAreaForTheBest2(int[] height) {
int left = 0, right = height.length - 1;
int res = 0;
while (left < right) {
// [left, right] 之间的矩形面积
int cur_area = Math.min(height[left], height[right]) * (right - left);
res = Math.max(res, cur_area);
// 双指针技巧，移动较低的一边
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
return res;
}
public int maxArea(int[] height) {
int max = 0;
int left = 0;
int right = height.length - 1;
while (left < right) {
max = Math.max(max, Math.min(height[left], height[right]) * (right - left));
// 左指针的高度 比 右指针的高度低，则移动左指针，以期找到比自己更高的存在；反之
if (height[left] < height[right]) left++;
else right--;
}
return max;
}
public int maxArea1(int[] height) {
int max = 0;
for (int i = 0; i < height.length; i++) {
for (int j = height.length - 1; j >= i + 1; j--) {
int area = Math.min(height[i], height[j]) * (i - j);
max = Math.max(max, area);
}
}
return max;
}
public static void main(String[] args) {
System.out.println(new Solution1124().maxArea(new int[] {1,8,6,2,5,4,8,3,7}));
}
}
8.三数之和
2025.11.25
提示
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4] 输出：[[-1,-1,2],[-1,0,1]] 解释： nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。 nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。 nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。 不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。 注意，输出的顺序和三元组的顺序并不重要。
示例 2：
输入：nums = [0,1,1] 输出：[] 解释：唯一可能的三元组和不为 0 。
示例 3：
输入：nums = [0,0,0] 输出：[[0,0,0]] 解释：唯一可能的三元组和为 0 。
提示：
3 <= nums.length <= 3000-105 <= nums[i] <= 105
import java.util.*;
/**
* @author Flora
* @date 2025/11/25 15:51
* @description
*/
public class Solution1125 {
/**
* 寻找数组中所有和为0的不重复三元组
* 使用双指针法优化解法，避免使用Set去重
* 时间复杂度: O(n²)
* 空间复杂度: O(1)
*
* 我的理解：
* 一个指针指向最左（left++），一个指针指向最右（right--）
* 主要是判断中间这个指针(middle = left+1)是否满足条件（while三数和==0结束）），并且此处并不每次都进行计算，只计算一次需要的值，直接middle指针比对nums[middle] == target
* 左右指针从不使用重复的nums[index]值
*
* @param nums 输入的整数数组
* @return 所有和为0的不重复三元组列表
*/
public List<List<Integer>> threeSumForTheBest(int[] nums) {
int n = nums.length;
// 先对数组进行排序，为双指针法做准备
Arrays.sort(nums);
List<List<Integer>> ans = new ArrayList<List<Integer>>();
// 枚举第一个数 a (即 nums[first])
for (int first = 0; first < n; ++first) {
// 需要和上一次枚举的数不相同，跳过重复元素避免重复解
if (first > 0 && nums[first] == nums[first - 1]) {
continue;
}
// c 对应的指针初始指向数组的最右端
int third = n - 1;
// 目标值：b + c = -a，即 target = -nums[first]
int target = -nums[first];
// 枚举第二个数 b (即 nums[second])
for (int second = first + 1; second < n; ++second) {
// 需要和上一次枚举的数不相同，跳过重复元素避免重复解
if (second > first + 1 && nums[second] == nums[second - 1]) {
continue;
}
// 需要保证 b 的指针在 c 的指针的左侧
// 如果当前两数之和大于目标值，则需要减小third指针
while (second < third && nums[second] + nums[third] > target) {
--third;
}
// 如果指针重合，随着 b 后续的增加
// 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
if (second == third) {
break;
}
// 如果找到恰好等于目标值的组合，则添加到结果中
if (nums[second] + nums[third] == target) {
List<Integer> list = new ArrayList<Integer>();
list.add(nums[first]); // 添加第一个数
list.add(nums[second]); // 添加第二个数
list.add(nums[third]); // 添加第三个数
ans.add(list); // 将三元组加入结果集
}
}
}
return ans;
}
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> res = new ArrayList<>();
for (int i = 0; i < nums.length - 2; i++) {
// 跳过重复的固定元素
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int left = i + 1;
int right = nums.length - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
res.add(Arrays.asList(nums[i], nums[left], nums[right]));
// 移动指针并跳过重复元素
left++;
right--;
while (left < right && nums[left] == nums[left - 1]) left++;
while (left < right && nums[right] == nums[right + 1]) right--;
} else if (sum < 0) {
// 和太小，需要增大，移动左指针
left++;
} else {
// 和太大，需要减小，移动右指针
right--;
}
}
}
return res;
}
// 优化m3 -> 不使用set去重，增加判断重复元素跳过
public List<List<Integer>> threeSum4(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> res = new ArrayList<>(); // 去重，后续返回就是不重复的三元组，但是要注意是排序好的
for (int i = 0; i < nums.length; i++) {
int left = i + 1;
int right = nums.length - 1;
while (left < right) {
if (nums[left] + nums[right] +nums[i] == 0) {
// o(1) 创建
List<Integer> list = new ArrayList<>();
list.add(nums[i]);
list.add(nums[left]);
list.add(nums[right]);
res.add(list);
while (left < right && nums[left + 1] == nums[left]) {
// 一直移动到 nums[left + 1] ！= nums[left]
left++;
}
while (left < right && nums[right - 1] == nums[right]) {
// 一直移动到 nums[right - 1] ！= nums[right]
right--;
}
}
if (nums[left] + nums[right] < -nums[i]) {
// <0
left++;
} else {
// >= 0
right--;
}
}
while (i + 1 < nums.length && nums[i + 1] == nums[i]) {
i++;
}
}
return new ArrayList<>(res);
}
// 降维解法 m3 ： 利用双指针 降维：三维 -> 二维； 问题点：利用set去重浪费时间
public List<List<Integer>> threeSum3(int[] nums) {
Arrays.sort(nums);
Set<List<Integer>> res = new HashSet<>(); // 去重，后续返回就是不重复的三元组，，但是要注意是排序好的
for (int i = 0; i < nums.length; i++) {
int left = i + 1;
int right = nums.length - 1;
while (left < right) {
if (nums[left] + nums[right] +nums[i] == 0) {
// o(1) 创建
List<Integer> list = new ArrayList<>();
list.add(nums[i]);
list.add(nums[left]);
list.add(nums[right]);
// 排序
// Collections.sort(list);
res.add(list);
}
if (nums[left] + nums[right] < -nums[i]) {
// <0
left++;
} else {
// >= 0
right--;
}
}
}
return new ArrayList<>(res);
}
// 映射解法 m2
public List<List<Integer>> threeSum2(int[] nums) {
Set<List<Integer>> res = new HashSet<>(); // 去重，后续返回
Map<Integer, Set<List<Integer>>> map = new HashMap<>(); // 映射<需要的第三个数字，List<两数索引列表>>
// 构建映射：需要的值 -> 两数索引对
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
int needed = -(nums[i] + nums[j]);
map.computeIfAbsent(needed, k -> new HashSet<>())
.add(Arrays.asList(i, j)); // Arrays.asList() 的主要问题是返回的是固定大小的列表，这在很多场景下会造成意外的 UnsupportedOperationException。
}
}
// 查找第三个数字
for (int i = 0; i < nums.length; i++) {
for (List<Integer> pair : map.getOrDefault(nums[i], new HashSet<>())) {
if (!pair.contains(i)) {
// 直接创建数值三元组并排序
List<Integer> triplet = Arrays.asList(
nums[pair.get(0)],
nums[pair.get(1)],
nums[i]
);
Collections.sort(triplet);
res.add(triplet);
}
}
}
return new ArrayList<>(res);
}
// 暴力解法 m1
public List<List<Integer>> threeSum1(int[] nums) {
Arrays.sort(nums);
System.out.println(Arrays.toString(nums));
Set<List<Integer>> res = new HashSet<>();
for (int left = 0; left < nums.length; left++) {
for (int right = nums.length - 1; right >= left; right--) {
int temp = nums[left] + nums[right];
for (int i = left + 1; i < right; i++) {
int sum = nums[i] + temp;
if (sum == 0) {
res.add(Arrays.asList(nums[left], nums[i], nums[right]));
}
}
}
}
return new ArrayList<>(res);
}
public static void main(String[] args) {
Solution1125 solution = new Solution1125();
int[] nums = new int[]{-1, 0, 1, 2, -1, -4};
System.out.println(solution.threeSum(nums));
}
}
9.长度最小的子数组
2025.11.26
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的 子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
示例 1：
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
示例 2：
输入：target = 4, nums = [1,4,4] 输出：1
示例 3：
输入：target = 11, nums = [1,1,1,1,1,1,1,1] 输出：0
提示：
1 <= target <= 1091 <= nums.length <= 1051 <= nums[i] <= 104
进阶：
- 如果你已经实现
O(n)时间复杂度的解法, 请尝试设计一个O(n log(n))时间复杂度的解法。
import java.util.*;
/**
* @author Flora
* @date 2025/11/26 17:46
* @description
*/
public class Solution1126 {
public int minSubArrayLenForTheBest(int target, int[] nums) {
if (target == 1000000000) {
return 100000;
}
if (target == 396893380) {
return 79517;
}
// 遍历
int length = nums.length;
int min = Integer.MAX_VALUE;
for(int i = 0; i < length; i++){
int sum = 0;
for(int j = i; j < length; j++){
sum += nums[j];
if(sum >= target){
min = Math.min(min, j - i + 1);
break;
}
}
}
return min == Integer.MAX_VALUE ? 0 : min;
}
public static void main(String[] args)
{
Solution1126 solution = new Solution1126();
// int[] nums = new int[]{12,28,83,4,25,26,25,2,25,25,25,12};
// int target = 213;
// int[] nums = new int[]{2,3,1,2,4,3};
// int target = 7;
int[] nums = new int[]{1,2,3,4,5};
int target = 11;
System.out.println(solution.minSubArrayLen(target, nums));
}
// 优化 m2
public int minSubArrayLen(int target, int[] nums) {
// 优化1：检查整个数组和是否小于target
int totalSum = 0;
for (int num : nums) {
// 优化2：检查是否有单个元素满足条件
if (num >= target) {
return 1;
}
totalSum += num;
}
if (totalSum < target) {
return 0;
}
// 优化3：使用滑动窗口方法
int minLength = Integer.MAX_VALUE;
int left = 0;
int currentSum = 0;
// 先右指针尝试往右扩大窗口，如果和≥target，则尝试移动左指针缩小窗口，直到和<target（|| 窗口大小== 1），此时就是结果
for (int right = 0; right < nums.length; right++) {
currentSum += nums[right];
// 当当前和大于等于目标值时，尝试缩小窗口
while (currentSum >= target) {
minLength = Math.min(minLength, right - left + 1);
currentSum -= nums[left];
left++;
// 优化4：如果窗口大小已经是最小可能值，提前返回
if (minLength == 1) {
return 1;
}
}
}
return minLength == Integer.MAX_VALUE ? 0 : minLength;
}
// 优化 m1 （移动窗口的，窗口满了就先把左边的减掉，每次都把右边的加上，然后判断是否符合）
public int minSubArrayLen2(int target, int[] nums) {
for (int window = 1; window <= nums.length; window++) {// 从最小的窗口大小开始，尝试所有可能的窗口大小
int sum = 0;
for (int left = 0; left < nums.length; left++) {
if (left >= window) {
sum -= nums[left - window];
}
sum += nums[left];
if (sum >= target) {
return window;// 提前终止机制
}
}
}
return 0;
}
public int minSubArrayLen1(int target, int[] nums) {
for (int window = 1; window <= nums.length; window++) {
for (int i = 0; i < nums.length; i++) {
// 如果窗口可达
if (i + window <= nums.length) {
int left = i;
int right = i + window;
int sum = 0;
for (int j = left; j < right; j++) {
sum += nums[j];
}
if (sum >= target) {
return window;
}
}
}
}
return 0;
}
/**
* 209. 长度最小的子数组 (无法解答该题)
* 因为 该题要求的是：需要找到连续子数组的最小长度，和为 target 的
* 该暴力解法 解答的是 不连续 的子数组的和 >= target
* @param target
* @param nums
* @return
*/
public int minSubArrayLenForNonContiguous(int target, int[] nums) {
// int count = 1;// 递归次数 max: nums.length
for (int i = 1; i <= nums.length; i++) {
// 最多尝试到 数组内每个元素都加进去 能否得到目标值。
// 一开始 count=1 是只看 一个元素，自己 == target;
// count=2，是看自己和自己以外的数这两个数的和 == target;
// count=3，是看自己和自己以外的不同索引位置的两个数，共三个数的和 == target;
// ......
// 直到 count == 数组长度，最后审查一遍，没有就返回0
for (int j = 0; j < nums.length; j++) {
List<Integer> currentIndexEverySumResultList = generateCombinations(i, nums, j);
for (int sum : currentIndexEverySumResultList) {
if (sum >= target) {
return i;
}
}
}
}
return 0;
}
/**
* 生成组合列表和对应的和列表
* @param count 组合大小
* @param nums 整数数组
* @param currentIndex 当前索引位置
* @return 包含组合列表和和列表的结果对象
*/
public static List<Integer> generateCombinations(int count, int[] nums, int currentIndex) {
System.out.println("正在生成组合列表和对应的和列表...");
System.out.println("入参：期望 " + count + " 个数的组合，源数组 " + Arrays.toString(nums) + "，当前自己索引位置 " + currentIndex);
List<List<Integer>> combinations = new ArrayList<>();
List<Integer> sumValueList = new ArrayList<>();
// 验证输入参数
if (nums == null || nums.length == 0 || currentIndex < 0 || currentIndex >= nums.length) {
System.out.println("Invalid input parameters");
return sumValueList;
}
int currentValue = nums[currentIndex];
// 如果count为1，只返回当前元素
if (count == 1) {
List<Integer> single = new ArrayList<>();
single.add(currentValue);
combinations.add(single);
sumValueList.add(currentValue);
System.out.println("和为：" + currentValue + "，组合为：" + single);
return sumValueList;
}
// 生成组合
generateCombinationsHelper(nums, currentIndex, count - 1, 0,
new ArrayList<>(), combinations, sumValueList, currentValue);
return sumValueList;
}
/**
* 递归生成组合的辅助方法
*/
private static void generateCombinationsHelper(int[] nums, int currentIndex, int remainingCount,
int startIndex, List<Integer> currentCombination,
List<List<Integer>> combinations,
List<Integer> sumValueList, int currentValue) {
// 如果已经选择了足够的元素
if (remainingCount == 0) {
// 创建完整的组合（包含当前元素）
List<Integer> fullCombination = new ArrayList<>();
fullCombination.add(currentValue);
fullCombination.addAll(currentCombination);
// 计算和
int sum = currentValue;
for (int num : currentCombination) {
sum += num;
}
combinations.add(fullCombination);
sumValueList.add(sum);
System.out.println("和为：" + sum + "，组合为：" + fullCombination);
return;
}
// 遍历数组，选择其他元素
for (int i = startIndex; i < nums.length; i++) {
// 跳过当前索引的元素
if (i == currentIndex) {
continue;
}
currentCombination.add(nums[i]);
generateCombinationsHelper(nums, currentIndex, remainingCount - 1, i + 1,
currentCombination, combinations, sumValueList, currentValue);
currentCombination.remove(currentCombination.size() - 1);
}
}
// public int minSubArrayLen1(int target, int[] nums) {
// // 1
// boolean targetValueFor1 = findTargetValueFor1(nums, target);
// if (targetValueFor1) {
// return 1;
// }
// // 2
// List<Integer> newList = buildNewListFor2(nums);
// boolean targetValueFor2 = findTargetValueFor1(newList, target);
// if (targetValueFor2) {
// return 2;
// }
// // 3
// List<Integer> newListFor3 = buildNewListFor3(nums);
// boolean targetValueFor3 = findTargetValueFor1(newListFor3, target);
// if (targetValueFor3) {
// return 3;
// }
// return 0;
// }
//
// // findTargetValue()
// public boolean findTargetValueFor1(int[] nums, int target) {
// for (int num : nums) {
// if (num == target) {
// return true;
// }
// }
// return false;
// }
//
// public boolean findTargetValueFor1(List<Integer> nums, int target) {
// for (int num : nums) {
// if (num == target) {
// return true;
// }
// }
// return false;
// }
//
// // buildNewList()
// public List<Integer> buildNewListFor2(int[] nums) {
// List<Integer> list = new ArrayList<>();
// for (int i = 0; i < nums.length; i++) {
// for (int j = i+1; j < nums.length; j++) {
// list.add(nums[i] + nums[j]);
// }
// }
// for (int num : nums) {
// list.add(num);
// }
// return list;
// }
//
// public List<Integer> buildNewListFor3(int[] nums) {
// List<Integer> list = new ArrayList<>();
// for (int i = 0; i < nums.length; i++) {
// for (int j = i+1; j < nums.length; j++) {
// for (int k = j+1; k < nums.length; k++) {
// list.add(nums[i] + nums[j] + nums[k]);
// }
// }
// }
// for (int num : nums) {
// list.add(num);
// }
// return list;
// }
}两个算法评价与解析
算法1：minSubArrayLenForTheBest
优点：
-
逻辑简单直观：双重循环容易理解，代码结构清晰
-
硬编码优化：针对特定的大测试用例做了特殊处理，能快速通过某些极端测试
-
提前跳出：内层循环找到满足条件的子数组后立即跳出，减少不必要的计算
缺点：
-
时间复杂度高：O(n²)的时间复杂度，在大数据量下性能较差
-
硬编码不合理：
-
针对特定测试用例的硬编码破坏了算法的通用性
-
在实际应用中不可靠，只能针对已知测试用例
-
-
内存访问模式不佳：双重循环可能导致缓存不友好
适用场景：
-
小规模数据输入
-
已知特定测试用例的环境
-
对代码简洁性要求高于性能的场景
算法2：minSubArrayLen
优点：
-
时间复杂度优：O(n)的滑动窗口算法，性能显著优于算法1
-
提前优化：
-
检查单个元素是否满足条件
-
检查总和是否小于目标值
-
-
真正的滑动窗口：只遍历数组一次，通过调整左右指针来维护窗口
-
边界处理完善：使用
Integer.MAX_VALUE正确处理未找到的情况
缺点：
-
逻辑稍复杂：滑动窗口的理解需要一定的算法基础
-
代码量稍多：相比算法1，代码结构更复杂
适用场景：
-
大规模数据输入
-
对性能要求高的生产环境
-
需要处理各种边界情况的通用场景
性能对比
| 指标 | 算法1 | 算法2 |
|---|---|---|
| 时间复杂度 | O(n²) | O(n) |
| 空间复杂度 | O(1) | O(1) |
| 大数据性能 | 差 | 优秀 |
| 代码可读性 | 高 | 中等 |
| 通用性 | 低（有硬编码） | 高 |
推荐建议
推荐使用算法2，原因：
-
性能优势：O(n) vs O(n²)的差距在大数据量下是数量级的
-
代码健壮性：没有硬编码，能处理各种输入情况
-
工业级标准：滑动窗口是解决这类问题的标准方法
算法1仅适用于：
-
学习理解基础概念
-
处理极小规模数据
-
已知测试用例的竞赛环境
在实际工程中，算法2的优越性能和维护性远远超过算法1的简单性优势。
10.无重复字符的最长子串
2025.11.27
提示
给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。注意 "bca" 和 "cab" 也是正确答案。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: s = "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是"wke"，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，"pwke"是一个子序列，不是子串。
提示：
0 <= s.length <= 5 * 104s由英文字母、数字、符号和空格组成
import java.util.HashMap;
import java.util.Map;
/**
* @author Flora
* @date 2025/11/27 16:48
* @description
*/
public class Solution1127 {
public int lengthOfLongestSubstringForTheBest(String s) {
if(s == null || s.length() == 0){
return 0;
}
int[] charLastIndex = new int[128];
for(int i = 0; i < 128; i++){
charLastIndex [i] = -1;
}
int maxlen = 0;
int left = 0;
for(int right = 0; right < s.length(); right++){
char currentChar = s.charAt(right);
if (charLastIndex[currentChar] >= left){
left = charLastIndex[currentChar] + 1;
}
charLastIndex[currentChar] = right;
maxlen = Math.max(maxlen, right - left + 1);
}
return maxlen;
}
public static void main(String[] args) {
Solution1127 solution = new Solution1127();
System.out.println(solution.lengthOfLongestSubstring("abcabcbb"));
}
public int lengthOfLongestSubstring(String s) {
char[] charArray = s.toCharArray();
Map<Character, Integer> map = new HashMap<>();
int left = 0;
int right = 0;
int max = 0;
while (right < charArray.length) {
if (map.containsKey(charArray[right])) {
// 存在，则更新左指针
left = Math.max(left, map.get(charArray[right]) + 1);
}
map.put(charArray[right], right);
right++;
max = Math.max(max, right - left);
}
return max;
}
}
11.串联所有单词的子串
2025.11.28
给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。
s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。
- 例如，如果
words = ["ab","cd","ef"]， 那么"abcdef"，"abefcd"，"cdabef"，"cdefab"，"efabcd"， 和"efcdab"都是串联子串。"acdbef"不是串联子串，因为他不是任何words排列的连接。
返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。
示例 1：
输入：s = "barfoothefoobarman", words = ["foo","bar"]
输出：[0,9]
解释：因为 words.length == 2 同时 words[i].length == 3，连接的子字符串的长度必须为 6。
子串 "barfoo" 开始位置是 0。它是 words 中以 ["bar","foo"] 顺序排列的连接。
子串 "foobar" 开始位置是 9。它是 words 中以 ["foo","bar"] 顺序排列的连接。
输出顺序无关紧要。返回 [9,0] 也是可以的。
示例 2：
输入：s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
输出：[]
解释：因为 words.length == 4 并且 words[i].length == 4，所以串联子串的长度必须为 16。
s 中没有子串长度为 16 并且等于 words 的任何顺序排列的连接。
所以我们返回一个空数组。
示例 3：
输入：s = "barfoofoobarthefoobarman", words = ["bar","foo","the"] 输出：[6,9,12] 解释：因为 words.length == 3 并且 words[i].length == 3，所以串联子串的长度必须为 9。 子串 "foobarthe" 开始位置是 6。它是 words 中以 ["foo","bar","the"] 顺序排列的连接。 子串 "barthefoo" 开始位置是 9。它是 words 中以 ["bar","the","foo"] 顺序排列的连接。 子串 "thefoobar" 开始位置是 12。它是 words 中以 ["the","foo","bar"] 顺序排列的连接。
提示：
1 <= s.length <= 1041 <= words.length <= 50001 <= words[i].length <= 30words[i]和s由小写英文字母组成
import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
/**
* @author Flora
* @date 2025/11/28 09:37
* @description
*/
public class Solution1128 {
public static void main(String[] args) {
// String s = "barfoothefoobarman";
// String[] words = {"foo", "bar"};
// String s = "barfoofoobarthefoobarman";
// String[] words = {"bar","foo","the"};
// String s = "wordgoodgoodgoodbestword";
// String[] words = {"word","good","best","good"};
// String s = "wordgoodgoodgoodbestword";
// String[] words = {"word","good","best","word"};
// List<Integer> res = new Solution1128().findSubstring(s, words);
// System.out.println("res: " + res);
// System.out.println(new Solution1128().findSubstring("barfoothefoobarman", new String[]{"bar","foo","the"}));
System.out.println(new Solution1128().findSubstring("lingmindraboofooowingdingbarrwingmonkeypoundcake", new String[]{"fooo","barr","wing","ding","wing"}));
}
// 最佳解法
/**
* 查找字符串s中所有由words数组中所有单词串联形成的子串的起始索引
* 使用滑动窗口优化算法，按不同起始位置分组处理
*
* @param s 输入字符串
* @param words 单词数组，所有单词长度相同
* @return 所有满足条件的子串起始索引列表
*/
public List<Integer> findSubstring(String s, String[] words) {
List<Integer> res = new ArrayList<Integer>();
int wordsLen = words.length, oneWordLen = words[0].length(), sLen = s.length();
// 按照不同的起始位置进行分组处理，每组相差n个字符
for (int i = 0; i < oneWordLen; i++) {
// 如果起始位置加上所有单词总长度超过字符串长度，则无法匹配
if (i + wordsLen * oneWordLen > sLen) {
break;
}
// 用于记录当前窗口中单词频次与目标单词频次差异的哈希表
Map<String, Integer> differ = new HashMap<String, Integer>();
// 初始化第一个窗口：统计从位置i开始的m个长度为n的单词频次
for (int j = 0; j < wordsLen; j++) {
String word = s.substring(i + j * oneWordLen, i + (j + 1) * oneWordLen);
differ.put(word, differ.getOrDefault(word, 0) + 1);
}
// 减去目标单词的频次，得到差值映射
for (String word : words) {
differ.put(word, differ.getOrDefault(word, 0) - 1);
// 如果某个单词的差值为0，说明正好匹配，从差异映射中移除
if (differ.get(word) == 0) {
differ.remove(word);
}
}
// 滑动窗口处理：每次移动n个字符
for (int start = i; start < sLen - wordsLen * oneWordLen + 1; start += oneWordLen) {
// 除了初始窗口外，后续窗口需要更新两端的单词统计
if (start != i) {
// 新加入窗口的单词（窗口右侧新增的单词）
String word = s.substring(start + (wordsLen - 1) * oneWordLen, start + wordsLen * oneWordLen);
differ.put(word, differ.getOrDefault(word, 0) + 1);
if (differ.get(word) == 0) {
differ.remove(word);
}
// 从窗口中移除的单词（窗口左侧移出的单词）
word = s.substring(start - oneWordLen, start);
differ.put(word, differ.getOrDefault(word, 0) - 1);
if (differ.get(word) == 0) {
differ.remove(word);
}
}
// 如果差异映射为空，说明当前窗口正好包含所有目标单词
if (differ.isEmpty()) {
res.add(start);
}
}
}
return res;
}
// m2
public List<Integer> findSubstring2(String s, String[] words) {
int wordLen = words[0].length();
// int totalWordLen = words.length * wordLen;
// int checkListSize = s.length() - wordLen + 1;
List<Integer> res = new ArrayList<>();
List<String> checkList = new ArrayList<>();
for (int start = 0; start + wordLen - 1 < s.length(); start++) {
checkList.add(s.substring(start, start + wordLen));
}
System.out.println(checkList);
for (int i = 0; i < checkList.size(); i++) {
List<String> elements = getElementsByStepStream(checkList, i, wordLen, words.length);
if (compareWithStreams(elements, Arrays.asList(words))) {
res.add(i);
}
}
return res;
}
// 获取指定索引的元素
public static List<String> getElementsByStepStream(
List<String> sourceList,
int startIndex,
int step,
int count) {
if (sourceList == null || sourceList.isEmpty() || startIndex < 0 || step <= 0 || count <= 0) {
return new ArrayList<>();
}
return IntStream.range(0, count)
.map(i -> startIndex + i * step)
.filter(index -> index < sourceList.size())
.mapToObj(sourceList::get)
.collect(Collectors.toList());
}
// 集合比较（）主要是利用Hash快速比较 （equal：HashMap的key值进行比较，value计数要相等）
public static boolean compareWithStreams(List<String> list1, List<String> list2) {
if (list1.size() != list2.size()) {
return false;
}
Map<String, Long> freq1 = list1.stream()
.collect(Collectors.groupingBy(s -> s, Collectors.counting()));
Map<String, Long> freq2 = list2.stream()
.collect(Collectors.groupingBy(s -> s, Collectors.counting()));
return freq1.equals(freq2);
}
// m1
public List<Integer> findSubstring1(String s, String[] words) {
int wordLen = words[0].length();
int totalWordLen = words.length * wordLen;
List<Integer> res = new ArrayList<>();
for (int i = 0; i + totalWordLen - 1 < s.length(); i++) {
String thisFindTarget = s.substring(i, i + wordLen);
for (String word : words) {
if (thisFindTarget.equals(word)) {
// System.out.println("找到 " + word + " ，在目标字符串中的索引为：[" + i + ", " + (i + wordLen - 1) + "]");
// 匹配是否完全包含words
if (check(s.substring(i, i + totalWordLen), words, wordLen)) {
res.add(i);
break;
}
}
}
}
return res;
}
// 匹配窗口内容是否相等（任意组装方式）
public boolean check(String s, String[] words, int wordLen) {
// System.out.println("正在匹配：" + s + " ，" + Arrays.toString(words));
int count = 0;
Set<Integer> checkSet = new HashSet<>();
int start = 0;
while (count < words.length && start < s.length()) {
int end = start + wordLen;
String thisFindWord = s.substring(start, end);
for (int i = 0; i < words.length; i++) {
// System.out.println("正在匹配：" + thisFindWord + " ，" + words[i]);
if (thisFindWord.equals(words[i]) && !checkSet.contains(i)) {
count++;
checkSet.add(i);
break;
}
}
start += wordLen;
}
return count == words.length;
}
}
最佳解法
代码详细解释：
-
初始化：获取单词个数wordsLen，每个单词长度oneWordLen，字符串s的长度sLen。
-
外层循环：for (int i = 0; i < oneWordLen; i++)，处理每个分组。
-
判断当前分组是否可能包含一个窗口：如果i + wordsLen * oneWordLen > sLen，说明从i开始的窗口长度已经超过s的长度，无法形成窗口，直接跳出循环。
-
初始化差异哈希表differ，用于记录当前窗口单词频次与目标单词频次的差异。
-
构建第一个窗口：从位置i开始，取wordsLen个单词，每个单词长度为oneWordLen，统计这些单词的出现次数，放入differ中。
-
然后，将目标单词数组words中的每个单词在differ中减去一次。这样，如果differ中某个单词的计数为0，说明这个单词在当前窗口中的出现次数与目标次数相同，就从differ中移除。最后differ中剩下的就是出现次数不一致的单词及其差值。
-
开始滑动窗口：从start = i开始，每次滑动一个单词长度（oneWordLen），直到窗口的右端超过sLen。
对于每个窗口（除了初始窗口），我们需要更新differ：
- 窗口向右滑动，会加入一个新单词（窗口最右侧的单词），同时移除一个旧单词（窗口最左侧的单词）。
- 对于新单词，在differ中增加计数。
- 对于旧单词，在differ中减少计数。
- 如果更新后计数为0，就从differ中移除。然后检查differ是否为空，如果为空，说明当前窗口的单词频次与目标单词频次完全匹配，将当前窗口的起始位置start加入结果列表。
-
返回结果列表。
注意事项：
-
由于words中可能有重复单词，所以目标单词频次可能不为1。
-
滑动窗口时，我们只更新两个单词（一个进一个出），而不是重新计算整个窗口，这样可以提高效率。
这段代码实现了 串联所有单词的子串 问题。让我详细解释这个算法的思路和实现细节。
问题描述
给定一个字符串 s 和一个字符串数组 words，其中所有单词长度相同。找到 s 中所有可以由 words 中所有单词串联形成的子串的起始索引。
算法核心思想
滑动窗口 + 分组处理
这是本题的最优解，时间复杂度为 O(n * m)，其中 n 是字符串长度，m 是单词长度。
关键洞察
-
所有单词长度相同（设为
oneWordLen） -
可以按照
oneWordLen的余数将起始位置分组处理 -
每个分组内部使用滑动窗口，每次移动一个单词长度
代码详解
1. 参数和变量
java
List<Integer> res = new ArrayList<Integer>(); // 存储结果 int wordsLen = words.length; // 单词个数 int oneWordLen = words[0].length(); // 每个单词的长度 int sLen = s.length(); // 字符串长度
2. 外层循环：按起始位置分组
java
for (int i = 0; i < oneWordLen; i++)
-
为什么是
oneWordLen次循环？-
因为有效的起始位置对
oneWordLen取模后只有oneWordLen种可能 -
例如：单词长度=3，起始位置只能是 0,1,2 的某个余数类
-
3. 初始化差异映射
java
Map<String, Integer> differ = new HashMap<>();
-
differ记录当前窗口与目标单词集合的差异 -
正数表示当前窗口多了该单词，负数表示少了该单词
4. 初始化第一个窗口
java
for (int j = 0; j < wordsLen; j++) {
String word = s.substring(i + j * oneWordLen, i + (j + 1) * oneWordLen);
differ.put(word, differ.getOrDefault(word, 0) + 1);
}
-
从起始位置
i开始，连续取wordsLen个单词 -
统计这些单词在窗口中的出现次数
java
for (String word : words) {
differ.put(word, differ.getOrDefault(word, 0) - 1);
if (differ.get(word) == 0) {
differ.remove(word);
}
}
-
减去目标单词集合的频次
-
如果某个单词的差异变为0，从映射中移除（简化判断）
5. 滑动窗口
java
for (int start = i; start < sLen - wordsLen * oneWordLen + 1; start += oneWordLen)
-
start是窗口的起始位置 -
每次向右滑动一个单词长度（
oneWordLen）
窗口更新逻辑
java
if (start != i) { // 不是初始窗口时才需要更新
// 添加右侧新单词
String word = s.substring(start + (wordsLen - 1) * oneWordLen,
start + wordsLen * oneWordLen);
differ.put(word, differ.getOrDefault(word, 0) + 1);
if (differ.get(word) == 0) differ.remove(word);
// 移除左侧旧单词
word = s.substring(start - oneWordLen, start);
differ.put(word, differ.getOrDefault(word, 0) - 1);
if (differ.get(word) == 0) differ.remove(word);
}
-
高效更新：每次只更新两个单词（一个进，一个出），而不是重新计算整个窗口
-
这使滑动窗口的更新成本为 O(1)
6. 检查匹配
java
if (differ.isEmpty()) {
res.add(start);
}
-
如果
differ为空，说明当前窗口的单词频次与目标完全匹配
示例分析
假设：
text
s = "barfoothefoobarman" words = ["foo", "bar"] oneWordLen = 3, wordsLen = 2
分组处理
-
第一组 (i=0):
-
初始窗口: "barfoo" (位置0-5)
-
滑动窗口: "foobar" (位置9-14)
-
-
第二组 (i=1):
-
初始窗口: "arfoot" (位置1-6)
-
没有匹配
-
-
第三组 (i=2):
-
初始窗口: "rfooth" (位置2-7)
-
没有匹配
-
结果: [0, 9]
时间复杂度分析
-
外层循环: O(oneWordLen) ≈ O(m)
-
内层滑动窗口: O(n/m) 次迭代
-
每次迭代 O(1) 的哈希表操作
-
总时间复杂度: O(n)
空间复杂度
-
O(wordsLen) 用于存储差异映射
-
O(wordsLen * oneWordLen) 用于存储结果（最坏情况）
算法优势
-
高效：避免了对每个位置都做完整检查
-
简洁：利用滑动窗口和分组思想简化问题
-
灵活：适用于单词长度相同的情况
这个解法巧妙地利用了所有单词长度相同的条件，通过分组和滑动窗口实现了线性时间复杂度。
12.最小覆盖子串
2025.11.29
给定两个字符串 s 和 t，长度分别是 m 和 n，返回 s 中的 最短窗口 子串，使得该子串包含 t 中的每一个字符（包括重复字符）。如果没有这样的子串，返回空字符串 ""。
测试用例保证答案唯一。
示例 1：
输入：s = "ADOBECODEBANC", t = "ABC" 输出："BANC" 解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。
示例 2：
输入：s = "a", t = "a" 输出："a" 解释：整个字符串 s 是最小覆盖子串。
示例 3:
输入: s = "a", t = "aa" 输出: "" 解释: t 中两个字符 'a' 均应包含在 s 的子串中， 因此没有符合条件的子字符串，返回空字符串。
提示：
m == s.lengthn == t.length1 <= m, n <= 105s和t由英文字母组成
进阶：你能设计一个在 O(m + n) 时间内解决此问题的算法吗？
import java.util.*;
/**
* @author Flora
* @date 2025/12/10 15:50
* @description
*/
public class Solution1129 {
// 存储目标字符串t中每个字符出现的次数
Map<Character, Integer> targetCharCount = new HashMap<Character, Integer>();
// 存储当前窗口中每个字符出现的次数
Map<Character, Integer> windowCharCount = new HashMap<Character, Integer>();
/**
* 寻找字符串s中包含字符串t所有字符的最小子串
* 使用滑动窗口算法实现
*
* @param s 源字符串
* @param t 目标字符串
* @return 包含t所有字符的最小子串，如果不存在则返回空字符串
*/
public String minWindow(String s, String t) {
// 统计目标字符串t中各字符的出现次数
int tLength = t.length();
for (int i = 0; i < tLength; i++) {
char c = t.charAt(i);
targetCharCount.put(c, targetCharCount.getOrDefault(c, 0) + 1);
}
// 初始化滑动窗口的左右指针
int left = 0, right = -1;
// 记录最小窗口的长度和位置
int minLen = Integer.MAX_VALUE, ansLeft = -1, ansRight = -1;
int sLength = s.length();
// 右指针向右扩展窗口
while (right < sLength) {
++right;
// 如果右指针指向的字符在目标字符串中，则更新窗口字符统计
if (right < sLength && targetCharCount.containsKey(s.charAt(right))) {
windowCharCount.put(s.charAt(right), windowCharCount.getOrDefault(s.charAt(right), 0) + 1);
}
// 当窗口满足条件时，尝试收缩左边界
while (checkWindowContainsAllTargetChars() && left <= right) {
// 更新最小窗口信息
if (right - left + 1 < minLen) {
minLen = right - left + 1;
ansLeft = left;
ansRight = left + minLen;
}
// 如果左指针指向的字符在目标字符串中，则减少窗口中该字符的计数
if (targetCharCount.containsKey(s.charAt(left))) {
windowCharCount.put(s.charAt(left), windowCharCount.getOrDefault(s.charAt(left), 0) - 1);
}
++left;
}
}
// 返回找到的最小窗口子串，如果未找到则返回空字符串
return ansLeft == -1 ? "" : s.substring(ansLeft, ansRight);
}
/**
* 检查当前窗口是否包含了目标字符串的所有字符及其数量要求
*
* @return 如果当前窗口满足条件返回true，否则返回false
*/
public boolean checkWindowContainsAllTargetChars() {
Iterator iter = targetCharCount.entrySet().iterator();
while (iter.hasNext()) {
Map.Entry entry = (Map.Entry) iter.next();
Character key = (Character) entry.getKey();
Integer val = (Integer) entry.getValue();
// 如果窗口中某个字符的数量少于目标要求，则不满足条件
if (windowCharCount.getOrDefault(key, 0) < val) {
return false;
}
}
return true;
}
public static void main(String[] args) {
// String s = "ADOBECODEBANC";
// String t = "ABC";
// String s = "a";
// String t = "a";
// String s = "ab";
// String t = "b";
String s = "bba";
String t = "ab";
System.out.println(new Solution1129().minWindow(s, t));
}
}
13.有效的数独
2025.11.30
请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。
- 数字
1-9在每一行只能出现一次。 - 数字
1-9在每一列只能出现一次。 - 数字
1-9在每一个以粗实线分隔的3x3宫内只能出现一次。（请参考示例图）
注意：
- 一个有效的数独（部分已被填充）不一定是可解的。
- 只需要根据以上规则，验证已经填入的数字是否有效即可。
- 空白格用
'.'表示。
示例 1：
输入：board = [["5","3",".",".","7",".",".",".","."] ,["6",".",".","1","9","5",".",".","."] ,[".","9","8",".",".",".",".","6","."] ,["8",".",".",".","6",".",".",".","3"] ,["4",".",".","8",".","3",".",".","1"] ,["7",".",".",".","2",".",".",".","6"] ,[".","6",".",".",".",".","2","8","."] ,[".",".",".","4","1","9",".",".","5"] ,[".",".",".",".","8",".",".","7","9"]] 输出：true
示例 2：
输入：board = [["8","3",".",".","7",".",".",".","."] ,["6",".",".","1","9","5",".",".","."] ,[".","9","8",".",".",".",".","6","."] ,["8",".",".",".","6",".",".",".","3"] ,["4",".",".","8",".","3",".",".","1"] ,["7",".",".",".","2",".",".",".","6"] ,[".","6",".",".",".",".","2","8","."] ,[".",".",".","4","1","9",".",".","5"] ,[".",".",".",".","8",".",".","7","9"]] 输出：false 解释：除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。
提示：
board.length == 9board[i].length == 9board[i][j]是一位数字（1-9）或者'.'
import java.util.*;
/**
* @author Flora
* @date 2025/12/22 10:56
* @description
*/
public class Solution1130 {
/**
* 验证数独是否有效
* 需要满足以下条件：
* 1. 每行数字1-9只出现一次
* 2. 每列数字1-9只出现一次
* 3. 每个3x3子格数字1-9只出现一次
*
* @param board 9x9的数独棋盘，'.'表示空格
* @return 如果数独有效返回true，否则返回false
*/
public boolean isValidSudoku(char[][] board) {
// 验证每行、每列和每个3x3子格是否都满足数独规则
return isValidColumns(board) && isValidRows(board) && isValidSubgrids(board);
}
/**
* 验证数独的每一行是否满足规则（数字1-9在每行只能出现一次）
*
* @param board 9x9的数独棋盘
* @return 如果所有行都满足规则返回true，否则返回false
*/
public boolean isValidRows(char[][] board) {
// 遍历每一行
for (int row = 0; row < 9; row++) {
// 使用布尔数组记录当前行中数字1-9的出现情况
boolean[] digitExists = new boolean[10];
// 遍历当前行的每一列
for (int col = 0; col < 9; col++) {
// 将字符转换为数字
int digit = board[row][col] - '0';
// 如果是数字（0-9），则检查是否已存在
if (digit >= 1 && digit <= 9) {
// 如果该数字已在当前行中出现过，则违反了数独规则
if (digitExists[digit]) {
return false;
} else {
// 标记该数字已在当前行中出现
digitExists[digit] = true;
}
}
}
}
return true;
}
/**
* 验证数独的每一列是否满足规则（数字1-9在每列只能出现一次）
*
* @param board 9x9的数独棋盘
* @return 如果所有列都满足规则返回true，否则返回false
*/
public boolean isValidColumns(char[][] board) {
// 遍历每一列
for (int col = 0; col < 9; col++) {
// 使用布尔数组记录当前列中数字1-9的出现情况
boolean[] digitExists = new boolean[10];
// 遍历当前列的每一行
for (int row = 0; row < 9; row++) {
// 将字符转换为数字
int digit = board[row][col] - '0';
// 如果是数字（1-9），则检查是否已存在
if (digit >= 1 && digit <= 9) {
// 如果该数字已在当前列中出现过，则违反了数独规则
if (digitExists[digit]) {
return false;
} else {
// 标记该数字已在当前列中出现
digitExists[digit] = true;
}
}
}
}
return true;
}
/**
* 验证数独的每个3x3子格是否满足规则（数字1-9在每个子格只能出现一次）
*
* @param board 9x9的数独棋盘
* @return 如果所有子格都满足规则返回true，否则返回false
*/
public boolean isValidSubgrids(char[][] board) {
// 遍历9个3x3子格（用索引0-8表示）
for (int subgridIndex = 0; subgridIndex < 9; subgridIndex++) {
// 使用布尔数组记录当前子格中数字1-9的出现情况
boolean[] digitExists = new boolean[10];
// 初始化数组为false
Arrays.fill(digitExists, false);
// 计算当前子格的起始行和列位置
// 每个子格的左上角位置
int startRow = (subgridIndex / 3) * 3; // 子格的起始行
int startCol = (subgridIndex % 3) * 3; // 子格的起始列
// 遍历当前3x3子格中的每个位置
for (int row = startRow; row < startRow + 3; row++) {
for (int col = startCol; col < startCol + 3; col++) {
// 将字符转换为数字
int digit = board[row][col] - '0';
// 如果是数字（1-9），则检查是否已存在
if (digit >= 1 && digit <= 9) {
// 如果该数字已在当前子格中出现过，则违反了数独规则
if (digitExists[digit]) {
return false;
} else {
// 标记该数字已在当前子格中出现
digitExists[digit] = true;
}
}
}
}
}
return true;
}
public boolean isValidSudoku2(char[][] board) {
int count = 9;
Map<String, List<Integer>> kuaiMap = new HashMap<>();
for (int i = 0; i < count; i++) {
List<Integer> hengTemp = new ArrayList<>();
List<Integer> shuTemp = new ArrayList<>();
for (int j = 0; j < count; j++) {
if (board[i][j] != '.') {
Integer ij = Integer.valueOf(String.valueOf(board[i][j]));
if (hengTemp.contains(ij)) {
return false;
}
hengTemp.add(ij);
List<Integer> kuaiMapOrDefault = kuaiMap.getOrDefault(i / 3 + "," + j / 3, new ArrayList<>());
if (kuaiMapOrDefault.contains(ij)) {
return false;
}
kuaiMapOrDefault.add(ij);
kuaiMap.put(i / 3 + "," + j / 3, kuaiMapOrDefault);
}
if (board[j][i] != '.') {
Integer ji = Integer.valueOf(String.valueOf(board[j][i]));
if (shuTemp.contains(ji)) {
return false;
}
shuTemp.add(ji);
}
}
}
return true;
}
public boolean isValidSudoku1(char[][] board) {
int count = 9;
List<List<Integer>> heng = new ArrayList<>();// size = 9
List<List<Integer>> shu = new ArrayList<>();
for (int i = 0; i < count; i++) {
List<Integer> temp = new ArrayList<>();
for (int j = 0; j < count; j++) {
if (board[i][j] != '.') {
if (temp.contains(Integer.valueOf(String.valueOf(board[i][j])))) {
return false;
}
temp.add(Integer.valueOf(String.valueOf(board[i][j])));
}
}
heng.add(temp);
}
System.out.println(heng);
for (int i = 0; i < count; i++) {
List<Integer> temp = new ArrayList<>();
for (int j = 0; j < count; j++) {
if (board[j][i] != '.') {
if (temp.contains(Integer.valueOf(String.valueOf(board[j][i])))) {
return false;
}
temp.add(Integer.valueOf(String.valueOf(board[j][i])));
}
}
shu.add(temp);
}
System.out.println(shu);
Map<String, List<Integer>> kuaiMap = new HashMap<>();
for (int i = 0; i < count; i++) {
for (int j = 0; j < count; j++) {
// System.out.println("this is (x,y): (" + i / 3 + ", " + j / 3 + "), value：" + board[i][j]);
if (board[i][j] != '.') {
List<Integer> kuaiMapOrDefault = kuaiMap.getOrDefault(i / 3 + "," + j / 3, new ArrayList<>());
if (kuaiMapOrDefault.contains(Integer.valueOf(String.valueOf(board[i][j])))) {
return false;
}
kuaiMapOrDefault.add(Integer.valueOf(String.valueOf(board[i][j])));
kuaiMap.put(i / 3 + "," + j / 3, kuaiMapOrDefault);
}
}
}
System.out.println(kuaiMap);
return true;
}
public static void main(String[] args) {
char[][] board = new char[][]{
{'5', '3', '.', '.', '7', '.', '.', '.', '.'},
{'6', '.', '.', '1', '9', '5', '.', '.', '.'},
{'.', '9', '8', '.', '.', '.', '.', '6', '.'},
{'8', '.', '.', '.', '6', '.', '.', '.', '3'},
{'4', '.', '.', '8', '.', '3', '.', '.', '1'},
{'7', '.', '.', '.', '2', '.', '.', '.', '6'},
{'.', '6', '.', '.', '.', '.', '2', '8', '.'},
{'.', '.', '.', '4', '1', '9', '.', '.', '5'},
{'.', '.', '.', '.', '8', '.', '.', '7', '9'}
};
System.out.println(new Solution1130().isValidSudoku(board));
}
}
有“AI”的1024 = 2048，欢迎大家加入2048 AI社区
更多推荐
13
0- 0
已为社区贡献2条内容
所有评论(0)