leetcode解题思路分析(一百四十九)1297 - 1304 题

2023-10-09 05:28

本文主要是介绍leetcode解题思路分析(一百四十九)1297 - 1304 题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

  1. 子串的最大出现次数
    给你一个字符串 s ,请你返回满足以下条件且出现次数最大的 任意 子串的出现次数:
    子串中不同字母的数目必须小于等于 maxLetters 。
    子串的长度必须大于等于 minSize 且小于等于 maxSize 。

首先能想到的是从MinSize开始遍历查找,然后利用set来保证满足maxLetters,用map来存储string出现的数量,最后取出现数量的最大值。然后因为子串的子串出现数量一定大于等于子串的出现数量,所以其实直接看minSize即可,少一圈循环。

class Solution {
public:int maxFreq(string s, int maxLetters, int minSize, int maxSize) {int n = s.size();unordered_map<string, int> occ;int ans = 0;for (int i = 0; i < n - minSize + 1; ++i) {string cur = s.substr(i, minSize);unordered_set<char> exist(cur.begin(), cur.end());if (exist.size() <= maxLetters) {string cur = s.substr(i, minSize);++occ[cur];ans = max(ans, occ[cur]);}}return ans;}
};
  1. 你能从盒子里获得的最大糖果数
    给你 n 个盒子,每个盒子的格式为 [status, candies, keys, containedBoxes] ,请你按照上述规则,返回可以获得糖果的 最大数目 。

广度优先遍历,对于暂时无法打开的存在队列中等待后续机会。

class Solution {
public:int maxCandies(vector<int>& status, vector<int>& candies, vector<vector<int>>& keys, vector<vector<int>>& containedBoxes, vector<int>& initialBoxes) {int n = status.size();vector<bool> can_open(n), has_box(n), used(n);for (int i = 0; i < n; ++i) {can_open[i] = (status[i] == 1);}queue<int> q;int ans = 0;for (int box: initialBoxes) {has_box[box] = true;if (can_open[box]) {q.push(box);used[box] = true;ans += candies[box];}}while (!q.empty()) {int big_box = q.front();q.pop();for (int key: keys[big_box]) {can_open[key] = true;if (!used[key] && has_box[key]) {q.push(key);used[key] = true;ans += candies[key];}}for (int box: containedBoxes[big_box]) {has_box[box] = true;if (!used[box] && can_open[box]) {q.push(box);used[box] = true;ans += candies[box];}}}return ans;}
};
  1. 将每个元素替换为右侧最大元素
    给你一个数组 arr ,请你将每个元素用它右边最大的元素替换,如果是最后一个元素,用 -1 替换。完成所有替换操作后,请你返回这个数组。

逆向遍历一遍即可。

class Solution {
public:vector<int> replaceElements(vector<int>& arr) {int n = arr.size();vector<int> ans(n);ans[n - 1] = -1;for (int i = n - 2; i >= 0; --i) {ans[i] = max(ans[i + 1], arr[i + 1]);}return ans;}
};
  1. 转变数组后最接近目标值的数组和
    给你一个整数数组 arr 和一个目标值 target ,请你返回一个整数 value ,使得将数组中所有大于 value 的值变成 value 后,数组的和最接近 target (最接近表示两者之差的绝对值最小)。如果有多种使得和最接近 target 的方案,请你返回这些整数中的最小值。请注意,答案不一定是 arr 中的数字。

因为value的改变导致数组和单调变化,所以一定是在不超过target最接近的value和value+1中选一个。采用二分法确定value(上界为max in arr),然后比较和即可。

