什么都略懂一点,生活更美好一些

0%

关于阶梯数问题的复盘

背景

昨天被问到了一道「阶梯数」的问题,题目还原如下:

给定一个整数数列,如果它满足取任意相邻两位上的值,只要满足差的绝对值都为 1,则称其为阶梯数。

复盘

现在回头一想是很基础的题目,可惜当场答得细碎。解题前我们得先找一些「甩锅」的理由:

  • 过度思考
    • 总是觉得出题者的意图附带有特别的含义
  • 思维惯性
    • 之前做的一些分类题,回文也好,DFS 也好,习惯将解题思路往里面套。
  • 心态问题
    • 表达能力作为输出的一种方式,刻意练习「小黄鸭」模式是必要的。

针对第一点,要意识到出题者对于白板编程的要求关注的是被提问者的解题思路,复杂难解的题目并不是考察的关键指标,观察对方遇到问题的思考过程比结果重要。在这短时间内了解一个人的行为与思考模式也算普遍且相对有效的手段。

对于如何处理思维惯性。选择忘记之前的经验不失为一种最好的办法。经验可以帮助处理已有的问题模式,但无法处理新类型的窘境。所谓无招胜有招,张三丰把太极剑传授给张无忌时,要他将招数尽数忘掉才算学会:

张无忌学第一遍时,他忘记了大半剑招;学第二遍时,他还有几招没忘;学第三遍时,他才把所有剑招忘记。《倚天屠龙记》原著描写如下:张无忌在殿上缓缓踱了一个圈子,沉思半晌,又缓缓踱了半个圈子,抬起头来,满脸喜色,叫道:「这我可全忘了,忘得干干净净的了。」张三丰道:「不坏,不坏!忘得真快,你这就请八臂神剑指教罢!」

李小龙的哲学中也有类似的思想:

清空你的杯子,方能再行注满,空无以求全。

至于最后的心态,要认识到慌乱对于求解并无裨益。需要从结果论调整为过程论,「连续的」到达目的地而不是「离散的」到达才是前进的方式。只要觉得方向没有问题,剩下的都是时间上的问题。

题解

解题思路为:一次遍历,每次的循环中取相邻数进行两两比较,只要中途不中断完成循环即为阶梯数:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static boolean valid(String str) {
char[] arr = str.toCharArray();
if (arr.length == 0) {
return false;
}

for (int i = 0; i < arr.length - 1; i++) {
int pre = Integer.parseInt(String.valueOf(arr[i]));
int next = Integer.parseInt(String.valueOf(arr[i + 1]));

if (Math.abs(pre - next) != 1) {
return false;
}
}

return true;
}