算法之美——数组和数

作者: 康凯森

日期: 2016-11-19

分类: 算法

single-number 落单的数

原题 给出2*n + 1 个的数字，除其中一个数字之外其他每个数字均出现两次，找到这个数字。

思路

一个数与自身异或的结果为0

java代码

public class Solution {
    /**
     *@param A : an integer array
     *return : a integer 
     */
    public int singleNumber(int[] A) {
        if (A.length == 0) {
            return 0;
        }

        int n = A[0];
        for(int i = 1; i < A.length; i++) {
            n = n ^ A[i];
        }

        return n;
    }
}

single-number-ii 落单的数 II

原题 给出3*n + 1 个的数字，除其中一个数字之外其他每个数字均出现三次，找到这个数字。

思路

若一个数字出现3次，则该数字的二进制表示中每个位置的数值为1的出现次数为3次，如：5的二进制表示为101，若5出现3次，则其二进制表示中的第一个位置和第二个位置出现1的次数和均为3。那么对该位1出现的次数对3取余，最终的结果所对应的就是所要求的Sing Number。

对int的32bit的各个位中1出现的次数，对数组中所有元素逐个进行统计，然后每个bit对3取余，最终的结果就是只出现一次的数字。

java代码

public class Solution {
    /**
     * @param A : An integer array
     * @return : An integer 
     */
    public int singleNumberII(int[] A) {
        if (A == null || A.length == 0) {
            return -1;
        }
        int result = 0;
        int[] bits = new int[32];
        for (int i = 0;i < 32;i++) {
            for(int j = 0;j < A.length;j++){
                bits[i] += A[j] >> i & 1;
                bits[i] = bits[i] % 3;
            }
            result = result | (bits[i] << i);  
        }
        return result;
    }
}

single-number-iii

原题 给出2*n + 2个的数字，除其中两个数字之外其他每个数字均出现两次，找到这两个数字。

思路

一个数与自身异或的结果为0。

如果对所有元素进行异或操作，最后剩余的结果是出现次数为1次的两个数的异或结果，此时无法直接得到这两个数具体的值。但是，因为这两个数一定是不同的，所以最终异或的值至少有一个位为1。我们可以找出异或结果中第一个值为1的位，然后根据该位的值是否为1，将数组中的每一个数，分成两个部分。这样每个部分，就可以采用Singal numberI中的方法得到只出现一次的数。

java代码

public class Solution {
    /**
     * @param A : An integer array
     * @return : Two integers
     */
    int findFirstBit1(int num) {
        int index = 0;
        while((num & 1) == 0) {
            ++index;
            num >>= 1;
        }
        return index;
    }

    boolean isBit1(int num, int index) {
        num = num >> index;
        if ((num & 1) == 1) 
            return true;
        else 
            return false;

    }

    public List<Integer> singleNumberIII(int[] A) {
        ArrayList<Integer> res = new ArrayList<Integer> ();
        if (A ==null || A.length == 0){
            return res;
        }
        int n = A.length;
        int result = 0;
        for (int i = 0;i < n;i ++){
            result ^= A[i];
        }

        int indexOfBit1 = findFirstBit1(result);

        int num1 = 0, num2 = 0;
        for(int i = 0; i < n; ++i) {
            if(isBit1(A[i], indexOfBit1)) {
                num1 ^= A[i];
            }
            else
                num2 ^= A[i];
        }
        res.add(num1);
        res.add(num2);
        return res;
    }
}

majority-number

原题 给定一个整型数组，找出主元素，它在数组中的出现次数严格大于数组元素个数的二分之一

java代码

public class Solution {
    /**
     * @param nums: a list of integers
     * @return: find a  majority number
     */
    public int majorityNumber(ArrayList<Integer> nums) {
        if (nums.size() == 0){
            return -1;
        }
        int result = nums.get(0);
        int count = 1;
        for (int i = 1;i < nums.size();i++){
            if (result == nums.get(i)){
                count ++;
            }
            else {
                count --;
                if (count == 0){
                    result = nums.get(i);
                    count = 1;
                }
            }
        }
        return result;
    }
}

majority-number-ii 主元素 II

原题 给定一个整型数组，找到主元素，它在数组中的出现次数严格大于数组元素个数的三分之一。

