题目列表：167、633、345、680、88、141、524
167. 两数之和 II - 输入有序数组
| 给定一个已按照升序排列的有序数组，找到两个数使得它们相加之和等于目标数。函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。 示例: 输入: numbers = [2, 7, 11, 15], target = 9 输出: [1,2] 解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。 |
|---|
题解思路：
使用双指针，一个指针指向值较小的元素，一个指针指向值较大的元素。
- 如果两个指针指向元素的和 sum == target，那么得到要求的结果；
- 如果 sum > target，移动较大的元素，使 sum 变小一些；
- 如果 sum < target，移动较小的元素，使 sum 变大一些。
public int[] twoSum(int[] numbers, int target) {if (numbers == null) return null;int i = 0, j = numbers.length - 1;while (i < j) {int sum = numbers[i] + numbers[j];if (sum == target) {return new int[]{i + 1, j + 1};} else if (sum < target) {i++;} else {j--;}}return null;}
633. 平方数之和
| 给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a平方 + b平方 = c 。 示例 1： 输入：c = 5 输出：true 解释：1 1 + 2 2 = 5 |
|---|
class Solution {
public boolean judgeSquareSum(int c) {
int a=0;
int b=(int)Math.sqrt(c);
while(a<=b){
int num=a*a+b*b;
if(num==c){
return true;
}else if(num>c){
b--;
}else if(num<c){
a++;
}
}
return false;
}
}
关键点：在于如何确定右指针的位置，如果将右指针的位置置于c，将会出现整型溢出的情况，改用long解决溢出问题，同样回出现超时的情况。
345. 反转字符串中的元音字母
编写一个函数，以字符串作为输入，反转该字符串中的元音字母。
public String reverseVowels(String s) {
char[] c = s.toCharArray();
int l = 0;
int r = c.length - 1;
while (l < r) {
if (!vertify(c[l])) {
l++;
continue;
}
if (!vertify(c[r])) {
r--;
continue;
}
char c1=' ';
c1 = c[l];
c[l++] = c[r];
c[r--] = c1;
}
String s1=new String(c);
return s1;
}
//判断是否为元音字母
public boolean vertify(char c) {
return (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u'||c=='A'||c=='E'||c=='I'||c=='O'||c=='U');
}
| 题解思路： 1、依旧是碰撞指针的思想，两边向中间操作，判断是否为元音字母，不是就移动指针，直到是开始交换。 |
|---|
while (!vertify(c[l])) {
l++;
}
while (!vertify(c[r])) {
r--;
}
if(l<r){ //这一步判断是一定要做的
char c1 = ' ';
c1 = c[l];
c[l++] = c[r];
c[r--] = c1;
}
中间的判断逻辑可以通过while循环来完成，但是后面一定要加上左右值的判断，不然原先替换好的值会被替换回去。
680. 验证回文字符串 Ⅱ
给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。示例 1: 输入: “aba” 输出: True |
|---|
所谓回文数就是指具有左右对称特点的字符串
使用双指针可以很容易判断一个字符串是否是回文字符串：令一个指针从左到右遍历，一个指针从右到左遍历，这两个指针同时移动一个位置，每次都判断两个指针指向的字符是否相同，如果都相同，字符串才是具有左右对称性质的回文字符串。
此题的题设相当于给予了左右指针多一次的机会。但是可能存在的删除左边或者是删除右边的情况，如果使用一个标识位来做判断的话就会显得比较的麻烦。因此我们可以考虑在提取出判断的方法，重新定义需要判断的长度
public boolean validPalindrome(String s) {
for (int i = 0, j = s.length() - 1; i < j; i++, j--) {
if (s.charAt(i) != s.charAt(j)) {
//考虑左右两种情况，任意一种情况满足条件即可。
return isPalindrome(s, i, j - 1) || isPalindrome(s, i + 1, j);
}
}
return true;
}
private boolean isPalindrome(String s, int i, int j) {
while (i < j) {
if (s.charAt(i++) != s.charAt(j--)) {
return false;
}
}
return true;
}
88. 合并两个有序数组
//给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int ai = m + n - 1;
int mi = m - 1;
int ni = n - 1;
while (ni >= 0) {
if (mi >= 0 && nums1[mi] > nums2[ni]) {
nums1[ai--] = nums1[mi--];
} else {
nums1[ai--] = nums2[ni--];
}
}
}
}
| 题解思路：（倒序处理） 1、题目给出了每个数组的实际有效长度，所以不要被后面的0所迷惑 2、数组1的有效长度为m，数组2的有效长度为n，所以其实真正有效的数组长度为m+n 3、因此我们只需要在nums数组长度为m+n的区间内操作即可，两数组的数进行比较，大的数放进数组 4、注意while和if中的边界条件 |
|---|
哪个数组赋值给长数组了，就移动哪一个。
141. 环形链表
题解思路：双指针，慢指针走一步，快指针走两步
public class Solution {
public boolean hasCycle(ListNode head) {
if(head==null){
return false;
}
ListNode slow=head;
ListNode fast=head.next;
while(slow!=null&&fast!=null&&fast.next!=null){
if(slow==fast){
return true;
}
slow=slow.next;
fast=fast.next.next;
}
return false;
}
}
**
524. 通过删除字母匹配到字典里最长单词
| 给定一个字符串和一个字符串字典，找到字典里面最长的字符串，该字符串可以通过删除给定字符串的某些字符来得到。如果答案不止一个，返回长度最长且字典顺序最小的字符串。如果答案不存在，则返回空字符串。 示例 1: 输入:s = “abpcplea”, d = [“ale”,”apple”,”monkey”,”plea”] 输出:“apple” |
|---|
class Solution {
public String findLongestWord(String s, List<String> d) {
String longest = "";
for (String target : d) {
int x = longest.length(), y = target.length();
//此处的longestcompareTo保证字典顺序
if (x > y || (x == y && longest.compareTo(target) < 0)) { *
continue;
} else if (isSubString(s, target)) {
longest = target;
}
}
return longest;
}
private boolean isSubString(String s, String target) {
int i = 0, j = 0;
while (i < s.length() && j < target.length()) {
if (s.charAt(i) == target.charAt(j)) {
j++;
}
i++;
}
return j == target.length();
}
}
注意点：初始筛选条件我写的是 if (x >= y ) { continue; }，但是这种写法是没有办法保证得到的结果满足字典顺序最小的条件
125. 验证回文串
- 空字符串如何看？
- 字符的定义？
大小写问题 ```java class Solution { public boolean isPalindrome(String s) {
int left = 0; int right = s.length() - 1; char[] c = s.toCharArray(); while (left < right) { if (!vertify(c[left])) { left++; continue; } if (!vertify(c[right])) { right--; continue; } if (toLowercase(c[left]) != toLowercase(c[right])) { return false; } left++; right--; } return true;}
//判断是否为字符或者是数字 public boolean vertify(char c) {
return ((c >= '0' && c <= '9') || (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z'));}
//字符大写转小写 public char toLowercase(char c) {
if (c >= 'A' && c <= 'Z') { c += 32; } return c;} }
| 题解思路：<br />1、判断回文数依旧可以考虑指针碰撞的方式解决。<br />2、关键在于判断之前要先处理大小写问题，以及除数字以及字母外的问题。<br />[字符可以直接通过字符之间比较，无需去考虑ASCII的值大小] |
| --- |
```java
class Solution {
public boolean isPalindrome(String s) {
if (null == s) {
return false;
}
if (s.length() == 0) {
return true;
}
s = s.replaceAll("[^a-zA-Z0-9]", "");
String reverse = String.valueOf(new StringBuilder(s).reverse());
return s.equalsIgnoreCase(reverse);
}
}
| 题解思路： 1、使用正则表达式替换无关符号 2、通过StringBuilder的反转功能 3、通过String的忽略大小写比较功能 |
|---|
11. 盛最多水的容器
给你 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
class Solution {
public int maxArea(int[] height) {
int l = 0;
int r = height.length - 1;
int h;//代表高度
int length;//代表长度
int area = 0;//代表面积
boolean flag = true;//标志位，下一次循环应该谁移动
while(l<r){
h = height[l] > height[r] ? height[r] : height[l];
length = r - l;
area = (h * length) > area ? (h * length) : area;
if(height[l]>height[r]){
r--;
}else{
l++;
}
}
return area;
}
| 题解思路： 1、一开始使用了双层嵌套循环的方式处理，但是耗时太长了 2、错误的处理步骤中，移动的方式是左移一步然后右移一步 3、正确的方式应该是哪边小就应该是哪边移动，这个思想和167号题是类似的 |
|---|
对O(n)的算法写一下自己的理解，一开始两个指针一个指向开头一个指向结尾，此时容器的底是最大的，接下来随着指针向内移动，会造成容器的底变小，在这种情况下想要让容器盛水变多，就只有在容器的高上下功夫。 那我们该如何决策哪个指针移动呢？我们能够发现不管是左指针向右移动一位，还是右指针向左移动一位，容器的底都是一样的，都比原来减少了 1。这种情况下我们想要让指针移动后的容器面积增大，就要使移动后的容器的高尽量大，所以我们选择指针所指的高较小的那个指针进行移动，这样我们就保留了容器较高的那条边，放弃了较小的那条边，以获得有更高的边的机会。
若有收获，就点个赞吧
0 人点赞
