算法练习7-北京尧图网络

1. 字母异位词分组题目要求将互为字母异位词的字符串放入同一组。例如[eat, tea, tan, ate, nat, bat]可以分为[[eat, tea, ate], [tan, nat], [bat]]核心思路字母异位词中每种字符出现的次数相同。将字符串排序后互为异位词的字符串一定会得到同一个结果eat - aet tea - aet ate - aet使用HashMapkey排序后的字符串 value具有相同 key 的原字符串列表复杂度设字符串平均长度为k字符串数量为n时间复杂度O(n × k log k) 空间复杂度O(n × k)2. 环形链表判断一个链表中是否存在环。3 - 2 - 0 - -4 ^ | |_________|核心思路快慢指针定义两个指针slow每次走 1 步 fast每次走 2 步无环fast最终会到达null有环fast会在环中追上slow两个指针会指向同一个节点。while (fast ! null fast.next ! null) { slow slow.next; fast fast.next.next; if (slow fast) { return true; } }复杂度时间复杂度O(n) 空间复杂度O(1)3. 最长回文子串在字符串中找到最长的回文子串。输入babad 输出bab 或 aba 输入cbbd 输出bb核心思路中心扩展回文串有两种中心奇数长度aba 中心是 b 偶数长度abba 中心在两个 b 之间因此每个位置都需要尝试两次扩展expandAroundCenter(s, i, i); // 奇数长度 expandAroundCenter(s, i, i 1); // 偶数长度扩展条件left 0 right s.length() s.charAt(left) s.charAt(right)起始下标计算当回文长度为len当前左中心为i时start i - (len - 1) / 2;这条公式能统一处理奇数长度与偶数长度回文。复杂度时间复杂度O(n²) 空间复杂度O(1)4. 零钱兑换给定硬币面额coins和金额amount求凑出目标金额所需的最少硬币数。无法凑出时返回-1。coins [1, 2, 5] amount 11 答案3 解释5 5 1为什么不能贪心coins [1, 3, 4] amount 6 贪心4 1 1需要 3 枚最优3 3只需要 2 枚因此不能只优先选择面额最大的硬币。核心思路一维动态规划定义dp[x]凑出金额 x 所需的最少硬币数量初始状态dp[0] 0;其他位置先初始化为不可能达到的大值Arrays.fill(dp, amount 1);状态转移dp[currentAmount] Math.min( dp[currentAmount], dp[currentAmount - coin] 1 );含义是最后选择一枚coin后前面先凑出currentAmount - coin。复杂度时间复杂度O(amount × coins.length) 空间复杂度O(amount)5. 买卖股票的最佳时机只能买入一次、卖出一次求最大利润。prices [7, 1, 5, 3, 6, 4] 答案5 第 2 天以 1 买入第 5 天以 6 卖出。核心思路维护历史最低价格遍历每一天的股价时维护minPrice截至当前日期的最低买入价格 maxProfit截至当前日期的最大利润for (int price : prices) { minPrice Math.min(minPrice, price); maxProfit Math.max(maxProfit, price - minPrice); }当出现一个更低价格时它将成为后续更好的买入机会当前价格则可以尝试作为卖出价格。复杂度时间复杂度O(n) 空间复杂度O(1)6. 除自身以外数组的乘积返回数组answer其中answer[i] 除 nums[i] 外其余元素的乘积输入[1, 2, 3, 4] 输出[24, 12, 8, 6]核心思路前缀积后缀积定义left[i]i 左边所有元素的乘积 right[i]i 右边所有元素的乘积因此answer[i] left[i] × right[i]例如nums [1, 2, 3, 4] left [1, 1, 2, 6] right [24, 12, 4, 1] answer [24, 12, 8, 6]边界位置left[0] 1; right[n - 1] 1;因为没有元素参与相乘时乘积定义为1。复杂度时间复杂度O(n) 空间复杂度O(n)还可以进一步优化为将前缀积直接存入answer再用一个变量从右向左累乘后缀积从而将额外空间优化到O(1)。7. 最大子数组和找到一个和最大的连续子数组。输入[-2, 1, -3, 4, -1, 2, 1, -5, 4] 输出6 最大连续子数组[4, -1, 2, 1]核心思路Kadane 算法不断累加当前连续子数组的和当前累计和大于等于0继续保留当前累计和小于0它会拖累后续结果直接丢弃从后续元素重新开始。int currentSum 0; int maxSum nums[0]; for (int num : nums) { currentSum num; maxSum Math.max(maxSum, currentSum); if (currentSum 0) { currentSum 0; } }为什么不能把maxSum初始化为 0对于全负数数组[-3, -2, -5]最大连续子数组和应该是-2若初始化为0会错误返回0。复杂度时间复杂度O(n) 空间复杂度O(1)8. 合并区间将所有重叠区间合并。输入[[1,3], [2,6], [8,10], [15,18]] 输出[[1,6], [8,10], [15,18]]核心思路排序贪心扫描先按区间左端点排序Arrays.sort(intervals, (a, b) - a[0] - b[0]);然后依次判断当前区间是否和结果中最后一个区间重叠。判断条件lastEnd currentStart若成立不重叠直接加入结果否则发生重叠更新右端点。lastEnd Math.max(lastEnd, currentEnd);端点相接也需要合并[1, 4] 和 [4, 5]两者在端点4相接结果应为[1, 5]因此“不重叠”的条件必须是lastEnd currentStart而不能写成lastEnd currentStart复杂度排序O(n log n) 扫描O(n) 总时间复杂度O(n log n) 空间复杂度O(n)

算法练习7

相关推荐

跨境业务踩坑记：那些年被文档翻译耽误的生意

Python实战信用评分卡建模：从逻辑回归到业务部署全流程解析

本地AI代码助手终极配置指南：从模型量化到IDE集成的全链路优化

更多资讯

Phoenix 中 OTel contextvars 与 async 边界的实战避坑指南：为何不在异步生成器清理路径里使用 contextvars

云栖大会第一印象：机器智能的经济学

Java工资管理系统课设：数据库设计与事务实战

Mac访达缩略图不显示？从缓存到QuickLook的完整修复指南

轻量级CRM自建实战：Node.js+Electron+SQLite完整指南

昇腾Atlas 300V部署YOLO：从环境搭建到推理优化全指南

今日更新

AI元人文：从工具使用到思维重构的深度探索

Python+CNN车牌识别实战：从数据预处理到模型训练与部署

Vim基础操作全攻略：保存退出、模式切换与高频命令实战

本周精选

深入解析Transformer多头注意力机制与工程优化

OpenClaw 的 Skills 跑学习任务，模型通道改到 TaoToken 通道行不行？

ChatGPT报错Oops, an error occurred! 全链路排查指南

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

读完文章，想聊聊您的网站？