1、二分查找
#include <iostream> #include<vector> using namespace std; int main() { int n; scanf_s("%d", &n); vector<int> nums(n); for (int i = 0; i < n; i++) scanf_s("%d", &nums[i]); int target; scanf_s("%d", &target); int left = 0, right = n - 1; int cnt = 0; while (left < right) { int mid = (left + right) / 2; cnt++; if (nums[mid] == target) break; else if (nums[mid] > target) right = mid - 1; else left = mid + 1; } cout << cnt << endl; return 0; }
2、编辑距离
dp[i][j] 表示将 s1 前 i 个字符转换为 s2 前 j 个字符所使用的最少操作数
- s1[i - 1] == s2[j - 1],dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j] + 1, dp[i][j - 1] + 1))
- s1[i - 1] != s2[j - 1],dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1
#include <iostream> #include<vector> #include<algorithm> using namespace std; int minDistance(string word1, string word2) { int m = word1.size(), n = word2.size(); vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0)); for (int i = 0; i <= m; i++) dp[i][0] = i; for (int j = 0; j <= n; j++) dp[0][j] = j; for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { int dist = min(dp[i - 1][j], dp[i][j - 1]) + 1; if (word1[i - 1] == word2[j - 1]) dp[i][j] = min(dp[i - 1][j - 1], dist); else dp[i][j] = min(dp[i - 1][j - 1] + 1, dist); } } return dp[m][n]; } int main() { string word1, word2; cin >> word1 >> word2; cout << minDistance(word1, word2) << endl; return 0; }
3、二叉树遍历
构建二叉树
#include <iostream> #include<vector> #include<algorithm> using namespace std; struct TreeNode { int val; TreeNode* left, * right; TreeNode(int v) : val(v), left(NULL), right(NULL) {} }; // 先序构建二叉树 int pos = 0; TreeNode* createTree(string s) { char c = s[pos++]; if (c == '#') return NULL; TreeNode* root = new TreeNode(c - '0'); root->left = createTree(s); root->right = createTree(s); return root; } // 二叉排序树 TreeNode* insert(TreeNode* root, int num) { if (root == NULL) return new TreeNode(num); if (root->val > num) root->left = insert(root->left, num); else root->right = insert(root->right, num); return root; } void preOrder(TreeNode* root) { if (root == NULL) return; cout << root->val << " "; preOrder(root->left); preOrder(root->right); } int main() { string s; cin >> s; //TreeNode* root = createTree(s); int num; cin >> num; TreeNode* root = new TreeNode(num); for (int i = 0; i < 4; i++) { cin >> num; root = insert(root, num); } preOrder(root); return 0; }
4、Hanoi 塔
move(n, A, C) 相当于 move(n - 1, A, B) => move(1, A, C) => move(n - 1, B, C)
总次数 nums[n] = 2*nums[n - 1] + 1 = 2^n - 1
#include <iostream> #include<vector> #include<algorithm> using namespace std; int cnt = 0; void move(int n, int total, char a, char b, char c) { if (n == 1) { cnt++; if(total - cnt < 100) printf("%d:%c->%c\n", 100 - total + cnt, a, c); } else { move(n - 1, total, a, c, b); move(1, total, a, b, c); move(n - 1, total, b, a, c); } } int main() { int n; cin >> n; int total = pow(2, n) - 1; printf("%d\n", total); move(n, total, 'A', 'B', 'C'); return 0; }