剑指offer_和为S的两个数字/最大连续子数组的最大和/丑数

和为S的两个数字

输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。

普通解法（我的解法）

public static ArrayList FindNumbersWithSum(int[] array, int sum) {
   ArrayList list = new ArrayList();
    int len = array.length;
    if (len == 0) {
        return list;
    } else {
        int mina = array[len - 1];
        int minb = array[len - 2];
        //取出数组最大值和次大值
        int i = 0;
        int j = 0;
        int flag = 0;
        for (i = 0; i < array.length - 1; i++) {
            for (j = i + 1; j < array.length; j++) {
                if (array[j] == sum - array[i] && array[i] * array[j] < mina * minb) {
                 //如果找到符合条件的数对，更新mina和minb的值，并且让计数器增加1，表示这样的数对存在
                    mina = array[i];
                    minb = array[j];
                    flag++;
                }
                continue;
                //找到之后直接跳出本层循环，因为数组递增，后面的数和肯定大于给定值
            }
        }
        if (flag != 0) {
        //如果找到了这个数对，将其加到list中
            list.add(mina);
            list.add(minb);
        }
        return list;
    }
}

高级解法（双侧夹逼）

import java.util.ArrayList;
public class Solution {
    public ArrayList FindNumbersWithSum(int [] array,int sum) {
        ArrayList list = new ArrayList();
        if (array == null || array.length < 2) {
            return list;
        }
        int i=0,j=array.length-1;
        while(i<j){
        //双侧夹逼，如果数对之和等于给定值，直接加入list，如果大于，这说明右侧数值过大，给右侧索引j减1，反之给i加1
         if(array[i]+array[j]==sum){
            list.add(array[i]);
            list.add(array[j]);
                return list;
           }else if(array[i]+array[j]>sum){
                j--;
            }else{
                i++;
            }

        }
        return list;
    }
}

数组中只出现过一次的数字

一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

题目为什么要强调有一个数字出现一次，其他的出现两次？我们想到了异或运算的性质：任何一个数字异
或它自己都等于0 。也就是说，如果我们从头到尾依次异或数组中的每一个数字，那么最终的结果刚好是
那个只出现一次的数字，因为那些出现两次的数字全部在异或中抵消掉了

//num1,num2分别为长度为1的数组。传出参数
//将num1[0],num2[0]设置为返回结果
public class Solution {
    public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
        if (array.length <= 1) {
            return;
        }
        int len = array.length;
        int sum = 0;
        for (int i = 0; i < len; i++) {
            sum = sum ^ array[i];
        }
        int j = 1;
        while ((sum & j) == 0) {
            j = j << 1;
        }
        for (int i = 0; i < len; i++) {
            if ((array[i] & j) == 0) {
                num1[0] = num1[0] ^ array[i];
            } else {
                num2[0] = num2[0] ^ array[i];
            }

        }
    }
}

最大连续子数组的最大和

在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和(子向量的长度至少是1)

使用动态规划
F（i）：以array[i]为末尾元素的子数组的和的最大值，子数组的元素的相对位置不变
F（i）=max（F（i-1）+array[i] ， array[i]）
res：所有子数组的和的最大值
res=max（res，F（i））
如数组[6, -3, -2, 7, -15, 1, 2, 2]
初始状态：
F（0）=6
res=6
i=1：
F（1）=max（F（0）-3，-3）=max（6-3，3）=3
res=max（F（1），res）=max（3，6）=6
i=2：
F（2）=max（F（1）-2，-2）=max（3-2，-2）=1
res=max（F（2），res）=max（1，6）=6
i=3：
F（3）=max（F（2）+7，7）=max（1+7，7）=8
res=max（F（2），res）=max（8，6）=8
i=4：
F（4）=max（F（3）-15，-15）=max（8-15，-15）=-7
res=max（F（4），res）=max（-7，8）=8
以此类推
最终res的值为8

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
         //数组只有一个元素，则连续子数组最大值就是arr[0]
        if (array.length == 1) {
            return array[0];
        }
        int res = array[0];
        //记录当前所有子数组的和的最大值
        int max = array[0];
        //纪录从array[i]开始的连续数组最大值
        for (int i = 1; i < array.length; i++) {
            max = max + array[i] > array[i] ? max + array[i] : array[i];
            //比较当前连续子数组的和与当前长度加1的连续子数组的,将较大值给max
            res = max > res ? max : res;
            //每次更新max后，将其与所有连续子数组和的最大值进行比较，更新res
        }
        return res;
    }
}

把数组排列成最小的数

输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。

先将整型数组转换成String数组，然后将String数组排序，最后将排好序的字符串数组拼接出来。关键就是制定排序规则。
排序规则如下：
若ab > ba 则 a > b，
若ab < ba 则 a < b，
若ab = ba 则 a = b；
解释说明：
比如 "3" "313"，所以要将二者拼接起来进行比较

import java.util.*;

public class Solution {
    public String PrintMinNumber(int [] numbers) {
        if (numbers == null || numbers.length == 0) {
            return "";
        }
        int len = numbers.length;
        String[] str = new String[len];
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < len; i++) {
            str[i] = String.valueOf(numbers[i]);
        }
        Arrays.sort(str, new Comparator() {
            @Override
            public int compare(String s1, String s2) {
                String c1 = s1 + s2;
                String c2 = s2 + s1;
                return c1.compareTo(c2);
            }
        });
        for (int i = 0; i < len; i++) {
            sb.append(str[i]);
        }
        return sb.toString();
    }
}

丑数(Ugly Number)

把只包含质因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数，但14不是，因为它包含质因子7。习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

我们需要一个辅助数组来存储我们找到的丑数，最笨的方法当然是每次从数组的第一个开始找 k ，使得它
的 2倍 3倍或者 5倍大于当前的数组最大值。
当然 k 的值不一定是唯一的，比如我们现在找第 4 丑数.我们从 1 开始，此时数组中最大的数 max = 1 :
max = 1 : 2*1 = 2、3*1 = 3 、 5*1 = 5 ，因为 2 最小，所以第二个丑数是 2 .
max = 2：2*1 = 2 <= 2 ,2*2 = 4、 3*1 = 3 ，5*1 = 5 ，最小的数是 3 ,所以第三个丑数是 3 .
max = 3：2*1 = 2 < 3 ，2*2 = 4, 3*1 = 3 <= 3 , 3*2 = 6 , 5*1 = 5，最小的数是 4 ，所以第四个丑数是 4.

 private static int UglyNumber(int index) {
        if (index <= 0) {
            return 0;
        }
        int[] arr = new int[index];
        arr[0] = 1;
        int temp = 1;
        int temp2 = 0;
        int temp3 = 0;
        int temp5 = 0;

        while (temp < index) {
            int a = arr[temp2] * 2;
            int b = arr[temp3] * 3;
            int c = arr[temp5] * 5;
            int min = (a > b ? b : a) > c ? c : (a > b ? b : a);
            // 找出三个数中最小的加入到arr中
            arr[temp] = min;
            if (min == a) {
                temp2++;
            }
            if (min == b) {
                temp3++;
            }
            if (min == c) {
                temp5++;
            }
            temp++;
        }
        return arr[index - 1];
    }