更新面试可能遇到以及遇到的算法题
排序
快速排序
class Solution {
public:
vector<int> MySort(vector<int>& arr) {
if (arr.empty()) {
return arr;
}
quick_sort(arr, 0, arr.size()-1);
return arr;
}
private:
void quick_sort(std::vector<int> &arr, int low, int high) {
if (low < high) {
int key = partition(arr, low, high);
quick_sort(arr, low, key-1);
quick_sort(arr, key+1, high);
}
}
int partition(std::vector<int> &arr, int low, int high) {
int base = low; // 第一个元素作为基准
while (low < high) {
while (arr[high] > arr[base] && low < high) --high;
while (arr[low] <= arr[base] && low < high) ++low;
std::swap(arr[low], arr[high]);
}
if (arr[base] >= arr[low]) { // 这里使用等于判断,防止首元素进行交换时产生越界
std::swap(arr[base], arr[low]);
return low;
} else {
std::swap(arr[base], arr[low-1]);
return low-1;
}
}
};
归并排序
class Solution {
public:
vector<int> MySort(vector<int>& arr) {
if (arr.empty()) {
return arr;
}
merge_sort(arr, 0 , arr.size()-1);
return arr;
}
private:
void merge_elem(std::vector<int> &arr, int low, int mid, int high) {
std::vector<int> temp;
int i = low, j = mid + 1;
// 排序插入
while (i <= mid && j <= high) {
if (arr[i] <= arr[j]) {
temp.push_back(arr[i++]);
} else {
temp.push_back(arr[j++]);
}
}
// 遍历剩下部分
while (i <= mid) {
temp.push_back(arr[i++]);
}
while (j <= high) {
temp.push_back(arr[j++]);
}
// 拷贝回原数组
for (int i = low, j = 0; i <= high; i++) {
arr[i] = temp[j++];
}
}
void merge_sort(std::vector<int> &arr, int low, int high) {
if (low < high) { // 分割到两个元素
int mid = (low+high) / 2;
merge_sort(arr, low, mid);
merge_sort(arr, mid+1, high);
merge_elem(arr, low, mid, high); // 递归到两个元素后合并回退
}
}
};
堆排序
class Solution {
public:
vector<int> MySort(vector<int>& arr) {
if (arr.empty()) {
return arr;
}
heap_sort(arr, 0, arr.size()-1);
return arr;
}
private:
void sink(std::vector<int> &arr, int node, int size) {
while (2*node + 1 <= size) {
int max_node = 2*node + 1;
if (max_node < size && arr[max_node] < arr[max_node+1]) { // 找到最大孩子
max_node++;
}
if (arr[node] >= arr[max_node]) {
break;
} else {
std::swap(arr[node], arr[max_node]);
}
node = max_node; // 持续下沉到叶子结点或满足条件
}
}
// 从零开始,使用(n-1)/2
void heap_sort(std::vector<int> &arr, int low, int high) {
for (int i = (high-1) / 2; i >= 0; i--) { // 构建最大堆
sink(arr, i, high);
}
while (high > 0) { // 交换-下沉 完成排序
std::swap(arr[high--], arr[0]); // 最大元素挪到末尾,再调整堆
sink(arr, 0, high);
}
}
};
冒泡排序
class Solution {
public:
vector<int> MySort(vector<int>& arr) {
if (arr.empty()) {
return arr;
}
bubble_sort(arr, arr.size()-1);
return arr;
}
private:
void bubble_sort(std::vector<int> &arr, int size) {
for (int i = 0; i < size; i++) { // n个元素循环n-1次
for (int j = 0; j < size - i; j++) { // 每次取出最大元素到最尾
if (arr[j] > arr[j+1]) {
std::swap(arr[j], arr[j+1]);
}
}
}
}
};
插入排序
class Solution {
public:
vector<int> MySort(vector<int>& arr) {
if (arr.empty()) {
return arr;
}
insertion_sort(arr, arr.size()-1);
return arr;
}
private:
void insertion_sort(std::vector<int> &arr, int size) {
for (int i = 1; i <= size; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j+1] = arr[j];
j--;
}
arr[j+1] = key;
}
}
};
选择排序
class Solution {
public:
vector<int> MySort(vector<int>& arr) {
if (arr.empty()) {
return arr;
}
selection_sort(arr, arr.size()-1);
return arr;
}
private:
void selection_sort(std::vector<int> &arr, int size) {
// 第一层循环选中n-1个元素
// 从选中元素后面 挑选出最小的元素与当前元素交换
// 选中元素最小则不交换
for (int i = 0; i < size; i++) {
int min = arr[i];
int index = i;
for (int j = i+1; j <= size; j++) {
if (arr[j] < min) {
min = arr[j];
index = j;
}
}
if (index != i) {
std::swap(arr[i], arr[index]);
}
}
}
};
计数排序
class Solution {
public:
vector<int> MySort(vector<int>& arr) {
if (arr.empty()) {
return arr;
}
counting_sort(arr, arr.size()-1);
return arr;
}
private:
void counting_sort(std::vector<int> &arr, int size) {
int max = arr[0];
std::vector<int> copy_arr(arr); // 辅助数组
for (int i = 0; i <= size; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
std::vector<int> temp(max+1, 0); // 大小为数据区间
for (int i = 0; i <= size; i++) {
temp[arr[i]]++; // 统计每个值出现的次数,存放在对应下标
}
// 计数累加
for (int i = 1; i < temp.size(); i++) {
temp[i] += temp[i-1]; // 记录当前值排的位数
}
// 反向填充数组
for (int i = size; i >= 0 ; i--) {
arr[--temp[copy_arr[i]]] = copy_arr[i]; // 索引比计数值小1,先自减
}
}
};
希尔排序
void shell_sort(std::vector<int> &a, int n) {
int i,j,gap;
// gap为步长,每次减为原来的一半。
for (gap = n / 2; gap > 0; gap /= 2) {
// 共gap个组,对每一组都执行直接插入排序
for (i = 0 ;i < gap; i++) {
for (j = i + gap; j < n; j += gap) {
// 如果a[j] < a[j-gap],则寻找a[j]位置,并将后面数据的位置都后移。
if (a[j] < a[j - gap]) {
int tmp = a[j];
int k = j - gap;
while (k >= 0 && a[k] > tmp) {
a[k + gap] = a[k];
k -= gap;
}
a[k + gap] = tmp;
}
}
}
}
}
二叉树的前中后序遍历(迭代)
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
class Solution {
public:
/**
*
* @param root TreeNode类 the root of binary tree
* @return int整型vector<vector<>>
*/
vector<vector<int> > threeOrders(TreeNode* root) {
if (root == nullptr) {
return std::vector<std::vector<int>>(3, std::vector<int>());
}
//
std::vector<std::vector<int>> res;
std::stack<TreeNode *> s;
std::vector<int> tmp;
//
s.push(root);
while (!s.empty()) {
TreeNode *cur = s.top();
s.pop();
tmp.push_back(cur->val);
if (cur->right) {
s.push(cur->right);
}
if (cur->left) {
s.push(cur->left);
}
}
res.push_back(tmp);
tmp.clear();
//
TreeNode *node = root;
while (node || !s.empty()) {
while (node) {
s.push(node);
node = node->left;
}
TreeNode *cur = s.top();
s.pop();
tmp.push_back(cur->val);
node = cur->right;
}
res.push_back(tmp);
tmp.clear();
//
s.push(root);
while (!s.empty()) {
TreeNode *cur = s.top();
s.pop();
tmp.push_back(cur->val);
if (cur->left) {
s.push(cur->left);
}
if (cur->right) {
s.push(cur->right);
}
}
std::reverse(tmp.begin(), tmp.end());
res.push_back(tmp);
return res;
}
};
#浦发银行##offer比较##中国农业银行#