76. 最小覆蓋子串

76. 最小覆蓋子串 - 力扣（LeetCode）

解法一： 暴力枚舉 + 哈希表

先定義left和right，可以在隨機(jī)位置
枚舉一個(gè)位置向后找，找到一個(gè)位置之后，發(fā)現(xiàn)這段區(qū)間是一個(gè)最小的區(qū)間之后，讓left移動(dòng)一格
然后right繼續(xù)從left開(kāi)始向后找

輸入：s = "ADOBECODEBANC", t = "ABC"
hash1:
在t中A出現(xiàn)1次，B出現(xiàn)1次，C出現(xiàn)1次

hash2：
在s中，記錄ABC出現(xiàn)幾次
只要在hash2中，字符統(tǒng)計(jì)出現(xiàn)的次數(shù)大于等于hash1，那么就是一個(gè)有效的枚舉

優(yōu)化：
? ? ? ? ? 符合要求
s = "-----------------------------"
? ? ? ? ? [L? ? ? ? R]

當(dāng)left向左移動(dòng)一步時(shí)，會(huì)有兩種情況
1：依舊符合要求
right不動(dòng)

2：不符合要求
right向右移動(dòng)，找符合要求的位置

兩個(gè)指針是同向運(yùn)動(dòng)的，所以單調(diào)性，所以可以使用滑動(dòng)窗口

解法二：滑動(dòng)窗口 + 哈希表

s = "A D O B E C O D E B A N C", t = "ABC"
? ? ? ?L
? ? ? ? ? R

1. left = 0, right = 0

2. 進(jìn)窗口 -> hash2[in]++

3. 判斷，當(dāng)窗口剛好合法時(shí)出窗口 -> check(hash1, hash2)

更新結(jié)果 -> 起始位置、最終的最短長(zhǎng)度

出窗口 -> hash2(out)--

判斷成立先更新結(jié)果，再出窗口然后繼續(xù)判斷

優(yōu)化：判斷條件
使用變量count標(biāo)記有效字符的“種類”

1. 進(jìn)窗口 -> 進(jìn)之后，當(dāng)hash2(in) == hash1(in), count++
只要hash2里面A的個(gè)數(shù)與hash1里面A的個(gè)數(shù)相等時(shí)統(tǒng)計(jì)

2. 出窗口 -> 出之前，當(dāng)hash2(out) == hash1(out), count--
比如出窗口后，hash2里面A的個(gè)數(shù)從1變成了0，然后hash1里面A為1，成為了無(wú)效字符，那么count--

3. 判斷條件 -> count == hash1.szie()

代碼：C++

