leetcode两数之和

IT互联网Harries 发表了文章 • 0 个评论 • 21 次浏览 • 2018-08-24 16:51 • 来自相关话题

两数之和

给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。 你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9

所以返回 [0, 1]

解决方案

这道题给了我们一个数组,还有一个目标数target,让我们找到两个数字,使其和为target,乍一看就感觉可以用暴力搜索,但是猜到OJ肯定不会允许用暴力搜索这么简单的方法,于是去试了一下,果然是Time Limit Exceeded,这个算法的时间复杂度是O(n^2)。那么只能想个O(n)的算法来实现,由于暴力搜索的方法是遍历所有的两个数字的组合,然后算其和,这样虽然节省了空间,但是时间复杂度高。一般来说,我们为了提高时间的复杂度,需要用空间来换,这算是一个trade off吧,我们只想用线性的时间复杂度来解决问题,那么就是说只能遍历一个数字,那么另一个数字呢,我们可以事先将其存储起来,使用一个HashMap,来建立数字和其坐标位置之间的映射,我们都知道HashMap是常数级的查找效率,这样,我们在遍历数组的时候,用target减去遍历到的数字,就是另一个需要的数字了,直接在HashMap中查找其是否存在即可,注意要判断查找到的数字不是第一个数字,比如target是4,遍历到了一个2,那么另外一个2不能是之前那个2,整个实现步骤为:先遍历一遍数组,建立HashMap映射,然后再遍历一遍,开始查找,找到则记录index。代码如下

方法一:

public class Solution {

   public int[] twoSum(int[] nums, int target) {

       HashMap<Integer, Integer> m = new HashMap<Integer, Integer>();

       int[] res = new int[2];

       for (int i = 0; i < nums.length; ++i) {

           m.put(nums[i], i);

       }

       for (int i = 0; i < nums.length; ++i) {

           int t = target - nums[i];

           if (m.containsKey(t) && m.get(t) != i) {

               res[0] = i;

               res[1] = m.get(t);

               break;

           }

       }

       return res;

   }

}

方法二

public class Solution {

   public int[] twoSum(int[] nums, int target) {

       HashMap<Integer, Integer> m = new HashMap<Integer, Integer>();

       int[] res = new int[2];

       for (int i = 0; i < nums.length; ++i) {

           if (m.containsKey(target - nums[i])) {

               res[0] = i;

               res[1] = m.get(target - nums[i]);

               break;

           }

           m.put(nums[i], i);

       }

       return res;

   }

} 查看全部
两数之和

给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。 你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9

所以返回 [0, 1]

解决方案

这道题给了我们一个数组,还有一个目标数target,让我们找到两个数字,使其和为target,乍一看就感觉可以用暴力搜索,但是猜到OJ肯定不会允许用暴力搜索这么简单的方法,于是去试了一下,果然是Time Limit Exceeded,这个算法的时间复杂度是O(n^2)。那么只能想个O(n)的算法来实现,由于暴力搜索的方法是遍历所有的两个数字的组合,然后算其和,这样虽然节省了空间,但是时间复杂度高。一般来说,我们为了提高时间的复杂度,需要用空间来换,这算是一个trade off吧,我们只想用线性的时间复杂度来解决问题,那么就是说只能遍历一个数字,那么另一个数字呢,我们可以事先将其存储起来,使用一个HashMap,来建立数字和其坐标位置之间的映射,我们都知道HashMap是常数级的查找效率,这样,我们在遍历数组的时候,用target减去遍历到的数字,就是另一个需要的数字了,直接在HashMap中查找其是否存在即可,注意要判断查找到的数字不是第一个数字,比如target是4,遍历到了一个2,那么另外一个2不能是之前那个2,整个实现步骤为:先遍历一遍数组,建立HashMap映射,然后再遍历一遍,开始查找,找到则记录index。代码如下

方法一:

public class Solution {

