一、消失的数字
数组 nums 包含从 0 到 n 的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数。在 O(n)时间内完成
1.异或运算:
public int missingNumber(int[] nums) {
int[] arr = new int[nums.length + 1];
int sum = 0;
for (int i = 0; i < arr.length; i++) {
sum ^= i;
}
for (int i = 0; i < nums.length ; i++) {
sum ^= nums[i];
}
return sum;
}1
2
3
4
5
6
7
8
9
10
11
2.空间换时间:
public int missingNumber1(int[] nums) {
int[] arr = new int[nums.length+1];
for (int i = 0; i < nums.length; i++) {
arr[nums[i]] = 1;
}
for (int i = 0; i < arr.length; i++) {
if(arr[i] != 1) {
return i;
}
}
return -1;
}1
2
3
4
5
6
7
8
9
10
11
12
二、轮转数组
给你一个数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数
这是之前写过一篇专门是旋转数组的:旋转数组三种方式
上面的思路是针对于左旋数组，对右旋数组只需要稍加修改即可
public static void reverse(int[] arr,int left,int right) {
while(left < right) {
int ret = arr[left];
arr[left] = arr[right];
arr[right] = ret;
left++;
right--;
}
}
public static void rotate(int[] nums, int k) {
k = k % nums.length;
reverse(nums,0,nums.length-1);
reverse(nums,0,k-1);
reverse(nums,k,nums.length-1);
System.out.println(Arrays.toString(nums));
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
三、存在重复元素
给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false
public boolean containsDuplicate(int[] nums) {
HashMap<Integer,Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
if(map.containsKey(nums[i])) {
return true;
}
map.put(nums[i],i);
}
return false;
}1
2
3
4
5
6
7
8
9
10
四、寻找峰值
给定一个长度为n的数组nums，请你找到峰值并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个所在位置即可。
1.峰值元素是指其值严格大于左右相邻值的元素。严格大于即不能有等于
2.假设 nums[-1] = nums[n] = -\infty−∞
3.对于所有有效的 i 都有 nums[i] != nums[i + 1]
4.你可以使用O(logN)的时间复杂度实现此问题吗？
public static int findPeakElement (int[] nums) {
if(nums == null || nums.length == 0) {
return -1;
}
if(nums.length == 1) {
return 0;
}
if(nums[0] > nums[1]) {
return 0;
}
if(nums[nums.length-1] > nums[nums.length-2]) {
return nums.length - 1;
}
int left = 0;
int right = nums.length - 1;
while(left < right) {
int mid = (left + right) / 2;
if(nums[mid] < nums[mid+1]) {
left = mid + 1;
}else {
right = mid;
}
}
return left;
}
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
五、珠玑妙算游戏
计算机有4个槽，每个槽放一个球，颜色可能是红色（R）、黄色（Y）、绿色（G）或蓝色（B）。例如，计算机可能有RGGB 4种（槽1为红色，槽2、3为绿色，槽4为蓝色）。作为用户，你试图猜出颜色组合。打个比方，你可能会猜YRGB。要是猜对某个槽的颜色，则算一次“猜中”；要是只猜对颜色但槽位猜错了，则算一次“伪猜中”。注意，“猜中”不能算入“伪猜中”。
给定一种颜色组合solution和一个猜测guess，编写一个方法，返回猜中和伪猜中的次数answer，其中answer[0]为猜中的次数，answer[1]为伪猜中的次数。
public static int[] masterMind(String solution, String guess) {
int[] arr = new int[2];
char[] ch = solution.toCharArray();
char[] c = guess.toCharArray();
for (int i = 0; i < c.length; i++) {
if(c[i] == ch[i]) {
arr[0]++;
ch[i] = 0;
c[i] = 1;
}
}
for (int i = 0; i < c.length; i++) {
for (int j = 0; j < guess.length(); j++) {
if(c[i] == ch[j]) {
ch[j] = 0;
arr[1]++;
