算法题杂记

发表于   |   更新于 | 分类于 | 评论数： | 阅读次数：
本文字数： 2.8k | 阅读时长 ≈ 3 分钟

交换两个数的特殊方法

加法

注意: 有可能导致溢出

1
2
3
a = a + b;         //但是加法可能会最终导致溢出
b = a - b;
a = a - b;

异或

1
2
3
a = a^b;
b = a^b;
a = a^b;

上面的实习原理是利用异或的自身特性:

1
2
a ^ a = 0
a ^ 0 = a

注意: 用异或交换两个整数存在一个陷阱

当交换两个相同的数字时, 由于异或自身的特性, 会使得这两个数字都变成0, 解决方法是加上一个判断条件:

1
2
3
4
5
if(a!=b){
  a = a^b;
  b = a^b;
  a = a^b;
}

不开根号求平方根

牛顿迭代法

假设要对 $a$ 进行开根, 那么就需要找到一个值 $x$, 满足 $x^2 = a$, 我们令 $f(x) = x^2 - a$ , 则只需找到使 $f(x)=0$ 的值 $x$ 即为开根后的值, 也就是说要求 $f(x)$ 与x轴的交点, 在x轴上任选一点 $(x_0, f(x_0))$, 求该点在函数 $f(x)$ 上面的切线方程如下:

也就是:

我们求该直线与x轴的交点, 即 $f(x)=0$ , 求得 $x$ 的值为:

如果上面求得的 $x$ 不是 $f(x)$ 与 x 轴的交点, 那么久继续这个过程, 直到结果满足我们需要的精度

1
2
3
4
5
6
7
8
9
int main(){
    double a = 24;//欲求24的开根
    double x = 1.0;
    while(abs(x*x-a)>0.0001){
        x = x- (x*x-a)/(2*x+1e-9);
    }
    cout<<x;
    return 0
}

二分法

1
2
3
4
5
6
7
8
9
10
11
int main(){
    double a = 24;//欲求24的开根
    double high = a;
    double low = 0;
    while(high-low>0.0001){
        double mid = (high+low)/2;
        if(mid*mid > t) high = mid;
        if(mid*mid < t) low = mid;
    }
    return low;
}

有两个数组, 数组很大, 其中一个数组存储着n个人的名字, 另一个数组存储着这n个人的身高?

问题一: 现在需要找出m个身高最高的人的名字, 要求时间和空间复杂度最低

问题二: 哪些排序算法时间复杂度是 $O(1)$ 的, 哪些不是

问题三: 哪些排序算法是稳定的, 哪些是不稳定的

  • 稳定: 冒泡, 插入排序, 归并(合并), 基数排序
  • 不稳定: 选择, 快排, 希尔排序, 堆排序

问题四: 现在需要设计一个算法, 每次从这n个人当中挑出一个人, 要求最终跳出的所有人当中, 身高高的人站的比例大

函数

轮盘赌算法

求下面函数的返回值:

1
2
3
4
5
6
7
8
int func(x){
    int countx=0;
    while(x){
        countx++;
        x=x&(x-1);
    }
    return countx;
}

假定x=9999, 答案:8
思路: 将x转化为2进制, 看含有1的个数

在多线程和大量并发环境下，如果有一个平均运行一百万次出现一次的bug， 你如何调试这个bug。

n个数里面求最大的m个数, (堆)

建立size为m的最小堆, 堆顶为最小的值, 堆内的数据都比堆顶小, 所以这m个数字即为n个数里面最大的m个数.

求两个不相交的连续子数组的最大和

题目：

有一个整数数组n，a和b是n里两个互不相交的子数组。返回sum(a)+sum(b)的最大值。

分析：

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
int SumOfTwoSubarray(const vector<int> &n)
{
	if (n.size() < 2)
	{
		throw exception();
	}
	vector<int> left(n.size()), right(n.size());
	int sum = n[0], maxnum = n[0];
	left[0] = n[0];
	right.back() = n.back();
	for (uint32_t i = 1; i < n.size()-1; ++i)
	{
		if (sum > 0)
			sum += n[i];
		else
			sum = n[i];
		if (sum > maxnum)
		{
			maxnum = sum;			
		}
		left[i] = maxnum;
	}
	sum = n.back();
	maxnum = n.back();
	for (uint32_t i = n.size()-2; i >=1; --i)
	{
		if (sum > 0)
			sum += n[i];
		else
			sum = n[i];
		if (sum > maxnum)
		{
			maxnum = sum;
		}
		right[i] = maxnum;
	}
	int res = 0x80000000;
	for (uint32_t i = 0; i < n.size() - 1; ++i)
		res = max(res, left[i] + right[i + 1]);
	return res;
}

新建两个数组left和right，left[i]表示n[0:i]的连续子数组的最大和，right[i]表示n[i:length-1]的连续子数组的最大和。left[i]+right[i+1]的最大值就是答案。

https://blog.csdn.net/bupt8846/article/details/48115931

随机数算法的实现

实现均匀分布的随机采样

实际正态分布的随机采样