1天前

## 方案一(双指针)

class Solution {
public int maxArea(int[] height) {
int l = 0, r = height.length - 1;
int max = Math.min(height[l], height[r]) * (r - l);
while (l < r) {
if (height[l] >= height[r]) r --;
else l ++;
max = Math.max(max, Math.min(height[l], height[r]) * (r - l));
}

return max;
}
}


1天前

# 方案一(动态规划)

class Solution {

public boolean isMatch(String s, String p) {
s = ' ' + s;
p = ' ' + p;
int n = s.length();
int m = p.length();
boolean[][] f = new boolean[n][m];
f[0][0] = true;

for (int i = 0; i < n; i++) {
for (int j = 1; j < m; j++) {
// 将 ?* 看做一组
if (j < m - 1 && p.charAt(j + 1) == '*') {
continue;
}

if (i != 0 && p.charAt(j) != '*') {
f[i][j] = f[i - 1][j - 1] && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.');
} else if (p.charAt(j) == '*') {
f[i][j] = f[i][j - 2] || (i != 0 && f[i - 1][j] && (s.charAt(i) == p.charAt(j - 1)
|| p.charAt(j - 1) == '.'));
}
}
}
return f[n - 1][m - 1];
}
}


1天前

## 方案一(暴力)

class Solution {
public boolean isPalindrome(int x) {
if (x < 0) return false;
if (x < 10) return true;

String str = Integer.toString(x);
int length = str.length();
for (int i = 0; i <= length / 2; i ++) {
if (str.charAt(i) != str.charAt(length - i - 1)) {
return false;
}
}

return true;
}
}


## 方案二(整数逆序)

class Solution {
public boolean isPalindrome(int x) {
// 1. 负数不可能是回文数
// 2. 末尾为0的也不可能是回文数，因为最高位肯定不是0 (但是 0 的话就是回文数，所以要排除这个特殊情况)
if (x < 0 || (x != 0 && x % 10 == 0)) return false;

int s = 0;
while (x > s) {
s = s * 10 + x % 10;
x /= 10;
}

return x == s || x == s / 10;
}
}


2天前

## 方案一(暴力)

class Solution {

public int myAtoi(String str) {
// 去除前面的空格
int startIndex = 0;
int length = str.length();
int res = 0;
int flag = 1;
while (startIndex < length && str.charAt(startIndex) == ' ') {
startIndex++;
}

char ch;
// 如果为空串或者第一个不为空格的字符不是数字，则没办法进行解析，直接返回 0
if (startIndex >= length || !(((ch = str.charAt(startIndex)) >= '0' || ch <= '9') || (ch == '-'
|| ch == '+'))) {
return res;
}

if (ch == '-' || ch == '+') {
if (ch == '-') {
flag = -1;
}
startIndex++;
}

for (; startIndex < length && (ch = str.charAt(startIndex)) >= '0' && ch <= '9'; startIndex++) {
int num = ch - '0';
if (flag > 0 && res > (Integer.MAX_VALUE - num) / 10) {
return Integer.MAX_VALUE;
} else if (flag < 0 && -res < (Integer.MIN_VALUE + num) / 10) {
return Integer.MIN_VALUE;
}
res = res * 10 + num;
}

return res * flag;
}
}


2天前

## 方案一

class Solution {
public int reverse(int x) {
int res = 0;
while(x != 0) {
if (x > 0 && res > (Integer.MAX_VALUE - x % 10) / 10) return 0;
if (x < 0 && res < (Integer.MIN_VALUE - x % 10) / 10) return 0;
res = res * 10 + x % 10;
x /= 10;
}
return res;
}
}


3天前

## 方案一(找规律)

class Solution {
public String convert(String s, int numRows) {
if (numRows == 1) {return s;}

int length = s.length();
StringBuilder sb = new StringBuilder(length);
int step = numRows + (numRows > 2 ? numRows - 2 : 0);
for (int i = 0; i < numRows; i++) {
for (int j = i, k = 1; j < length; j += step, k ++) {
sb.append(s.charAt(j));
if (numRows > 2 && i > 0 && i < numRows - 1  && (k * step - i < length)) {
sb.append(s.charAt(k * step - i));
}
}
}

return sb.toString();
}
}


8天前

## 方案一(暴力)

class Solution {
public String longestPalindrome(String s) {
int length = s.length();
if (length <= 1) return s;

int maxLength = 1;
int startIndex = 0;
int endIndex = 1;
int l, r;
for (int i = 0; i < length; i++) {
// 以 i 为回文串的中心
l = i; r = i;
while (l >= 1 && r < length - 1 && s.charAt(l - 1) == s.charAt(r + 1)) {
l --;
r ++;
}
if (maxLength < r - l + 1) {
maxLength = r - l + 1;
startIndex = l;
endIndex = r + 1;
}

// 如果 s[i] == s[i+1]，就以 i 和 i + 1 为中心
if (i < length - 1 && s.charAt(i) == s.charAt(i + 1)) {
l = i;
r = i + 1;
while (l - 1 >= 0 && r + 1 < length && s.charAt(l - 1) == s.charAt(r + 1)) {
l --;
r ++;
}
if (maxLength < r - l + 1) {
maxLength = r - l + 1;
startIndex = l;
endIndex = r + 1;
}
}
}

return s.substring(startIndex, endIndex);
}
}


9天前

