Kenway's Blog

【笔记】经典算法模板

发表于 更新于 分类于

必背重点题

字典序的第K小数字

给一个整数n和一个k，求在字典序排序的小于n的数组中的第k个数字

解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int findKthNumber(int n, int k) {
    int count = 1;
    int cur = 1;
    while(count < k){
        int tmpCount = getCount(cur, n);
    
        if(count + tmpCount > k){ 
            cur *= 10;
            count++;
        }else{
            cur++;
            count += tmpCount;
        }
    }
        
    return cur;
}

int getCount(int cur, int n){
    int res = 0;
    for(int a = cur, b = cur+1; a <= n; a*=10, b*=10){
        res += min(n+1, b) - a;
    }
    
    return res;
}

约瑟夫环问题

0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字
例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3

1
2
3
4
5
vector<int> dp(n+1);
for (int i = 2; i <= n; i++) {
    dp[i] = (dp[i-1] + m) % i;
}
return dp[n];

二叉树的前序遍历(迭代)

  • 迭代法(统一格式)：栈 + nullptr标识已访问节点
    • 前序遍历
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      vector<int> ans;
      stack<TreeNode*> s;
      if(root) s.push(root);

      while(!s.empty()){
          TreeNode* now = s.top();
          s.pop();
          if(now){
              if(now->right) s.push(now->right);
              if(now->left) s.push(now->left);
              s.push(now);
              s.push(nullptr);
          }else{
              now = s.top();
              s.pop();
              ans.push_back(now->val);
          }
      }

      return ans;

寻找排序数组旋转后的最小值

给一个排序数组经过若干步旋转后得到的数组，求用logn的时间复杂度找到最小值(即原先排序数组的头部成员)

解法：二分法变形

1
2
3
4
5
6
7
8
9
10
11
12
13
int left = 0, right = nums.size()-1;

while(left < right){
    int mid = left +(right - left) / 2;
    
    if(nums[mid] < nums[right]){
        right = mid;
    }else{
        left = mid + 1;
    }
}

return nums[right];

进阶：这个数组里面可能有重复数字

解法：在基础上多加一个nums[mid] == nums[right]的判断

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int left = 0, right = nums.size()-1;

while(left < right){
    int mid = left +(right - left) / 2;
    
    if(nums[mid] < nums[right]){
        right = mid;
    }else if(nums[mid] < nums[right]){
        left = mid + 1;
    }else{
        right--;
    }
}

return nums[right];

快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
//快速排序从小到大
void quickSort(int left, int right, vector<int>& arr)
{
	if(left >= right) return;
	
    srand((int)time(0));
    int tmp = (rand() % (right - left + 1)) + left; 
    int temple = nums[tmp];
    nums[tmp] = nums[left];
    nums[left] = temple;

	int i, j, base, temp;
	i = left, j = right;
	base = arr[left]; 
	while (i < j){
		while (arr[j] >= base && i < j) j--;
		while (arr[i] <= base && i < j) i++; 
			temp = arr[i];
			arr[i] = arr[j];
			arr[j] = temp;
		}
	}
	
	arr[left] = arr[i];
	arr[i] = base;
	quickSort(left, i - 1, arr);
	quickSort(i + 1, right, arr);
}

归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
vector<int> sortArray(vector<int>& nums) {
    vector<int> temple(nums.size());
    mergeSort(nums,temple,0,nums.size()-1);
    
    return nums;
}


void mergeSort(vector<int>& nums, vector<int>& temple, int left, int right){
    if(left >= right) return;
        
    int mid = (right - left) / 2 + left;
    mergeSort(nums, temple, left, mid);
    mergeSort(nums, temple, mid+1, right);
    merge(nums, temple, left, right); 
        
    return;
}

void merge(vector<int>& nums, vector<int>& temple, int left, int right){
    int mid = (right - left) / 2 + left;
        
    int i = left, j = mid+1, k = 0;
    while(i <= mid && j <= right){
        if(nums[i] < nums[j]) temple[k++] = nums[i++];
        else temple[k++] = nums[j++];
    }
        
    while(j <= right) temple[k++] = nums[j++];
        
    while(i <= mid) temple[k++] = nums[i++];
        
    for(int i = left; i <=right; i++) nums[i] = temple[i-left]; 
        
    return;
}

堆排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
vector<int> main(vector<int> nums){
    heapSort(nums);
    
    return nums;
}

void heapSort(vector<int> &arr, int size){
    for(int i=size/2 - 1; i >= 0; i--){
        adjust(arr, size, i);
    }
 
    for(int i = size - 1; i >= 1; i--){
        swap(arr[0], arr[i]);
        adjust(arr, i, 0);
    }
}

