一维模拟
# 189. 轮转数组 (opens new window)
方法一：数学
class Solution {
public void rotate(int[] nums, int k) {
int n = nums.length;
k %= n;
int cnt = gcd(k,n);
for(int i=0;i<cnt;i++){
int cur = i;
int anchor = nums[i];
do{
int nxt = (cur+k)%n;
int tmp = nums[nxt];
nums[nxt] = anchor;
anchor = tmp;
cur = nxt;
}while(i!=cur);
}
}
int gcd(int x,int y){
return y>0?gcd(y,x%y):x;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
方法二：反转三次
nums = "----->-->"; k =3 result = "-->----->"; reverse "----->-->" we can get "<--<-----" reverse "<--" we can get "--><-----" reverse "<-----" we can get "-->----->"1
2
3
4
5
6
class Solution {
public 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);
}
void reverse(int[] nums,int a,int b){
int i=a,j=b;
while(i<j){
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
i++;
j--;
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 238. 除自身以外数组的乘积 (opens new window)
class Solution {
public int[] productExceptSelf(int[] nums) {
int l=1,r=1;
int[] ret = new int[nums.length];
for(int i=0;i<nums.length;i++){
ret[i] = l;
l *= nums[i];
}
for(int j=nums.length-1;j>=0;j--){
ret[j] *= r;
r *= nums[j];
}
return ret;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 414. 第三大的数 (opens new window)
class Solution {
public int thirdMax(int[] nums) {
Arrays.sort(nums);
int cnt = 1;
int n = nums.length-1;
for(int i=n;i>0;i--){
if(nums[i]!=nums[i-1] && ++cnt==3){
return nums[i-1];
}
}
return nums[n];
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
2
3
4
5
6
7
8
9
10
11
12
13
# 495. 提莫攻击 (opens new window)
class Solution {
public int findPoisonedDuration(int[] timeSeries, int duration) {
int ans=0,end=0;
for(int i=0;i<timeSeries.length;i++){
ans += duration;
if(timeSeries[i]<=end){
ans -= end-timeSeries[i];//去重复时间
}
end = timeSeries[i]+duration;
}
return ans;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
2
3
4
5
6
7
8
9
10
11
12
13
# 628. 三个数的最大乘积 (opens new window)
class Solution {
public int maximumProduct(int[] nums) {
Arrays.sort(nums);
int n = nums.length-1;
return Math.max(nums[n]*nums[n-1]*nums[n-2],
nums[0]*nums[1]*nums[n]);
}
}
1
2
3
4
5
6
7
8
2
3
4
5
6
7
8
# 274. H 指数 (opens new window)
方法一：排序
class Solution {
public int hIndex(int[] citations) {
Arrays.sort(citations);
int h = 0;
int i = citations.length-1;
while(i>=0 && citations[i]>h){
h++;
i--;
}
return h;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
2
3
4
5
6
7
8
9
10
11
12
方法二：计数排序
class Solution {
public int hIndex(int[] citations) {
int n = citations.length;
int tot = 0;
// 记录当前引用次数的论文有几篇
int[] cnt = new int[n+1];
for(int i=0;i<n;i++){
if(citations[i]>=n)
cnt[n]++;
else
cnt[citations[i]]++;
}
for(int i=n;i>=0;i--){
tot += cnt[i];
if(tot >= i)
return i;
}
return 0;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 275. H 指数 II (opens new window)
class Solution {
public int hIndex(int[] citations) {
int h=0,i=citations.length-1;
while(i>=0 && citations[i]>h){
h++;
i--;
}
return h;
}
}
1
2
3
4
5
6
7
8
9
10
2
3
4
5
6
7
8
9
10
# 453. 最小操作次数使数组元素相等 (opens new window)
class Solution {
public int minMoves(int[] nums) {
int minNum = Arrays.stream(nums).min().getAsInt();
int res = 0;
for(int num:nums){
res += num-minNum;
}
return res;
}
}
1
2
3
4
5
6
7
8
9
10
2
3
4
5
6
7
8
9
10
# 665. 非递减数列 (opens new window)
class Solution {
public boolean checkPossibility(int[] nums) {
int cnt = 0;
for(int i=1;i<nums.length;i++){
if(nums[i]<nums[i-1]){
if(i==1 || nums[i]>=nums[i-2]){
nums[i-1] = nums[i];
}else{
nums[i] = nums[i-1];
}
if(++cnt>1){
return false;
}
}
}
return true;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18