记一次惨痛的编程考试经历

一次惨痛的编程考试经历

最近一个月,一直在刷leetcode来准备公司的上机编程考试,平均每天刷3道题左右,主要是中等题型,偶尔也刷困难题.
按照题目的类型在刷,如分治,递归回溯,二叉树,dfs,bfs,dp,前缀和这些.自以为准备的很充分,结果还是挂了.
心中的郁闷可想而知,俗话说,”大痛者必有大志”,从成长型思维来看,还是很有必要总结一下失败的经验的.
先来回顾一下考试题目:
1.一道系统设计题目,主要考查如何组织代码实现不同的排序策略,整体上比较简单,也做出来了
2.一道深度优先遍历题目,本来以为能轻松做出,可是没有AC,也一直没有想出原因,也因此而挂了
3.二维前缀和+合并区间,只想到了用二维前缀和,后面合并区间没有优化,造成超时

其中第2题还一直怀疑用例有问题,一直没有发现代码中的bug.直到几天后,才发现问题.代码其实仔细推敲就会发现不符合题目要求,没有考虑清楚  
叶子节点的情形.

总结了下失利原因有以下几点:

  1. 准备考试要首先搞清楚考的是什么?算法一般不会考太难的,重点还是在于有没有好的编程习惯.编程习惯包括如何审题分析线索,如何设计用例,如何调试,如何熟练的使用语言等.
  2. 体会到了测试驱动开发的重要性,如何根据题目设计有效的用例和考虑清楚所有边界条件.
  3. 之前刷题只注重有没有解题思路和题目的难度上,用例不过也是直接看失败用例,造成思维逻辑有漏洞
  4. 完全没有练习如何对照题目的限制条件设计用例,如何调试代码验证符合预期,一味地追求刷题数量,忽略了本质.
  5. 做题不纯粹是速度,更重要的是准确,如果代码有bug和没有代码是一样的.

归并排序

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

def merge_sort(a):
def merge_array(a, i, j):
if i >= j:
return a

def merge(a, left_i, left_j, right_i, right_j):
new_a = []
i, j = left_i, right_i
while i <= left_j and j <= right_j:
if a[i] <= a[j]:
pos = i
i += 1
else:
pos = j
j += 1
new_a.append(a[pos])

if i <= left_j:
new_a.extend(a[i:left_j+1])

if right_i <= right_j:
new_a.extend(a[j:right_j+1])

a[left_i:right_j+1] = new_a

mid = i + (j - i) // 2
merge_array(a, i, mid)
merge_array(a, mid+1, j)
merge(a, i, mid, mid+1, j)
return a

return merge_array(a, 0, len(a)-1)

if __name__ == "__main__":
print(merge_sort([1, 3, 2, 4, 6, 8, 7]))
print(merge_sort([8]))
print(merge_sort([9, 8, 7, 4, 3, 2, 0]))
print(merge_sort([9, 10, 12, 14, 13, 22, 100]))

查找第k大元素

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

"""
Copyright (c) Huawei Technologies Co., Ltd. 2021-2021. All rights reserved.
Description: easy_ut p215 file
Author: zhangxiaoan 00565442
Create: 2021/4/30 16:19
"""

def top_k(nums, k):
def partition(nums, left, right):
if left >= right:
return 1

sel = nums[right]
pos = left-1
start = left
while start < right:
if nums[start] > sel:
pos += 1
if start != pos:
tmp = nums[pos]
nums[pos] = nums[start]
nums[start] = tmp
start += 1
pos += 1
nums[pos], nums[right] = sel, nums[pos]
return pos - left + 1

def quick_find(nums, left, right, k):
m = partition(nums, left, right)
if m == k:
return nums[left + m - 1]

if m > k:
return quick_find(nums, left, left + m - 2, k)
else:
return quick_find(nums, left + m, right, k - m)
return quick_find(nums, 0, len(nums)-1, k)

