baozi's page
0%

算法

发表于 更新于 分类于

埃氏筛

1
2
3
4
5
6
7
8
9
10
vector<bool> is_prime(n, true);
is_prime[0] = false;
is_prime[1] = false;
for (int i = 2; i <= n; i++) {
  if (is_prime[i]) {
    for (int j = 2 * i; j <= n; j += i) {
      is_prime[j] = false;
    }
  }
}

排序算法

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
void bubble_sort(std::vector<int>& nums) {
	int n = nums.size();
	for (int i = 0; i < n - 1; i++) {
		for (int j = 0; j < n - 1 - i; j++) {
			if (nums[j] > nums[j + 1]) {
				std::swap(nums[j], nums[j + 1]);
			}
		}
	}
}

void sellection_sort(std::vector<int>& nums) {
	int n = nums.size();
	for (int i = 0; i < n; i++) {
		int min = i;
		for (int j = i + 1; j < n; j++) {
			if (nums[min] > nums[j]) {
				min = j;
			}
		}
		std::swap(nums[i], nums[min]);
	}
} 

int partition(std::vector<int>& nums, int low, int high) {
	int pivot = nums[low];
	while (low < high) {
		while (low < high && nums[high] > pivot) {
			high--;
		}
		nums[low] = nums[high];
		while (low < high && nums[low] < pivot) {
			low++;
		}
		nums[high] = nums[low];
	}
	nums[low] = pivot;
	return low;
}
void quick_sort(std::vector<int>& nums, int low, int high) {
	if (low < high) {
		int pivot = partition(nums, low, high);
		quick_sort(nums, low, pivot - 1);
		quick_sort(nums, pivot + 1, high);
	}
}

回溯

1
2
3
4
5
6
7
8
9
10
11
12

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }
    for (选择 : 本层集合中的元素) {
        处理节点;
        backtracking(路径, 选择列表); // 递归
        撤销处理; // 回溯
    }
}

二叉树的层序遍历

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
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

//	使用二维数组保存遍历结果
//	使用队列
vector<vector<int>> level_order(TreeNode* root) {
  vector<int> temp;
  vector<vector<int>> res;
  if (!root) {
  	return res;
  }
  queue<TreeNode*> q;
  q.push(root);
  while (!q.empty()) {
    temp.clear();
    int len = q.size();
    for (int i = 0; i < len; i++) {
      TreeNode* node = q.front();
      q.pop();
      temp.push_back(node->val);
      if (node -> left) {
        q.push(node -> left);
      }
      if (node ->right) {
        q.push(node -> right);
      }
    }
    res.push_back(temp);
  }
  return res;
}

高精度乘法

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
#include <iostream>
#include <string>
#include <vector>
using namespace std;
vector<int> mul(vector<int>&A,int b)
{
    vector<int> C;
    for(int i=0,t=0;i<A.size()||t;i++)
    {
        if(i<A.size())
            t+=A[i]*b;
        C.push_back(t%10);
        t/=10;
    }
    while(C.size()>1&&C.back()==0)
        C.pop_back();
    return C;
}
int main()
{
    vector<int> A;
    string a;
    int b;
    cin >> a >> b;
    for(int i=int(a.size())-1;i>=0;i--)
        A.push_back(a[i]-'0');
    auto C=mul(A,b);
    for(int i=int(C.size())-1;i>=0;i--)
        cout << C[i];
    return 0;
}

高精度加法

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
#include <iostream>
#include <string>
#include <vector>
using namespace std;
vector<int> add(vector<int>&a,vector<int>&b)
{
    vector<int> A,B;
    if(a.size()<b.size())
    {
        A=b;
        B=a;
    }
    else
    {
        A=a;
        B=b;
    }
    vector<int> C;
    int t=0;
    for(int i=0;i<A.size();i++)
    {
        t+=A[i];
        if(i<B.size())
            t+=B[i];
        C.push_back(t%10);
        t/=10;
    }
    if(t)
        C.push_back(t);
    return C;
}
int main()
{
    vector<int> A,B;
    string a,b;
    cin >> a >> b;
    for(int i=int(a.size())-1;i>=0;i--)
        A.push_back(a[i]-'0');
    for(int i=int(b.size())-1;i>=0;i--)
        B.push_back(b[i]-'0');
    auto C=add(A,B);
    for(int i=int(C.size())-1;i>=0;i--)
        cout << C[i];
}

位运算

1
2
3
4
5
6
7
8
9
10
11
12
13
// 不使用+-来计算两数之和
int add (int a, int b) {
  while (b) {
    int carry = (a & b) << 1;	//进位
    a = a ^ b;	// 无进位结果
    b = carry;
  }
  return a;
}
// 奇数的最低位总是1，偶数的最低位总是0
if (num & 1) {
  cout << "奇数" << endl;
}

01背包

问题描述：给定 n 个物品，第 i 个物品的重量为 wgt[i−1]、价值为 val[i−1] ，和一个容量为 cap 的背包。每个物品只能选择一次，问在限定背包容量下能放入物品的最大价值。

定义状态：[i, c],物品编号i和背包容量c

对于当前物品，有两种方案

​ 不放入背包：[i, c] = [i - 1, c]

​ 放入背包：[i, c] = [i - 1, c - weight[i - 1]],价值增加val[i];

