4 _Jason_ZHANG

尚未进行身份认证

Undergraduate & Computer Science & Beihang Univ. github.com/jasonlovescoding

等级
TA的排名 4w+

主成分个数 - 快排中partition的深入理解

算法课课后习题对深化理解某一算法确实很有帮助.. 这一次课程学习了快速排序,每一次排序都涉及一个partition操作,也就是把数组分为比pivot大的部分,和比pivot小的部分。这个题目是在线性时间内找到某一长N的数组中出现次数超过某一比例,如N/3的全部元素。https://leetcode.com/problems/majority-element-ii/Given

2016-09-22 00:21:59

求两个排好序的数组的中位数 - 二分法

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

逆序数个数 (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

8-puzzle 可解性的证明 & 最优解性的证明

问题来自Coursera上Princeton所开AlgorithmsPartI第四周的作业:http://coursera.cs.princeton.edu/algs4/assignments/8puzzle.html这一次作业要求用PriorityQueue实现一个经典的A*搜索算法,来找到一个8-puzzle问题的解(或者在有限时间内发现它的无解性)。作业要求里对算法的描述很细致

2016-09-21 23:38:05

北京地铁乘坐路线查询

【问题描述】编写一个程序实现北京地铁最短乘坐(站)线路查询,输入为起始站名和目的站名,输出为从起始站到目的站的最短乘坐站换乘线路。注:1. 要求采用Dijkstra算法实现;2)本题在实际测试时对数据文件进行了调整,使得输入的两站间只有一条最短路径。【输入形式】文件bgstations.txt为数据文件(可从课程网站中课程信息处下载),包含了北京地铁的线路及车站信息。其格式如下

2016-09-20 13:30:24

独立路径计算

【问题描述】老张和老王酷爱爬山,每周必爬一次香山。有次两人为从东门到香炉峰共有多少条路径发生争执,于是约定一段时间内谁走过对方没有走过的路线多谁胜。给定一线路图(无向连通图,两顶点之间可能有多条边),编程计算从起始点至终点共有多少条独立路径,并输出相关路径信息。注:独立路径指的是从起点至终点的一条路径中至少有一条边是与别的路径中所不同的,同时路径中不存在环路。 【输入形

2016-09-20 13:28:37

C程序括号匹配检查

【问题描述】编写一程序检查C源程序文件中{}、()等括号是否匹配,并输出第一个检测到的不匹配的括号及所对应括号所在的行号(程序中只有一个括号不匹配)。注意:1.     除了括号可能不匹配外,输入的C源程序无其它语法错误;2.     字符常量、字符串常量及注释中括号不应被处理,注释包括单行注释//和多行/* */注释3. 字符和字符串常量中不包含特殊的转义字符(\',\")

2016-09-20 13:25:09

银行排队模拟

【问题描述】一个系统模仿另一个系统行为的技术称为模拟,如飞行模拟器。模拟可以用来进行方案论证、人员培训和改进服务。计算机技术常用于模拟系统中。生产者-消费者(Server-Custom)是常见的应用模式,见于银行、食堂、打印机、医院、超等提供服务和使用服务的应用中。这类应用的主要问题是消费者如果等待(排队)时间过长,会引发用户抱怨,影响服务质量;如果提供服务者(服务窗口)过多,将提高运管商

2016-09-20 13:24:11

全排列数的生成

这学期好忙,整个人都变懒了。。coursera上的课程作业只来得及更新到github上,希望自己以后看着注释还能记得怎么做。。。得空把上学期的一些作业放这里。【问题描述】输入整数N( 1 【输入形式】输入整数N。【输出形式】输出有N!行,每行都是从1~N所有整数的一个全排列,各整数之间以空格分隔。各行上的全排列不重复。输出各行遵循“小数优先”原则, 在各全排列中,较小的数尽量靠

2016-09-20 13:21:42

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

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

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

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

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

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

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

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

Huffman编码文件压缩 - Huffman树的建立与编码

【问题描述】编写一程序采用Huffman编码对一个正文文件进行压缩。具体压缩方法如下:1.    对正文文件中字符(换行字符'\'除外,不统计)按出现次数(即频率)进行统计2.    依据字符频率生成相应的Huffman树(未出现的字符不生成)3.    依据Huffman树生成相应字符的Huffman编码4.    依据字符Huffman编码压缩文件(即按照Huffman编码

2016-05-20 11:09:26

一个带有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

一元多项式相乘 - 链表的简单应用

【问题描述】编写一个程序实现两个一元多项式相乘。【输入形式】首先输入第一个多项式中系数不为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

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!