问题描述: 在一个大小为n的数组中，其中有一个数出现的次数超过n/2，求出这个数。...这题看似很简单，但是找到最优解不容易，一般情况我们首先想到最笨的方法，每选一个数，遍历一次数组，复杂度O(N^2),或者先排序再找那个数，复杂度一般为O(NlgN),或者用hash，时间复杂度O(N)，...所以这些都不是最优解，我们先分析一下这个题目，设该数出现的次数为x，则x满足，n/2+1 #include using namespace std; /*在大小为n的数组中寻找次数超过n/2的数*/ int find_data(vector
****************************************************************************************** // // 求和为n...的连续正整数序列 - C++ - by Chimomo // // 题目： 输入一个正整数n，输出全部和为n的连续正整数序列。...//// Answer: Suppose n = i+(i+1)+......+(j-1)+j, then n = (i+j)(j-i+1)/2 = (j*j-i*i+i+j)/2 => j^2+j+(i-i^2-2n) = 0 => j = (sqrt(1-4(i-i^2-2n...n/2], do this arithmetic to check if there is a integer answer.//// Note: 二次函数 ax^2+bx+c=0 的求根公式为： x
我说小朋友：如果想指定 HashMap 对象的容量得用2的N次方 。假如不是2的N次方那么在第一次put 元素的时候也会自动把容量设置为比传入参数大的最小的2的N次方，并不是你指定的这个值。...而本文开头提到的实例化容量大小指的则是数组的大小。 如何计算元素在数组中所对应的下标？...假如初始容量为2的3次方数字8，当哈希值与容量大小减一的值进行与运算时可以保证结果比较均匀的分布在数组上。 ...那么你想想，假如指定的容量大小为5又会怎么样呢？如果是5，那么就会出现非常严重的哈希碰撞，所以为了避免这种情况出现。HashMap 并没有傻乎乎的直接使用用户指定的容量大小。...而是在实例化 HashMap 对象时，如果初始容量大小不是2的N次方则会把 threshold 设置成比传入初始容量大的最小的2的N次方。
学更好的别人， 做更好的自己。...——《微卡智享》 本文长度为1543字，预计阅读4分钟 前言 本题原本按我最喜欢的暴力破解提交的，结果到最后几个大数据的时候提示超时了，最后也是看了官方的思路，了解了动态规划的思路去解的这个题，所以本篇写了两个实现的方法...并创建初始值为0的添加进散列表 2 循环遍历数组的数（同暴力法相同），计算遍历到挡前数的和 3 用当前的和减去我们求到的和的值，去寻找Hash散列表中是否存在减后的值对应的数，如果存在输入值+1，不存在就写入散列表...（提高自己输出东西的质量，以后我也尽量以视频为主，文章贴代码或相关的一些来实现，题外话，写文章还是快，做一个视频动画效果有时候一下子就一天过去了，不过这样我觉得感观上吸收应该会更好，所以会坚持这样下去）... maps; //第一位前缀合肯定是0，默认值为1 maps[0] = 1; int count = 0;
2022-07-09：总长度为n的数组中，所有长度为k的子序列里，有多少子序列的和为偶数？答案2022-07-09：方法一：递归，要i还是不要i。方法二：动态规划。需要两张dp表。代码用rust编写。...k = rand::thread_rng().gen_range(0, n) + 1; let mut arr = random_array(n, vv); let ans1...= arr.len() as i32; // even[i][j] : 在前i个数的范围上(0...i-1)，一定选j个数，加起来是偶数的子序列个数 // odd[i][j] : 在前i个数的范围上...(0...i-1)，一定选j个数，加起来是奇数的子序列个数 let mut even: Vec> = vec!...=n { for j in 1..
2022-08-22：给定一个数组arr，长度为n，最多可以删除一个连续子数组， 求剩下的数组，严格连续递增的子数组最大长度。 n <= 10^6。 来自字节。5.6笔试。...= arr.len() as i32; for L in 0..n { for R in L..n { let mut cur = delete(arr,...dp[(i - 1) as usize] + 1 } else { 1 }; // // rank : 就是当前的数字...// // 1~rank-1 : 第二个信息的max let mut p2 = if rank0 > 1 { st.max1(rank0 - 1) + 1 }...cur += 1; } else { cur = 1; } // 我的当前值是rank // 之前有没有还是rank的记录
2021-08-25：给定数组father大小为N，表示一共有N个节点，father[i] = j 表示点i的父亲是点j， father表示的树一定是一棵树而不是森林，queries是二维数组，大小为M...*2，每一个长度为2的数组都表示一条查询，[4,9], 表示想查询4和9之间的最低公共祖先…，[3,7], 表示想查询3和7之间的最低公共祖先…，tree和queries里面的所有值，都一定在0~N-1...返回一个数组ans，大小为M，ans[i]表示第i条查询的答案。 福大大 答案2021-08-25： 树链剖分。 代码用golang编写。...= make([]int, this.n) this.son = make([]int, this.n) this.siz = make([]int, this.n) this.top...= make([]int, this.n) this.n-- cnum := make([]int, this.n) for i := 0; i < this.n; i++ {
一、pair 1.1pair的定义和结构 在C++中，pair是一个模板类，用于一对值的组合。它位于头文件中。...在C++中，vector是一个动态数组容器可以存储一系列相同类型的元素....容器大小管理:可以使用size（）函数获取vector中元素的数量，使用empty（）函数检查vector是否为空，还可以使用resize（）函数调整ector的大小。...，数组存储结构体类型数据，node是结构体类型 指定长度和初始值的初始化 vector v(n);// 定义一个长度为n的数组，初始值默认为0，下标范围[0, n - 1] vector<int...} else { cout << "向量不为空" << endl; } //获取向量的大小 cout << "向量的大小: " << numbers.size() << endl;
2）理解所有中心的回文最右边界R，和取得R时的中心点C。 3）理解 L…(i`)…C…(i)…R 的结构，以及根据i’回文长度进行的状况划分。...4）每一种情况划分，都可以加速求解i回文半径的过程。...代码用的是第3种方法，用golang编写，代码如下： package main import "fmt" func main() { fmt.Println("yyabcbaxxx的最长回文子串长度是...最长回文子串
2021-07-31：给定数组father，大小为N，表示一共有N个节点，father[i] = j 表示点i的父亲是点j， father表示的树一定是一棵树而不是森林，给定数组values，大小为N，...int v；4)查询在树上从a到b的整条链上所有节点值的累加和，入参：int a, int b。...节点编号是1~n n int // 谁是头 h int // 朴素树结构 tree [][]int // 权重数组 原始的0节点权重是6 -> val[1...= 0 j i这个节点，重儿子是j son []int // siz[i] i这个节点为头的子树，有多少个节点 siz []int // top[i] = j i这个节点...= this.son[u] { this.dfs2(v, v) } } } } // head为头的子树上，所有节点值+
这里P是实对称矩阵，可以采用上一篇的方法，先进行Household变换将P变成三对角矩阵，然后使用QR迭代算法求解特征值和特征向量，迭代次数60，误差eps=0.000001，代码： void cstrq...，通过X*e得到了Q的特征向量eigenvector大小36000*k，它构成了降维子空间。...求矩阵L的特征值矩阵b（大小为201）和特征向量矩阵q（大小为2020）。从中选择特征向量构成新的矩阵num_q，大小为20*k。...构造特征子空间，计算 T 乘以 p_q，得到eigenvector，大小为36000*k，也是k张特征脸。...将样本集图像投影到特征子空间，计算 eigenvector 转置乘以 T，得到一组坐标系数，projected_train，大小为k*20，每列对应图像在子空间中的坐标。
2022-08-22：给定一个数组arr，长度为n，最多可以删除一个连续子数组，求剩下的数组，严格连续递增的子数组最大长度。n 1 { st.max1(rank0 - 1) + 1 } else {...cur += 1; } else { cur = 1; } // 我的当前值是rank // 之前有没有还是rank的记录
vector 常被称为 向量容器，在尾部插入或删除元素，时间复杂度为 O(1)；而在容器头部或者中部插入或删除元素，时间复杂度为 O(n)。...# 创建时指定大小，默认初始值都为 0 vector nums(20,1); # 创建时指定大小，初始值为 1 vector nums {1, 2, 3, 4, 5}; size...，以 second 为第二关键字（字典序） string string 是 C++ 标准库的一个重要的部分，主要用于字符串处理。...# 判空 clear() # 清空 substr(pos,len) # 返回pos开始长度为len的子串 find(s)/rfind(s)...的元素的迭代器 [] # 重载 [] 运算符 参考 STL 教程：C++ STL 快速入门 C++ STL 常用容器 API 总结
Vector容器是C++ STL中的一个动态数组容器，可以在运行时动态地增加或减少其大小，存储相同数据类型的元素，提供了快速的随机访问和在末尾插入或删除元素的功能。...该容器可以方便、灵活地代替数组，容器可以实现动态对数组扩容删除等各种复杂操作，其时间复杂度O(l)常数阶，其他元素的插入和删除为O(n)线性阶，其中n为容器的元素个数，vector具有自动的内存管理机制...2.1 数组向量基础应用如下C++代码，展示了如何使用STL的vector容器对数组进行元素添加、弹出、大小重置和空间调整等操作，并使用自定义函数MyPrint()输出结果。...使用resize()函数重新设置容器的最大存储空间为10，并使用reserve()函数调整容器的空间大小为30，并再次使用MyPrint()函数输出结果。...MyPrint(var); system("pause"); return 0;}2.2 数组向量正/反向遍历如下C++代码，展示了三种不同的遍历方法，分别是使用数组下标、使用正向迭代器和反向迭代器遍历
Vector容器是C++ STL中的一个动态数组容器，可以在运行时动态地增加或减少其大小，存储相同数据类型的元素，提供了快速的随机访问和在末尾插入或删除元素的功能。...该容器可以方便、灵活地代替数组，容器可以实现动态对数组扩容删除等各种复杂操作，其时间复杂度O(l)常数阶，其他元素的插入和删除为O(n)线性阶，其中n为容器的元素个数，vector具有自动的内存管理机制...2.1 数组向量基础应用 如下C++代码，展示了如何使用STL的vector容器对数组进行元素添加、弹出、大小重置和空间调整等操作，并使用自定义函数MyPrint()输出结果。...使用resize()函数重新设置容器的最大存储空间为10，并使用reserve()函数调整容器的空间大小为30，并再次使用MyPrint()函数输出结果。...MyPrint(var); system("pause"); return 0; } 2.2 数组向量正/反向遍历 如下C++代码，展示了三种不同的遍历方法，分别是使用数组下标、使用正向迭代器和反向迭代器遍历
以前一直在用C语言，很多数据结构都是自己造的，比如链表、队列等，但是搞竞赛还是C++ 有优势，感觉好多题都是针对C++ 出题的 所以打算学学C++，所以现在先整理一下STL中一些最常用的容器的使用方法和迭代器备用...容器（Container） 迭代器（Iterator） 1、容器 作为STL的最主要组成部分－－容器，分为向量（vector），双端队列(deque)，表(list)，队列（queue），堆栈(stack... 双端队列deque 基本上与向量相同，唯一的不同是，其在序列头部插入和删除操作也具有常量时间复杂度 表list 对任意元素的访问与对两端的距离成正比，但对某个位置上插入和删除一个项的花费为常数时间...具有快速查找能力 3、迭代器 它的具体实现在中，我们完全可以不管迭代器类是怎么实现的，大多数的时候，把它理解为指针是没有问题的（指针是迭代器的一个特例，它也属于迭代器...) 搜寻「连续发生 n 次」的子序列 set_difference() 差集 set_intersection() 交集 set_symmetric_difference() 对称差集 set_union
STL STL 作为一个封装良好，性能合格的 C++ 标准库，在算法竞赛中运用极其常见。...C++ 标准模板库 (STL, Standard Template Library)：包含一些常用数据结构与算法的模板的 C++ 软件库。...常用容器 顺序容器 向量vector 头文件：#include 连续的顺序的储存结构（和数组一样的类别），但是有长度可变的特性。...que.pop(); 取堆顶 .top() int a = que.top(); 查看大小 / 判空 略 略 进出队复杂度 O(\log n)，取堆顶 $O(1)....字符串连接 + string s = s1 + s2; 尾接字符串 += s += "awa"; 取子串 .substr(起始下标, 子串长度) string sub = s.substr(2, 10)
2022-08-26：用一个大小为 m x n 的二维网格 grid 表示一个箱子 你有 n 颗球。箱子的顶部和底部都是开着的。...箱子中的每个单元格都有一个对角线挡板，跨过单元格的两个角， 可以将球导向左侧或者右侧。 将球导向右侧的挡板跨过左上角和右下角，在网格中用 1 表示。...返回一个大小为 n 的数组 answer ， 其中 answer[i] 是球放在顶部的第 i 列后从底部掉出来的那一列对应的下标， 如果球卡在盒子里，则返回 -1。..., ans); } fn find_ball(grid: &mut Vec>) -> Vec { let n = grid.len() as i32; let...{ // (0,0) (0,1) (0,2) let mut i = 0; let mut j = col; while i < n
详细代码例如以下： /*使用非递归的思想 假设有一个数组 大小为n 那么就使用n 位的二进制 假设对应的位为1 那么就输出这个位 假设对应的位为0 那么就不输出这个位*/ /* 使用位图的思想...构造一个位集合 大小和数组大小一样，假设位图中对应的 位为1,表示能够输出这个数组中的元素 假设位图中对应位为0 表示数组中对应位不输出 这里模拟位图使用的数组 ，这里的重点是模拟数组加1...4）空间复杂度：该方法每次迭代都是独立进行，与上次迭代的结果没有不论什么关系。因此每次输出子集之后内存都能够被反复利用。 仅仅须要一个与原集合相同大小的数组。空间复杂度为O(n)。...第k次迭代的迭代次数为：2^k-1。 n>=k>=1。迭代n次，总的遍历次数为：2^(n+1)-(2+n),n>=1。 则时间复杂都为O(2^n)。 3）空间复杂度 因为该算法。...由于是递归，在第一种方法时，使用了C++中的bitset,这种方法效率非常高，在第二个方法中，使用两个向量的目的是，一个向量记录了这次迭代须要输出的集合，一个向量是为了这次迭代须要參考上次输出的情况。
C++ STL 教程 在前面的章节中，我们已经学习了 C++ 模板的概念。...C++ STL（标准模板库）是一套功能强大的 C++ 模板类，提供了通用的模板类和函数，这些模板类和函数可以实现多种流行和常用的算法和数据结构，如向量、链表、队列、栈。...下面的程序演示了向量容器（一个 C++ 标准的模板），它与数组十分相似，唯一不同的是，向量在需要扩展大小的时候，会自动处理它自己的存储需求： 实例 #include #include...，有几点要注意： push_back( ) 成员函数在向量的末尾插入值，如果有必要会扩展向量的大小。...size( ) 函数显示向量的大小。 begin( ) 函数返回一个指向向量开头的迭代器。 end( ) 函数返回一个指向向量末尾的迭代器。
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
即时通信 IM
ICP备案
云直播
实时音视频