思路

1.选择两个candidate

2.scan数组，如果和两个candidate相等，则相应的candidate count+1；如果不相等，两个candidate的counter都减1（前提是counter都大于0）；如果某一个counter已经等于0，那么替换candidate为当前数

3.我们最后得到两个candidate，但是不知道谁更majority，因为一个例子就是1,1,1,1,3,3,3,2,2,2,5,5,5,最后candidate1=1， counter=1，candidate2=5，counter2=3，原因就是candidate1在之前被错误的抵消了很多。所以要再扫一遍。

java代码

public class Solution {
    /**
     * @param nums: A list of integers
     * @return: The majority number that occurs more than 1/3
     */
    public int majorityNumber(ArrayList<Integer> nums) {
        int candidate1 = 0, candidate2 = 0;
        int count1, count2;
        count1 = count2 = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (candidate1 == nums.get(i)) {
                count1 ++;
            } else if (candidate2 == nums.get(i)) {
                count2 ++;
            } else if (count1 == 0) {
                candidate1 = nums.get(i);
                count1 = 1;
            } else if (count2 == 0) {
                candidate2 = nums.get(i);
                count2 = 1;
            } else {
                count1--;
                count2--;
            }
        }
        count1 = count2 = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums.get(i) == candidate1) {
                count1++;
            } else if (nums.get(i) == candidate2) {
                count2++;
            }
        }    
        return count1 > count2 ? candidate1 : candidate2;
    }
}

majority-number-iii 主元素 III

原题 给定一个整型数组，找到主元素，它在数组中的出现次数严格大于数组元素个数的1/k。

思路

使用HashMap，存k个值，key为数组中的元素值，value为该值出现的次数。若同时有k个不同的元素在map中，则抵销一次，即所有value减一，并删除value为零的key，遍历一遍后，map中value最大的key为答案。

java代码

public class Solution {
    /**
     * @param nums: A list of integers
     * @param k: As described
     * @return: The majority number
     */
    public int majorityNumber(ArrayList<Integer> nums, int k) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();

        for (Integer i : nums) {
            if (!map.containsKey(i)) {
                map.put(i, 1);
            } else {
                map.put(i, map.get(i) + 1);
            }

            if (map.size() >= k) {
                removeKey(map);
            }
        }
        if (map.size() == 0) {
            return Integer.MIN_VALUE;
        }

        int maxKey = 0;
        int max = 0;
        Set<Integer> keySet = map.keySet();
        for (Integer i : keySet) {
            int count = 0;
            for (Integer j : nums) {
                if (i.equals(j)) {
                    count++;
                }
            }
            if (count > max) {
                max = count;
                maxKey = i;

            }
        }

        return maxKey;
    }

    private void removeKey(Map<Integer, Integer> map) {
        Set<Integer> keySet = map.keySet();
        List<Integer> removeList = new ArrayList<>();
        for (Integer key : keySet) {
            if (map.get(key) == 1) {
                removeList.add(key);
            }
            else {
                map.put(key, map.get(key) - 1);
            }
        }
        for (Integer key : removeList) {
            map.remove(key);
        }
    }
}

best-time-to-buy-and-sell-stock 买卖股票的最佳时机

原题 假设有一个数组，它的第i个元素是一支给定的股票在第i天的价格。如果你最多只允许完成一次交易(例如,一次买卖股票),设计一个算法来找出最大利润。

思路

扫描一遍，找出后一项-前一项的最大值即可

java代码

public class Solution {
    /**
     * @param prices: Given an integer array
     * @return: Maximum profit
     */
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }

        int min = Integer.MAX_VALUE;  //just remember the smallest price
        int profit = 0;
        for (int i : prices) {
            min = i < min ? i : min;
            profit = (i - min) > profit ? i - min : profit;
        }

        return profit;
    }
}

best-time-to-buy-and-sell-stock-ii 买卖股票的最佳时机 II

原题 假设有一个数组，它的第i个元素是一个给定的股票在第i天的价格。设计一个算法来找到最大的利润。你可以完成尽可能多的交易(多次买卖股票)。然而,你不能同时参与多个交易(你必须在再次购买前出售股票)。

思路

best-time-to-buy-and-sell-stock的基础累加即可

java代码

