- 验证回文串
125. 验证回文串
简单
如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。
字母和数字都属于字母数字字符。
给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 。
示例 1：
输入: s = "A man, a plan, a canal: Panama" 输出：true 解释："amanaplanacanalpanama" 是回文串。
注意for循环的坑，这里对字符大小写进行变化时，不可以使用另一种形式的for循环，因为for(char ch : chs)中的ch只是一个局部变量，并不会对chs数组中的元素进行更新
class Solution {public boolean isPalindrome(String s) {// 1. 数据预处理一下// 2. 去掉所有空格// 3. 然后双指针一个从前，一个从后面String str = s.replaceAll("[^a-zA-Z0-9]", ""); // 去掉所有非字母数字字符char[] chs = str.toCharArray();int n = chs.length;for(int i = 0; i < n; i++) {if(chs[i] >= 'A' && chs[i] <= 'Z') {chs[i] = (char)(chs[i] + 32);}}System.out.print(n);for(int i = 0,j = n-1; i < n/2; i++,j-- ) {if(chs[i] != chs[j]) {System.out.print(chs[i] + " " + chs[j]);return false;}}return true;}
}判断子序列
392. 判断子序列
简单
给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
进阶：
如果有大量输入的 S，称作 S1, S2, ... , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？
致谢：
特别感谢 @pbrother 添加此问题并且创建所有测试用例。
示例 1：
输入：s = "abc", t = "ahbgdc" 输出：true
class Solution {public boolean isSubsequence(String s, String t) {/**判断s 是不是 t的子序列思路：双指针法，使用两个指针依次匹配即可*/if(s.length() == 0) return true;for(int i =0,j =0; j < t.length(); j++) {if(s.charAt(i) == t.charAt(j)) {if(++i == s.length()) { // 已经匹配完s了return true;}}}return false; // s还有没有匹配完的，说明不是子序列}
}- 两数之和 —— 输入有序数组 —— O(n)
167. 两数之和 II - 输入有序数组
给你一个下标从 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] 。
167. 两数之和 II - 输入有序数组 - 力扣（LeetCode）
class Solution {public int[] twoSum(int[] numbers, int target) {// 如果求和小于 目标值；说明 A[0] + A[j] 小的，应该用 A[1] + A[j] 故 i++// 如果求和大于 目标值：说明 A[0] + A[j] 大于target，则说明其大了，应该用 A[0] + A[j-1]的内容尝试，故 j--// 遍历这个numbers; // 双指针思想 // 原来的空间是一个二维的矩阵 （朴素算法）int n = numbers.length;int i = 0 , j = n-1;while(i < n && j > 0){int sum = numbers[i] + numbers[j];if(sum < target) {i ++;}else if(sum > target) {j --;}else { // sum == targetreturn new int[]{i+1,j+1};}}return new int[]{-1,-1}; // 没有找到}
}- 盛最多水的容器
11. 盛最多水的容器
给定一个长度为 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。
参考题解：
11. 盛最多水的容器 - 力扣（LeetCode）
class Solution {public int maxArea(int[] height) {/**装最多的水，就是在求这个矩形的最大面积矩形的长为后面的下标减去前面的下标；矩形的宽为两个长条中更小的一个朴素算法：———— 超时用一个变量记录最大值然后以左边第一个为左柱子，依次遍历右边的柱子，计算面积下一轮以左边第二个为右柱子双指针思想：同样的是在一个n*n空间内部搜索得到O(n)的思想，必须要通过双指针，指针每一次移动，意味着排除掉一根柱子如果左边的柱子较短，那么相当于左边的柱子全部被使用了此时如果固定左边的柱子，然后移动右边的柱子，此时水的高度一定不会增加；相当于排除了左柱子当把这些柱子对称过来时，之前的左柱子不就相当于现在的右柱子；所以也是同理，如果右边较小，则排除了一次右柱子总之：就是每次拿两端比较，排除较小一端的柱子,双指针中就是通过 i++,j-- 实现*/// return method1(height);return doublePointerMethod(height);}private int doublePointerMethod(int[] height) {int n = height.length;int i = 0, j = n-1;int ans = 0;while(i < n-1 && j > 0) {int area = 0;if(height[i] <= height[j]) {// 左边的柱子更小，记录左边柱子的情况，然后排除这根柱子area = height[i] * (j-i);i ++;}else { // 右边柱子更小，记录右边柱子的情况，然后排除这根柱子area = height[j] * (j-i);j --;}ans = Math.max(area, ans);}return ans;}public int method1(int[] height) {int ans = 0;int n = height.length;for(int i = 0; i < n-1; i++) {for(int j = i+1; j < n; j++) {int area = Math.min(height[i],height[j]) * (j-i);ans = Math.max(area,ans); // 更新ans}}return ans;}
}搜索二维矩阵 Ⅱ
240. 搜索二维矩阵 II
中等
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
- 每行的元素从左到右升序排列。
- 每列的元素从上到下升序排列。
示例 1：
输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5 输出：true
- 三数之和 —— 固定一个，用双指针遍历下一层
15. 三数之和
中等
给你一个整数数组 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] 。 注意，输出的顺序和三元组的顺序并不重要。
参考题解：15. 三数之和 - 力扣（LeetCode）
class Solution {public List<List<Integer>> threeSum(int[] nums) {// 是否存在三个数不重复(可以相等)，但是三个数却可以相加为0/**朴素思想： 三重for循环：固定第一个参数，然后下一个，然后固定第二个参数，继续下一个，遍历最后一个思路2：可不可以先进行排序，然后对排序的结果进行操作，如果第一个和第二个参数大于0了，就不用判断第三个了，但这只是剪枝；思路3：固定第一个k,然后对后面两个使用双指针，这样优化到O(n); 而第一次有n个，所以总时间复杂度为O(n^2)操作为先排序*/Arrays.sort(nums);List<List<Integer>> res = new ArrayList<>();for(int k = 0; k < nums.length - 2; k++) {if(nums[k] > 0) break;// 如果当前的k与之前的相同，则跳过，因为已经把nums[k]的所有组合加入到结果中了if(k > 0 && nums[k] == nums[k - 1]) continue;// 使用双指针遍历下面两个元素nums[i] , nums[j]int i = k + 1, j = nums.length - 1;while(i < j) {int sum = nums[k] + nums[i] + nums[j]; if(sum < 0) { // 结果小0，增大nums[i],且去掉所有相同的nums[i]，因为已经不满足case了while(i < j && nums[i] == nums[++i]); }else if(sum > 0) { // 结果大0，减小nums[j],且去掉所有相同的nums[j]while(i < j && nums[j] == nums[--j]);}else { // = 0 收集结果,并进入下一个元素res.add(new ArrayList<Integer>(Arrays.asList(nums[k],nums[i],nums[j])));while(i < j && nums[i] == nums[++i]);while(i < j && nums[j] == nums[--j]);}}}return res;}
}