LeetCode

做笔记

对于遇到的每个题目,事后都做上标记:普通题目,难题、好题。此外,每个题目都分为以下几个步骤做好详细的笔记:

1. 原题目

2. 自己的第一遍解法

3. 网上好的解法

4. 自己可以改进的地方

5. 进一步精简优化自己的代码直至代码简无可简这是非常关键的一步,到达这一步,才会发现获得能力的提升远远要超过简单地把题目解出来

6. 获得的思考(或者学习到的地方,可以是算法、数据结构或者Java的特性—例如Stream等等)

每一个题目都经过至少一遍这样的迭代。这样几遍下来,我对于每个题目都有了更加深刻的理解,大部分的题目我都有自信能够写出最优解甚至代码都是最优化的(至少比论坛回复里面的最高票答案还要精简)。

 

举个例子,两数之和问题。

我最早的解法是暴力搜索。当时的代码(Java)是这样的:

class Solution {
    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i+1; j < nums.length; j++) {
                if (nums[j] == target - nums[i]) {
                    return new int[]{i, j};
                }
            }
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

 

这个解法不仅复杂度高,而且代码冗长繁琐。

后来看了网上高票答案的解法,知道了用hashmap来做,于是写出了优化的代码(Java):

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer,Integer> map = new HashMap<>();
        int[] res = new int[2];
        for (int i = 0; i < nums.length; i++) {
            int dif = target - nums[i];
            if (map.get(dif) != null) {
                res[0] = map.get(dif);
                res[1] = i;
                return res;
            }
            map.put(nums[i],i);
        }
        return res;
    }
}

 

再后来,对代码进行了一些细节的简化:

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap();
        
        for (int i = 0; i < nums.length; ++i) {
            if (map.containsKey(target- nums[i])) {
                return new int[]{map.get(target- nums[i]), i};
            }
            map.put(nums[i], i);
        }
        return new int[]{-1, -1};
    }
}

 

至此,代码几乎达到最精简状态。(中间有略去几次迭代)总之,不断地学习别人的代码,改进自己的代码,不断地锤炼自己的代码,直至算法最优化,代码最简洁!

潜移默化中,不仅对题目解法有了更深刻的理解(什么是最优解),而且也知道如何用最简洁的代码实现这个最优解。

 

再举个极端的例子吧,179. 最大数,这个题目我最后精简成的代码如下:

public String largestNumber(int[] nums) {

    return Arrays.stream(nums)

    .mapToObj(String::valueOf)

    .sorted((s1, s2) -> (s2 + s1).compareTo(s1 + s2))

    .reduce((s1, s2) -> s1.equals("0") ? s2 : s1 + s2).get();

}

 

我本人不是算法高手,算是勤能补拙类型。这样长期坚持下来,慢慢地感觉自己编程能力提升了很多。不仅面试的时候得心应手,而且在工作中提交code review的时候,往往有自信说自己的代码是简单,干净与优雅的。

 

内容来源于网络如有侵权请私信删除