0%

算法相关

分享一些平时遇到算法相关的程序,其中包括基础的数据算法,矩阵相关算法等

数据算法相关

随机返回列表的全部元素

写一个函数,随机返回输入列表的全部元素

1
2
3
4
5
6
7
import random

def random_lst_val(lst):
len_ = len(lst)
while len_ > 0:
yield lst.pop(random.randint(0, len_ - 1))
len_ = len_ - 1

最长的没有重复字母的子字符串

给一个字符串,找出长度最长的且没有重复字符的子字符串,如:abcabcbb->abc长度是3,bbbbb->b长度是1,pwwkew->wke长度是3

1
2
3
4
5
6
7
8
9
10
11
12
def longest_substring(str_):
tmp_longest_word = {}
word = ''
for i in str_:
if i not in word:
word += i
else:
tmp_longest_word[len(word)] = word
word = i

longest_idx = max(tmp_longest_word.keys())
return tmp_longest_word[longest_idx], longest_idx

将矩阵0元素所在行列置0

给定一个0、1矩阵,请写一个矩阵转换函数,将所有0所处的行和列所有元素置为0,并分析时间复杂度:

1
2
3
1 0 0          0 0 0
1 0 1 --> 0 0 0
1 1 1 1 0 0

Python函数

  • 通过Numpy计算
1
2
3
4
5
6
7
8
9
10
import numpy as np

def tran_a_row_col_zero(a):
"""
:param a: array
"""
i, j = np.where(a==0)
a[i, :] = 0
a[:, j] = 0
return a
  • 用内置库计算
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import copy

lst = [[1, 0, 0], [1, 0, 1], [1, 1, 1]]

def change_row_col2zero(arr, i, j):
len_ = len(arr)
arr[i] = [0] * (len_)
for idx in range(len_):
arr[idx][j] = 0
return arr

def transform_list(l):
len_ = len(l)
len_sub = len(l[0])
copy_ = copy.deepcopy(lst)

for i in range(len_):
for j in range(len_sub):
if lst[i][j] == 0:
change_row_col2zero(copy_, i, j)

return copy_

print transform_list(lst)

时间复杂度

  • Numpy时间复杂度未知
  • 用内置库,如果矩阵是方阵且行数为n: O(n^3)

阿姆斯特朗数

一个n位正整数等于其各位数字的n次方之和,则称该数为阿姆斯特朗数,例如1^3 + 5^3 + 3^3 = 153,写一个函数,计算所有给定范围内的阿姆斯特朗数

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
def armstrong_number(*args):
"""用户输入范围的armstrong_number
:param args:
:type args: tuple
:return:
"""
# 检查用户输入数量
if len(args) == 3:
start, end, step = args
if len(args) == 2:
start, end = args
step = 1
if len(args) == 1:
end = args[0]
start, step = 0, 1

for num in xrange(start, end, step):
# 指数位数和
sum = 0
# 指数
n = len(str(num))

temp = num
while temp > 0:
digit = temp % 10
sum += digit ** n
temp //= 10

if num == sum:
yield num

斐波那契数列

斐波那契数列定义:F(0)=0,F(1)=1, F(n)=F(n-1)+F(n-2),例如0,1,1,2,3,5…给一个通用函数,输入数列最大值,得到一系列斐波那契数列

1
2
3
4
5
def fab(max):
a, b = 0, 1
while a <= max:
yield a
a, b = b, a + b

任意连续整数阶乘的和

1
2
def add_factorial(n):
return reduce(lambda x, y: x + y, map(lambda x: x * x, range(1, n + 1)))

任意连续区间的素数、质数

1
2
3
4
def is_prime(start, stop):
# 要求x大于2并且x在区间[2, x)中没有整除的除数
return filter(lambda x: x >= 2 and not [x for i in range(2, x) if x % i == 0],
range(start, stop + 1)) # 取出质数,x从range(start,stop) 取的数

字典中最大的value对应的keys

1
2
3
4
5
def dct_max_val_key(dct):
max_value = max(dct.values())
keys = [k for k, v in dct.items() if k == max_value]
# 最大值对应的key可能有一个或者多个
return keys[0] if len(keys) == 1 else keys

字符串最长且相邻元素不相同的子字符串

找出一个字符串中最长的相邻字符串中不重复的子字符串,并输出字符串的长度。如 11101111,最长是3,子字符串是101。110011 最长是2 子字符串是10 或 01

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
def find_large_sub_str(string):
"""只能找到最长的长度,当有多个值重复的时候不能找到全部最长的子字符串"""
sub_str = ''
pre = None
dct = {}

for i in string:
if pre != i:
sub_str += i
else:
dct[len(sub_str)] = sub_str
sub_str = pre
pre = i

max_key = max(dct.iterkeys())
return max_key, dct[max_key]

def find_large_sub_str_1(string):
"""能找到重复的长度的子字符串"""
sub_str = ''
pre = None
dct = {}

for i in string:
if pre != i:
sub_str += i
else:
dct[sub_str] = len(sub_str)
sub_str = pre
pre = i

