16. 3Sum Closest
Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
For example, given array S = {-1 2 1 -4}, and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
實(shí)現(xiàn)思路
先確定一個(gè)數(shù)弃舒，然后從剩余的部分中由首尾分別選取出兩個(gè)數(shù)來(lái)進(jìn)行比較,但要注意的是过椎，這道題不能像上道題一樣過(guò)濾掉重復(fù)的元素骇两，因?yàn)檫@里重復(fù)的元素也是可以累加的恶迈。
實(shí)現(xiàn)代碼
public class Solution {
//實(shí)現(xiàn)思路：先確定一個(gè)數(shù)齿穗，然后從剩余的部分中由首尾分別選取出兩個(gè)數(shù)來(lái)進(jìn)行比較
public int threeSumClosest(int[] nums, int target) {
//先設(shè)置rs的初始值
int rs = nums[0] + nums[1] + nums[2];
Arrays.sort(nums);
for (int i = 0; i < nums.length - 2; i ++){
int lo = i + 1;
int hi = nums.length - 1;
int sum;
//進(jìn)行首尾過(guò)濾選出兩個(gè)數(shù)
while (lo < hi){
sum = nums[i] + nums[lo] + nums[hi];
if(sum > target){
hi --;
} else {
lo ++;
}
//更新結(jié)果
if (Math.abs(sum - target) < Math.abs(rs - target)){
rs = sum;
}
}
}
return rs;
}
}
生成布雷碼
在一組數(shù)的編碼中阵难，若任意兩個(gè)相鄰的代碼只有一位二進(jìn)制數(shù)不同舅列， 則稱(chēng)這種編碼為格雷碼(Gray Code)，請(qǐng)編寫(xiě)一個(gè)函數(shù)声滥，使用遞歸的方法生成N位的格雷碼眉撵。
給定一個(gè)整數(shù)n，請(qǐng)返回n位的格雷碼落塑，順序?yàn)閺?開(kāi)始纽疟。
測(cè)試樣例
1
返回：["0","1"]
實(shí)現(xiàn)思路
使用遞歸方法解決：n位gray碼是由n-1位gray碼生成，比如：求n=3的gray碼憾赁，首先知道n=2的gray碼是(00,01,11,10)污朽。那么n=3的gray碼其實(shí)就是對(duì)n=2的gray碼首位添加0或1生成的，添加0后變成(000,001,011,010)缠沈，添加1后需要順序反向就變成(110,111,101,100)膘壶，組合在一起就是(000,001,011,010,110,111,101,100)错蝴。
實(shí)現(xiàn)代碼
import java.util.*;
public class GrayCode {
public String[] getGray(int n) {
// write code here
String[] rs = null;
//n為1時(shí)洲愤，直接返回該結(jié)果
if (n == 1){
return new String[]{"0","1"};
} else {
//獲取前面所生成的gray碼
String[] tmp = getGray(n-1);
rs = new String[2*tmp.length];
//通過(guò)添加0和1來(lái)增加新的碼
for (int i = 0; i < tmp.length; i ++){
rs[i] = "0" + tmp[i];
rs[rs.length-1-i] = "1" + tmp[i];
}
}
return rs;
}
}