void adjust(vector<int> &arr, int len, int index){
    int left = 2*index + 1;
    int right = 2*index + 2;
 
    int maxIdx = index;
    if(left<len && arr[left] > arr[maxIdx]) maxIdx = left;
    if(right<len && arr[right] > arr[maxIdx]) maxIdx = right;
 
    if(maxIdx != index){
        swap(arr[maxIdx], arr[index]);
        adjust(arr, len, maxIdx);
    }
}

至少有 K 个重复字符的最长子串

给你一个字符串 s 和一个整数 k ，请你找出 s 中的最长子串， 要求该子串中的每一字符出现次数都不少于 k 。返回这一子串的长度
解法：对字符种类个数kind依次枚举+滑动窗口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
int longestSubstring(string s, int k) {
    int res = 0;
    for(int i = 1; i <= 26; i++){
        res = max(res, box(s, k, i));
    }
    return res;
}

int box(string s, int k, int kind){
    int left = 0, right = 0;
    unordered_map<char, int> memo;
    
    int maxLen = INT_MIN;
    int isValid = 0;
    while(right < s.size()){
        memo[s[right]]++;
        if(memo[s[right]] == k){
            isValid++;
        }
        right++;
        
        while(memo.size() > kind){
            memo[s[left]]--;
            if(memo[s[left]] == k-1) isValid--;
            if(memo[s[left]] == 0) memo.erase(s[left]);
            left++;
        }
        
        if(isValid == kind) maxLen = max(maxLen, right-left);
    }
    
    return maxLen;
}

分割数组的最大值

给一个数组和分割次数m，求分割m次后，最小的最大子数组之和，例如1,2,3,4分割两次得到123和4，最大子数组之和为6，该值在这个分割情况是最小的

解法：合法函数+二分查找

  • 最大子数组之和，最小值为最大数字，最大值为原数组之和
  • 亮点是：已知上下界，将其转换成二分查找的思想
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    int splitArray(vector<int>& nums, int m) {
        int left = 0, right = 0;
        for(int i = 0; i < nums.size(); i++){
            right += nums[i];
            left = max(left, nums[i]);
        }

        int res = 0;
        while(left <= right){
            int mid = left + (right - left) / 2;
            
            if(isValid(nums, m, mid)){
                res = mid;
                right = mid - 1;
            }else{
                left = mid + 1;
            }
        }
        
        return res;
    }

    bool isValid(vector<int>& nums, int m, int x){
        int sum = 0;
        int count = 0;
        for(int i = 0; i < nums.size(); i++){
            if(sum + nums[i] > x){
                sum = nums[i];
                count++;
            }else{
                sum += nums[i];
            }
        }
        
        if(sum != 0) count++;
        
        if(count > m) return false;
        return count;
    }

搜寻名人

有编号从0到n-1的人，其中有一个名人，所有人都认识名人，名人不认识任何人。只能用knows(i,j)来询问i是否认识j

解法：

  • 先找出不认识任何人的人famous，利用所有人都认识名人这一点来迭代更新
  • 检验这个人是否是名人
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    int famous = 0;
    for(int i = 1; i < n; i++){
        if(knows(famous, i)){
            famous = i;
        }
    }

    for(int i = 0; i < n; i++){
        if(i == famous) continue;
        
        if(knows(famous, i) || !knows(i, famous)) return -1;
    }

    return famous;

最长重复子串

给你一个字符串 s ，考虑其所有 重复子串 ：即 s 的（连续）子串，在 s 中出现 2 次或更多次。这些出现之间可能存在重叠。例如输入：s = “banana” 输出：”ana”

解法：二分查找+字符串哈希

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
string longestDupSubstring(string s) {
    int len = -1, index = -1;
    
    int left = 1, right = s.size();
    while(left <= right){
        int mid = (right-left) / 2 + left;
        
        int t = isValid(s, mid);
        if(t != -1){
            index = t;
            len = mid;
            left = mid + 1;
        }else right = mid - 1;
    }
    
    if(len == -1 || index == -1)  return "";
    return s.substr(index, len);
}
    
    int isValid(string& s, int m){
    int mode = pow(10, 9) + 7;
    int base1 = 131;
    unordered_map<int, bool> memo;
    
    vector<unsigned long long> hash1(s.size()+1);
    vector<unsigned long long> power1(s.size()+1);
        
    power1[0] = 1;
    for(int i = 1; i <= s.size(); i++){
        hash1[i] = hash1[i-1] * base1 + s[i-1]-'a';
        power1[i] = power1[i-1] * base1;
    }
    
    for(int i = 1; i + m -1 <= s.size(); i++){
        int j = i + m - 1;
        int code1 = hash1[j] - hash1[i-1]*power1[j-i+1];
        
        if(memo.count(code1) > 0){
            return i-1;
        }
        
        memo[code1] = true;
    }
    
    return -1;
}