leetcode解题思路分析(五十)432 - 438 题

2024-09-05 04:58

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

  1. 全O(1)的数据结构

哈希表+链表即可

class AllOne {
public:/** Initialize your data structure here. */struct Node{unordered_set<string> container;int val = 0;Node(int v):val(v){}};unordered_map<string, list<Node>::iterator> kv;list<Node> List;AllOne() {}/** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */void inc(string key) {if(kv.count(key)){auto oldNode = kv[key];auto newNode = next(oldNode, 1);if(newNode == List.end() || newNode->val>oldNode->val+1){newNode = List.insert(newNode, Node(oldNode->val+1));}newNode->container.insert(key);oldNode->container.erase(key);if(oldNode->container.empty()){List.erase(oldNode);}kv[key] = newNode;} else {auto newNode = List.begin();if(List.empty() || List.begin()->val>1)newNode = List.insert(List.begin(), Node(1));newNode->container.insert(key);kv[key] = newNode;}}/** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */void dec(string key) {if(kv.count(key)){auto oldNode = kv[key];if(oldNode->val==1) {kv.erase(key);} else {auto newNode = next(oldNode, -1);if(oldNode==List.begin() || newNode->val<oldNode->val-1){newNode = List.insert(oldNode, Node(oldNode->val-1));}newNode->container.insert(key);kv[key] = newNode;}oldNode->container.erase(key);if(oldNode->container.empty()){List.erase(oldNode);}}}/** Returns one of the keys with maximal value. */string getMaxKey() {if(List.empty()) return "";return *List.rbegin()->container.begin();}/** Returns one of the keys with Minimal value. */string getMinKey() {if(List.empty()) return "";return *List.begin()->container.begin();}
};
  1. 最小基因变化
    现在给定3个参数 — start, end, bank,分别代表起始基因序列,目标基因序列及基因库,请找出能够使起始基因序列变化为目标基因序列所需的最少变化次数。如果无法实现目标变化,请返回 -1。

依次从基因库找变换一个字母可以构成的,然后删除基因库中的对应基因,继续查找直至找到或者找不到

class Solution {
public:int Dif_num(string& s1, string& s2){int cnt = 0;for (int i = 0; i < s1.size(); i++){if (s1[i] != s2[i])cnt++;}return cnt;}int minMutation(string start, string end, vector<string>& bank) {queue<string>qu;qu.push(start);int res = 0;unordered_map<string, int>vis;while (!qu.empty()){int size = qu.size();for (int i = 0; i < size; i++){string cur = qu.front();vis[cur] = 1;qu.pop();if (cur == end)return res;for (int i = 0; i < bank.size(); i++){if (Dif_num(cur, bank[i]) == 1 && !vis[bank[i]]){qu.push(bank[i]);}}}res++;}return -1;}
};
  1. 字符串中的单词数
    统计字符串中的单词个数,这里的单词指的是连续的不是空格的字符。

考察一个边界条件,十分简单了

class Solution {
public:int countSegments(string s) {int ret = 0;if (s.size() == 0) return ret;else if (s[0] != ' ') ret++;for (int i  = 0; i < s.size() - 1; i++){if (s[i] == ' ' && s[i + 1] != ' ') {ret++;i++;}}return ret;}
};
  1. 无重叠区间
    给定一个区间的集合,找到需要移除区间的最小数量,使剩余区间互不重叠。

贪心算法的经典运用。先排序,然后挨个判断:如果包含关系则取小的,如果交错则抛弃后者,如果不相交则都存着

class Solution {
public:int eraseOverlapIntervals(vector<vector<int>>& intervals) {if (intervals.empty()) return 0;sort(intervals.begin(), intervals.end());int left = intervals[0][1];int res = 0;for (int i = 1; i < intervals.size(); ++i) {if (intervals[i][0] < left) {++res;left = min(left, intervals[i][1]);} else {left = intervals[i][1];}}return res;}
};
  1. 寻找右区间
    给定一组区间,对于每一个区间 i,检查是否存在一个区间 j,它的起始点大于或等于区间 i 的终点,这可以称为 j 在 i 的“右侧”。

分别存两份数组以区间起点和终点排序,然后进行比较得出右侧区间

