当ChatGpt走进面试间 - 爱吱声

public static int findSingleNumber(int[] arr) {
int[] bitSum = new int[32];
for (int i = 0; i < arr.length; i++) {
int bitMask = 1;
for (int j = 31; j >= 0; j--) {
int bit = arr[i] & bitMask;
if (bit != 0) {
bitSum[j] += 1;
}
bitMask = bitMask << 1;
}
}
int result = 0;
for (int i = 0; i < 32; i++) {
result = result << 1;
result += bitSum[i] % 3;
}
return result;
}

复制代码

public class Fraction {
private int numerator;
private int denominator;
public Fraction(int numerator, int denominator) {
if (denominator == 0) {
throw new IllegalArgumentException("分母不能为0");
}
this.numerator = numerator;
this.denominator = denominator;
}
public Fraction add(Fraction fraction) {
int numerator = this.numerator * fraction.denominator + fraction.numerator * this.denominator;
int denominator = this.denominator * fraction.denominator;
return new Fraction(numerator, denominator);
}
public Fraction subtract(Fraction fraction) {
int numerator = this.numerator * fraction.denominator - fraction.numerator * this.denominator;
int denominator = this.denominator * fraction.denominator;
return new Fraction(numerator, denominator);
}
public Fraction multiply(Fraction fraction) {
int numerator = this.numerator * fraction.numerator;
int denominator = this.denominator * fraction.denominator;
return new Fraction(numerator, denominator);
}
public Fraction divide(Fraction fraction) {
int numerator = this.numerator * fraction.denominator;
int denominator = this.denominator * fraction.numerator;
return new Fraction(numerator, denominator);
}
public Fraction simplify() {
int gcd = gcd(this.numerator, this.denominator);
return new Fraction(this.numerator / gcd, this.denominator / gcd);
}
private int gcd(int a, int b) {
if (b == 0) {
return a;
}
return gcd(b, a % b);
}
@Override
public String toString() {
if (this.numerator == 0) {
return "0";
}
if (this.denominator == 1) {
return String.valueOf(this.numerator);
}
return this.numerator + "/" + this.denominator;
}
}

复制代码

方法一：通过哈希表来实现。我们可以遍历数组，用哈希表记录每个数字出现的次数，如果某个数字只出现了一次，那么就找到了答案。

方法二：使用异或运算。对于每个数字，我们可以使用异或运算将其与之前的数字进行比较，如果最终的结果是非零的，那么就找到了只出现一次的数字。

以下是用 Python 实现这个程序的示例代码：

# 读取数据
arr = [1, 2,  2,1, 1, 2, 3]

# 方法一：使用哈希表来实现
def find_single_with_hash(arr):
# 初始化一个哈希表
hash_map = {}
for ele in arr:
      if ele in hash_map:
         hash_map[ele] += 1
      else:
         hash_map[ele] = 1
# 遍历哈希表，找出只出现一次的数字
for k, v in hash_map.items():
      if v == 1:
         return k
return None

# 方法二：使用异或运算
def find_single_with_xor(arr):
res = 0
for ele in arr:
      res ^= ele
return res

# 测试
print(find_single_with_hash(arr))
print(find_single_with_xor(arr))