【C++ 算法进阶】算法提升七

正数数组中那两个数&结果最大 （贪心）

题目

给定一个由正整数组成的数组 现在要求你返回哪两个数组 & 的结果最大

题目分析

这道题和算法提升六中的异或有着明显的不同 因为在&运算中 只要有一个数是0 最后的结果就是0

也就是说 如果我们当前位是0 走0号线 1号线都是有理由的 但是我们无法比较0和1号线下面谁更好 所以说前缀树的方式是行不通的

但是 & 的特性告诉我们 尽量要前面位数的数字都为1

所以说我们就能有这样的思路

从最高位开始遍历整个数组 查看当前位置1的数量

• 如果数量小于1 则说明当前位必定是0 没法求出最大值
• 如果数量等于2 我们就可以直接将这两个数相与 得出最终答案
• 如果数量大于3 则说明当前位必定是1 继续求下个为止的数据即可

代码详解

int Maxxx(vector<int>& arr) {// lnSize 数组的大小int ans = 0;int M = arr.size();// move 移动的位数for (int move = 30; move >= 0; move--) {// lnBit 当前比特位的数字int tmp = M;int lnBit = 0; int count = 0;int i = 0;while (i < M){lnBit = (arr[i] >> move) & 1;if (lnBit == 1) {int tmp = arr[i];arr[i] = arr[count];arr[count] = tmp;count++;}i++;}M = count;if (count < 2) {M = tmp;}if (count == 2) {return arr[0] & arr[1];}}return arr[0] & arr[1];
}

最小相机覆盖问题 （二叉树递归套路）

题目

给定一个二叉树 我们在树的节点上安装摄像头

节点上的每个摄影头都可以监视其父对象 自身及其子节点

计算监控树的所有节点所需的最小摄像头数量

题目分析

如果我们这里按照一般的二叉树套路分析 这里有这两种情况

• 当前节有相机 且下方节点都被覆盖
• 当前节点无相机 且下方节点都被覆盖

但是只是这两种可能性 我们不能得出最佳答案

我们假设当前节点为X 如果只根据情况1 2 我们得不出最佳的答案

最佳答案为在X的子节点放置一个相机

所以说我们要推出这三种可能性

1. X有相机 且X下方都被覆盖了
2. X无相机 且X下方都被覆盖了 且X也被覆盖了
3. X无相机 且X下方都被覆盖了 且X没被覆盖

代码详解

#include <iostream>
#include <memory>class TreeNode {
public:int val;TreeNode* left;TreeNode* right;explicit TreeNode(int value) : val(value), left(nullptr), right(nullptr) {}
};enum class Status {Uncovered,CoveredNoCamera,CoveredHasCamera
};class Data {
public:Status status;int camera;Data(Status stat, int cam) : status(stat), camera(cam) {}
};// 独立的 process 函数
Data process(TreeNode* root) {if (!root) return Data(Status::CoveredHasCamera, 0);Data left = process(root->left);Data right = process(root->right);int camera = left.camera + right.camera;if (left.status == Status::CoveredNoCamera || right.status == Status::CoveredNoCamera) {return Data(Status::CoveredHasCamera, camera + 1);}if (left.status == Status::CoveredHasCamera || right.status == Status::CoveredHasCamera) {return Data(Status::CoveredHasCamera, camera);}return Data(Status::Uncovered, camera);
}class CameraCoverage {
public:static int resolveMinCamera(TreeNode* root) {Data data = process(root);return data.camera + (data.status == Status::Uncovered ? 1 : 0);}
};int main() {// 测试用例可以在这里添加return 0;
}

拼接字符串 （动态规划 + 前缀树）

题目

假设所有字符都是小写字母 字符串为str

arr是去重的单词表 每个单词都不是空字符且可以使用N次

使用arr中的字符有多少种可以拼接str的方法 （不存在无解的情况）

题目分析

这道题很明显是一个从左到右的动态规划模型

我们根据这个模型可以设置如下的递归函数

int process(string& s, int i) 

我们规定这个函数的意义是 返回从string的i位置开始 返回有多少种方法数可以让单词拼接成s

我们假设所有的单词都被我们放在了set里

代码详解

#include <unordered_set>
#include <vector>
#include <string>using namespace std;unordered_set<string> wordSet; // 假设已经填充好单词表
vector<int> dp;int process(const string& s, int i) {if (i == s.size()) {return 1;}if (dp[i] != -1) {return dp[i]; // 如果已经计算过，直接返回结果}int lnWays = 0;for (int index = i + 1; index <= s.size(); index++) {// 直接检查当前子字符串 s[i:index] 是否在 wordSet 中if (wordSet.count(s.substr(i, index - i))) {lnWays += process(s, index); // 递归调用下一个位置}}return dp[i] = lnWays; // 存储结果
}int countWays(const string& str) {dp.assign(str.size(), -1); // 初始化动态规划数组return process(str, 0);
}

我们这里就写出来了动态规划无优化的方法

但是这种方法的时间复杂度显然是过高的 因为每次拼接字符串的时候我们都需要遍历整个数组 导致了很多无用的遍历 （我们只需要遍历set中有的就行了）

那么这个时候我们就想起用前缀树了

class TireNode
{
public:unordered_map<char, TireNode*> children;bool isEnd = false;
};class Tire
{
public:TireNode* root;Tire() {root = new TireNode();}void insert(string& str) {TireNode* cur = root;for (auto ch : str) {if (!cur->children.count(ch)) {cur->children[ch] = new TireNode();}cur = cur->children[ch];}cur->isEnd = true;}};

这个时候我们只需要用一个map来记录下各个单词可能走的路径 并且继续下各个单词可能的节点 就能极大的优化查找字符串的效率

unordered_set<string> set;
int process(string& s, int i) {if (i == s.size()){return 1;}int ways = 0;TireNode* node = tire.root;for (int index = i; index < s.size(); index++){char ch = s[index];if (node ->children.count(ch)) {node = node->children[ch];if (node->isEnd == true) {ways += process(s, index + 1);}}else{break;}}return ways;
}