面试经典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;
}

如果右边扔进来的也是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;}
}

精简的思路决定一切

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;}
}

双指针的思路。

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;}}
}

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;}

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;}
}

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;}
}

274.H指数

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

Arrays.sort(citations);
int h = 0, i = citations.length - 1; 
while (i >= 0 && citations[i] > h) {h++; i--;
}
return h;

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