襄樊大型网站建设,中国有限公司官网,yandex搜索引擎,编辑网站在线注册系统力扣爆刷第108天之CodeTop100五连刷26-30 文章目录 力扣爆刷第108天之CodeTop100五连刷26-30一、15. 字符串相加二、300. 最长递增子序列三、42. 接雨水四、43. 重排链表五、142. 环形链表 II 一、15. 字符串相加
题目链接#xff1a;https://leetcode.cn/problems/add-strin…力扣爆刷第108天之CodeTop100五连刷26-30 文章目录 力扣爆刷第108天之CodeTop100五连刷26-30一、15. 字符串相加二、300. 最长递增子序列三、42. 接雨水四、43. 重排链表五、142. 环形链表 II 一、15. 字符串相加
题目链接https://leetcode.cn/problems/add-strings/description/ 思路留一个位置记录余数每次取一个数下来进行计算然后反向拼接然后翻转即可。
class Solution {public String addStrings(String num1, String num2) {StringBuilder res new StringBuilder();int i num1.length()-1, j num2.length()-1, up 0;while(i 0 || j 0 || up ! 0) {int a i 0 ? num1.charAt(i)-0 : 0;int b j 0 ? num2.charAt(j)-0 : 0;int sum a b up;res.append(sum % 10);up sum / 10;i--;j--;}res.reverse();return res.toString();}
}二、300. 最长递增子序列
题目链接https://leetcode.cn/problems/longest-increasing-subsequence/ 思路求最长递增子序列的长度是非连续的一层for是解决不了的定义dp[i]表示区间[0, i]以nums[i]为结尾的最长递增子序列的长度求dp[i]就要遍历[0,i]每一个位置利用定义进行推导nums[j]nums[i]dp[j]是以nums[j]为结尾的区间的最大长度那么dp[i]dp[j]1。
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;}
}
三、42. 接雨水
题目链接https://leetcode.cn/problems/trapping-rain-water/description/ 思路利用单调栈构造凹槽即可栈内递减当前元素大于栈顶栈顶出栈出来的这个为凹槽底部然后利用当前元素为右边界当前栈顶为左边界结合出栈的凹槽底部进行雨水容量计算。
class Solution {public int trap(int[] height) {DequeInteger 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[stack.peek()], height[i]) - mid;sum w*h;}}stack.push(i);}return sum;}
}四、43. 重排链表
题目链接https://leetcode.cn/problems/reorder-list/description/ 思路这次写的有点丑陋下次可以拆分成三个函数来写。具体步骤为三步 第一步利用快慢指针寻找链表中点。 第二步翻转后半部分链表。 第三步前半部分和后边部分合并即可。 class Solution {public void reorderList(ListNode head) {ListNode slow head, fast head;while(fast ! null fast.next ! null) {slow slow.next;fast fast.next.next;}ListNode p slow.next, pre p;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 spre slow.next;ListNode fpre fast.next;slow.next fast;slow spre;fast.next spre;fast fpre;}}
}五、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) {slow head;while(slow ! fast) {slow slow.next;fast fast.next;}return slow;}}return null;}
}
