面试经典150题【1-10】

面试经典150题【1-10】

88. 合并两个有序数组

逆向双指针，打卡题

27.移除元素

也是逆向双指针，不过要注意思路和代码的简洁

public static int removeElement(int[] nums, int val) {
    int left = 0;
    int right = nums.length;
    while (left < right) {
        if (nums[left] == val) {
            nums[left] = nums[right - 1];
            right--;
        } else {
            left++;
        }
    }
    return left;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

如果右边扔进来的也是val,那么在下一次循环的时候还会再扔。
也能解决[3,3],val=3的这种情况。
要注意他写的是，只左移动（right–)或只右移动(left++)

26.删除有序数组中的重复项

class Solution {
    public int removeDuplicates(int[] nums) {
        int index = 0;
        for (int i = 1; i < nums.length; i++) {
            //找到不重复的元素，赋值到数组的开头
            if (nums[i] != nums[index]) {
                nums[++index] = nums[i];
            }
        }
        return index + 1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

精简的思路决定一切

80.删除有序数组中的重复项II

class Solution {
    public int removeDuplicates(int[] nums) {
        int n=nums.length;
        if(n<2) {
            return n;
        }
        int slow=2,fast=2;
        while(fast<n){
            if(nums[fast]!=nums[slow-2]){
                nums[slow]=nums[fast];
                slow++;
            }
            fast++;
        }
        return slow;

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

双指针的思路。

169.多数元素

摩尔投票法，很简单。

189.轮转数组

1.开辟一个新数组去做，然后再拷贝回原数组
public static void arraycopy(Object src, int srcPos, Object dest, int destPos, int length)
参数
src − 这是源数组。
srcPos − 这是源数组中的起始位置。
dest − 这是目标数组。
destPos − 这是目标数据中的起始位置。
length − 这是要复制的数组元素的数量。
2.新开辟一个数组，空间太大了。可以只新建一个临时变量temp
1，4，7，3，6，2，5，1.是有顺序的，也可能是几个顺序环。反正只搞一个变量也够用
3.先全部倒转，7，6，5，4，3，2，1
然后倒转前k个，还有后面的几个。5，6，7，1，2，3，4即为答案。

class Solution {
    public void rotate(int[] nums, int k) {
        k %= nums.length;
        reverse(nums, 0, nums.length - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.length - 1);
    }

    public void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start += 1;
            end -= 1;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

121.买卖股票的最佳时机1

 public int maxProfit(int[] prices) {
        int profit=0,lowestPrice=Integer.MAX_VALUE;
        for(int i=0;i<prices.length;i++){
            lowestPrice=Math.min(lowestPrice,prices[i]);
            profit=Math.max(profit,prices[i]-lowestPrice);
        }
        return profit;
        
    }
1
2
3
4
5
6
7
8
9

122. 买卖股票的最佳时机 II

在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。
就是可以多次购买和出售的意思。
那直接求所有正梯度的和就行。

55.跳跃游戏

从前往后去刷就行

class Solution {
    public boolean canJump(int[] nums) {
        if(nums.length==1){
           return true;
        }
        int cover =nums[0];
        for(int i=0;i<=cover;i++){
            cover=Math.max(cover,nums[i]+i);
            if(cover>=nums.length-1){
                return true;
            }
        }
        return false;

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

45.跳跃游戏II

class Solution {
    public int jump(int[] nums) {
        if(nums.length==1) return 0;
        int nextEnd=nums[0],end=0;
        int ans=0;
        //是nums.length-1，要遍历所有
        for(int i=0;i<nums.length-1;i++){
            nextEnd=Math.max(nextEnd,i+nums[i]);
            //到达一步的终点之后，找累计到此的下一步的终点
            if(end==i){
                ans++;
                end=nextEnd;
            }
        }
        return ans;

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

274.H指数

一种就是先排序，然后从后往前判断是不是H指数

Arrays.sort(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

或者定义一个大数组来计数，这个数组也不是很大，因为H指数最大就是n
int[] counter = new int[n + 1];
然后统计，然后从后往前找H指数。
或者对H值进行二分，0-N的范围。总共要执行LogN轮，每次执行需要N（看是否满足H值条件）。