if __name__ == "__main__":
print(top_k([1], 1))
print(top_k([3, 1, 2, 4], 2))
print(top_k([3, 2, 1, 5, 6, 4], 2))
print(top_k([5, 2, 4, 1, 3, 6, 0], 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
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
"""
Copyright (c) Huawei Technologies Co., Ltd. 2021-2021. All rights reserved.
Description: easy_ut p282 file
Author: zhangxiaoan 00565442
Create: 2021/4/29 9:25
"""


def add_operators(num, target):
n = len(num)
ans = []

def gen_expr(num, index, expr, prev_op, prev_value, value):
nonlocal n, target, ans

start = num[index]
end = index
while end < n:
val = int(num[index:end + 1])
expr.append(prev_op)
expr.append(num[index:end + 1])


if prev_op == '+':
next_val = value + val
if prev_op == '-':
next_val = value - val
if prev_op == '*':
next_val = value + prev_value * val

if end == n - 1:
if next_val == target:
ans.append("".join(expr[1:]))

expr.pop()
expr.pop()
return

if prev_op == '+':
gen_expr(num, end + 1, expr, "*", val, value)
elif prev_op == '-':
gen_expr(num, end + 1, expr, "*", -val, value)
else:
gen_expr(num, end + 1, expr, "*", prev_value * val, value)


gen_expr(num, end + 1, expr, "+", 0, next_val)
gen_expr(num, end + 1, expr, "-", 0, next_val)
expr.pop()
expr.pop()

if start == '0':
break

end += 1

gen_expr(num, 0, [], "+", 0, 0)
return ans


if __name__ == "__main__":
print(add_operators("123", 6))
print(add_operators("232", 8))
print(add_operators("105", 5))
print(add_operators("00", 0))
print(add_operators("3456237490", 9191))
print(add_operators("134562379", 134562379))
print(add_operators("123456789", 45))

查找两个有序数组的中位数


def find_media_sorted_arrays(nums1, nums2):
    m, n = len(nums1), len(nums2)

    def find_kth(nums1, nums2, k):
        m, n = len(nums1), len(nums2)
        if m < n:
            return find_kth(nums2, nums1, k)

        if n == 0:
            return nums1[k-1] 

        if k == 1:
            return min(nums1[0], nums2[0])

        m2 = min(n, (k+1)//2)
        m1 = k - m2
        if nums1[m1-1] < nums2[m2-1]:
            return find_kth(nums1[m1:], nums2, k - m1)
        else:
            return find_kth(nums1, nums2[m2:], k - m2)
        

    total = m + n
    if total % 2 != 0:
        return find_kth(nums1, nums2, total//2 + 1)
    else:
        return (find_kth(nums1, nums2, total//2) + find_kth(nums1, nums2, total//2 + 1))/2

    
if __name__ == "__main__":
    print(find_media_sorted_arrays([1, 3], [2]))
    print(find_media_sorted_arrays([1, 2], [3, 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
32
33
34
35
36
37
38
39
40
41
42

"""
Copyright (c) Huawei Technologies Co., Ltd. 2021-2021. All rights reserved.
Description: easy_ut p_offer_51 file
Author: zhangxiaoan 00565442
Create: 2021/4/28 17:38
"""
def merge_reverse(nums, i, j):
if j < i:
return [], 0

if i == j:
return nums[i:i+1], 0

mid = i + (j-i)//2
left, left_num = merge_reverse(nums, i, mid)
right, right_num = merge_reverse(nums, mid+1, j)

new_nums, reverse = [], 0
n_left, n_right = len(left), len(right)
n_i, n_j = 0, 0
while n_i < n_left and n_j < n_right:
if left[n_i] <= right[n_j]:
new_nums.append(left[n_i])
n_i += 1
else:
new_nums.append(right[n_j])
reverse += n_left - n_i
n_j += 1

new_nums.extend(left[n_i:])
new_nums.extend(right[n_j:])

return new_nums, reverse + left_num + right_num


def reversePairs(nums):
return merge_reverse(nums, 0, len(nums)-1)[1]

if __name__ == "__main__":
print(reversePairs([7, 5, 6, 4]))
print(reversePairs([1, 3, 2, 3, 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
31

def quick_sort(a):
def quick_sort_array(a, i, j):
if i >= j:
return a

def partition(a, i, j):
pos = i
while i < j:
if a[i] < a[j]:
if i != pos:
a[pos], a[i] = a[i], a[pos]
pos += 1
i += 1
a[pos], a[j] = a[j], a[pos]
return pos


k = partition(a, i, j)
quick_sort_array(a, i, k-1)
quick_sort_array(a, k+1, j)
return a

return quick_sort_array(a, 0, len(a)-1)

if __name__ == "__main__":
print(quick_sort([1, 3, 2, 4, 5, 8, 7, 0]))
print(quick_sort([1]))
print(quick_sort([]))
print(quick_sort([9, 8, 7, 3, 2, 0]))
print(quick_sort([9, 18, 27, 33, 42, 50]))

动态规划

dp动态规划

解决问题

通常用于解决最优化问题,通常做出一组选择来达到最优解.

特点

  • 做出每个选择时,通常会生成与原问题形式相同的子问题
  • 多于一个选择子集都会生成相同的子问题(子问题重叠)

关键技术

  • 对每个相同的子问题保存其解,当其重复出现时避免重复求解
  • 通常可将指数时间的算法转换为多项式级别的算法

步骤

  1. 刻画一个最优解的结构特征
  2. 递归地定义最优解的值
  3. 计算最优解的值,通常采用自底向上的方法
  4. 利用计算出的信息构造一个最优解

典型问题

算法导论

钢条切割
求两个序列的最长公共子序列
构造最优二叉搜索树