横向打印二叉树

题目

横向打印二叉树

题目描述

二叉树可以用于排序。其原理很简单:对于一个排序二叉树添加新节点时,先与根节点比较,若小则交给左子树继续处理,否则交给右子树。
当遇到空子树时,则把该节点放入那个位置。
比如,10 8 5 7 12 4 的输入顺序,应该建成二叉树如下图所示,其中.表示空白。

...|-12
10-|
...|-8-|
.......|...|-7
.......|-5-|
...........|-4

本题目要求:根据已知的数字,建立排序二叉树,并在标准输出中横向打印该二叉树。

更新Win8.1后浏览器无法打开网页解决办法

最近有朋友反映在更新至Win8.1后出现了,浏览器无法打开网页但是可以登陆QQ的症状。

以下便是当时的解决办法:

以管理员身份进入命令行模式

  1. 以管理员身份进入命令行模式。(按下Win+R组合键,出现如上图界面,勾选以管理员权限创建任务,然后输入cmd,点击确定,弹出一个命令行窗口。)
  2. 输入netsh winsock reset,按照提示重启后即可。

删除数字问题的数学证明

A1…An组成的序列,删除第一个非递减数字的前一个数字,那么余下的它是一个最大的数。

证明:
设第一个非递减的数字为Ai+1 ,那么前一个数字是Ai,同时有Ai < Ai+1
假设存在其他解….然后要么是更低位的数字Aj,要么是更高位的 Ak > Ak+1。

A1 … Ai-1 Ai Ai+1 … Aj-1 Aj Aj+1
A1 … Ai-1 Ai Ai+1 … Aj-1 Aj Aj+1

两者比较

A1 … Ai-1 Ai+1 … Aj-1 Aj Aj+1
A1 … Ai-1 Ai Ai+1 … Aj-1 Aj+1

因为Ai < Ai+1, 所以删除Ai情况组成的数大于删除Ak情况组成的数。

对于更高位的Ak > Ak+1,同理可证。

书的页码

题目

一本书的页面从自然数1开始顺序编码直到自然数n。书的页码按照n的位数编排,不足时补充前导数字0。例如,n是149时,第6页用数字006表示,而不是06或6。现在要求你对给定书的总页码n,计算出书的全部页码分别用到多少次数字0,1,2,…,9.

Sierpinski三角形

大自然一切都是随机的,但是很多事物又反应了它自身的规律。
在学习分形的过程中,再一次见到了这种随机中的规律,一切都那么的美妙。

谢宾斯基(Sierpinski)分形三角形,这里使用画点构图的方法。

按照其生成算法:
1.在一个平面里,取三个点ABC,组成一个三角形
2.在这个三角形附近,任选一点T作为第一个点
3.在ABC三点中任意选一个点P,画出P与上一个点Q的中点,并画出
4.达到迭代次数退出,否则回第3步

直流电路分析2B法的程序设计解决方案

直流电路分析中较为普通的一种方法是2B法,这种方法在手工计算上非常麻烦,而且不易编程求解。而回路电流法和结点电压法在手工计算和编程实现上都更为简单(这两种方法在电路分析软件上已经使用)。但是这并不影响我探究使用2B法编程,因为2B法反映的是一个非常普通的拓扑学运用。

线段树学习

线段树适合解决N次成段更新的问题。例如,给你N条不超过K的线段,然后有M次询问,每次询问要求你回答一个点出现了几次。当给你的线段是 [2,5] [4,6] [0,7]时,依次问你2出现了多少次?4出现了多少次?7出现了多少次?你应该要给出的答案是 2,3,1。

一个很容易想到的算法就是建立一个N*2的数组,读入每个线段的首尾值记录在数组中,每次询问遍历整个数组逐个判断得出结果。不可否认这是一种解决办法,但是在数据量大的时,它显得非常不合理。(数据量的不同决定了算法,在不考虑输入数据的情况下,讨论算法的优劣是没有意义的。)这种算法每次询问需要遍历整个数组,因此时间复杂度是O(M*N),空间复杂度是O(N*2)。

另一个很容易想到的算法就是开拓一个很大的数组,读入一个线段的首尾值后,将线段范围内的点都更新。那么询问的时候,每次询问的时候直接读取下标就可以了。这种算法的复杂度取决于出现的线段最长值K和线段多少的N,时间复杂度是O(K*N),空间复杂度是O(K)。

可以说第一种算法适用于线段数目不多,查询也不多的情况,第二种算法适用于线段的最大长度很小,线段数量不多,但是询问次数非常多的情况。

可以说这两种方法对数据都有种严格的要求。一个较为折中的考虑就是采用线段树来存储数据。线段树是 O((M+N)*logK)的时间复杂度,代价只是空间复杂度的小幅度上升(现在机器内存都已经很大了,在这种问题上时间显得比空间重要)。