Algorithm
本周选择的算法题是：Sum of Square Numbers
规则如下：
Given a non-negative integer c, your task is to decide whether there’re two integers a and b such that a2 + b2 = c.
Example 1:
Input: 5
Output: True
Explanation: 1 * 1 + 2 * 2 = 5
Example 2:
Input: 3
Output: False
Solution
这题有好几种解决。
双指针暴力解法
class Solution:
def judgeSquareSum(self, c: int) -> bool:
left, right = 0, int(sqrt(c))
while left <= right:
num = left*left + right*right
if num == c:
return True
elif num < c:
left += 1
else:
right -= 1
return False
使用 sqrt 的优化版本
class Solution:
def judgeSquareSum(self, c: int) -> bool:
for left in range(int(sqrt(c)) + 1):
right = sqrt((c - left*left))
if right.is_integer():
return True
return False
基于二分实现的 sqrt
class Solution:
def judgeSquareSum(self, c: int) -> bool:
def can_sqrt(num, start, end):
if start > end: return False
mid = start + (end - start) // 2
if mid*mid == num:
return True
elif mid*mid < num:
return can_sqrt(num, mid+1, end)
else:
return can_sqrt(num, start, mid-1)
left = 0
while left*left <= c:
right = c - left*left
if can_sqrt(right, 0, right):
return True
left += 1
return False
Review
Difference between Coding and Programming
Difference Between 是一个科普性质的网站：
- 学究风，抠细节
- 话题极广，涵盖从商业到技术，包括最近流行的 nCoV
就这篇文章而言，可以通过它对 programmer 的定义反思自己是不是合格的程序员：
- 对语言有深入的了解和理解？
- 为场景找出合适的设计模式？
- 能用最少的代码达到最好的性能？
- 能在问题发生前分析出代码潜在的问题？
- …
程序员要致力于解决复杂的问题，毕竟编程很复杂。
ps: 这篇文章的评论区也挺有意思的
Tip
这周用 Python 做题时发现有两种写法对性能影响很大 :(
n**2 or n*n
在二分法的实现中，后者比前者的执行时间少了48%左右。
n == int(n) or n.is_integer()
这两个相比，虽然没有上述 n*n 效率提升的那么明显，但是后者还是会快一些。
以上都是基于 LeetCode’s Runtime 得出的结论。
Share
这周分享了一篇小水文：Swift: weak 的 strong 时机