Day3

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).

实现思路

先确定一个数，然后从剩余的部分中由首尾分别选取出两个数来进行比较,但要注意的是，这道题不能像上道题一样过滤掉重复的元素，因为这里重复的元素也是可以累加的。

实现代码

public class Solution {
    //实现思路：先确定一个数，然后从剩余的部分中由首尾分别选取出两个数来进行比较
    public int threeSumClosest(int[] nums, int target) {
        //先设置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;
            //进行首尾过滤选出两个数
            while (lo < hi){
                sum = nums[i] + nums[lo] + nums[hi];
                if(sum > target){
                    hi --;
                } else {
                    lo ++;
                }
                //更新结果
                if (Math.abs(sum - target) < Math.abs(rs - target)){
                    rs = sum;
                }
            }
        }
        
        return rs;
    }
}

生成布雷码

在一组数的编码中，若任意两个相邻的代码只有一位二进制数不同， 则称这种编码为格雷码(Gray Code)，请编写一个函数，使用递归的方法生成N位的格雷码。
给定一个整数n，请返回n位的格雷码，顺序为从0开始。

测试样例

1
返回：["0","1"]

实现思路

使用递归方法解决：n位gray码是由n-1位gray码生成，比如：求n=3的gray码，首先知道n=2的gray码是(00,01,11,10)。那么n=3的gray码其实就是对n=2的gray码首位添加0或1生成的，添加0后变成(000,001,011,010)，添加1后需要顺序反向就变成(110,111,101,100)，组合在一起就是(000,001,011,010,110,111,101,100)。

实现代码

import java.util.*;

public class GrayCode {
    public String[] getGray(int n) {
        // write code here
        String[] rs = null;
        //n为1时，直接返回该结果
        if (n == 1){
            return new String[]{"0","1"};
        } else {
            //获取前面所生成的gray码
            String[] tmp = getGray(n-1);
            rs = new String[2*tmp.length];
            //通过添加0和1来增加新的码
            for (int i = 0; i < tmp.length; i ++){
                rs[i] = "0" + tmp[i];
                rs[rs.length-1-i] = "1" + tmp[i];
            } 
        }
        return rs;
    }
}