面试经典代码题

本文旨在整理面试过程中经典的考题

一、字符串操作

1 字符串转数字(atoi/stoi)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int StrToInt(string str) {
int len = str.length();
if (len == 0) return 0;
int i = 0;
while (i < len && str[i] == ' ') ++i; // 排除开头的空格
if (i == len) return 0;

if (!isdigit(str[i]) && str[i] != '+' && str[i] != '-') return 0; //判断第一个符号
bool neg = str[i]=='-' ? true : false;
i = isdigit(str[i]) ? i : i+1;
long long ans = 0L;

while (i < len && isdigit(str[i])) {
ans = ans * 10 + (str[i++]-'0');
if (!neg && ans > INT_MAX) {
ans = INT_MAX;
break;
}
if (neg && ans > 1L + INT_MAX) {
ans = 1L + INT_MAX;
break;
}
}
if (i != len) return 0; // 不要此处,就是atoi()库函数的实现
return !neg ? static_cast<int>(ans) : static_cast<int>(-ans);
}

2 编程实现strcpy函数

1
2
3
4
5
6
7
8
9
#include <stdio.h>

char* strcpy(char* dest_str,const char src_str){
if(dest_str==NULL||src_str==NULL)
return NULL;
char* strdestCopy = dest_str;
while((*dest_str++=*src_str++)!='\0');
return strdestCopy;
}

二、排序

2. 求第k大的数的方法及各自的复杂度

1 首先使用快速排序算法将数组按照从大到小排序,然后取第k个,其时间复杂度最快为O(nlogn)

2 使用堆排序,建立最大堆,然后调整堆,知道获得第k个元素,其时间复杂度为O(n+klogn)

3 首先利用哈希表统计数组中个元素出现的次数,然后利用计数排序的思想,线性从大到小扫描过程中,前面有k-1个数则为第k大的数

利用快排思想,从数组中随机选择一个数i,然后将数组分成两部分$D_l$,$D_r$,$D_l$的元素都小于i,Dr的元素都大于i。然后统计Dr元素个数,如果Dr元素个数等于k-1,那么第k大的数即为k,如果Dr元素个数小于k,那么继续求Dl中第k-Dr大的元素;如果Dr元素个数大于k,那么继续求Dr中第k大的元素。

另外追问一下,当有相同元素时,还可以使用什么不同的方法求第k大的元素

当有相同元素的时候,首先利用哈希表统计数组中个元素出现的次数,然后利用计数排序的思想,线性从大到小扫描过程中,前面有k-1个数则为第k大的数,平均情况下时间复杂度为O(n)

3. Top K问题:海量数据

1. 直接全部排序(只适用于内存够的情况)

当数据量较小的情况下,内存中可以容纳所有数据。则最简单也是最容易想到的方法是将数据全部排序,然后取排序后的数据中的前K个。

这种方法对数据量比较敏感,当数据量较大的情况下,内存不能完全容纳全部数据,这种方法便不适应了。即使内存能够满足要求,该方法将全部数据都排序了,而题目只要求找出top K个数据,所以该方法并不十分高效,不建议使用。

2. 快速排序的变形 (只使用于内存够的情况)

这是一个基于快速排序的变形,因为第一种方法中说到将所有元素都排序并不十分高效,只需要找出前K个最大的就行。

这种方法类似于快速排序,首先选择一个划分元,将比这个划分元大的元素放到它的前面,比划分元小的元素放到它的后面,此时完成了一趟排序。如果此时这个划分元的序号index刚好等于K,那么这个划分元以及它左边的数,刚好就是前K个最大的元素;如果index > K,那么前K大的数据在index的左边,那么就继续递归的从index-1个数中进行一趟排序;如果index < K,那么再从划分元的右边继续进行排序,直到找到序号index刚好等于K为止。再将前K个数进行排序后,返回Top K个元素。这种方法就避免了对除了Top K个元素以外的数据进行排序所带来的不必要的开销。

3. 最小堆法

