Siyao's Blog


  • 首页

  • 关于

  • 标签

  • 分类

  • 归档

  • 搜索

c++STL中vector的一些操作

发表于 2017-11-04 | 分类于 c++
字数统计: 144 | 阅读时长 ≈ 1
记录c++STL中vector的一些操作 指定长度vector声明vector<int> vec(n);//长度为nvector<int> vec(n,t);//长度为n,值为t 指定长度二维vector声明声明一个m*n维的矩阵: vector<vector<int> > vec(m,vector<int>(n));vector<vector<int> > vec(n,vector<int>(n,0));//所有元素都是0 vector排序#include<algorithm>sort ...
阅读全文 »

回溯法、【leetcode】51.52 N-Queens

发表于 2017-11-04 | 分类于 算法 , leetcode
字数统计: 9,070 | 阅读时长 ≈ 45
什么是回溯回溯是一种穷举,但与brute force有一些区别,回溯带了两点脑子的,并不多,brute force一点也没带。如果用爬山来比喻:第一点脑子是回溯知道回头;相反如果是brute force,发现走不通立刻跳下山摔死,换第二条命从头换一条路走。第二点脑子是回溯知道剪枝;如果有一条岔路走不通,那这条路我们不走,就可以少走很多不必要走的路。 识别回溯问题判断回溯很简单,拿到一个问题,你感觉如果不穷举一下就没法知道答案,那就可以开始回溯了。一般回溯的问题有三种: Find a path to success 有没有解 Find all paths to success 求所有解 求所有 ...
阅读全文 »

c++STL中堆的使用

发表于 2017-11-04 | 分类于 c++
字数统计: 408 | 阅读时长 ≈ 2
方法一:priority_queue这种方法需要#include<queue> 最基本的使用方法,对于一串数字建堆: riority_queue<int> heap; 这种情况下默认为最大堆,也就是堆顶元素值最大。 如果需要建立最小堆,可以采用如下方式: priority_queue<int, vector<int>, greater<int> >qi2;//最小堆priority_queue<int, vector<int>, less<int> >qi2;//最大堆 然而在多数情况下,我们还需要 ...
阅读全文 »

【九章算法强化班】第k大

发表于 2017-11-04 | 分类于 算法 , leetcode
字数统计: 1,529 | 阅读时长 ≈ 7

求数组/矩阵的第k大元素

涉及leetcode题目

  1. 278. Kth Smallest Number In Matrix
  2. 373. Kth Smallest Sum In Two Sorted Arrays
  3. Kth Largest in N Arrays

278. Kth Smallest Number In Matrix

题目

Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.

给定一个的矩阵,满足行递增和列递增,要求返回第k大的元素。

example

matrix = [
[ 1, 5, 9],
[10, 11, 13],
[12, 13, 15]
],
k = 8,
return 13.
阅读全文 »

DSP国内硕士论文总结

发表于 2017-11-02 | 分类于 DSP
字数统计: 1,087 | 阅读时长 ≈ 4
准备开题,先看一下国内的相关硕士学位论文,知网上down的。 2017 大数据平台下的互联网广告点击率预估模型 基于腾讯社交广告数据集,hive+hadoop环境下实现GBDT+FM分布式点击率预估,用到贝叶斯平滑等,竞赛在分布式环境下的扩展。 ​ 2016 针对在线广告实时竞价系统的相关算法研究、电子科大、郭威 将竞价策略总结为预算控制和估价算法两个步骤,提出一种预算步进(buget pacing)算法和一个出价模型 数据集:iPinyou 2.2介绍计算广告核心问题和结算方式 核心问题:广告主、用户、媒体三方博弈,涉及信息检索、机器学习、最优化三个领域。 结算方式以及适用场景:CP ...
阅读全文 »

Hive中静态分区和动态分区

