什么做网站做个多少钱啊,wordpress样式表,外贸 wordpress英文版,南京网站南京网站设计制作公司目录 正数数组中那两个数结果最大 #xff08;贪心#xff09;题目题目分析代码详解 最小相机覆盖问题 #xff08;二叉树递归套路#xff09;题目题目分析代码详解 拼接字符串 #xff08;动态规划 前缀树#xff09;题目题目分析代码详解 正数数组中那两个数结果最大 贪心题目题目分析代码详解 最小相机覆盖问题 二叉树递归套路题目题目分析代码详解 拼接字符串 动态规划 前缀树题目题目分析代码详解 正数数组中那两个数结果最大 贪心
题目
给定一个由正整数组成的数组 现在要求你返回哪两个数组 的结果最大
题目分析
这道题和算法提升六中的异或有着明显的不同 因为在运算中 只要有一个数是0 最后的结果就是0
也就是说 如果我们当前位是0 走0号线 1号线都是有理由的 但是我们无法比较0和1号线下面谁更好 所以说前缀树的方式是行不通的
但是 的特性告诉我们 尽量要前面位数的数字都为1
所以说我们就能有这样的思路
从最高位开始遍历整个数组 查看当前位置1的数量
如果数量小于1 则说明当前位必定是0 没法求出最大值如果数量等于2 我们就可以直接将这两个数相与 得出最终答案如果数量大于3 则说明当前位必定是1 继续求下个为止的数据即可
代码详解
int Maxxx(vectorint 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的子节点放置一个相机
所以说我们要推出这三种可能性
X有相机 且X下方都被覆盖了X无相机 且X下方都被覆盖了 且X也被覆盖了X无相机 且X下方都被覆盖了 且X没被覆盖
代码详解
#include iostream
#include memoryclass 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 stringusing namespace std;unordered_setstring wordSet; // 假设已经填充好单词表
vectorint 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_mapchar, 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_setstring 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;
}
