Two Pointers
1. 28. Implement strStr()
用 i 记录haystack偏移量，j 记录 needle 的偏移量。
class Solution {
public int strStr(String haystack, String needle) {
int lenH = haystack.length();
int lenN = needle.length();
if( lenN > lenH)
return -1;
if(lenN == 0)
return 0;
for(int i = 0; i <= lenH - lenN; i++){
boolean flag = true;
for(int j = 0; j < lenN; j++){
if( haystack.charAt(i + j) != needle.charAt(j)){
flag = false;
break;
}
}
if (flag)
return i;
}
return -1;
}
}
2. 125. Valid Palindrome
只需要建立两个指针，head 和 tail, 分别从字符的开头和结尾处开始遍历整个字符串，如果遇到非字母数字的字符就跳过，继续往下找，直到找到下一个字母数字或者结束遍历，如果遇到大写字母，就将其转为小写。等左右指针都找到字母数字时，比较这两个字符，若相等，则继续比较下面两个分别找到的字母数字，若不相等，直接返回false.
Character.isLetterOrDigit ( char ). 判断是否为字符或数字
Character.toLowercase ( char ) . 两个函数
class Solution {
public boolean isPalindrome(String s) {
if( s.isEmpty())
return true;
int head = 0, tail = s.length() -1;
char cHead, cTail;
while( head <= tail){
cHead = s.charAt(head);
cTail = s.charAt(tail);
if(!Character.isLetterOrDigit(cHead))
head++;
else if(!Character.isLetterOrDigit(cTail))
tail--;
else{
if(Character.toLowerCase(cHead) != Character.toLowerCase(cTail))
return false;
head++;
tail--;
}
}
return true;
}
}
3. 142. Linked List Cycle II Medium
用快慢指针，假设有环时，head到环起点距离为A，环起点到相遇地点为B，慢指针走A+B，快指针移动距离总是慢指针两倍，且比慢指针多走一圈设为N。A+B+N = 2A + 2B。
A = N - B。head到环起点(新设一个指针指向head) = 一圈 减去 环起点到相遇地点 = 相遇点到环起点距离。
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode fast = head, slow = head;
while(fast!=null && fast.next!=null){
slow = slow.next;
fast = fast.next.next;
if( fast == slow){
slow = head;
while( slow != fast){
slow = slow.next;
fast = fast.next;
}
return fast;
}
}
return null;
}
}