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

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

867. 转置矩阵
     给你一个二维整数数组 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;}
};

868. 二进制间距
     给定一个正整数 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;}
};

869. 重新排序得到 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));}
};

870. 优势洗牌
     给定两个大小相等的数组 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;}
};

871. 最低加油次数

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

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;}
};

872. 叶子相似的树
     如果有两棵二叉树的叶值序列是相同，那么我们就认为它们是 叶相似 的。如果给定的两个根结点分别为 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);}}
};

873. 最长的斐波那契子序列的长度
     如果序列 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 题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---