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
def mergeSort(arr):
import math
if(len(arr)<2):
return arr
middle = math.floor(len(arr)/2)
left, right = arr[0:middle], arr[middle:]
return merge(mergeSort(left), mergeSort(right))


def merge(left,right):
result = []
while left and right:
if left[0] <= right[0]:
result.append(left.pop(0))
else:
result.append(right.pop(0))
while left:
result.append(left.pop(0))
while right:
result.append(right.pop(0))
print(result)
return result


if __name__ == '__main__':
arr = [8, 4, 5, 7, 1, 3, 6, 2]
mergeSort(arr)

贪心算法

贪心算法是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,算法得到的是在某种意义上的局部最优解

Read more »

快慢指针

快慢指针就是定义两根指针,移动的速度一快一慢,以此来制造出自己想要的差值。这个差值可以让我们找到链表上相应的节点。

Read more »

动态规划

动态规划,无非就是利用历史记录,来避免我们的重复计算。而这些历史记录,我们得需要一些变量来保存,一般是用一维数组或者二维数组来保存。

Read more »

一、遇到的问题

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
// 象棋中结算积分的函数
function calculate(selfsocores, othersocores, result, color, mult) {
let finalsocores; //最终积分
let factor; //因子
let expect; //期望
let gap; //积分差
let variable;
switch (color) {
case PLAY_COLOR.RED:
variable = -100;
break; // 红方
case PLAY_COLOR.BLACK:
variable = 100;
break; // 黑方
default:
variable = 0;
break;
}
if (selfsocores < 1000) {
factor = 120;
} else if (selfsocores < 1400) {
factor = 60;
} else if (selfsocores < 1800) {
factor = 30;
} else if (selfsocores < 2000) {
factor = 25;
} else if (selfsocores < 2200) {
factor = 20;
} else if (selfsocores < 2400) {
factor = 15;
} else {
factor = 10;
}
gap = ((othersocores - selfsocores) + variable) / 400;
expect = 1 / (Math.pow(10, gap) + 1);
console.log("factor:", factor, "variable:", variable, "expect:", expect, "gap:", gap, factor * (result - expect));
finalsocores = Math.floor(selfsocores + mult * parseInt(factor * (result - expect)));
return finalsocores;
}

1
2
3
4
5
6
7
输入为: selfsocores = 5083, othersocores = 1818, result = 1, color = 1, mult = 1;
输出为:factor: 10 variable: 100 expect: 0.999999987767929 gap: -7.9125 1.223207102274415e-7
1
5084

其中 factor * (result - expect) 的值为 1.223207102274415e-7,远小于1,但 parseInt(factor * (result - expect)) 却得到结果1

二、科学计数法

JavaScript中对于极大或者极小的数,可以用科学计数法e来表示的浮点数值来表示。科学计数法允许字母e 或 E 的后面,跟着一个整数,表示这个数值的指数部分。

以下两种情况,JavaScript 会自动将数值转为科学计数法表示

1
2
3
4
5
6
7
8
9
10
11
(1) 小于1且小数点后面带有6个0以上的浮点数值:
JavaScript 代码:
0.0000003 // 3e-7
0.00000033 // 3.3e-7
0.000003 // 0.000003

(2) 整数位数字多于21位:
JavaScript 代码:
1234567890123456789012 //1.2345678901234568e+21
1234567890123456789012.1 //1.2345678901234568e+21
123456789012345678901 //123456789012345680000

三、parseInt函数

1
2
3
4
5
语法:parseInt(string [ , radix])

string 要被解析的值。如果参数不是一个字符串,则将其转换为字符串(使用ToString 抽象操作)。字符串开头的空白符将会被忽略

radix 从2到36,表示字符串的基数。请注意,10不是默认值!

由于某些数字在其字符串表示形式中使用e字符(例如 6.022×23 表示 6.022e23 ),因此当对非常大或非常小的数字使用数字时,使用 parseInt 截断数字将产生意外结果。

1
2
console.log(parseInt(0.0000015));   // print 0
console.log(parseInt(0.00000015)); // print 1

官方定义: https://developer.mozilla.org/zh-CN/docs/Web/JavaScript/Reference/Global_Objects/parseInt

在日常的编程中,我们难免会遇到去打开个文件的需求。python标准库中有一个walk()方法,是一个简单易用的文件、目录遍历器,可以帮助我们高效的处理文件、目录。

Read more »

排列组合算法

paixu

1
2
3
对于abc的排列,当我们进行排列时,可以先考虑第1位可能有哪些情况,如上图所示
有a,b,c三种情况,然后再对后面的两位进行排列,采用相同的思路,可以很容易的
就通过递归实现全排列了。

python实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14

def rank(data, step):
"""
:param data:
:param step: 当前的首位
"""
if step == len(data) - 1:
print data
else:
for i in range(step, len(data)):
# 遍历这一层中的各种选择,比如先a首位,然后可选择下一个是b、c
data[step], data[i] = data[i], data[step]
# 递归后面的情况, 选了之后在遍历b、c
rank(data, step + 1)
1
2
3
4
5
有一个数组[1, 2, 3, 4, 5, 6],我想从里面随机选出三个来,有哪些取法。

1,首先从第一个元素下手,对于第一个元素,我们有两个选择:要 or 不要。
2,如果要了,那么我们需要选择的元素就少了一个了,我们只需要从后面的元素中选出两个就够了。
3,如果不要,我们就从第二个元素继续看,此时我们还是要选出三个。

python实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def combine(data, step, select_data, target_num):
if len(select_data) == target_num:
# 选择的元素已经够了,就输出并返回
print(select_data)
return
if step >= len(data):
# 没有元素选了
return
# 选择当前元素
select_data.append(data[step])
combine(data, step + 1, select_data, target_num)
# 从已选择元素中先删除
select_data.pop()
# 不选择当前元素
combine(data, step + 1, select_data, target_num)