中文博客

刷题进行时

2018年1月2日 · tech

赶在Master的尾巴前开始刷题吧！

• algorithm
• computer science

又过去了一个学期。在这个本应该是第一个学期的第二个学期期间，自己从头上了一边Data Science的各项基础课，包括算法，概率论和统计推断，却一直没有在刷题上下功夫。新年新气象，2018年就从刷题开始好了。

准备工作

LeetCode的账号早就申请好了，自己也曾经考虑报一个九章算法的课程系统刷题，不过最后都胎死腹中。打开LeetCode的网站，初步目标是将Easy先行刷一遍，当遇到问题或者觉得刷不下去之后考虑上一个九章算法的培训班。

Reference

这里是复习记录，遇到问题和有想法的时候会在这里更新。

Week 1: 1/1/2018 - 1/7/2018

1. Two Sum （约用时1.5h）

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

问题

• 没有一个明确和清晰的分析方法，知道naive algorithm能实现O(n^2),也知道应该存在O(n)的算法，不过不能具体跟之前课上学到的对应起来。
• 知道应该用hash table之后还去查了Python中的hash table，结果发现直接用dict就可以完成，对于python的库已经忘记的差不多了，需要从头过一遍。
• 具体逻辑上推了3遍才出来，逻辑不够清晰，还是得熟能生巧。
• 逻辑跑通了之后没有handle edge case: 第一个test case[3,2,4],6就是没有考虑3不可以重复出现。
• 用了简单粗暴的方法直接筛掉所有的target/2之后发现nums是可以重复的。[3,3], 6就是，自己在建立dict的时候没有考虑重复的情况倒是return null。
• 之后又用了个愚蠢的方法每次都重新建立一个sub-dict把当前的element删掉，在测试最后一个test case的时候RT没有过。
• 最后决定在最前面判断edge case：如果nums存在2个一样的element且值为target/2，则直接return 这两个element的index，如果不是的话进入for loop判断。

感悟

• 自己还是太naive，掉入了几乎所有的陷阱T_T 考虑问题的时候首先找到切入点（数据结构是怎样的，RT最好大概能到多少，为了达到最佳RT需要怎么设计Data Structure和Algorithm），然后把基本代码写出来，最后考虑edge case和hidden case。
• 自己的方法是一次性将所有的element加入到dict中，可能会导致edge case的出现。如果每一步加一次的话可以有效避免。

附录：最终的code

class Solution:
    def twoSum(self, nums, target):
        my_dict = {item:index for index,item in enumerate(nums)} # Create dict with item:index key-pair.
        if target % 2 == 0 and nums.count(target/2) == 2: # Edge case: two identical elements with target/2 value?
            return [i for i,val in enumerate(nums) if val==target/2] # return list of indexes. See reference
        else:
            for index, item in enumerate(nums): # for all elements in the list, O(n) RT 
                seek_number = target-nums[index] # Get the seek number
                if seek_number != target/2 and seek_number in my_dict: # avoid the edge case
                    return [index, my_dict[seek_number]]
                    break

(后续内容已省略，仅作为迁移示例)