2019-10-16 Daily Report

概览

回首夕阳红尽处,应是长安。

时间:Wednesday, October 16, 2019 10:06 AM

作者:Syncher Pylon


  • 学习算法
  • 学习英语

算法学习笔记

回头一看,学习算法也有一段时间了,从大学开始,上上下下买的算法书也有 5 本了。再看看 Leetcode Profile 也做了不少题了,可是通过率一直在下降,每次参加 Leetcode 周末竞赛遇到的最大困惑或是就是 Debug 时间太长。俗话说”学而不思则罔,思而不学则殆“,一味的刷题是没有用的,我需要思考、总结、练习。思考为什么不能 Bugfree,思考如何解题,思考为什么要学算法;总结解题模板,做到触类旁通,总结解题步骤,争取 Bugfree;练习也是要有针对性的,针对自己的薄弱环节然后加强练习。

关于如何 Bugfree 的思考?

要做到 Bugfree 我认为至少需要两步,首先得保证解题思路(方法)可行,不考虑时空复杂度情况下可行的;其次是解的边界条件和非法输入要被正确处理。基于以上思考, 我希望对解题步骤做新的尝试:

  1. 思考解题算法,如果题目较难,可以借助一个或多个普通用例分析问题(如果超过一定时间还分析不出来应该参考别人的思路)
  2. 验证算法的正确性
  3. 考虑 corner case 对算法的影响
  4. 如果算法可行,开始写代码
  5. 调试和验证

Leetcode 858 Score of Parentheses 为例

算法一:递归

1
2
3
4
5
6
7
Case 0: "()" = 1
Case 1: The whole string is balanced
e.g.: "(A)"
res = 2 * score("A")
Case 2: Substring is balanced
e.g.: "(A)(B)"
res = score("(A)") + score("(B)")

因为题目对输入做了限制, S 一定是平衡的,而且 S 非空,所有情况都在算法考虑中,没有边角情况,所以算法实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
def scoreOfParentheses(self, S: str) -> int:
def score(s, l, r):
if r - l == 1:
return 1 # "()"
b = 0
for i in range(l, r):
if s[i] == "(":
b += 1
else:
b -= 1
if b == 0:
# score("(A)(B)(C)") = score("(A)") + score("(B)(C)")
return score(s, l, i) + score(s, i + 1, r)

return 2 * score(s, l+1, r-1)


return score(list(S), 0, len(S)-1)

英语学习笔记

  • closer: a short distance away or apart in space or time.

  • pivotal: of crucial importance in relation to the development or success of something else.

    a pivotal role in aligning

  • foresee: be aware of beforehand; predict

  • synergy: 协同作用

    In order to leverage synergies, …

  • not damaged or impaited in any way; complete

    stay intact

  • facilitate: make (an action or process) easy or easier.

  • seam: 接缝

  • seamless: smooth and without seams or obvious joins.

  • transition: the process or a period of changing from one state to another

    I fully trust you to facilitate a seamless transition.

  • one more: 再多一个

having major effect on someone or something

important crucial fundamental vital significant central critical pivotal substantial

参考词典:https://www.macmillandictionary.com/us

本文标题:2019-10-16 Daily Report

文章作者:Syncher

发布时间:2019年10月16日 - 10:10

最后更新:2019年10月18日 - 18:10

原始链接:https://0x400.com/2019-10-16-diary-2019-10-16.html

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。