发表于 2017-11-02 | 分类于 hive
字数统计: 602 | 阅读时长 ≈ 3
差别两者主要的差别在于:加载数据的时候,静态分区需要手动设定不同的分区,按分区分别导入数据,;而动态分区不需要指定分区key的值,会根据key对应列的值自动分区写入,如果该列值对应的分区目录还没有创建, 会自动创建并写入数据。 静态分区创建分区表create table zhangsiyao.dt_0802_0815 (itime string,uid string,gid string,app_ver string,unet int ,device_type string,device_os string,client_type string,crtv_id int,country stri ...
阅读全文 »

利用Hive中percentile_approx计算等频划分分位点

发表于 2017-11-02 | 分类于 hive
字数统计: 526 | 阅读时长 ≈ 3
等频划分等频划分:按照数据的分布情况,每个区间的数据数量一样,平均划分成k个区间 等比划分:按照数据的全部取值情况,平均划分成k个区间 Hive 中计算分位数的函数:percentile_approxhive 中的percentile_approx函数可以确定等频划分的分位点percentile_approx(col,array(0.2,0.4,0.6,0.8))[0.0,4001.0,4061.0] 其中col为要划分的列,array中的数字代表划分的位置,比如(0.2,0.4,0.6,0.8)就是钱20%数量的样本被分到一个区间,然后20%-40%的样本被分到一个区间…. 返回值是一个ar ...
阅读全文 »

TPC_DS工具生成数据导入Hive

发表于 2017-11-02
字数统计: 2,293 | 阅读时长 ≈ 14
生成步骤 1.在官网上(http://www.tpc.org/tpcds/ )去下载最新的:TPC-DS. 2.解压: 下载的 zip 文件放在 Linux 上解压,并进入他的 tools 目录. 3.编译:make (忽略编译警告,只保证生成过程成功完成). 这里需要Linux安装上了 gcc , gcc c++, expect 等. 4.生成数据:在tools目录下执行:./dsdgen -scale 100 -force (-force:会覆盖原来生成的data,否则不覆盖);生成的25个.dat 的数据文件. 默认只能生成 100GB, 300GB, 1TB, 3TB, 10TB, ...
阅读全文 »

【算法导论】动态规划(二)矩阵链乘法

发表于 2017-11-01 | 分类于 算法导论
字数统计: 261 | 阅读时长 ≈ 1

矩阵链乘法问题

矩阵乘法

两个矩阵A和B相乘,维度分别为$ p×q$和$ q×r$,则$A*B$的时间复杂度为$pqr$

MATRIX_MULTIPLY(A,B){
for (int i = 0;i <A.rows;i++){
for(int j = 0;j < B.cols;j++){
for(int k = 0;k < A.cols;k++){
C[i,j] = A[i,k]*B[k,j];
}}}}

矩阵链乘法

​ 首先,给定一个矩阵链 ,三个矩阵的规模分别为:10×100 , 100×5 ,5×50 ,计算他们的乘积有两种方式:

$((A_1A_2)A_3)$
$(A_1(A_2A_3))$

可以看出,对一串矩阵做乘法操作,乘法的顺序影响到算法的时间复杂度。由此,引出矩阵链乘法问题:

给定n个矩阵的链,矩阵 的规模为,确定代价最低的计算顺序,使得计算乘积$A_1A_2A_n$所需标量乘法次数最小。

阅读全文 »

【算法导论】动态规划(一)钢条切割

发表于 2017-10-31 | 分类于 算法导论
字数统计: 1,389 | 阅读时长 ≈ 6

1. 动态规划(Dynamic programming)

这里programming指的是表格,而非编程。动态规划通常用来求解最优化问题

与分治法对比:

  1. 相同点:都是通过子问题组合求解原问题
  2. 不同点:分治法将问题划分为不相交的子问题,求解再合并,动态规划应用于子问题重叠的情况,即不同的子问题具有公共的子子问题,此时如果用分治法就会出现重复计算求解。为了避免重复动态规划对子问题只求解一次,将其保存在表格中,从而无需每求解一个子子问题时重复计算。

2. 求解步骤

  1. 刻画最优解的结构特征
  2. 递归定义最优解的值
  3. 计算最优解的值,通常采用自底向上的方法
  4. 利用计算出的信息构造最优解

其中不是所有的题目都会要求4,仅仅要求3,要求4的时候,我们需要在得到3的同事维护一些额外的信息来求出4。

看到这四个步骤的时候,还是挺懵逼的,继续往下看=.=

阅读全文 »
1…678…12
Siyao

Siyao

siyao小朋友画圈圈的地方

120 日志
25 分类
32 标签
© 2017 — 2018 Siyao
由 Hexo 强力驱动
|
主题 — NexT.Pisces
| Site words total count: 222.8k
访问人次 次 总访问量 次