Dimple在左耳听风ARTS打卡（第八期）

程序员小跃

发布于 2019-12-25 17:27:02

2470

发布于 2019-12-25 17:27:02

文章被收录于专栏：程序员小跃程序员小跃程序员小跃

所谓ARTS：每周至少做一个LeetCode的算法题；阅读并点评至少一篇英文技术文章；学习至少一个技术技巧；分享一篇有观点和思考的技术文章。（也就是Algorithm、Review、Tip、Share 简称ARTS）这是第八期打卡。

Algorithm LeetCode算法

删除排序数组中的重复项 (https://leetcode.com/problems/remove-duplicates-from-sorted-array/)

题目描述：给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

示例 1：

给定数组 nums = [1,1,2], 

函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。 

你不需要考虑数组中超出新长度后面的元素。

示例 2:

给定 nums = [0,0,1,1,1,2,2,3,3,4],

函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。

说明：

为什么返回数值是整数，但输出的答案是数组呢?

请注意，输入数组是以“引用”方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

拿到算法题，真的得好好考虑考虑边界问题，以及一定要仔细审题，仔细审题，仔细审题，重要的事情说三遍。小编一开始很兴奋，看到这题的时候，三下五除二就想到了用Map来做，毕竟key是可以冲掉相同的，最后得出的结果就是数量啦。请看我第一次的代码：

public int removeDuplicates(int[] nums) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i : nums) {
        map.put(i, i);
    }
    return map.size();
}

看到这你们笑哭有没有，我这样做只是做出了数量，但是没有改变nums数组的结构，所以很遗憾，肯定是各种GG咯，大大的“Wrong Answer”送给我。差点爆粗口。

没办法，还是继续深挖题目，才看到题目的最后一段温馨提示，不能改变数组结构，必须在原地修改。此时看到这题，其实就是把重复的数字用后面不重复的替换掉，后面的数据不用管了，因为系统会自动检测你提供的重复数字的长度来获取答案。

思路很清晰了有木有，你都没必要考虑后面的情形，只需要通过你的算法把重复的数字填充即可。哇咔咔，恍然大悟。接下来就是考验算法功力的时候了，小编这里经过很多种实验，最后把最优解拿出来和大家共享。

解题之后，我看了下别人的思路，才有了这个最优解，不然又是各种循环，各种遍历了。或许，这就是算法题的魅力所在吧，题目谁都能解，就看你用什么办法，来达到最优路径。就如同我们写程序一样，功能谁都可以写，就看你怎么写出一个性能更好的功能来面对线上意想不到的压力。

做算法题我也能得出各种心得，给自己送一颗小星星鼓励下吧。如果你能悟出其他的道理，告诉小编，小编给你加鸡腿。

public static int removeDuplicates(int[] nums) {
    int i = 0;
    for (int n : nums) {
        int x = i - 1;
        if (i < 1 || n != nums[x]) {
            int j = i++;
            nums[j] = n;
        }

    }
    return i;
}

Review 阅读并点评至少一篇英文文章

Google I/O 2019 (https://www.androidauthority.com/google-io/)

上周即5.7--5.9号，Google开启了一年一度的I/O大会，这又是开发者的一次盛会，国内很多新闻都第一时间报道，尤其是混迹我们IT圈子，消息更是灵通。

什么是Google I/O大会呢？开篇就给我们介绍了，这是Google一年一度的开发者大会，谷歌会宣布其现有应用和服务的新硬件，软件和各种更新。如何观看呢？因为这个大会持续3天，有各种各样的小活动，小讲座等，所以官方会给出keynote的地址，以及视频给我们进行观看。怎么获取门票呢？参加过国内大会的都知道，这是通过官方随机获取的，小编去年报名了，就是没中。他这个大会也是随机的，不过中了的朋友，还是需要支付门票的哦。

小编之前知道这个大会，是因为学习Android，所以会经常关心这块。这篇文章，也主要讲了Android相关的新品。

众所周知，现在Android设备和iOS设备，是智能手机的两大霸主，所以这次大会，又更新了Android Q Beta 3版本，这也是一年一度的惯例了，都会把最新系统展示出来。还有以前的Google亲儿子的手机都是代工的，最近开启了自己的模式，重新命名为pixel系列。这次发布了Google Pixel 3a和 Pixel 3a XL手机，感兴趣的朋友，可以通过渠道获取哦。小编同学以前用过亲儿子，确实还不错的。

以前多多少少听过百度的自动驾驶，Google也在搞，而且技术还是很牛逼的样子，这次大会也有介绍，Android Automotive OS。从这篇文章来看，只是大致写了部分，其实还有很多其他的关于开发者相关的。比如Google已经支持Kotlin作为Android的第一语言，Google宣布Flutter将会支持Web，并且还会支持macOS、Windows and Linux，这是迈向跨平台的又一大步。

关于开发者大会的内容，请各位自行通过资源去搜索哦。小编在这就将这么多啦。其实还有很多有趣的，吸引我的东西，我争取再找找。