max_val = max(dct.itervalues())
keys = [k for k, v in dct.items() if v == max_val]
return max_val, keys[0] if len(keys) == 1 else keys

字符串str中的连续最长的数字串

读入一个字符串str,输出字符串str中的连续最长的数字串。例如:abcd12345ed125ss123456789 输出:123456789

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def str_longest_int(s):
result_dict = {}
int_set = set([str(i) for i in range(0, 10)])
tmp = ''

for i in s:
if i in int_set:
tmp += i
elif tmp:
result_dict[tmp] = len(tmp)
tmp = ''
# 防止最后还有一个值
if tmp:
result_dict[tmp] = len(tmp)

max_val = max(result_dict.values())
key = [key for key in result_dict if result_dict[key] == max_val]
return key[0] if len(key) == 1 else key

s = 'abcd12345ed125ss123456789'
print str_longest_int(s)

字符数组最后一个单词长度

输入:”Hello World “。输出:5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def last_word_len(s):
len_ = len(s)
curr = 0
index = -1
tmp = ''

while curr < len_:
if s[index] != ' ':
tmp += s[index]
# 避免倒数第一个是' '
elif index != -1:
return len(tmp)
index -= 1
curr += 1

# 只要一个单词的情况
return len(s.strip())

s = "Hello_World "
print last_word_len(s)

数组中找指定和

数组A由1000万个随机正整数(int)组成,设计算法,给定整数n,在A中找出a和 b,使其符合如下等式:n = a + 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
"""
题目数据量大看似吓人 但是还是要透过现象看本质
set用于去重 如果set太大也可以改成bitmap
"""

def two_sum_1(a, n):
"""标准leetcode的twosum问题"""
mid_dict = {}

for val in a:
if val in mid_dict:
return val, mid_dict[val]
else:
mid_dict[n - val] = val

return None

def two_sum_2(a, n):
"""根据问题调整成set格式"""
mid_set = set()

for val in a:
if val in mid_set:
return val, n - val
else:
mid_set.add(n - val)

return None

a = [1, 2, 3, 4, 5, 6, 7, 8, 9]
n = 10
print two_sum_1(a, n)
print two_sum_2(a, n)

判断重量

给定两颗钻石的编号g1、g2,编号从1开始,同时给定关系数组vector,其中元素为一些二元组,第一个元素为一次比较中较重的钻石的编号,第二个元素为较轻的钻石的编号。最后给定之前的比较次数n。请返回这两颗钻石的关系,若g1更重返回1,g2更重返回-1,无法判断返回0。输入数据保证合法,不会有矛盾情况出现。输入:2,3,[[1,2],[2,4],[1,3],[4,3]],4 返回: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
27
28
29
30
"""
* 根据描述简历一个有向图 在图中找到指定两点之间是否有路径
* 钻石编号是顶点,比较关系是边,生成有向图。先做两个顶点是否可达判断,再进行拓扑排序
"""
def bigger(x, y, l, n):
"""用递归调用 看是否有大小关系"""
for i in range(n):
if l[i][0] == x:
if l[i][1] == y:
return 1
else:
return bigger(l[i][1], y, l, n)

def compare(g1, g2, p, n):
"""要经过两次比较 比价g1 g2谁更大"""
tag = bigger(g1, g2, p, n)

# 先交换后比较
if tag != 1:
tag = bigger(g2, g1, p, n)

if tag == 1:
tag = -1
else:
tag = 0
return tag


print compare(2, 3, [[1, 2], [2, 4], [1, 3], [4, 3]], 4)
print compare(3, 2, [[1, 2], [2, 4], [1, 3], [4, 3]], 4)

每隔两个数删除一个数

有一个整型数组a[n]顺序存放0~n-1,要求每隔两个数删掉一个数,到末尾时循环至开头继续进行,求最后一个被删掉的数的原始下标位置。
以8个数(n=8)为例:{0,1,2,3,4,5,6,7},0->1->2(删除)->3->4->5(删除)->6->7->0(删除),如此循环直到最后一个数被删除。

1
2
3
"""
生成一个循环链表,一个值记录当前索引,当索引能被2整除且不为0时,删除该值,知道链表只剩一个元素
"""

LeetCode

Longest Substring Without Repeating Characters

LeetCode[3]:Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters.
Examples:
Given “abcabcbb”, the answer is “abc”, which the length is 3.
Given “bbbbb”, the answer is “b”, with the length of 1.
Given “pwwkew”, the answer is “wke”, with the length of 3. Note that the answer must be a substring, “pwke” is a subsequence and not a substring.

1
2
3
4
5
6
7
8
9
10
11
12
13
def lengthOfLongestSubstring(s):
start = maxLength = 0
usedChar = {}

for i in range(len(s)):
if s[i] in usedChar and start <= usedChar[s[i]]:
start = usedChar[s[i]] + 1
else:
maxLength = max(maxLength, i - start + 1)

usedChar[s[i]] = i

return maxLength