1. 两数之和
思路一：暴力遍历所有组合
class Solution {
public int[] twoSum(int[] nums, int target) {
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] == target) {
return new int[] {i, j};
}
}
}
//没找到
return new int[] {-1, -1};
}
}
思路二：利用map，key存储元素凑成target所需的差值，value存储元素下标
class Solution {
public int[] twoSum(int[] nums, int target) {
//value代表下标，key代表target与当前元素只差，即：target - nums[value]
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
if (map.containsKey(nums[i])) {
return new int[] {map.get(nums[i]), i};
} else {
map.put(target - nums[i], i);
}
}
//没找到
return new int[] {-1, -1};
}
}
2. 两数相加
思路：直接模拟加法
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode cur1 = l1;
ListNode cur2 = l2;
//哑结点
ListNode dummy = new ListNode(-1);
ListNode cur = dummy;
//进位
int carry = 0;
while (cur1 != null || cur2 != null || carry != 0) {
int val1 = cur1 != null ? cur1.val : 0;
int val2 = cur2 != null ? cur2.val : 0;
int sum = val1 + val2 + carry;
int reminder = sum % 10;
carry = sum / 10;
//尾插法
ListNode tempNode = new ListNode(reminder);
cur.next = tempNode;
cur = cur.next;;
if (cur1 != null) cur1 = cur1.next;
if (cur2 != null) cur2 = cur2.next;
}
return dummy.next;
}
}
3. 无重复字符的最长子串
class Solution {
public int lengthOfLongestSubstring(String s) {
//窗口左右边界，左闭右开
int left = 0, right = 0;
//存储字符及其在窗口中的个数
Map<Character, Integer> window = new HashMap<>();
int maxLen = 0;
while (right < s.length()) {
//窗口扩大
char rightChar = s.charAt(right);
right++;
window.put(rightChar, window.getOrDefault(rightChar, 0) + 1);
//如果新加入窗口的字符个数大于1次，窗口应该收缩
while(window.get(rightChar) > 1) {
char leftChar = s.charAt(left);
left++;
window.put(leftChar, window.get(leftChar) - 1);
}
maxLen = Math.max(maxLen, right - left);
}
return maxLen;
}
}
4. 寻找两个正序数组的中位数
思路一：直接合并两个有序数组，根据数组长度求中位数。时间复杂为O(m+n)，空间复杂度为O(m+n)
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int m = nums1.length;
int n = nums2.length;
int[] tempArr = new int[m + n];
int i = 0, j = 0;
int k = 0;
while(i < m && j < n) {
if (nums1[i] < nums2[j]) {
tempArr[k++] = nums1[i++];
} else {
tempArr[k++] = nums2[j++];
}
}
//nums1还有剩余
while (i < m) {
tempArr[k++] = nums1[i++];
}
//nums2还有剩余
while (j < n) {
tempArr[k++] = nums2[j++];
}
int midIndex = (m + n) / 2;
double mid = 0;
//长度为偶数
if ((m + n) % 2 == 0) {
mid = (tempArr[midIndex - 1] + tempArr[midIndex]) / 2.0;
} else {
mid = tempArr[midIndex];
}
return mid;
}
}
思路二：无需真正合并数组，先根据两个数组的长度确定中位数是合并后数组中的第几个数，然后根据规则将指向两个数组的下标移动对应次数就好。时间复杂为O(m+n)，空间复杂度为O(1)
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int m = nums1.length;
int n = nums2.length;
//i, j分别表示nums1和nums2的分割线，i为[0, m]，j为[0, n];
//[0, i)表示nums1中已经遍历过的下标，对应j类似
int i = 0, j = 0;
//记录最新遍历的两个数
int newest = 0, secondNew = 0;
//奇数：中位数是第(m+n)/2 + 1个数（下标从1开始）
//偶数：中位数是第(m+n)/2和第(m+n)/2 + 1数的平均数（下标从1开始）
int cnt = (m + n) / 2 + 1;
for (int k = 0; k < cnt; k++) {
secondNew = newest;
// j >= n 表示指向nums2已经没有元素
if (j >= n || (i < m && nums1[i] < nums2[j])) {
newest = nums1[i];
i++;
} else {
newest = nums2[j];
j++;
}
}
//偶数
if ((m + n) % 2 == 0) {
return (newest + secondNew) / 2.0;
} else {
return newest;
}
}
}
终于说服自己
思路三：使用二分法直接在两个数组中找中位数分割线，使得nums1和nums2中分割线满足以下性质即可根据分割线左右的数来确定中位数：
前置：m = nums1.length，n = nums2.length。设i为nums1中分割线，则取值为[0, m]，表示分割线左侧元素下标为[0, i-1]，分割线右侧元素下标为[i, m-1]；设j为nums2中分割线，....。
-
m+n为偶数：i + j = (m + n )/2，为奇数：i + j = (m + n)/2 + 1。 -
分割线左侧元素
小于等于分割线右侧元素。由于两个数组均为正序数组，则只需要要求：nums1[i-1] <= nums2[j] && nums2[j-1] <= nums1[i]；由于该条件等价于在[0, m]中找到最大的i使得nums1[i-1] <= nums2[j]，因此可以使用二分查找。（证明：假设我们已经找到了满足条件的最大i，使得nums1[i-1] <= nums2[j]，那么此时必有nums[i] > nums2[j]，进而有nums[i] > nums2[j-1]）
分割线找到后，若m+n为奇数，分割线左侧的最大值即为中位数；若为偶数，分割线左侧的最大值与分割线右侧的最小值的平均数即为中位数。时间复杂度：O(log(min(m, n)))，空间复杂度：O(1)
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
// 始终保证nums1为较短的数组，nums1过长可能导致j为负数而越界
if (nums1.length > nums2.length) {
int[] temp = nums1;
nums1 = nums2;
nums2 = temp;
}
int m = nums1.length;
int n = nums2.length;
// m+n 为奇数，分割线要求左侧有 (m+n)/2 + 1 个元素
// m+n 为偶数，分割线要求左侧有 (m+n)/2 个元素
// 两种情况其实可以统一写作 (m+n+1)/2，表示对(m+n)/2向上取整
// 对整数来说，向上取整等于：(被除数 + (除数 - 1)) / 除数
// 也可以使用Math类中提供的库函数
int leftTotal = (m + n + 1) / 2;
int left = 0, right = m;
while (left < right) {
// +1 向上取整避免 left + 1 = right 时可能无法继续缩小区间而陷入死循环
int i = left + (right - left + 1) / 2;
int j = leftTotal - i;
//要找最大i，使得nums1[i-1] <= nums2[j]
//使用对立面缩小区间
if (nums1[i - 1] > nums2[j]) {
// [i+1, m]均不满足
right = i - 1;
} else {
// i满足说明[0, i-1]均不为满足条件的最大i，舍去以缩小区间
left = i;
}
}
//退出循环时left=right，表示最终nums1中分割线的位置
int i = left;
//nums2中分割线的位置
int j = leftTotal - left;
System.out.println(i);
//判断极端情况
int nums1LeftMax = (i == 0) ? Integer.MIN_VALUE : nums1[i - 1]; //nums1分割线左边没有元素
int nums2LeftMax = (j == 0) ? Integer.MIN_VALUE : nums2[j - 1]; //nums2分割线左边没有元素
int nums1RightMin = (i == m) ? Integer.MAX_VALUE : nums1[i]; //nums1分割线右边没有元素
int nums2RightMin = (j == n) ? Integer.MAX_VALUE : nums2[j]; //nums2分割线右边没有元素
if ((m + n) % 2 == 0) {
return (Math.max(nums1LeftMax, nums2LeftMax) + Math.min(nums1RightMin, nums2RightMin)) / 2.0;
} else {
return Math.max(nums1LeftMax, nums2LeftMax);
}
}
}
备注：这里使用的二分法和二分法查找x的平方根使用的方法很像，都是要查找满足条件的最大值。
参考：官方题解：方法二、wei哥：二分查找定位短数组的「分割线」（Java ）
5. 最长回文子串
思路：动态规划获取任意两个区间的子串是否为回文子串，如果是则记录开始下标和长度
class Solution {
public String longestPalindrome(String s) {
int len = s.length();
int maxLen = 0;
int start = 0;
//dp[i][j]: 字符串s[i, j]是否为回文字符串
boolean[][] dp = new boolean[len][len];
for (int j = 0; j < len; j++) {
for (int i = 0; i <= j; i++) {
if (s.charAt(i) == s.charAt(j) && (j - i <= 2 || dp[i + 1][j - 1])) {
dp[i][j] = true;
if (j - i + 1 > maxLen) {
maxLen = j - i + 1;
start = i;
}
}
}
}
return s.substring(start, start + maxLen);
}
}
7. 整数反转
此题的难点在处理越界:
class Solution {
public int reverse(int x) {
int result = 0;
while (x != 0) {
int reminder = x % 10;
// 首先要明确不能直接拿result和最大最小值比较，无论越界与否系统都只解析32位，
// 那么解析之后result肯定都在最大最小值之间，因此要 /10 以提前判断；
if (result < Integer.MIN_VALUE/10 || (result == Integer.MIN_VALUE/10 && reminder < -8)) {
return 0;
}
if (result > Integer.MAX_VALUE/10 || (result == Integer.MAX_VALUE/10 && reminder > 7)) {
return 0;
}
x /= 10;
result = result * 10 + reminder;
}
return result;
}
}
不理解可以阅读：画解算法：7. 整数反转
8. 字符串转换整数 (atoi)
难点在理解需求并编码
class Solution {
public int myAtoi(String s) {
//去掉首尾空格
s = s.trim();
int flag = 1;
int index = 0;
int len = s.length();
//第一位只能是 正负号 或 数字(数字留到后面处理)
if (index < len) {
if (s.charAt(index) == ‘+‘) {
flag = 1;
index++;
} else if (s.charAt(index) == ‘-‘) {
flag = -1;
index++;
}
//s为空
} else {
return 0;
}
int result = 0;
while (index < len) {
char curChar = s.charAt(index);
//只能是数字
if (!Character.isDigit(curChar)) {
break;
}
//判断是否越界
if (result > Integer.MAX_VALUE/10 || (result == Integer.MAX_VALUE/10 && (curChar - ‘0‘) > 7)) {
return Integer.MAX_VALUE;
}
//这里 curChar - ‘0‘ 都为正，与上例有不同之处
if (result < Integer.MIN_VALUE/10 || (result == Integer.MIN_VALUE/10 && (curChar - ‘0‘) > 8)) {
return Integer.MIN_VALUE;
}
result = result * 10 + (curChar - ‘0‘) * flag;
index++;
}
return result;
}
}
10. 正则表达式匹配
class Solution {
public boolean isMatch(String s, String p) {
int sLen = s.length();
int pLen = p.length();
//状态：dp[i][j] 表示s的前i个字符和p的前j个字符能否匹配，即 s[0, i-1] 和 p[0, j-1] 能否匹配
boolean[][] dp = new boolean[sLen + 1][pLen + 1];
//前置：i, j分别代表dp的横、纵下标，对应的s、p的下标都应减去1
//初始值：dp 默认都为flase
//dp[0][0] = true, 即s和p都为空
//dp[i][0] = false, 其中i >= 1, 即s不为空p为空
//dp[0][1] = false, 由于p[0]不能为*，s为空，p只有一个字符且不为‘*‘的情况下必然不能匹配成功
//s为空，p不为空且p[0, j-1]以‘*‘结尾时，还不能直接断定dp的值。
//因为‘*‘可以选择将它前面的字符匹配零次以消除‘*‘前面的字符。
//因此 dp[0][j] = dp[0][j - 2], j >= 2。若s为空，p不为空且 p[0, j-1] 不以‘*‘结尾，那么有：
//dp[0][j] = false, j >= 1。
dp[0][0] = true;
for (int j = 2; j < pLen + 1; j++) {
if (p.charAt(j - 1) == ‘*‘) {
dp[0][j] = dp[0][j - 2];
}
}
//状态转移：
//当 s[0, i-1] 和 p[0, j-1] 的末尾字符相等或p的末尾字符为‘.‘，则有：dp[i][j] = dp[i - 1][j - 1];
//当 p[0, j-1] 的末尾字符即 p[j - 1] 为‘*‘需要讨论：
// 若 s[i - 1] 与 p[j - 2] 相等，如：s(ab), p(cab*)，那么*可以选择将b 重复一次 则s末尾的b和p末尾的b*匹配抵消，
// 则有：dp[i][j] = dp[i - 1][j - 2]；
// 同时*也可以选择将b 重复多次 以匹配抵消s中最后一个b，此时p虽然也损失一个b但任然还剩多个b，可以将其看成b*
// 故有：dp[i][j] = dp[i - 1][j];
// 此外*也可以选择将b 去掉，故：dp[i][j] = dp[i][j - 2]
// 综上：dp[i - j] = dp[i - 1][j - 2] || dp[i - 1]dp[j] || dp[i][j - 2]
// 若 p[j - 2] 为 ‘.‘，同上
// 若 s[i - 1] 与 p[j - 2] 不等且后者不为‘.‘，如：s(ab), p(eabd*)，那么*可以选择将d 去掉 ，
// 则有：dp[i][j] = dp[i][j - 2]
for (int j = 1; j < pLen + 1; j++) {
for (int i = 1; i < sLen + 1; i++) {
if (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == ‘.‘) {
dp[i][j] = dp[i - 1][j - 1];
} else if (p.charAt(j - 1) == ‘*‘) {
if (s.charAt(i - 1) == p.charAt(j - 2) || p.charAt(j - 2) == ‘.‘) {
dp[i][j] = dp[i - 1][j -2] || dp[i - 1][j] || dp[i][j - 2];
} else {
dp[i][j] = dp[i][j - 2];
}
}
}
}
return dp[sLen][pLen];
}
}
11. 盛最多水的容器
class Solution {
public int maxArea(int[] height) {
int left = 0, right = height.length - 1;
int maxArea = 0;
while (left < right) {
int width = right - left;
int high = Math.min(height[left], height[right]);
int area = width * high;
maxArea = Math.max(area, maxArea);
//左边小则直接去掉，因为它和右边剩余的任意一个元素组成的面积都不会比当前更大
if (height[left] < height[right]) {
left++;
//去掉右边
} else {
right--;
}
}
return maxArea;
}
}
推荐题解：O(n) 双指针解法：理解正确性、图解原理（C++/Java）
13. 罗马数字转整数
class Solution {
//罗马数字的特点是将各个字符代表的十进制数相加即可完成对十进制的转换
public int romanToInt(String s) {
Map<String, Integer> map = new HashMap<>() {
{
put("I", 1);
put("V", 5);
put("X", 10);
put("L", 50);
put("C", 100);
put("D", 500);
put("M", 1000);
//几种额外情况
put("IV", 4);
put("IX", 9);
put("XL", 40);
put("XC", 90);
put("CD", 400);
put("CM", 900);
}
};
int res = 0;
for (int i = 0; i < s.length();) {
if ((i < s.length() - 1) && map.containsKey(s.substring(i, i + 2))) {
res += map.get(s.substring(i, i + 2));
i += 2;
} else {
res += map.get(s.substring(i, i + 1));
i++;
}
}
return res;
}
}
推荐题解：画解算法：13. 罗马数字转整数
class Solution {
//要用尽可能短的罗马字符代替十进制
public String intToRoman(int num) {
String[] keys = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
StringBuilder sb = new StringBuilder();
for (int i = 0; i < keys.length; i++) {
String tempKey = keys[i];
int tempVal = values[i];
while (num >= tempVal) {
num -= tempVal;
sb.append(tempKey);
}
if (num <= 0) {
break;
}
}
return sb.toString();
}
}