[mermaid]graph TD
A[Start: Two Pointer]
A1[题号: 101, 102, 103]
B[Search]
B1[Binary Search]
B1a[题号: 301, 302, 303]
B2[DFS - Depth First Search]
B2a[题号: 501, 502, 503]
B3[BFS - Breadth First Search]
B3a[题号: 601, 602, 603]
C[Sort]
C1[Bubble Sort]
C1a[题号: 701, 702, 703]
C2[Quick Sort]
C2a[题号: 801, 802, 803]
C3[Merge Sort]
C3a[题号: 901, 902, 903]
D[Greedy Algorithm]
D1[题号: 1001, 1002, 1003]
E[Divide and Conquer]
E1[题号: 1101, 1102, 1103]
F[DP - Dynamic Programming]
F1[题号: 1201, 1202, 1203]
A --> A1
A --> B
B --> B1
B1 --> B1a
B --> B2
B2 --> B2a
B --> B3
B3 --> B3a
B --> C
C --> C1
C1 --> C1a
C --> C2
C2 --> C2a
C --> C3
C3 --> C3a
C --> D
D --> D1
D --> E
E --> E1
E --> F
F --> F1 [/mermaid]
双指针
题号： 167 Two Sum II – Input Array Is Sorted
https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/description/
题目描述
给定一个已按非递减顺序排列的整数数组numbers，请找出两个数，使它们相加之和等于特定目标数target。返回这两个数的索引（以1为起始索引），即numbers[index1]和numbers[index2]，其中1 <= index1 < index2 <= numbers.length。
返回两个数字的索引，以长度为2的整数数组[index1, index2]的形式。测试用例保证有且仅有一个解决方案。不得使用相同元素两次。
您的解决方案只能使用恒定的额外空间。
我的要点笔记：
- 返还array 的语法是这样：
return new int[] {l+1,r+1};，返还空array记得用new int [2]. - index要加1，因为他要的是第几位数而不是index
我的答案：
class Solution {
public int[] twoSum(int[] numbers, int target) {
int l = 0, r = numbers.length -1;
while(l<r){
int sum = numbers[l] + numbers[r];
if(sum == target){
return new int[] {l+1,r+1};
}
if( sum < target){
l ++;
}else{
r--;
}
}
return new int[2];
}
}
更优答案：
(请在此处添加更优答案)
题号： 633 Sum of Square Numbers
https://leetcode.com/problems/sum-of-square-numbers/description/
题目描述
判断一个非负整数c是否为两个整数的平方和。换言之，是否存在两个整数a和b，使得a^2 + b^2 = c。
我的要点笔记：
- 使用Math.sqrt(target)作为初始r
- 因为涉及平方，使用long而不是int
我的答案：
class Solution {
public boolean judgeSquareSum(int c) {
long x =0, y = (long) Math.sqrt(c);
while ( x <= y){
long sum =x*x+y*y;
if ( sum == c) return true;
if (sum < c){
x++;
}else{
y--;
}
}
return false;
}
}
更优答案：
(请在此处添加更优答案)
题号： 345 Reverse Vowels of a String
https://leetcode.com/problems/reverse-vowels-of-a-string/description/
题目描述
编写一个函数，以字符串作为输入，反转该字符串中的元音字母。
我的要点笔记：
- 用string或者hashset很快，储存vowels
- 可以用双while优化
我的答案：
class Solution {
public String reverseVowels(String s) {
String vowels = "AEIOUaeiou";
int l = 0 , r = s.length()-1;
char [] res = s.toCharArray();
while(l < r){
if(vowels.indexOf(s.charAt(l)) >= 0 &&vowels.indexOf(s.charAt(r)) >= 0){
char temp = s.charAt(l);
res[l] = res[r];
res[r]=temp;
l++;
r--;
}else if(vowels.indexOf(s.charAt(l)) < 0){
l++;
}else if(vowels.indexOf(s.charAt(r)) <0){
r--;
}
}
return new String(res);
}
}
更优答案：
class Solution {
public String reverseVowels(String s) {
char[] word = s.toCharArray();
int start = 0;
int end = s.length() - 1;
String vowels = "aeiouAEIOU";
while (start < end) {
// Move start pointer until it points to a vowel
while (start < end && vowels.indexOf(word[start]) == -1) {
start++;
}
// Move end pointer until it points to a vowel
while (start < end && vowels.indexOf(word[end]) == -1) {
end--;
}
// Swap the vowels
char temp = word[start];
word[start] = word[end];
word[end] = temp;
// Move the pointers towards each other
start++;
end--;
}
String answer = new String(word);
return answer;
}
}
题号： 680 Valid Palindrome II
https://leetcode.com/problems/valid-palindrome-ii/description/
题目描述
给定一个非空字符串s，最多删除一个字符。判断是否能成为回文字符串。
我的要点笔记：
- 我加了一个helper判断palindrome，然后一个boolean flag来判断是否可以移除一个字符
- 移除字符有两种情况，移除左边的或者右边的
- 大概是O（n）
我的答案：
class Solution {
public boolean validPalindrome(String s) {
return palindramHelper(s,true);
}
boolean palindramHelper(String s, boolean ifHasChance){
int l = 0 , r = s.length()- 1;
while( l <= r){
if(s.charAt(l) == s.charAt(r)){
l++;
r--;
}else{
if(ifHasChance){
return palindramHelper(s.substring(l,r),false) || palindramHelper(s.substring(l+1,r+1),false);
}else{
return false;
}
}
}
return true;
}
}
更优答案：
(请在此处添加更优答案)
题号： 88 Merge Sorted Array
https://leetcode.com/problems/merge-sorted-array/description/
题目描述
给你两个有序整数数组nums1和nums2，请你将nums2合并到nums1中，使nums1成为一个有序数组。
初始化nums1和nums2的元素数量分别为m和n。你可以假设nums1有足够的空间（空间大小等于m + n）来保存nums2中的元素。
我的要点笔记：
- 从大到小排序
- 如果短的用尽了，可以判断退出因为肯定整个是sorted
我的答案：
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int x = m-1, y = n - 1 , i = m+n-1;
while(y >= 0){
if(x >=0 && nums1[x] > nums2[y]){
nums1[i] = nums1[x];
x--;
}else{
nums1[i] = nums2[y];
y--;
}
i--;
}
}
}
更优答案：
(请在此处添加更优答案)
题号： 141 Linked List Cycle
https://leetcode.com/problems/linked-list-cycle/description/
题目描述
给定一个链表，判断链表中是否有环。
为了表示给定链表中的环，我们使用整数pos来表示链表尾连接到链表中的位置（索引从0开始）。如果pos是-1，则在该链表中没有环。注意：pos不作为参数进行传递，仅仅是为了标识链表的实际情况。
如果链表中存在环，则返回true。否则，返回false。
我的要点笔记：
- 差速，一个快一个慢，注意查null
我的答案：
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public boolean hasCycle(ListNode head) {
if( head == null)return false;
ListNode list1= head;
ListNode list2 =head.next;
while ( list1 != null && list2 != null &&list1.next != null && list2.next!= null){
if( list1==list2)return true;
list1=list1.next;
list2=list2.next == null? null : list2.next.next;
}
return false;
}
}
更优答案：
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public boolean hasCycle(ListNode head) {
ListNode slow ,fast;
if( head==null) return false;
slow=head;
fast=head.next;
while(slow!=fast) {
if(fast==null || fast.next==null) return false;
slow=slow.next;
fast=fast.next.next;
}
return true;
}
}
题号： 524 Longest Word in Dictionary through Deleting
https://leetcode.com/problems/longest-word-in-dictionary-through-deleting/description/
题目描述
给定一个字符串s和一个字符串数组d。你需要从s中删除一些字符，使得它构成字符串列表d中的一个字符串，找出能构成的最长字符串。如果有多个相同长度的结果，返回字典序中最小的字符串。
通过删除s中的一个字符能得到字符串t，可以认为t是s的子序列，我们可以使用双指针来判断一个字符串是否为另一个字符串的子序列。
我的要点笔记：
- string对比大小用 curr.compareTo(res)
- 直接跳过不符合条件的string，比如过短
我的答案：
class Solution {
public String findLongestWord(String s, List<String> dictionary) {
String res = "";
for(int i = 0 ; i < dictionary.size(); i++){
String curr = dictionary.get(i);
if(curr.length() < res.length()) continue;
int l = 0 , r = 0;
while (l < s.length() && r < curr.length()){
if(s.charAt(l) == curr.charAt(r)){
r++;
}
l++;
}
if(r < curr.length())continue;
if((curr.length() > res.length())||(res.length() == curr.length() && curr.compareTo(res) < 0)){
res = curr;
}
}
return res;
}
}
更优答案：
(请在此处添加更优答案)
请根据您的需要在各部分填写相应的笔记和答案。如果您需要其他题目的信息，或有其他问题，随时告诉我！
