这篇文章带大家了解几道富途的PHP面试算法题：

判断数组是否是出栈顺序

#include <iostream>
using namespace std;
#include <vector>
#include <stack>
//判断数组是否是出栈顺序
bool isStackOutRight(vector<int>&sIn, vector<int>&sOut, int length) {
//辅助栈
stack<int>stackdata;
int index = 0;
for (int i = 0; i < length; i++) {
if (!stackdata.empty() && stackdata.top() == sOut[i]) {
stackdata.pop();
}
else {//辅助栈为空，或者不等于首元素，指向压栈操作
while (index < length && sIn[index] != sOut[i]) {
stackdata.push(sIn[index++]);
}
if (index == length) {
return false;
}
else {
index++;
}
}
}
return true;
}

股票的最大利润

//一个数组找收益最大的买入和卖出点（股票的最大利润）
int Maxdiff(vector<int>&v) {
int length = v.size();
if (v.empty() || length < 2) {
return 0;
}
int min = v[0];
int Maxdiff = v[1] - v[0];
int m = 0, n = 1;
for (int i = 2; i < length; i++) {
if (v[i - 1] < min) {
min = v[i - 1];
m = i - 1;
}
if (v[i] - min > Maxdiff) {
Maxdiff = v[i] - min;
n = i;
}
}
cout << m << " " << n << endl;
return Maxdiff;
}
int main() {
vector<int>v = { 9,11,8,5,7,12,16,14 };
int res = Maxdiff(v);
cout << res << endl;
system("pause");
return 0;
}

二叉排序树插入

//二叉排序树插入
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int val) :val(val) {};
};
bool Insert(TreeNode *head, int key) {
if (head == nullptr) {
TreeNode *tmp = new TreeNode(key);
tmp->left = nullptr;
tmp->right = nullptr;
}
if (head->val < key) {
Insert(head->right, key);
}
else if (head->val > key) {
Insert(head->left, key);
}
else {
return false;
}
return true;
}

括号的匹配

bool isValid(string s) {
map<char, char>mp;
mp.insert(make_pair(')', '('));
mp.insert(make_pair('}', '{'));
mp.insert(make_pair(']', '['));
stack<char>stk;
for (int i = 0; i < s.size(); i++) {
if (s[i] == '(' || s[i] == '{' || s[i] == '[') {
stk.push(s[i]);
}
else if (s[i] == '}' || s[i] == ')' || s[i] == ']') {
if (stk.top() == mp[s[i]]) {
stk.pop();
}
else {
return false;
}
}
}
if (stk.empty()) {
return true;
}
}
};

死锁的例子

#include <iostream>
#include <thread>
#include <mutex>
//#include <unistd.h>
#include <windows.h>
using namespace std;
mutex mt1, mt2;
static int data1 = 1, data2 = 1;
void a2() {
mt2.lock();
data1++;
cout << " a2 " << data1 << endl;
Sleep(1);
mt1.lock();  //此时a1已经对mt1上锁，所以要等待
data2++;
mt1.unlock();
mt2.unlock();
}
void a1() {
mt1.lock();
data2++;
cout << " a1 " << data2 << endl;
Sleep(1);
mt2.lock();  //此时a2已经对mt2上锁，所以要等待
data1++;
mt2.unlock();
mt1.unlock();
}
int main() {
//int data = 1;
thread t2(a2);
thread t1(a1);
t1.join();
t2.join();
cout << "main here" << endl;  //要t1线程、t2线程都执行完毕后才会执行
system("pause");
return 0;
}

随机打乱有序数组

洗牌算法

