给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
请你 合并nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
**注意：**最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
解法：
合并之后，直接排序 Arrays.sort(nums1);
新建数组，用双指针拷贝到新数组中，最后把数组拷贝回原来的nums1.
双指针从后面开始，这样就有位置放多余的元素，不用新建数组。
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int p1 = m - 1, p2 = n - 1;
int tail = m + n - 1;
int cur;
while (p1 >= 0 || p2 >= 0) {
if (p1 == -1) {
cur = nums2[p2--];
} else if (p2 == -1) {
cur = nums1[p1--];
} else if (nums1[p1] > nums2[p2]) {
cur = nums1[p1--];
} else {
cur = nums2[p2--];
}
nums1[tail--] = cur;
}
}
}
class Solution {
public int removeElement(int[] nums, int val) {
int n = nums.length;
int left = 0;
for (int right = 0; right < n; right++) {
if (nums[right] != val) {
nums[left] = nums[right];
left++;
}
}
return left;
}
}
class Solution {
public 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;
}
}
class Solution {
public int removeDuplicates(int[] nums) {
int n = nums.length;
if (n == 0) {
return 0;
}
int fast = 1, slow = 1;
while (fast < n) {
if (nums[fast] != nums[fast - 1]) {
nums[slow] = nums[fast];
++slow;
}
++fast;
}
return slow;
}
}
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[slow - 2] != nums[fast]) {
nums[slow] = nums[fast];
++slow;
}
++fast;
}
return slow;
}
}
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;
}
}
}
解法2.使用额外的数组。
class Solution {
public void rotate(int[] nums, int k) {
int n = nums.length;
int[] newArr = new int[n];
for (int i = 0; i < n; ++i) {
newArr[(i + k) % n] = nums[i];
}
System.arraycopy(newArr, 0, nums, 0, n);
}
}
public class Solution {
public int maxProfit(int prices[]) {
int minprice = Integer.MAX_VALUE;
int maxprofit = 0;
for (int i = 0; i < prices.length; i++) {
if (prices[i] < minprice) {
minprice = prices[i];
} else if (prices[i] - minprice > maxprofit) {
maxprofit = prices[i] - minprice;
}
}
return maxprofit;
}
}
class Solution {
public int maxProfit(int[] prices) {
int ans = 0;
int n = prices.length;
for ( int i=1; i<n; i++){
ans += Math.max(0, prices[i]-prices[i-1]);
}
return ans;
}
}
解法2.动态规划
定义状态 dp[i][0]表示第 i天交易完后手里没有股票的最大利润，dp[i][1]表示第 i 天交易完后手里持有一支股票的最大利润（i从 0 开始）。
class Solution {
public int jump(int[] nums) {
int length= nums.length;
int end =0;
int maxPosition=0;
int steps=0;
for ( int i=0;i< length-1; i++){
maxPosition = Math.max(maxPosition, i+nums[i]);
if(i ==end ){
end = maxPosition;
steps++;
}
}
return steps;
}
}
class Solution {
public int hIndex(int[] citations) {
Arrays.sort(citations);
int h = 0, i = citations.length - 1;
//考虑什么时候h需要加一,找到了一篇被引用了至少 h+1 次的论文
//为什么是citations[i] > h，而不是>=呢？考虑只有1个元素的情况，citations[0]=0,h=0,得到的结果应该是0而不是1。
//如果当前 H 指数为 h 并且在遍历过程中找到当前值 citations[i]>h，则说明我们找到了一篇被引用了至少 h+1 次的论文，所以将现有的 h值加 1
while (i >= 0 && citations[i] > h) {
h++;
i--;
}
return h;
}
}
新建并维护一个数组 counter用来记录当前引用次数的论文有几篇，
从后向前遍历数组 counter，对于每个 0≤i≤n，在数组 counter 中得到大于或等于当前引用次数 i 的总论文数。
public class Solution {
public int hIndex(int[] citations) {
int n = citations.length, tot = 0;
int[] counter = new int[n + 1];
for (int i = 0; i < n; i++) {
//对于引用次数超过论文发表数的情况，我们可以将其按照总的论文发表数来计算即可
if (citations[i] >= n) {
counter[n]++;
} else {
counter[citations[i]]++;
}
}
for (int i = n; i >= 0; i--) {
tot += counter[i];
if (tot >= i) {
return i;
}
}
return 0;
}
}
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int n = gas.length;
int i = 0;
while (i < n) {
int sumOfGas = 0, sumOfCost = 0;
//cnt是本轮触发可以走的步数
int cnt = 0;
while (cnt < n) {
int j = (i + cnt) % n;
sumOfGas += gas[j];
sumOfCost += cost[j];
if (sumOfCost > sumOfGas) {
break;
}
cnt++;
}
if (cnt == n) {
return i;
} else {
i = i + cnt + 1;
}
}
return -1;
}
}
图解法
找到sum的最小值，并且小于0的那个点。要找的值就是下一个点：
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int sum = 0;
int min = Integer.MAX_VALUE;
int minIndex = -1;
for(int i = 0; i < gas.length; i++){
sum = sum + gas[i] - cost[i];
if(sum < min && sum < 0){
min = sum;
minIndex = i;
}
}
if(sum < 0) return -1;
return (minIndex + 1 )%gas.length;
}
}
class Solution {
public int candy(int[] ratings) {
int n = ratings.length;
int[] left = new int[n];
for ( int i=0; i< n ; i++){
if(i>0 && ratings[i] > ratings[i-1]){
left[i] = left[i-1]+1;
}else{
left[i]=1;
}
}
int right=0, ret=0;
for ( int i=n-1; i>=0; i--){
if(i < n-1&& ratings[i] > ratings[i+1]){
right++;
}else{
right=1;
}
ret += Math.max(left[i], right);
}
return ret;
}
}
为了得到 left，需要将 top 出栈。在对 top 计算能接的雨水量之后，left 变成新的 top，重复上述操作，直到栈变为空，或者栈顶下标对应的 height 中的元素大于或等于 height[i]。
class Solution {
public int trap(int[] height) {
int ans = 0;
Deque<Integer> stack = new LinkedList<Integer>();
int n = height.length;
for (int i = 0; i < n; ++i) {
//判断stack中是否还有小于当前值的元素，保证单调栈的单调性
while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
int top = stack.pop();
if (stack.isEmpty()) {
break;
}
//面积等于两边的距离乘以(两边的最小高度-当前的高度）
int left = stack.peek();
int currWidth = i - left - 1;
int currHeight = Math.min(height[left], height[i]) - height[top];
ans += currWidth * currHeight;
}
stack.push(i);
}
return ans;
}
}