当前位置: 首页 > news >正文

Mar 14 | Datawhale 01~04 打卡 | Leetcode面试下

第一阶段主要就是学习字符串的处理和二叉树的遍历。前一段时间学习了二叉树的遍历,记忆还比较深刻,这几个题还是比较轻松的做出来了;但是像Longest Palindromic Substring这样的题除了简单的字符串处理(回文判断),还要使用动态规划之类的算法,很久以前简单学习了一下动态规划,但一段时间不用很快就忘记了。这一题我尝试用暴力来解,但很容易就超时了。周末找个时间重新好好学习一下dp!

⚠️ 注:代码我都是用js写的,不是python!

DAY 1

3. Longest Substring Without Repeating Characters (medium)

String | Sliding Window + Hash Table

/*** @param {string} s* @return {number}*/
var lengthOfLongestSubstring = function(s) {let start = 0; // Start of the current windowlet maxLength = 0; // Maximum length of substring found so farconst map = {}; // Map to store the last index of each characterfor(let end = 0; end < s.length; end++) {const currentChar = s[end];// If the character is found in the map and is within the current window,// move the start to the next position after the last occurrence of currentCharif (map[currentChar] >= start) {start = map[currentChar] + 1;}// Update the last index of the current charactermap[currentChar] = end;// Update maxLength if the current window size is largermaxLength = Math.max(maxLength, end - start + 1);}return maxLength;
};

5. Longest Palindromic Substring (medium)

勉强通过的brute-force

/*** @param {string} s* @return {string}*/const isPalindrome = (s, l, r) => {for (let i = l, j = r; i < j; i++, j--) {if(s[i] !== s[j]) return false;}return true;
}
var longestPalindrome = function(s) {let longest = '';for (let start = 0; start < s.length; start++) {for (let end = start; end < s.length; end++) {let substr = s.substring(start, end + 1); if (isPalindrome(s, start, end) && substr.length > longest.length) {longest = substr;}}}return longest;
};

8. String to Integer (atoi) (medium)

晕 @_@ 好难cover所有testcase!

/*** @param {string} s* @return {number}*/
var myAtoi = function(s) {let i = 0, sign = 1, result = 0, INT_MAX = 2**31 - 1, INT_MIN = -(2**31);// Ignore leading whitespacewhile (s[i] === ' ') i++;// Handle signif (s[i] === '+' || s[i] === '-') {sign = s[i] === '+' ? 1 : -1;i++;}// Convert number and avoid non-digit characterswhile (i < s.length && s[i] >= '0' && s[i] <= '9') {result = result * 10 + (s[i] - '0');i++;}// Apply signresult *= sign;// Clamp to 32-bit signed integer rangeif (result < INT_MIN) return INT_MIN;if (result > INT_MAX) return INT_MAX;return result;
};

DAY 2

151. Reverse Words in a String (medium)

43. Multiply Strings (medium)

额(⊙﹏⊙),说实话没明白这题是啥意思。
不过题目说,Note: You must not use any built-in BigInteger library or convert the inputs to integer directly.
之后再仔细研究一下这题!

var multiply = function(num1, num2) {return (BigInt(num1) * BigInt(num2)).toString();
};

14. Longest Common Prefix (easy)

