C++ 刷题笔记

ops/2024/9/23 5:22:39/

1、最大组合数

给你 m个整数,你可以按照一定的顺序将他们首尾相连构成一个新的组合数字。请输出值最大的组合数字。
如整数1,23,组合起来有两种情况,123和231,因为231>123,所以231答案。
再比如, 输入:123,456,78,输出:78456123。
请你使用C++实现。

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>// 自定义排序函数
bool compare(const std::string &a, const std::string &b) {return a + b > b + a;
}std::string largestNumber(std::vector<int> &nums) {// 将整数转为字符串std::vector<std::string> numStrs;for (int num : nums) {numStrs.push_back(std::to_string(num));}// 使用自定义的比较函数进行排序std::sort(numStrs.begin(), numStrs.end(), compare);// 如果排序后第一个字符串是 "0",说明所有数字都是 0if (numStrs[0] == "0") {return "0";}// 拼接排序后的字符串std::string result;for (const std::string &str : numStrs) {result += str;}return result;
}int main() {// 输入测试数据std::vector<int> nums = {123, 456, 78};// 输出最大组合数字std::string result = largestNumber(nums);std::cout << "最大组合数字: " << result << std::endl;return 0;
}

这个题主要用到了字典序,字典序遵循以下规则:

  1. 首先比较两个字符串的第一个字符。字母或数字越小的排在前面,越大的排在后面。
  2. 如果第一个字符相同,则继续比较第二个字符,以此类推,直到找到不同的字符为止。
  3. 如果一个字符串的前缀与另一个字符串相同,较短的字符串排在前面。

在程序中,字典序常用来对字符串进行排序,比如在C++的 std::sort 中,默认的比较方式就是字典序。

2、公平送礼

现在进行礼品派发活动,不同礼品价格不同,为公平起见,需要将金部的礼品公平的分配到粉丝手中,里每位粉丝全到的礼品总价格相同。请帮忙确认以下的礼品教量和价格是否可以满是公平的分配原则,可以则返回true,否则返回false。
输入:5,4,1,3,2,3,2
输出:true
因为可以按照(5)、(2,3)、(2,3)、(1,4)组合。
C语言实现。

