力扣爆刷第154天之TOP100五连刷36-40(最长公共子序列、二分、二叉树右视图)
文章目录
- 力扣爆刷第154天之TOP100五连刷36-40(最长公共子序列、二分、二叉树右视图)
- 一、1143. 最长公共子序列
- 二、94. 二叉树的中序遍历
- 三、82. 删除排序链表中的重复元素 II
- 四、704. 二分查找
- 五、199. 二叉树的右视图
一、1143. 最长公共子序列
题目链接:https://leetcode.cn/problems/longest-common-subsequence/description/
思路:求最长公共子序列也是经典题目了,和上一期的编辑距离类似,只不过本题只有删除操作,所谓的删除的操作其实是让位继承。
定义dp[i][j]表示区间text1[0, i]和区间text2[0, j]中以text1[i]和text2[j]为结尾的最长公共子序列。
那么,如果text1[i] == text2[j],长度就依赖于text1[i-1]和text2[j-1]的状态,即dp[i][j] = dp[i-1][j-1]+1.
那么,如果text1[i] != text2[j],结尾处不相等就退而求其次,要么是text1退一步,要么是text2退一步,但不管谁退,都应该保留下最长的公共子序列,即dp[i][j] = max(dp[i-1][j], dp[i][j-1])。
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
int[][] dp = new int[text1.length()+1][text2.length()+1];
for(int i = 0; i < text1.length(); i++) {
for(int j = 0; j < text2.length(); j++) {
if(text1.charAt(i) == text2.charAt(j)) {
dp[i+1][j+1] = dp[i][j]+1;
}else{
dp[i+1][j+1] = Math.max(dp[i+1][j], dp[i][j+1]);
}
}
}
return dp[text1.length()][text2.length()];
}
}
二、94. 二叉树的中序遍历
题目链接:https://leetcode.cn/problems/binary-tree-inorder-traversal/description/
思路:中序遍历很经典的题目,没什么好说的,左中右的遍历顺序,在中节点收集即可。
class Solution {
List<Integer> list = new ArrayList<>();
public List<Integer> inorderTraversal(TreeNode root) {
traverse(root);
return list;
}
void traverse(TreeNode root) {
if(root == null) return ;
traverse(root.left);
list.add(root.val);
traverse(root.right);
}
}
三、82. 删除排序链表中的重复元素 II
题目链接:https://leetcode.cn/problems/remove-duplicates-from-sorted-list-ii/description/
思路:删除链表中所有的重复的元素,所以需要三个指针,一个是前驱,一个是当前,一个是后继,如果后两个元素相等,则不停的移动后继指针,直至不等,保留前驱节点是为了方便删除。
/**
* 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 deleteDuplicates(ListNode head) {
if(head == null) return head;
ListNode root = new ListNode(-1, head);
ListNode pro = root, p = head, pre = head.next;
while(pre != null) {
if(p.val == pre.val) {
while(pre != null && p.val == pre.val) pre = pre.next;
p.next = null;
pro.next = pre;
if(pre != null) {
p = pre;
pre = pre.next;
}
}else{
pro = p;
p = pre;
pre = pre.next;
}
}
return root.next;
}
}
四、704. 二分查找
题目链接:https://leetcode.cn/problems/binary-search/description/
思路:也是很经典的题目了,二分查找就不再叙述了。
class Solution {
public int search(int[] nums, int target) {
int left = 0, right = nums.length-1;
while(left <= right) {
int mid = left + (right - left) / 2;
if(nums[mid] == target) return mid;
else if(nums[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
}
五、199. 二叉树的右视图
题目链接:https://leetcode.cn/problems/binary-tree-right-side-view/description/
思路:本题也算是一个经典题目了,可以使用层序遍历,也可以使用递归的方法,层序遍历非常简单,我就不写了,这里使用递归的方法,右视图嘛,所以先遍历右子树再遍历左子树,那么怎么能得到右视图呢,关键在于从右往左,并且优先记录第一个下探到下一层的节点,这个用全局深度来控制即可,
class Solution {
List<Integer> list = new ArrayList<>();
int max = -1;
public List<Integer> rightSideView(TreeNode root) {
traverse(root, 0);
return list;
}
void traverse(TreeNode root, int deep) {
if(root == null) return ;
if(max < deep) {
max = deep;
list.add(root.val);
}
traverse(root.right, deep+1);
traverse(root.left, deep+1);
}
}