面试过程中的算法题目总结。
Consecutive Numbers Sum
Tips：如果是连续数，那么是可以使用等差数列求和的。并且这个求解的是符合条件的解的个数。时间复杂度是O ($\sqrt{n}$) 。对于一个正整数N，如果能写成K个连续正整数相加的形式，则有，
$$
\begin{split}
N &= ( x + 1 ) + ( x + 2 ) + \dots + ( x + K ) \\
N &= K \times x + \frac { ( 1 + K ) \times K } { 2 } \\
\end{split}
$$
所以， N 能够被 K个连续正整数相加的条件是， $\left( N - \frac { K * ( K + 1 ) } { 2 } \right)$ 能够被 K 整除。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
class Solution(object):
def consecutiveNumbersSum(self, N):
"""
:type N: int
:rtype: int
"""
res =0
n =0
while n*(n+1) <= 2*N:
top =N -(n *n +n)/2
if top <=0:
break
elif top %(n +1) ==0:
res +=1
n +=1
return res
|
C ++的代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class Solution {
public:
// 数学就是要求 excactly 这样的准确
// 如果最后多了，那么限制条件一定是不够严格；反之也是成立的
int consecutiveNumbersSum(int N) {
// 这个i 表示连续数字的长度
int i =0;
int counts =0;
while(i*(i +1) <= 2*N)
{
// 边界条件必要难把握
int top = N - (1+i) *i/2;
if(top <=0) break;
if(top % (i +1) ==0) counts ++;
i ++;
}
return counts;
}
};
|
如何近似的求解 pi
Tips: 随机抽样，注意是均匀分布而不是正太分布，对应python 中的实现是 randrange() 而不是 random() 函数。注意有精度的问题
1
2
3
4
5
6
7
8
9
10
11
|
from random import randrange
total = 100000
res =0
i =0
while i< total:
x = randrange(0, total+1)/100000.0
y = randrange(0, total+1)/ 100000.0
if(x*x + y*y <= 1): res +=1;
i += 1
print( res*1.0/ total*4)
|
在一个圆内随机采样得到结果的概率？ 4/pai
求解的过程？
方法一： 使用 range(0，1) 平均函数
方法二： 使用 range(0, 1) 随机得到r， 使用 sigta 得到[0, 2pai]，然后两者相乘。但是对于 r 是需要 进行 根号r 处理。否则的话，最后的结果是不均匀的
对于第二种方式，使用极坐标表示的方式不会
1
2
3
4
5
6
7
8
9
10
11
|
import math
from random import randrange
n = 1000000
r = randrange(0,n+1)/n
thetha = r * 2*math.pi
area =thetha * r* 4
print(r)
print(thetha)
print(area)
|
中文转换成阿拉伯数字
中文转成阿拉伯数字（含有点）
如果有“点”，那么就截断处理，分成小数点之前和之后。
二进制数中的1
在二进制中，经常使用到的就是 & 和 >> 两个操作。 >> 移位操作只是针对整数，对于浮点数和 unsigned int 这个是不能用的，在后面两种类型中，需要使用到 ·/=· 这样的操作，该操作是通用的。时间复杂度是 $log(n)$。
1
2
3
4
5
6
7
8
9
10
11
12
13
|
class Solution {
public:
int hammingWeight(uint32_t n) {
int cout =0;
while(n)
{
if(n &1 ==1)
cout ++;
n /=2;
}
return cout;
}
};
|
如果1出现的次数比较少， 时间复杂度变成了$O(k)$， K 表示字符串中 1 的个数， 所以 n &(n-1) 是一个很好的操作。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
int count3(Byte v){
int count =0;
while (v) {
v &= (v-1);// 使得最大位的1变成0 ，在二进制的角度上
count +=1 ;
}
}
// 使用空间代替时间, 这个是可以进行穷举的
int count4(Byte v){
int countTable [256] ={0, 1,1,2...8}
int count =countTable[v];
return count;
}
|
给定一个数字N N的阶乘有多少个0?
Tips: 数学问题，N 是可以通过质因数(2, 3, 5)进行分析 $N =(2^x +3^y+ 5^z) $， 然后0的个数是 $min(x, z) -> z $, 最后就相当于每个数字的5的个数。到最后是在统计 5 的个数，数字N 分解因式之后 5 的个数。 时间复杂度是$O(log_5N)$ 还是log 的时间复杂度
1
2
3
4
5
6
7
8
9
10
11
12
|
int count(Byte， v){
int count;
for(int i =0; i<=v; i++)
{
while (i) {
count +=1;
i /=5;
}
}
return count;
}
|
1
2
3
4
5
6
7
8
9
|
int count(Byte, v){
int count =0;
while (v >4) {
count += v/5;
v =v /5;
}
return count;
}
|
求解 N! 中的二级制表示中最低位1的位置
在二进制中，经常使用到的就是 & 和 >> 两个操作。 >> 移位操作只是针对整数，对于浮点数和 unsigned int 这个是不能用的，在后面两种类型中，需要使用到 ·/=· 这样的操作，该操作是通用的。
还是从二进制的角度出发。
1
2
3
4
5
6
7
8
9
10
11
12
13
|
class Solution {
public:
int hammingWeight(uint32_t n) {
int cout =0;
while(n)
{
if(n &1 ==1)
cout ++;
n /=2;
}
return cout +1;
}
};
|
寻找每个 ID，该ID 出现的频率是大于 0.5, 出现的次数大于总数的一半
Tips: 如果每次删除两个不同的ID，那么 最多的ID 出现的次数还是大于总数的一般，不断的重复这个过程。时间复杂度是O(n)，想法是上面那种，但是在操作的时候，并不是删除了某个ID。看代码是一清二楚的。
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
|
Type Find(Type *ID, int N)
{
Type candidate;
int nTimes =0, i;
for(i =0; i< N; i++){
if (nTimes ==0)
{
candidate =ID[i];
nTimes =1
}
else
{
if(ID[i] ==candidate){
nTimes +=1;
}
else{
nTimes -=1;
}
}
}
// 这个应该还是需要最后判断一下 candidate 是不是出现了 [2/N] 次数，因为有一种情况是不存在的
}
|
尾递归
尾调用定义: 在某个函数的最后一步调用另一个函数.进入下一个递归之后，该层次的递归已经结束，不需要使用栈空间进行保留信息。
1
2
3
4
5
6
|
function f(x) {
if (x > 0) {
return m(x)
}
return n(x);
}
|
上面代码中，函数m和n都属于尾调用，因为它们都是函数f的最后一步操作。不一定是最后一行。
同理是可以推广到尾递归。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
function f() {
let m = 1;
let n = 2;
return g(m + n);
}
f();
// 等同于
function f() {
return g(3);
}
f();
// 等同于
g(3);
|
尾递归的意义在于防止栈溢出。因为递归的调用是非常消耗内存的，需要再栈中保存N 个调调用记录，很容易发生栈溢出 (stack overflow) 。但是对于为递归来说，只有一个调用记录，因为上一个已经结束，所以是不会发生 “栈溢出”错误的。
Fibonacci 数列
最原始的解法，递归，其中有很多重复的计算子单元。
程序的开始就像百度的面试官那样说的，都是应该考虑一下特殊情况，有可能考虑不全，但是一定要有这个意识。到了递归中，不再是特殊情况这种事情，而是跳出条件。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
int Fibonacci(int n)
{
if (n <0)
{
return 0;
}
else if(n ==1)
{
return 1;
}
else
{
return Fibonacci(n -1) + Fibonacci(n -2);
}
}
|
解法二： 时空都是 O(N)，重点是从递归转成了循环。
1
2
3
4
5
6
7
8
9
10
11
|
def Fibonacci(n ):
if n ==0:
return 0
elif n ==1:
return 1
arr =[0] *(n+1)
arr[0] =0
arr[1] =1
for i in range(2, n+1):
arr[i] =arr[i-1] +arr[i-2]
return arr[-1]
|
在上面的基础上进行优化，空间复杂度变成 O(1)
a, b =b, a+b # 在python，连续赋值是从左往右的。也就是说， 先保存 b, 和 a+b，然后执行 a =b, b = a+b
所以在python 中交换两个数字可以写成这样： a, b = b, a (python 中是从左往右进行赋值的)
时间复杂度是$O(n)$, 空间复杂度 $O(1)$, 因为空间上只是依赖前两个，并不需要保存整个数组。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
class Solution(object):
def fib(self, N):
"""
:type N: int
:rtype: int
"""
if N <=0:
return 0
elif N ==1:
return 1
a, b =0, 1
for i in range(N ):
a, b =b, a+b # 在python，连续赋值是从左往右的。
return a
|
寻找数组中的最大值和最小值
时间复杂度是 O(N)，使用了两个值进行min_n 和max_n 的判断。 如果数组本身没有什么有序性的话 ，那么时间复杂度就是 $O(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
|
#include<iostream>
using namespace std;
#define INF 10^9
void FindMinMax(int a[], int size, int &min, int &max)
{
max =-INF;
min =INF;
for (int i =0; i<size -1; i++)
{
// 这种判断方式 还是值得学习的，细节就是 index 的边界
if (a[i] < a[i+1])
{
if(a[i+1]> max ) max =a[i+1];
if(a[i] < min) min =a[i];
}
else
{
if(a[i] > max) max =a[i] ;
if(a[i+1] < min) min =a[i+1];
}
}
}
int main()
{
int arr[10];
int length =sizeof(arr)/ sizeof(arr[0]);
int min, max;
FindMinMax(arr, length, min, max);
}
|
寻找最近点对
在二维平面上的n个点中，找出最接近的一对点
第一次碰到这个题目的时候，还在想图的结构，现在看来只要是有array 的存在，那么这个是一定按照 array 的情况进行遍历求解。
解法一： 暴力法，时间复杂度是$O(n^2)$
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
|
#include<iostream>
#include<cmath>
using namespace std;
const int N =101;
struct Point{
float x, y;
}point[N];
// 因为是枚举的，所以还是得存储一下原来输入
int n;
double cal_dis(Point & a, Point & b)
{
return sqrt((a.x-b.x) *(a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
int main()
{
cin >>n;
int i =0;
while(i <n)
{
int x, y;
cin >>x >>y;
point[i].x =x;
point[i].y =y;
}
double min_v= cal_dis(point[0],point[1]), tmp;
int ind1, ind2;
// 枚举的思想就是，就是两两进行比较
for(int i =0; i<n; i++)
{
for(int j =i+1; j<n; j++)
{
tmp =cal_dis(point[i], point[j]);
if(tmp < min_v)
{
min_v =tmp;
ind1 =i;
ind2 =j;
}
}
}
cout << min_v<< endl;
return 0;
}
|
解法二：分治法
参考这里, 最后的时间复杂度可以降低到 $O(nlogn)$，没有看懂。
使用分治法（divide and conquer）解题步骤：
- divide 将要解决的问题分成若干小规模的同类问题
- conquer- 当子问题划分的足够小，能够使用较简单的方式解决
- combine 将子问题的解逐层合并构成原问题的解
采用分而治之的思想，分成左右两个子集，$S_l$ 和$S_r$ ，然后分别计算两个子集之内的最小的距离，然后需要计算两个子集边界附近的点的距离。从算法步骤上讲，先存储点 point 这样的一个结构体，然后按照point 中的x 进行排序。
$\delta$ 是从左右两个子集中取得的点与点之间的最小距离，那么意味着两点之间的距离 最小是 $\delta $，所以在正方形 ($2\delta$, $2\delta$ ) 的区间内，左半部分的点到右半部分的点的距离最少是 $\delta$，根据割舍原理，那么最多只需要比较6个点。这里的是每个点，只需要个其他的6个点进行比较，而不是总共只有6个点。
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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
|
#include <ctime>
#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;
#define INFINITE_DISTANCE 65535 // 无限大距离
#define COORDINATE_RANGE 100.0 // 横纵坐标范围为[-100,100]
#ifndef Closest_pair
typedef struct Point
{// 二维坐标上的点Point
double x;
double y;
}Point;
double Distance(Point a, Point b)
{//平面上任意两点对之间的距离公式计算
return sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y));
}
bool compareX(Point a, Point b)
{//自定义排序规则：依照结构体中的x成员变量升序排序
return a.x < b.x;
}
bool compareY(Point a, Point b)
{//自定义排序规则：依照结构体中的x成员变量升序排序
return a.y < b.y;
}
float ClosestPair(Point points[], int length, Point &a, Point &b)
{// 求出最近点对记录，并将两点记录再a、b中
double distance; //记录集合points中最近两点距离
double d1, d2; //记录分割后两个子集中各自最小点对距离
int i = 0, j = 0, k = 0, x = 0; //用于控制for循环的循环变量
Point a1, b1, a2, b2; //保存分割后两个子集中最小点对
if (length < 2)
return INFINITE_DISTANCE; //若子集长度小于2，定义为最大距离，表示不可达
else if (length == 2)
{//若子集长度等于2，直接返回该两点的距离
a = points[0];
b = points[1];
distance = Distance(points[0], points[1]);
}
else
{//子集长度大于3，进行分治求解
Point *pts1 = new Point[length]; //开辟两个子集
Point *pts2 = new Point[length];
sort(points, points + length, compareX); //调用algorithm库中的sort函数对points进行排序，compareX为自定义的排序规则
double mid = points[(length - 1) / 2].x; //排完序后的中间下标值，即中位数
for (i = 0; i < length / 2; i++)
pts1[i] = points[i];
for (int j = 0, i = length / 2; i < length; i++)
pts2[j++] = points[i];
d1 = ClosestPair(pts1, length / 2, a1, b1); //分治求解左半部分子集的最近点
d2 = ClosestPair(pts2, length - length / 2, a2, b2); //分治求解右半部分子集的最近点
if (d1 < d2) { distance = d1; a = a1; b = b1; } //记录最近点，最近距离
else { distance = d2; a = a2; b = b2; }
//merge - 进行子集合解合并
//求解跨分割线并在δ×2δ区间内的最近点对
Point *pts3 = new Point[length];
for (i = 0, k = 0; i < length; i++) //取得中线2δ宽度的所有点对共k个
if (abs(points[i].x - mid) <= distance)
pts3[k++] = points[i];
sort(pts3, pts3 + k, compareY); // 以y排序矩形阵内的点集合
for (i = 0; i < k; i++)
{
if (pts3[j].x - mid >= 0) // 只判断左侧部分的点
continue;
x = 0;
for (j = i + 1; j <= i + 6 + x && j < k; j++) //只需与有序的领接的的6个点进行比较
{
if (pts3[j].x - mid < 0)
{// 假如i点是位于mid左边则只需判断在mid右边的j点即可
x++;
continue;
}
if (Distance(pts3[i], pts3[j]) < distance)
{//如果跨分割线的两点距离小于已知最小距离，则记录该距离和两点
distance = Distance(pts3[i], pts3[j]);
a = pts3[i];
b = pts3[j];
}
}
}
}
return distance;
}
void SetPoints(Point *points, int length)
{//随机函数对点数组points中的二维点进行初始化
srand(unsigned(time(NULL)));
for (int i = 0; i < length; i++)
{
points[i].x = (rand() % int(COORDINATE_RANGE * 200)) / COORDINATE_RANGE - COORDINATE_RANGE;
points[i].y = (rand() % int(COORDINATE_RANGE * 200)) / COORDINATE_RANGE - COORDINATE_RANGE;
}
}
int main()
{
int num; //随机生成的点对个数
Point a, b; //最近点对
double diatance; //点对距离
cout << "请输入二维点对个数:";
cin >> num;
if (num < 2)
cout << "请输入大于等于2的点个数！！" << endl;
else
{
cout << endl << "随机生成的" << num << "个二维点对如下：" << endl;
Point *points = new Point[num];
SetPoints(points, num);
for (int i = 0; i < num; i++)
cout << "(" << points[i].x << "," << points[i].y << ")" << endl;
diatance = ClosestPair(points, num, a, b);
cout << endl << endl << "按横坐标排序后的点对:" << endl;
for (int i = 0; i < num; i++)
cout << "(" << points[i].x << "," << points[i].y << ")" << endl;
cout << endl << "最近点对为：" << "(" << a.x << "," << a.y << ")和" << "(" << b.x << "," << b.y << ")" << endl << "最近点对距离为：" << diatance << endl;
}
system("pause");
}
#endif // !Closest_pair
|
对比一下一维的情况。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
double MinDifference(double arr[], int n)
{
if (n <2) return 0;
sort(arr, arr+n);
// sort(arr, arr+n myfunction) 降序
double minDiff =arr[1] - arr[0];
for (int i =2; i<n;i++)
{
double tmp =arr[i] -arr[i-1];
if (tmp <minDiff)
{
minDiff =tmp;
}
}
return minDiff;
}
|
快速寻找满足条件的两个数
第一种解法： 排序之后 然后二分查找 O(nlogn) +O(logn) -> O(nlogn)
在有序的数组中，必然使用二分进行查找，这样查找的效率从O(n) -> O(log 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
|
#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 1001
int arr[MAXN];
bool findSum(int arr[], int n, int sum)
{
int i =0; int j =n-1;
while (i<j)
{
int tmp =arr[i] +arr[j];
if (tmp ==sum)
{
printf("(%d, %d)", arr[i], arr[j]);
return true;
}
else if(tmp <sum) i ++;
else j --;
}
return false;
}
int main()
{
int n, sum, i,j;
cin >> n >>sum;
for(i =0; i<n;i++) cin >>arr[i];
sort(arr, arr+n);
bool res =findSum(arr, n, sum);
return 0;
}
|
第二种解法：使用辅助的空间 dictionary 存储，空间复杂度O(N) + 时间复杂度 O(N)
使用python 中的 dictionary， in 这种操作是非常具有可读性的。并且这种操作的时间复杂度是O(1) ,这个是不容置疑的，这个是字典的特性。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
def twoSum(arr, total):
if not arr:
return arr
from collections import defaultdict
dic =defaultdict(int)
for num in arr:
dic[num] = dic[num] +1
for key in dic:
if total -key in dic:
return (key, total -key)
return (-1, -1)
|
子数组的最大乘积
给定一个长度为 N 的整数数组，只允许用乘法，不能用除法， 计算任意 ( N-1) 个数的组合中乘积最大的一组。
限制条件： 必须要选出 （N-1）个数字，只能使用乘法。
第一种解法：暴力求解，遍历出n 个，然后需要 n-1 次相乘，所以时间复杂度是 $O(N^2)$
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
|
#include<iostream>
using namespace std;
class Solution {
public:
int maxProduct(int *nums) {
int res;
int max;
int i, j;
int n= sizeof(nums) /sizeof(nums[0]);
for(i =0; i<n; i++)
{
for(j =0; j<n; j++) // 使用 for 循环的形式将子集相乘
{
res =1;
res *= ( (i==j) ? 1: nums[j]);
if (res ==0) break;
}
max =( i==0 ? res: max); // 实际上是对于 max 的出释怀
max =( max < res? res: max); // 这种语法是比较简洁的
}
return max;
}
}
```
上述方式进行了很多重复的运算，可以保存下来子问题，减少时间复杂度。实现的时候，两个list 分别从左右两边进行累乘运算。所以第二种解法：时间复杂度从 $O(n^2) $ 降低为 $ O(n)$ 。从做题的结果上看，如果最后求解的是一个值，那么很有可能使用 $O(1) $ 的空间复杂度得到。
```c++
class Solution {
public:
// 简单粗暴的解法，在遍历的过程中需要维护 minv 和maxv
int maxProduct(vector<int>& nums) {
if(nums.empty()) return 0;
int n =nums.size();
int minv =nums[0], maxv =nums[0], res =nums[0];
for(int i =1; i< n; i++)
{
int nv =minv, xv =maxv;
maxv =max(nums[i], max(nums[i]* nv, nums[i] * xv));
minv =min(nums[i], min(nums[i] * nv, nums[i] * xv));
res =max(res, maxv);
}
return res;
}
};
|
最长递增子序列
第一种方式，时间复杂度是 O($n^2$),
思想是dp. dp[i] 表示 到目前为止前i 个数字中的 最长递增子序列。
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
|
class Solution {
public:
// O(m^2) 的时间复杂度，dp[i] 表示前i 个数字最长的递增子序列的长度
// 递推方程是 dp[i] =max(dp[j] +1) 其中 j< i， 并且 nums[i] > nums[j]
// 初始化 dp ={1} 因为如果只有一个元素，那么dp[0] =1
int lengthOfLIS(vector<int>& nums) {
if(nums.empty()) return 0;
int n =nums.size();
vector<int>dp(n, 1);
int res =0;
for(int i =0; i< n; i++)
{
// 遍历前面的所有dp[j]
for(int j =0; j<i; j++)
{
if(nums[i] > nums[j])
{
dp[i] =max(dp[i], dp[j] +1);
}
}
res =max(res, dp[i]);
}
return res;
}
};
|
python 实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
class Solution(object):
def lengthOfLIS(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if(not nums) : return 0;
n =len(nums)
dp =[1] *n
res =0
for i in range(n):
for j in range(0, i):
if(nums[i] > nums[j]):
dp[i] =max(dp[i], dp[j] +1)
res =max(res, dp[i])
return res
|
上面的时间复杂度是O($ n^2$), 在于每次都是遍历了之前所有的情况 (dp) ，还有一种方式创建一个辅助数组，用于存储之前已经排好序的元素，遍历的时候使用二分查找进行遍历。于是第二种解法就出来了，时间复杂度是 O(n logn). 这个辅助函数不是从原来的数组不是最长增数组本身，这个函数只能用于计算最后的长度，得不到数组。
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
|
class Solution {
public:
int binary_search(vector<int> &h, int l, int r, int target)
{
while(l<r)
{
int mid = l +r >>1;
if(h[mid] < target) l =mid +1;
else r =mid;
}
return l;
}
int lengthOfLIS(vector<int>& nums) {
if(nums.empty()) return 0;
int n =nums.size();
vector<int> h(n, 0);
h[0] =nums[0];
int index =0;
for(int i =1; i<n; i++)
{
if(nums[i] > h[index]) h[++index] =nums[i];
else
{
int pos =binary_search(h, 0, index, nums[i]);
h[pos] =nums[i];
}
}
return index+1;
}
};
|
数组循环移位
暴力求解 时间复杂度是O($KN$) K表示移位的次数 N 表示数组的长度。在c++中，数组如果是一个个移位，那么时间复杂度是$O(kn)$， 但是如果是两两交换位置，那么时间复杂度是$O(n)$，所以这个是有优化的空间的。
C++ 解法
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
|
#include<iostream>
#include<vector>
using namespace std;
void rightShift(vector<int> arr, int n , int k)
{
if (arr.empty() or arr.size() ==0)
return ;
if (k>n) k =k%n;
while(k --)
{
int temp =arr[n-1];
for(int i =n-1; i>0; i--) arr[i] =arr[i-1];
arr[0] =temp;
}
}
int main()
{
return 0;
}
|
C语言解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
void rightShift(int *arr, int n, int k)
{
if (arr ==NULL or n ==0)
return ;
if (k>n) k =k%n;
while(k --)
{
int temp =arr[n-1];
for (int i =n-1; i>0; i--)
{
arr[i] =arr[i-1];
}
arr[0] =temp;
}
}
|
解法二：
原来序列 abcd1234 转换成 1234abcd ，分成两部分， 1234 和abcd 看成两个整体，右移就是把数组的两个部分交换一下
通过以下的方法进行实现， 逆序1234, 逆序abcd , 逆序整个数组, 整个arr 的 reverse
时间复杂度：这个不是递归，只是同一个函数调用了三次，时间复杂度分别是 O($ \frac{k}{2}$), O( $\frac{N-k}{2}$) 和 O($\frac{N}{2}$)，所以总的时间复杂度是 O(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
|
#include<stdio.h>
const int N =101;
int n, k;
void reverse(char *arr, int b, int e)
{
while( b<e)
{
int t =arr[e];
arr[e] =arr[b];
arr[b] =t;
b ++;
e --;
}
}
void right_shift(char *arr, int n, int k)
{
k %=n;
reverse(arr, 0, n-k -1);
reverse(arr, n-k, n -1);
reverse(arr, 0, n -1);
}
int main()
{
char arr[N];
scanf("%d %d", &n, &k);
gets(arr);
right_shift(arr, n, k);
puts(arr);
return 0;
}
|
数组分割?
题目概述：有一个没有排序，元素个数为2N的正整数数组。要求把它分割为元素个数为N的两个数组，并使两个子数组的和最接近。
这里的dp[k][s]表示从前k个数中取k个数，且k不超过n，且这些数之和为s的取法是否存在。
算法时间复杂度是 $O(N^2*sum)$
讲解可以参考这个，反正我是没有很看动画
https://blog.csdn.net/linyunzju/article/details/7729774
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
54
|
#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 101
#define MAXSUM 100000
int A[MAXN];
bool dp[MAXN][MAXSUM];
// 使用全局变量 解决定义二维的数组的问题
void find(int *a, int n, int sum)
{
int k1, k2, s;
for (k1 =1; k1<2*n; k1++)
{
for(k2 =min(k1, n) ;k2>=1; k2--)
{
for(s =1; s<=sum/2; s++)
{
if (s >=A[k1] && dp[k2-1][s-A[k1]]) dp[k2][s] =true;
}
}
}
for (s =sum/2; s>=1 && !dp[n][s] ; s--)
{
cout << sum-2*s<< endl;
}
}
int main(){
int n, i;
cin >> n;
for(i=1; i<=2*n; i++)
{
cin >> A[i];
}
int sum =0;
for (i =1; i<=2*n; i++)
{
sum += A[i];
}
memset(A, 0, sizeof(dp));
dp[0][0] =true;
find(A, n, sum);
return 0;
}
|
只考加法的面试题
写一个程序，对于一个 64位正整数，输出所有可能的连续（两个以上）自然数之和的算式
因为这里涉及到了连续自然数，那么一定要使用等差数列，然后进行枚举。在时间复杂度 O(n) 内解决问题。
数学问题
设存在连续自然数，首项为$A_1$，项数为m，即
$$
A_1 + A_2 + \ldots + A_m = { M }
$$
使用求和公式
$$A_1 \times m + \frac{m \times ( m - 1 )}{2} = M$$
可以整理得到关于 $m$ 的一元二次方程方程
$$ m^2 +2\times( A_1 -1) \times m -2 \times M =0$$
解得
$$m = \frac{ (1- 2 \times A_1) \pm \sqrt{( 4*(A_1-1)^2 +8 \times M}}{2}$$
所以要求 m 是整数，那么需要满足两个条件：
- $\sqrt{( 4*(A_1-1)^2 +8 \times M}$ 是整数
- 整个分子是偶数
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
|
#include<iostream>
#include<cmath>
using namespace std;
int main()
{
int n;
while (cin >> n) {
for (int i =0; i<n/2; i ++)
{
int a =i;
int w =(2*a -1)*(2*a -1) +8*n;
int k =(int)sqrt(w);
if (k*k != w) continue;
int m =k +1-2*a;
if (m%2 ==1) continue;
else
cout << i << " "<<i+m/2-1 << endl;
}
}
return 0;
}
|
** 字符串移位包含的问题 **
这种移位并没有说明怎么移位，然后移动几位，所以应该是不能模拟出来的，下面是有一个既定的结论，如果在移位中包含，那么一定是在 strstr 这个中的。于是解法一就出来了。
补充cpp 的一些语法：
- 1 和true是等价的
- 字符串和字符数组的定义和初始化
直接进行初始化定义：
1
2
|
char *a ="string1";
char b[] ="string2";
|
局部变量 a b 都是在栈中，a 是指向了一个常亮， “string1” 而b 是指向了了一个数组。实际上前者的赋值是错误的，因为是其实不可改变的。使用 const char * a=“string1” 更加合适。
char 类型转换成 string类型
cpp 中使用 string 第一种方式
1
2
3
4
5
6
7
8
9
10
11
|
#include<iostream>
#include<cstring>
using namespace std;
int main()
{
string str;
str ="hello world";
cout << str <<endl;
return 0;
}
|
这种是 cpp 中使用string 的第二种方式
1
2
3
4
5
6
7
8
9
10
11
12
|
#include<iostream>
using namespace std;
int main()
{
std:: string str;
str ="hello world";
cout << str <<endl;
return 0;
}
|
问题的解法：
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
|
#include<iostream>
using namespace std;
bool isContain(char *s1, char *s2) {
int len = strlen(s1); //假设s1位较长的字符串
char s[len * 2];
for(int i = 0; i < 2; i++) {
for(int j = 0; j < len; j++) {
s[i * len + j] = s1[j];
}
}
if(strstr(s, s2) != NULL) {
return true;
} else {
return false;
}
}
int main()
{
char* s1 ="hello";
char* s2 ="hel";
bool result;
result =isContain(s1, s2);
cout << isContain(s1, s2) <<endl;
return 0;
}
|
解法二： python 实现，时间复杂度是O(n) 空间复杂度是(1) ，使用取模运算
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
def match(src, des):
if not src or not des:
return False
len1 =len(src)
len2 =len(des)
if len1 ==0 and len2 ==0:
return True
for i in range(len1):
if des[0] == src[i]:
for j in range(1, len2):
if des[j] != src[ (i+j)%len1]:
break
else:
return True
return False
|
Letter Combinations of a Phone Number
这个是做过的，深度优先算法
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
|
class Solution:
def letterCombinations(self, digits):
if not digits or digits == "":
return []
# 命名很到位，任何的dictionary 都是可以使用 maps 进行命名的
# 注意从 list 到tuple 减少了内存的使用
maps ={
'1': (),
'0': (),
'2': ('a', 'b', 'c'),
'3': ('d', 'e', 'f'),
'4': ('g', 'h', 'i'),
'5': ('j', 'k', 'l'),
'6': ('m', 'n', 'o'),
'7': ('p', 'q', 'r', 's'),
'8': ('t', 'u', 'v'),
'9': ('w', 'x', 'y', 'z')
}
results = [""]
for digit in digits:
tuple1 = maps[digit]
tmp =[]
if len(tuple1) == 0:
continue
# 二重循环， results 是之前的结果，然后每次都是要在其基础上添加一些东西
for prefix in results:
for suffix in tuple1:
tmp.append(prefix + suffix)
results = tmp
return results
|
** 求一维子数组的最大和 **
题目：输入一个整形数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。
使用了 $O(n)$ 的空间，可以优化成 $O(1)$ 的空间
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
class Solution {
public:
// 注意转移方程是 dp[i] =max(dp[i-1]+ nums[i], nums[i])
int maxSubArray(vector<int>& nums) {
int n =nums.size();
vector<int> dp(n, 0);
dp[0] =nums[0];
int res =nums[0];
for(int i =1; i< n; i++)
{
// 因为可能出现负数的情况
dp[i] =max(dp[i-1] + nums[i], nums[i]);
res =max(dp[i], res);
}
return res;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
class Solution {
public:
// 注意转移方程是 dp[i] =max(dp[i-1]+ nums[i], nums[i])
int maxSubArray(vector<int>& nums) {
int n =nums.size();
int max_v =INT_MIN;
int t =0; // 开始的时候要初始化好
for(auto num : nums)
{
t +=num;
max_v =max(max_v, t);
t =max(0, t);
}
return max_v;
}
};
|
二维子数组最大和
Tips: 通过枚举矩阵的上下界，然后再用一维情况的方法确定左右边界，就可以得到二维问题的解。二维数组是$ (m \times n) $， 那么该方法的时间复杂度是 $O( n^2 \times m) $.
当然也可以枚举左右边界，然后使用一维情况去确定上下界，所以时间复杂度是 $ O( m \times n \times min(m ,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
54
55
56
57
58
59
60
61
62
63
|
#include<iostream>
#include<cstdio>
#include<ctime>
using namespace std;
#define M 4
#define N 4
#include <memory.h>
int maxSubArray(int *arr, int len) //最大子序列和
{
int i, sum = arr[0], b = 0;
for (i = 0; i<len; ++i)
{
if (b>0)
b += arr[i];
else
b = arr[i];
if (b>sum)
sum = b;
}
return sum;
}
int maxSubMatrix(int n, int m, int array[M][N])
{
int i, j, h, max, sum = -100000;
int b[100];
for (i = 0; i < n; i++)
{
memset(b, 0, sizeof(b)); //初始化b[]
for (j = i; j < n; j++) //把第i行到第j行相加,对每一次相加求出最大值
{
for (h = 0; h<m; h++)
{
b[h] += array[j][h]; //二维数组压缩成一维数组，然后求最大子序列和
}
max = maxSubArray(b, h);
if (max>sum)
sum = max;
}
}
return sum;
}
int main()
{
int arr[M][N] = { { -15, -21,5, -12 }, { -7, 21, 20, 12 }, { 21, 0, -1, 13 }, { 10, 20, -10, -18 } };
cout << "随机二维数组为：" << endl;
//srand(time(0));
//for (int i = 0; i < M; i++)
//{
// for (int j = 0; j < N; j++)
// {
// arr[i][j] = rand() % 50 - 25;
// cout << arr[i][j] << " ";
// }
// cout << endl;
//}
cout << maxSubMatrix(M, N, arr) << endl;
system("pause");
return 0;
}
|
使用C++ 中的vector 进行改写，思路正确，但结果出错。
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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
|
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
#define M 4
#define N 4
#define MAX 100000
int maxSubarray2(vector<int> arr, int n)
{
int max_num= -MAX;
int cur_num =0;
for (int i =0; i<n; i++)
{
cur_num += arr[i];
if (cur_num < 0) cur_num =0;
if( cur_num > max_num) max_num =cur_num;
}
// 这个步骤是处理整数中有正有负的情况
/*
if (max_num ==0)
{
max_num =arr[0];
for(int i =1; i<n;i ++)
if (arr[i] >max_num) max_num =arr[i];
}
*/
return max_num;
}
int maxSubmatrix(int rows, int cols, vector<vector<int>> arr)
{
int i, j, k, max=arr[0][0], sum =-10000;
vector<int> b;
for (i =0;i< rows;i++)
{
vector <int> b(cols, 0) ;
for (j =i; j< rows; j++)
{
for(k =0;k <cols;k++) b[k] += arr[j][k];
sum =maxSubarray2(b, k);
if(sum > max) max =sum;
}
}
return max;
}
int main()
{
vector<vector<int>> arr = { { -15, -21,5, -12 }, { -7, 21, 20, 12 }, { 21, 0, -1, 13 }, { 10, 20, -10, -18 } };
//cout << arr[1][1]<<endl;
cout << maxSubmatrix(M, N, arr) << endl;
vector<int> tmp ={2, 0, -4, 9, -1,2};
cout << tmp.size()<<endl;
cout<< maxSubarray2(tmp, tmp.size())<< endl;
return 0;
}
|
把ip 地址转换成唯一的映射关系。
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
|
# 方法一
# 这个实际上是转成了大整数,比如 0.0.0.0 转成 0; 255.255.255.255 转成 255255255255
def fun2(str):
res =0
for i in range(4):
tmp =str[i*3:(i+1)*3]
res = res*1000+ int(tmp)
return res
def fun1(str):
if len(str)>3 or len(str) ==0: return -1;
if len(str) ==3: return str
if len(str) ==2: return "0"+str
if(len(str) ==1): return "00"+str
def str2int(str):
str1 =str.split(".")
if len(str1) != 4: return -1
res =""
for i in range(4):
res += fun1(str1[i])
print("to string", res)
res2 =fun2(res)
print("to int ", res2)
if __name__ =="__main__":
str =input()
str2int(str)
|