Jaqen's Blog

每周 ARTS 第 3 期

字数统计: 1.1k阅读时长: 3 min
2019/07/30 Share

Algorithm

描述

判断一个整数是否是回文数。回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。

示例 1

输入: 121
输出: true

示例 2

输入: -121
输出: false
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

示例 3

输入: 10
输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数。

方法

不考虑转换为字符串。

数字本身反转对比,相同就是回文。但是反转后的数字可能出现溢出问题。

最优解是反转一半的数字,前一半与后一半的反转如果相同,就是回文。

关键在于如何确定反转数字的位数已经达到原始数字位数的一半?

将原始数字除以 10,然后给反转后的数字乘上 10,所以,当原始数字小于反转后的数字时,就意味着我们已经处理了一半位数的数字。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public boolean isPalindrome(int x) {
// 特殊情况:
// 当 x < 0 时,x 不是回文数。
// 同样地,如果数字的最后一位是 0,为了使该数字为回文,
// 则其第一位数字也应该是 0
// 只有 0 满足这一属性
if(x < 0 || (x % 10 == 0 && x != 0)) {
return false;
}

int revertedNumber = 0;
while(x > revertedNumber) {
revertedNumber = revertedNumber * 10 + x % 10;
x /= 10;
}

// 当数字长度为奇数时,我们可以通过 revertedNumber/10 去除处于中位的数字。
// 例如,当输入为 12321 时,在 while 循环的末尾我们可以得到 x = 12,revertedNumber = 123,
// 由于处于中位的数字不影响回文(它总是与自己相等),所以我们可以简单地将其去除。
return x == revertedNumber || x == revertedNumber/10;
}

复杂度分析

时间复杂度:O(log10(n))
空间复杂度:O(1)

Review

7 Skills of Highly Effective Programmers

高效程序员的七项技能

作者介绍了高效程序员的七项技能,很有意思。

1. 学习如何阅读别人的代码

能够阅读别人的代码,有两点好处。一是读别人的代码时,能够了解到什么样的代码设计是糟糕的,对于自己做代码设计有很大帮助。二是你知道了什么样的代码是别人容易理解的,什么样的代码时别人难以理解的。

读别人代码时一定要多吐槽,这样别的工程师就会觉得你是个优秀的工程师。

能够阅读别人的代码使你更有价值,毕竟,再庞大复杂的系统代码,即使使得别人困惑,也不会难住你。

2. 对糟糕项目的直觉

对糟糕项目的直觉,需要长期的项目实践。烂项目做多了,自然就有了这种直觉。

3. 避免会议

开会在所难免。写代码需要集中精力,管理好会议时间就非常重要了。一种方法是每天留出两个时间集中开会,第二就是比其他人早点到,安静的写代码。

4. Github

Github 命令使编程更加美好。

5. 编写简单可维护的代码

刚入门的程序员喜欢将他们知道的所有都提现到代码中,导致不必要的复杂性。

过度在使用设计模式、过度抽象会导致项目可维护性很差。

6. 学会说”不”,分清轻重缓急

大公司里,永远都有无穷尽的活儿,学会说“不”,分清轻重缓急,只做当前重要的、能做的事。

7. 操作设计思想

“考虑未来的用户需要如何使用您的新模块,他们可能不正确地使用它,可能需要哪些参数,以及未来的程序员可能需要您的代码的方式是否不同。”

开发之前多考虑边缘案例和整个高层设计。

Tip

总结分析了 YUV 格式:

YUV 格式详解

Share

之前写的一篇文章,介绍了达克效应。

达克效应

公众号看到一篇文章,觉得写的不错,技术人员都应该看看对照自己。

技术人员如何破除达克效应(认知偏差)?

CATALOG
  1. 1. Algorithm
  2. 2. Review
  3. 3. Tip
  4. 4. Share