dp[i,c]=max(dp[i−1,c],dp[i−1,c−wgt[i−1]]+val[i−1]

滑动数组

定长滑动数组

给你字符串 s 和整数 k 。

请返回字符串 s 中长度为 k 的单个子字符串中可能包含的最大元音字母数。

例如s = "abciiidef", k = 3

从左到右遍历 s。
首先统计前 k−1=2 个字母的元音个数，这有 1 个。
s[2]=c 进入窗口，此时找到了第一个长为 k 的子串 abc，现在元音个数有 1 个，更新答案最大值。然后 s[0]=a 离开窗口，现在元音个数有 0 个。
s[3]=i 进入窗口，此时找到了第二个长为 k 的子串 bci，现在元音个数有 1 个，更新答案最大值。然后 s[1]=b 离开窗口，现在元音个数有 1 个。
s[4]=i 进入窗口，此时找到了第三个长为 k 的子串 cii，现在元音个数有 2 个，更新答案最大值。然后 s[2]=c 离开窗口，现在元音个数有 2 个。
s[5]=i 进入窗口，此时找到了第四个长为 k 的子串 iii，现在元音个数有 3 个，更新答案最大值。然后 s[3]=i 离开窗口，现在元音个数有 2 个。
s[6]=d 进入窗口，此时找到了第五个长为 k 的子串 iid，现在元音个数有 2 个，更新答案最大值。然后 s[4]=i 离开窗口，现在元音个数有 1 个。
s[7]=e 进入窗口，此时找到了第六个长为 k 的子串 ide，现在元音个数有 2 个，更新答案最大值。然后 s[5]=i 离开窗口，现在元音个数有 1 个。
s[8]=f 进入窗口，此时找到了第七个长为 k 的子串 def，现在元音个数有 1 个，更新答案最大值。遍历结束。

步骤：

入：下标为 i 的元素进入窗口，更新相关统计量。如果 i<k−1 则重复第一步。
更新：更新答案。一般是更新最大值/最小值。
出：下标为 i−k+1 的元素离开窗口，更新相关统计量。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int maxVowels(string s, int k) {
        unordered_set<char> vowles = {'a', 'e', 'i', 'o', 'u'};
        int ans = 0;
        int cur = 0;
        for (int i = 0; i < s.size(); i++) {
            if (vowles.count(s[i]) > 0) {
                cur++;
            }
            if (i < k - 1) {
                continue;
            }
            ans = max(ans, cur);
            if (vowles.count(s[i - k + 1]) > 0) {
                cur--;
            }
        }
        return ans;
    }
};

不定长滑动数组

给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int lengthOfLongestSubstring(string s) {
        int res = 0;
        int left = 0;
        unordered_map<char, int> cnt;
        for (int right = 0; right < s.size(); right++) {
            cnt[s[right]]++;
            while (cnt[s[right]] > 1) {
                cnt[s[left]]--;
                left++;
            }
            res = max(res, right - left + 1);
        }
        return res;
    }

越长越合法

给你一个字符串 s ，它只包含三种字符 a, b 和 c 。

请你返回 a，b 和 c 都 至少 出现过一次的子字符串数目。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int numberOfSubstrings(string s) {
        int left = 0;
        unordered_map<char, int> cnt;
        int ans = 0;
        for (int right = 0; right < s.size(); right++) {
            cnt[s[right]]++;
            while (cnt['a'] && cnt['b'] && cnt['c']) {
                cnt[s[left]]--;
                left++;
            }
            ans += left;
        }
        return ans;
    }

现在的已经满足了，更长的子串就满足，+left

越短越合法

给你一个整数数组 nums 和一个整数 k ，请你返回子数组内所有元素的乘积严格小于 k 的连续子数组的数目。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        int cur = 1;
        int res = 0;
        int left = 0;
        if (k <= 1) {
            return 0;
        }
        for (int right = 0; right < nums.size(); right++) {
            cur *= nums[right];
            while (cur >= k) {
                cur /= nums[left];
                left++;
            }
            res += right - left + 1;
        }
        return res;
    }

长的合法，长的所有子串都合法，+ right - left + 1

恰好

例如，要计算有多少个元素和恰好等于 k 的子数组，可以把问题变成：

计算有多少个元素和 ≥k 的子数组。
计算有多少个元素和 >k，也就是 ≥k+1 的子数组。
答案就是元素和 ≥k 的子数组个数，减去元素和 ≥k+1 的子数组个数。这里把 > 转换成 ≥，从而可以把滑窗逻辑封装成一个函数 f，然后用 f(k) - f(k + 1) 计算，无需编写两份滑窗代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int my_fun(vector<int>& nums, int goal) {
        int left = 0;
        int res = 0;
        int cur = 0;
        for (int right = 0; right < nums.size(); right++) {
            cur += nums[right];
            while (cur >= goal && left <= right) {
                cur -= nums[left];
                left++;
            }
            res += left;
        }
        return res;
    }
    int numSubarraysWithSum(vector<int>& nums, int goal) {
        return my_fun(nums, goal) - my_fun(nums, goal + 1);
    }

二分

1
mid = left + (right - left) / 2; //避免溢出
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// lower_bound,指向第一个 ≥ value 的元素的迭代器。
int binarySearch(vector<int>& nums,int target) {
  int left = 0;
  int right = nums.size() - 1;
  while (left <= right) {
    int mid = left + (right - left) / 2;
    if (nums[mid] >= target) {
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }
  return left;
}
1
auto it = lower_bound(nums, target);	//二分，返回的是迭代器，值为*it
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// upper_bound,指向第一个 > value 的元素的迭代器。
int binarySearch(vector<int>& nums,int target) {
  int left = 0;
  int right = nums.size() - 1;
  while (left <= right) {
    int mid = left + (right - left) / 2;
    if (nums[mid] > target) {
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }
  return left;
}