和为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];
} 
京公网安备 11010502036488号