本文主要是介绍[LeetCode][LCR164]破解闯关密码——重定义排序规则+贪心,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
文章目录
- 1 题目
- 2 思考
- 3 解法1:自写快排
- 4 解法2:为 sort() 函数提供自定义的排序规则
- 4.1 如何为 sort() 函数提供自定义的排序规则:
- 4.2 C++ 匿名函数的使用
- 4.2.1 什么是lambda函数的捕获列表
- 4.3 解法2代码
1 题目
LCR 164. 破解闯关密码
闯关游戏需要破解一组密码,闯关组给出的有关密码的线索是:一个拥有密码所有元素的非负整数数组 password,密码是 password 中所有元素拼接后得到的最小的一个数。请编写一个程序返回这个密码。
- 示例 1:
输入:
password = [15, 8, 7]
输出:"1578"
- 示例 2:
输入:
password = [0, 3, 30, 34, 5, 9]
输出:"03033459"
2 思考
- 这道题的重点就是如何对数字们进行排序,按照一般的想法,就是放在前面的数字由于是在高位,所以应该放更小的数字
- 但是这道题无法使用这种简单的方式进行排序,因为提供的数字位数不一样。如示例1中:“15” 是最大的,但是由于其可以在千位提供更小的 “1”,所以应该放最前面
- 如果按每一个数字的每一个位依次去筛选,那时间复杂度将会很高,而且代码很难写
- 其实回过头看,如果只有2个元素,最朴素的想法就是进行两次尝试:先把 a 放在 b 的前面,组成ab,再尝试组成ba,然后比较ab 和 ba,哪一个小哪一个就是正确的排序方式
- 这种方式可以直接扩展到多个元素
- 若拼接字符串 (x+y>y+x) ,则 x “大于” y;
- 反之,若 (x+y<y+x) ,则 x “小于” y 。
来源:https://leetcode.cn/leetbook/read/illustration-of-algorithm/lxm4ze/
- 也就是如果 x+y>y+x,那么 x 应该放 y 的后面,如果 x+y<y+x,那么 x 就应该放在 y 的前面
3 解法1:自写快排
class Solution {
public:string crackPassword(vector<int>& password) {vector<string> strs;for(auto &ele:password){strs.push_back(to_string(ele));}quickSort(strs, 0, strs.size()-1);string ans;for(auto &ele:strs){ans +=ele;}return ans;}void quickSort(vector<string>& str, int l, int r){if(l>=r) return;int i=l, j=r;while(i<j){while(i<j && str[j]+str[l]>=str[l]+str[j]) --j;while(i<j && str[i]+str[l]<=str[l]+str[i]) ++i;swap(str[i], str[j]);}swap(str[i], str[l]);quickSort(str, l, i-1);quickSort(str, i+1, r);}
};
- 上面的代码中,直接对拼接后的字符串的字典序进行了比较,是按照每个字符的ASCII码值来逐个比较两个字符串的大小的,当此位比较结果相同时,则进行下一位的比较
- 由于是从最高位开始比较的,因此直接比较字符串就可以得到两个数的大小比较结果,而无需转为 int 进行比较
4 解法2:为 sort() 函数提供自定义的排序规则
4.1 如何为 sort() 函数提供自定义的排序规则:
bool customCompare(int a, int b) {// 自定义排序规则,这里以升序排序为例return a < b;
}int main() {vector<int> vec = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5}; // 示例容器// 使用比较函数进行排序sort(vec.begin(), vec.end(), customCompare);// 输出已排序的结果for (int num : vec) {cout << num << " ";}return 0;
}
4.2 C++ 匿名函数的使用
在 C++ 中,lambda 函数的一般语法模板如下:
[capture](parameters) -> return_type { // 函数体
}
capture
是一个可选部分,用于捕获外部变量,可以为空([]
)或包含指定的变量。例如,[x, &y]
表示按值捕获变量 x,按引用捕获变量 y。parameters
是参数列表,与普通函数的参数列表类似。return_type
是返回类型。在 C++11 中,通常可以省略这个部分,因为编译器可以根据返回语句来推断返回类型。{}
内是 lambda 函数的函数体。
例如,一个简单的 lambda 函数可如下定义:
[]() { std::cout << "Hello, Lambda!" << std::endl;
}
这个例子中的 lambda 函数没有捕获列表,没有参数,没有指定返回类型,函数体只是输出 “Hello, Lambda!”。
这种语法形式使得在代码中方便地定义简短的函数,特别是当这些函数只会在局部使用时。
4.2.1 什么是lambda函数的捕获列表
捕获列表(capture list)指定了 lambda 表达式中可以访问的外部变量的方式。捕获列表位于 lambda 表达式的起始位置,用方括号包围。
捕获列表有以下几种形式:
[]
:不捕获任何外部变量。lambda 表达式只能使用其参数和在其作用域内可见的变量。[x, &y]
:按值和按引用捕获变量。通过在方括号中指定变量名,可以选择按值或按引用进行捕获。在方括号中使用逗号分隔不同的捕获方式。
例子:
int x = 1;
int y = 2;
auto func = [x, &y]() { /*...*/ };
在这个例子中,lambda 表达式捕获了变量 x 和 y。x 是按值捕获,因此 lambda 函数会持有 x 的拷贝;y 是按引用捕获,因此 lambda 函数会直接引用变量 y。
使用按值捕获时,lambda 函数会创建外部变量的拷贝,并在其内部使用。而使用按引用捕获时,lambda 函数会直接引用外部变量,因此对外部变量的修改会反映在 lambda 函数中。
捕获外部变量可以让 lambda 表达式更加灵活,并且在使用外部变量时,可以更好地控制其是否可以修改外部变量。
4.3 解法2代码
class Solution {
public:string crackPassword(vector<int>& password) {vector<string> strs;for(auto &ele:password){strs.push_back(to_string(ele));}sort(strs.begin(), strs.end(), [](string &a, string &b){return a+b<b+a;});string ans;for(auto &ele:strs){ans +=ele;}return ans;}
};
这篇关于[LeetCode][LCR164]破解闯关密码——重定义排序规则+贪心的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!