复试练习

int dp[1002][1002]; class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * s1和s2最长公共子序列的长度 * @param s1 string字符串 * @param s2 string字符串 * @return int整型 */ int LCS(string s1, string s2) { // 最小问题的情况 for (int j = 0; j <= s1.size(); j++) { dp[0][j] = 0; // s1前缀为0 所以最大公共子序列长度为0 } for ...

#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <vector> #include <algorithm> using namespace std; // 全局数组 int father[1010]; // 结构体 边 struct Edge { int u; int v; int weight; // 带权图 // 构造函数的特点 类里面 没有返回值 名字和类名相同 Edge(int _u, int _v, int _weight) { u = _u; v = _v; weight =...

#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> using namespace std; // 全局变量 int father[1001]; int setCount = 0; // 统计并查集(相互不连通)的数量 // 初始化 void InitDisjoinSet(int n) { for (int i = 1; i <= n; i++) { father[i] = i; } } // 找根结点 int FindDisjoinSet(int u) { if (u == father[u]) { return u; } ...

#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <string> using namespace std; // 无需parent找父节点 struct TreeNode { char data; TreeNode* left; TreeNode* right; }; // 创建二叉搜索/排序树 void InsertBST(TreeNode* &proot, char data) { TreeNode* pNew = new TreeNode; pNew->data = data; ...

#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> using namespace std; struct TreeNode { char data; TreeNode* left; TreeNode* right; }; // 分治法 TreeNode* RecursiveBuildTree(int &i,char str[]) { char c = str[i]; i++; if (c == '#') { return NULL; // 此子树为空子树 } else { TreeNode* pNew = new Tree...

#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <string> #include <vector> using namespace std; // 求n的指数形式 string Get2sExponet(int n) { if (n == 0) { return "0"; // 0单独处理 } vector<int> exp; // 获取二进制1下标 // 从大到小 / 从高到低 方便计算值 for (int i = 15; i >= 0; i--...

#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <string> #include <stack> #include <map> using namespace std; int main() { char str[1000] = { 0 }; map<char, int> priority = { // 定义运算优先级 {'\0', 0}, // 结束符优先级最低 {'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}, }; while ...

#include <iostream> #include <stack> // 后进先出 using namespace std; int main() { stack<string> strStack; stack<string> outStack; // 备份strStack栈，不影响其继续压栈 int m; string str; cin >> m; for (int i = 1; i <= m;i++) { cin >> str; strStack.push(str); outStack = strStack...

#include <stdio.h> #include <stack> #include <string> using namespace std; int main() { stack<string> myStack; // stack<char[20]>这样错误 int m; scanf("%d", &m); for (int i = 0; i < m; i++) { char strArr[200] = { 0 }; // c语言字符数组 scanf("%s", strArr...

// 求整数部分不补零的方法(vector<char>/string前置补零时间复杂度高) #include <iostream> #include <string> using namespace std; // 获取整数部分 string getInteger(string a) { return a.substr(0, a.find(".")); } // 获取小数部分 string getFraction(string a) { return a.substr(a.find(".") + 1, a.size()...

#include <iostream> #include <string> using namespace std; // 获取整数部分 string getInteger(string a) { // 从0开始 截取a.find(".")长度 // 截取[ ) 左闭右开区间 return a.substr(0, a.find(".")); } // 获取小数部分 string getFraction(string a) { // a.size()实际长度，但是下标要-1。 find()得到的为下标 // 从a.find(&quo...

#include <iostream> // map不允许 关键字重复 的键值对，只会读入第一对，其它无影响 #include <map> #include <vector> #include <algorithm> using namespace std; int main() { char input[200] = {0}; // 初始化 // 按照key排序，会打乱 原先输入顺序，关于顺序可以用vector记录 multimap<char, int> charAndPos; // 题目要求可以记录重复的char vector&l...

#include <iostream> #include <map> #include <vector> #include <algorithm> using namespace std; int main() { char str[200] = { 0 }; // 字符串 //记录每个字符的位置 一对多 // !!! 相同字符，可以按照先后顺序往 动态数组 存入位置，即一个字符，对应多个位置 // 如 字符a 动态数组中 2 表示位置为2 map<char, vector<int>> timesMap; vector&l...

#include <iostream> #include <vector> // 数据长度未知，用动态数组 using namespace std; int main() { int n, target; // 迭代器需要另配 记录下标的数据 while (cin >> n) { vector<int> dataSource(n); for (int i = 0; i < n; i++) { cin >> dataSource[i]; } cin >> target; for (int i = 0; i < n...

#include <iostream> #include <map> using namespace std; int main() { int n, target; map<int, int> dataSource; pair<int, int> temp; // 准备插入的键值对 while (cin >> n) { dataSource.clear(); // 重置 for (int i = 0; i < n; i++) { cin >> temp.first; temp.second = i; dataSou...

#include <iostream> #include <vector> using namespace std; int main() { int L, M, start, end, count; // 用标志数组表示有树无树 vector<int> interval; vector<int>::iterator it; while (cin >> L >> M) { // 多轮一定要记得清空必要的上一轮数据 count = 0; interval.clear(); // 动态数组填充值 while (L >= ...

#include <iostream> #include <vector> using namespace std; int main() { int factorSum; // 因子总和 vector<int> factor; // 因子 vector<int> equalNumber; // 完数 vector<int> overNumber; // 盈数 vector<int>::iterator it; // 迭代器 for (int i = 2; i <= 60; i++) { factor.clear()...

#include <iostream> using namespace std; void nextDay(int& year, int& month, int& day) { // 每个月份的天数数组 int dayOfMonth[] = { 0,31,28,31,30,31,30,31,31,30,31,30,31 }; // 是否闰年判断条件 bool isLeap = year % 400 == 0 || year % 4 == 0 && year % 100 != 0; if (isLeap) { dayOfMonth[2] = 2...

#include <iostream> using namespace std; void nextDay(int &year,int & startMonth,int & startDay) { // 每个月份的天数数组 int dayOfMonth[] = { 0,31,28,31,30,31,30,31,31,30,31,30,31 }; // 是否闰年判断条件 bool isLeap = year % 400 == 0 || year % 4 == 0 && year % 100 != 0; if (isLeap) { dayOfMo...