class Solution {
    /**
     * @param prices: Given an integer array
     * @return: Maximum profit
     */
    public int maxProfit(int[] prices) {
        if ( prices == null || prices.length == 0){
            return 0;
        }
        int profit = 0;
        for (int i = 1; i < prices.length; i++){

            if (prices[i] > prices[i-1]){
                profit += prices[i] - prices[i-1];

            }
        }
        return profit;
    }
}

买卖股票的最佳时机 III

原题 假设你有一个数组，它的第i个元素是一支给定的股票在第i天的价格。设计一个算法来找到最大的利润。你最多可以完成两笔交易。

样例

给出一个样例数组 [4,4,6,1,1,4,2,5], 返回 6

思路

基本思想是分成两个时间段，然后对于某一天，计算之前的最大值和之后的最大值

代码

class Solution {
    /**
     * @param prices: Given an integer array
     * @return: Maximum profit
     */
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length <= 1) {
            return 0;
        }

        int[] left = new int[prices.length];
        int[] right = new int[prices.length];

        // DP from left to right;
        left[0] = 0;
        int min = prices[0];
        for (int i = 1; i < prices.length; i++) {
            min = Math.min(prices[i], min);
            left[i] = Math.max(left[i - 1], prices[i] - min);
        }

        //DP from right to left;
        right[prices.length - 1] = 0;
        int max = prices[prices.length - 1];
        for (int i = prices.length - 2; i >= 0; i--) {
            max = Math.max(prices[i], max);
            right[i] = Math.max(right[i + 1], max - prices[i]);
        }

        int profit = 0;
        for (int i = 0; i < prices.length; i++){
            profit = Math.max(left[i] + right[i], profit);  
        }

        return profit;
    }
};

买卖股票的最佳时机 IV

原题 假设你有一个数组，它的第i个元素是一支给定的股票在第i天的价格。

设计一个算法来找到最大的利润。你最多可以完成 k 笔交易

思路

我们维护两种量，一个是当前到达第i天可以最多进行j次交易，最好的利润是多少（global[i][j]），另一个是当前到达第i天，最多可进行j次交易，并且最后一次交易在当天卖出的最好的利润是多少（local[i][j]）

同时注意当K很大时的情况,变为买卖股票的最佳时机ii。

java代码

class Solution {
    /**
     * @param k: An integer
     * @param prices: Given an integer array
     * @return: Maximum profit
     */
    public int maxProfit(int k, int[] prices) {
        if (k == 0) {
            return 0;
        }
        if(prices==null || prices.length==0)  
        return 0;  

        if (k >= prices.length / 2) {
            int profit = 0;
            for (int i = 1; i < prices.length; i++) {
                if (prices[i] > prices[i - 1]) {
                    profit += prices[i] - prices[i - 1];
                }
            }
            return profit;
        }
        int len = prices.length;  
        int[][] local = new int[len][k+1];       
        int[][] global = new int[len][k+1];     
        for(int i=1; i<len; i++) {  
            int diff = prices[i] - prices[i-1];  
            for(int j=1; j<=k; j++) {  
                local[i][j] = Math.max(global[i-1][j-1]+Math.max(diff,0), local[i-1][j]+diff);  
                global[i][j] = Math.max(global[i-1][j], local[i][j]);  
            }  
        }  
        return global[len-1][k];   
    }
};

最大子数组

原题 给定一个整数数组，找到一个具有最大和的子数组，返回其最大和。

思路

扫描一遍，遇到负数则重新累加求和。

java代码

public class Solution {
    /**
     * @param nums: A list of integers
     * @return: A integer indicate the sum of max subarray
     */
    public int maxSubArray(ArrayList<Integer> nums) {
        if(nums == null || nums.size() == 0){
            return 0;
        }
        int thissum = 0;
        int maxsum = nums.get(0);
        for (int i : nums){
            thissum += i;
            if (thissum > maxsum){
                maxsum = thissum;
            }
            else if (thissum < 0){
                thissum = 0;
            }
        }
        return maxsum;
    }
}

最大子数组 II

原题 给定一个整数数组，找出两个不重叠子数组使得它们的和最大。

每个子数组的数字在数组中的位置应该是连续的。

返回最大的和。

思路

