广东省两学一做网站,最好的免费软件网站建设,4399游戏官网入口,xampp使用教程 wordpress力扣爆刷第153天之TOP100五连刷26-30#xff08;接雨水、环形链表、最长上升子序列#xff09; 文章目录 力扣爆刷第153天之TOP100五连刷26-30#xff08;接雨水、环形链表、最长上升子序列#xff09;一、300. 最长递增子序列二、415. 字符串相加三、143. 重排链表四、42.…力扣爆刷第153天之TOP100五连刷26-30接雨水、环形链表、最长上升子序列 文章目录 力扣爆刷第153天之TOP100五连刷26-30接雨水、环形链表、最长上升子序列一、300. 最长递增子序列二、415. 字符串相加三、143. 重排链表四、42. 接雨水五、142. 环形链表 II 一、300. 最长递增子序列
题目链接https://leetcode.cn/problems/longest-increasing-subsequence/description/ 思路求最长递增子序列典型的动态规划题定义dp数组表示dp[i]为以nums[i]为结尾的区间中的最长递增子序列。那么对于dp[i]来说区间中的每一个元素都有可能是最长递增子序列的一部分对于每一个区间从千往后遍历寻找。
class Solution {public int lengthOfLIS(int[] nums) {int[] dp new int[nums.length];Arrays.fill(dp, 1);int max 1;for(int i 1; i nums.length; i) {for(int j 0; j i; j) {if(nums[j] nums[i]) {dp[i] Math.max(dp[i], dp[j]1);}}max Math.max(dp[i], max);}return max;}
}
二、415. 字符串相加
题目链接https://leetcode.cn/problems/add-strings/description/ 思路字符串相加这也是非常经典的题目主要是边界条件的控制利用 || 或条件不全为0的情况下不会推出循环来完成不等长字符串的相加以及进位的相加。注意使用stringbuilder添加完成后翻转。
class Solution {public String addStrings(String num1, String num2) {int i num1.length() - 1, j num2.length() - 1;int res 0;StringBuilder sb new StringBuilder();while(i 0 || j 0 || res ! 0) {int a i 0 ? num1.charAt(i) - 0 : 0;int b j 0 ? num2.charAt(j) - 0 : 0;int sum res a b;res sum / 10;sb.append(sum % 10);i--;j--;}return sb.reverse().toString();}
}三、143. 重排链表
题目链接https://leetcode.cn/problems/reorder-list/description/ 思路题目要求如下重排其实很简单只需要找到链表中点然后把中点后面的节点翻转然后再逐个拼接。 如1 2 3 4 5中点3 后面翻转 5 4 然后得到了两个链表1 2 3和 5 4 然后逐一拼接即可得到1 5 2 4 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 void reorderList(ListNode head) {ListNode root new ListNode(-1, head);ListNode slow root, fast root;while(fast ! null fast.next ! null) {slow slow.next;fast fast.next.next;}ListNode p slow.next, pre null;slow.next null;while(p ! null) {pre p.next;p.next slow.next;slow.next p;p pre;}fast slow.next;slow.next null;slow head;while(fast ! null) {ListNode t1 slow.next;ListNode t2 fast.next;slow.next fast;fast.next t1;slow t1;fast t2;}}
}四、42. 接雨水
题目链接https://leetcode.cn/problems/trapping-rain-water/description/ 思路接雨水单调栈。只需要用单调栈构建出来一个凹槽即可即当前元素小于等于栈顶元素即入栈大于栈顶元素则出栈出栈出来的就是凹槽的底部当前元素是凹槽的右边现在的栈顶是凹槽的左边这样就可以计算凹槽的长和宽进行面积计算。
class Solution {public int trap(int[] height) {LinkedListInteger stack new LinkedList();int sum 0;for(int i 0; i height.length; i) {while(!stack.isEmpty() height[i] height[stack.peek()]) {int mid height[stack.pop()];if(!stack.isEmpty()) {int w i - stack.peek() - 1;int h Math.min(height[i], height[stack.peek()]) - mid;sum w * h;}}stack.push(i);}return sum;}
}五、142. 环形链表 II
题目链接https://leetcode.cn/problems/linked-list-cycle-ii/description/ 思路求环形链表的入口也是一道经典的题目快慢指针如果相遇则说明有环然后两个指针一个从头结点出发一个从相遇节点出发再次相遇即为环的入口。
public class Solution {public ListNode detectCycle(ListNode head) {ListNode slow head, fast head;while(fast ! null fast.next ! null) {slow slow.next;fast fast.next.next;if(slow fast) break;}if(fast null || fast.next null) return null;fast slow;slow head;while(fast ! slow) {slow slow.next;fast fast.next;}return slow;}
}
