力扣爆刷第171天之TOP200五连刷121-125（跳跃游戏、买卖股票、旋转链表）

力扣爆刷第171天之TOP200五连刷121-125（跳跃游戏、买卖股票、旋转链表）

一、55. 跳跃游戏

题目链接：https://leetcode.cn/problems/jump-game/description/
思路：所谓跳跃游戏指的是，每次根据数组中元素的值来确定接下来要走的步数，看看能否走到数组尾部。本质上来说就是维护一个右边界，检测是否超出了右边界，超出了就不可抵达。维护的右边界需要不断更新。

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

二、123. 买卖股票的最佳时机 III

题目链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/description/
思路：经典的买卖股票问题，最多买卖两次，不能同时购入，问最多可剩余多少钱。
1、首先分辨本题是一个动态规划题，动态规划本身就是状态与选择。
2、对于这个问题，每一天都有两种状态，即持有股票与不持有股票，而持有股票又分为：之前就已经持有了，和今天才持有。而不持有股票又分为：之前就不持有了，和今天才刚不持有。
3、所以我们可以为每一天定义两种操作，即持有与不持有，分别计算最大值。

class Solution {public int maxProfit(int[] prices) {int[] dp = new int[4];dp[0] = -prices[0];dp[2] = -prices[0];for(int i = 1; i < prices.length; i++) {dp[0] = Math.max(dp[0], -prices[i]);dp[1] = Math.max(dp[1], dp[0] + prices[i]);dp[2] = Math.max(dp[2], dp[1] - prices[i]);dp[3] = Math.max(dp[3], dp[2] + prices[i]);}return dp[3];}
}

三、排序奇升偶降链表

题目链接：https://mp.weixin.qq.com/s/0WVa2wIAeG0nYnVndZiEXQ
思路：本题让把一个链表，奇数升序，偶数降序的链表，给进行排序，返回一个升序链表。其实不难。一共三步。
1、把链表按照奇数和偶数拆分为一个升序链表和一个降序链表。
2、把降序链表进行翻转，得到升序链表。
3、把两个升序链表进行归并排序。

public ListNode sortList(ListNode root) {ListNode head1 = new ListNode();ListNode head2 = new ListNode();// 1、按照奇数和偶数进行拆分ListNode p = root, p1 = head1, p2 = head2;while (p != null) {p1.next = p;p = p.next;p1 = p1.next;p1.next = null;if(p != null) {p2.next = p;p = p.next;p2 = p2.next;p2.next = null;}}// 2、翻转偶数对应的降序序列p2 = head2.next;ListNode pro = null;head2.next = null;while(p2 != null) {pro = p2.next;p2.next = head2.next;head2.next = p2;p2 = pro;}// 3、归并两个升序链表p1 = head1.next;p2 = head2.next;ListNode head = new ListNode();p = head;while(p1 != null && p2 != null) {if(p1.val < p2.val) {p.next = p1;p1 = p1.next;}else{p.next = p2;p2 = p2.next;}p = p.next;}if(p1 != null) p.next = p1;if(p2 != null) p.next = p2;return head.next;}

四、61. 旋转链表

题目链接：https://leetcode.cn/problems/rotate-list/description/
思路：给一个链表和一个数字k，要求把链表向右自动k位，超出部分自动移到链表首部，其实很简单。
1、首先要处理的是k，需要把k限制在链表的总长度之内，可以先遍历一遍链表，然后把k对总长度进行取余，如果为0就不用旋转了，可以直接返回。
2、这样就好办了，只需要使用快慢指针，快指针先走k步，然后快慢指针同步向右走，当快指针抵达结尾处，慢指针指向的位置就是倒数第K个节点。
3、然后从慢指针位置截断，把右边的链表拼接到头结点上即可。

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode rotateRight(ListNode head, int k) {if(head == null || head.next == null) return head;// 1、对K进行取余，使得旋转位数小于总长度int count = 0;ListNode p = head;while(p != null) {count++;p = p.next;}k = k % count;if(k == 0) return head;// 2、快慢指针，定位到倒数第k个位置ListNode slow = head, fast = head;for(int i = 0; i < k; i++) {fast = fast.next;}while(fast.next != null) {fast = fast.next;slow = slow.next;}p = slow.next;slow.next = null;fast.next = head;return p;}
}

五、7. 整数反转

题目链接：https://leetcode.cn/problems/reverse-integer/description/
思路：整数翻转也属于经典题目了，只需要每次取余得到的余数作为新数的基数，然后每次对基数乘10左移，对原数除10截短，期间判断是否超限。

class Solution {public int reverse(int x) {int res = 0, min = Integer.MIN_VALUE / 10, max = Integer.MAX_VALUE / 10;int a = Integer.MIN_VALUE % 10, b = Integer.MAX_VALUE % 10;while(x != 0) {int temp = x % 10;if(res < min || (res == min && temp < a)) return 0;if(res > max || (res == max && temp > b)) return 0;res = res * 10 + temp;x = x / 10;}return res;}
}