字串小筆記

紀錄一些好玩的字串判斷方法

判斷遞增子序列

判斷遞增子序列的方法,假設當前字串為
2,5,7,8,9,2,3,4,3,1 此時可以發線子序列可以拆分為
1. 2,5,7,8,9 length = 5
2. 2,3,4 length = 3
3. 3 length = 1
4. 1 length = 1
因此就可以發現相鄰的遞增子序列為 min(length=5,length=3)
而兩個遞增子序列屬於同一個遞增段的話最大長度則為 $\lfloor \frac{cnt}{2} \rfloor$
因此要求長度即

for(int i=0;i<nums.size();i++){
    cnt++; // record the current string length 
    if(i == nums.size()-1 || nums[i] >= nums[i-1]){ // 1. 判斷是否到尾 2. 判斷是否為嚴格遞增序列即a1 > a2
        ans = max({ans,cnt,min(pre,cnt)}); // pre 為上個遞增子序列的長度
        pre = cnt;
        cnt = 0; // 重設
    }
    return ans;
}

LCS

KMP

基環樹

以Leetcode 287為例,目的是要尋找在一個包含n+1個整數的陣列且其數字範圍在1~n
- prove 假設為有n+1個球要放入n個箱子現在將第i個數放在第nums[i]個箱子，根據鴿籠原理則必有一個箱子重複放即為重複數

#include <vector>
using namespace std;
class Solution {
public:
    int findDuplicate(vector<int>& nums) {
      int slow = 0;
      int fast = 0;
      while(true) {
        slow = nums[slow]; // equal to slow.next;
        fast = nums[nums[fast]]; //equal to fast.next.next
        if(slow == fast) break;
      }
      int head = 0;
      while(slow != head){
        slow = nums[slow];
        head = nums[head];
      }
      return slow;
    }
};

先藉由slow和fast找到存在cycle的地方,再透過head重新遍歷,找到的入口數即為重複數