力扣爆刷第108天之CodeTop100五连刷26-30

力扣爆刷第108天之CodeTop100五连刷26-30

一、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) {Deque<Integer> 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;}
}