面试最常考的算法题

总结面试中最常考的算法题：

双指针

快慢指针

1.判定链表中是否含有环

2.已知链表中含有换，返回这个环的起始位置

3.寻找链表的中点

4.寻找链表的倒数第K个元素

左右指针

1.二分查找

2.两数之和

3.反转数组

4.滑动窗口

思路：
1、我们在字符串A中使用左右指针技巧，初始化left=right=0,把索引闭区间[left,right]称为一个窗口。
2、我们先不断地增加right指针扩大窗口[left,right]，直到窗口中的字符串符合要求（包含了T中的所有字符）
3、此时，我们停止增加right，转而不断增加left指针缩小窗口[left,right]，直到窗口中的字符串不再符合要求（不包含T中的所有字符了）。同时，每次增加left，我们都要更新一轮结果
4、重复第2和第3步，直到right到达字符串A的尽头。

// 模式串 B、目标串 A
let B = ...;
let A = ...;
// 双指针
let left = 0,right = 0;
// 滑动窗口中相应字符出现次数
let windows = {};
// A中字符出现次数
let needs = {};
// 限定规则操作
let valid;
// 符合规则计数
let match = 0 ;
// 变化窗口
while(right < A.length){
    // 增大窗口
    if(valid){
    windows.add(B[right]);
    }
    // 前进窗口
    right++;
    // 限定规则计数满足题意
    while(match === needs.length){
        if(valid){
        // 缩小窗口
        window.remove(B[left]);
        // 归位规则计数
        match--;
        // 继续下一轮、增大前进窗口
        left++;
        }
    }
}

参考大佬简便 抽象框架思想

string s,t;//在s中寻找t的最小覆盖子串
int left = 0, right = 0;
string res=s;
while (right < s.size()) {
    window.add(s[right]);
    right++;
    
    while (window符合要求) {
    	res = minLen(res,window);//如果这个窗口的子串更短，则更新res
        window.remove(s[left]);
        left++;
    }
}
return res;

1、3. 无重复字符的最长子串

class Solution {
public:
   int lengthOfLongestSubstring(string s){
    int left = 0, right = 0;
    unordered_map<char, int> window;
    int res = 0;//记录最长长度

    while (right < s.size()) {
        char c1 = s[right];
        window[c1]++;
        right++;

        while (window[c1]>1) {
            char c2 = s[left];
            window[c2]--;
            left++;
        }
        res = max(res,right-left);
    }
    return res;
	}
};

2、30. 串联所有单词的子串

3、76. 最小覆盖子串

4、159. 至多包含两个不同字符的最长子串

5、209. 长度最小的子数组

6、239. 滑动窗口最大值

7、340. 至多包含 K 个不同字符的最长子串

8、438. 找到字符串中所有字母异位词

9、567. 字符串的排列

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        int left = 0, right = left;
    	unordered_map<char, int> needs;
    	unordered_map<char, int> window;
    	for (char c : s1) needs[c]++;
    	int match = 0;
    
    	while (right < s2.size()) {
       	 char c1 = s2[right];
        	if (needs.count(c1)) {
            window[c1]++;
            if (window[c1] == needs[c1])
                match++;
        	 }else {
                match = 0;
                window.clear();
                left = right + 1;
            }
        right++;

        while (match == needs.size()) {
            // 如果 window 的大小合适
            // 就把起始索引 left 加入结果
            if (right - left == s1.size()) {
                return true;
            }
            char c2 = s2[left];
            if (needs.count(c2)) {
                window[c2]--;
                if (window[c2] < needs[c2])
                    match--;
            }
            left++;
        }
    }
    return false;
    }
};

10、632. 最小区间

11、727. 最小窗口子序列

二分查找

寻找一个数

字符串乘法

43字符串相乘

class Solution {
public:
    string multiply(string num1, string num2) {
        int m = num1.size(), n= num2.size();
        //结果最多为m+n位
        vector<int> res(m+n,0);
        //从个位数开始逐位相乘
        for(int i = m-1;i>=0;i--)
            for(int j=n-1;j>=0;j--){
                int mul = (num1[i]-'0') * (num2[j]-'0');
                //乘积在res对应的索引位置
                int p1 = i+j,p2=i+j+1;

                //叠加到res上
                int sum = mul +res[p2];
                res[p2] = sum%10;
                res[p1]+=sum/10;
            }
            //结果前缀可能存的0（未使用的位）
            int i=0;
            while(i<res.size() && res[i]==0) i++;

            string str;
            for(;i<res.size();i++)  
            str.push_back('0'+res[i]);

            return str.size()==0 ?"0":str;
    }
};

var multiply = function(num1, num2) {
  if (num1 == "0" || num2 == "0") return "0";
  let l1 = num1.length,
    l2 = num2.length;
  let res = new Array(l1 + l2 - 1).fill(0);
  for (let i = 0; i < l2; i++) {
    for (let j = 0; j < l1; j++) {
      res[i + j] += +num2[i] * +num1[j];
    }
  }
  let len = res.length;
  let str = "",
    num = 0;
  while (len--) {
    num += res[len];
    str = (num % 10) + str;
    num = (num / 10) | 0;
  }
  return num > 0 ? num + str : str;
};

链表

树