leetcode解题思路分析（一百零一）867 - 873 题

2024-09-05 04:48
文章标签 零一 leetcode 867 873 解题 一百 思路 分析

本文主要是介绍leetcode解题思路分析（一百零一）867 - 873 题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

  1. 转置矩阵
    给你一个二维整数数组 matrix， 返回 matrix 的 转置矩阵 。矩阵的 转置 是指将矩阵的主对角线翻转，交换矩阵的行索引与列索引。

加粗样式

class Solution {
public:vector<vector<int>> transpose(vector<vector<int>>& matrix) {int m = matrix.size(), n = matrix[0].size();vector<vector<int>> transposed(n, vector<int>(m));for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {transposed[j][i] = matrix[i][j];}}return transposed;}
};
  1. 二进制间距
    给定一个正整数 n，找到并返回 n 的二进制表示中两个 相邻 1 之间的 最长距离 。如果不存在两个相邻的 1，返回 0 。如果只有 0 将两个 1 分隔开（可能不存在 0 ），则认为这两个 1 彼此 相邻 。两个 1 之间的距离是它们的二进制表示中位置的绝对差。例如，“1001” 中的两个 1 的距离为 3 。

遍历一次然后依次取值

class Solution {
public:int binaryGap(int n) {int last = -1, ans = 0;for (int i = 0; i < 32; ++i)if (((n >> i) & 1) > 0) {if (last >= 0)ans = max(ans, i - last);last = i;}return ans;}
};
  1. 重新排序得到 2 的幂
    给定正整数 N ，我们按任何顺序（包括原始顺序）将数字重新排序，注意其前导数字不能为零。如果我们可以通过上述方式得到 2 的幂，返回 true；否则，返回 false。

先把所有2的幂存起来，然后对数字取查是否有每位数的数字统计都一毛一样的即可

string countDigits(int n) {string cnt(10, 0);while (n) {++cnt[n % 10];n /= 10;}return cnt;
}unordered_set<string> powerOf2Digits;int init = []() {for (int n = 1; n <= 1e9; n <<= 1) {powerOf2Digits.insert(countDigits(n));}return 0;
}();class Solution {
public:bool reorderedPowerOf2(int n) {return powerOf2Digits.count(countDigits(n));}
};
  1. 优势洗牌
    给定两个大小相等的数组 A 和 B，A 相对于 B 的优势可以用满足 A[i] > B[i] 的索引 i 的数目来描述。返回 A 的任意排列，使其相对于 B 的优势最大化。

贪心算法求解，需要考虑的是，对于A排序后如何减小重复访问次数，对于B如何进行记录。

class Solution {
public:vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) {int n = nums1.size();//先按照从大到小排序sort(nums1.begin(), nums1.end(), greater<int>());vector<pair<int, int>> sorted2(n);for(int i = 0; i < n; i++){sorted2[i] = {nums2[i], i};}sort(sorted2.begin(), sorted2.end(), [](const auto& a, const auto& b){return a.first > b.first;});vector<int> res(n);//双指针记录 A 中来对战的马匹int left = 0, right = n - 1;//遍历 B 中所有的马匹for(int i = 0; i < n; i++){//当前B的马匹auto [cur, idx] = sorted2[i];//A 打不过 B，找最弱的来if(nums1[left] <= cur) {res[idx] = nums1[right];right--;} else {//打的过，就直接比res[idx] = nums1[left];left++;} }return res;}
};
  1. 最低加油次数

栈存储加油站位置，然后再贪心遍历，只选择油最多的油站

class Solution {
public:int minRefuelStops(int target, int startFuel, vector<vector<int>>& stations) {stations.push_back(vector<int>({target, 0}));priority_queue<int> pq;int res = 0, pos = 0, tank = startFuel;for (auto &v : stations) {int curpos = v[0];int curval = v[1];tank = tank - curpos + pos;while (!pq.empty() && tank < 0) {tank += pq.top();pq.pop();res++;}if (tank < 0) return -1;pq.push(curval);pos = curpos;}return res;}
};
  1. 叶子相似的树
    如果有两棵二叉树的叶值序列是相同，那么我们就认为它们是 叶相似 的。如果给定的两个根结点分别为 root1 和 root2 的树是叶相似的，则返回 true；否则返回 false 。