class Solution {
public:int check(const vector<int>& arr, int x) {int ret = 0;for (const int& num: arr) {ret += (num >= x ? x : num);}return ret;}int findBestValue(vector<int>& arr, int target) {sort(arr.begin(), arr.end());int n = arr.size();vector<int> prefix(n + 1);for (int i = 1; i <= n; ++i) {prefix[i] = prefix[i - 1] + arr[i - 1];}int l = 0, r = *max_element(arr.begin(), arr.end()), ans = -1;while (l <= r) {int mid = (l + r) / 2;auto iter = lower_bound(arr.begin(), arr.end(), mid);int cur = prefix[iter - arr.begin()] + (arr.end() - iter) * mid;if (cur <= target) {ans = mid;l = mid + 1;}else {r = mid - 1;}}int choose_small = check(arr, ans);int choose_big = check(arr, ans + 1);return abs(choose_small - target) <= abs(choose_big - target) ? ans : ans + 1;}
};
  1. 最大得分的路径数目
    给你一个正方形字符数组 board ,你从数组最右下方的字符 ‘S’ 出发。
    你的目标是到达数组最左上角的字符 ‘E’ ,数组剩余的部分为数字字符 1, 2, …, 9 或者障碍 ‘X’。在每一步移动中,你可以向上、向左或者左上方移动,可以移动的前提是到达的格子没有障碍。
    一条路径的 「得分」 定义为:路径上所有数字的和。
    请你返回一个列表,包含两个整数:第一个整数是 「得分」 的最大值,第二个整数是得到最大得分的方案数,请把结果对 10^9 + 7 取余。
    如果没有任何路径可以到达终点,请返回 [0, 0] 。

因为只能向上、左、左上,所以动态规划解题是很容易想到的。

using PII = pair<int, int>;class Solution {
private:static constexpr int mod = (int)1e9 + 7;public:void update(vector<vector<PII>>& dp, int n, int x, int y, int u, int v) {if (u >= n || v >= n || dp[u][v].first == -1) {return;}if (dp[u][v].first > dp[x][y].first) {dp[x][y] = dp[u][v];}else if (dp[u][v].first == dp[x][y].first) {dp[x][y].second += dp[u][v].second;if (dp[x][y].second >= mod) {dp[x][y].second -= mod;}}}vector<int> pathsWithMaxScore(vector<string>& board) {int n = board.size();vector<vector<PII>> dp(n, vector<PII>(n, {-1, 0}));dp[n - 1][n - 1] = {0, 1};for (int i = n - 1; i >= 0; --i) {for (int j = n - 1; j >= 0; --j) {if (!(i == n - 1 && j == n - 1) && board[i][j] != 'X') {update(dp, n, i, j, i + 1, j);update(dp, n, i, j, i, j + 1);update(dp, n, i, j, i + 1, j + 1);if (dp[i][j].first != -1) {dp[i][j].first += (board[i][j] == 'E' ? 0 : board[i][j] - '0');}}}}return dp[0][0].first == -1 ? vector<int>{0, 0} : vector<int>{dp[0][0].first, dp[0][0].second};}
};
  1. 层数最深叶子节点的和
    给你一棵二叉树的根节点 root ,请你返回 层数最深的叶子节点的和 。

采用深度遍历或者广度遍历均可。

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int deepestLeavesSum(TreeNode* root) {int size = 0;int sum  = 0;std::list<TreeNode*> NodeList;if (root)NodeList.push_back(root);while (NodeList.size()){size = NodeList.size();sum  = 0;for (int i = 0; i < size; ++i){std::list<TreeNode*>::iterator iter = NodeList.begin();if ((*iter)->left)NodeList.push_back((*iter)->left);if ((*iter)->right)NodeList.push_back((*iter)->right);sum += (*iter)->val;NodeList.pop_front();}}return sum;}
};
  1. 和为零的 N 个不同整数
    给你一个整数 n,请你返回 任意 一个由 n 个 各不相同 的整数组成的数组,并且这 n 个数相加和为 0 。

很无聊的一道题,直接镜像对称或者从0累加最后来个-sum都可以。

class Solution {
public:vector<int> sumZero(int n) {vector<int> ret;bool isOdd = n % 2 == 0 ? false : true;int begin = 0 - n / 2;int end   = n / 2;for (int i = begin; i <= end; ++i){if (i == 0 && !isOdd)continue;ret.push_back(i);}return ret;}
};

