40. 数组中只出现一次的数
一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
思路：常规思路是HashMap统计次数，输出只出现一次的数。另一种比较厉害的思路是使用异或，我们知道相同的数异或之后的结果为0；不同的数，异或的结果就是两个数转换成二进制之后将相同位变为0之后的那个二进制数。因为异或运算满足交换律，因此题设中除了两个数只出现一次，其它数都出现两次，将所有数字异或，得到的值与这两个数直接异或的值是相同的。
假设上述异或后的值为1101，那么第一个1的位置为1，表示这两个数在第1位出现了不同。因此我们只需要将数组分为两组，第1位为1的一组，第1位不为1的一组，此时在这两组中，只有这两个数字是只出现一次的，在这两组中再进行异或操作，最后就能得到这两个数。
解法一：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import java.util.HashMap;
public class Solution {
public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
for(int n: array){
if(!map.containsKey(n)) map.put(n, 1);
else map.put(n, map.get(n) + 1);
}
int count = 1;
for(int n: array){
if(map.get(n) == 1 && count == 1) {
num1[0] = n;
count++;
}
else if(map.get(n) == 1 && count == 2) {
num2[0] = n;
break;
}
}
}
}
解法二：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public class Solution {
public void FindNumsAppearOnce(int[] array, int num1[], int num2[]) {
if (array == null || array.length < 2)
return;
int resultExclusiveNor = 0;
for (int item : array)
resultExclusiveNor ^= item;
int firstIndex = findFirstIndex(resultExclusiveNor);
num1[0]=0;
num2[0]=0;
for(int item:array){
if(isBit1(item,firstIndex)) num1[0]^=item;
else num2[0]^=item;
}
}
public int findFirstIndex(int n) {
int index = 0;
while ((1 & n) == 0 && index < 32) {
n = n >> 1;
index++;
}
return index;
}
public boolean isBit1(int num, int index) {
boolean check = false;
num = num >> index;
if ((num & 1) == 1) check = true;
return check;
}
}
41. 和为s的连续正数序列
小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!
输出描述:
输出所有和为S的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序
思路： 设置两个游标，small表示解序列的头部元素，big表示解序列的尾部元素，若按求和公式，得到这个序列的和小于s，则令big加1；反之，small加1；若等于s，则存储该序列，big继续加1。另外还有很多数学上的解法，例如通过求和公式，利用small直接求解big。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import java.util.ArrayList;
public class Solution {
public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
int small = 1, big = 2;
ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
while(small <= sum/2){
int tmpSum = (small + big)*(big - small + 1)/2;
if(tmpSum > sum) small++;
else if (tmpSum < sum) big++;
else{
ArrayList<Integer> sequence = new ArrayList<Integer>();
for(int i = small; i <= big; i++){
sequence.add(i);
}
res.add(sequence);
big++;
}
}
return res;
}
}
42. 和为S的两个数
输入一个递增排序的数组和一个数字S，在数组中查找两个数，是的他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。
输出描述:
对应每个测试案例，输出两个数，小的先输出。
思路： 定义两个游标，一个指向数组头部，另一个指向尾部。左右夹逼，遇到的第一对和为S的两个数，必然乘积最小。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
ArrayList<Integer> res = new ArrayList<Integer>();
int i = 0, j = array.length - 1;
while(i < j){
if(array[i] + array[j] > sum) j--;
else if(array[i] + array[j] < sum) i++;
else {
res.add(array[i]);
res.add(array[j]);
return res;
}
}
return res;
}
}
43. 左旋转字符串
汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。是不是很简单？OK，搞定它！
思路： 有多种解法，假设长度为s，左移n位。
- 新建一个辅助字符串，字符串从n位到第s-1位，移到辅助字符串的第0位至第s-n-1位；字符串的第0至n-1位，移至辅助字符串的第s-n位至s-1位，输出辅助字符串。用python就是s[n:] + s[:n]。
- 将字符串翻倍，例abcd编程abcdabcd，若左移动2位，则输出翻倍后字符串的第2后长度为s的子串。
- 将字符串在第n-1位分割位两个子串，各自反转，再反转整个字符串。例abcdefgh，n为3，各自反转后cbahgfed，整体反转defghabc。
解法一：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {
public String LeftRotateString(String str,int n) {
if(str.length() == 0) return "";
n = n % str.length();
char[] c = str.toCharArray();
char[] res = new char[str.length()];
for(int i = n; i < str.length(); i++){
res[i - n] = c[i];
}
for(int i = 0; i < n; i++){
res[str.length() - n + i] = c[i];
}
return String.valueOf(res);
}
}
解法二：
1
2
3
4
5
6
7
8
public class Solution {
public String LeftRotateString(String str,int n) {
if(str.length() == 0) return "";
n = n % str.length();
String res = str + str;
return res.substring(n, str.length() + n);
}
}
解法三：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
public String reverse(String str , int left, int right){
char[] strlist = str.toCharArray();
int i = left, j = right;
while(i < j) {
char tmp = strlist[j];
strlist[j--] = strlist[i];
strlist[i++] = tmp;
}
return str = String.valueOf(strlist);
}
public String LeftRotateString(String str,int n) {
if(str.length() == 0) return "";
n = n % str.length();
str = reverse(str, 0, n - 1);
str = reverse(str, n, str.length() - 1);
return reverse(str, 0 , str.length() - 1);
}
}