面试笔试算法学习总结
2021-07-03 00:19:03 0 举报AI智能生成
面试笔试算法学习总结
作者其他创作
大纲/内容
leetcode
oj-599.两数之和
暴力枚举
双层for循环
有序，时间复杂度o(n方),空间复杂度o(1)
无序，时间复杂度o(n方),空间复杂度o(1)
二分查找
固定一个值，查找另一个值
有序:时间复杂度o(nlogn)，空间复杂度O（1）
无序:时间复杂度o(nlogn)，空间复杂度O（1）
使用快排，复杂度o(nlogn)
总复杂度o(2nlogn)，约等于nlongn
unordered_map
值作为key，下标作为value
查找对应的值的count是不是为1
有序:时间复杂度o（n），空间复杂度o（n）
无序:时间复杂度o（n），空间复杂度o（n）
hash不需要排序，所以不影响
双指针
一个指针指向数组头，一个指针指向数组位
如果指针值相加相等输出
如果和大于t，左移右指针，如果和小于t，右移左指针
有序: 时间复杂度0（n/2），也就是o(n),空间复杂度o(1)
无序: 时间复杂度o(nlogn),空间复杂度o(1)
nlogn+n约等于nlongn
总结：有序使用双指针最快，无序使用unordered_map最快
oj-600.杨氏矩阵
暴力枚举
时间复杂度o(n*m)，空间复杂度o(1)
记录每个元素位置
时间复杂度o(n*m)，空间复杂度o(1)
从矩阵左下角出发，向右走/向上走，调整指针方法
时间复杂度o(n+m)，空间复杂度o(1)
矩阵的下标x和y，和上题的双指针本质是一样的
le-01.两数之和
unordered_map
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> ans;
unordered_map<int,int> m;
for(int i=0;i<nums.size();i++){
if(m.count(target-nums[i])==1) {
ans.push_back(m[target-nums[i]]);
ans.push_back(i);
break;
}
m[nums[i]]=i;
}
return ans;
}
};
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> ans;
unordered_map<int,int> m;
for(int i=0;i<nums.size();i++){
if(m.count(target-nums[i])==1) {
ans.push_back(m[target-nums[i]]);
ans.push_back(i);
break;
}
m[nums[i]]=i;
}
return ans;
}
};
le-07.整数反转
反转过程可能数值越界，比如2099999999
class Solution {
public:
int reverse(int x) {
int t=0;
while(x){
if(t>INT_MAX /10 || t== INT_MAX/10 && x>7) {
return 0;
}
if(t<INT_MIN/10 || t==INT_MIN/10 && x<-8){
return 0;
}
t=t*10+x%10;
x/=10;
}
return t;
}
};
public:
int reverse(int x) {
int t=0;
while(x){
if(t>INT_MAX /10 || t== INT_MAX/10 && x>7) {
return 0;
}
if(t<INT_MIN/10 || t==INT_MIN/10 && x<-8){
return 0;
}
t=t*10+x%10;
x/=10;
}
return t;
}
};
le-09.回文数
注意负数不算回文数
class Solution {
public:
bool isPalindrome(int x) {
if(x<0){
return false;
}
long long a = (long long)x;
long long b =0;
while(a>0){
b=b*10+a%10;
a/=10;
}
if(b==(long long)x) {
return true;
} else {
return false;
}
}
};
public:
bool isPalindrome(int x) {
if(x<0){
return false;
}
long long a = (long long)x;
long long b =0;
while(a>0){
b=b*10+a%10;
a/=10;
}
if(b==(long long)x) {
return true;
} else {
return false;
}
}
};
le-13.罗马数字转整数
class Solution {
public:
int romanToInt(string s) {
int ans=0;
for(int i =0;i<s.size();i++){
if(s[i]=='V'){
ans+=5;
}else if(s[i]=='L'){
ans+=50;
}else if(s[i]=='D'){
ans+=500;
}else if(s[i]=='M'){
ans+=1000;
}else if(s[i]=='I'){
if(s[i+1]=='V'){
ans+=4;
i++;
}else if(s[i+1]=='X'){
ans+=9;
i++;
}else{
ans+=1;
}
}else if(s[i]=='X'){
if(s[i+1]=='L'){
ans+=40;
i++;
}else if(s[i+1]=='C'){
ans+=90;
i++;
}else{
ans+=10;
}
}else if(s[i]=='C'){
if(s[i+1]=='D' || s[i+1]=='M'){
ans+=(s[i+1]=='D')? 400:900;
i++;
}else{
ans+=100;
}
}
}
return ans;
}
};
public:
int romanToInt(string s) {
int ans=0;
for(int i =0;i<s.size();i++){
if(s[i]=='V'){
ans+=5;
}else if(s[i]=='L'){
ans+=50;
}else if(s[i]=='D'){
ans+=500;
}else if(s[i]=='M'){
ans+=1000;
}else if(s[i]=='I'){
if(s[i+1]=='V'){
ans+=4;
i++;
}else if(s[i+1]=='X'){
ans+=9;
i++;
}else{
ans+=1;
}
}else if(s[i]=='X'){
if(s[i+1]=='L'){
ans+=40;
i++;
}else if(s[i+1]=='C'){
ans+=90;
i++;
}else{
ans+=10;
}
}else if(s[i]=='C'){
if(s[i+1]=='D' || s[i+1]=='M'){
ans+=(s[i+1]=='D')? 400:900;
i++;
}else{
ans+=100;
}
}
}
return ans;
}
};
le-14.最长公共前缀
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
if(strs.size()==0) {
return "";
}
string ans =strs[0];
for(int i =1;i<strs.size();i++){
string t=ans;
ans="";
for(int j=0;j<t.size() && j<strs[i].size();j++){
if(t[j]==strs[i][j]){
ans+=t[j];
}else{
break;
}
}
if(ans==""){
break;
}
}
return ans;
}
};
public:
string longestCommonPrefix(vector<string>& strs) {
if(strs.size()==0) {
return "";
}
string ans =strs[0];
for(int i =1;i<strs.size();i++){
string t=ans;
ans="";
for(int j=0;j<t.size() && j<strs[i].size();j++){
if(t[j]==strs[i][j]){
ans+=t[j];
}else{
break;
}
}
if(ans==""){
break;
}
}
return ans;
}
};
le-26. 删除有序数组中的重复项
不适用额外空间，使用两个指针，一个当前存储的指针，一个遍历的指针
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
if(nums.size()==0){
return 0;
}
int ind=1,last=nums[0];
for(int i =1;i<nums.size();i++){
if(last !=nums[i]){
nums[ind]=nums[i];
ind++;
last=nums[i];
}
}
return ind;
}
};
public:
int removeDuplicates(vector<int>& nums) {
if(nums.size()==0){
return 0;
}
int ind=1,last=nums[0];
for(int i =1;i<nums.size();i++){
if(last !=nums[i]){
nums[ind]=nums[i];
ind++;
last=nums[i];
}
}
return ind;
}
};
le-35.搜索插入位置
二分查找
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
if(target> nums[nums.size()-1]) {
return nums.size();
}
int l =0,r=nums.size()-1;
while(l!=r){
int mid=(l+r)/2;
if(nums[mid]>=target){
r=mid;
}else{
l=mid+1;
}
}
return l;
}
};
public:
int searchInsert(vector<int>& nums, int target) {
if(target> nums[nums.size()-1]) {
return nums.size();
}
int l =0,r=nums.size()-1;
while(l!=r){
int mid=(l+r)/2;
if(nums[mid]>=target){
r=mid;
}else{
l=mid+1;
}
}
return l;
}
};
le-69.x的平方根
二分查找
class Solution {
public:
int mySqrt(int x) {
long long l=0,r=x;
while(l!=r){
long long mid=(l+r+1)/2;
if(mid*mid<=x){
l=mid;
}else{
r=mid-1;
}
}
return r;
}
};
public:
int mySqrt(int x) {
long long l=0,r=x;
while(l!=r){
long long mid=(l+r+1)/2;
if(mid*mid<=x){
l=mid;
}else{
r=mid-1;
}
}
return r;
}
};
le-278.第一个错误版本
二分查找
class Solution {
public:
int firstBadVersion(int n) {
long long l=1,r=n;
while(l!=r){
long long mid=(l+r)/2;
if(isBadVersion(mid)){
r=mid;
}else{
l=mid+1;
}
}
return l;
}
};
public:
int firstBadVersion(int n) {
long long l=1,r=n;
while(l!=r){
long long mid=(l+r)/2;
if(isBadVersion(mid)){
r=mid;
}else{
l=mid+1;
}
}
return l;
}
};
le-38.外观数列
class Solution {
public:
string ans[35]={"","1"};
void work (string &s,int cnt,char c){
s+=(char)(cnt+'0');
s+=c;
}
void func(string &s1, string &s2) {
int cnt=1;
for(int i =1;i<s1.size();i++){
if(s1[i-1]==s1[i]){
cnt++;
}else{
work(s2,cnt,s1[i-1]);
cnt=1;
}
}
work(s2,cnt,s1[s1.size()-1]);
}
string countAndSay(int n) {
for(int i=2;i<=n;i++){
func(ans[i-1],ans[i]);
}
return ans[n];
}
};
public:
string ans[35]={"","1"};
void work (string &s,int cnt,char c){
s+=(char)(cnt+'0');
s+=c;
}
void func(string &s1, string &s2) {
int cnt=1;
for(int i =1;i<s1.size();i++){
if(s1[i-1]==s1[i]){
cnt++;
}else{
work(s2,cnt,s1[i-1]);
cnt=1;
}
}
work(s2,cnt,s1[s1.size()-1]);
}
string countAndSay(int n) {
for(int i=2;i<=n;i++){
func(ans[i-1],ans[i]);
}
return ans[n];
}
};
le-136.只出现一次的数字
异或原理，相同的数异或等于0
class Solution {
public:
int singleNumber(vector<int>& nums) {
int ans=0;
for(int i =0;i<nums.size();i++){
ans^=nums[i];
}
return ans;
}
};
public:
int singleNumber(vector<int>& nums) {
int ans=0;
for(int i =0;i<nums.size();i++){
ans^=nums[i];
}
return ans;
}
};
le-66.加一
本质是大整数加法
递归与排列组合
oj-240.图形打印
画x图形
每次递归画左上右上中间左下右下的图形
oj-235.递归实现指数型枚举
从n中任意选一些
每一层选择一个数字，存在num[ind]里面
start=>这层从几开始选
ind=>当前层级（选的是第几个数）
本质是搜索，深度优先搜索，需要回溯机制，oj-235-2.cpp的cnt就是回溯机制
oj-236.递归实现组合型枚举
从N个数中选择M个数
CNM = N*(N-1)*(N-2)*...*M/1*2*3*...*M
比235题多一个参数，还剩几个数需要选，作为递归边界条件，还剩的是0个数，则结束返回
oj-237.递归实现排列性枚举
N个数字全排列
ANN=N*(N-1)*(N-2)*....*1
mark数组标记是否被占用
应用
235 从n中任意选一些
236 从N个数中选择M个数
237 N个数字全排列
将这些数字转为数组下标，可以有很多应用场景
STL使用（标准模板库）
STL六大组件
容器
vector
list
deque
set
map
算法
sort
search
适配器
迭代器
泛型指针
分配器
malloc
calloc
仿函数
字符串
引入头文件<string>
声明 string str
str.size()/str.length()返回字符串长度
str.find("找什么",从哪里找)
str="abcde"; str.find("cd")返回2
str="abcde"; str.find("cd",3)返回string::npos, size_t类型，值是-1
str.insert(哪里,"什么")--插入
str="abcde";str.insert(2,"123");输出ab123cde
str.substr(在哪，长度)--截取
str="abcde";str.substr(2,3);输出cde
str="abcde";str.substr(2);输出cde---截取到最后
str.replace(在哪,长度,"什么")---替换
str.begin()指向字符串的头指针
str.end()指向'\0'的指针
sort(str.begin(),str.end())对字符串排序
reverse(str.begin(),str.end())对于字符串反转
vector---向量---动态数组
引入头文件<vector>
声明 vector<int> v;
v.size()---获得元素的数量
v.push_back(x)---在最后加入x
v[a]---访问下标为a的元素
可用这种方法，给某个元素赋值
vector<int> v(5,1)---申请5个大的空间，初始化都为1
vector<int> v(3,5)---3个5
v.capacity()---返回vector的空间大小
扩容大小依赖于编译器，可能是2倍，可能是1.5倍
二维数组 vector<vector<int> > v;
C++11标准前>>之间必须有空格
C++11标准后可以
编译指定标准方法---g++ aaa.cpp -std=c++11
二维数组赋值 vector<int> v2(5); v.push_back(v2);
二维数组访问 v[1][2]
二维数组初始化vector<vector<int> > v(5,vector<int>(6,2));---初始化5行6列的值全为2的数组
字符串的vector类型 vector<string> v;
可以排序--sort(v.begin(),v.end());
自定义类型的vector vector<node> v; v.push_back((node){4,5,6});
stack--栈
头文件<stack>
声明stack<int> sta;
sta.size()---返回元素数量
sta.push(x)--向栈顶插入x
sta.pop()---弹出栈顶元素
sta.top()---栈顶元素
sta.empty()--是否为空
双端队列容器封装出来，去掉头端插入弹出，是容器适配器
queue--队列
头文件<queue>
声明queue<int> que;
que.size()返回元素数量
que.push(x)--插入元素
que.pop()--出队
que.front()--队首元素
que.empty()--是否为空
que.back()---队尾元素
双端队列封装出来，是容器适配器
队列没有迭代器
deque双端队列
头文件<deque>
声明 deque<int> que;
随机访问常数级别
队尾对头插入/移除常数级别
插入或移除--线性级别o(n)
que.size()--返回元素数量
que.push_front(x)---头部插入
que.pop_front()--头部弹出
que.push_back(x)--尾部插入
que_pop_back()--尾部弹出
que.fornt()---头部元素
que.back()--尾部元素
双端队列可以通过下标直接访问---que[i]
本质是一个指针表--每个指针指向实际的内存空间
双端队列是顺序容器
priority_queue优先队列
头文件<queue>
本质不是队列，是个堆，是数组模拟的二叉树
随便入队
出队是优先级最高的元素
声明priority_queue<int> que
que.size()返回元素数量
que.push(x)--插入元素
que.pop()--弹出元素
que.top()--对顶元素
que.empty()--判断是否空
默认是大顶堆，值越大优先级越高priority_queu<int,vector<int>,less<int> > que;
实现小顶堆priority_queu<int,vector<int>,greater<int> > que;
自定义类型的优先队列 priority_queue<node> que; que.push((node){3,5});
排序方法需要指定
默认排序方法：重载小于号（重载大于号没有用）
struct node内部 bool operator< (const node &a) const { return this->x >a.x;}
默认大顶堆，重载小于号，小于号里面实现>的功能，最终实现小顶堆
指定排序方法--仿函数
prioriy_queue<node,vector<node>, cmp>que; 声明时指定cmp函数
struct cmp{bool operator()(const node &a, const node &b}{return a.x>b.x}
重载括号，输出小顶堆
注意点
1. 涉及到排序的容器，都需要指定排序方法（比较方法）
2. 如果重载，必须重载小于号，重载大于号没有用
set集合
一种集合，可排序、可去重
插入、查找、删除操作复杂度是对数级别的
一般使用平衡树实现
红黑树
引入头文件<set>
声明 set<int> s;
s.size()--返回元素数量
s.insert(x);--插入元素
s.erase(x);---删除元素
s.find(x);---查找元素---返回一个迭代器，通过判断是不是s.end()判断是否找到
s.count(x);---统计set中x的数量；0就是没有，1就是有
迭代器遍历---for(auto it=s.begin();it != s.end(); it++) { cout << *it << " ";} 输出从小到大的排序
编译加上-std=c++11
反迭代器rbegin()指向最后一位；rend()指向第一位前一位；
自定义类型的set结构
需要重载小于号
bool operator< (const node &b) const {return this->x <b.x;}
multiset
允许元素重复
头文件<set>
unordered_set
set的无序版本
数据结构是hash表
操作复杂度是常数级的
头文件<unordered_set>
编译需要增加-std=c++11
声明unordered_set<int> s;
s.size();---返回元素数量
s.insert(x)---插入元素x
s.erase(x);--删除x元素
s.find(x);---查找x元素
s.find("abc")!=s.end()----找到
s.count(x);---返回元素数量
如果要使用自定义结构，自己需要实现hash方法
unordered_multiset
map
存储键值对的数据结构
存储结构是红黑树
有序的
操作复杂度都是对数级的o(logN)
如果键是自定义，需要给出键排序方法
set的增强扩展版
存储pair
pair<int,char>
存储两个字段
需要头文件<utility>
通过make_pair(x,y);
通过a.firt访问前面的，通过second访问后面的
引入头文件<map>
声明map<int,char> m;
map中第一个是键值，是唯一的
m.size()--返回元素数量
m.insert(pair)--插入元素
m.erase(key);---删除键值为key的元素
m.find(x);--查找
m.count(x);---计数
m[key]='A';---直接访问和修改
m[key]访问，如果key不存在，会插入一个元素，值为默认值，int为0
如果频繁访问，建议使用临时值存储下来t=m["abc"]
迭代器遍历---for(auto it=m.begin();it != m.end(); it++) { cout << it->first << " "<<it->second<<endl;} 输出元素通过键的字典序排序
编译加上-std=c++11
multimap
允许多个相同键值的键值对存在
不能使用m.["abc"]访问，因为可能有多个
unordered_map
hash表结构
操作复杂度平均常数级
扩容等特殊场景不一定快
unordered_multimap
oj
oj-378.字符串括号匹配2
stack
sta.push()
sta.top()
sta.pop()
oj-379.仓库日志
stack
货物站
极大值栈
新来元素和栈顶元素比较，谁大入谁
同理可以做一个极小栈
oj-569.溶液模拟器
stack
oj-384.敲七
queue
oj-385.海港
queue
搜索
分类
深度优先搜索DFS
广度优先搜索BFS
应用
遍历树
搜索地图
深搜+递归
解决连通性问题
1. 存地图，外面存一圈0，方便判断边界
2. 方向数组的使用
3. 去重
改地图
标记数组
广搜+队列
解决最少步数问题
也可以解决连通性问题
DFS.CPP
OJ-399.小明吃饭
bfs广搜
oj-535.瓷砖
dfs深度搜索，查找连通性
可以到达的瓷砖的总数
oj-536. 最大黑色区域
整行输入技巧，并且从1开始存
for(int i =1;i<=n;i++){
cin>>&mmap[i][1];
}
cin>>&mmap[i][1];
}
遍历找到1，从这个1开始深搜，连通性计数，找到最大的区域
oj-397.僵尸来袭
与536题目接近，这个题目求联通区域的数量
使用深搜遍历
oj-396.填涂颜色
从“1”圈外的0入手，因为数组本身被1层“0”包围，我们遍历外层的0，将外层的零值修改为2
注意需要判断边界
可以用深搜，也可以用广搜，这里用的广搜
双层循环输出，遇到1输出1，遇到2输出0，遇到0输出2
oj-404. 01迷宫简易版
因为0-1-0-1变化，通过不同判断，所以不能依赖外圈0，需要判断边界
直接修改原数组有问题，增加标记数组判断
可以深搜，可以广搜，这里用广搜
oj-405. 01迷宫
查询30000次可能超时，使用记忆化数组
记忆数组可以复用标记数组mark
另外还需要一个数据结构，这里是队列，存储联通的点
oj-304. 骑士风度的牛
马走日的走法--方向数组不同
最少步数--用广搜
oj-398. 马的遍历
马走日的走法--方向数组不同
需要判断边界
可能有走不到的点，记得标记-1
oj-401. 奇怪的象棋游戏升级版
既能马走日，又能象走田---方向数组变化
判断边界
oj-303. 矩阵距离一
以0为起点遍历，可能会超时
可以考虑以1为起点
多个起点的场景
将多个起点先放入队列，然后启动广搜
oj-305. 乳草的入侵
8个方向，方向数组需要更新
行列输入反的
起点xy转化,1,1对应左下角
oj-81.小明回家
走地图，途径某点，再到达终点，买手机后可能回头路
去重：两个标记数组，或者用bitmap标记
//flag==0 没手机
//flag==1 有手机
//mark[x][y]==0 有没有手机都没去过
//mark[x][y]==1 没有手机去过
//mark[x][y]==2 有手机去过
//mark[x][y]==3 有没有手机都去过
//flag==1 有手机
//mark[x][y]==0 有没有手机都没去过
//mark[x][y]==1 没有手机去过
//mark[x][y]==2 有手机去过
//mark[x][y]==3 有没有手机都去过
mark标记使用flag+1赋值
另外位运算优先级低，注意加括号
oj-527.飞跃原野
能飞能走，飞有能量限制，走不消耗能量
需要三位mark标记数组，最后一维代表能量
oj-402.奇怪的电梯
最小步数用广搜
结构用楼层加上步数
oj-528.关系网络
通过最少的人，广度搜索
oj-530. 警察找车
不是最小步数，但是需要按层搜索，所以还是要用广搜
每一层遍历前，需要记录当前层的数量
每一层分别去重
起点也可能是终点，所以第一次离开后要标记成.
oj-529.龙与虫
将所有能打到敌人的地点都标记为终点
最小步数用广搜
因为多次搜索，每次搜索需要恢复原始地图
oj-531. 奇怪的电视
二进制位存储状态
oj-534.体积
oj-235.递归实现指数型枚举
使用check数组标记去重
oj-537. 门票问题
oj-236.递归实现组合型枚举
字母先排序
oj-539. 速算游戏
转化数字
通过递归枚举顺序
算--库里
sort
oj-540.生日购物
类似oj-235.递归实现指数型枚举
选取任意个，检查和为x
2的40次方，必超时
分成两半搜
oj-541. 相遇问题
1.暴力求每个人从1到N的所有时间答案
递归、深搜
从1点出发，向2到N查找，如果有路就走，递归如果走到n点就保留答案
2.找两个人的数组中有没有相同的，有相同的找最小的
从两个人的时间答案中比较
每个人的路怎么存，----通过邻接矩阵
怎么递归---两个参数，到达的点和当前的时间
如果当前是N点，找到答案了，存储时间
两个人分别求解，存在两个数组中，通过index表示人，开三维数组
搜索五要素
1.存--状态是如何存储定义的
dfs--递归的参数
bfs--队列中存储的自定义结构
2.起
3.终
4.转
状态如何转移
5.重
开标记数组
必考点
排列组合
搜索
模拟
二分
stl容器
编码能力提升
欧拉计划
1. 3或者5的倍数之和
方法1.遍历判断
方法2.(首数+尾数)*个数/2等于总和
2.斐波那契额数列偶数和
方法1.定义数组存所有数，遍历判断累加
方法2.只保存前一项和后一项，遍历累加
4.最大三位数乘积的回文数
判断回文
两层循环，内层循环从i开始
36.一百万内十进制和二进制都是回文的数字和
判断n进制回文
6.和的平方和平方和的差
8.连续13个数的最大乘积
注意遇到0的处理
11.四个方向最大乘积
方向矩阵
14.最长考拉兹序列
int变量越界 long long
记忆数组--空间换时间，num数组存储
13.大整数加法
字符顺序颠倒
0位存数字长度
1-n位存数字
每位加法
每位判断大于9则进位处理
14.第一个1000位的斐波那契额数列
利用大整数加法计算数列
处理前一位和后一位的技巧
大整数乘法
最小长度为a的长度加上b的长度-1
每一位计算结果加入a的位置+b的位置-1
进位不能++，要/10
大整数减法
先判断大小，存flag符号
逐位相减，负数借位
15.网格路径
存储数据，外面包一圈0
每个点的方法的左边点的方法加上上面点的方法
18.最大路径和
存储三角形数据
本行数据等于上方数据和左上方数据较大者和当前数据相加
外面包一圈零
oj-590树塔狂想曲
num数组存储原数组
utd数组存储从上往下求的数组
dtu数组存储从下往上求的数组
ans数组存储经过本节点的最大路径数组
fin存储本行的最大路径、次大路径、最大路径的j列
用scanf提高效率
二分专题
排序
排序函数sort <algorithm>
sort（num,num+10）
sort(num,num+10,cmp)
bool cmp(const int &a, const int &b) {retuan a>b;}
oj/sort.cpp
oj-381.谁拿了最多奖学金
sort排序
#include <string>头文件
只能用cin输入，不能用scanf
可以直接赋值 s="abc"
可以直接按照字典序用><比较大小
可以用+连接两个字符串s=s1+s2
s.size()/s.length()获取字符串长度
oj-375.cpp奖学金
sort排序
oj-380 大统领投票
sort排序
长整数排序
#include <string>头文件
只能用cin输入，不能用scanf
可以直接赋值 s="abc"
可以直接按照字典序用><比较大小
可以用+连接两个字符串s=s1+s2
s.size()/s.length()获取字符串长度
euler-22.名字打分
名字文件整理
:%s/","/ /g
名字从文件输入
while(cin>>name[n])
名字排序
sort（name,name+n）
二分
二分精确
oj-388奇怪的刮刮乐
先sort排序
后二分查找精确值
oj-386.吃瓜群众
定义一个struct包含瓜的数量和编号
自定义排序方法
后二分查找精确值
while(l<=r){
int mid =(l+r)/2;
if(wm[mid].num==t){
printf("%d\n",wm[mid].ind);
break;
}
if(wm[mid].num<t){
l=mid+1;
}else{
r=mid-1;
}
}
int mid =(l+r)/2;
if(wm[mid].num==t){
printf("%d\n",wm[mid].ind);
break;
}
if(wm[mid].num<t){
l=mid+1;
}else{
r=mid-1;
}
}
二分特殊
oj-387吃瓜群众升级版
二分特殊情况
0000011111找第一个1
while(l!=r){
int mid =(l+r)/2;
if(wm[mid].num>=t){
r=mid;
}else{
l=mid+1;
}
}
int mid =(l+r)/2;
if(wm[mid].num>=t){
r=mid;
}else{
l=mid+1;
}
}
1111100000找最后一个1
while(l!=r){
int mid =(l+r+1)/2;
if(wm[mid].num>=t){
r=mid-1;
}else{
l=mid;
}
}
int mid =(l+r+1)/2;
if(wm[mid].num>=t){
r=mid-1;
}else{
l=mid;
}
}
建立墙
wm[0].num=2000000000;
wm[0].ind=0;
wm[0].ind=0;
参加排序
找不到时能输出编号0
二分答案
oj-390原木切割
二分答案
小段长度递增--木头段数递减
归结为11110000二分特殊情况
以小段长度为方法的索引，求段数
while(l!=r){
int mid =(l+r+1)/2;
if(func(mid)>=t){
l=mid;
}else{
r=mid-1;
}
}
int mid =(l+r+1)/2;
if(func(mid)>=t){
l=mid;
}else{
r=mid-1;
}
}
oj-389暴躁的程序猿
二分答案
随着距离的增大，安排人数递减
oj-393切绳子
二分答案
小数二分答案
while(r-l>精度)
double l=0, r=tr;
while(r-l>0.00001){
double mid = (l+r)/2;
int s=func(mid);
if(s>=m){
l=mid;
}else{
r=mid;
}
}
while(r-l>0.00001){
double mid = (l+r)/2;
int s=func(mid);
if(s>=m){
l=mid;
}else{
r=mid;
}
}
保留两位小数，舍掉两位后的所有数
方法1
1.2356*100
强行转int 123
123/100.0=1.23
printf("%.2f\n",(int)(t*100)/100.0);
方法2
减0.005=1.2306
%.2f保留两位的四舍五入输出
printf("%.2f\n",t-0.005);
oj-82伐木
二分答案
随着锯高度的提高，切割木头减少
11111100000
int bs(){
int l=0,r=tr;
while(l!=r){
int mid=((long long)l+r+1)/2;
long long s=func(mid);
if(s>=m){
l=mid;
}else{
r=mid-1;
}
}
return r;
}
int l=0,r=tr;
while(l!=r){
int mid=((long long)l+r+1)/2;
long long s=func(mid);
if(s>=m){
l=mid;
}else{
r=mid-1;
}
}
return r;
}
int类型越界，使用longlong类型
oj-391数列分段
最小的最大和
二分答案
每段和作为索引
段数作为查找值
随着每段和增加，段数减少
000001111找第一个1
long long bs(){
while(l!=r){
long long mid =(l+r)/2;
long long s=func(mid);
if(s<=m){
r=mid;
}else{
l=mid+1;
}
}
return l;
}
while(l!=r){
long long mid =(l+r)/2;
long long s=func(mid);
if(s<=m){
r=mid;
}else{
l=mid+1;
}
}
return l;
}
oj-394跳石头
最短跳跃距离的最大值
二分答案
最短跳跃距离作为索引
移掉的石头数作为查找值
随着最短距离增加，移走的石头数量增加
11111000找最后一个1
int bs(){
while(l!=r){
int mid=(l+r+1)/2;
int s=func(mid);
if(s<=m){
l=mid;
}else{
r=mid-1;
}
}
return l;
}
while(l!=r){
int mid=(l+r+1)/2;
int s=func(mid);
if(s<=m){
l=mid;
}else{
r=mid-1;
}
}
return l;
}
距离最近为x需要移走石头的数量
int func(int x){
int t=0,last=0;
for(int i=1;i<=n+1;i++){
if(num[i]-last<x){
t++;
}else{
last=num[i];
}
}
return t;
}
int t=0,last=0;
for(int i=1;i<=n+1;i++){
if(num[i]-last<x){
t++;
}else{
last=num[i];
}
}
return t;
}
oj-392丢瓶盖
最近距离最大
排序
二分答案
oj
模拟--给思路写代码
oj-477元音字母
字符串输入
char s[105];
cin>>s;
cin>>s;
以字符串末尾\0作为循环条件
for(int i=0;s[i];i++){
oj-479乒乓球
abs绝对值，需要引入头文件<cmath>
计分和局数结束分开处理
oj-480保龄球
oj-481冰壶比赛
oj-484.柱状统计图
声明b[128]直接用ascii码存储
求最高的行
找到每行的最后一个位置
循环打印，有打印*，没有打印空格
oj-485.均分纸牌
贪心解
oj-503.独木舟
从轻到重排序，从重的开始向前匹配，第一个小于等于载重的计数
计数过的数组位置零
oj-504.删数
从前向后遍历，大数在前小数在后的情况，删除前面大数
string头文件
s.replace(起始位置，替换长度，替换成什么)
567199,删除7---s.replace(2,1,"")
s.size()包含最后一个'\0'，注意循环不要越界
最后输出考虑前置零，用flag处理
oj-505.最大整数
数字按照某种方式排序
连接后的字典序排序
bool cmp(const string &a,const string &b){
return a+b>b+a;
}
return a+b>b+a;
}
排序后依次输出数字
oj-506.打热水
从小到大排序，使总等待时间最短
等待时间总和等于每位同学等待时间的和
oj-508.两人过河
先sort排序，从小到大
如果1个人，时间是num[0]
如果2个人，时间是num[1]
如果是3个人，时间是num[1]+num[0]+num[2]
如果是多于4个人，两种方案选择时间短的
让最快的来回送手电
让最快的两个过去，最快的回来，最慢的两个过去，次快的回来，两人过去
oj-509.智力大冲浪
钱从躲到少排序
优先完成钱多的任务
安排在靠后的时间完成
枚举
oj-513.楼层编号
遍历楼层，不包含t的cnt++
oj-514.火柴棒等式
两层枚举，上限1111
oj-515.比例简化
条件1 A' B'小于L
条件2：A' B'互质
因为从小到大遍历，所以互质的应该先遍历，不互质的不更新答案
条件3： A'/B' > A/B
条件4：A'/B' -A/B越小越好
oj-516.奶牛碑文
CCOOWW 算出现了 8 次 COW
前缀和：快速求解区间和
对于每个O，前面的C的数量和后面W的数量乘积，就是与这个O组成COW的数量
字符串从1开始输入：cin>>n>>&str[1];
正向求C的前缀和数组，反向求W的前缀和数组
oj-517.三角形个数
for枚举最短边长度1~n/3
枚举次短边，最短边i~（n-i）/2
三角形条件 i+j>n-i-j
oj-518.金币
第一天1个硬币
第2、3天两个硬币
第4、5、6天三个硬币
两层循环
外层while（1）
内层根据当前金币数循环
oj-519.优雅数
10的16次，1s会超时
构造优雅数的思路
第一层for循环特殊数是什么0~9 i
第二层for循环特殊数字是什么0~9；J 一般和特殊相同时continue
第三层for循环，优雅数的长度3~17 K
第四层for循环，特殊数的位置1~长度k L
特殊情况考虑前置0
一般数字前置零
特殊数字前置零
第五层for循环，判断是否在L和R之间
0 条评论
下一页