//方法一  抽牌
#include <algorithm>
#include <ctime>
void Fisher_Yates_Shuffle1(vector<int>&nums, vector<int>&res) {
// 时间复杂度为O(n^2),空间复杂度O(n)
int k;
while (!nums.empty()) {
srand((unsigned)time(NULL));
k = rand() % nums.size();
res.push_back(nums[k]);
nums.erase(nums.begin() + k);
}
}
int main() {
vector<int>nums = { 1,2,3,4,5,6,7,8,9 };
vector<int>res;
Fisher_Yates_Shuffle1(nums, res);
for (int i = 0; i < res.size(); i++) {
cout << res[i] << " ";
}
cout << endl;
system("pause");
return 0;
}
//方法二
#include <algorithm>
#include <ctime>
int main() {
vector <int>nums = { 1,2,3,4,5,6,7,8,9 };
srand((unsigned)time(NULL));
random_shuffle(nums.begin(), nums.end());
for (int i = 0; i < nums.size(); i++) {
cout << nums[i] << " ";
}
cout << endl;
system("pause");
return 0;
}
// 洗牌算法
1. 建立一个数组大小为 n 的数组 arr，分别存放 1 到 n 的数值；
2. 生成一个从 0 到 n - 1 的随机数 x；
3. 输出 arr 下标为 x 的数值，即为第一个随机数；
4. 将 arr 的尾元素和下标为 x 的元素互换；
5. 同2，生成一个从 0 到 n - 2 的随机数 x；
6. 输出 arr 下标为 x 的数值，为第二个随机数；
7. 将 arr 的倒数第二个元素和下标为 x 的元素互换；
   ……
如上，直到输出 m 个数为止
#include <algorithm>
#include <ctime>
int main() {
vector <int>nums = { 1,2,3,4,5,6,7,8,9 };
int n = nums.size();
int k = n - 1;
while (k >= 1) {
srand((unsigned)time(NULL));
int m = rand() % (k+1);
swap(nums[m], nums[k]);
k--;
}
for (int i = 0; i < n; i++) {
cout << nums[i] << " ";
}
cout << endl;
system("pause");
return 0;
}

给定一个非负整数的列表，安排它们形成最大的数字

bool compare(int item1, int item2) {
//使用 to_string 把 int 转换成为 string
string m = to_string(item1);
string n = to_string(item2);
string mn = m + n;
string nm = n + m;
return mn > nm; // 〉降序 生成最大的数； < 升序 生成最小的数 
}
string PrintMinNumber(vector<int>nums) {
string res = "";
if (nums.size() == 0) {
return res;
}
sort(nums.begin(), nums.end(), compare);
for (int i = 0; i < nums.size(); i++) {
res += to_string(nums[i]);
}
return res;
}
int main() {
vector<int>nums = { 2,32,321 };
string res = PrintMinNumber(nums);
cout << res << endl;
system("pause");
return 0;
}

判断栈的出栈顺序是否正确

#include <iostream>
using namespace std;
#include <vector>
#include <stack>
#include <string>
bool isStackOutRight(vector<int>&sIn, vector<int>sOut, int length) {
stack<int>stackdata;//辅助栈 需要用到一个辅助栈stackdata来存储压入栈而尚未出栈的元素
int index = 0;
for (int i = 0; i < length; i++) {
if (!stackdata.empty() && stackdata.top() == sOut[i]) {
stackdata.pop();
}
else { //辅助栈为空，或者不等于首元素，指向压栈操作
while (index < length && sIn[index] != sOut[i]) {
stackdata.push(sIn[index++]);
}
if (index == length) {
return false;
}
else {
index++;
}
}
}
return true;

原地移除字符串中空格

void trimAllSpace(string &str) {
string s = " ";
int pos = str.find(s, 0);
while (pos != -1) {
str.erase(pos, 1);
pos = str.find(s, 0);
}
}
int main() {
string str = "fdsf fgfg  ggfdg ";
trimAllSpace(str);
cout << str << endl;
system("pause");
return 0;
}

更多相关技术内容咨询欢迎前往并持续关注六星社区了解详情。

程序员编程交流QQ群：805358732

如果你想用Python开辟副业赚钱，但不熟悉爬虫与反爬虫技术，没有接单途径，也缺乏兼职经验
关注下方微信公众号：Python编程学习圈，获取价值999元全套Python入门到进阶的学习资料以及教程，还有Python技术交流群一起交流学习哦。