Java — LeetCode 面试经典150题(一)

双指针

125.验证回文串

题目

如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。
字母和数字都属于字母数字字符。
给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 。

提示：

1 <= s.length <= 2e5
s 仅由可打印的 ASCII 字符组成

示例 1：

输入: s = "A man, a plan, a canal: Panama"
输出：true
解释："amanaplanacanalpanama" 是回文串。

示例 2：

输入：s = "race a car"
输出：false
解释："raceacar" 不是回文串。

示例 3：

输入：s = " "
输出：true
解释：在移除非字母数字字符之后，s 是一个空字符串 "" 。由于空字符串正着反着读都一样，所以是回文串。

解析:

该题是个水题，只需要移除所有非字母数字字符之后，利用双指针从新的字符串的头部和尾部不断地向对方推进，进行比较。
当两个不相同的字符时，就结束，说明此串不是回文串。

代码:

class Solution {public boolean isPalindrome(String s) {String p=s.toLowerCase();System.out.print(p);char[] a=new char[p.length()];int len=0;for (int i=0;i<p.length();i++){if (p.charAt(i)>='a'&&p.charAt(i)<='z'||p.charAt(i)>='0'&&p.charAt(i)<='9'){a[len++]=p.charAt(i);}}boolean flag=true;for (int i=0,j=len-1;i<=j;i++,j--){if (a[i]!=a[j]){flag=false;break;}}return flag;}
}

392.判断子序列

题目

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

提示：

0 <= s.length <= 100
0 <= t.length <= 1e4
两个字符串都只由小写字符组成。

示例 1：

输入：s = "abc", t = "ahbgdc"
输出：true

示例 2：

输入：s = "axc", t = "ahbgdc"
输出：false

解析：

遍历字符串 t，用一个指针 l 指向字符串 s 的最后一个与 s 匹配的字符的位置。
当 t[i]==s[l] 时，l++。直到遍历结束，比较 l 与字符串 s 的长度即可。

代码：

class Solution {public boolean isSubsequence(String s, String t) {int n = t.length(), m = s.length();if (m == 0)return true;int l = 0;for (int i = 0; i < n; i++) {if (t.charAt(i) == s.charAt(l)) {l++;}if (l == m) {break;}}if (l == m)return true;return false;}
}

167.两数之和 II - 输入有序数组

题目

给你一个下标从 1 开始的整数数组 numbers ，该数组已按非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。
如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。
以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。
你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。
你所设计的解决方案必须只使用常量级的额外空间。

提示：

2 <= numbers.length <= 3 * 1e4
-1000 <= numbers[i] <= 1000 , numbers 按 非递减顺序 排列
-1000 <= target <= 1000
仅存在一个有效答案

示例 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] 。

解析：

该数组已经按照非递减顺序排列，设置两个指针，分别指向数组头部和尾部。
如果指向的两个数的和大于目标数，就需要将小的那个数变大，即头部指针向后移动；反之，尾部指针向前移动。
直到两个数的和等于目标数。(仅存一个有效答案哦！)

代码

class Solution {public int[] twoSum(int[] numbers, int target) {int n=numbers.length;int l=0,r=n-1;int[] ans=new int[2];while (l<r){if (numbers[l]+numbers[r]==target){ans[0]=l+1;ans[1]=r+1;break;}else if (numbers[l]+numbers[r]<target){l++;}else{r--;}}return ans;}
}

11.盛最多水的容器

题目

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明：你不能倾斜容器。

提示：

n == height.length
2 <= n <= 1e5
0 <= height[i] <= 1e4

示例 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

解析：

首先知道怎么计算水量，水量等于两个端点的距离 * 两条线较短的一条的长度。
设置两个指针指向数组的头部和尾部，一个最开始的水量就是尾部减头部的距离 * 较小的长度。
什么情况才可能比这个状态的水量大呢？就是取决于两点的距离和较短的一条线长度。
将短的那条线的指针向里面推进，只有当较短的变长了，才有可能水量变大。
这样不断推进两边端点，不断增加线的长度。每次找到后，取水量的最大值即可。

代码：

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

15.三数之和

题目

给你一个整数数组 nums ，判断是否存在三元组[nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。
请你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。

提示：

3 <= nums.length <= 3000
-1e5 <= nums[i] <= 1e5

示例 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 。

解析：

首先，数据最大是3000，所以双for循环不会超时，所以用双for循环遍历nums[i]和nums[j]，那么关于剩下的数就是判断0-nums[i]-nums[j]是否在数组中了，我是用的map，将数组中的数和它的坐标存在map对象中，判断该数是否存在且不是第i个数也不是第j个数。
然后就是去重问题，我将符合条件的三个数，存放进一个数组中，进行sort。然后将数组的三个数放进List中，将List放进一个Set中，进行去重。(有更简便的算法，我这个是更加合理地使用集合的那些容器)

代码：

class Solution {public List<List<Integer>> threeSum(int[] nums) {Set<List<Integer>> res = new HashSet<>();Map<Integer, Integer> m = new HashMap<>();for (int i = 0; i < nums.length; i++) {m.put(nums[i], i);}for (int i = 0; i < nums.length; i++)for (int j = i + 1; j < nums.length; j++) {int k = 0 - nums[i] - nums[j];if (m.containsKey(k) && m.get(k) != i && m.get(k) != j) {List<Integer> s = new ArrayList<>();int[] a = new int[3];a[0] = nums[i];a[1] = nums[j];a[2] = k;Arrays.sort(a);s.add(a[0]);s.add(a[1]);s.add(a[2]);res.add(s);}}return new ArrayList<List<Integer>>(res);}
}