【leetcode】两数之和
2024-08-25 17:02:27
https://leetcode.com/problems/two-sum/
Example:
Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
Java：
版本1，暴力搜索（减少了部分搜索），预计打败全世界30%的答案。
public int[] twoSum(int[] nums, int target) {
int size = nums.length;
int size2 = size - 1;
for (int i=0; i<size2; i++) {
for (int j=i+1; j<size; j++) {
if ((nums[i] + nums[j]) == target) {
int[] pair = new int[2];
pair[0] = i;
pair[1] = j;
return pair;
}
}
}
int[] pair = new int[2];
return pair;
}
版本2，,通过HashMap解决循环匹配问题，预计打败全世界50%
HashMap<Integer, Integer> mm = new HashMap<Integer, Integer>();
int size = nums.length;
for (int i=0; i<size; i++) {
mm.put(nums[i], i);
}
Integer tmp = 0;
Integer v= 0;
for (int i=0; i<size; i++) {
tmp= target - nums[i];
v = mm.get(tmp);
if (v != null && v.intValue()!=i) {
int[] pair = new int[2];
pair[0] = i;
pair[1] = v;
return pair;
}
}
int[] pair = new int[2];
return pair;
版本3, 写到版本2的时候，肯定会想到把循环合并到一起执行，预计打败全世界58%。
HashMap<Integer, Integer> mm = new HashMap<Integer, Integer>();
int size = nums.length;
Integer tmp = 0;
Integer v= 0;
mm.put(nums[0], 0); for (int i=1; i<size; i++) {
tmp= target - nums[i];
v = mm.get(tmp);
if (v != null) {
int[] pair = new int[2];
pair[0] = i;
pair[1] = v;
return pair;
}
mm.put(nums[i], i);
} int[] pair = new int[2];
return pair;
版本4. 上面的代码已经不知道怎么优化，那么就减少int和Integer的转换吧,自己定制了一个IntHashMap，开始打败了68%，后面优化了hash的处理，提升到79%。
static final int MISSIDX = -1;
public int[] twoSum(int[] nums, int target) {
IntHashMap mm = new IntHashMap();
int size = nums.length;
int tmp = 0;
int v = 0;
mm.put(nums[0], 0);
for (int i = 1; i < size; i++) {
tmp = target - nums[i];
v = mm.get(tmp);
if (v != MISSIDX) {
int[] pair = new int[2];
if (tmp == nums[i]) {
pair[0] = v;
pair[1] = i;
} else {
pair[0] = i;
pair[1] = v;
}
return pair;
}
mm.put(nums[i], i);
} int[] pair = new int[2];
return pair;
} static class IntHashMap {
public static final int DEFAULT_INITIAL_CAPACITY = 16;
public static final int MAXIMUM_CAPACITY = 1073741824;
public static final float DEFAULT_LOAD_FACTOR = 0.75F;
private transient IntEntry[] table;
private transient int size;
private int threshold;
private final float loadFactor; public IntHashMap(int initialCapacity) {
this.loadFactor = 0.75F;
int capacity = 1;
while (capacity < initialCapacity) {
capacity <<= 1;
}
this.threshold = ((int)(capacity * loadFactor));
this.table = new IntEntry[capacity];
} public IntHashMap() {
this.loadFactor = 0.75F;
this.threshold = 12;
this.table = new IntEntry[16];
} protected int indexFor(int key, int length) {
return key & length - 1;
} public int get(int key) {
int i = indexFor(key, this.table.length);
IntEntry e = this.table[i];
while (true) {
if (e == null)
return MISSIDX;
if (e.key == key)
return e.value;
e = e.next;
}
} public void put(int key, int value) {
int i = indexFor(key, this.table.length);
addEntry(key, value, i);
} private void addEntry(int key, int value, int bucketIndex) {
IntEntry e = this.table[bucketIndex];
this.table[bucketIndex] = new IntEntry(key, value, e);
if (this.size++ >= this.threshold)
resize(2 * this.table.length);
} protected void resize(int newCapacity) {
IntEntry[] oldTable = this.table;
int oldCapacity = oldTable.length;
if (oldCapacity == 1073741824) {
this.threshold = 2147483647;
return;
} IntEntry[] newTable = new IntEntry[newCapacity];
transfer(newTable);
this.table = newTable;
this.threshold = ((int) (newCapacity * this.loadFactor));
} private void transfer(IntEntry[] newTable) {
IntEntry[] src = this.table;
int newCapacity = newTable.length;
for (int j = 0; j < src.length; j++) {
IntEntry e = src[j];
if (e != null) {
src[j] = null;
do {
IntEntry next = e.next;
int i = indexFor(e.key, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
} while (e != null);
}
}
} public String toString() {
return Arrays.deepToString(this.table);
}
} static class IntEntry {
protected final int key;
protected int value;
protected IntEntry next; protected IntEntry(int k, int v, IntEntry n) {
this.value = v;
this.next = n;
this.key = k;
} public int getKey() {
return this.key;
} public int getValue() {
return this.value;
} public void setValue(int newValue) {
this.value = newValue;
} public boolean equals(Object o) {
if (!(o instanceof IntEntry))
return false;
IntEntry e = (IntEntry) o;
int eKey = e.getKey();
int eVal = e.getValue();
if (eKey == getKey()) {
return eVal == MISSIDX ? false : getValue() == MISSIDX ? true
: eVal == getValue();
}
return false;
} public int hashCode() {
return this.key ^ (this.value == MISSIDX ? 0 : value);
} public String toString() {
return "[" + key + "," + value + "]";
}
}
版本5. hashMap这个方向看来是尽头了，那用稀疏数组吧，貌似打败了87.62%
static final int MISSIDX = -1;
public int[] twoSum_0_4(int[] nums, int target) {
SparseIntArray mm = new SparseIntArray();
int size = nums.length;
int tmp = 0;
int v = 0;
mm.put(nums[0], 0);
for (int i = 1; i < size; i++) {
tmp = target - nums[i];
v = mm.get(tmp);
if (v != MISSIDX) {
int[] pair = new int[2];
if (tmp == nums[i]) {
pair[0] = v;
pair[1] = i;
} else {
pair[0] = i;
pair[1] = v;
}
return pair;
}
mm.put(nums[i], i);
} int[] pair = new int[2];
return pair;
} static final int[] EMPTY_INTS = new int[0];
static int idealByteArraySize(int need) {
for (int i = 4; i < 32; i++)
if (need <= (1 << i) - 12)
return (1 << i) - 12; return need;
}
static int idealIntArraySize(int need) {
return idealByteArraySize(need * 4) / 4;
}
static int binarySearch(int[] array, int size, int value) {
int lo = 0;
int hi = size - 1; while (lo <= hi) {
final int mid = (lo + hi) >>> 1;
final int midVal = array[mid]; if (midVal < value) {
lo = mid + 1;
} else if (midVal > value) {
hi = mid - 1;
} else {
return mid; // value found
}
}
return ~lo; // value not present
}
static class SparseIntArray {
private int[] mKeys;
private int[] mValues;
private int mSize;
public SparseIntArray() {
this(10);
}
public SparseIntArray(int initialCapacity) {
initialCapacity = idealIntArraySize(initialCapacity);
mKeys = new int[initialCapacity];
mValues = new int[initialCapacity];
mSize = 0;
}
public int get(int key) {
return get(key, MISSIDX);
}
public int get(int key, int valueIfKeyNotFound) {
int i = binarySearch(mKeys, mSize, key); if (i < 0) {
return valueIfKeyNotFound;
} else {
return mValues[i];
}
}
public void put(int key, int value) {
int i = binarySearch(mKeys, mSize, key); if (i >= 0) {
mValues[i] = value;
} else {
i = ~i; if (mSize >= mKeys.length) {
int n = idealIntArraySize(mSize + 1); int[] nkeys = new int[n];
int[] nvalues = new int[n]; System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length);
System.arraycopy(mValues, 0, nvalues, 0, mValues.length); mKeys = nkeys;
mValues = nvalues;
} if (mSize - i != 0) {
System.arraycopy(mKeys, i, mKeys, i + 1, mSize - i);
System.arraycopy(mValues, i, mValues, i + 1, mSize - i);
} mKeys[i] = key;
mValues[i] = value;
mSize++;
}
} public String toString() {
if (mSize <= 0) {
return "{}";
} StringBuilder buffer = new StringBuilder(mSize * 28);
buffer.append('{');
for (int i=0; i<mSize; i++) {
if (i > 0) {
buffer.append(", ");
}
int key = mKeys[i];
buffer.append(key);
buffer.append('=');
int value = mValues[i];
buffer.append(value);
}
buffer.append('}');
return buffer.toString();
}
}
最新文章
- MySQL架构优化实战系列1：数据类型与索引调优全解析
- java读取文件之txt文本
- 丰富自己的代码库-SqlServerHelper(Ado)
- HDU 2072 单词数
- MFC中树控件CTreeCtrl的用法
- hbulider 快捷键以及常用
- 后缀自动机（SAM）
- 什么是dtd文件，为什么需要dtd
- Webstorm less watcher 配置
- 利用JS去做响应式布局
- python--第十二天总结（Python操作 RabbitMQ、Redis、Memcache、SQLAlchemy）
- Maven聚合工程的使用
- 玩树莓派(raspberry pi) 2/3 raspbian的遇到的一些问题
- [daily][pcaman] pacman滚动升级跳过指定包
- 关于Lambda
- Maltego——互联网情报聚合工具初探（转）
- pycharm最常用的快捷键总结
- 解决方案，org.hibernate.LazyInitializationException: could not initialize proxy - no Session
- 利用机器学习实现微信小程序-加减大师自动答题
- Spring Data MongoDB 三：基本文档查询（Query、BasicQuery