48. 不用加减乘除做加法
写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。
思路：不能用加减乘除，那么只能用二进制的位运算。不考虑进位，二进制中1+0 = 1，1+1=0，与异或运算相同；考虑进位，1+1进位1，1+0进位0，这和与运算相同，但是进位是进给左侧一位，因此再做一次左移。现在，num1与num2相加，我们先做一次异或，得到两个数不进位相加的值sum；令两个数相与左移，得到纯进位值carry，需要再相加这两部分才能得到最终的值，但是可能又出现进位，因此就是循环上述操作。这相当于把num1+num2转化为sum+carry，carry为0，也就是不再进位的时候，此时异或值就是答案。
1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
public int Add(int num1,int num2) {
int sum = 0, carry = 0;
do{
sum = num1 ^ num2;
carry = (num1 & num2) << 1;
num1 = sum;
num2 = carry;
}
while(num2!=0);
return num1;
}
}
49. 把字符串转换成整数
将一个字符串转换成一个整数，要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0
思路： 关键是要判断一些边界条件，例如非法输入、正负号等。正常的思路就是逐个读取字符串字符，乘十累加。
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
33
34
public class Solution {
boolean invalidInput = false;
public int StrToInt(String str) {
if(str.length() == 0){
invalidInput = true;
return 0;
}
boolean negative = false;
int start = 0;
char[] strlist = str.toCharArray();
if(strlist[0] == '-'){
negative = true;
start = 1;
}
long sum = 0;
for(int i = start; i < strlist.length; i++){
if(strlist[i] == '+') continue;
if(strlist[i] < 48 || strlist[i] > 57){
invalidInput = true;
return 0;
}
sum = sum*10 + strlist[i] - 48;
}
sum = negative?-sum:sum;
if(sum > Integer.MAX_VALUE || sum < Integer.MIN_VALUE){
return 0;
}
return (int)sum;
}
}
50. 数组中的重复数字
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。
思路： 利用HashMap统计次数，第一个超过一次的就是正解。另外一种思路，因为数字范围为0～n-1，数字本身可以作为标识，当我们顺序遍历到数字i，则去访问t = numbers[numbers[i]]，并给该t做一个标记，例如取负号、加上length等操作；遍历的时候需要对这些操作取逆还原成原来0～n-1内的数字，而利用这个数字本身去访问数组相应位置的值的时候，如果得到的数字已经做过这些操作，那么说明已经访问过，返回该数组即可。两种方法都是复杂度O(n)，HashMap需要额外空间，而第二种方法修改了原先的数组。
解法一：
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
import java.util.HashMap;
public class Solution {
// Parameters:
// numbers: an array of integers
// length: the length of array numbers
// duplication: (Output) the duplicated number in the array number,length of duplication array is 1,so using duplication[0] = ? in implementation;
// Here duplication like pointor in C/C++, duplication[0] equal *duplication in C/C++
// 这里要特别注意~返回任意重复的一个，赋值duplication[0]
// Return value: true if the input is valid, and there are some duplications in the array number
// otherwise false
public boolean duplicate(int numbers[],int length,int [] duplication) {
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
for(int i = 0; i < length; i++){
if(!map.containsKey(numbers[i])) map.put(numbers[i], 1);
else map.put(numbers[i], map.get(numbers[i]) + 1);
}
for(int i = 0; i < length; i++){
if(map.get(numbers[i]) > 1) {
duplication[0] = numbers[i];
return true;
}
}
return false;
}
}
解法二：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {
public boolean duplicate(int numbers[],int length,int [] duplication) {
if(length == 0) return false;
for(int num : numbers){
int index = num;
if(index < 0) index = -index;
if(numbers[index] < 0){
duplication[0] = index;
return true;
}
numbers[index] = -numbers[index];
}
return false;
}
}
51. 构建乘积数组
给定一个数组A[0,1,…,n-1],请构建一个数组B[0,1,…,n-1],其中B中的元素B[i]=A[0]A[1]…A[i-1]A[i+1]…A[n-1]。不能使用除法。
思路： 1. B[i]的值是A中所有值的乘积除以A[i]，因此首先计算A中所有值的乘积t，加入B[i]时，用t/A[i]，注意A中0元素的存在，当A[i]=0时，B中除第i个之外所有值都为0，B[i]的值为A中除A[i]之外的所有值的乘积；当A中有两个以上的0，则B中所有元素为0。
- 建立两个游标，i和j分别从A的首位开始累乘，如下表所示：
| 1 | A[1] | A[2] | … | A[n-1] |
|---|---|---|---|---|
| A[0] | 1 | A[2] | … | A[n-1] |
| A[0] | A[1] | 1 | … | A[n-1] |
| A[0] | A[1] | … | 1 | |
| A[0] | A[1] | … | A[n-2] | 1 |
逐行计算出每行1两侧的A部分数组的乘积，存储在left和rigth中，例如，rigth[m] = x,下一行的值就是x * A[m+1]。B[i]的值就是left[i] * right[i]。
解法一：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import java.util.ArrayList;
public class Solution {
public int[] multiply(int[] A) {
int[] B = new int[A.length];
ArrayList<Integer> zero = new ArrayList<Integer>();
int total = 1;
for(int i = 0; i < A.length; i++){
if(A[i] == 0){
zero.add(i);
continue;
}
total *= A[i];
}
if(zero.size() > 1) return B;
for(int j = 0; j < B.length; j++){
if(zero.size() > 0){
if(j == zero.get(0)) B[j] = total;
else B[j] = 0;
}
else B[j] = total / A[j];
}
return B;
}
}
解法二：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Solution {
public static int[] multiply(int[] A) {
if(A == null){
return null;
}
int len = A.length;
int[] forword = new int[len];
int[] back = new int[len];
int[] B = new int[len];
forword[0] = 1;
back[len - 1] = 1;
for(int i = 1; i < len; i++){
forword[i] = A[i - 1] * forword[i - 1];
}
for(int i = len - 2; i >= 0; i--){
back[i] = A[i + 1] * back[i + 1];
}
for(int i = 0; i < len; i++){
B[i] = forword[i] * back[i];
}
return B;
}
}