当前位置：首页 > article >正文

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

article 2024/11/2 16:21:00

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

题目

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

题目分析

这道题和算法提升六中的异或有着明显的不同因为在&运算中只要有一个数是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的子节点放置一个相机

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

X有相机且X下方都被覆盖了
X无相机且X下方都被覆盖了且X也被覆盖了
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;
}