首页
学习
活动
专区
工具
TVP
发布

kalifaの日々

专栏成员
53
文章
67962
阅读量
29
订阅数
POJ2431-最优队列(最小堆)解法
这道题有一个坑,就是给出的加油站到终点的距离不一定是降序排列好了的。 所以得到input之后要先对数据进行排序。我直接用了#include<algorithm>下的sort函数,对pair<int,int>类型的输入进行排序,非基本类型的数据排序需要重写sort函数的第三个参数。 源代码 #include<queue> #include<iostream> #include<string> #include<vector> #include<algorithm> using namespace std;
kalifa_lau
2018-04-28
7770
线段树 BIT 求冒泡排序的交换次数
线段树特别适合与区间相关的运算,比如MRQ(minimum range query)求一段区间内的最小值。 BIT可以看作是压缩了的线段树,由于(某类)线段树的右节点可以由父结点和左兄弟求出来,所以右结点就不用存了。 求冒泡排序的交换次数,直观的想可以直接在冒泡排序的过程中计算交换次数,时间复杂度是O(n^2)。交换次数其实是(位置在j的前面,数值还比aj大的数)j从0到n求和。算法的特点是反复对某一区间内的所有元素求和,可以用BIT来优化。 做法是,i从0到n遍历,在循环的某一趟中,dat[ai]表
kalifa_lau
2018-04-28
1.6K0
动态规划真的可以为所欲为的(Leetcode 62/63)
看起来不错的运行效率 62题: 动态规划递推公式: 站在当前方块上可选择的路径数量 = 我正下方那个方块可选择的路径数量 + 我右侧那个方块可选择的路径数量; 边界情况: 棋盘上最右边那列只能选择往下走,所以dp[i][n-1]=1; 棋盘最下面那一行只能选择往右面走,所以dp[m-1][j] = 1; 进一步优化:重复利用一行数组代替m*n的dp数组,节省空间。 class Solution { public: int uniquePaths(int m, int n) {
kalifa_lau
2018-04-28
6480
大数的十进制转换成二进制
要求输出最多有30位的十进制数的二进制表示。 10的30次方大概是2的100次方,最大的long long int最多也只能表示到2的64次方,所以用字符串来存这个数,然后通过遍历字符串的方式来模仿整数除法。 #include <cstdio> #include <iostream> #include <string.h> using namespace std; char sp[100]; int res[100]; int n,length; bool isAllZero(char* str)
kalifa_lau
2018-04-28
1.5K0
检测一个int n是否是k的整数次幂的通用方法
1.如果k是质数,那么先求出int范围内能被表示的最大的k的x次方——max,然后判断max%n==0。 例如判断一个数n是否是3的指数次幂: int max; void getMax() { int max = 1; while(true) { if(max*3/3==max) max *= 3; else return; } bool pow3(int n) { if(max==0) getMax(); return (n>0
kalifa_lau
2018-04-28
1.2K0
一个易于理解的C++全排列(permutation)实现
通常我们用这两条语句可以得到一个数组的全排列: sort(nums.begin(),nums.end()); //调用next_permutation求全排列的时候必须先给容器排序 do{ get_pirnt(nums) //这里是一个可以打印输出nums的函数 }while(next_permutation(nums.begin(),nums.end()); //调用该C++内置函数可以输出字典序大于当前nums的所有排列。 还可以自己写一个函数实现同样的功能,下面的函数使用递归,每次取出
kalifa_lau
2018-04-26
1.7K0
大数乘法
其实大数乘法就是在考虑大数加法的进位的同时,考虑字符串num1和字符串num2相乘时,每一位所在的位置,以及加法运算中多了一个乘法项。 可运行的cpp代码 class Solution { public: string multiply(string num1, string num2) { string res(num1.size()+num2.size(),'0'); for(int i=num1.size()-1;i>=0;i--)
kalifa_lau
2018-04-26
1K0
C++迪杰斯特拉最短路径算法实现
input 第一行表示这个图有4条边,下面五行代表这个图的5条边。 4 0 2 2 0 1 5 1 3 2 2 3 6 -1 0 0 输入样例 out 分别输出结点“0”到结点0,1,2,3的最短距离
kalifa_lau
2018-04-26
1.4K0
没有更多了
社区活动
【纪录片】中国数据库前世今生
穿越半个世纪,探寻中国数据库50年的发展历程
Python精品学习库
代码在线跑,知识轻松学
博客搬家 | 分享价值百万资源包
自行/邀约他人一键搬运博客,速成社区影响力并领取好礼
技术创作特训营·精选知识专栏
往期视频·千货材料·成员作品 最新动态
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档