和买卖股票的最佳时机 III 思路一样。用俩个数组，一个从左往右扫，一个从右往左扫。

java代码

public class Solution {
    /**
     * @param nums: A list of integers
     * @return: An integer denotes the sum of max two non-overlapping subarrays
     */
    public int maxTwoSubArrays(ArrayList<Integer> nums) {
        // write your code
        int size = nums.size();
        int[] left = new int[size];
        int[] right = new int[size];
        int sum = 0;
        int minSum = 0;
        int max = Integer.MIN_VALUE;
        for(int i = 0; i < size; i++){
            sum += nums.get(i);
            max = Math.max(max,sum);
            sum = Math.max(sum,0);
            left[i] = max;
        }
        sum = 0;
        minSum = 0;
        max = Integer.MIN_VALUE;
        for(int i = size - 1; i >= 0; i--){
            sum += nums.get(i);
            max = Math.max(max, sum );
            sum = Math.max(sum,0);
            right[i] = max;
        }
        max = Integer.MIN_VALUE;
        for(int i = 0; i < size - 1; i++){
            max = Math.max(max, left[i] + right[i + 1]);
        }
        return max;
    }
}

maximum-subarray-iii 最大子数组iii

原题 给定一个整数数组和一个整数k，找出k个不重叠子数组使得它们的和最大。

每个子数组的数字在数组中的位置应该是连续的。

返回最大的和。

思路

思路类似买卖股票的最佳时机 IV，用DP解。

java代码

public class Solution {
    /**
     * @param nums: A list of integers
     * @param k: An integer denote to find k non-overlapping subarrays
     * @return: An integer denote the sum of max k non-overlapping subarrays
     */

        public int maxSubArray(ArrayList<Integer> nums, int k) {
        if (nums == null)
            return 0;
        int len = nums.size();
        if (len < k)
            return 0;

        int[][] globalMax = new int[k + 1][len + 1];
        for (int i = 1; i <= k; i++) {
            int localMax = Integer.MIN_VALUE;

            for (int j = i - 1; j < len; j++) {
                localMax = Math.max(localMax, globalMax[i - 1][j]) + nums.get(j);
                if (j == i - 1)
                    globalMax[i][j + 1] = localMax;
                else
                    globalMax[i][j + 1] = Math.max(globalMax[i][j], localMax);
            }
        }
        return globalMax[k][len];
    }



}

minimum-subarray 最小子数组

原题

思路

同最大子数组

java代码

public class Solution {
    /**
     * @param nums: a list of integers
     * @return: A integer indicate the sum of minimum subarray
     */
    public int minSubArray(ArrayList<Integer> nums) {
        if (nums == null || nums.size() == 0) {
            return 0;
        }
        int tempSum = 0;
        int minSum = nums.get(0);
        for (int i = 0; i < nums.size(); i++){

            tempSum += nums.get(i);
            minSum = Math.min(tempSum , minSum);
            tempSum = Math.min(tempSum , 0);
        }
        return minSum;
    }
}

maximum-subarray-difference 最大子数组差

给定一个整数数组，找出两个不重叠的子数组A和B，使两个子数组和的差的绝对值|SUM(A) - SUM(B)|最大。

返回这个最大的差值。

思路

左右各扫描一遍。建立俩个数组，每个数组存放对应的从左，从右的最大，最小值。

代码

