算法,两数之和

问题来源:two sum

问题描述

给定一个整数数组,返回两个数字的索引,使它们相加到一个特定的目标。 您可以假设每个输入都只有一个解决方案, 而您可能不会使用相同的元素两次。

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

正向思维解法

直接遍历所有的组合,求出问题的解

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 (target == nums[j] + nums[i]) {
                        return new int[] { i, j };
                    }
         }
    }
    throw new IllegalArgumentException("No two sum solution");
}

分析:
这是最简单的解法。两个嵌套循环,时间复杂度为O(n2)。空间复杂度为O(1)

逆向思维解法

用目标减去加数1,得到加数2,再在数组中寻找。

实现1

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 (target - nums[i] == nums[i]) {
                    return new int[] { i, j };
                }
            }
        }
        throw new IllegalArgumentException("No two sum solution");
    }

分析
没错,就是和第一解法时间空间复杂度都是一样的😂。没事,我们可以优化一下的。

实现2

在实现一中,我们的瓶颈主要是在如何根据值去找到索引的问题上,所以这里我们使用Map去优化根据值去寻找位置的瓶颈

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        map.put(nums[i], i);
    }
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement) && map.get(complement) != i) {
            return new int[] { i, map.get(complement) };
        }
    }
    throw new IllegalArgumentException("No two sum solution");
}

分析:
我们使用一个循环把数据与位置建立索引,然后获取的时候直接从map中直接获取,这样就可以避免了两个嵌套的循环了,是的时间复杂度为O(n) ,空间复杂度为O(1).

note: 在算法中,我们不考虑map这些数据结构具体实现使用的时间

实现3

实现2中使用了两个循环,能不能把第一个循环也去掉呢?答案是可以的。一边循环,一边插入map,然后获取这个差值是否已经加入到map中。

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement)) {
            return new int[] { map.get(complement), i };
        }
        map.put(nums[i], i);
    }
    throw new IllegalArgumentException("No two sum solution");
}

分析:
这个复杂度和实现2是一样的,时间为O(n),空间为O(n),但细看还是有差别的,这个算法的实际上比实现2的快了1倍

Android Studio 3.0 Beta1 更新日志

翻译自谷歌博客

2017年8月9日,星期三

Android Studio 3.0 Beta 1现在可以在金丝雀和开发渠道中使用。

已知问题

如果您现有的Android Studio项目使用的是Android插件3.0.0的Alpha版本(如3.0.0-alpha9),则迁移到Android 3.0.0-beta1后sync your project将会遇到: Gradle project refresh failed

解决此问题的办法就是从菜单栏中选择 Build> Clean Project - 您只需对每个项目执行一次此操作。然后,您可以通过从工具栏中单击“ Sync Project ” ,将其与Gradle对应。

此版本包含各种错误修复,包括以下内容:

修复了使用Kotlin插件崩溃的类加载问题。
修复了菜单栏不再显示的问题。(问题#63743086

如何合法的修改Git子模块远端

首先直接修改根目录下的.gitmoudule 文件

[submodule "libraries/GaiaLibrary4BLE"]
    path = libraries/GaiaLibrary4BLE
    url = http://yousumodule_remote

然后同步设置

使用一下命令把设置同步到.git/config 文件中

git submodule synca

最后更新远端信息

使用以下命令更新远端信息

git submodule update --init --recursive --remote

其实就是从远端递归式的初始化的意思

JobScheduler 使用指南

什么是JobScheduler?

JobScheduler 是Android 5.0之后提供的后台执行操作的API。简单点描述就是可以根据一系列条件,目前包括,时间,是否在充电,ContentProvider 是否改变等条件触发工作。这是和AlarmManager最大的区别,AlarmManager 只能在一个时间启动,不能根据机子时间启动。

会在什么情况下使用呢?

  • 用户拍了一张照片的时候需要触发相应的操作,这个时候就可以监听照片的ContentProvider ,发生改变就能触发我的操作。当然,这个同样适用于所有ContentProvider
  • 固定时间唤醒进行响应的操作
  • 需要设备空闲的时候进行图片的OCR识别保存信息
  • 需要设备空闲而且在充电的时候并且连接着WIFI的时候才能图片上传到服务器

继续阅读“JobScheduler 使用指南”