class Solution {
public:string minWindow(string s, string t) {// 數(shù)組模擬哈希表，因?yàn)槿怯⑽淖址鹖nt hash1[128] = {0}; // 統(tǒng)計(jì)字符串t中每個(gè)字符的頻次int hash2[128] = {0}; // 統(tǒng)計(jì)窗口內(nèi)每個(gè)字符的頻次int kinds = 0; // 統(tǒng)計(jì)有效字符有多少種for(auto ch : t) {// if(hash[ch] == 0) kinds++;// hash[ch]++;// 同上if(hash1[ch]++ == 0) kinds++; // 加之前如果等于0，說(shuō)明找到一個(gè)有效字符，所以kinds++}int minlen = INT_MAX, begin = -1; // minlen是最小覆蓋子串長(zhǎng)度，begin存的是起始位置for(int left=0, right=0, count=0; right<s.size(); right++){char in = s[right];//     hash2[in]++;//     if(hash2[in] == hash1[in])//     {//         count++;//     }// 同上if(++hash2[in] == hash1[in]) count++; // 進(jìn)窗口+維護(hù)count變量while(count == kinds) // 判斷條件{// 只要窗口長(zhǎng)度小于minlenif(right - left + 1 < minlen) // 更新結(jié)果{minlen = right - left + 1;begin = left;}// 出窗口char out = s[left++];// if(hash2[out] == hash1[out]) count--;// hash2[out]--;// 同上if(hash2[out]-- == hash1[out]) count--; // 說(shuō)明此時(shí)有效字符的種類要減少}}if(begin == -1) return ""; // 如果等于-1說(shuō)明沒(méi)有找到一個(gè)子串，返回空串else return s.substr(begin, minlen); // 找到了就把它裁出來(lái)}
};

704. 二分查找

704. 二分查找 - 力扣（LeetCode）

原理：
[1, 2, 3, 4, 5, 6, 7, 8], t = 5

解法一：暴力解法 -> O(N)

從左往右依次用t跟數(shù)組的元素對(duì)比

比如選擇4，那么在升序數(shù)組中，4和4左邊區(qū)間的元素肯定比5小

解法二：二分查找算法“二段性”

當(dāng)數(shù)組有二段性的時(shí)候就可以用二分查找算法

二段性：
當(dāng)我們發(fā)現(xiàn)一個(gè)規(guī)律，然后根據(jù)這個(gè)規(guī)律選取某一個(gè)點(diǎn)后，能把這個(gè)數(shù)組分成兩部分
然后根據(jù)規(guī)律可以有選擇性的舍去一部分，然后根據(jù)這個(gè)規(guī)律在另一個(gè)部分里面繼續(xù)查找的時(shí)候就可以用二分查找

選擇中間點(diǎn)，時(shí)間復(fù)雜度最優(yōu)

? ? ? ? ? ? ? ? ?M
[ ? ? ? ? ? ? ? ?x ? ? ? ? ? ? ? ? ], t
?L ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? R

L = left, R = right, M = mid

樸素版本二分查找算法的核心：

第一種情況：x < t，刪除左區(qū)間 -> left = mid + 1 -> 然后再在更新之后的[left, right]區(qū)間尋找結(jié)果

第二種情況：x > t，刪除右區(qū)間 -> right = mid - 1 -> 然后再在更新之后的[left, right]區(qū)間尋找結(jié)果

第三種情況：x = t，直接返回結(jié)果

細(xì)節(jié)問(wèn)題：
1. 循環(huán)結(jié)束的條件 -> left > right

2. 為什么是正確的

3. 時(shí)間復(fù)雜度
循環(huán)1次：
2次：
3次：
...
x次：1 -> -> = n -> x = logN

代碼實(shí)現(xiàn)：C++

class Solution {
public:int search(vector<int>& nums, int target) {int left = 0, right = nums.size() - 1;while(left <= right){// int mid = (left + right) / 2; // 有溢出風(fēng)險(xiǎn)int mid = left + (right - left)/2; // 防止溢出if(nums[mid] < target) left = mid + 1;else if(nums[mid] > target) right = mid - 1;else return mid;}return -1;}
};

二分查找的樸素版本模版：

// 樸素二分模版
// int left = 0, right = nums.size() - 1;while (left <= right){int mid = left + (right - left) / 2; if (......) left = mid + 1;else if (......) right = mid - 1;else return ......;}

JZ64?求1+2+3+...+n

求1+2+3+...+n_?？皖}霸_?？途W(wǎng) (nowcoder.com)

由于題目限制了常規(guī)的控制語(yǔ)句和條件判斷，不能使用典型的循環(huán)或遞歸方法，我們需要找到一種繞開(kāi)這些限制的方法來(lái)實(shí)現(xiàn)累加。

可以先定義一個(gè)類，在其構(gòu)造函數(shù)中實(shí)現(xiàn)累加操作。

構(gòu)造函數(shù)Sum()：每次創(chuàng)建Sum類的對(duì)象時(shí)，構(gòu)造函數(shù)會(huì)執(zhí)行一次，將當(dāng)前的i值加到sum中，并將i自增1

int i = 1; // 初始化一個(gè)全局變量 i，初始值為 1，從1開(kāi)始累加
int sum = 0; class Sum {
public:Sum() {sum += i; // 在構(gòu)造函數(shù)中，將當(dāng)前的 i 值加到 sum 上++i; // 將 i 自增 1}
};

在主函數(shù)里面調(diào)用這個(gè)函數(shù)

class Solution {
public:int Sum_Solution(int n) {Sum a[n]; // 創(chuàng)建一個(gè) Sum 類的對(duì)象數(shù)組 a，大小為 nreturn sum; // 返回全局變量 sum 的值}
};

每次創(chuàng)建Sum類的對(duì)象時(shí)，構(gòu)造函數(shù)會(huì)自動(dòng)執(zhí)行累加操作。通過(guò)創(chuàng)建一個(gè)包含n個(gè)對(duì)象的數(shù)組，可以自動(dòng)調(diào)用構(gòu)造函數(shù)n次。

在C++中，創(chuàng)建一個(gè)類對(duì)象數(shù)組會(huì)自動(dòng)調(diào)用數(shù)組中每個(gè)對(duì)象的構(gòu)造函數(shù)。通過(guò)創(chuàng)建一個(gè)包含n個(gè)對(duì)象的數(shù)組，可以確保構(gòu)造函數(shù)被調(diào)用n次，從而完成累加。