public class Solution {
    /**
     * @param nums: A list of integers
     * @return: An integer indicate the value of maximum difference between two
     *          Subarrays
     */
    public int maxDiffSubArrays(ArrayList<Integer> nums) {
        if (nums == null || nums.size() == 0) {
            return 0;
        }
        int len = nums.size();
        int[] leftMin = new int[len];
        int[] leftMax = new int[len];
        int endMin = nums.get(0), endMax = nums.get(0);
        leftMin[0] = endMin;
        leftMax[0] = endMax;
        for (int i=1;i<len;i++){
            //Calculate max subarray.
            endMax = Math.max(nums.get(i), nums.get(i)+endMax);
            leftMax[i] = Math.max(leftMax[i-1],endMax);

            //Calculate min subarray.
            endMin = Math.min(nums.get(i),nums.get(i)+endMin);
            leftMin[i] = Math.min(leftMin[i-1],endMin);
        }

        int[] rightMin = new int[len];
        int[] rightMax = new int[len];
        endMin = nums.get(len-1);
        endMax = nums.get(len-1);
        rightMin[len-1] = endMin;
        rightMax[len-1] = endMax;
        for (int i=len-2;i>=0;i--){
            endMax = Math.max(nums.get(i),nums.get(i)+endMax);
            rightMax[i] = Math.max(rightMax[i+1],endMax);
            endMin = Math.min(nums.get(i),nums.get(i)+endMin);
            rightMin[i] = Math.min(rightMin[i+1],endMin); 
        }

        int maxDiff= 0;
        for (int i=0;i<len-1;i++){
            if (maxDiff<Math.abs(leftMin[i]-rightMax[i+1]))
                maxDiff = Math.abs(leftMin[i]-rightMax[i+1]);

            if (maxDiff<Math.abs(leftMax[i]-rightMin[i+1]))
                maxDiff = Math.abs(leftMax[i]-rightMin[i+1]);
        }
        return maxDiff;
    }
}

subarray-sum 子数组之和

原题 给定一个整数数组，找到和为零的子数组。你的代码应该返回满足要求的子数组的起始位置和结束位置

思路

使用Map 来记录index,sum的值。当遇到两个index的sum相同时，表示从index1+1到index2是一个解。 注意：添加一个index = -1作为虚拟节点。这样我们才可以记录index1 = 0的解。

java代码

public class Solution {
    /**
     * @param nums: A list of integers
     * @return: A list of integers includes the index of the first number 
     *          and the index of the last number
     */
    public ArrayList<Integer> subarraySum(int[] nums) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        if (nums==null || nums.length==0) return res;
        int len = nums.length;
        Map<Integer,Integer> map = new HashMap<Integer , Integer>();

        map.put(0,-1);
        int sum =0;
        for (int i=0;i<len;i++){
            sum += nums[i];
            //check the exists of current sum.
            if (map.containsKey(sum)){
                int start = map.get(sum)+1;
                res.add(start);
                res.add(i);
                return res;
            } else {

                map.put(sum,i);
            }
        }

        return res;
    }
}

subarray-sum-closest 最接近零的子数组和

原题 给定一个整数数组，找到一个和最接近于零的子数组。返回第一个和最有一个指数。你的代码应该返回满足要求的子数组的起始位置和结束位置。

思路

连续数组的和其实就是前缀和之间的差，而要求和最接近于零，也就是说，两个前缀和要最接近，那么直接前缀和排序，相邻两项比较即。 由O(nlogn)的时间复杂度我们也可以想到排序。

java代码

class CustomComparator implements Comparator<int[]> {
    public int compare(int[] a, int[] b) {
        return Integer.compare(a[0], b[0]);
    }
}

public class Solution {

    /**
     * @param nums: A list of integers
     * @return: A list of integers includes the index of the first number 
     *          and the index of the last number
     */
   public ArrayList<Integer> subarraySumClosest(int[] nums) {
        ArrayList<Integer> rst = new ArrayList<Integer>();
        if(nums == null || nums.length == 0) {
            return rst;
        }
        if (nums.length == 1) {
            rst.add(0); rst.add(0);
            return rst;
        }
        int[][] culmulate = new int[nums.length][2];
        culmulate[0][0] = nums[0];
        culmulate[0][1] = 0;
        for (int i = 1; i < nums.length; i++) {
            culmulate[i][0] = culmulate[i - 1][0] + nums[i];
            culmulate[i][1] = i;
        }

        Arrays.sort(culmulate, new CustomComparator());
        int min = Integer.MAX_VALUE;
        int start = 0;
        int end = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            int temp = culmulate[i + 1][0] - culmulate[i][0];
            if (temp <= min) {
                min = temp;
                start = culmulate[i][1];
                end = culmulate[i + 1][1];
            }
        }
         if (start < end) {
            rst.add(start + 1);
            rst.add(end);
        } else {
            rst.add(end + 1);
            rst.add(start);
        }
        return rst;
    }
}

2-sum 两数之和

原题 给一个整数数组，找到两个数使得他们的和等于一个给定的数target。

你需要实现的函数twoSum需要返回这两个数的下标, 并且第一个下标小于第二个下标。注意这里下标的范围是1到n，不是以0开头。

