leetcode解题思路分析(一百零一)867 - 873 题

2024-09-05 04:48

本文主要是介绍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

相关文章

Java程序进程起来了但是不打印日志的原因分析

《Java程序进程起来了但是不打印日志的原因分析》:本文主要介绍Java程序进程起来了但是不打印日志的原因分析,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Java程序进程起来了但是不打印日志的原因1、日志配置问题2、日志文件权限问题3、日志文件路径问题4、程序

Java字符串操作技巧之语法、示例与应用场景分析

《Java字符串操作技巧之语法、示例与应用场景分析》在Java算法题和日常开发中,字符串处理是必备的核心技能,本文全面梳理Java中字符串的常用操作语法,结合代码示例、应用场景和避坑指南,可快速掌握字... 目录引言1. 基础操作1.1 创建字符串1.2 获取长度1.3 访问字符2. 字符串处理2.1 子字

Python 迭代器和生成器概念及场景分析

《Python迭代器和生成器概念及场景分析》yield是Python中实现惰性计算和协程的核心工具,结合send()、throw()、close()等方法,能够构建高效、灵活的数据流和控制流模型,这... 目录迭代器的介绍自定义迭代器省略的迭代器生产器的介绍yield的普通用法yield的高级用法yidle

Python获取C++中返回的char*字段的两种思路

《Python获取C++中返回的char*字段的两种思路》有时候需要获取C++函数中返回来的不定长的char*字符串,本文小编为大家找到了两种解决问题的思路,感兴趣的小伙伴可以跟随小编一起学习一下... 有时候需要获取C++函数中返回来的不定长的char*字符串,目前我找到两种解决问题的思路,具体实现如下:

C++ Sort函数使用场景分析

《C++Sort函数使用场景分析》sort函数是algorithm库下的一个函数,sort函数是不稳定的,即大小相同的元素在排序后相对顺序可能发生改变,如果某些场景需要保持相同元素间的相对顺序,可使... 目录C++ Sort函数详解一、sort函数调用的两种方式二、sort函数使用场景三、sort函数排序

kotlin中const 和val的区别及使用场景分析

《kotlin中const和val的区别及使用场景分析》在Kotlin中,const和val都是用来声明常量的,但它们的使用场景和功能有所不同,下面给大家介绍kotlin中const和val的区别,... 目录kotlin中const 和val的区别1. val:2. const:二 代码示例1 Java

Go标准库常见错误分析和解决办法

《Go标准库常见错误分析和解决办法》Go语言的标准库为开发者提供了丰富且高效的工具,涵盖了从网络编程到文件操作等各个方面,然而,标准库虽好,使用不当却可能适得其反,正所谓工欲善其事,必先利其器,本文将... 目录1. 使用了错误的time.Duration2. time.After导致的内存泄漏3. jsO

Spring事务中@Transactional注解不生效的原因分析与解决

《Spring事务中@Transactional注解不生效的原因分析与解决》在Spring框架中,@Transactional注解是管理数据库事务的核心方式,本文将深入分析事务自调用的底层原理,解释为... 目录1. 引言2. 事务自调用问题重现2.1 示例代码2.2 问题现象3. 为什么事务自调用会失效3

找不到Anaconda prompt终端的原因分析及解决方案

《找不到Anacondaprompt终端的原因分析及解决方案》因为anaconda还没有初始化,在安装anaconda的过程中,有一行是否要添加anaconda到菜单目录中,由于没有勾选,导致没有菜... 目录问题原因问http://www.chinasem.cn题解决安装了 Anaconda 却找不到 An

Spring定时任务只执行一次的原因分析与解决方案

《Spring定时任务只执行一次的原因分析与解决方案》在使用Spring的@Scheduled定时任务时,你是否遇到过任务只执行一次,后续不再触发的情况?这种情况可能由多种原因导致,如未启用调度、线程... 目录1. 问题背景2. Spring定时任务的基本用法3. 为什么定时任务只执行一次?3.1 未启用