第一题：给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
private static int getNum(Integer[] nums) {
int num = 0;
for (int i = 0; i < nums.length; i++) {
num ^= nums[i];
}
return num;
}
测试
public static void main(String[] args) {
Integer[] nums = {4,1,2,1,2};
System.out.println(getNum(nums));
}
结果
image.png
异或：其运算法则相当于不带进位的二进制加法。如果a、b两个值不相同，则异或结果为1。如果a、b两个值相同，异或结果为0。
解：
- 4：00000100
- 1 : 00000001
- 2 : 00000010
按{4,1,2,1,2}依次异或 - 4 ^ 1 = 00000100 ^ 00000001 = 00000101
- （4 ^ 1） ^ 2 = 00000101 ^ 00000010 = 00000111
- （4 ^ 1 ^ 2 ）^ 1 = 00000111 ^ 00000001 = 00000110
- （4 ^ 1 ^ 2 ^ 1） ^ 2 = 00000110 ^ 00000010 = 00000100 = 4
第二题：编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。
示例 1：
输入：["h","e","l","l","o"]
输出：["o","l","l","e","h"]
public static void reverseString(char[] s) {
if(s.length <= 1) {
return;
}
int j = s.length - 1;
for (int i = 0; i < s.length/2; i++,j--) {
s[i] ^= s[j];
s[j] ^= s[i];
s[i] ^= s[j];
}
}
测试
public static void main(String[] args) {
char[] s = {'h','e','l','l','o'};
reverseString(s);
for (char c : s) {
System.out.println(c);
}
}
结果
image.png
第三题：不使用运算符 + 和 - ，计算两整数 a 、b 之和。
题解：不能使用+和-，可以使用位运算符来计算。
1、位运算有如下4中
0+1=1
1+0=1
0+0=0
1+1=1
这个是很明显的异或，但是没有进位。那么怎么处理进位呢。
这里先举个例子，如下：
0010 0011 这两个进位是在第二位（从右到左），使用位与运算可得到，得进位到第三位（从右到左），那么我们只需要往左边移动一位（<<1）即可得到进位。以下只要一直重复此过程，直到进位为0的时候，那么异或得到的即是两个数字相加的结果。
public static int getSum(int a, int b) {
if(b == 0) {
return a;
}
int m = a ^ b;
int n = (a & b) << 1;
return getSum(m,n);
}
测试
public static void main(String[] args) {
int a = 5,b = 7;
System.out.println(getSum(a, b));
}
结果
