寻找重复数 leetcode hot100 最后一题
思路：当成链表找环处理。每到一个位置i 那下一次就到arr[i]对应的位置。显然入环节点就是重复的数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| public int findDuplicate(int[] nums) {
int kuai = 0;
int man = 0;
while(true){
kuai = nums[nums[kuai]];
man = nums[man];
if(kuai == man){
kuai = 0;
while(kuai != man){
kuai = nums[kuai];
man = nums[man];
}
return kuai;
}
}
}
|
接雨水
思路：初始版，类似与前缀和跟后缀和，我开两个数组记录i左边的最大值和右边的最大值，然后求出当前位置能接的雨水。sum+=Math.max(0,Math.min(left[i],right[i])-nums[i])
优化: 双指针思路，左右两边各一个指针。并且维护两个变量记录，左指针左边的最大值和右指针右边的最大值。对于左指针来说左边的最大值肯定是确定的，右指针同理。所以只需要判断两边谁的最大值更小，那么这一边就可以结算了，并且移动指针，更新最大值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| public int trap(int[] height) {
int l =1,r=height.length-2,lmax = height[0],rmax = height[height.length-1],sum=0;
while(l<=r){
if(lmax>=rmax){
sum+=Math.max(0,rmax-height[r]);
rmax = Math.max(rmax,height[r--]);
}else {
sum+=Math.max(0,lmax-height[l]);
lmax= Math.max(lmax,height[l++]);
}
}
return sum;
}
|
胖娃坐船
给定数组 people 。people[i]表示第 i 个人的体重 ，船的数量不限，每艘船可以承载的最大重量为 limit。
每艘船最多可同时载两人，但条件是这些人的重量之和最多为 limit。
返回 承载所有人所需的最小船数 。
思路：排序，然后双指针，一个指针指向最轻的，一个指针指向最重的，如果最轻的+最重的<=limit，那么可以一起载，两个指针同时移动，ans++。否则，最重的指针移动,ans++。即胖子自己一个船。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| public int numRescueBoats(int[] people, int limit) {
Arrays.sort(people);
int n =people.length;
int l =0;
int r =n-1;
int ans = 0;
while(l<=r){
if(people[r]+people[l] <= limit){
r--;
l++;
}else {
r--;
}
ans++;
}
return ans;
}
|
变种：如果要求两个的体重加起来等于偶数呢？ 很简单，分为奇偶两个数组，然后分别处理，把两个结果加起来即可。
供暖器
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| public int findRadius(int[] houses, int[] heaters) {
Arrays.sort(houses);
Arrays.sort(heaters);
int result = 0;
int heaterIndex = 0;
for (int house : houses) {
while (heaterIndex < heaters.length - 1 &&
Math.abs(heaters[heaterIndex] - house) >=
Math.abs(heaters[heaterIndex + 1] - house)) {
heaterIndex++;
}
result = Math.max(result, Math.abs(heaters[heaterIndex] - house));
}
return result;
}
|
缺失的第一个正数
给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
思路：我现在就想让每个位置都对应，即i位置上放的就是i+1。此时，我维护两个指针，l的左边是满足我这个条件的，r的右边是肯定不满足的垃圾。初始化l=0,r=n。
现在开始遍历：每次都观察l位置上的是否满足，如果满足那就l++。如果不满足判断它是不是我需要的，即它在不在当前l到r范围内（因为小于l的已经就位了，不需要你，大于r的已经超过了，不需要你）。关于为什么大于r就算超过这里解释一下。因为理想状态下我数组长度为n那么我就有1-n这些数，但一旦一个数不满足（r—），那我肯定到不了n了,最大就是r。还有一种情况，现在我需要你，但是在num[num[l]-1] 已经有一个相同的你了，说明你重复了。所以也会被当成垃圾。以上三种情况会被当成垃圾，跟—r位置交换。剩下最后一种情况，你是我需要的而且你还没到应该到的位置，于是我把你交换到对应的位置。下次循环，继续看i位置的数。 直到l<r。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
public static int firstMissingPositive(int[] arr) {
int l = 0;
int r = arr.length;
while (l < r) {
if (arr[l] == l + 1) {
l++;
} else if (arr[l] <= l || arr[l] > r || arr[arr[l] - 1] == arr[l]) {
swap(arr, l, --r);
} else {
swap(arr, l, arr[l] - 1);
}
}
return l + 1;
}
|
wechat