   public int[] twoSum(int[] nums, int target) {

       HashMap<Integer, Integer> m = new HashMap<Integer, Integer>();

       int[] res = new int[2];

       for (int i = 0; i < nums.length; ++i) {

           m.put(nums[i], i);

       }

       for (int i = 0; i < nums.length; ++i) {

           int t = target - nums[i];

           if (m.containsKey(t) && m.get(t) != i) {

               res[0] = i;

               res[1] = m.get(t);

               break;

           }

       }

       return res;

   }

}

方法二

public class Solution {

   public int[] twoSum(int[] nums, int target) {

       HashMap<Integer, Integer> m = new HashMap<Integer, Integer>();

       int[] res = new int[2];

       for (int i = 0; i < nums.length; ++i) {

           if (m.containsKey(target - nums[i])) {

               res[0] = i;

               res[1] = m.get(target - nums[i]);

               break;

           }

           m.put(nums[i], i);

       }

       return res;

   }

}

linux利用grep查看打印匹配的下几行或前后几行的命令

IT互联网Harries 发表了文章 • 0 个评论 • 77 次浏览 • 2018-05-25 11:25 • 来自相关话题

linux系统中,利用grep打印匹配的上下几行 
如果在只是想匹配模式的上下几行,grep可以实现。
 
$grep -5 'parttern' inputfile //打印匹配行的前后5行
 
$grep -C 5 'parttern' inputfile //打印匹配行的前后5行
 
$grep -A 5 'parttern' inputfile //打印匹配行的后5行
 
$grep -B 5 'parttern' inputfile //打印匹配行的前5行
  查看全部
linux系统中,利用grep打印匹配的上下几行 
如果在只是想匹配模式的上下几行,grep可以实现。
 
$grep -5 'parttern' inputfile //打印匹配行的前后5行
 
$grep -C 5 'parttern' inputfile //打印匹配行的前后5行
 
$grep -A 5 'parttern' inputfile //打印匹配行的后5行
 
$grep -B 5 'parttern' inputfile //打印匹配行的前5行
 

什么情况会出现yong GC?

回复

IT互联网Ask 发起了问题 • 1 人关注 • 0 个回复 • 103 次浏览 • 2018-04-24 15:12 • 来自相关话题

什么情况会出现Full GC

回复

IT互联网Ask 发起了问题 • 1 人关注 • 0 个回复 • 87 次浏览 • 2018-04-24 15:12 • 来自相关话题

如何做到不停服务24小时发布服务

IT互联网Ask 发表了文章 • 0 个评论 • 59 次浏览 • 2018-04-20 14:09 • 来自相关话题

央行下调存款准备金率的影响?

财经Ask 发表了文章 • 0 个评论 • 64 次浏览 • 2018-04-18 11:30 • 来自相关话题

下调存款准备金率时间:

从2015年4月开始,央行开始下调金融机构的人民币存款准备金率,下调幅度达到了0.5%,接着又继续连续下调了人民币存款准备金率一个百分点。时间到了2017年,央行存款准备金率又有了一些新的变化。 根据目前所公布的数据可以看出,对于大型的金融机构来说,调整之后的央行存款准备金率为18.5%,相比调整前的19.5%来说,下降了一个百分点;对于中小金融机构来说,调整之后的央行存款准备金率为15%,相比较调整前的16%来说,下降了一个百分点。而下调存款准备金率,就可以进一步地影响到金融机构的信贷能力。

什么是存款准备金率?

首先提到存款准备金率就不得不提存款准备金,存款准备金是什么意思呢?其实就是金融机构将用户的存款的一部分交给中央银行,这么做的作用是为了保证金融机构有足够的钱来满足用户的存款提款和结算的要求,而金融机构的存款准备金额占其存款总额的比例就是存款准备金率。由此可见下调存款准备金率影响到金融机构的信贷能力和扩张能力,从而也可以间接地影响到货币的供应量。那么下调存款准备金率影响具体有哪些呢?

下调存款准备金率影响:

