leetcode水题(一)
Two Sum 1
public int[] twoSum(int[] numbers,int target){
Map<Integer,Integer> map = new HashMap<Integer,Integer>();
for(int i=0;i<numbers.length;i++){
int num = numbers[i];
if(map.containsKey(target-num)){
return new int[]{map.get(num)+1,i+1};
}
map.put(num, i);
}
throw new IllegalArgumentException("No two sum solution");
}
首先，暴力解法也就是遍历数组中的每个数字，在数组中寻找target-当前数字，显然时间复杂度比较高，这是一个O(n²)的算法，而在上述代码中我们使用了一个map以O(n)的空间换时间，由于map的put和contains都是O(1)复杂度的操作，算法的时间复杂度为O(n)。
Two Sum 2
题目2和题目1类似，只是在这里input是一个有序的数组，当然我们可以采用题目1的解法，只是貌似没有利用上有序这个条件。
那么谈到有序数组，最常用的算法包括二分查找和双指针法。
public int[] twoSum2(int[] numbers,int target){
int l = 0, r = numbers.length - 1;
while(l<r){
int num = numbers[l] + numbers[r];
if(num<target){
l++;
} else if(num>target){
r--;
} else {
return new int[]{l+1,r+1};
}
}
throw new IllegalArgumentException("no solution");
}
首先是双指针法，很直观的想法，我们用两个指针向数组中间移动，如果当前指向的两数之和num小于给定数字target,我们就将左指针向右移动一位，如果两数之和大于给定数字，就将右指针向左移动一位，直至与给定数字相等。
public int[] twoSum3(int[] numbers,int target){
for(int i=0;i<numbers.length;i++){
int targetNum = target - numbers[i];
int j = binarySearch(numbers,targetNum,i+1);
if(j!=-1){
return new int[]{i+1,j+1};
}
}
return numbers;
}
public int binarySearch(int[] numbers,int key,int begin){
int l = 0,r = numbers.length-1;
while(l<r){
int midum = (l+r)>>>1;
if(numbers[midum]<key){
l = midum+1;
} else if(numbers[midum]>key){
r = midum;
} else {
return midum;
}
}
return -1;
}
二分法这里稍显复杂，但与前面的思路类似，我们遍历给定数组中的每个数字，计算出目标数字与给定数字的差，并使用二分法在剩余数组中查找该值，二分法的时间复杂度为
O(log n),故算法整体复杂度为O(nlogn)。
Two Sum3
该题目是让我们设计一个数据结构，支持add 和find操作，add操作很简单，即将数字加入当前数据结构中，find操作为在数据结构中找到两数字，其和为给定数字。
显然，这样的题目最简单的做法就是将add进来的所有数字一一求和，并存储在一个哈希表里面，这样在find操作执行时就能以O(1)的时间复杂度直接返回结果，这样的
算法并不是不好，相反，在一个‘读多写少’的场景下，这样的算法很有用。
另外一个想法是在每一个add操作执行时找到当前插入元素‘应该插入的位置’，这里我们利用了插入排序的思想，即保证了我们数据结构中的数字始终是有序状态的，这样，在
find操作执行时，由于数组有序，可以使用双指针法找到结果值。
最后一个方法使用一个HashMap存储，在这里不得不感叹Map的通用性，主要因为在很多算法中，我们都需要‘以空间换时间’，而Map操作的复杂度又很低，故深受众多码农
朋友青睐。
待续。。。。
参考资料:
1.leetcode
2. clean code handbook
最新文章
- pure virtual function call
- 处理数组的forEach map filter的兼容性
- Java实验四和实验五
- 第20章 DLL高级技术（3）
- July 15th, Week 29th Friday, 2016
- poi 读取 excel（.xlsx） 2007及以上版本
- WLS_Oracle Weblogic管理概述（概念）
- 10款很酷的HTML5动画和实用的HTML5应用
- Oracle SQL 劈开字符串
- IE 浏览器下 button元素自动触发click？
- Simple screenshot that explains the non-static invocation.
- 写一个将当前页面 URL 中的 get 参数解析成一个对象的方法。
- android File文件的读写操作
- 取distinct数据同时还取其他字段
- AD域中添加了一个策略导致的问题
- J2EE进阶(十九)FileNotFoundException: http://hibernate.org/dtd/hibernate-mapping-3.0.dtd
- Redis入门到高可用（二）—— Redis启动及使用
- vue之介绍
- kettle中源和目标表结构不一致的情况处理
- OpenCV 机器学习之 支持向量机的使用方法实例