本文主要是介绍力扣爆刷第118天之CodeTop100五连刷76-80,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
力扣爆刷第118天之CodeTop100五连刷76-80
文章目录
- 力扣爆刷第118天之CodeTop100五连刷76-80
- 一、221. 最大正方形
- 二、240. 搜索二维矩阵 II
- 三、162. 寻找峰值
- 四、234. 回文链表
- 五、112. 路径总和
一、221. 最大正方形
题目链接:https://leetcode.cn/problems/maximal-square/description/
思路:求最大的正方形,可以定义dp[i][j]表示nums[i][j]=1时,且以它为右下角的正方形的最长边长,有了定义以后就要想办法找出状态之间的转移,右下角是依赖于左边,上边,左上角的,关系如何传递?右下角的边长应该是这三个边长中最短的加1。由此便可以达到递推公式:dp[i+1][j+1] = Math.min(Math.min(dp[i+1][j], dp[i][j+1]), dp[i][j]) + 1;
class Solution {public int maximalSquare(char[][] matrix) {int m = matrix.length, n = matrix[0].length, max = matrix[0][0] - '0';int[][] dp = new int[m+1][n+1];for(int i = 0; i < m; i++) {for(int j = 0; j < n; j++) {if(matrix[i][j] == '0') continue;if(i == 0 || j == 0) {dp[i+1][j+1] = 1;}else{dp[i+1][j+1] = Math.min(Math.min(dp[i+1][j], dp[i][j+1]), dp[i][j]) + 1;}max = Math.max(max, dp[i+1][j+1]);}}return max * max;}
}
二、240. 搜索二维矩阵 II
题目链接:https://leetcode.cn/problems/search-a-2d-matrix-ii/description/
思路:矩阵本身是从左往右递增,从上往下递增,所以要利用这个特性,当前位置的左边都是比它小的,当前位置的下边都是比它大的,从右上角开始向左或者向下寻找,深度优先递归即可。
class Solution {boolean flag = false;public boolean searchMatrix(int[][] matrix, int target) {dfs(matrix, target, 0, matrix[0].length-1);return flag;}void dfs(int[][] matrix, int target, int x, int y) {if(x < 0 || x >= matrix.length || y < 0 || y >= matrix[0].length || flag) return;if(matrix[x][y] == target) {flag = true;return;}else if(target < matrix[x][y]) {dfs(matrix, target, x, y-1);}else{dfs(matrix, target, x+1, y);}}}
三、162. 寻找峰值
题目链接:https://leetcode.cn/problems/find-peak-element/description/
思路:题目要求时间复杂度log n,显然要使用二分查找,不过本题的二分查找因为没有一个明确的目的,是要去左区间还是右区间,那就是全部都要去,都要遍历,所以就是一个二叉树的遍历,相当于要前序遍历二叉树,剩下的就是判断和边界条件了,以及早停。
class Solution {int flag = -1;public int findPeakElement(int[] nums) {if(nums.length == 1) return 0;bs(nums, 0, nums.length-1);return flag;}void bs(int[] nums, int left, int right) {if(left > right || flag != -1) return ;int mid = left + (right - left) / 2;if(mid-1 == -1) {if(nums[mid] > nums[mid+1]) {flag = mid;return ;}}else if(mid+1 == nums.length) {if(nums[mid] > nums[mid-1]) {flag = mid;return ;}}else if(nums[mid] > nums[mid-1] && nums[mid] > nums[mid+1]) {flag = mid;return ;}bs(nums, left, mid-1);bs(nums, mid+1, right);}
}
四、234. 回文链表
题目链接:https://leetcode.cn/problems/palindrome-linked-list/description/
思路:链表求回文,可以快慢指针找到链表中间节点,然后翻转后半部分,然后比较,另外就是要注意链表的奇偶个数,要做一下处理。
class Solution {public boolean isPalindrome(ListNode head) {ListNode slow = head, fast = head;while(fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;}if(fast != null) slow = slow.next;fast = reverse(slow);slow = head;while(fast != null) {if(slow.val != fast.val) return false;slow = slow.next;fast = fast.next;}return true;}ListNode reverse(ListNode node) {ListNode root = new ListNode();ListNode p = node, pre = null;while(p != null) {pre = p.next;p.next = root.next;root.next = p;p = pre;}return root.next;}
}
五、112. 路径总和
题目链接:https://leetcode.cn/problems/path-sum/description/
思路:路径总和很简单,就是在二叉树中使用回溯算法,思路和典型的回溯类似,确定好收集结果的点,前序遍历,当前节点左右子树遍历完,向上返回时要去掉前面添加的状态。
class Solution {boolean flag = false;int sum = 0;public boolean hasPathSum(TreeNode root, int targetSum) {order(root, targetSum);return flag;}void order(TreeNode root, int targetSum) {if(root == null || flag) return;sum += root.val;if(root.left == null && root.right == null) {if(sum == targetSum){flag = true;return;}}order(root.left, targetSum);order(root.right, targetSum);sum -= root.val;}
}
这篇关于力扣爆刷第118天之CodeTop100五连刷76-80的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!