## 方案一(双指针算法)

class Solution {
// 用的是 BitSet 存储子串中各个字符的占用情况，仅仅适用于子串中字符在 ASCII 码范围内
// 如果超过这个范围，可以使用 HashMap 作为替代方案。
BitSet bitSet = new BitSet(256);
public int lengthOfLongestSubstring(String s) {
int maxLength = 0;
for (int beginIndex = 0, endIndex = 0; endIndex < s.length(); endIndex++) {
char ch = s.charAt(endIndex);
while (bitSet.get(ch)) {
bitSet.clear(s.charAt(beginIndex ++));
}
bitSet.set(ch);
maxLength = Math.max(maxLength, endIndex - beginIndex + 1);
}

return maxLength;
}
}


# 4. 寻找两个正序数组中的中位数

## 错误方案一(暴力)

class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
/*
合并这两个数组
*/
// 合并后的数组
int[] fetchedNums = new int[nums1.length + nums2.length];
// i 代表 fetchNums 的下标;j 代表 nums1 的下标;k 代表 nums2 的下标
int i = 0, j = 0, k = 0;
while (j < nums1.length && k < nums2.length) {
if (nums1[j] <= nums2[k]) {
fetchedNums[i ++] = nums1[j ++];
} else {
fetchedNums[i ++] = nums2[k ++];
}
}
while (j < nums1.length) {fetchedNums[i ++] = nums1[j ++];}
while (k < nums2.length) {fetchedNums[i ++] = nums2[k ++];}

/*
求合并后数组的中位数
*/
if ((fetchedNums.length & 1) == 1) {
return fetchedNums[fetchedNums.length / 2] / 1.0;
} else {
return (fetchedNums[fetchedNums.length / 2] + fetchedNums[fetchedNums.length / 2 - 1]) / 2.0;
}
}
}


## 方案一(递归)

class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int total = nums1.length + nums2.length;
if ((total & 1) == 0) {
// 如果是偶数，取 (total / 2) 和 (total / 2 + 1) 的平均值
int num1 = findKthNumber(nums1, 0, nums2, 0, total / 2);
int num2 = findKthNumber(nums1, 0, nums2, 0, total / 2 + 1);
return (num1 + num2) / 2.0;
} else {
// 如果是奇数，只需要取 total / 2 + 1
return findKthNumber(nums1, 0, nums2, 0, total / 2 + 1) / 1.0;
}
}

private int findKthNumber(int[] nums1, int i, int[] nums2, int j, int k) {
// 保证 nums1.length <= nums2.length
if (nums1.length - i > nums2.length - j) return findKthNumber(nums2, j, nums1, i, k);

// 如果 nums1 中的元素都被丢弃了(可以理解为 nums1 为空)，那么结果肯定为 nums2[j + k - 1]
if (nums1.length == i) return nums2[j + k - 1];
// 如果 k = 1，那么表示取两个数组中最小的那个值
if (k == 1) return Math.min(nums1[i], nums2[j]);
// 边界值处理，由于 k = nums1.length + nums2.length，又因为 nums2.length > nums1.length
// 所以 nums1.length 可能会小于 k/2，所以如果要丢弃的话，只能丢弃 nums1.length，而不是 k/2
int si = Math.min(i + k / 2, nums1.length), sj = j + k / 2;
/*
核心思路
如果 nums1[k/2] > nums2[k/2] 那么说明 nums2 的前 k/2 中肯定不包含第 k 小的数
反之依然，nums1[k/2] < nums2[k/2] 那么说明 nums1 的前 k/2 中肯定不包含第 k 小的数
如果 nums1[k/2] == nums2[k/2]，那么说明 nums[k/2] 和 nums2[k/2] 都有可能是第 k 小的数，所以抛弃任意一个都能得到结果
*/
if (nums1[si - 1] > nums2[sj - 1]) {
return findKthNumber(nums1, i, nums2, sj, k - k / 2);
} else {
return findKthNumber(nums1, si, nums2, j, k - si + i);
}
}
}


9天前

## 方案一(双指针算法)

class Solution {
// 用的是 BitSet 存储子串中各个字符的占用情况，仅仅适用于子串中字符在 ASCII 码范围内
// 如果超过这个范围，可以使用 HashMap 作为替代方案。
BitSet bitSet = new BitSet(256);
public int lengthOfLongestSubstring(String s) {
int maxLength = 0;
for (int beginIndex = 0, endIndex = 0; endIndex < s.length(); endIndex++) {
char ch = s.charAt(endIndex);
while (bitSet.get(ch)) {
bitSet.clear(s.charAt(beginIndex ++));
}
bitSet.set(ch);
maxLength = Math.max(maxLength, endIndex - beginIndex + 1);
}

return maxLength;
}
}


14天前

# 2. 两数相加

## 方案一(模拟)

/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode l3 = new ListNode(0);
ListNode res = l3;
int c = 0;
int sum = 0;
while (l1 != null || l2 != null) {
sum = c;
if (l1 != null) {
sum += l1.val;
l1 = l1.next;
}
if (l2 != null) {
sum += l2.val;
l2 = l2.next;
}
l3.next = new ListNode(sum % 10);
l3 = l3.next;
c = sum / 10;
}
if (c != 0) {
// 可能还有进位，所以需要特殊处理
l3.next = new ListNode(c);
}

return res.next;
}
}