1.下调存款准备金率影响理财收益率:会直接导致理财可投资资产的减少和资产收益率的下降,反过来会倒逼银行理财收益率的下降。从过去两次降准的经验看,在降准启动3个月之后的银行理财收益率会出现显着下降,1年平均降幅在1%左右。

2.下调存款准备金率影响股市:下调存款准备金率对于股市是重大利好,股市近期会出现高开,但应提防低走,以免追高低走套牢。

3.下调存款准备金率影响楼市:对于购房者来说,由于银行资金充裕,会有更多的钱可以贷出,购房压力会有一定的降低,所以小编在这提醒买房的朋友如果继续观望的话可能会错过购房时机和购房成本,这是应积极入市 查看全部
下调存款准备金率时间:

从2015年4月开始,央行开始下调金融机构的人民币存款准备金率,下调幅度达到了0.5%,接着又继续连续下调了人民币存款准备金率一个百分点。时间到了2017年,央行存款准备金率又有了一些新的变化。 根据目前所公布的数据可以看出,对于大型的金融机构来说,调整之后的央行存款准备金率为18.5%,相比调整前的19.5%来说,下降了一个百分点;对于中小金融机构来说,调整之后的央行存款准备金率为15%,相比较调整前的16%来说,下降了一个百分点。而下调存款准备金率,就可以进一步地影响到金融机构的信贷能力。

什么是存款准备金率?

首先提到存款准备金率就不得不提存款准备金,存款准备金是什么意思呢?其实就是金融机构将用户的存款的一部分交给中央银行,这么做的作用是为了保证金融机构有足够的钱来满足用户的存款提款和结算的要求,而金融机构的存款准备金额占其存款总额的比例就是存款准备金率。由此可见下调存款准备金率影响到金融机构的信贷能力和扩张能力,从而也可以间接地影响到货币的供应量。那么下调存款准备金率影响具体有哪些呢?

下调存款准备金率影响:

1.下调存款准备金率影响理财收益率:会直接导致理财可投资资产的减少和资产收益率的下降,反过来会倒逼银行理财收益率的下降。从过去两次降准的经验看,在降准启动3个月之后的银行理财收益率会出现显着下降,1年平均降幅在1%左右。

2.下调存款准备金率影响股市:下调存款准备金率对于股市是重大利好,股市近期会出现高开,但应提防低走,以免追高低走套牢。

3.下调存款准备金率影响楼市:对于购房者来说,由于银行资金充裕,会有更多的钱可以贷出,购房压力会有一定的降低,所以小编在这提醒买房的朋友如果继续观望的话可能会错过购房时机和购房成本,这是应积极入市

TMT是什么意思?

回复

IT互联网Ask 发起了问题 • 1 人关注 • 0 个回复 • 96 次浏览 • 2018-04-17 22:02 • 来自相关话题

为什么树能活几百年?

生活见闻Ask 发表了文章 • 0 个评论 • 124 次浏览 • 2018-04-17 15:25 • 来自相关话题

qq如何修改密保邮箱?

生活见闻Ask 发表了文章 • 0 个评论 • 64 次浏览 • 2018-04-17 15:25 • 来自相关话题

第一步、进入QQ安全中心,可以百度一下QQ安全中心进入;

第二步、登录你的QQ帐号以及密码;

第三步、在右上角有一个站点地图,鼠标移过去,会出现一个下拉框;

第四步、在最后一行找到个人资料并点击进去;

第五步、点击修改你的邮箱就OK啦
第一步、进入QQ安全中心,可以百度一下QQ安全中心进入;

第二步、登录你的QQ帐号以及密码;

第三步、在右上角有一个站点地图,鼠标移过去,会出现一个下拉框;

第四步、在最后一行找到个人资料并点击进去;

第五步、点击修改你的邮箱就OK啦

很多开发者都有创业的想法,那么如果给你 100 万用来创业,你会去做什么呢?

回复

IT互联网Harries 发起了问题 • 1 人关注 • 0 个回复 • 118 次浏览 • 2018-04-08 16:22 • 来自相关话题