Learning to be Giant.

做Leetcode的时候的一些记录

|

最近在做Leetcode,这里记录一些做题过程中疏忽或者意识到的东西,方便以后查阅

Balanced Binary Tree

题目见这里

我竟然想当然的觉得只要判断一下两棵子树的高度就可以,但是忘了只要任意一棵不管在什么level上面的子树只要不平衡,那么整棵树就不平衡。例子如:

        1
       / \
      2   2
     /     \
    3       3

char* and string literal

从C++11开始,字符串常量不可以直接赋给一个char*的变量了,原因在于这样从语法上给与了修改字符串常量的可能性。

char* str = "apple"; // WRONG
const char* str = "apple"; // CORRECT

Word Ladder问题

在Leetcode上面的这道题Word Ladder

首先想到对这个dictionary构建一个图,然后在图上利用Dijkstra算法搜索最短路径。但是实现完之后超时。之后看到有人提到说因为这个问题每条边都是相同的权重,所以没必要用Dijkstra,使用BFS就可以了。于是重新利用BFS写了一遍就通过了……

Dynamic Programming

Decode Ways

题目见这里

我起初的考虑是用递归搜索,但是总是超时,后来意识到这个题可以用DP。说起来这是DP比较简单的一个题目,一开始没想到主要还是自己对于DP了解不透彻,不习惯应用。

在写DP的过程当中有一个问题需要记录一下:

首先,基本思路是只考虑这个字符串的n前缀,即前n个字母组成的子串。那么递推公式就是:

\[P_n = P_{n-1}*a_1 + P_{n-2}*a_2\]

其中$a_1$和$a_2$分别表示如果将该子串中的最后一个字母单独加入能否构成一个新的子串,以及如果单独加入该子串中的后两个字母能否构成新的子串。这里需要注意的是,针对$a_2$,不需要考虑两个数字分别表示两个字母的情况,只需要考虑两个数字组合起来表示一个字母的情况,原因在于前者已经被$P_{n-1}$表示过了。

另外,在这个题目里面还有一个小trick,就是这道题目竟然会测试0这样的输入,即错误输入。所以在代码当中我对错误输入还进行了一些判断。

Disclaimer: This is a personal weblog. The opinions expressed here represent my own and not those of any entity with which I have been, am now, or will be affiliated.

Comments