// 利用两个数组,分别排序起点和终点位置
class Solution {
public:vector<int> findRightInterval(vector<vector<int>>& intervals) {vector<pair<int, int>> start;vector<pair<int, int>> end;int len = intervals.size();for(int i = 0; i < len; i++){start.push_back(make_pair(intervals[i][0], i));end.push_back(make_pair(intervals[i][1],i));}sort(start.begin(), start.end());sort(end.begin(), end.end(),[](pair<int, int> p1, pair<int, int> p2){if(p1.first == p2.first)return p1.second < p2.second;return p1.first < p2.first;//如果两个终点相同,会返回那个索引小的});vector<int> ans(len, -1);int indexS = 0;int indexE = 0;while(indexS < len && indexE < len){while(indexS < len && (start[indexS].second == end[indexE].second || start[indexS].first < end[indexE].first))indexS++;if(indexS < len)ans[end[indexE++].second] = start[indexS].second;}return ans;}
};
  1. 路径总和3
    给定一个二叉树,它的每个结点都存放着一个整数值。找出路径和等于给定数值的路径总数。

使用前缀和记录从而减小内存消耗,只需遍历一次树即可。

/*** 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:unordered_map<int, int> m;int sum, res = 0;
public:void dfs(TreeNode* root, int cur_sum){if (root == nullptr) return;if (m.count(cur_sum - sum))res += m[cur_sum - sum];m[cur_sum] ++;if (root->left)  dfs(root->left, cur_sum + root->left->val);if (root->right) dfs(root->right, cur_sum + root->right->val);m[cur_sum]--;}int pathSum(TreeNode* root, int sum) {if (root == nullptr) return 0;this->sum = sum;// 构建前缀和m[0] = 1;dfs(root, root->val);return res;}
};
  1. 找到字符串中所有字母异位词
    给定一个字符串 s 和一个非空字符串 p,找到 s 中所有是 p 的字母异位词的子串,返回这些子串的起始索引。

采用双指针滑动,用一个字典数组保存P的特征,滑动的过程中–,如果恰好为0且长度相等则说明找到了,否则滑动指针并++

class Solution {
public:vector<int> findAnagrams(string s, string p) {vector<int> res;int m[128] = {0};int left = 0, right = 0, need = 0;for (char c : p)++m[c];while (right < s.size()){if (m[s[right]] > 0)     ++need;--m[s[right]];++right;while (need == p.size()){if (right - left == p.size())   res.push_back(left);      //通过长度判断异位词,加入res中if (m[s[left]] == 0)     --need;++m[s[left]];++left;}}return res;}
};

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



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

相关文章

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

性能分析之MySQL索引实战案例

文章目录 一、前言二、准备三、MySQL索引优化四、MySQL 索引知识回顾五、总结 一、前言 在上一讲性能工具之 JProfiler 简单登录案例分析实战中已经发现SQL没有建立索引问题,本文将一起从代码层去分析为什么没有建立索引? 开源ERP项目地址:https://gitee.com/jishenghua/JSH_ERP 二、准备 打开IDEA找到登录请求资源路径位置

透彻!驯服大型语言模型(LLMs)的五种方法,及具体方法选择思路

引言 随着时间的发展,大型语言模型不再停留在演示阶段而是逐步面向生产系统的应用,随着人们期望的不断增加,目标也发生了巨大的变化。在短短的几个月的时间里,人们对大模型的认识已经从对其zero-shot能力感到惊讶,转变为考虑改进模型质量、提高模型可用性。 「大语言模型(LLMs)其实就是利用高容量的模型架构(例如Transformer)对海量的、多种多样的数据分布进行建模得到,它包含了大量的先验

SWAP作物生长模型安装教程、数据制备、敏感性分析、气候变化影响、R模型敏感性分析与贝叶斯优化、Fortran源代码分析、气候数据降尺度与变化影响分析

查看原文>>>全流程SWAP农业模型数据制备、敏感性分析及气候变化影响实践技术应用 SWAP模型是由荷兰瓦赫宁根大学开发的先进农作物模型,它综合考虑了土壤-水分-大气以及植被间的相互作用;是一种描述作物生长过程的一种机理性作物生长模型。它不但运用Richard方程,使其能够精确的模拟土壤中水分的运动,而且耦合了WOFOST作物模型使作物的生长描述更为科学。 本文让更多的科研人员和农业工作者

MOLE 2.5 分析分子通道和孔隙

软件介绍 生物大分子通道和孔隙在生物学中发挥着重要作用,例如在分子识别和酶底物特异性方面。 我们介绍了一种名为 MOLE 2.5 的高级软件工具,该工具旨在分析分子通道和孔隙。 与其他可用软件工具的基准测试表明,MOLE 2.5 相比更快、更强大、功能更丰富。作为一项新功能,MOLE 2.5 可以估算已识别通道的物理化学性质。 软件下载 https://pan.quark.cn/s/57

leetcode-24Swap Nodes in Pairs

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode swapPairs(L

leetcode-23Merge k Sorted Lists

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode mergeKLists

衡石分析平台使用手册-单机安装及启动

单机安装及启动​ 本文讲述如何在单机环境下进行 HENGSHI SENSE 安装的操作过程。 在安装前请确认网络环境,如果是隔离环境,无法连接互联网时,请先按照 离线环境安装依赖的指导进行依赖包的安装,然后按照本文的指导继续操作。如果网络环境可以连接互联网,请直接按照本文的指导进行安装。 准备工作​ 请参考安装环境文档准备安装环境。 配置用户与安装目录。 在操作前请检查您是否有 sud

线性因子模型 - 独立分量分析(ICA)篇

序言 线性因子模型是数据分析与机器学习中的一类重要模型,它们通过引入潜变量( latent variables \text{latent variables} latent variables)来更好地表征数据。其中,独立分量分析( ICA \text{ICA} ICA)作为线性因子模型的一种,以其独特的视角和广泛的应用领域而备受关注。 ICA \text{ICA} ICA旨在将观察到的复杂信号

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目: 题解: class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &