当前位置: 代码迷 >> 综合
 解决方案列表
  • [综合] 如何实现O(n)的2-sum

    2-sum问题实现找数组中的二元数组(a,b)(a+b=0) 方法一: 循环O(n2) 方法二:二分查找: for(inti=0;i<n;i++){ Binary_Search(-a[i]); } 结果O(nlogn) 方法三:牺牲空间换取时间基数排序算法 比如10^8内的整数 a[10^8]...

    67
    热度
  • [综合] Find local minima in an array

    YouaregivenanarrayArr[1..n]withthespecialpropertythatArr[1]≥Arr[2]andArr[n?1]≤Arr[n].WesaythatanelementArr[x]isalocalminimumifitislessthanorequaltobot...

    18
    热度
  • [综合] 数据范围和时间

    一个int4个字节32个位 字节的大小B 1024B=1KB 1024KB=1MB 65536KB=64MB 一秒1E次一般运算

    87
    热度
  • [综合] 0-1背包的优化

    以上方法的时间和空间复杂度均为O(N*V),其中时间复杂度基本已经不能再优化了,但空间复杂度却可以优化到O(V)。 先考虑上面讲的基本思路如何实现,肯定是有一个主循环i=1..N,每次算出来二维数组f[i][0..V]的所有值。那么,如果只用一个数组f[0..V],能不能保证第i次循环结束后f[v...

    46
    热度
  • [综合] scanf的使用注意

    格式字符串 格式字符串的一般形式为: %[*][输入数据宽度][长度]类型 其中有方括号[]的项为任选项。各项的意义如下。 %x和%X都能读16进制,并且他们不区分A和a 2)“*”符用以表示该输入项,读入后不赋予相应的变量,即跳过该输入值。如: scanf("%d%*d%d",&...

    32
    热度
  • [综合] c++ string reverse 用法

    reverse() std::voidreverse(s.begin(),s.end()); 上面是原地反转的方法,如果需要反转到别的string里面,一样简单: s1.assign(s.rbegin(),s.rend()); 效率也相当理想。

    58
    热度
  • [综合] memset calloc malloc

    calloc虽然把内存都初始化了,但是会降低效率,相当于Malloc完了在进行一个memset: 1.分配内存空间函数malloc调用形式:(类型说明符*)malloc(size)功能:在内存的动态存储区中分配一块长度为"size"字节的连续区域。函数的返回值为该区域的首地址。“类型说明符”表示把...

    35
    热度
  • [综合] hdoj 2544

    单源最短路径:从一个源头出发到所有点的最短路径 BFS只能求无权重图的单源最短路径 最优子结构:两个节点间的最短路径必然包含其他最短路径(最优子结构可以使用贪心和动态规划) 只要不包含一个权值为负的环路,负的最短路径就是有意义的。否则,再走一遍最短路径就能实现更小的权重. 最短路径不包含环。如果包...

    9
    热度
  • [综合] 弗洛伊德算法 路径还原

    用DP来解决,在只使用顶点0~k和i,j的情况下(i,j作为起点和重点,0~k个点作为中间点),记i到j的最短长度为dp[k][i][j],k=-1表示只是用i和j两个点,此时dp[0][i][j]=cost[i][j] 接下来,我们分i到j的最短路恰好经过k和不经过k两种,如果不经过k点 那么就是...

    3
    热度
  • [综合] 0-1背包问题:输出最小背包

    如何输出最小背包? 0-1背包 #include<iostream> usingnamespacestd; constintmaxn=1005; intdp[maxn][maxn]; intweight[maxn]; intvalue[maxn]; intn,v; intmax(int...

    7
    热度
  • [综合] 部分和问题-dfs穷举

    给定整数a1,a2,..am判断是否可以从中选出若干个数字,使得他们的和恰好为n 我们要判断每个数字选或者不选 #include<iostream> usingnamespacestd; constintmaxn=10005; inta[maxn]; intn; intsum; boo...

    19
    热度
  • [综合] LCS-DP

    longestcommonsequence最长公共子序列 不一定要连续的公共序列 比如ABCDEF ASSBWWC也有ABC作为最长公共子序列 longestcommonsubstring最长公共子串才是连续的 暴力求解方式: 公共子序列的解决方式: 设X=<x1,x2...xm>,...

    82
    热度
  • [综合] 回溯算法-8皇后

    回溯算法的本质是深度优先搜索,回溯又叫试探法(backtracking),深度优先遇到障碍再返回来。 回溯法要先定义一个解空间,用便于搜索的方式整理解空间,然后深度优先搜索。 八皇后问题: 解空间? 八个皇后在棋盘上面的排列位置可以用一个8元数组表示, X1,X2,X3,X4,X5,X6,X7,X8...

    83
    热度
  • [综合] 动态规划水题

    1.二维数组最小和M*N维的二维数组,每个位置有一个非负值,每次只能从右或者从下走,求从(1,1)走到(M,N)的最小值简单dp,开始的时候设置边界为INF枚举:C(m+n-2,m)(其中有m步向下走)dp[i][j]=min(dp[i-1][j],dp[i][j-1])+dis[i][j]; 2....

    90
    热度
  • [综合] 双端队列stl

    C++Deque(双向队列) 是一种优化了的、对序列两端元素进行添加和删除操作的基本序列容器。它允许较为快速地随机访问,但它不像vector把所有的对象保存在一块连续的内存块,而是采用多个连续的存储块,并且在一个映射结构中保存对这些块及其顺序的跟踪。向deque两端添加或删除元素的开销很小。它不需要...

    91
    热度
  • [综合] 尺取法 poj3061

    尺取法:就是两个指针表示区间[l,r]的开始与结束然后根据题目来将端点移动,是一种十分有效的做法。适合连续区间的问题 1poj3061 给定长度为n的数列整数a0,a1,a2,a3.....an-1以及整数S。求出和不小于S的连续子序列的长度的最小值。如果解不存在,则输出0。 方法1;暴力:O(n^...

    34
    热度
  • [综合] dp-挑战程序设计竞赛-状态的选择 多重部分和 LIS

    DP的核心是状态的定义,状态的巧妙定义。 多重部分和 题目:给定整数a1、a2、.......an,每种数各mi个,判断是否可以从中选出若干数,使它们的和恰好为K。 分析:这是一个完全背包恰好装满的问题,当然可以用O(NKmi) 但通过把状态dp[i][j]定义成第i个数字使得和为j剩下的个数 这样...

    61
    热度
  • [综合] 大一下一点小小的总结

    1.对于学校的课,想要拿高绩点,上课的ppt是很主要的。读透课本倒不是那么必要。 2.正如李笑来所说,很多时候犹豫要不要去做这件事情的成本比深入了解的时间花的还多。很多事情可以先先做一下再判断可不可做。

    12
    热度
  • [综合] pair (c++)

    pair的类型: pair实质上是一个结构体 pair是一种模版类型。每个pair可以存储两个值。这两种值无限制。也可以将自己写的struct的对象放进去。。 pair<string,int>p; pair<int,int>p; pair<double,int>p...

    82
    热度
  • [综合] 第一天集训补题目

    1.树形dp 题目描述:每个公司开party,但是开party的时候,和老板呆在一起会很不自在(每个人仅有一个老板,自己老板的老板不是老板),现在给出员工关系. Nowyourtaskistofindthemaximumnumberofemployeesthatmayattendthepartywi...

    28
    热度