思路

和 subarray-sum 子数组之和 问题一样

java代码

public class Solution {
    /*
     * @param numbers : An array of Integer
     * @param target : target = numbers[index1] + numbers[index2]
     * @return : [index1 + 1, index2 + 1] (index1 < index2)
     */
    public int[] twoSum(int[] numbers, int target) {
    HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
    int[] result = new int[2];

    for (int i = 0; i < numbers.length; i++) {
        if (map.containsKey(numbers[i])) {
            int index = map.get(numbers[i]);
            result[0] = index+1 ;
            result[1] = i+1;
            break;
        } else {
            map.put(target - numbers[i], i);
        }
    }

    return result;
    }
}

3-sum 三数之和

原题 给出一个有n个整数的数组S，在S中找到三个整数a, b, c，找到所有使得a + b + c = 0的三元组。

思路

a + b + c = 0 => a + b = -c; 我们很自然的想到排序，再从俩头扫。设置最小的c,第2小和最大的为a 和 b. 固定c,让a++或者b--.对整个数组循环这个过程。

代码

 public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
    ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();

    if (num.length < 3)
        return result;

    // sort array
    Arrays.sort(num);

    for (int i = 0; i < num.length - 2; i++) {
        // //avoid duplicate solutions
        if (i == 0 || num[i] > num[i - 1]) {

            int negate = -num[i];

            int start = i + 1;
            int end = num.length - 1;

            while (start < end) {
                //case 1
                if (num[start] + num[end] == negate) {
                    ArrayList<Integer> temp = new ArrayList<Integer>();
                    temp.add(num[i]);
                    temp.add(num[start]);
                    temp.add(num[end]);

                    result.add(temp);
                    start++;
                    end--;
                    //避免重复
                    while (start < end && num[end] == num[end + 1])
                        end--;

                    while (start < end && num[start] == num[start - 1])
                        start++;
                //case 2
                } else if (num[start] + num[end] < negate) {
                    start++;
                //case 3
                } else {
                    end--;
                }
            }

        }
    }

    return result;

3-sum-closest 三数之和 II

给一个包含n个整数的数组S, 找到和与给定整数target最接近的三元组，返回这三个数的和。

思路

和上题一样，排序后，俩头扫。只是每次保留和target的差的最小值

public int threeSumClosest(int[] nums ,int target) {
    int min = Integer.MAX_VALUE;
    int result = 0;

    Arrays.sort(nums);

    for (int i = 0; i < nums.length; i++) {
        int j = i + 1;
        int k = nums.length - 1;
        while (j < k) {
            int sum = nums[i] + nums[j] + nums[k];
            int diff = Math.abs(sum - target);

            if(diff == 0) return sum;

            if (diff < min) {
                min = diff;
                result = sum;
            }
            if (sum <= target) {
                j++;
            } else {
                k--;
            }
        }
    }

    return result;
    }

4-sum 四数之和

给一个包含n个数的整数数组S，在S中找到所有使得和为给定整数target的四元组(a, b, c, d)。

思路

和前俩题思路一样，只不过排序后要固定前俩个数字，俩头扫。需要俩重循环。

public class Solution {
    public ArrayList<ArrayList<Integer>> fourSum(int[] num, int target) {
        ArrayList<ArrayList<Integer>> rst = new ArrayList<ArrayList<Integer>>();
        Arrays.sort(num);

        for (int i = 0; i < num.length - 3; i++) {
            if (i != 0 && num[i] == num[i - 1]) {
                continue;
            }

            for (int j = i + 1; j < num.length - 2; j++) {
                if (j != i + 1 && num[j] == num[j - 1])
                    continue;

                int left = j + 1;
                int right = num.length - 1;
                while (left < right) {
                    int sum = num[i] + num[j] + num[left] + num[right];
                    if (sum < target) {
                        left++;
                    } else if (sum > target) {
                        right--;
                    } else {
                        ArrayList<Integer> tmp = new ArrayList<Integer>();
                        tmp.add(num[i]);
                        tmp.add(num[j]);
                        tmp.add(num[left]);
                        tmp.add(num[right]);
                        rst.add(tmp);
                        left++;
                        right--;
                        while (left < right && num[left] == num[left - 1]) {
                            left++;
                        }
                        while (left < right && num[right] == num[right + 1]) {
                            right--;
                        }
                    }
                }
            }
        }

        return rst;
    }
}