/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可** * @param prices int整型一维数组 礼物的价格* @param pricesLen int prices数组长度* @param k int整型 粉丝人数* @return bool布尔型*/
#include <stdlib.h>
#include <stdbool.h>
int mycompare(const void* p1, const void* p2) {return *(int*)p2 - *(int*)p1;
}
// 回溯法
bool huisu(int* prices, int* fans, int targetPrice, int idx, int pricesLen, int k) {if (idx == pricesLen) return true;int cur = prices[idx];for (int i = 0; i < k; i++) {if(fans[i] + cur <= targetPrice) {fans[i] += cur;int a = fans[i];// 如果满足就再多分一份礼物if (huisu(prices, fans, targetPrice, idx+1, pricesLen, k)) {return true;}fans[i] -= cur;}if(fans[i] == 0) break;}return false;
}
bool canEqualDistribution(int* prices, int pricesLen, int k) {// write code hereint sum = 0;for (int i = 0; i < pricesLen; i++) {sum += prices[i];}if (sum % k != 0) {return false;}int targetPrice = sum / k;qsort(prices, pricesLen, sizeof(int), mycompare);if (prices[0] > targetPrice) return false;int *fans = (int*)calloc(k, sizeof(int));bool res = huisu(prices, fans, targetPrice, 0, pricesLen, k);free(fans);return res;
}int main() {int prices[] = {5, 4, 1, 3, 2, 3, 2};int n = sizeof(prices) / sizeof(prices[0]);int k = 4;canEqualDistribution(prices, n, k);return 0;
}

这道题主要用回溯法解决,注意C语言的语法问题。

3、最长递增子序列

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;int longestIncreasingSubsequence(const vector<int> &nums)
{if (nums.empty())return 0;// dp[i] 代表以 nums[i] 结尾的最长递增子序列的长度vector<int> dp(nums.size(), 1);int maxLength = 1;for (int i = 1; i < nums.size(); ++i){for (int j = 0; j < i; j++){if (nums[i] > nums[j]){dp[i] = max(dp[i], dp[j] + 1);}}maxLength = max(maxLength, dp[i]);}cout << maxLength << endl;cout << dp[nums.size() - 1] << endl;return dp[nums.size() - 1];
}int main()
{int n;cin >> n;vector<int> nums(n);for (int i = 0; i < n; ++i){cin >> nums[i];}cout << longestIncreasingSubsequence(nums) << endl;return 0;
}

动态规划求解,这里注意要用两个for循环,一个是不行的,会忽略掉很多种情况。一个for循环遍历求dp[i],另一个for循环查看有没有比nums[i]小的,只要有都加入子序列。


http://www.ppmy.cn/ops/111757.html

相关文章

工厂模式(一):简单工厂模式

一、概念 顾名思义&#xff0c;带着工厂&#xff0c;两字肯定就是有标准、快速、统一等等一些工厂独有的特点。 那么什么是简单工厂模式呢&#xff1f; 定义&#xff1a;简单工厂模式是一种创建对象的设计模式&#xff0c;它定义了一个工厂类通过某个静态方法来生成不同类型的…

逻辑漏洞-其二(登录验证码安全)

2.登录验证码安全 验证码漏洞检测流程 2.1 图形验证码 无效验证 2.1.1 验证码可爆破 验证码可爆破&#xff0c;即验证码过于简单&#xff0c;例如验证码中字符数量过少&#xff0c;比如只有四位组成&#xff0c;且只包含 0-9 的数字还没有干扰点 &#xff0c;亦或者 验证码可以…

新装mysql8 并开启外网连接

1. 数据库安装 sudo apt-get update && sudo apt-get install mysql 2. 修改配置文件&#xff0c;允许外网ip访问 sudo vi /etc/mysql/mysql.conf.d/mysqld.cnf 注释掉bind-address这一行&#xff0c;将其修改为&#xff1a; # bind-address 127.0.0.1 bind-add…

安卓玩机工具-----无需root权限 卸载 禁用 删除当前机型app应用 ADB玩机工具

ADB玩机工具 ADB AppControl是很实用的安卓手机应用管理工具&#xff0c;无需root权限&#xff0c;通过usb连接电脑后&#xff0c;可以很方便的进行应用程序安装与卸载&#xff0c;还支持提取手机应用apk文件到电脑上&#xff0c;此外还有手机系统垃圾清理、上传文件等…

Redisson 分布式锁的使用详解

一、分布式锁的概述 1.1 分布式锁的背景 在单机系统中&#xff0c;Java 提供了 synchronized 和 Lock 等锁机制来确保并发情况下的线程安全。然而&#xff0c;在分布式系统中&#xff0c;多个服务实例运行在不同的物理或虚拟机上&#xff0c;无法直接使用这些本地的锁机制来控…

C# 批量更改文件后缀名称

解决问题思路 解决固定文件夹下更改文件后缀名&#xff0c;采用轮询的方式&#xff0c; 流程如下&#xff1a; 获取当前文件名&#xff08;带后缀的文件名&#xff09;截取文件名称&#xff0c;去掉后缀另存为带更改后的后缀文件 注意&#xff1a;采用第三方插件&#xff0…

【MySQL学习】基础指令全解:构建你的数据库技能

&#x1f4c3;个人主页&#xff1a;island1314 &#x1f525;个人专栏&#xff1a;MySQL学习 ⛺️ 欢迎关注&#xff1a;&#x1f44d;点赞 &#x1f442;&#x1f3fd;留言 &#x1f60d;收藏 &#x1f49e; &#x1f49e; &#x1f49e; 引言 下面的操作都是在windows 的…

k8s dashboard token 生成/获取

创建示例用户 在本指南中&#xff0c;我们将了解如何使用 Kubernetes 的服务帐户机制创建新用户、授予该用户管理员权限并使用与该用户绑定的承载令牌登录仪表板。 对于以下每个和的代码片段ServiceAccount&#xff0c;ClusterRoleBinding您都应该将它们复制到新的清单文件(如)…