一、两数之和
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
你可以按任意顺序返回答案。
示例 ：
输入：nums = [2,7,11,15], target = 9 输出：[0,1] 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
进阶：
你可以想出一个时间复杂度小于 O(n2) 的算法吗？
代码：
import org.junit.Test;
import java.util.HashMap;
import java.util.Arrays;
class TwoSum {
//使用哈希表
public int[] twoSum(int[] nums, int target) {
// 创建一个哈希表来存储数字及其下标
HashMap<Integer, Integer> numMap = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i]; // 计算目标值与当前元素的差
// 检查差值是否已经在哈希表中
if (numMap.containsKey(complement)) {
return new int[] { numMap.get(complement), i }; // 返回下标
}
// 将当前元素及其下标添加到哈希表中
numMap.put(nums[i], i);
}
// 如果没有找到，返回空数组（根据题意，这种情况不会发生）
return new int[0];
}
public static void main(String[] args) {
TwoSum ts = new TwoSum();
int[] nums = {2, 7, 11, 15};
int target = 9;
// 调用 twoSum 方法并打印结果
int[] result = ts.twoSum(nums, target);
System.out.println("输出 [" + result[0] + ", " + result[1] + "]"); // 输出: [0, 1]
}
//只是简单的循环
@Test
public void test1(){
int target = 9;
int[] nums = {2,7,11,15};
System.out.println(Arrays.toString(twoShow(nums, target)));
}
public int[] twoShow(int[] nums,int target){
for (int i = 0; i < nums.length; i++) {
for (int j = 0; j < nums.length; j++) {
if (nums[i] + nums[j] == target) {
return new int[]{i,j};
}
}
}
return null;
}
}二、两数相加
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例 1
输入：l1 = [2,4,3], l2 = [5,6,4] 输出：[7,0,8] 解释：342 + 465 = 807.
三、 无重复字符的最长子串
给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。
示例 1
输入: s = "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
代码：
import java.util.HashMap;
public class LongestSubstring {
public static void main(String[] args) {
String s = "abcabcbb"; // 示例输入
int result = lengthOfLongestSubstring(s);
System.out.println("最长不含重复字符的子串长度: " + result); // 输出结果
}
public static int lengthOfLongestSubstring(String s) {
// 使用 HashMap 存储字符及其最新出现的索引
HashMap<Character, Integer> charIndexMap = new HashMap<>();
int maxLength = 0; // 用于存储最长子串的长度
int start = 0; // 窗口的起始位置
// 遍历字符串的每个字符
for (int i = 0; i < s.length(); i++) {
char currentChar = s.charAt(i); // 当前字符
// 如果当前字符在 HashMap 中存在且其索引大于等于窗口的起始位置
if (charIndexMap.containsKey(currentChar) && charIndexMap.get(currentChar) >= start) {
// 更新窗口的起始位置
start = charIndexMap.get(currentChar) + 1;
}
// 更新当前字符的索引
charIndexMap.put(currentChar, i);
// 更新最大长度
maxLength = Math.max(maxLength, i - start + 1);
}
return maxLength; // 返回最长子串的长度
}
}
四、寻找两个正序数组的中位数
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。
示例 1
输入：nums1 = [1,3], nums2 = [2] 输出：2.00000 解释：合并数组 = [1,2,3] ，中位数 2
代码：
class MedianOfTwoSortedArrays {
// 查找两个有序数组的中位数
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
// 确保 nums1 是较小的数组
if (nums1.length > nums2.length) {
int[] temp = nums1;
nums1 = nums2;
nums2 = temp;
}
int m = nums1.length; // nums1 的长度
int n = nums2.length; // nums2 的长度
int totalHalf = (m + n + 1) / 2; // 两个数组总元素的一半
int imin = 0, imax = m; // 初始化二分查找的边界
while (imin <= imax) {
int i = (imin + imax) / 2; // nums1 的中点索引
int j = totalHalf - i; // nums2 中对应的索引
if (i < m && nums2[j - 1] > nums1[i]) {
// i 太小，需要增大
imin = i + 1;
} else if (i > 0 && nums1[i - 1] > nums2[j]) {
// i 太大，需要减小
imax = i - 1;
} else {
// i 是合适的
int maxLeft = 0; // 左侧最大值
if (i == 0) {
maxLeft = nums2[j - 1]; // 特殊情况：nums1 为空
} else if (j == 0) {
maxLeft = nums1[i - 1]; // 特殊情况：nums2 为空
} else {
maxLeft = Math.max(nums1[i - 1], nums2[j - 1]); // 两个数组左侧的最大值
}
// 如果总长度为偶数，找到第二大值
if ((m + n) % 2 == 0) {
int minRight = 0; // 右侧最小值
if (i == m) {
minRight = nums2[j]; // 特殊情况：nums1 在末尾
} else if (j == n) {
minRight = nums1[i]; // 特殊情况：nums2 在末尾
} else {
minRight = Math.min(nums1[i], nums2[j]); // 两个数组右侧的最小值
}
return (maxLeft + minRight) / 2.0; // 返回两个中间元素的平均值
} else {
return maxLeft; // 对于奇数总长度，直接返回左侧最大值
}
}
}
// 如果输入数组未排序或无效，抛出异常
throw new IllegalArgumentException("输入的数组未排序或无效");
}
public static void main(String[] args) {
MedianOfTwoSortedArrays solution = new MedianOfTwoSortedArrays();
int[] nums1 = {1, 3}; // 第一个有序数组
int[] nums2 = {2}; // 第二个有序数组
double median = solution.findMedianSortedArrays(nums1, nums2);
System.out.println("中位数是: " + median); // 输出: 2.00000
}
}五、最长回文子串
给你一个字符串 s，找到 s 中最长的 回文 子串。
示例 1
输入：s = "babad" 输出："aba" 解释："bab" 同样是符合题意的答案。
代码：
class LongestPalindrome {
public static void main(String[] args) {
// 示例字符串
String s = "babad";
// 调用方法找到最长的回文子串
String result = longestPalindrome(s);
// 打印结果
System.out.println("最长的回文数为: " + result);
}
public static String longestPalindrome(String s) {
// 如果字符串为空或长度小于1，返回空字符串
if (s == null || s.length() < 1) {
return "";
}
// 初始化起始和结束索引
int start = 0, end = 0;
// 遍历字符串的每一个字符
for (int i = 0; i < s.length(); i++) {
// 检查以当前字符为中心的奇数长度回文
int len1 = expandAroundCenter(s, i, i);
// 检查以当前字符和下一个字符为中心的偶数长度回文
int len2 = expandAroundCenter(s, i, i + 1);
// 获取两种情况中更长的回文长度
int len = Math.max(len1, len2);
// 如果找到的回文长度大于之前记录的长度，更新起始和结束索引
if (len > end - start) {
start = i - (len - 1) / 2; // 计算回文的起始位置
end = i + len / 2; // 计算回文的结束位置
}
}
// 返回找到的最长回文子串
return s.substring(start, end + 1);
}
// 从中心扩展，检查回文长度
private static int expandAroundCenter(String s, int left, int right) {
// 当左右字符相等时继续向外扩展
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
left--; // 向左扩展
right++; // 向右扩展
}
// 返回回文的长度
return right - left - 1; // right - left - 1 是当前找到的回文的长度
}
}
六、Z字形变换
将一个给定字符串 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"
代码：
import java.util.ArrayList;
import java.util.List;
class ZigzagConversion {
public String convert(String s, int numRows) {
// 特殊情况处理
if (numRows <= 1 || numRows >= s.length()) {
return s;
}
// 用于存储每一行的字符
List<StringBuilder> rows = new ArrayList<>();
for (int i = 0; i < Math.min(numRows, s.length()); i++) {
rows.add(new StringBuilder());
}
// 逐字符填充每一行
int currentRow = 0;
boolean goingDown = false;
for (char c : s.toCharArray()) {
rows.get(currentRow).append(c);
// 判断是否需要改变方向
if (currentRow == 0) {
goingDown = true;
} else if (currentRow == numRows - 1) {
goingDown = false;
}
// 更新当前行
currentRow += goingDown ? 1 : -1;
}
// 合并所有行
StringBuilder result = new StringBuilder();
for (StringBuilder row : rows) {
result.append(row);
}
return result.toString();
}
public static void main(String[] args) {
ZigzagConversion converter = new ZigzagConversion();
String s = "PAYPALISHIRING";
int numRows = 3;
String result = converter.convert(s, numRows);
System.out.println(result); // 输出: PAHNAPLSIIGYIR
}
}七、整数反转
给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。
如果反转后整数超过 32 位的有符号整数的范围 [−231, 231 − 1] ，就返回 0。
假设环境不允许存储 64 位整数（有符号或无符号）。
示例 1
-
输入：x = 123 输出：321
代码：
public class ReverseInteger {
public int reverse(int x) {
// 设定反转后的结果为0
int result = 0;
// 处理负数的情况
// 使用long类型来避免溢出，虽然最终返回类型为int
while (x != 0) {
// 取出当前的最后一位数字
int digit = x % 10;
x /= 10; // 去掉最后一位数字
// 检查结果是否会在反转后溢出
// 由于result是int，最大值是Integer.MAX_VALUE
// 先检查是否会溢出，再进行乘法操作
if (result > Integer.MAX_VALUE / 10 ||
(result == Integer.MAX_VALUE / 10 && digit > 7)) {
return 0; // 溢出，返回0
}
if (result < Integer.MIN_VALUE / 10 ||
(result == Integer.MIN_VALUE / 10 && digit < -8)) {
return 0; // 溢出，返回0
}
// 将当前的数字添加到结果中
result = result * 10 + digit;
}
return result;
}
public static void main(String[] args) {
ReverseInteger ri = new ReverseInteger();
int x = 123; // 示例输入
int reversed = ri.reverse(x); // 反转
System.out.println("输入: " + x + ", 反转后的结果: " + reversed); // 输出结果
}
}
八、字符串转换整数
请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数。
函数 myAtoi(string s) 的算法如下：
- 空格：读入字符串并丢弃无用的前导空格（
" "） - 符号：检查下一个字符（假设还未到字符末尾）为
'-'还是'+'。如果两者都不存在，则假定结果为正。 - 转换：通过跳过前置零来读取该整数，直到遇到非数字字符或到达字符串的结尾。如果没有读取数字，则结果为0。
- 舍入：如果整数数超过 32 位有符号整数范围
[−231, 231 − 1]，需要截断这个整数，使其保持在这个范围内。具体来说，小于−231的整数应该被舍入为−231，大于231 − 1的整数应该被舍入为231 − 1。
返回整数作为最终结果。
示例 1
- 输入：s = "42"
- 输出：42
九、回文数
给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。
回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
- 例如，
121是回文，而123不是。
示例 1
输入：x = 121 输出：true
代码：
public class PalindromeNumber {
public static void main(String[] args) {
int x = 121; // 测试输入
boolean result = isPalindrome(x); // 调用 isPalindrome 方法
System.out.println(result); // 输出结果
}
/**
* 判断一个整数是否是回文数
*
* @param x 输入的整数
* @return 如果是回文数返回 true，否则返回 false
*/
public static boolean isPalindrome(int x) {
// 如果 x 是负数或者是以 0 结尾且不是 0，本身不是回文数
if (x < 0 || (x % 10 == 0 && x != 0)) {
return false;
}
int reversedNumber = 0; // 用于存储反转后的数字
while (x > reversedNumber) {
// 将 x 的最后一位数字添加到 reversedNumber 的后面
reversedNumber = reversedNumber * 10 + x % 10;
// 去掉 x 的最后一位数字
x /= 10;
}
// 当 x 等于 reversedNumber 或 x 等于 reversedNumber / 10 时，说明是回文数
return x == reversedNumber || x == reversedNumber / 10;
}
}
十、正则表达式匹配
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
'.'匹配任意单个字符'*'匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s 的，而不是部分字符串。
示例 1
输入：s = "aa", p = "a" 输出：false 解释："a" 无法匹配 "aa" 整个字符串。
代码：
class RegexMatch {
public static void main(String[] args) {
String s = "aa";
String p = "a";
System.out.println(isMatch(s, p)); // 输出: false
}
public static boolean isMatch(String s, String p) {
// s 的长度
int sLen = s.length();
// p 的长度
int pLen = p.length();
// dp[i][j] 表示 s 的前 i 个字符与 p 的前 j 个字符是否匹配
boolean[][] dp = new boolean[sLen + 1][pLen + 1];
// 空字符串与空模式匹配
dp[0][0] = true;
// 处理模式中以 * 结尾的情况，允许空字符串匹配
for (int j = 1; j <= pLen; j++) {
if (p.charAt(j - 1) == '*') {
dp[0][j] = dp[0][j - 2];
}
}
// 填充 dp 数组
for (int i = 1; i <= sLen; i++) {
for (int j = 1; j <= pLen; j++) {
char currentCharS = s.charAt(i - 1);
char currentCharP = p.charAt(j - 1);
// 当前字符匹配的情况
if (currentCharS == currentCharP || currentCharP == '.') {
dp[i][j] = dp[i - 1][j - 1];
}
// 处理 '*' 的情况
else if (currentCharP == '*') {
// '*' 可以匹配零个字符
dp[i][j] = dp[i][j - 2];
// '*' 可以匹配一个或多个前面的字符
if (currentCharS == p.charAt(j - 2) || p.charAt(j - 2) == '.') {
dp[i][j] = dp[i][j] || dp[i - 1][j];
}
}
}
}
// 返回 s 和 p 的匹配结果
return dp[sLen][pLen];
}
}
![[Python学习日记-48] Python 中的时间处理模块—— time 与 datetime](https://i-blog.csdnimg.cn/direct/e046d0cf3b8541429bc00c3f8e7e4ac9.png)
