438. Find All Anagrams in a String

思路:

双指针,指向模式串str的子串首位s和末尾+1e

遍历思路:

  1. 不断添加e位置上的字符c
  2. 如果c不属于p,则双指针跳过c
  3. 如果c属于p,则更新。
    1. 但是如果包括的c字符太多了,则移动s直至数量符合条件
    2. 如果所有字符数量都添加完全一致,则添加结果。移动s一位,更新即可。

看了其他题解,发现有一个条件我忽略了,指针之间的距离是相等的,也就是说这是一个滑动窗口问题~草了。

那这很简单,维护一下窗口值就行了。

可以说滑动窗口就是一个简单的双指针。

Read more

142. Linked List Cycle II

思路:

用快慢指针fastslow去发现链表中的圆,再使用一个指针和p1一起遍历链表:

fig1

2(a + b) = a + b + (b + c ) *n 得到

a = c + (b + c ) *(n - 1)

如此可以推得,如果从p0从head和slow一起出发,会在环的入口处相遇。如此就可以推得算法的正确性。

另外开始验证,fastlow会在第一个low指针的第一圈相遇。

设置两个指针相遇时,low指针走了路程s1 = a + s + n(b + c)fast指针走了路程s2 = a + s + k(b + c)。同时有s1 * 2 = s2,则有a + s = (k - 2n)(b +c)

上面的证法不行:

slow刚入环的时候,fast在距离环入口的位置B,慢指针走了C,最后设环长为L

C % L = (2 *C + B) % L

等价于

C + NL = 2 * C + B

C = NL - B 当N==1,有0<=C<=B

当然,需要另外一个推理:

两个步长分别为1和2的指针,经过必定能相遇,可以通过遍历所有状态得知。

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *p1 = head, *p2 = head;
        int flag = 0, cyclen = 0, tlen = 0;
        while(p1){
            p1 = p1->next;
            if(p1 == nullptr) return nullptr;
            p1 = p1->next;
            p2 = p2->next;
            if(p1 == p2) break;            
        }
        if(p1 == nullptr) return nullptr;
        // while(1){
        //     p1 = p1->next->next;
        //     p2 = p2->next;
        //     cyclen++;   
        //     if(p1 == p2) break;         
        // }
        ListNode *p0 = head;
        while(p0 != p1){
            p0 = p0->next;
            p1 = p1->next;
            tlen++;
        }
        return p0;
    }
};

167. Two Sum II - Input array is sorted

思路:

双指针遍历。复杂度$O(n)$。

代码:

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int n = numbers.size();
        int l = 0, r = n - 1;
        while(l < r){
            int s = numbers[l] + numbers[r];
            if(s > target) r--;
            else if(s < target) l++;
            else break;
        }
        // vector<int> v(2,0);
        // v[0] = l + 1; v[1] = r + 1;
        // return v;
        return {l + 1, r + 1};    
    }
};