leetcode解题思路分析(二十六)187 - 192题

2024-09-05 05:08

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

  1. 重复的DNA序列
    编写一个函数来查找 DNA 分子中所有出现超过一次的 10 个字母长的序列(子串)。
class Solution {
public:vector<string> findRepeatedDnaSequences(string s) {//对应二进制00, 01, 10, 11.那么10个组合只要20位就够了。unordered_map<char, int> m{{'A', 0}, {'C', 1}, {'G', 2}, {'T', 3}};vector<string> res;bitset<1 << 20> s1, s2; //那么所有组合的值将在0到(1 << 20 - 1)之间int val = 0, mask = (1 << 20) - 1; //mask等于二进制的20个1//类似与滑动窗口先把前10个字母组合for (int i = 0; i < 10; ++i) val = (val << 2) | m[s[i]];s1.set(val); //置位for (int i = 10; i < s.size(); ++i){val = ((val << 2) & mask) | m[s[i]]; //去掉左移的一个字符再加上一个新字符if (s2.test(val)) continue; //出现过两次跳过if (s1.test(val)){res.push_back(s.substr(i - 9, 10));s2.set(val);}else s1.set(val);}return res;}
};
  1. 买卖股票的最佳时机4
    给定一个数组,它的第 i 个元素是一支给定的股票在第 i 天的价格。
    设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
    注意: 你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

本题采用动态规划求解,和前面几题的区别在于需要考虑k。如果K比较多支持每天都在买和卖,则直接累加,否则需要考虑哪天卖出最划算

class Solution {
public:int maxProfit(int k, vector<int>& prices) {if(!prices.size()) return 0;if(k >= prices.size()/2){int maxsumval = 0;for(int i = 1; i < prices.size(); i++)if(prices[i] > prices[i - 1])maxsumval += prices[i] - prices[i - 1];return maxsumval;}vector<int> dp(k + 1, 0);vector<int> v(k + 1, prices[0]);for(int i = 1; i < prices.size(); i++){for(int t = 1; t <= k; t++){v[t] = min(v[t], prices[i] - dp[t - 1]);dp[t] = max(dp[t], prices[i] - v[t]);  }} return dp[k];}
};
  1. 旋转数组
    给定一个数组,将数组中的元素向右移动 k 个位置,其中 k 是非负数。

首先将所有元素反转。然后反转前 k 个元素,再反转后面 n-kn−k 个元素,就能得到想要的结果。

class Solution {
public:void rotate(vector<int>& nums, int k) {reverse(nums.begin(), nums.end() - k % nums.size());reverse(nums.end() - k % nums.size(), nums.end());reverse(nums.begin(), nums.end());}
};
  1. 颠倒二进制位
    颠倒给定的 32 位无符号整数的二进制位。

首先,我们将原来的 32 位分为 2 个 16 位的块。
然后我们将 16 位块分成 2 个 8 位的块。
然后我们继续将这些块分成更小的块,直到达到 1 位的块。
在上述每个步骤中,我们将中间结果合并为一个整数,作为下一步的输入。

class Solution {
public:uint32_t reverseBits(uint32_t n) {n = (n >> 16) | (n << 16);n = ((n & 0xff00ff00) >> 8) | ((n & 0x00ff00ff) << 8);n = ((n & 0xf0f0f0f0) >> 4) | ((n & 0x0f0f0f0f) << 4);n = ((n & 0xcccccccc) >> 2) | ((n & 0x33333333) << 2);n = ((n & 0xaaaaaaaa) >> 1) | ((n & 0x55555555) << 1);return n;}
};
  1. 位1的个数
    编写一个函数,输入是一个无符号整数,返回其二进制表达式中数字位数为 ‘1’ 的个数

最简单的方法就是逐位检查

class Solution {
public:int hammingWeight(uint32_t n) {int ret = 0;while(n)        {if (n & 1) ret++;n >>= 1;}return ret;}
};

在二进制表示中,数字 nn 中最低位的 11 总是对应 n - 1n−1 中的 00 。因此,将 nn 和 n - 1n−1 与运算总是能把 nn 中最低位的 11 变成 00 ,并保持其他位不变。


class Solution {
public:int hammingWeight(uint32_t n) {int count = 0;while(n > 0){n &= (n - 1);++count;}return count;}
};
  1. 统计词频
    写一个 bash 脚本以统计一个文本文件 words.txt 中每个单词出现的频率。

本题其实分两步,第一步是单次分割,第二步是将分割的单次进行统计。

单次分割可以使用awk或者catxargs实现

awk '{for(i=1;i<=NF;i++){print $i}}' words.txt cat words.txt | xargs -n1

使用awk命令来完成这个任务的话很简单,在进行分割的过程中直接用一个关联数组直接保存每一个单词出现的次数

awk '{for(i=1;i<=NF;i++){asso_array[$i]++;}};END{for(w in asso_array){print w,asso_array[w];}}' words.txt

使用cat + xargs的话需要使用sort以及uniq实现

cat words.txt | xargs -n1 | sort | uniq -c

最终代码

awk '{for(i=1;i<=NF;i++){asso_array[$i]++;}};END{for(w in asso_array){print w,asso_array[w];}}' words.txt | sort -rn -k2cat words.txt | xargs -n1 | sort | uniq -c | sort -rn | awk '{print $2,$1}'

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



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

相关文章

哈希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 &