刷题记录｜目标101题--双指针
写在前面
开个贴记录一下刷题的过程，目前参照leetcode101，目标101题，由于太久没写java了，也会涉及到一些java的基础用法，希望能和大家共勉吧～
已刷链接：
双指针
No.1 Two Sum II - Input Array Is Sorted
题目链接：https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/
设计到的算法：双指针
解题思路：左右各一个指针滑动既可
class Solution {
public int[] twoSum(int[] numbers, int target) {
int i = 0, j = numbers.length - 1;
while(numbers[i] + numbers[j] != target) {
if (numbers[i] + numbers[j] < target) {
i ++;
} else {
j --;
}
}
int[] result = {++i,++j};
return result;
}
} No.2 Merge Sorted Array
题目链接：https://leetcode.com/problems/merge-sorted-array/
涉及到的算法：双指针
解题思路：
从前往后的两个指针不可行因为会覆盖，那么考虑从后往前数两个指针，发现从后往前是work的
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int i = m - 1, j = n - 1, current = m + n - 1;
while (i >= 0 && j >= 0) {
if (nums1[i] > nums2[j]) {
nums1[current--] = nums1[i--];
} else {
nums1[current--] = nums2[j--];
}
}
while(i >= 0) {
nums1[current--] = nums1[i--];
}
while(j >= 0) {
nums1[current--] = nums2[j--];
}
}
} No. 3 Linked List Cycle II
题目链接：https://leetcode.com/problems/linked-list-cycle-ii/
涉及到的算法：快慢指针
解题思路：快慢指针
快慢指针中如果用图表示就是将路径分为abc三段，a表示从链表头到成环点，b表示从环点到相遇处，c表示从相遇处到环点，其计算公式如下（图好丑TT）
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode detectCycle(ListNode head) {
if (head == null) return null;
ListNode fast = head;
ListNode slow = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
break;
}
}
if (fast.next == null || fast.next.next == null) {
return null;
}
fast = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
} No.4 Minimum Window Substring
题目链接：https://leetcode.com/problems/minimum-window-substring/
涉及到的算法：滑动窗口
解题思路：
首先需要先遍历一遍string t，用数组记录下来他的character出现的次数。
用l和r指针遍历这个数组，在遍历时及时更新这个数组。
- 如果r滑过了则将对应character次数--，
- 如果l滑过了，此时如果只是单一的character数组，我们在看到l指针指向的字符对应在character数组中的计数为0时，无法区分是这个字符从未在string t中出现过，可以划走还是出现过但是正好被指针r覆盖，所以展示的0，此时不能划走，故引入数组flag[]，在首次遍历时同时记录数组character和数组flag
- 需要将string s从头到位遍历一遍，存储一个最小值，中间每次满足条件时将值与最小值对比，如果比最小值还要小更新最小值
- 涉及到的java原理：
class Solution {
public String minWindow(String s, String t) {
if (t.length() > s.length()) return "";
int[] characters = new int[128];
boolean[] flag = new boolean[128];
for (int i = 0; i < t.length(); i++) {
int index = t.charAt(i);
flag[index] = true;
characters[index]++;
}
int begin_index = 0, end_index = s.length(),count = 0;
for (int r = 0,l = 0; r < s.length(); r++) {
int indexR = s.charAt(r);
if (flag[indexR] && characters[indexR]-- > 0) {
count++;
}
while (count == t.length()) {
int indexL = s.charAt(l);
if (flag[indexL] && ++characters[indexL] > 0) {
if (r-l+1 < end_index-begin_index +1) {
begin_index = l;
end_index = r;
}
count--;
}
l++;
}
}
return end_index == s.length() ? "" : s.substring(begin_index,end_index+1);
}
} No.5 Sum of Square Numbers
题目链接：https://leetcode.com/problems/sum-of-square-numbers/
涉及到的算法：双指针
解题思路：
Two Sum 变种
这里需要注意两点：
- 不能将r=c/2,而要使用java的开根号方法double Math.sqrt()，向下取整，防止溢出
- 因为 0 <= c && c <= 231 - 1,我们在计算时如果使用 a2 + b2 容易溢出，可以使用 c - a2 的形式去判断，就不会溢出了
class Solution {
public boolean judgeSquareSum(int c) {
if (c <= 2) return true;
int l = 0, r = (int)(Math.sqrt(c));
while(l <= r) {
int left = l * l;
int right = c - left;
if (right == r * r) {
return true;
} else if (right < r * r) {
r --;
} else {
l ++;
}
}
return false;
}
} No.6 Valid Palindrome II
题目链接：https://leetcode.com/problems/valid-palindrome-ii/
涉及到的算法：双指针
解题思路：左右各一个指针，遇见不同时尝试跳过左边的数字和跳过右边的数字两种情况就可以。
class Solution {
public boolean validPalindrome(String s) {
int l = 0, r = s.length() - 1;
while (l < r && s.charAt(l) == s.charAt(r)) {
l++;r--;
}
if (s.charAt(l) == s.charAt(r)) return true;
return isPalindrome(s.substring(l + 1,r + 1)) || isPalindrome(s.substring(l,r));
}
private boolean isPalindrome(String s) {
int l = 0, r = s.length() - 1;
while (l < r && s.charAt(l) == s.charAt(r)) {
l++;r--;
}
if (s.charAt(l) == s.charAt(r)) return true;
return false;
}
} No.7 Longest Word in Dictionary through Deleting
题目链接：https://leetcode.com/problems/longest-word-in-dictionary-through-deleting/
涉及到的算法：双指针
解题思路：
先给 dictionary 排序，排完以后就是一个简单的对比string的问题
class Solution {
public String findLongestWord(String s, List<String> dictionary) {
Collections.sort(dictionary,(a,b) -> {
if (a.length() != b.length()) {
return b.length() - a.length();
}
for (int i = 0; i < a.length(); i++) {
if (a.charAt(i) != b.charAt(i)) {
return a.charAt(i) - b.charAt(i);
}
}
return 0;
});
for(int i = 0; i < dictionary.size();i++) {
if (dictionary.get(i).length() > s.length()) {
continue;
}
String target = dictionary.get(i);
int j = 0,k = 0;
for(; j < s.length() && k < target.length(); j++) {
if (s.charAt(j) == target.charAt(k)) {
k++;
}
}
if (k == target.length()) {
return target;
}
}
return "";
}
} No. 8 Longest Substring with At Most K Distinct Characters
本题需要leetcode会员，贫穷的我选择直接看好心人的题解T T：https://aaronice.gitbook.io/lintcode/two_pointers/longest_substring_with_at_most_k_distinct_characters
涉及到的java知识：
题目：
解题思路：
求一个最长的substring的length，可以知道我们的思路是采用一个双指针的滑动窗口，在滑动的过程中去更新这个length，生息的问题是如何去维护这个滑动窗口。
我们要能确定这个这个substring的窗口中有几种字符需要额外开辟一块存储空间，去存储在这个窗口中哪些字符出现了，出现了几次。
我们需要获取在这个窗口中出现的distinct character的数量，但是数组无法确定究竟有哪些不同的character被存入，所以我们要换用可以直接获得size的hashmap进行储存，开辟一块存储，存储对应character出现次数的index
如何滑动：
设置一个左指针firstIndex 一个右指针endInex表示滑动窗口的起始与结尾，每次将endInex右++，将其指向的character存入hashMap，如果曾经有就将其次数++；
如果此时hashMap的size已经大于k了，就可以开始移动左指针firstIndex，进行删除操作，直到size不再大于k；
每次移动右指针时更新最长的值，最后返回记录的最长的值
#力扣刷题##逃离互联网#
腾讯二面453人在聊