给你两个按 非递减顺序 排列的整数数组 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;
}
}
}
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
解法：1双指针
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;
}
}
解法：
1.同样双指针，但是判断的是slow-2和fast的值是否相同
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;
}
}
给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于⌊ n/2 ⌋ 的元素。
我们遍历数组 nums 中的所有元素，对于每个元素 x，在判断 x 之前，如果 count 的值为 0，我们先将 x 的值赋予 candidate，随后我们判断 x：
如果 x 与 candidate 相等，那么计数器 count 的值增加 1；
如果 x 与 candidate 不等，那么计数器 count 的值减少 1。
在遍历完成后，candidate 即为整个数组的众数。
class Solution {
public int majorityElement(int[] nums) {
int count = 0;
Integer candidate = null;
for (int num : nums) {
if (count == 0) {
candidate = num;
}
count += (num == candidate) ? 1 : -1;
}
return candidate;
}
}
给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
解法1：
反转再反转：
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);
}
}
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
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;
}
}
给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h 指数。
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;
}
}
n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
你需要按照以下要求，给这些孩子分发糖果：
每个孩子至少分配到 1 个糖果。
相邻两个孩子评分更高的孩子会获得更多的糖果。
请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。
解法：
分别计算左右两个数组，然后取两边的最大值加起来。
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;
}
}
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
解法：
分别找到当前位置左右两边的最大高度。则最后的结果就是两边最大高度的最小值减去柱子的高度
class Solution {
public int trap(int[] height) {
int n = height.length;
if(n==0){
return 0;
}
int[] leftMax = new int[n];
leftMax[0] = height[0];
for(int i=1; i< n; i++){
leftMax[i] = Math.max(leftMax[i-1], height[i]);
}
int[] rightMax= new int[n];
rightMax[n-1] = height[n-1];
for(int i=n-2; i >=0 ; i--){
rightMax[i] = Math.max(rightMax[i+1], height[i]);
}
int ans=0;
for(int i=0;i< n; i++){
ans += Math.min(leftMax[i], rightMax[i]) - height[i];
}
return ans;
}
}
解法2.单调栈
维护一个单调栈，单调栈存储的是下标，满足从栈底到栈顶的下标对应的数组 height中的元素递减。
从左到右遍历数组，遍历到下标 i 时，如果栈内至少有两个元素，记栈顶元素为 top 的下面一个元素是 left，则一定有 height[left]≥height[top]。
为了得到 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;
}
}