Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1’s in their binary representation and return them as an array.

Example:
For num = 5 you should return [0,1,1,2,1,2].

Follow up:

  • It is very easy to come up with a solution with run time O(n*sizeof(integer)). But can you do it in linear time O(n) /possibly in a single pass?
  • Space complexity should be O(n).
  • Can you do it like a boss? Do it without using any builtin function like __builtin_popcount in c++ or in any other language.

Hint:

  1. You should make use of what you have produced already.
  2. Divide the numbers in ranges like [2-3], [4-7], [8-15] and so on. And try to generate new range from previous.
  3. Or does the odd/even status of the number help you in calculating the number of 1s?

一开始没看 Hint ,看到题目的要求下意识的想到了树状数组中 lowbit 的用法,但是感觉这样还是不能满足 O(N) 的时间要求……

思路大体是这样的,首先从 num 开始计算出 1 的个数,然后通过形似 num-=(num&-num) 的运算消去最后一个 1 ,完成对下一个 num 的计数,然后依次类推。之后从 num 递减,若出现了未记录的数,则继续如上的计算。

代码如下:

 

背景

2015 年 C 程序设计专题课程第三次 Project,基于 bhh 老师移植加改写的 watcom c + graphics.h 实现。

除了 dosbox 效率比较坑,也没有什么太多的问题吧(其实是已经记不清了

v20150614 版俄罗斯方块(其实只是修改日期……)实现了基本的功能 + 排行榜,但是具体的设置界面当时为了赶 DDL 就没有去写,时间都基本耗在 bgm 的实现上去了……(找了各种 dos 下 wav 的播放实现,翻遍了各种“远古”的论坛,最后却发现库函数里提供了相应的函数 T_T

v20150628 版是为了课上展示准备的版本,当时用了一上午?把界面改的舒服了一些,同时增加了方块在底部的投影以及方块的暂存功能。

打字游戏

俄罗斯方块v20150614

俄罗斯方块v20150628

报告及源码

一、问题说明

在Dosbox环境下,自行设计相关的算法与数据结构,实现图形化的俄罗斯方块与文本形式的打字游戏。

二、算法设计与说明

俄罗斯方块的算法主要涉及到对应图形的绘制以及对应储存矩阵(数组)的操作。我们采用了通过显示器频率中断控制扫描状态池矩阵的数据进行全屏输出与脏矩形绘制相结合的方法进行了图形的绘制,然而由于平台的限制,画面仍有一定可能出现抖动或卡滞的情况。在对方块的操作中,我们则每次获取按键后,扫描矩阵以获得当前活动的方块区域,在对其进行对应的移位或伪转置操作(实现旋转)。(By LLonely)

打字游戏的设计则是随机获取单词,并依次在随机位置输出,判断按键与屏幕上活动单词的匹配情况,再依次循环判断,若不匹配,则重置标记,再次重新开始匹配。如果有活动单词被匹配完毕,则激活动画,并清除该单词。通过循环与延迟函数更新屏幕的状态,控制活动单词的产生、移动与消失,同时刷新得分与统计数据。(By MagicPants)

三、数据结构设计与说明

在俄罗斯方块中:

  1. 采用了一个状态池(pool结构的二维数组)来储存所有池内位置的状态与颜色,也就是此前所提到的矩阵。结构定义如下:
  1. 采用了一个brick_default结构来储存不同种类方块(I、O、L、J、S、Z、T形方块)的颜色、规模与形状。结构定义如下:
  1. 采用SCORE结构储存得分与对应信息。结构定义如下:
  1. 采用了一个menu_entry结构进行菜单的储存,同时开发了framework模块对该结构进行操作(未完成)。结构定义如下:
  1. 采用了一个position结构的一维数组来储存变更的状态以实现脏矩形绘制。

在打字游戏中:

  1. 采用了白老师所提供示例中的一系列针对字典操作的数据结构。
  2. 定义了一个WORD结构来储存对应的单词。结构定义如下

四、系统设计难点与解决方案

打字游戏除字典读取外无难点(有示例可解决)。以下难点针对于俄罗斯方块。

1、难点:

①俄罗斯方块的旋转操作。

②绘图效果的优化。

③动态效果与时间控制。

2、解决方案(与难点对应):

①确定当前活动方块的范围后,截取该区域的活动方块状态,进行矩阵的旋转操作,适当调整形状后,与状态池进行比对,判断能否放入状态池,若能则在状态池中清除原有的活动方块,更新为新的活动方块;若不能则放弃此次旋转。

②采用脏矩形的方法绘制,明显降低了画面的抖动。

③采用通过读取屏幕的垂直回扫中断进行时间的控制。

五、人员分工说明

本小组依旧采用Git进行版本库控制。其中,俄罗斯方块主要由LLonely开发,MagicPants负责测试及细节的调整,打字游戏主要由MagicPants开发,LLonely负责测试以及对应的优化。

六、源码

我会在 GitHub 上建一个 Repo ,把那些代码 push 上去……(不过肯定不是原 Repo

背景

大一下学期 C 程序设计专题(C大程)的第二个专题,关于链表的操作,比较水的一次 Project ,当时正好生病了,便也没做的太认真,一开始是打算采用 GUI 或者 TeX 或者 HTML + CSS 实现多项式的显示的,以及幂为多项式的运算的,然而最后 DDL 在五一期间,赶完通识课的论文后就没有精力了(尤其是还生病了),当时的坑就放弃了。将具体链表操作的实现(毕竟比较简单)交给了队友 MagicPants ,然后我就实现了简单的 IO 操作和文件的模块化划分(这次变成我是可有可无的角色了(⊙﹏⊙))。不过当时正好看了《 C 专家编程》,便尝试了一下可变参量列表。

Screenshot1

Screenshot2

Screenshot3

报告及源码

继续阅读

相关背景

去年 C 程序设计专题的第一个 Project (模块化程序设计与递归函数专题),当时出于一种拿高分+逼格的目的,写了两个版本—— Console 版和 GUI 版。

Project 的要求就是用递归求解平面迷宫问题(或者用递归求解 N 皇后问题),然后再无其他限制。

当时在老师提及八皇后问题后,已经尝试写过若干个版本的 N 皇后了,所以 Project 就选择了迷宫问题。

效果图

Console 版

console-1

console-2 console-3

GUI 版(EGE实现)

maze-1 maze-2 maze-3

感想

怎么说呢,在当时,对我而言,这也算是有一定的难度的。当时最为繁琐的就是图形库的选择与图形化的实现,尤其是图形库的选择过程。当时尝试了GTK+, SDL, easyX, EGE,最后只有 easyX 和 EGE 能在我的电脑上正常的使用。然后又听说 EGE 的效率比 easyX 高,于是便选择了 EGE ,看了大约两个小时文档(然后发现几乎都没用到),最后写出了 GUI 版的 Project。

然后为了演示的效果,又用深度优先搜索实现了迷宫的自动生成。最终与基于递归实现的迷宫寻径整合到一起,实现了这个 Project。

具体实现及思路

采用一个全局的动态二维数组用于储存迷宫信息(如下表所示),同时记录墙体与空间位置。然后用若干个结构体记录坐标。

迷宫生成的方式,则是参考了 Wikipedia 的描述,首先将原始迷宫初始化为一张完全方格图,然后设定起点和终点,从起点开始进行深度优先搜索,每次遍历的方向与步数都随机取值,途中遇能拆的墙(墙对面有未遍历过的空间)则“拆墙”(将该位置改为空余的空间),直至遍历全图。

至于路经的寻找则是用相对简单的递归实现的(实际也是一个深度优先搜索,其实用广度优先搜索效率会高一些?,但是题目要求使用递归实现),一个简简单单的回溯过程。将终点位置作为递归出口,递推关系为相邻两空余点间的水平或垂直移动——若可以从当前坐标移动到某一相邻坐标(墙壁或路径点或标记不可通点为无法移动到的点),则将该点标记为路径点,从可移动位置进行下一轮的移动;若从当前点无法移动到其所有相邻的坐标,则将改点标记为不可通点,从当前函数返回,继续进行上一路径点所对应的移动过程。以此类推,在迷宫可通、迷宫大小合适的情况下,必然可得出至少一个可行解。(这一段是当时在报告上写的,直接了粘贴过来)这种思路很简单,可惜递归的实现一点都不优雅,当问题规模增大时,必然会堆栈溢出。尽管当时我的能力足以实现一个模拟堆栈的版本,但精力有限(总不能将时间都耗在这门课上),未去实现。

(差不多都忘了……早知当时就该顺手更新上来的)

源码

有点惨不忍睹……算是自己的黑历史吧。。。

当时交的版本随机遍历以生成迷宫,未采用 DFS

(当时写的修改版中函数竟然用的是 ‘dps’ 什么鬼(⊙﹏⊙))

Console 版(上交时的格式)

GUI 版(还有一个 Res 目录存放了实现动画的图片)

采用 DFS 的 GUI 版

 

(待下次有空时再将剩余的几个发上来(⊙﹏⊙)

趁着刚刚开学,事情并不算太多(其实也不少),把去年自己写的 C 程序设计专题的 Project 都发上来,为这一级的学弟学妹们提供参考吧。

  • 模块化程序设计与递归函数专题(迷宫寻径或八皇后问题): Maze-Project
  • 链表及其操作和应用专题(多项式计算器):Polynomial-Project
  • 图形化程序设计专题(俄罗斯方块或打字游戏):Tetris-Project
  • 算法专题(快速排序与插入排序):Sorting-Project

然而,时隔一年(应该是过去了一个学期),却发现自己并没有太大的进步,真是一种糟糕的感受。

上个学期真的是因为生病而整个荒废掉了,几乎没有什么长进,sigh~

很久以前的一份作业,似乎今年3月份时做的,都忘了思路了……

编程求某一个正整数的所有划分数。如输入6,则输出:

6 = 5+1
6 = 4+2
6 = 4+1+1
6 = 3+3
6 = 3+2+1
6 = 3+1+1+1
6 = 2+2+2
6 = 2+2+1+1
6 = 2+1+1+1+1
6 = 1+1+1+1+1+1

题目要求大致就是这样子,原题目要求是递归实现,但忘了为何我最后使用了迭代+链表实现了,反正不是自己要交的作业~ 代码如下~

有同学今年修了这门课,他来问我这道题,给他讲了递归版,顺手发上来吧。

继续阅读

  用链表和迭代的思维实现的汉诺塔,循环次数太多,效率有些差,但总是比递归要好一些的。
  思路是:在任何条件下,需要被移动的圆盘以及其被移动的目标位置都是可知且唯一的,所以可以通过迭代的方式实现。
  代码如下:
继续阅读