这是一种局部淘汰法。先读取前K个数,建立一个最小堆。然后将剩余的所有数字依次与最小堆的堆顶进行比较,如果小于或等于堆顶数据,则继续比较下一个;否则,删除堆顶元素,并将新数据插入堆中,重新调整最小堆。当遍历完全部数据后,最小堆中的数据即为最大的K个数。

4. 分治法

将全部数据分成N份,前提是每份的数据都可以读到内存中进行处理,找到每份数据中最大的K个数。此时剩下NK个数据,如果内存不能容纳NK个数据,则再继续分治处理,分成M份,找出每份数据中最大的K个数,如果M*K个数仍然不能读到内存中,则继续分治处理。直到剩余的数可以读入内存中,那么可以对这些数使用快速排序的变形或者归并排序进行处理。

5. Hash法

如果这些数据中有很多重复的数据,可以先通过hash法,把重复的数去掉。这样如果重复率很高的话,会减少很大的内存用量,从而缩小运算空间。处理后的数据如果能够读入内存,则可以直接排序;否则可以使用分治法或者最小堆法来处理数据。

详细代码:

  1. 利用快速排序的思想进行查找
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Finder {
public:
int findKth(vector<int> a, int n, int K) {
// write code here
return quickfind(a,0,n-1,K);
}
int quickfind(vector<int> &a,int low,int high,int K){
int pivot = partition(a,low,high);
if(pivot+1<K) //中轴位置少于K个,在右子数组中继续查找
return quickfind(a,pivot+1,high,K);
else if(pivot+1>K) //中轴位置大于K个,在左子数组中继续查找
return quickfind( a, low, pivot-1,K);
return a[pivot];
}
int partition(vector<int> &a,int low, int high){
int val = a[low];
while(low<high){
while(low<high&&a[high]<=val) high--; // 从右往左扫描,直到遇到比基准元素大的元素
a[low] = a[high];
while(low<high&&a[low]>=val) low++; //从左往右扫描,直到遇到比基准元素小的元素
a[high] = a[low];
}
a[low] = val;
return low;
}
};

三、链表

1. LRU缓存机制

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class LRUCache {
int capacity;
list<pair<int,int>> ls;
unordered_map<int,list<pair<int,int>>::iterator> key_add; //获取数据需要用哈希表 // 见与链表中的地址

public:
LRUCache(int capacity) {
this->capacity = capacity;
}

int get(int key) {
//如果要访问的节点不存在
if(key_add.find(key)==key_add.end())
return -1;
// 把访问的节点移动到最前边的一个;
pair<int,int> kv = *key_add[key];
ls.erase(key_add[key]);
ls.push_front(kv);
key_add[key] = ls.begin();
return kv.second;
}

void put(int key, int value) {
if(key_add.find(key)==key_add.end()){
ls.push_front({key,value});
key_add[key] = ls.begin();

if(ls.size()>capacity){
int lastkey = ls.back().first;
key_add.erase(lastkey);
ls.pop_back();
}
}
else{
ls.erase(key_add[key]);
ls.push_front({key,value});
key_add[key] = ls.begin();
}
}
};

2. 合并n个有序数组

假设你得到了k个排好序的数组,每个都有n个元素,希望将它们整体组合成一个有着kn个元素的有序数组。考虑以下方法:将k个数组分为k/2对,并使用归并排序来合并每对,则你有了k/2个排序好的数组;重复此方法,直到合并结束。那么程序运行的时间复杂度是O(nklog⁡n)

3. 链表翻转

利用哨兵

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Void reversal_list(node * head)
{
node* pre_node = nullptr;
node* cur_node = head->next;
node* next_node = cur_node->next;
if(cur_node == nullptr) return ;
while(1)
{
cur_node->next = forward_node;
pre_node = cur_node;
cur_node = next_node;
if(cur_node == nullptr)
break;
next_node = cur_node->next;
}
head->next = pre_node;
}

双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* cur = NULL, *pre = head;
while (pre != NULL) {
ListNode* t = pre->next;
pre->next = cur;
cur = pre;
pre = t;
}
return cur;
}
};