这篇关于leetcode解题思路分析(一百四十九)1297 - 1304 题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/170650

相关文章

MyBatis Plus 中 update_time 字段自动填充失效的原因分析及解决方案(最新整理)

《MyBatisPlus中update_time字段自动填充失效的原因分析及解决方案(最新整理)》在使用MyBatisPlus时,通常我们会在数据库表中设置create_time和update... 目录前言一、问题现象二、原因分析三、总结:常见原因与解决方法对照表四、推荐写法前言在使用 MyBATis

Python主动抛出异常的各种用法和场景分析

《Python主动抛出异常的各种用法和场景分析》在Python中,我们不仅可以捕获和处理异常,还可以主动抛出异常,也就是以类的方式自定义错误的类型和提示信息,这在编程中非常有用,下面我将详细解释主动抛... 目录一、为什么要主动抛出异常?二、基本语法:raise关键字基本示例三、raise的多种用法1. 抛

github打不开的问题分析及解决

《github打不开的问题分析及解决》:本文主要介绍github打不开的问题分析及解决,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、找到github.com域名解析的ip地址二、找到github.global.ssl.fastly.net网址解析的ip地址三

Mysql的主从同步/复制的原理分析

《Mysql的主从同步/复制的原理分析》:本文主要介绍Mysql的主从同步/复制的原理分析,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录为什么要主从同步?mysql主从同步架构有哪些?Mysql主从复制的原理/整体流程级联复制架构为什么好?Mysql主从复制注意

java -jar命令运行 jar包时运行外部依赖jar包的场景分析

《java-jar命令运行jar包时运行外部依赖jar包的场景分析》:本文主要介绍java-jar命令运行jar包时运行外部依赖jar包的场景分析,本文给大家介绍的非常详细,对大家的学习或工作... 目录Java -jar命令运行 jar包时如何运行外部依赖jar包场景:解决:方法一、启动参数添加: -Xb

Apache 高级配置实战之从连接保持到日志分析的完整指南

《Apache高级配置实战之从连接保持到日志分析的完整指南》本文带你从连接保持优化开始,一路走到访问控制和日志管理,最后用AWStats来分析网站数据,对Apache配置日志分析相关知识感兴趣的朋友... 目录Apache 高级配置实战:从连接保持到日志分析的完整指南前言 一、Apache 连接保持 - 性

Linux中的more 和 less区别对比分析

《Linux中的more和less区别对比分析》在Linux/Unix系统中,more和less都是用于分页查看文本文件的命令,但less是more的增强版,功能更强大,:本文主要介绍Linu... 目录1. 基础功能对比2. 常用操作对比less 的操作3. 实际使用示例4. 为什么推荐 less?5.

spring-gateway filters添加自定义过滤器实现流程分析(可插拔)

《spring-gatewayfilters添加自定义过滤器实现流程分析(可插拔)》:本文主要介绍spring-gatewayfilters添加自定义过滤器实现流程分析(可插拔),本文通过实例图... 目录需求背景需求拆解设计流程及作用域逻辑处理代码逻辑需求背景公司要求,通过公司网络代理访问的请求需要做请

Java集成Onlyoffice的示例代码及场景分析

《Java集成Onlyoffice的示例代码及场景分析》:本文主要介绍Java集成Onlyoffice的示例代码及场景分析,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要... 需求场景:实现文档的在线编辑,团队协作总结:两个接口 + 前端页面 + 配置项接口1:一个接口,将o

IDEA下"File is read-only"可能原因分析及"找不到或无法加载主类"的问题

《IDEA下Fileisread-only可能原因分析及找不到或无法加载主类的问题》:本文主要介绍IDEA下Fileisread-only可能原因分析及找不到或无法加载主类的问题,具有很好的参... 目录1.File is read-only”可能原因2.“找不到或无法加载主类”问题的解决总结1.File