力扣面试经典150题

链接：面试经典 150 题 - 学习计划 - 力扣（LeetCode）全球极客挚爱的技术成长平台

1.合并两个有序数组

思路：

双指针，逆向填充nums1

代码：

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int l=nums1.length-1;
        int i=m-1,j=n-1;
        while(i>=0&&j>=0){
            if(nums1[i]>nums2[j]){
                nums1[l--]=nums1[i];
                i--;
            }else{
                nums1[l--]=nums2[j];
                j--;
            }
        }
        while(i>=0){
            nums1[l--]=nums1[i--];
        }
        while(j>=0){
            nums1[l--]=nums2[j--];
        }
    }
}

2.移除元素

思路：快慢指针，快指针探索，慢指针填充

代码：

class Solution {
    public int removeElement(int[] nums, int val) {
        int i=0,j=0;
        int len=nums.length;
        int sum=0;
        while(j
            if(nums[j]!=val){
                nums[i]=nums[j];
                i++;
                sum++;
            }
            j++;
        }
        return sum;
    }
}

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

思路：数组是非严格递增的，所以重复项都是紧挨着的。使用快慢指针，快指针探索，慢指针填充

代码：

class Solution {
    public int removeDuplicates(int[] nums) {
        int i=1,j=1;
        int len=nums.length;
        int sum=1;
        while(j
            if(nums[j]!=nums[j-1]){
                nums[i]=nums[j];
                i++;
                sum++;
            }
            j++;
        }
        return sum;
    }
}

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

思路：所有元素最多可以出现两次，所以将nums[j]!=nums[i-2]的纳入囊中，注意为什么不是j-2，因为只需要考虑结果集中元素。

代码：

class Solution {
    public int removeDuplicates(int[] nums) {
        int i = 2,j = 2;
        int len = nums.length;
        int sum=2;
        while(j
            if(nums[j]!=nums[i-2]){
                nums[i]=nums[j];
                i++;
                sum++;
            }
            j++;
        }
        return sum;
    }
}

5.多数元素

思路：出现次数大于 ⌊ n/2 ⌋ 的元素一定是数组的中位数，只需要将数组排序取中位数即可

代码：

class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length/2];
    }
}

6.轮转数组

思路：复制nums数组，每个元素向右移k个位置后会处于nums[(i+k)%nums.length]位置，然后用复制出的数组进行赋值

代码：

class Solution {
    public void rotate(int[] nums, int k) {
        int []newNums=Arrays.copyOf(nums, nums.length);
        for(int i=0;i
            nums[(i+k)%nums.length]=newNums[i];
        }
    }
}

7.买卖股票的最佳时机

思路：找出给定数组中两个数字之间的最大差值（最大利润）并且第二个数字（卖出价格）必须大于第一个数字（买入价格）。每一天考虑这么一个问题：如果我是在历史最低点买进的，那么我今天卖出能赚多少钱？当考虑完所有天数之时，我们就得到了最好的答案。minPrice用来记录今天前的最低价，maxProfit用来记录最大利润

代码：

class Solution {
    public int maxProfit(int[] prices) {
        int minPrice=Integer.MAX_VALUE;
        int maxProfit=0;
        int len=prices.length;
        for(int