- 作者：20岁爱吃必胜客（坤制作人），近十年开发经验, 跨域学习者，目前于海外某世界知名高校就读计算机相关专业。
- 荣誉：
阿里云博客专家认证、腾讯开发者社区优质创作者，在CTF省赛校赛多次取得好成绩。跨领域学习，喜欢摄影、弹吉他、咏春拳。文章深入浅出、语言风趣；爱吃必胜客社区创立者，旨在“发现美 欣赏美
⭐️题目
给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。
示例 1：
输入：nums = [1,2,3,1]
输出：true
示例 2：
输入：nums = [1,2,3,4]
输出：false
示例 3：
输入：nums = [1,1,1,3,3,4,3,2,4,2]
输出：true
提示：
1 <= nums.length <= 105
-109 <= nums[i] <= 109
通过次数763,189提交次数1,386,055
🌟题目分析
想法，脑子里没别的，我就想两重循环，最笨的方法。
两个for循环直接干出来，就像插入排序一样。
肯定超时得了~
然后想到，先排序，后前后比较，NlogN
🌟 python实现方法
python set()函数去重，如果去重后长度和原长度不同则返回Ture
变成个 集合
return len(set(nums)) != len(nums)
感觉毫无使用价值，不算是个通法
空间换时间的哈希表更通用
class Solution: def containsDuplicate(self, nums: List[int]) -> bool: #python哈希表 seen = collections.defaultdict(int) for key,value in enumerate(nums): seen[value]+=1 if seen[value]>1: return True return False
enumerate
s = [1, 2, 3, 4, 5] e = enumerate(s) for index, value in e: print('%s, %s' % (index, value)) 输出结果： 0, 1 1, 2 2, 3 3, 4 4, 5
默认字典defaultdict-在访问不存在的键的时候
在访问不存在的键的时候，给一个默认值，不会给异常
collections.defaultdict()函数
collections.defaultdict 空字典模块用法简介
用 defaultdict 快速实现
collections.defaultdict() 方法，可以为字典设置一个默认取值 Default（实质上是什么都没有）。该方法设置的初衷，是为了避免在引用不存在的 key 时候发生的 “KeyError” 错误。
举例：defaultdict 设置默认 value 取值为0
from collections import defaultdict s = 'mississippimississippi' dict = defaultdict(int) for char in s: dict[char]+=1 print(dict) defaultdict(<class 'int'>, {'m': 2, 'i': 8, 's': 8, 'p': 4})
python hash表
在平时刷题的时候经常会用到python的hash表，下面介绍下默认字典的用法。
collections.defaultdict()的使用
示例1.collections.defaultdict(list)
import collections s = [('yellow', 1), ('blue', 2), ('yellow', 3), ('blue', 4), ('red', 1)] # defaultdict d = collections.defaultdict(list) for k, v in s: d[k].append(v) print(d.items())
输出：dict_items([(‘yellow’, [1, 3]), (‘blue’, [2, 4]), (‘red’, [1])])
示例2.collections.defaultdict(set)
import collections s = [('yellow', 1), ('blue', 2), ('yellow', 3), ('blue', 4), ('red', 1)] d = collections.defaultdict(set) for k, v in s: d[k].add(v) print(d.items())
输出：dict_items([(‘yellow’, {1, 3}), (‘blue’, {2, 4}), (‘red’, {1})])
示例3.collections.defaultdict(int)
import collections s = [('yellow', 1), ('blue', 2), ('yellow', 3), ('blue', 4), ('red', 1)] d = collections.defaultdict(set) for k, v in s: d[k].add(v) print(d.items())
输出：dict_items([(‘m’, 1), (‘i’, 4), (‘s’, 4), (‘p’, 2)])
分析
通过示例1、2、3 的输出结果可以看出，结果类型是dict字典类型，defaultdict翻译为默认字典就更好理解了。key值可自定义，value的类型与collections.defaultdict()括号中设置类型的相同，比如collections.defaultdict(list)对应的是[1, 3]、[2, 4]、[1]这样的list类型，而其值与具体操作相关，上例中对应的是相同key的value值。
所以示例明白学会了，其他的对象类型也不难理解。
拓展
python文档数据类型使用说明如下：
class collections.defaultdict([default_factory[, …]])
返回一个新的类似字典的对象。 defaultdict 是内置 dict 类的子类。它重载了一个方法并添加了一个可写的实例变量。其余的功能与 dict 类相同，此处不再重复说明。
第一个参数 default_factory 提供了一个初始值。它默认为 None 。所有的其他参数都等同与 dict 构建器中的参数对待，包括关键词参数。
defaultdict 对象除了支持 dict 的操作，还支持下面的方法作为扩展:
missing(key)
如果 default_factory 是 None ， 它就升起一个 KeyError 并将 key 作为参数。
如果 default_factory 不为 None ， 它就会会被调用，不带参数，为 key 提供一个默认值， 这个值和 key 作为一个对被插入到字典中，并返回。
如果调用 default_factory 升起了一个例外，这个例外就被扩散传递，不经过改变。
这个方法在查询键值失败时，会被 dict 中的 getitem() 调用。不管它是返回值或升起例外，都会被 getitem() 传递。
注意 missing() 不会 被 getitem() 以外的其他方法调用。意思就是 get() 会向正常的dict那样返回 None ，而不是使用 default_factory 。
defaultdict 支持以下实例变量:
default_factory
这个属性被 missing() 方法使用；它从构建器的第一个参数初始化，如果提供了的话，否则就是 None 。
说了半天，越看越糊涂。找的大佬的解释如下：
defaultdict
dict subclass that calls a factory function to supply missing values。
解释：defaultdict属于内建函数dict的一个子类，调用工厂函数提供缺失的值。
工厂函数又是什么呢？来自python 核心编程的解释，工厂函数看上去有点像函数， 实质上他们是类。当你调用它们时， 实际上是生成了该类型的一个实例， 就像工厂生产货物一样。
较熟悉的有：
int(), long(), float(), complex() ,str(), unicode(), basestring() ,list(), tuple() ,type(),set()
除此之外：
dict() ,bool(),frozenset(),object(),classmethod() ,staticmethod(),super(),property() ,file()
这里的defaultdict(function_factory)构建的是一个类似dictionary的对象，其中keys的值可自定义，但是values的类型，是function_factory的类实例，而且具有默认值。比如defaultdict(int)则创建一个类似dictionary对象，里面任何的values都是int的实例，而且就算是一个不存在的key, d[key] 也有一个默认值，这个默认值是int()的默认值0.
函数 int() 总是返回0，是常数函数的特殊情况。一个更快和灵活的方法是使用lambda函数，可以提供任何常量值(不只是0)。
————————————————
版权声明：本文为CSDN博主「kuangd_1992」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/kuangd_1992/article/details/127150196
🌟 set 集合本质-哈希表
python中集合 set 的介绍
Python中的集合类似于数学中的集合概念,它是一组无序、不可重复元素序列,集合用{value1,value2}创建,某种程度上可以把集合看作是没有值的字典。
集合使用大括号{}框定元素，并以逗号进行分隔。
a={1,3,4,1} print(a) {1, 3, 4}
字典和集合的创建方式通常有以下几种：
###字典的创建 d1 = {'name': 'jason', 'age': 20, 'gender': 'male'} d2 = dict({'name': 'jason', 'age': 20, 'gender': 'male'}) d3 = dict([('name', 'jason'), ('age', 20), ('gender', 'male')]) d4 = dict(name='jason', age=20, gender='male') d1 == d2 == d3 ==d4 True ###集合的创建 s1 = {1, 2, 3} s2 = set([1, 2, 3]) s1 == s2 True
🌟 C语言方法
struct hashTable{ int key; UT_hash_handle hh; }; bool containsDuplicate(int* nums, int numsSize){ struct hashTable* set=NULL; for(int i=0; i<numsSize;i++){ struct hashTable * tmp; HASH_FIND_INT(set,nums+i,tmp); if(tmp==NULL){ tmp=malloc(sizeof(struct hashTable)); tmp->key=nums[i]; HASH_ADD_INT(set,key,tmp); }else{ return true; } } return false; }
struct hashTable { int key; UT_hash_handle hh; }; bool containsDuplicate(int* nums, int numsSize) { struct hashTable* set = NULL; for (int i = 0; i < numsSize; i++) { struct hashTable* tmp; HASH_FIND_INT(set, nums + i, tmp); if (tmp == NULL) { tmp = malloc(sizeof(struct hashTable)); tmp->key = nums[i]; HASH_ADD_INT(set, key, tmp); } else { return true; } } return false; }
🌟C语言哈希表
#include "uthash.h" struct my_struct { int id; /* key */ char name[10]; UT_hash_handle hh; /* 使此结构可哈希 makes this structure hashable */ }; /*声明哈希为NULL指针*/ struct my_struct *users = NULL; /* important! initialize to NULL */
这里我们将id作为一个索引值，也就是键值，将name作为value。
注意：一定要包含UT_hash_handle hh（在之后的个别函数中可能会用到这个UT_hash_handle）；hh不需要初始化，它可以命名为任何名称，一般都命名为hh。
查找元素
struct my_struct *find_user(int user_id) { // 返回哈希结构体类型的变量 struct my_struct *s; HASH_FIND_INT( users, &user_id, s ); /* s: output pointer */ return s; // 如果存在就返回正确的地址，反之返回空地址NULL }
在上述代码中，第一个参数users是哈希表，第二个参数是user_id的地址（一定要传递地址）函数的用法而已不必太在意原理。最后s是输出变量。当可以在哈希表中找到相应键值时，s返回给定键的结构，当找不到时s返回NULL。
添加元素
HASH_ADD_INT表示添加的键值为int类型 HASH_ADD_STR表示添加的键值为字符串类型 HASH_ADD_PTR表示添加的键值为指针类型 HASH_ADD表示添加的键值可以是任意类型
void add_user(int user_id, char *name) { struct my_struct *s; /*重复性检查，当把两个相同key值的结构体添加到哈希表中时会报错*/ HASH_FIND_INT(users, &user_id, s); /* id already in the hash? */ /*只有在哈希中不存在ID的情况下，我们才创建该项目并将其添加。否则，我们只修改已经存在的结构。*/ if (s==NULL) { s = (struct my_struct *)malloc(sizeof *s); //现在才实际分配空间 s->id = user_id; HASH_ADD_INT( users, id, s ); /* id: name of key field */ } strcpy(s->name, name); }
HASH_ADD_INT函数中，第一个参数users是哈希表，第二个参数id是键字段的名称。最后一个参数s是指向要添加的结构的指针。
头文件怎么说
#ifndef 是"if not defined"的简写，是预处理功能（宏定义、文件包含、条件编译）当中的条件编译，在实际开发中可以用于做test或者不同版本的不同适配。
在vscode中可以通过json脚本的define来定义ifndef 的值，或者在通过gcc编译的时候添加上宏来进行条件编译。
ifndef 可以根据是否已经定义了一个变量来进行分支选择，其作用是：
防止头文件的重复包含和编译；
便于程序的调试和移植；
什么是万能头文件？
C++的万能头文件是：
#include <bits/stdc++.h>
它是一个包含了每一个标准库的头文件。
优点：
在算法竞赛中节约时间；
减少了编写所有必要头文件的工作量。
缺点：
不是GNU C++库的标准头文件，在部分情况下会编译失败；
包含了很多不必要的东西，会大大增加编译时间。
C++方法
class Solution { public: bool containsDuplicate(vector<int>& nums) { set<int> set; for(int x:nums){ set.insert(x); } if(set.size()!=nums.size()){ return true; } return false; } };
class Solution { public: bool containsDuplicate(vector<int>& nums) { //排序+查 // sort(nums.begin(),nums.end()); // for(int i=0; i<nums.size()-1; i++){ // if(nums[i]==nums[i+1]) // return true; // } // return false; //哈希表方法 unordered_set<int> s; for(auto x:nums){ if(s.find(x)!= s.end()){ return true; } s.insert(x); } return false; } };
class Solution { public: bool containsDuplicate(vector<int>& nums) { //排序+查 // sort(nums.begin(),nums.end()); // for(int i=0; i<nums.size()-1; i++){ // if(nums[i]==nums[i+1]) // return true; // } // return false; //哈希表方法 unordered_set<int> s; for(auto x:nums){ if(s.find(x)== s.end()){ s.insert(x); } else{ return true; } } return false; } };
unordered_set c++哈希表
初始化
创建空的set
unordered_set<int> set1;
拷贝构造
unordered_set<int> set2(set1);
使用迭代器构造
unordered_set<int> set3(set1.begin(), set1.end());
使用数组作为其初值进行构造
unordered_set<int> set4(arr,arr+5);
移动构造
unordered_set<int> set5(move(set2));
使用处置列表进行构造
unordered_set<int> set6 {1,2,10,10};
四、unordered_set的常用内置函数
empty()函数——判断是否为空
//若容器为空，则返回 true；否则 false
set1.empty();
find()函数——查找
//查找2，找到返回迭代器，失败返回end() set1.find(2);
count()函数——出现次数
//返回指2出现的次数，0或1 set1.count(2);
insert()函数——插入元素
//插入元素，返回pair<unordered_set<int>::iterator, bool> set1.insert(3); //使用initializer_list插入元素 set1.insert({1,2,3}); //指定插入位置，如果位置正确会减少插入时间，返回指向插入元素的迭代器 set1.insert(set1.end(), 4); //使用范围迭代器插入 set1.insert(set2.begin(), set2.end());
关于insert函数的返回值：
insert()只传入单个参数（待插入元素）
会返回一个 pair 对象
这个 pair 对象包含一个迭代器，以及一个附加的布尔值用来说明插入是否成功
如果元素被插入，返回的迭代器会指向新元素
如果没有被插入，迭代器指向阻止插入的元素
auto pr = words.insert("ninety"); // Returns a pair - an iterator & a bool value
insert()传入两个参数（迭代器+待插入元素）
可以用一个迭代器作为insert()的第一个参数，它指定了元素被插入的位置
在这种情况下，只会返回一个迭代器
auto iter = words.insert (pr.first, "nine"); // 1st arg is a hint. Returns an iterator
insert()传入初始化列表
插入初始化表中的元素
在这种情况下，什么都没有返回
words.insert({"ten", "seven", "six"}); // Inserting an initializer list
emplace()函数——插入元素(转移构造)
//使用转移构造函数添加新元素3，比insert效率高
set1.emplace(3);
erase()函数——删除元素
//删除操作，成功返回1，失败返回0 set1.erase(1); //删除操作，成功返回下一个pair的迭代器 set1.erase(set1.find(1)); //删除set1的所有元素，返回指向end的迭代器 set1.erase(set1.begin(), set1.end());
bucket_count()函数——篮子数目
//返回容器中的篮子总数 set1.bucket_count();
bucket_size()函数——篮子中元素数目
//返回1号篮子中的元素数
set1.bucket_size(1);
bucket()函数——在哪个篮子
//元素1在哪一个篮子 set1.bucket(1);
clear()函数——清空
set1.clear();
load_factor()函数——负载因子
//负载因子，返回每个篮子元素的平均数，即size/float(bucket_count); set1.load_factor();
rehash()函数——设置篮子数目并重新分布
//设置篮子的数量为20，并且重新rehash set1.rehash(20);
C++ 中 set 和 unordered_set 常用语法
set 和 unordered_set 都是是不重复的集合。set 的底层通过树实现，且会自动为集合内元素按由小到大排序。unordered_set 的底层通过哈希表实现，并不会自动排序。当创建一个不需要排序的集合时应使用 unordered_set，因为哈希表对元素的查找更快。
结论：需要排序的集合用 set，不需要排序的集合用unordered_set。
基于范围的for循环(C++11)
基于范围的for循环(C++11)
for 语句允许简单的范围迭代：
int my_array[5] = {1, 2, 3, 4, 5}; // 每个数组元素乘于 2 for (int &x : my_array) { x *= 2; cout << x << endl; } // auto 类型也是 C++11 新标准中的，用来自动获取变量的类型 for (auto &x : my_array) { x *= 2; cout << x << endl; }
上面for述句的第一部分定义被用来做范围迭代的变量，就像被声明在一般for循环的变量一样，其作用域仅只于循环的范围。而在":"之后的第二区块，代表将被迭代的范围。
实例
#include<iostream> #include<string> #include<cctype> using namespace std; int main() { string str("some string"); // range for 语句 for(auto &c : str) { c = toupper(c); } cout << str << endl; return 0; }
上面的程序使用Range for语句遍历一个字符串，并将所有字符全部变为大写，然后输出结果为：
SOME STRING
参考自 c++ primer plus
int my_array[5] = { 1, 2, 3, 4, 5 }; // 不会改变 my_array 数组中元素的值 // x 将使用 my_array 数组的副本 for (int x : my_array) { x *= 2; cout << x << endl; } // 会改变 my_array 数组中元素的值 // 符号 & 表示 x 是一个引用变量，将使用 my_array 数组的原始数据 // 引用是已定义的变量的别名 for (int& x : my_array) { x *= 2; cout << x << endl; } // 还可直接使用初始化列表 for (int x : { 1, 2, 3, 4, 5 }) { x *= 2; cout << x << endl; }
C++预处理
参数宏
您可以使用 #define 来定义一个带有参数的宏，如下所示：
#include <iostream> using namespace std; #define MIN(a,b) (a<b ? a : b) int main () { int i, j; i = 100; j = 30; cout <<"较小的值为：" << MIN(i, j) << endl; return 0; }
当上面的代码被编译和执行时，它会产生下列结果：
较小的值为：30
条件编译
有几个指令可以用来有选择地对部分程序源代码进行编译。这个过程被称为条件编译。
条件预处理器的结构与 if 选择结构很像。请看下面这段预处理器的代码：
#ifdef NULL #define NULL 0 #endif
您可以只在调试时进行编译，调试开关可以使用一个宏来实现，如下所示：
#ifdef DEBUG cerr <<"Variable x = " << x << endl; #endif
如果在指令 #ifdef DEBUG 之前已经定义了符号常量 DEBUG，则会对程序中的 cerr 语句进行编译。您可以使用 #if 0 语句注释掉程序的一部分，如下所示：
#if 0 不进行编译的代码 #endif
让我们尝试下面的实例：
实例
#include <iostream> using namespace std; #define DEBUG #define MIN(a,b) (((a)<(b)) ? a : b) int main () { int i, j; i = 100; j = 30; #ifdef DEBUG cerr <<"Trace: Inside main function" << endl; #endif #if 0 /* 这是注释部分 */ cout << MKSTR(HELLO C++) << endl; #endif cout <<"The minimum is " << MIN(i, j) << endl; #ifdef DEBUG cerr <<"Trace: Coming out of main function" << endl; #endif return 0; }
当上面的代码被编译和执行时，它会产生下列结果：
Trace: Inside main function The minimum is 30 Trace: Coming out of main function
⭐️总结
数组存在重复元素，首先我们可以将数组排序，然后再遍历判断，但是这样的复杂度是 NlogN，
但是，我一般会选择牺牲空间保时间，所以这里我将使用哈希表来解决，让时间复杂度为 N。
🌟 流程如下：
创建一个哈希表，然后从左往右遍历数组。
检测哈希表中是否已存在当前字符，若存在，直接返回结果，若不存在，将当前字符加入哈希表，供后续判断使用即可
🌟 我的故事
python学习之路任重而道远，要想学完说容易也容易，说难也难。 很多人说python最好学了，但扪心自问，你会用python做什么了？
刚开始在大学学习c语言，写一个飞行棋的小游戏，用dos界面来做，真是出力不讨好。 地图要自己一点一点画出来，就像这样：
================ | | | | |===============
从此讨厌编程，不想继续学下去。每次作业应付。 算法考试，数据结构考试随便背代码，只求通过。 最后呢？我学会变成了吗？只能对一些概念侃侃而谈，但真的会几行代码，能写出实用工具吗？ 答案变得模糊。 所以我们要从现在开始，学好python，不要再糊弄下去！！！
