不完整的笔试总结
趋势科技：
问题1：
台阶，初始站在台阶0 ，每次可以走一个台阶或者两个台阶
规定坏台阶数量 并指明坏台阶所在的位置，求到达终点的方案个数。
典型的斐波那契数列的基础上修改
输入：
10 2
3 5
#include<bits/stdc++.h>
using namespace std;
int main(){
int steps, badsteps;
cin >> steps >> badsteps;
vector<int> dp(steps+1, 0);
for (int i = 0; i < badsteps; i++)
{
int index;
cin >> index;
//走到该台阶的方法为0
dp[index] = -1;
}
dp[0] = 1;
dp[1] = dp[1] == -1 ? 0 : 1;
for (int i = 2; i <= steps;i++){
if(dp[i]==-1){
dp[i] = 0;
}
else{
dp[i] = dp[i - 1] + dp[i - 2];
}
}
cout<< dp[steps]<<endl;
return 0;
}问题2：
扑克牌排序，包含花色。
牌大小 A 2 3 4 5 6 7 8 9 T J Q K
花色 d< c< h< s
输入任意张数的扑克牌，进行从小到大进行排序
#include<bits/stdc++.h>
using namespace std;
struct node{
char color;
int num;
int c;
};
int check(char t){
switch (t)
{
case 'd':
return 1;
case 'c':
return 2;
case 'h':
return 3;
case 's':
return 4;
}
}
int judge(char c){
switch (c)
{
case 'A':
return 1;
case 'T':
return 10;
case 'J':
return 11;
case 'Q':
return 12;
case 'K':
return 13;
}
}
bool cmp(node n1,node n2){
if(n1.num!=n2.num){
return n1.num < n2.num;
}
return n1.c < n2.c;
}
int main()
{
string str;
vector<string> poker;
do{
cin >> str;
poker.push_back(str);
} while (getchar() != '\n');
int k = 0;
int n = poker.size();
node nd[n];
for (int i = 0; i < n; i++)
{
//题目中10 用T表示了，如果扑克牌10是用数字表示，则需要单独处理
// if(poker[i][0] == '1'){
// nd[k].num = 10;
// nd[k].color = poker[i][2];
// nd[k].c = check(nd[k].color);
// }
if(poker[i][0] >='2' && poker[i][0]<='9'){
nd[k].num = poker[i][0] - '0';
nd[k].color = poker[i][1];
nd[k].c = check(nd[k].color);
}
else{
nd[k].num = judge(poker[i][0]);
nd[k].color = poker[i][1];
nd[k].c = check(nd[k].color);
}
k++;
}
sort(nd, nd + n, cmp);
for (int i = 0; i < n;i++){
if(nd[i].num>=10){
switch (nd[i].num){
case 10:
cout << 'T';
break;
case 11:
cout << 'J';
break;
case 12:
cout << 'Q';
break;
case 13:
cout << 'K';
break;
}
}
else{
cout << nd[i].num;
}
cout << nd[i].color << " ";
}
return 0;
}
// 输入：8s Tc Jc Js Qs Kc As 4h
// 输出：1s 4h 8s Tc Jc Js Qs Kc选择题： 二维数组的指针表示
#include<bits/stdc++.h>
using namespace std;
int main(){
int a[2][4] = {{1, 2, 3, 4}, {5,10, 7, 9}};
cout << "输出" << a[1][1] << endl;
cout << "输出" << *(a[1]+2) << endl;
cout << "输出" << *(*(a+1)+2) << endl;
cout << "输出" << *(a[1])+3 << endl;
cout << "输出" << *((a[1]+1)) << endl;
return 0;
}
//
输出10
输出7
输出7
输出8
输出10 面试问题：
1.linux下获知系统版本信息的方式：
lsb_release -a2.查找某一个文件的路径
find . -name "文件名"
find . name exam1.cpp
结果
./Linux/design/exam1.cpp
./Linux/string/exam1.cpp
./Linux/redbook/exam1.cpp
./Linux/tencent/exam1.cpp
./Linux/meituan/exam1.cpp
3.字符
char *p = "hello"
char p[] = "hello"
区别是什么？
如果是在C++环境下 char *p 不能直接指向常量字符串，会报错。
在C语言中可以。
这两条命令，指针p和字符串数组都是在栈中。"hello"是在常量区。p指针指向”hello“所在的地址 。
"hello"赋值给字符串数组p。
两者区别在于p指针不能改变常量字符串的值。而字符串数组可以修改其中的字符。另外进行一部分测试，sizeof ，char[] 字符串常量的长度包含最后一个空字符。
#include<iostream>
#include<string>
using namespace std;
int main(){
char a[] = "hello";
cout << "size of a:" << sizeof(a)<<endl;
char *p = a;
cout << "p[2] = " << p[2] << endl;
a[4] = 's';
cout << "size of a:" <<sizeof(a) << ","
<< "sizeof(p):" << sizeof(p) << endl;
cout << a << endl;
cout <<"p[2] ="<< p[2] << endl;
string str = "hello";
cout << "size of str:" << sizeof(str) << ","
<< "length of str:" << str.length() << endl;
return 0;
}
结果：
size of a:6
p[2] = l
size of a:6,sizeof(p):8
hells
p[2] =l
size of str:32,length of str:5
美团:
问题1：
优美字符串，如果一个字符串改变顺序后存在不是回文字符串的字符串，则说明这个字符串是优美字符串。
例子：
aaaaa 不是优美字符串
abba -> abab 是优美字符串
c
a 一个字符不是优美字符串
//其实如果字符串长度大于1 这个字符串还有两个及以上不同字符 则是优美字符串思路：从小到达进行排序
双指针 i ，j
while(i<j){
判断s[i]== s[j]
}#include<bits/stdc++.h>
using namespace std;
bool cmp(char s1,char s2){
return s1 < s2;
}
bool ans(string &s){
sort(s.begin(), s.end(),cmp);
int i = 0;
int j = s.length()-1;
while(i<j){
if(s[i]==s[j]){
i++;
j--;
}
else{
return true;
}
}
//false 说明是回文 不是优美
return false;
}
int main(){
int n;
cin >> n;
vector<string> str(n,"");
for (int i = 0; i < n; i++)
{
cin >> str[i];
}
for (int i = 0; i < str.size();i++)
{
if(str[i].length() == 1){
cout << "NO" << endl;
}
else if(ans(str[i]) == true){
cout << "YES" << endl;
}
else if(ans(str[i])==false){
cout << "NO" << endl;
}
}
return 0;
}博乐科技：
题目1：
给定数组，以及一个int型的值K，寻找数组中两数之和小于K的最大值
思路：排序，双指针，指向index[0] 和index[n-1]，while(i< j){}
找出符合条件的最大值
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 输入有两个参数L和K，其中L是一个整型1维数组，K是一个整型变量。0 < L.length < 10000；0 < L[i] < 1000；0 < K > 2000。
* @param L int整型vector 整型一维数组
* @param K int整型 整型变量
* @return int整型
*/
int TwoSum(vector<int>& L, int K) {
// 排序
sort(L.begin(),L.end());
int i = 0;
int j = L.size()-1;
int res = -1;
while(i<j){
int sum = L[i]+L[j];
if(sum<K){
i++;
res = max(res,sum);
}
else {
j--;
}
}
return res;
}
};题目4：N皇后问题 :输出 所有可行方案
经典回溯问题解法 ，重点在于创建多个bool数组进行条件判断
以及字符串二维数组初始化
vector<string>的初始化方法
vector<vector<string>>(n,string(n,'.'));#include<bits/stdc++.h>
using namespace std;
class Solution
{
private:
vector<bool> col, dia1, dia2;
vector<vector<string>> res;
void putQueen(int n,int index,vector<int> &row){
if(index == n){
res.push_back(generateBoard(n, row));
return;
}
for (int i = 0; i < n;++i){
//确保各列 ，各对角线唯一
if (!col[i] && !dia1[index + i] && !dia2[index - i + n - 1]){
row.push_back(i);
col[i] = true;
dia1[index + i] = true;
dia2[index - i + n - 1] = true;
putQueen(n, index + 1, row);
//回溯
col[i] = false;
dia1[index + i] = false;
dia2[index - i + n - 1] = false;
row.pop_back();
}
//如果不满足条件则跳过寻找下一个列位置
}
return;
}
vector<string>generateBoard(int n,vector<int> &row){
assert(row.size() == n);
//字符串数组初始化
vector<string> board(n, string(n, '.'));
for (int i = 0; i < n;++i){
board[i][row[i]] = 'Q';
}
return board;
}
public:
vector<vector<string>> solveNQueens(int n) {
res.clear();
//布尔数组进行判断
col = vector<bool>(n, false);
dia1 = vector<bool>(2 * n - 1, false);
dia2 = vector<bool>(2 * n - 1, false);
//row数组确定每一行row 第几列放置皇后
vector<int> row;
putQueen(n, 0, row);
return res;
}
};腾讯tencent：
问题1：
存在一个数字由4个以上公因数组成，要求每两个公因数的差不小于n。
输入一个数字n，求出可以构成的最小的数。
思路：公因数包含1和本身。
所以只要找出两个公因数，由于合数还可以再分解，会使得差小于n。
所以另外两个公因数应该为差大于等于n的质数。
根据筛选先求出质数表，自己规定数字范围。
#include<bits/stdc++.h>
using namespace std;
void primelist(vector<int> &ans,int num){
vector<bool> isprime(num + 1, true);
for (int i = 2; i <= num; i++)
{
if(isprime[i]){
ans.push_back(i);
//存在倍数关系的数字全部筛选掉
for (int j = i * i; j <= num;j+=i){
isprime[j] = false;
}
}
}
return;
}
int main(){
int n;
cin >> n;
vector<int> ans;
primelist(ans,10000);
int res = 1;
int k = 2;
set<int> st;
for (auto num : ans)
{
st.insert(num);
}
//st中为去重的素数
int tmp = 1;
while (k < 4 )
{
tmp += n;
while(st.find(tmp) == st.end())
{
tmp++;
}
res *= tmp;
k++;
}
cout << "res = " << res<<endl;
return 0;
}
WPS：
字符串转字符atoi
简单模式：只对十进制数字有效
#include<iostream>
using namespace std;
int atoi(const char * str){
int value = 0;
int sign = 1;
if(*str == '-'){
sign = -1;
str++;
}
while(*str >='0' && *str <='9'){
value = value * 10 + *str - '0';
str++;
}
return sign * value;
}
int main(){
cout << atoi("123")<<endl;
return 0;
}
//123包含8进制和16进制的atoi函数
#include<iostream>
using namespace std;
int atoii(const char * str){
int value = 0;
int radix;
int sign = 1;
if(*str == '-'){
sign = -1;
str++;
}
//如果是16进制的情况
if(*str == '0' && (*(str+1) == 'x' || *(str+1) == 'X' )){
radix = 16;
str+=2;
}
else if(*str == '0'){
radix = 8;
str++;
}
else{
radix = 10;
}
while(*str){
//16进制的情况下 要要考虑10-15
if(radix == 16){
if(*str >='0' && *str <= '9'){
value = value * radix + *str - '0';
}
else {
value = value * radix + *str - 'a' + 10;
}
}
//8进制和10进制
else
value = value * radix + *str - '0';
str++;
}
return sign * value;
}
int main(){
cout << atoii("123")<<endl;
cout << atoii("0x12") << endl;
cout << atoii("012") << endl;
return 0;
}
/*
123
18
10
*/其他
进制转换
给定一个整数，编写一个算法将这个数转换为十六进制数。对于负整数，我们通常使用 补码运算 方法。
了解知识：位运算
#include<iostream>
using namespace std;
int main(){
int a = 1;
a = a >> 1; // 右移1位
cout << "a=" << a << endl;
int b = 2;
b = b << 1; //左移1位
cout << "b=" << b << endl;
int c = -2; //负数进行补码运算
int d = 0xf; //15 16进制
cout << "d = " << d << endl;
c = c & d; //14= (-2+16) & 0xf
cout << "c=" << c << endl;
return 0;
}class Solution {
public:
string toHex(int num) {
if(num == 0){
return "0";
}
string res = "";
for(int i = 7;i>=0;i--){
int tmp = (num>>(4*i))&0xf;
if(res.length()>0 || tmp!=0 ){
char ans = tmp<10 ? tmp +'0' : tmp - 10 + 'a';
res.push_back(ans);
}
}
return res;
}
};
百度面试：
合并两个有序数组
#include<iostream>
#include<cstring>
using namespace std;
void merge(int A[],int m,int B[],int n){
cout << "m = " << m << ",n = " << n << endl;
int res[m + n];
int i = 0;
int j = 0;
int k = 0;
while(i<m || j<n){
if(i== m){
res[k++] = B[j++];
}
else if(j == n){
res[k++] = A[i++];
}
else{
res[k++] = A[i] <= B[j] ? A[i++] : B[j++];
}
}
cout << sizeof(res)/sizeof(res[0]) << endl;
// for (int i = 0; i < m + n; i++)
// {
// A[i] = res[i];
// }
memcpy(A, res, sizeof(res));
return;
}
int main(){
int A[] = {1, 3, 4};
int m = sizeof(A)/sizeof(A[0]);
int B[] = {4, 5, 6};
int n = sizeof(B)/sizeof(B[0]);
merge(A, m, B, n);
for (int i = 0; i < m + n; i++)
{
cout << A[i] << ",";
}
cout << endl;
return 0;
}结果
m = 3,n = 3
6
1,3,4,4,5,6,左值引用和右值引用
左值引用，传入参数为引用，浅拷贝，效率高。
右值引用可以完美转发。调用移动构造函数，避免了拷贝，提高了程序效率。
TCP四次挥手
LRU算法简述。
常见的缓存算法：
LRU(Least recently used)最近最少使用，如果数据最近被访问过，那么将来被访问的几率也很高。
LFU(Least frequently used)最不经常使用，如果一个数据在最近一段时间内使用次数最少，那么在将来一段时间内使用的可能性很小。
FIFO(First in first out)先进先出，如果一个数据最先进入缓存中，则应该最早淘汰掉。
LRU缓存：
像浏览器的缓存策略、memcached的缓存策略都是使用LRU这个算法，LRU算法会将近期最不会访问的数据淘汰掉。LRU如此流行的原因是实现比较简单，而且对于实际问题也很实用，良好的运行时性能，命中率较高。下面谈谈如何实现LRU缓存：
- 新数据插入到链表头部
- 每当缓存命中（即缓存数据被访问），则将数据移到链表头部。
- 当链表满的时候，将链表尾部的数据丢弃。
LRU Cache具备的操作：
- set(key,value)：如果key在hashmap中存在，则先重置对应的value值，然后获取对应的节点cur，将cur节点从链表删除，并移动到链表的头部；若果key在hashmap不存在，则新建一个节点，并将节点放到链表的头部。当Cache存满的时候，将链表最后一个节点删除即可。
- get(key)：如果key在hashmap中存在，则把对应的节点放到链表头部，并返回对应的value值；如果不存在，则返回-1。
LRU采用双向链表和MAP实现。这里采用双向链表的原因是：如果采用普通的单链表，则删除节点的时候需要从表头开始遍历查找，效率为O(n)，采用双向链表可以直接改变节点的前驱的指针指向进行删除达到O(1)的效率。使用Map来保存节点的key、value值便于能在O(logN)的时间查找元素,对应get操作。
#include<iostream>
#include<map>
using namespace std;
struct CacheNode{
int key;
int value;
CacheNode *pre, *next;
CacheNode(int k,int v):key(k),value(v),pre(NULL),next(NULL){}
};
class LRUCache{
private:
int size;
CacheNode *head, *tail;
map<int, CacheNode *> mp;
public:
LRUCache(int capacity){
size = capacity;
head = NULL;
tail = NULL;
}
int get(int key){
map<int, CacheNode *>::iterator it = mp.find(key);
if(it != mp.end()){
CacheNode *node = it->second;
remove(node);
setHead(node);
return node->value;
}
else{
return -1;
}
}
void set(int key,int value){
map<int, CacheNode *>::iterator it = mp.find(key);
if(it != mp.end()){
CacheNode *node = it->second;
remove(node);
setHead(node);
}
else{
CacheNode *newnode = new CacheNode(key, value);
if(mp.size()>=size){
map<int, CacheNode *>::iterator iter = mp.find(tail->key);
remove(tail);
mp.erase(iter);
}
setHead(newnode);
mp[key] = newnode;
}
}
void remove(CacheNode *node){
if(node->pre != NULL){
node -> pre->next = node->next;
}
else{
head = node->next;
}
//更新删除结点的下一个结点的前驱结点
if(node -> next !=NULL){
node->next->pre = node->pre;
}
else{
//如果删除的是最后一个结点，则尾结点指向删除结点 的前一个结点
tail = node->pre;
}
}
void setHead(CacheNode *node){
node->next = head;
node->pre = NULL;
if(head != NULL){
head->pre = node;
}
head = node;
if(tail == NULL){
tail = head;
}
}
};
int main(){
//设置缓存大小
LRUCache *lrucache = new LRUCache(2);
lrucache->set(2, 1);
lrucache->set(1, 1);
cout << lrucache->get(2) << endl;
lrucache->set(4, 1);
cout << lrucache->get(1) << endl;
cout << lrucache->get(2) << endl;
return 0;
}
