- 博客(48)
- 资源 (8)
- 收藏
- 关注
RSS订阅原创 主成分个数 - 快排中partition的深入理解
算法课课后习题对深化理解某一算法确实很有帮助.. 这一次课程学习了快速排序，每一次排序都涉及一个partition操作，也就是把数组分为比pivot大的部分，和比pivot小的部分。这个题目是在线性时间内找到某一长N的数组中出现次数超过某一比例，如N/3的全部元素。https://leetcode.com/problems/majority-element-ii/Given
2016-09-22 00:21:59
1727
原创 求两个排好序的数组的中位数 - 二分法
There are two sorted arrays A and B of size m and nrespectively. Find the median of the two sorted arrays.Have you met this question in a real interview? YesExampleGiven A=[1,2
2016-09-22 00:14:06
2111
原创 逆序数个数 (Inversion Counting) - Merge and Sort
普林斯顿的算法课质量很赞，这次作业中涉及到一个"逆序数"的知识，正好在之前学习mergesort时有一道课后提供的面试题与之相关，于是试着实现了。原题链接：http://www.practice.geeksforgeeks.org/problem-page.php?pid=558Given an array, find inversion count of array.
2016-09-22 00:07:21
3123
原创 8-puzzle 可解性的证明 & 最优解性的证明
问题来自Coursera上Princeton所开Algorithms Part I第四周的作业：http://coursera.cs.princeton.edu/algs4/assignments/8puzzle.html这一次作业要求用Priority Queue实现一个经典的A*搜索算法，来找到一个8-puzzle问题的解（或者在有限时间内发现它的无解性）。作业要求里对算法的描述很细致
2016-09-21 23:38:05
9714
原创 北京地铁乘坐路线查询
【问题描述】编写一个程序实现北京地铁最短乘坐（站）线路查询，输入为起始站名和目的站名，输出为从起始站到目的站的最短乘坐站换乘线路。注：1. 要求采用Dijkstra算法实现；2）本题在实际测试时对数据文件进行了调整，使得输入的两站间只有一条最短路径。【输入形式】文件bgstations.txt为数据文件（可从课程网站中课程信息处下载），包含了北京地铁的线路及车站信息。其格式如下
2016-09-20 13:30:24
9265
2
原创 独立路径计算
【问题描述】老张和老王酷爱爬山，每周必爬一次香山。有次两人为从东门到香炉峰共有多少条路径发生争执，于是约定一段时间内谁走过对方没有走过的路线多谁胜。给定一线路图（无向连通图，两顶点之间可能有多条边），编程计算从起始点至终点共有多少条独立路径，并输出相关路径信息。注：独立路径指的是从起点至终点的一条路径中至少有一条边是与别的路径中所不同的，同时路径中不存在环路。 【输入形
2016-09-20 13:28:37
13932
11
原创 C程序括号匹配检查
【问题描述】编写一程序检查C源程序文件中{}、()等括号是否匹配,并输出第一个检测到的不匹配的括号及所对应括号所在的行号（程序中只有一个括号不匹配）。注意：1. 除了括号可能不匹配外，输入的C源程序无其它语法错误；2. 字符常量、字符串常量及注释中括号不应被处理，注释包括单行注释//和多行/* */注释3. 字符和字符串常量中不包含特殊的转义字符（\',\"）
2016-09-20 13:25:09
8042
原创 银行排队模拟
【问题描述】一个系统模仿另一个系统行为的技术称为模拟，如飞行模拟器。模拟可以用来进行方案论证、人员培训和改进服务。计算机技术常用于模拟系统中。生产者-消费者（Server-Custom）是常见的应用模式，见于银行、食堂、打印机、医院、超等提供服务和使用服务的应用中。这类应用的主要问题是消费者如果等待（排队）时间过长，会引发用户抱怨，影响服务质量；如果提供服务者（服务窗口）过多，将提高运管商
2016-09-20 13:24:11
5647
2
原创 全排列数的生成
这学期好忙，整个人都变懒了。。coursera上的课程作业只来得及更新到github上，希望自己以后看着注释还能记得怎么做。。。得空把上学期的一些作业放这里。【问题描述】输入整数N( 1 【输入形式】输入整数N。【输出形式】输出有N!行，每行都是从1~N所有整数的一个全排列，各整数之间以空格分隔。各行上的全排列不重复。输出各行遵循“小数优先”原则, 在各全排列中，较小的数尽量靠
2016-09-20 13:21:42
5391
原创 CSAPP3e - x86-64 assembly code analysis - Attack Lab: Level II
这一部分要求我使用ROP的方法来攻击rtarget这个程序。rtarget增加了一些现代的保护手段，例如随机产生rsp的地址，这使得我无法预测每次run的时候栈帧的位置，从而不能像PART I level2中那样预测到rsp的位置注入exploit code。退一步说，就算我成功注入了，还有金丝雀保护机制（canary）来确定某些位置的值是否发生变化，以及直接规定某些存储区域是不可执行（inexe
2016-06-11 19:47:19
2283
2
原创 CSAPP3e - x86-64 assembly code analysis - Attack Lab: Level I
这个lab的目的在于进一步分析汇编码。由于冯氏体系下数据和程序代码都以二进制存储，而且某些不安全的代码可能会在扫描缓冲区时跨越边界，改变一些不应当改变的值，这就给了著名的buffer overflow attack机会。先期知识：最好搞清楚函数调用的机制，弄明白rsp的值和其指向的值到底是什么PART 1要求我使用经典的buffer overflow attack插入我自己的exploit c
2016-06-10 21:30:47
4610
原创 CSAPP3e - x86-64 assembly code analysis - Bomb Lab: phase 6
phase_6的代码很长，不过很有结构，按功能划分首先来看第一段：00000000004010f4 : 4010f4: 41 56 push %r14 4010f6: 41 55 push %r13 4010f8: 41 54 push %r12 4010fa: 55
2016-06-06 23:12:35
3314
原创 CSAPP3e - x86-64 assembly code analysis - Bomb Lab: phase 5
首先来看phase_5做了什么:0000000000401062 : 401062: 53 push %rbx 401063: 48 83 ec 20 sub $0x20,%rsp 401067: 48 89 fb mov %rdi,%rbx
2016-06-06 23:10:56
2260
原创 CSAPP3e - x86-64 assembly code analysis - Bomb Lab: phase 4
先看看phase_4做了什么:000000000040100c : 40100c: 48 83 ec 18 sub $0x18,%rsp 401010: 48 8d 4c 24 0c lea 0xc(%rsp),%rcx 401015: 48 8d 54 24 08 lea 0x8
2016-06-04 23:07:28
2986
原创 CSAPP3e - x86-64 assembly code analysis - Bomb Lab: phase 3
首先来看phase_3的代码0000000000400f43 : 400f43: 48 83 ec 18 sub $0x18,%rsp 400f47: 48 8d 4c 24 0c lea 0xc(%rsp),%rcx 400f4c: 48 8d 54 24 08 lea 0x8(%rsp),%rdx 400f5
2016-05-31 14:25:57
2483
原创 CSAPP3e - x86-64 assembly code analysis - Bomb Lab: phase 2
首先来看phase_2的代码：0000000000400efc : 400efc: 55 push %rbp 400efd: 53 push %rbx 400efe: 48 83 ec 28 sub $0x28,%rsp 400f02: 48 89 e6
2016-05-30 21:56:19
1656
原创 CSAPP3e - x86-64 assembly code analysis - Bomb Lab: phase 1
第二个lab，bomb lab，一个"legendary lab"（原话就是这样），通过看C的源码可以看出共有6个phase，每个phase其实就是一个拆弹的过程:每一个phase里要求输入一个字符串，如果正确，这个phase的bomb就会被解除，并进入下一个phase。很显然，phase的难度是逐步增加的，到后面单独一个phase的分析都快赶上lab1的工作量了... 分区写吧，一个一个
2016-05-27 18:25:10
3241
原创 Huffman编码文件压缩 - Huffman树的建立与编码
【问题描述】编写一程序采用Huffman编码对一个正文文件进行压缩。具体压缩方法如下：1. 对正文文件中字符(换行字符'\'除外，不统计)按出现次数（即频率）进行统计2. 依据字符频率生成相应的Huffman树（未出现的字符不生成）3. 依据Huffman树生成相应字符的Huffman编码4. 依据字符Huffman编码压缩文件（即按照Huffman编码
2016-05-20 11:09:26
5349
1
原创 一个带有Kruskal、Prim、Dijkstra算法的图类型 - C++ for C Programmers
C++ for C Programmers 这门课讲了图论中三个重要的算法： Kruskal's Minimum Spanning Tree, Prim's Minimum Spanning Tree, Dijkstra's Shortest Path.这里把三个算法实现后作为成员函数写在一个图的类里，图是用邻接矩阵存储的，支持随机生成。#include #include #inc
2016-05-20 11:03:26
737
原创 一元多项式相乘 - 链表的简单应用
【问题描述】编写一个程序实现两个一元多项式相乘。【输入形式】首先输入第一个多项式中系数不为0的项的系数和指数，以一个空格分隔。且该多项式中各项的系数均为0或正整数，系数和最高幂次不会超过int类型的表示范围。对于多项式 anxn +a n-1 x n-1 + … + a1x1 + a0x0 的输入方法如下： an n a n-1 n-1 … a1 1 a0
2016-04-26 17:08:47
7813
1
原创 猴子选大王 - 约瑟夫问题
【问题描述】要从n只猴子中选出一位大王。它们决定使用下面的方法：n只猴子围成一圈，从1到n顺序编号。从第q只猴子开始，从1到m报数，凡报到m的猴子退出竞选，下一次又从退出的那只猴子的下一只开始从1到m报数，直至剩下的最后一只为大王。请问最后哪只猴子被选为大王。【输入形式】控制台输入三个整数n，m，q。【输出形式】输出最后选为大王的猴子编号。【样例输入】7 4 3【样例输
2016-04-26 17:07:31
6955
3
原创 计算器表达式计算 后缀表达式+树实现 - 逆波兰表示法+调度场算法
这题基本是靠翻维基百科把逆波兰表示法和Dijkstra的调度场算法生搬下来的.. 还要学习一个啊【问题描述】从标准输入中读入一个整数算术运算表达式，如5 - 1 * 2 * 3 + 12 / 2 / 2 = 。计算表达式结果，并输出。要求：1、表达式运算符只有+、-、*、/，表达式末尾的’=’字符表示表达式输入结束，表达式中可能会出现空格；2、表达式中不含圆括号，
2016-04-26 14:59:42
4318
原创 五子棋危险判断 - 图与连线
这题其实不难，但是纪念一下头一次"信仰提交成功"2333【问题描述】已知两人分别执白棋和黑棋在一个围棋棋盘上下五子棋，若同一颜色的棋子在同一条横行、纵行或斜线上连成5个棋子，则执该颜色棋子的人获胜。编写程序读入某一时刻下棋的状态，并判断是否有人即将获胜，即：同一颜色的棋子在同一条横行、纵列或斜线上连成4个棋子，且该4个棋子的两端至少有一端为空位置。输入的棋盘大小是19×19，用
2016-04-26 14:54:14
5592
3
原创 大数乘法 - 大数作为字符串的C语言操作
【问题描述】编写程序实现两个超长整数（大于等于0，每个最长80位数字）的乘法运算。【输入形式】从键盘分行读入两个超长整数，要考虑输入高位可能为0的情况（如00083），每行的最后都有回车换行。【输出形式】输出只有一行，是两个长整数的乘法运算结果，从高到低依次输出各位数字，各位数字紧密输出。除非结果为0，否则最高位不能为0。【输入样例】1340
2016-04-26 14:51:18
4525
原创 POJ 3069 Saruman's Army - 贪心
Saruman's ArmyTime Limit: 1000MS Memory Limit: 65536KTotal Submissions: 6578 Accepted: 3355DescriptionSaruman the White must lead his army along a s
2016-03-15 14:43:23
520
原创 POJ 3617 Best Cow Line - 贪心
Best Cow LineTime Limit: 1000MS Memory Limit: 65536KTotal Submissions: 16160 Accepted: 4559DescriptionFJ is about to take his N (1 ≤ N ≤ 2,000) cows
2016-03-12 20:53:00
413
原创 三字符字典内的序号与字符串互查 - 进制转换
SIGMA={a,b,c} SIGMA* is based on SIGMA with these rules:1. SIGMA ⊆ SIGMA*2. if s1∈SIGMA*, s2∈ SIGMA*, then s1s2∈SIGMA*3. Any element of SIGMA* can be formed within finite application of r
2016-03-11 11:43:25
500
原创 noip 2000年 乘积最大 - DP
这是学习DP时接触的一道题，当时忘记发了，现在补发一下【题目描述】今年是国际数学联盟确定的“2000——世界数学年”，又恰逢我国著名数学家华罗庚先 生诞辰90周年。在华罗庚先生的家乡江苏金坛，组织了一场别开生面的数学智力竞赛的活动，你的一个好朋友XZ也有幸得以参加。活动中，主持人给所有参加活动的选手出了这样一道题目: 设有一个长度N的数字串，要求选手使用K个乘号将它分成K+1个
2016-03-01 23:21:14
671
原创 Singly Linked List & Destructor - C++ for C Programmers 3.4
/* Update on Oct 7th Finally figured out the reason for the malfunction of str destructor. It is really about pass-by-reference, which means when I call "a.inputName_by_Seq(n2, 10);"(just a
2016-02-29 22:27:01
563
原创 （广度优先搜索第一课）迷宫的最短路径 - BFS
给定一个大小为N*M的迷宫，由通道('.')和墙壁('#')组成，其中通道S表示起点，通道G表示终点，每一步移动可以达到上下左右中不是墙壁的位置。试求出起点到终点的最小步数。（本题假定迷宫是有解的）(N,M样例输入：10 10#S######.#......#..#.
2016-02-29 22:10:01
12776
4
原创 POJ 2386 Lake Counting - DFS
Lake CountingTime Limit: 1000MS Memory Limit: 65536KTotal Submissions: 26533 Accepted: 13329DescriptionDue to recent rains, water has pooled in vari
2016-02-29 20:35:29
347
原创 POJ 1328 Radar Installation - 贪心算法
Assume the coasting is an infinite straight line. Land is in one side of coasting, sea in the other. Each small island is a point locating in the sea side. And any radar installation, locating on the coasting, can only cover d distance, so an island in the
2016-01-14 19:35:16
437
原创 24点 - DFS
Time Limit:1000ms Memory Limit: 65535KB在Jason生活的星球上，算术学期末总是考同样的题目：抽四张扑克牌，在1秒内通过四则运算让其结果为24。但是Jason的算术太拙了，总是没办法在1秒内得到正确答案。期末考试就快要到了，但正直的Jason不想靠命运力神抽4张6来通过考试。你能为Jason设计一个24点的算法，好让他不挂
2015-12-29 17:18:36
826
原创 BNUOJ49098 神奇的身高 - DP （LIS）
Time Limit: 2000ms Memory Limit: 65536KB有一群小伙伴站成一行，每个人的身高都是非负整数，但是他们站在一起并不和谐。需要将他们的身高变成严格单调递增的正整数序列才是和谐的。现在你有一种神奇的魔法，可以任意改变一个人的身高。现在问题来了，你最少需要改变多少人的身高才能使整个队伍和谐。（改变后的身高必须为整数）Input 有多组测试数据
2015-12-29 11:04:10
2670
原创 OJ3RD 1157 合并相邻数字 - DP
题目描述给你 n 个数字每次可以合并相邻的两个数字，即为这两个数字的和代替他们原来的位置，这种操作耗费的代价为合并的两个数字之和求最终将一串数组合并成为一个数字消耗的最小代价。输入多组测试数据。每组输入数据有两行第一行为一个整数 n（1≤n≤100），表示 n 个数第二行为空格隔开的n个整数a1…an，表示数字大小(1输出对于每组数据，输出一行，
2015-12-26 19:20:32
2086
原创 Tyvj P1005 采药 - DP 0/1背包问题
辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。” 如果你是辰辰，你能完成这个任务吗？
2015-12-26 18:47:04
782
原创 Dijkstra's Shortest Path - C++ for C Programmers 2.5
课程来自：https://class.coursera.org/cplusplus4c-002/lecture这节课讲述的是Dijkstra最短路径算法的具体实现。Dijkstra最短路径算法是贪心算法的一个实例，给定一个无向图，出发点s以及目的点t，要求s到t的最短路径。核心步骤是：每次都选取离s最近的且没有被关闭的点将其关闭。数组约定: dist[i]表示i号点到s点的最短距
2015-12-26 10:45:42
484
原创 POJ 2828 Buy Tickets - Segment Tree
Railway tickets were difficult to buy around the Lunar New Year in China, so we must get up early and join a long queue…The Lunar New Year was approaching, but unluckily the Little Cat still had schedules going here and there. Now, he had to travel by tr
2015-12-25 23:25:44
425
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人