k-sum k数和

给定n个不同的正整数，整数k（k < = n）以及一个目标数字。 在这n个数里面找出K个数，使得这K个数的和等于目标数字，求问有多少种方案？

思路

经过前面几道和K相关的问题，我们意识到应该用动态规划（DP）了。 建立递推方程如下：

 if (t <= A[i - 1]) {
   f[i][j][t] = f[i - 1][j - 1][t - A[i - 1]];
     }
 f[i][j][t] += f[i - 1][j][t];

我们用f[i][j][t] 代表前i个数，挑j个数，组成和为t的方案总数。 （1）我们可以把当前A[i - 1]这个值包括进来，所以需要加上D[i - 1][j - 1][t - A[i - 1]]（前提是t – A[i - 1]要大于0）

（2）我们可以不选择A[i - 1]这个值，这种情况就是D[i - 1][j][t]，也就是说直接在前i-1个值里选择一些值加到target.



public class Solution {
    /**
     * @param A: an integer array.
     * @param k: a positive integer (k <= length(A))
     * @param target: a integer
     * @return an integer
     */
     public int  kSum(int A[], int k, int target) {
        int n = A.length;
        int[][][] f = new int[n + 1][k + 1][target + 1];
        for (int i = 0; i < n + 1; i++) {
            f[i][0][0] = 1;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= k && j <= i; j++) {
                for (int t = 1; t <= target; t++) {
                    f[i][j][t] = 0;
                    if (t >= A[i - 1]) {
                        f[i][j][t] = f[i - 1][j - 1][t - A[i - 1]];
                    }
                    f[i][j][t] += f[i - 1][j][t];
                } // for t
            } // for j
        } // for i
        return f[n][k][target];
    }
}

fast-power 快速幂

计算an % b，其中a，b和n都是32位的整数。

思路

a的n次方等于a的n/2次方乘以a的n/2次方。注意奇偶。

class Solution {
    /*
     * @param a, b, n: 32bit integers
     * @return: An integer
     */
    public int fastPower(int a, int b, int n) {
        if (n == 1) {
            return a % b;
        }
        if (n == 0) {
            return 1 % b;
        }

        long product = fastPower(a, b, n / 2);
        product = (product * product) % b;
        if (n % 2 == 1) {
            product = (product * a) % b;
        }
        return (int) product;
    }
};

sqrtx x的平方根

Implement int sqrt(int x).Compute and return the square root of x

二分查找。由时间复杂度logn以及相关数学知识我们应该想到

public class Solution {
    public int sqrt(int x) {
        long lo = 0;
        long hi = x;

        while (hi >= lo) {     
            long mid = lo+(hi-lo)/2;
            if (x < mid * mid) {
                hi = mid-1;      // not hi = mid
            } else {
                lo = mid+1;  
            }
        }
        return (int) hi;
    }
}

Trailing Zeros n!尾部0的个数

Write an algorithm which computes the number of trailing zeros in n factorial.

思路

由数学知识我们知道，n!中尾部0的个数取决于5的个数，但是还有5的n次方我们不要忘记统计，因为2的个数总是多于5的。

class Solution {
    /*
     * param n: As desciption
     * return: An integer, denote the number of trailing zeros in n!
     */
    public long trailingZeros(long n) {
        long x = 5;
        long result = 0;
        while (n >= x){
            result += n / x;
            x *= 5;
        }
        return result;
    }
};

o1-check-power-of-2 o1时间检查是否是2的幂

Using O(1) time to check whether an integer n is a power of 2.

思路

如果是n是2的幂，则有n&(n-1) == 0. 位运算中小技巧还是蛮多的。

class Solution {
    /*
     * @param n: An integer
     * @return: True or false
     */
    public boolean checkPowerOf2(int n) {
        if (n == 0 || n == Integer.MIN_VALUE){
            return false;
        }
        boolean flag = false;
        if ((n & n - 1) == 0){
            flag = true;
        }
        return flag;
    }
};

参考资料

九章算法

《OLAP 性能优化指南》欢迎 Star&共建

《OLAP 性能优化指南》

欢迎关注微信公众号

康凯森