简单的递归

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if (head == NULL || head->next == NULL) {
return head;
}
ListNode* ret = reverseList(head->next);
head->next->next = head;
head->next = NULL;
return ret;
}
};

妖魔化的双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if (head == NULL) { return NULL; }
ListNode* cur = head;
while (head->next != NULL) {
ListNode* t = head->next->next;
head->next->next = cur;
cur = head->next;
head->next = t;
}
return cur;
}
};

4. 表示数值的字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
bool isNumber(string s) {
int len = s.length();
int i = 0;
while(i<len&&s[i]==' ') i++; //忽略空格
bool flag = GetSignedIntBaseNumber(s,len,i);
if(i<len&&s[i]=='.'){
i++;
flag = GetUnSignedIntBaseNumber(s,len,i)||flag;
}
if(i<len&&i!=0 && (s[i]=='e'||s[i]=='E')){
i++;
flag=flag&&GetSignedIntBaseNumber(s,len,i);
}
while(i<len&&s[i]==' ') i++; //忽略空格
return i>=len&&flag;
}

bool GetSignedIntBaseNumber(string &str,int len,int &i){
if(str[i]=='+'||str[i]=='-')
i++;
return GetUnSignedIntBaseNumber(str,len,i);
}
bool GetUnSignedIntBaseNumber(string &str,int len,int &i){
int tmp = i;
while(i<len&&isdigit(str[i]))
i++;
return i>tmp;
}
};

5. 删除链表的重复元素

82. 删除排序链表中的重复元素 II

给定一个排序链表,删除所有含有重复数字的节点,只保留原始链表中 没有重复出现 的数字。

示例 1:

1
2
输入: 1->2->3->3->4->4->5
输出: 1->2->5

示例 2:

1
2
输入: 1->1->1->2->3
输出: 2->3

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if(!head || !head->next) return head;
ListNode *root = new ListNode(INT_MAX);
root -> next = head;
ListNode *pre = root;
while(pre&&pre->next){
ListNode *pcur = pre->next;
if(pcur->next==nullptr||pcur->next&&pcur->val!=pcur->next->val)
pre = pcur;
else{
while(pcur->next&&pcur->next->val==pcur->val)
pcur = pcur->next;
pre->next = pcur->next;
}
}
return root -> next;
}
};

四、回溯

1. N皇后问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
unordered_set<int> columns;
unordered_set<int> diagonals1;
unordered_set<int> diagonals2;
vector<vector<string>> solutions;

public:
vector<vector<string>> solveNQueens(int n) {
auto queens = vector<int>(n, -1);
backtrack(queens, n, 0);
return solutions;
}

void backtrack(vector<int> &queens, int n, int row) {
if (row == n) {
vector<string> board = generateBoard(queens, n);
solutions.push_back(board);
} else {
for (int i = 0; i < n; i++) {
if (columns.find(i) != columns.end()) {
continue;
}
int diagonal1 = row - i;
if (diagonals1.find(diagonal1) != diagonals1.end()) {
continue;
}
int diagonal2 = row + i;
if (diagonals2.find(diagonal2) != diagonals2.end()) {
continue;
}
queens[row] = i;
columns.insert(i);
diagonals1.insert(diagonal1);
diagonals2.insert(diagonal2);
backtrack(queens, n, row + 1);
queens[row] = -1;
columns.erase(i);
diagonals1.erase(diagonal1);
diagonals2.erase(diagonal2);
}
}
}

vector<string> generateBoard(vector<int> &queens, int n) {
auto board = vector<string>();
for (int i = 0; i < n; i++) {
string row = string(n, '.');
row[queens[i]] = 'Q';
board.push_back(row);
}
return board;
}
};

五、数字游戏

1 求平方和

1
2
3
4
5
6
7
8
9
10
11
12
int sqrt(int x) {
// write code here
int sum = 0;
for(int i = 0;i<=x;i++){
int odd = 2*i+1;
sum+=odd;
if(sum>x){
return i;
}
}
return 0;
}

2 判断一个数是不是二的倍数

1
a % 2 == 0 或者a & 0x0001 == 0