中序遍历取叶子，然后判断俩数组即可

/*** 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:bool leafSimilar(TreeNode* root1, TreeNode* root2) {bool ret = false;std::vector<int> leaf1, leaf2;findLeaf(leaf1, root1);findLeaf(leaf2, root2);if (leaf1.size() != leaf2.size()){goto Exit0;}for (int i = 0; i < leaf1.size(); ++i){if (leaf1[i] != leaf2[i]){goto Exit0;}}ret = true;Exit0:return ret;}private:void findLeaf(std::vector<int> &leaf, TreeNode* pNode){if (pNode->left == NULL && pNode->right == NULL){leaf.push_back(pNode->val);}if (pNode->left){findLeaf(leaf, pNode->left);}if (pNode->right){findLeaf(leaf, pNode->right);}}
};
  1. 最长的斐波那契子序列的长度
    如果序列 X_1, X_2, …, X_n 满足下列条件，就说它是 斐波那契式 的：
    n >= 3
    对于所有 i + 2 <= n，都有 X_i + X_{i+1} = X_{i+2}
    给定一个严格递增的正整数数组形成序列 arr ，找到 arr 中最长的斐波那契式的子序列的长度。如果一个不存在，返回 0 。

采用动态规划的思想解题。设 longest[i, j] 是结束在 [i, j] 的最长路径。那么 如果 (i, j) 和 (j, k) 是连通的， longest[j, k] = longest[i, j] + 1。jN+k是将(j,k)映射为N进制数，保证每个不同的(j,k)都有不同的N进制数jN+k一一对应。

class Solution {
public:int lenLongestFibSubseq(vector<int>& A) {int N = A.size();unordered_map<int, int> index;for (int i = 0; i < N; ++i)index[A[i]] = i;unordered_map<int, int> longest;int ans = 0;for (int k = 0; k < N; ++k)for (int j = 0; j < k; ++j) {if (A[k] - A[j] < A[j] && index.count(A[k] - A[j])) {int i = index[A[k] - A[j]];longest[j * N + k] = longest[i * N + j] + 1;ans = max(ans, longest[j * N + k] + 2);}}return ans >= 3 ? ans : 0;}
};

这篇关于leetcode解题思路分析（一百零一）867 - 873 题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1137993。

相关文章

哈希leetcode-1

哈希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索引优化四、MySQL 索引知识回顾五、总结 一、前言 在上一讲性能工具之 JProfiler 简单登录案例分析实战中已经发现SQL没有建立索引问题，本文将一起从代码层去分析为什么没有建立索引？ 开源ERP项目地址：https://gitee.com/jishenghua/JSH_ERP 二、准备 打开IDEA找到登录请求资源路径位置
阅读更多...
透彻！驯服大型语言模型（LLMs）的五种方法，及具体方法选择思路

透彻！驯服大型语言模型（LLMs）的五种方法，及具体方法选择思路

引言 随着时间的发展，大型语言模型不再停留在演示阶段而是逐步面向生产系统的应用，随着人们期望的不断增加，目标也发生了巨大的变化。在短短的几个月的时间里，人们对大模型的认识已经从对其zero-shot能力感到惊讶，转变为考虑改进模型质量、提高模型可用性。 「大语言模型(LLMs)其实就是利用高容量的模型架构（例如Transformer）对海量的、多种多样的数据分布进行建模得到，它包含了大量的先验
阅读更多...
SWAP作物生长模型安装教程、数据制备、敏感性分析、气候变化影响、R模型敏感性分析与贝叶斯优化、Fortran源代码分析、气候数据降尺度与变化影响分析

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

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

MOLE 2.5 分析分子通道和孔隙

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

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

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）篇

线性因子模型 - 独立分量分析（ICA）篇

序言 线性因子模型是数据分析与机器学习中的一类重要模型，它们通过引入潜变量（ latent variables \text{latent variables} latent variables）来更好地表征数据。其中，独立分量分析（ ICA \text{ICA} ICA）作为线性因子模型的一种，以其独特的视角和广泛的应用领域而备受关注。 ICA \text{ICA} ICA旨在将观察到的复杂信号
阅读更多...
C++ | Leetcode C++题解之第393题UTF-8编码验证

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 &
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2