[知识总结] 【CodeTop x LeetCode】Page 5 : 81-100面试高频算法题题解
作者:CC下载站 日期:2021-11-20 09:37:00 浏览:64 分类:编程开发
更多答案也可以关注我的GitHub算法仓库——Algorithm
所有代码都是在力扣上提交通过的,保证代码的正确无误
基础数据结构:
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 TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
153.寻找旋转排序数组中的最小值
二分查找的变种,想这些二分查找变种相关的题目我掌握的实际并不好,需多次练习理解
public int findMin(int[] nums) {
int l = 0;
int h = nums.length - 1;
while (l < h) {
int mid = (l + h)/2;
if (nums[mid] < nums[h]) {
h = mid;
}else {
l = mid + 1;
}
}
return nums[l];
}
排序
(纯排序题目,这里就不放代码了,之前有)
128. 最长连续序列
题目要求O(n)的时间复杂度,这里先使用Set把元素放入并去重,开始遍历,遍历数为x
- 如果存在x-1,跳过此次(因为要避免重复计算,要每次从连续数列的第一个开始计算)
- 存在x+1,继续查找更大的
- 更新结果
public int longestConsecutive(int[] nums) {
if (nums.length == 0) {
return 0;
}
Set<Integer> set = new HashSet<>();
for (int i = 0; i < nums.length; i++) {
set.add(nums[i]);
}
int res = 0;
for (int i = 0; i < nums.length; i++) {
int x = nums[i];
if (!set.contains(x-1)) {
int cur = 0;
while (set.contains(x)) {
cur++;
x++;
}
res = Math.max(res, cur);
}
}
return res;
}
62.不同路径
经典动规,不多说了
public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
for (int i = 0; i < m; i++) {
dp[i][0] = 1;
}
for (int i = 0; i < n; i++) {
dp[0][i] = 1;
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
return dp[m-1][n-1];
}
136.只出现一次的数字
要求时间O(n),空间O(1),则使用异或!
- 因为
0^a=a
,a^a=0
,所以一个数字连续两次和0异或之后为0 - 又因为异或操作满足分配律,所以一个数组里的数字连续异或之后,剩余的结果即为只出现一次的数字!
public int singleNumber(int[] nums) {
int res = 0;
for (int num : nums) {
res ^= num;
}
return res;
}
240.搜索二维矩阵 II
从右上角开始,向左下开始寻找
public boolean searchMatrix(int[][] matrix, int target) {
int row = 0;
int col = matrix[0].length - 1;
while (col >= 0 && row < matrix.length) {
if (matrix[row][col] == target) {
return true;
}
if (target < matrix[row][col]) {
col--;
}else {
row++;
}
}
return false;
}
221.最大正方形
动规,状态转移方程为dp[i][j] = Math.min(dp[i-1][j-1], Math.min(dp[i-1][j],dp[i][j-1])) + 1
,同时更新最优解
public int maximalSquare(char[][] matrix) {
int[][] dp = new int[matrix.length][matrix[0].length];
int res = 0;
for (int i = 0; i < matrix.length; i++) {
dp[i][0] = matrix[i][0] - '0';
res = Math.max(res, dp[i][0]);
}
for (int i = 0; i < matrix[0].length; i++) {
dp[0][i] = matrix[0][i] - '0';
res = Math.max(res, dp[0][i]);
}
for (int i = 1; i < dp.length; i++) {
for (int j = 1; j < dp[0].length; j++) {
if (matrix[i][j] == '0') {
continue;
}
dp[i][j] = Math.min(dp[i-1][j-1], Math.min(dp[i-1][j],dp[i][j-1])) + 1;
res = Math.max(res, dp[i][j]);
}
}
return res*res;
}
162.寻找峰值
二分变体
public int findPeakElement(int[] nums) {
int l = 0, r = nums.length - 1;
while (l < r) {
int mid = (l + r) / 2;
if (nums[mid] < nums[mid + 1]) {
l = mid + 1;
} else {
r = mid;
}
}
return l;
}
猜你还喜欢
- 03-29 [编程相关] Winform窗体圆角以及描边完美解决方案
- 03-29 [前端问题] has been blocked by CORS policy跨域问题解决
- 03-29 [编程相关] GitHub Actions 入门教程
- 03-29 [编程探讨] CSS Grid 网格布局教程
- 10-12 [编程相关] python实现文件夹所有文件编码从GBK转为UTF8
- 10-11 [编程算法] opencv之霍夫变换:圆
- 10-11 [编程算法] OpenCV Camshift算法+目标跟踪源码
- 10-11 [Python] python 创建 Telnet 客户端
- 10-11 [编程相关] Python 基于 Yolov8 + CPU 实现物体检测
- 03-15 [脚本工具] 使用go语言开发自动化脚本 - 一键定场、抢购、预约、捡漏
- 01-08 [编程技术] 秒杀面试官系列 - Redis zset底层是怎么实现的
- 01-05 [编程技术] 《Redis设计与实现》pdf
取消回复欢迎 你 发表评论:
- 精品推荐!
-
- 最新文章
- 热门文章
- 热评文章
[跨境电商] TikTok中视频课程30天线上陪跑
[电影] [摩登笑探 冇面俾].1995.HDTV1080i.国语中字
[电影] 非常偵探/The Private Eye Blues 1994
[摄影] 让手机秒变单反的手机拍摄好物
[电影](香港怀旧老电影)《情义我心知》1989.VCDRip.MKV[粤语双字]
[电影] [五个堕落的男女][HD-MKV/1.88G][国语中字][1080P]
[游戏娱乐] 《赤痕:夜之仪式》v1.50中文版
[游戏娱乐] 《极乐迪斯科》v20230509导演剪辑版
[电影] 2023年美国剧情片《包围》BD中英双字
[课程] 张景明教授《一病一讲·100集》
[资料] [大学期末救急课] 猴博士+高斯课堂+斐多课堂,全集视频合集
[云资源] 价值2万元的老男孩Python教程
[书库] 史上最全摄影书推荐(附700本PDF版打包下载)
[云资源] 花了一千多元买的私人健身教程
[下载工具] Internet Download Manager 6.42.7 (IDM)
[影视] 灌篮高手 WEB-DL版下载/Slam Dunk/スラムダンク/灌篮高手:THE FIRST/灌篮高手电影版 2022 The First Slam Dunk 61.35G
[资料] 3000 套电影电视剧 LOGO 宣传片常用音效合集包
[安卓软件] 酷我音乐APP_v10.7.6.4 去广告破解豪华VIP版
[即时通讯] 微信PC版WeChat 3.9.9.43 多开防撤回绿色版
[安卓软件] Solid Explorer文件管理器APP 2.8.38 破解版
[云资源] 价值2万元的老男孩Python教程
[影视] 灌篮高手 WEB-DL版下载/Slam Dunk/スラムダンク/灌篮高手:THE FIRST/灌篮高手电影版 2022 The First Slam Dunk 61.35G
[云资源] 花了一千多元买的私人健身教程
[书库] 史上最全摄影书推荐(附700本PDF版打包下载)
[动画] 北斗神拳(1984) [两季合集] [MKV]
[资料] 抗战阵亡将士资料+续编
[电视剧] 三体 (2024) 全8集 网飞版本 中文字幕 合集
[纪录片] 河西走廊【10集 国语 中文字幕 1080P 10.8G MP4】
[电影] 2024年喜剧片·热辣滚烫 [mp4]
[影视] 铁爪 WEB-DL版下载 2023 The Iron Claw 23.48G
- 最新评论
-
杂物房内的旧档资源不保证有效CC下载站 评论于:05-14 不能**123 评论于:05-14 我想看看mw2ddyy 评论于:04-26 好东西阿zfy123123 评论于:04-18 谢谢楼主xiaoqi 评论于:04-12 勿在线解压,勿手机解压,请在电脑上用最新款压缩软件解压!推荐360压缩或者好压CC下载站 评论于:04-10 无法解压啊,客服能不能给个解压教程ravengrey 评论于:04-10 谢谢支持!!CC下载站 评论于:03-26 很棒的资源,感谢分享云体风身 评论于:03-26 感谢分享,好东西云体风身 评论于:03-26
- 热门tag