二分查找：
int binarySearch(int arr[], int n, int target) {
int left = 0;
int right = n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid; // 找到目标值，返回索引
} else if (arr[mid] < target) {
left = mid + 1; // 目标值在右半部分，缩小左边界
} else {
right = mid - 1; // 目标值在左半部分，缩小右边界
}
}
return -1; // 没有找到目标值
}
选择排序：
void selectionSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
// 找到未排序部分的最小元素的索引
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// 将最小元素与当前位置交换
swap(arr[i], arr[minIndex]);
}
}
插入排序：
void insertionSort(int arr[]) {
int n = arr.size();
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
// 将arr[i]插入到已排序序列arr[0...i-1]中的正确位置
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
计数排序：
void countingSort(int arr[], int n) {
// 找到数组中的最大值
int maxVal = *max_element(arr, arr + n);
// 创建计数数组，初始化为0
int count[maxVal + 1] = {0};
// 计数每个元素的出现次数
for (int i = 0; i < n; i++) {
count[arr[i]]++;
}
// 根据计数数组构造排序后的数组
int index = 0;
for (int i = 0; i <= maxVal; i++) {
while (count[i] > 0) {
arr[index++] = i;
count[i]--;
}
}
}
// 高精度加法，a和b都是字符串形式的非负整数
vector<int> add(string &a, string &b) {
vector<int> result;
int carry = 0; // 进位
int sum = 0;
for (int i = a.size() - 1, j = b.size() - 1; i >= 0 || j >= 0 || carry; i--, j--) {
sum = carry;
if (i >= 0) sum += a[i] - '0';
if (j >= 0) sum += b[j] - '0';
result.push_back(sum % 10);
carry = sum / 10;
}
reverse(result.begin(), result.end());
// 去除前导零
while (result.size() > 1 && result[0] == 0) {
result.erase(result.begin());
}
return result;
}
高精度乘单个整型：
vector<int> multiply(string &a, int b) {
vector<int> result(a.size(), 0);
int carry = 0;
for (int i = a.size() - 1; i >= 0; --i) {
int product = (a[i] - '0') * b + carry;
result[i] = product % 10;
carry = product / 10;
}
if (carry) result.insert(result.begin(), carry);
// 移除前导零
while (result.size() > 1 && result.front() == 0) result.erase(result.begin());
return result;
}
2 条评论
-
xrqmzl LV 1 SU @ 2024-8-12 16:00:45已修改
1. 计算中缀表达式的过程
中缀表达式是一种我们常见的表达式表示形式，运算符位于操作数之间，例如
(3 + 5) * 2。计算步骤：
- 初始化：
- 创建一个操作数栈用于存放数字。
- 创建一个操作符栈用于存放运算符。
- 从左到右扫描表达式：
- 如果是数字：将数字读取并压入操作数栈。
- **如果是左括号
(**：将左括号压入操作符栈。 - **如果是右括号
)**：- 弹出操作符栈中的运算符，并从操作数栈中弹出对应数量的操作数进行计算，直到遇到左括号为止。
- 弹出左括号（但不处理它）。
- **如果是运算符（
+、-、*、/、^等）**：- 比较当前运算符与操作符栈顶运算符的优先级。
- 如果当前运算符的优先级低于或等于栈顶运算符的优先级，则弹出栈顶运算符，并从操作数栈中弹出对应数量的操作数进行计算，将结果压入操作数栈。
- 重复上述步骤，直到当前运算符的优先级高于栈顶运算符的优先级或栈为空。
- 将当前运算符压入操作符栈。
- 表达式扫描完成后：
- 将操作符栈中剩余的运算符依次弹出，并从操作数栈中弹出对应数量的操作数进行计算。
- 结果：
- 操作数栈中的唯一值即为表达式的最终计算结果。
2. 计算前缀表达式的过程
前缀表达式，也称为波兰表达式，是一种运算符位于操作数之前的表达式形式，例如
* + 3 5 2。计算步骤：
- 初始化：
- 创建一个操作数栈用于存放数字。
- 从右到左扫描表达式：
- 如果是数字：将数字读取并压入操作数栈。
- **如果是运算符（
+、-、*、/、^等）**：- 从操作数栈中依次弹出两个数字，将其与当前运算符进行计算。
- 将计算结果压入操作数栈。
- 表达式扫描完成后：
- 操作数栈中只剩下一个元素，这个元素即为表达式的最终计算结果。
3. 计算后缀表达式的过程
后缀表达式，也称为逆波兰表达式，是一种运算符位于操作数之后的表达式形式，例如
3 5 + 2 *。计算步骤：
- 初始化：
- 创建一个操作数栈用于存放数字。
- 从左到右扫描表达式：
- 如果是数字：将数字读取并压入操作数栈。
- **如果是运算符（
+、-、*、/、^等）**：- 从操作数栈中依次弹出两个数字，将其与当前运算符进行计算。
- 将计算结果压入操作数栈。
- 表达式扫描完成后：
- 操作数栈中只剩下一个元素，这个元素即为表达式的最终计算结果
判断是否为中缀表达式：
#include <bits/stdc++.h> using namespace std; bool isInfix(const string &exp) { int lp = 0; // 左括号计数 int rp = 0; // 右括号计数 bool expOp = false; // 期待操作符 bool prevOp = false; // 前一个是否为操作符 bool prevNum = false; // 前一个是否为数字 bool neg = false; // 负号标志 for (int i = 0; i < exp.size(); ++i) { char c = exp[i]; if (isspace(c)) { continue; // 忽略空格 } if (c == '(') { lp++; expOp = false; prevOp = false; prevNum = false; neg = false; } else if (c == ')') { rp++; if (rp > lp) return false; if (prevOp) return false; expOp = true; prevOp = false; prevNum = false; } else if (c == '+' || c == '*' || c == '/' || c == '^') { if (!expOp) return false; if (prevOp) return false; expOp = false; prevOp = true; prevNum = false; neg = false; } else if (c == '-') { if (i == 0 || exp[i - 1] == '(' || prevOp) { neg = true; // 负号 continue; } if (!expOp) return false; if (prevOp) return false; expOp = false; prevOp = true; prevNum = false; neg = false; } else if (isdigit(c)) { if (expOp) return false; expOp = true; prevOp = false; prevNum = true; neg = false; } else { return false; // 非法字符 } } if (lp != rp) return false; if (prevOp) return false; return true; } int main() { string expr; cout << "Enter an expression: "; cin >> expr; if (isInfix(expr)) { cout << "是中缀表达式" << endl; } else { cout << "不是中缀表达式" << endl; } return 0; }中缀转后缀的方法：
将一个中缀表达式（我们日常使用的算术表达式，如
3 + 4 * 2 / (1 - 5)）转换为后缀表达式（也称为逆波兰表示法，RPN），可以使用栈这一数据结构来实现。后缀表达式的特点是运算符位于其操作数之后，这种表示法便于计算机处理算术表达式，无需考虑括号和运算符优先级。转换步骤：
- 初始化两个栈：运算符栈 s1 和存储中间结果的栈 s2；
- 从左至右扫描中缀表达式；
- 遇到操作数时，将其压入 s2；
- 遇到运算符时，比较其与 s1 栈顶运算符的优先级：
- 如果 s1 为空，或栈顶运算符为左括号
(，则直接将此运算符入栈； - 否则，若优先级比栈顶运算符的高，也将运算符压入 s1；
- 否则，将 s1 栈顶的运算符弹出并压入到 s2 中，再次转到 (4-1) 与 s1 中新的栈顶运算符相比较；
- 如果 s1 为空，或栈顶运算符为左括号
- 遇到括号时：
- 如果是左括号
(，则直接压入 s1； - 如果是右括号
)，则依次弹出 s1 栈顶的运算符，并压入 s2，直到遇到左括号为止，此时将这一对括号丢弃；
- 如果是左括号
- 重复步骤 2 至 5，直到表达式的最右边；
- 将 s1 中剩余的运算符依次弹出并压入 s2；
- 依次弹出 s2 中的元素，将其逆序排列，即为后缀表达式。
例子：
将中缀表达式
1 + ((2 + 3) * 4) - 5转换为后缀表达式的过程如下：- 扫描到
1，压入 s2； - 扫描到
+，压入 s1； - 扫描到
(，压入 s1； - 扫描到
2，压入 s2； - 扫描到
+，压入 s1； - 扫描到
3，压入 s2； - 扫描到
)，依次弹出 s1 栈顶的+、(，压入 s2； - 扫描到
*，压入 s1； - 扫描到
4，压入 s2； - 扫描到
)，弹出*，压入 s2； - 扫描到
-，压入 s1； - 扫描到
5，压入 s2； - 表达式结束，依次弹出 s1 中的
+、-，压入 s2； - 逆序弹出 s2 中的元素，得到后缀表达式
1 2 3 + 4 * + 5 -。
通过这种方法，任何中缀表达式都可以转换为后缀表达式。
❤️ 3👍 3😄 1 - 初始化：
-
@ 2024-6-25 16:56:05
M进制转10进制：
#include <bits/stdc++.h> using namespace std; int main() { string str; cin >> str; int m; cin >> m; int x = 0; int k = 0; int sum = 0; int len = str.size(); char cc = ' '; int temp = 0; for (int j = len - 1; j >= 0; j--) { cc = str[j]; if (cc >= 'A' && cc <= 'Z') { temp = int(cc - 'A' + 10); } else { temp = int(cc - '0'); } if (temp != 0) sum += temp * pow(m, k); k++; } cout << sum; return 0; }10进制转M进制
#include <bits/stdc++.h> using namespace std; // A= 10, B=11, C=12,D=13,E=14 string strB(int x,int b){ //10进制转b进制 1-20 string str=""; int yushu=0; while(x!=0){ yushu=x%b; if(yushu>9){ str+=char(yushu+'A'-10); }else{ str+= char(yushu+'0'); } x/=b; } std::reverse(str.begin(),str.end());//将一个字符串倒序的函数用法 return str; } int main(){ int a; int b; cin>>a>>b; string str=strB(a,b); cout<<str; return 0; }👍 2
- 1