/*** @param {string[]} strs* @return {string}*/
var longestCommonPrefix = function(strs) {if (strs.length === 0) return "";for (let i = 0; i < strs[0].length; i++) {let c = strs[0][i];for (let j = 1; j < strs.length; j++) {if (strs[j].length <= i || strs[j][i] !== c) {return strs[0].slice(0, i);// return strs[0].substring(0, i);}}}return strs[0];
};

一点优化:先将strs 排序,然后直接选取第一个和最后一个比较。
时间复杂度:O( m ∗ n m*n mn) --> O( n l o g n + m nlog_n+m nlogn+m)

var longestCommonPrefix = function(strs) {if (strs.length === 0) return "";strs.sort();for (let i = 0; i < strs[0].length; i++) {let c = strs[0][i];if(strs[0][i] !== strs[strs.length-1][i]) {return strs[0].substring(0, i);}}return strs[0];
};

DAY 3

144. Binary Tree Preorder Traversal (easy)

const traversal = function (root, res) {if (root === null) return ;res.push(root.val);traversal(root.left, res);traversal(root.right, res);
};var preorderTraversal = function (root) {let res = [];traversal(root, res);return res;
};

94. Binary Tree Inorder Traversal (easy)

var inorderTraversal = function(root) {let res = [];traversal(root, res);return res;
};const traversal = function (root, res) {if (root === null) return;traversal(root.left, res);res.push(root.val);traversal(root.right, res);
};

102. Binary Tree Level Order Traversal (medium)

用队列,先进先出

const levelOrderTraversal = function(root, res, queue) {if(root === null) return [];queue.push(root);while(queue.length !== 0) {const length = queue.length; // the length of root array: 7let level = []; // store each level arrayfor(let i = 0; i< length; i++) {let node = queue.shift(); // take the first num, i.e. the root nodelevel.push(node.val); if(node.left) {queue.push(node.left);} if(node.right) {queue.push(node.right);}}res.push(level);}return res;
}var levelOrder = function(root) {let res = [], queue = [];levelOrderTraversal(root, res, queue);return res;
};

DAY 4

103. Binary Tree Zigzag Level Order Traversal (medium)

用层序遍历,然后隔一行翻转

var zigzagLevelOrder = function(root) {let res = [], queue = [];let zigzag = 1if(root === null) return [];queue.push(root);while(queue.length !== 0) {const length = queue.length;let level = [];for(let i = 0; i< length; i++) {let node = queue.shift();level.push(node.val); if(node.left) queue.push(node.left);if(node.right) queue.push(node.right);}if(zigzag === 1) {res.push(level);}else {res.push(level.reverse());}zigzag = -zigzag;}return res;
};

236. Lowest Common Ancestor of a Binary Tree (medium)

自底向上查找 -> 回溯 -> 后序遍历(左右中)

var lowestCommonAncestor = function(root, p, q) {function dfs(root, q, p) {if (root === q || root === p || root === null) return root;let left = dfs(root.left, q, p)let right = dfs(root.right, q, p)if(left !== null && right !== null) return root;else if(left !== null && right === null) return left;else if(left === null && right !== null) return right;else return null;}return dfs(root, q, p);
};

104. Maximum Depth of Binary Tree (easy)

层序遍历求层数,用dfs应该也能做…

var maxDepth = function(root) {let queue = [];let count = 0;queue.push(root);if (root === null) return count;while(queue.length !== 0) {let length = queue.length;for(let i =0; i < length; i++){let node = queue.shift();if(node.left) {queue.push(node.left);}if(node.right) {queue.push(node.right);}}count++;}return count;
};

相关文章:

Mar 14 | Datawhale 01~04 打卡 | Leetcode面试下

第一阶段主要就是学习字符串的处理和二叉树的遍历。前一段时间学习了二叉树的遍历&#xff0c;记忆还比较深刻&#xff0c;这几个题还是比较轻松的做出来了&#xff1b;但是像Longest Palindromic Substring这样的题除了简单的字符串处理&#xff08;回文判断&#xff09;&…...

【计算机网络】什么是http?

​ 目录 前言 1. 什么是HTTP协议&#xff1f; 2. 为什么使用HTTP协议&#xff1f; 3. HTTP协议通信过程 4. 什么是url&#xff1f; 5. HTTP报文 5.1 请求报文 5.2 响应报文 6. HTTP请求方式 7. HTTP头部字段 8. HTTP状态码 9. 连接管理 长连接与短连接 管线化连接…...

【python开发】并发编程(上)

并发编程&#xff08;上&#xff09; 一、进程和线程&#xff08;一&#xff09;多线程&#xff08;二&#xff09;多进程&#xff08;三&#xff09;GIL锁 二、多线程开发&#xff08;一&#xff09;t.start()&#xff08;二&#xff09;t.join()&#xff08;三&#xff09;t.…...

用c语言实现扫雷游戏

文章目录 概要整体架构流程代码的实现小结 概要 学习了c语言后&#xff0c;我们可以通过c语言写一些小程序&#xff0c;然后我们这篇文章主要是&#xff0c;扫雷游戏的一步一步游戏。 整体架构流程 扫雷网页版 根据上面网页版的基础扫雷可以看出是一个99的格子&#xff0c;…...

LeetCode 2882.删去重复的行

DataFrame customers ------------------- | Column Name | Type | ------------------- | customer_id | int | | name | object | | email | object | ------------------- 在 DataFrame 中基于 email 列存在一些重复行。 编写一个解决方案&#xff0c;删除这些重复行&#…...

对OceanBase进行 sysbench 压测前,如何用 obdiag巡检

有一些用户想对 OceanBase 进行 sysbench 压测&#xff0c;并向我询问是否需要对数据库的各种参数进行调整。我想起有一个工具 obdiag &#xff0c;具备对集群进行巡检的功能。因此&#xff0c;我正好借此机会试用一下这个工具。 obdiag 功能的比较丰富&#xff0c;详细情况可参…...

每天学习几道面试题|Kafka架构设计类

文章目录 1. Kafka 是如何保证高可用性和容错性的&#xff1f;2. Kafka 的存储机制是怎样的&#xff1f;它是如何处理大量数据的&#xff1f;3. Kafka 如何处理消费者的消费速率低于生产者的生产速率&#xff1f;4. Kafka 集群中的 Controller 是什么&#xff1f;它的作用是什么…...

.rmallox勒索病毒解密方法|勒索病毒解决|勒索病毒恢复|数据库修复

导言&#xff1a; 近年来&#xff0c;勒索病毒的威胁日益增加&#xff0c;其中一种名为.rmallox的勒索病毒备受关注。这种病毒通过加密文件并勒索赎金来威胁受害者。本文将介绍.rmallox勒索病毒的特点&#xff0c;以及如何恢复被其加密的数据文件&#xff0c;并提供预防措施&a…...

安卓性能优化面试题 11-15

11. 简述APK安装包瘦身方案 ?(1):剔 除掉冗余的代码与不必要的jar包;具体来讲的话,我们可以使用SDK集成的ProGuard混淆工具,它可以在编译时检查并删除未使用的类、字段、方法 和属性,它会遍历所有代码找到无用处的代码,所有那些不可达的代码都会在生成最终apk文件之前被…...

Python错题集-9PermissionError:[Errno 13] (权限错误)

1问题描述 Traceback (most recent call last): File "D:\pycharm\projects\5-《Python数学建模算法与应用》程序和数据\02第2章 Python使用入门\ex2_38_1.py", line 9, in <module> fpd.ExcelWriter(data2_38_3.xlsx) #创建文件对象 File "D:…...

QT TCP通信介绍

QT是一个跨平台的C应用程序开发框架&#xff0c;它提供了一套完整的工具和库&#xff0c;用于开发各种类型的应用程序&#xff0c;包括图形用户界面(GUI)应用程序、命令行工具、网络应用程序等。QT提供了丰富的功能和类来简化网络通信的开发&#xff0c;其中包括TCP通信。 TCP…...

保姆级教学!微信小程序设计全攻略!

微信小程序开启了互联网软件的新使用模式。在各种微信小程序争相抢占流量的同时&#xff0c;如何设计微信小程序&#xff1f;让用户感到舒适是设计师在产品设计初期应该考虑的问题。那么如何做好微信小程序的设计呢&#xff1f;即时设计总结了以下设计指南&#xff0c;希望对准…...

日期差值的计算

1、枚举所有数值进行日期判断 时间复杂度是o(n)的&#xff0c;比较慢&#xff0c;单实例能凑合用&#xff0c;多实例的话时间复杂度有点高。 核心代码就是判断某个八位数能否表示一个日期。 static int[] month {0,31,28,31,30,31,30,31,31,30,31,30,31};static String a, b…...

为什么需要Occupancy?

1.能够得到3D的占用信息 在基于BEV (鸟瞰图) 的2D预测模型中&#xff0c;我们通常仅具有二维平面&#xff08;x和y坐标&#xff09;上的信息。这种方法对于很多应用场景来说已经足够&#xff0c;但它并不考虑物体在垂直方向&#xff08;z轴&#xff09;上的分布。这限制了模型的…...

SSA优化最近邻分类预测(matlab代码)

SSA-最近邻分类预测matlab代码 麻雀搜索算法(Sparrow Search Algorithm, SSA)是一种新型的群智能优化算法&#xff0c;在2020年提出&#xff0c;主要是受麻雀的觅食行为和反捕食行为的启发。 数据为Excel分类数据集数据。 数据集划分为训练集、验证集、测试集,比例为8&#…...

nginx相关内容的安装

nginx的安装 安装依赖 yum install gcc gcc-c automake autoconf libtool make gd gd-devel libxslt-devel -y 安装lua与lua依赖 lua安装步骤如下: mkdir /www mkdir /www/server #选择你自己的目录即可,不需要跟我一致 cd /www/server tar -zxvf lua-5.4.3.tar.gz cd lua-5.4…...

基于SpringBoot和Echarts的全国地震可视化分析实战

目录 前言 一、后台数据服务设计 1、数据库查询 2、模型层对象设计 3、业务层和控制层设计 二、Echarts前端配置 1、地图的展示 2、次数排名统计 三、最终结果展示 1、地图展示 2、图表展示 总结 前言 在之前的博客中基于SpringBoot和PotsGIS的各省地震震发可视化分…...

基于YOLOv8/YOLOv7/YOLOv6/YOLOv5的农作物害虫检测系统(深度学习模型+UI界面+训练数据集)

摘要&#xff1a;开发农作物害虫检测系统对于提高农业生产效率和作物产量具有关键作用。本篇博客详细介绍了如何运用深度学习构建一个农作物害虫检测系统&#xff0c;并提供了完整的实现代码。该系统基于强大的YOLOv8算法&#xff0c;并对比了YOLOv7、YOLOv6、YOLOv5&#xff0…...

21 # 高级类型:条件类型

条件类型&#xff08;Conditional Types&#xff09;是一种高级的类型工具&#xff0c;它允许我们基于一个类型关系来选择另一个类型。条件类型通常使用条件表达式 T extends U ? X : Y 的形式&#xff0c;其中根据泛型类型 T 是否可以赋值给类型 U 来确定最终的类型是 X 还是…...

Java之List.steam().sorted(Comparator.comparing())排序异常解决方案

使用steam().sorted(Comparator.comparing())对List<T>集合里的String类型字段进行倒序排序&#xff0c;发现倒序失效。记录解决方案。 异常代码如下: customerVOList customerVOList.stream().sorted(Comparator.comparing(CustomerVOVO::getCustomerRate).reversed()…...

day52 ResNet18 CBAM

在深度学习的旅程中&#xff0c;我们不断探索如何提升模型的性能。今天&#xff0c;我将分享我在 ResNet18 模型中插入 CBAM&#xff08;Convolutional Block Attention Module&#xff09;模块&#xff0c;并采用分阶段微调策略的实践过程。通过这个过程&#xff0c;我不仅提升…...

【位运算】消失的两个数字(hard)

消失的两个数字&#xff08;hard&#xff09; 题⽬描述&#xff1a;解法&#xff08;位运算&#xff09;&#xff1a;Java 算法代码&#xff1a;更简便代码 题⽬链接&#xff1a;⾯试题 17.19. 消失的两个数字 题⽬描述&#xff1a; 给定⼀个数组&#xff0c;包含从 1 到 N 所有…...

高频面试之3Zookeeper

高频面试之3Zookeeper 文章目录 高频面试之3Zookeeper3.1 常用命令3.2 选举机制3.3 Zookeeper符合法则中哪两个&#xff1f;3.4 Zookeeper脑裂3.5 Zookeeper用来干嘛了 3.1 常用命令 ls、get、create、delete、deleteall3.2 选举机制 半数机制&#xff08;过半机制&#xff0…...

1688商品列表API与其他数据源的对接思路

将1688商品列表API与其他数据源对接时&#xff0c;需结合业务场景设计数据流转链路&#xff0c;重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点&#xff1a; 一、核心对接场景与目标 商品数据同步 场景&#xff1a;将1688商品信息…...

《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》

在注意力分散、内容高度同质化的时代&#xff0c;情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现&#xff0c;消费者对内容的“有感”程度&#xff0c;正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中&#xff0…...

VTK如何让部分单位不可见

最近遇到一个需求&#xff0c;需要让一个vtkDataSet中的部分单元不可见&#xff0c;查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行&#xff0c;是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示&#xff0c;主要是最后一个参数&#xff0c;透明度…...

uniapp微信小程序视频实时流+pc端预览方案

方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度​WebSocket图片帧​定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐​RTMP推流​TRTC/即构SDK推流❌ 付费方案 &#xff08;部分有免费额度&#x…...

Spring AI 入门:Java 开发者的生成式 AI 实践之路

一、Spring AI 简介 在人工智能技术快速迭代的今天&#xff0c;Spring AI 作为 Spring 生态系统的新生力量&#xff0c;正在成为 Java 开发者拥抱生成式 AI 的最佳选择。该框架通过模块化设计实现了与主流 AI 服务&#xff08;如 OpenAI、Anthropic&#xff09;的无缝对接&…...

第 86 场周赛:矩阵中的幻方、钥匙和房间、将数组拆分成斐波那契序列、猜猜这个单词

Q1、[中等] 矩阵中的幻方 1、题目描述 3 x 3 的幻方是一个填充有 从 1 到 9 的不同数字的 3 x 3 矩阵&#xff0c;其中每行&#xff0c;每列以及两条对角线上的各数之和都相等。 给定一个由整数组成的row x col 的 grid&#xff0c;其中有多少个 3 3 的 “幻方” 子矩阵&am…...

AspectJ 在 Android 中的完整使用指南

一、环境配置&#xff08;Gradle 7.0 适配&#xff09; 1. 项目级 build.gradle // 注意&#xff1a;沪江插件已停更&#xff0c;推荐官方兼容方案 buildscript {dependencies {classpath org.aspectj:aspectjtools:1.9.9.1 // AspectJ 工具} } 2. 模块级 build.gradle plu…...