3 不用+加减乘除做加法

1
2
3
4
5
6
7
8
9
10
11
int Add(int num1, int num2)
{
int sum,carry;
do{
sum = num1^num2;
carry = (num1&num2)<<1;
num1 = sum;
num2 = carry;
}while(num2!=0);
return num1;
}

高楼扔鸡蛋

887. 鸡蛋掉落

你将获得 K 个鸡蛋,并可以使用一栋从 1N 共有 N 层楼的建筑。

每个蛋的功能都是一样的,如果一个蛋碎了,你就不能再把它掉下去。

你知道存在楼层 F ,满足 0 <= F <= N 任何从高于 F 的楼层落下的鸡蛋都会碎,从 F 楼层或比它低的楼层落下的鸡蛋都不会破。

每次移动,你可以取一个鸡蛋(如果你有完整的鸡蛋)并把它从任一楼层 X 扔下(满足 1 <= X <= N)。

你的目标是确切地知道 F 的值是多少。

无论 F 的初始值如何,你确定 F 的值的最小移动次数是多少?

六、计算几何

1. 给定三角形ABC和一点P(x,y,z),判断点P是否在ABC内

根据面积法,如果P在三角形ABC内,那么三角形ABP的面积+三角形BCP的面积+三角形ACP的面积应该等于三角形ABC的面积。算法如下:

计算三角形面积

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <math.h>
using namespace std;
#define ABS_FLOAT_0 0.0001
struct point_float
{
float x;
float y;
};
float GetTriangleSquar(const point_float pt0, const point_float pt1, const point_float pt2)
{
point_float AB, BC;
AB.x = pt1.x - pt0.x;
AB.y = pt1.y - pt0.y;
BC.x = pt2.x - pt1.x;
BC.y = pt2.y - pt1.y;
return fabs((AB.x * BC.y - AB.y * BC.x)) / 2.0f;
}
bool IsInTriangle(const point_float A, const point_float B, const point_float C, const point_float D)
{
float SABC, SADB, SBDC, SADC;
SABC = GetTriangleSquar(A, B, C);
SADB = GetTriangleSquar(A, D, B);
SBDC = GetTriangleSquar(B, D, C);
SADC = GetTriangleSquar(A, D, C);
float SumSuqar = SADB + SBDC + SADC;
return ((-ABS_FLOAT_0 < (SABC - SumSuqar)) && ((SABC - SumSuqar) < ABS_FLOAT_0));
}

七、动态规划

474. 一和零

给你一个二进制字符串数组 strs 和两个整数 mn

请你找出并返回 strs 的最大子集的大小,该子集中 最多m0n1

如果 x 的所有元素也是 y 的元素,集合 x 是集合 y子集

示例 1:

1
2
3
4
输入:strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
输出:4
解释:最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ,因此答案是 4 。
其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意,因为它含 4 个 1 ,大于 n 的值 3 。

示例 2:

1
2
3
输入:strs = ["10", "0", "1"], m = 1, n = 1
输出:2
解释:最大的子集是 {"0", "1"} ,所以答案是 2 。

提示:

  • 1 <= strs.length <= 600
  • 1 <= strs[i].length <= 100
  • strs[i] 仅由 '0''1' 组成
  • 1 <= m, n <= 100

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
int findMaxForm(vector<string>& strs, int m, int n) {
vector<vector<int>> dp(m+1,vector<int>(n+1,0));
for(auto str:strs)
{
int zero = 0;
int one = 0;
for(int i = 0;i<str.length();i++)
{
zero += str[i]=='0'?1:0;
one += str[i]=='1'?1:0;
}
for(int i = m;i>=zero;i--)
for(int j = n;j>=one;j--)
{
dp[i][j] = max(dp[i-zero][j-one]+1,dp[i][j]);
}
}
return dp[m][n];
}
};
打赏
  • 版权声明: 本博客所有文章除特别声明外,均采用 Apache License 2.0 许可协议。转载请注明出处!
  • © 2019-2022 guoben
  • PV: UV:

微信