Category: 不学无术

Categories
不学无术

1056. Mice and Rice (25)

时间限制
30 ms
内存限制
32000 kB
代码长度限制
16000 B
判题程序
Standard
========
Mice and Rice is the name of a programming contest in which each programmer must write a piece of code to control the movements of a mouse in a given map. The goal of each mouse is to eat as much rice as possible in order to become a FatMouse.

Continue reading “1056. Mice and Rice (25)”
Categories
不学无术 木有技术

浅谈PCA 人脸识别

版权声明：转载时请以超链接形式标明文章原始出处和作者信息及本声明
http://leen2010.blogbus.com/logs/124631640.html

前几天讨论班我讲了基于PCA的人脸识别，当时我自己其实也只是知道这个算法流程，然后基于该算法利用c++实现了，效果还不错。后来跟师兄一起讨论的时候，才发现这个PCA还是有相当深刻的意义。
PCA的算法：矩阵C=AAT，A的每一列是一张人脸注（将一张人脸图片用一个列向量表示，即对于128*128的图片，将视为16384维的列向量），A的列数就是图片的张数。算法就是求矩阵C的特征向量，每个向量称之为特征脸[1]。为了简单，只取其中部分的特征向量，这些特征向量对应于某些特征值，通常是前M个大的特征值。这样便得到了M个特征向量。接下来就是将每张图片在这M个特征向量上做投影，得到一个M维的权重向量w=（w1,…wM），一个人可能有多张图片，于是将对应于这个人的权重向量做一个平均作为这个人的权重向量。然后对于每个新来的人脸，先求得一个权重向量，然后与人脸库中每个人的权重向量做比较，如果小于某个阈值，则认为他是人脸库中的这个人；否则视为unknown。当然，文章中还给出了另外一个判断一张图像是否是人脸的方法，这里不再讨论。对于计算的时候我们实际上求的是ATA，至于二者的关系，可以参考文章[1]，因为与后面讨论的关系不大，这里不细说了。
有个上述简介，我们就大概知道了PCA到底是怎么做的了。刨根问底一下，C到底是什么，C的特征向量又到底是什么，对应于特征值大的特征向量有有什么意义。
1.C到底是什么？我们先看一下C的（i,j）元素是什么。很简单，就是A的第i行与AT的第j列的乘积。那么A的第i行又是什么呢？就是每张图片的第i个像素构成的一个向量。则C的（i,j）元素就是每张图片的第i个像素构成的向量与每张图片的第j个像素构成的向量的乘积。回忆一下概率论中的协方差cov(x,y)=E((x-x–)(y- y–)),这里x– 是x的平均。如果我们把图片的第i个像素视为一个随机变量Xi，那么人脸库中的每张人脸的第i个像素的取值即为这个随机变量的所有取值。根据注，A的第i行的每个值都已经减去了Xi的均值，因此C的（i,j）元素就是随机变量Xi与Xj的协方差。到此，我们已经知道C是什么了。
2.C的特征向量是什么。我们知道对C求特征向量是找到一个可逆矩阵Q，使得Q-1CQ是一个对角阵D，D的元素即为特征值，Q中的每一列即为特征向量，与特征值所在的列一一对应。注意，因为C是实对称阵，故必然可以对角化。由于C是对称的，C的特征向量是正交的，因此Q便是一个正交阵，故Q-1即为QT。先从简单的角度来看，假设C已经是一个对角阵了，并且对角元素依次递减。即随机变量Xi与Xj(i!=j)时是不相关的，而Xi的方差则随着i的增大而减小。也就是前几个像素是方差比较大的像素，即在第一个像素上，每张图片的值变化最大，第二个像素次之，依此类推。举个例子，假设第一个像素表示人脸的额头上的某个点（也许你会问，第一个像素不是图片的最左上角的那个像素吗？为什么会是额头上的某个点，后面会说明为什么可以这么假设），而在这个点上，有些人有痣，有些人没有，那么这一点的方差就会比相邻的额头上的其他点大，因为其他点上，每个人的额头都差不多，因此其像素值也差不多，方差就小了。现在来考虑QTAATQ=D,这里依然假设D中的元素依次递减。对于QTA，QT的每一行是一个特征向量，QT的第i行与A的每一列相乘得到QTA的每一行，从矩阵的角度也可以看作是用QT对A做一个变换。记住这里的QTA可以看做前面讨论的A，那么变换的结果就是使得QTA前面的行对应的是方差大的像素，而且这个变换会把方差最大的放到了第一行（因为D的降序排列），这里也就解释了为什么前面那个例子可以认为第一个像素是额头上的某个点，因为做了变换。我们选择了QT的前M行作为特征向量，因为他们对应了前M个大的特征值。这里可以举一个直观但是不一定恰当的例子，人的头发部分对应的那些像素，经过QT变换后回到某个像素上，那么这个像素会是QTA中的哪个位置呢，我认为应该是QTA的列中靠下面的像素，因为在头发这个像素的地方每个人基本都是头发（这句话很别扭，我是想说，对于比较正规的人脸库，即每张人脸不会有太大的变化，某个人头发的对应的那几个像素对于其他人来说也都是头发，因此变换后这个像素对于每个人都差不多，方差小，固然会在比较靠后的位置了）。QTA的每一列的前M个元素对应的就是每张人脸的权重向量w。因此每张人脸的权重向量的同一个分量可以看作是新的像素，这些新的像素对应着方差依次减小的像素。对于一张新来的人脸，让他在特征向量上作投影得到权重向量，在这些方差大的像素处，如果跟某个人的比较接近，则认为是这个人，这个也是合理的。至此，也许没能讲清楚特征向量是什么，但我想对应于特征值大的特征向量有什么意义这一点也交代的差不多了。
3.2中交代了说了，这里想不到有什么需要补充的了。
理解了这几个问题之后，PCA简洁明了（这本来就是的）而又有深刻意义了。我突然发现原来看似简单的理论其实水深的很，o(︶︿︶)o ！我看文章实在是不够认真，如果没有师兄提问，估计我也不会去想这个问题。再次感谢WF师兄。
 
[1]Eigenfaces for Recognition. Matthew Turk,Alex Pentland 1991
注：A的每一列是一张人脸，这里的人脸是每张人脸减去了所有人脸的平均后的人脸

Categories
不学无术

1019. General Palindromic Number (20)

A number that will be the same when it is written forwards or backwards is known as a Palindromic Number. For example, 1234321 is a palindromic number. All single digit numbers are palindromic numbers.
Although palindromic numbers are most often considered in the decimal system, the concept of palindromicity can be applied to the natural numbers in any numeral system. Consider a number N > 0 in base b >= 2, where it is written in standard notation with k+1 digits ai as the sum of (aibi) for i from 0 to k. Here, as usual, 0 <= ai < b for all i and ak is non-zero. Then N is palindromic if and only if ai = ak-i for all i. Zero is written 0 in any base and is also palindromic by definition.
Given any non-negative decimal integer N and a base b, you are supposed to tell if N is a palindromic number in base b.
Input Specification:
Each input file contains one test case. Each case consists of two non-negative numbers N and b, where 0 <= N <= 109 is the decimal number and 2 <= b <= 109 is the base. The numbers are separated by a space.
Output Specification:
For each test case, first print in one line “Yes” if N is a palindromic number in base b, or “No” if not. Then in the next line, print N as the number in base b in the form “ak ak-1 … a0“. Notice that there must be no extra space at the end of output.
Sample Input 1:

27 2

Sample Output 1:

Yes
1 1 0 1 1

Sample Input 2:

121 5

Sample Output 2:

No
4 4 1

===========================
最近产量太低，都是有小bug的答案，唯独这道题终于。。。。
其实这道题相当简单，不想说啥了
时间空间都没有限制，如果机试碰到这种题，那估计是八辈子修来的福。。。
直接贴答案吧。。
===========================

#include 
using namespace std;
long resultSize = 0;
const int MAX_BUFF_SIZE = 30;
int buff[MAX_BUFF_SIZE];
void calcBase(long inputVal, long base)
{
	//计算以base为低的inputVal的值
	if(inputVal == 0)
	{
		resultSize = 1;
		buff[0] = 0;
		return;
	}
	resultSize = 0;
	while(inputVal > 0)
	{
		buff[resultSize++] = inputVal % base;
		inputVal /= base;
	}
}
bool isPalindrome()
{
	long limit = resultSize /2;
	for(long i=0; i> a >> b;
	calcBase(a, b);
	if( isPalindrome())
		cout << "Yes" << endl;
	else
		cout << "No" << endl;
	while(--resultSize)
	{
		cout << buff[resultSize] << " ";
	}
	cout << buff[0];
	return 0;
}
Categories
不学无术

vi 操作笔记

本文转载自：
http://www.cnblogs.com/xiaochaohuashengmi/archive/2011/10/14/2211202.html
======================================
1.关于退出

:wq!  ----强制保存退出
:wq  ---- 保存退出
:x   ----- 作用和:wq 一样
ZZ  ---- 作用和:wq一样，(注意Z是大写的，并且不是在命令模式)
:q  ---- 退出
:q!  ---  强制退出

 
==============================================
2.关于移动
h : 在当前行向左移动一个字符
j:  移动到下一行
k:  移动到上一行
l:  在当前行向右移动一个字符
Ctrl +f:  向前滚动一页
Ctrl +b:  向后滚动一页
:n   将光标定位到第n行
:$   将光标定位到最后一行
0   将光标定位到本行的行首
$   将光标定位到本行的行尾
G   将光标定位到本文章的最后一行，与:   $功能相同。
H   将光标定位到屏幕的顶端
M   将光标定位到屏幕的中间
L   将光标定位到屏幕的底端
============================================
3.关于搜索
/:   后面跟要查找的东西，在文件中向前搜索
?:  后面跟要查找的东西，在文件中向后搜索
n:  向前重复搜索
N:  向后重复搜索
=============================================
4.关于复制
yy:  复制光标当前行
nyy:  复制光标当前行到当前行以下的n-1行
:1,100 co 200   将1~100的内容复制到第200行。
:100,102 co $   将100~102行的内容复制到最后一行。
==============================================
5.关于粘贴
p :   粘贴到当前行的下一行
P(大) :   粘贴到当前行的 上一行
==============================================
6.关于删除.剪切

dd   删除当前行
ndd   与nyy相似
dw   删除一个单词
ndw   与ndd相似
x    删除一个字符
nx   删除n个字符
dG   删除当前光标到文件末尾的所有内容。
d0   删除当前光标到本行行首的所有内容
d$   删除当前光标到本行行尾的所有内容
:1,100d  删除1~100
:100d    删除第100行
:1,100 mo $   将1~100行的内容移动到最后一行。
=============================================
7.关于插入
i:  在当前位置的字符前面进入插入模式
I:  在当前行的开头进行插入
a:  在当前位置的字符后面进入插入模式
A:  在当前行的结尾进行插入
o:  在当前行下面打开一个新行进行插入
O:  在当前行上面打开一个新行进行插入
=============================================
8.关于撤销
 
u:  撤销上一次的更改
=============================================
9.关于替换
regexp:  是要匹配的式样
replacement:  是要替换的字符串
:s/regexp/replacement   ————————-替换当前行出现的第一个式样
:s/regexp/replacement/g  ————————-替换当前行所有的匹配
:%s/regexp/replacement/g  ———————–替换文件中所有匹配式样
=============================================
PS:  还有一个重要的命令就是”.” 命令，这个命令是用来重复上一命令的
 
vi里如何：撤销上次操作？，多次重复一组编辑操作？…….
 
a)   撤消上一个编辑操作。       ====>   u
b)   重复上一个编辑操作。     =====>   .
c)   还原被撤消的编辑操作。   ======>   Ctrl   +   R
d)   多次重复一组编辑操作。 ====>  “. ” 命令可以重复最近一次的编辑动作.
 
 

 
 
 
 

《鸟哥的Linux私房菜》vi 讲义

 

Categories
不学无术

Sleeping barber problem （睡觉的理发师问题）

今天做操作系统作业碰到的问题，一时想不出怎么做，后来Google了一下发现是个经典问题。
=========================================================================
以下英文内容转载自：http://www.answers.com/topic/sleeping-barber-problem
本人的理解继续往下看。
In computer science, the sleeping barber problem is a classic inter-process communication and synchronization problem between multiple operating system processes. The problem is analogous to that of keeping a barber working when there are customers, resting when there are none and doing so in an orderly manner.
The analogy is based upon a hypothetical barber shop with one barber. The barber has one barber chair and a waiting room with a number of chairs in it. When the barber finishes cutting a customer’s hair, he dismisses the customer and then goes to the waiting room to see if there are other customers waiting. If there are, he brings one of them back to the chair and cuts his hair. If there are no other customers waiting, he returns to his chair and sleeps in it.
Each customer, when he arrives, looks to see what the barber is doing. If the barber is sleeping, then the customer wakes him up and sits in the chair. If the barber is cutting hair, then the customer goes to the waiting room. If there is a free chair in the waiting room, the customer sits in it and waits his turn. If there is no free chair, then the customer leaves. Based on a naïve analysis, the above description should ensure that the shop functions correctly, with the barber cutting the hair of anyone who arrives until there are no more customers, and then sleeping until the next customer arrives. In practice, there are a number of problems that can occur that are illustrative of general scheduling problems.
The problems are all related to the fact that the actions by both the barber and the customer (checking the waiting room, entering the shop, taking a waiting room chair, etc.) all take an unknown amount of time. For example, a customer may arrive and observe that the barber is cutting hair, so he goes to the waiting room. While he is on his way, the barber finishes the haircut he is doing and goes to check the waiting room. Since there is no one there (the customer not having arrived yet), he goes back to his chair and sleeps. The barber is now waiting for a customer and the customer is waiting for the barber. In another example, two customers may arrive at the same time when there happens to be a single seat in the waiting room. They observe that the barber is cutting hair, go to the waiting room, and both attempt to occupy the single chair.
The Sleeping Barber Problem is often attributed to Edsger Dijkstra (1965), one of the pioneers in computer science.
Many possible solutions are available. The key element of each is a mutex, which ensures that only one of the participants can change state at once. The barber must acquire this mutex exclusion before checking for customers and release it when he begins either to sleep or cut hair. A customer must acquire it before entering the shop and release it once he is sitting in either a waiting room chair or the barber chair. This eliminates both of the problems mentioned in the previous section. A number of semaphores are also required to indicate the state of the system. For example, one might store the number of people in the waiting room.
A multiple sleeping barbers problem has the additional complexity of coordinating several barbers among the waiting customers.

Implementation

  • The following pseudocode guarantees synchronization between barber and customer and is deadlock free, but may lead to starvation of a customer. The functions wait() and signal() are functions provided by the semaphores.
# The first two are mutexes (only 0 or 1 possible)
Semaphore barberReady = 0
Semaphore accessWRSeats = 1     # if 1, the # of seats in the waiting room can be incremented or decremented
Semaphore custReady = 0         # the number of customers currently in the waiting room, ready to be served
int numberOfFreeWRSeats = N     # total number of seats in the waiting room
def Barber():
  while true:                   # Run in an infinite loop.
    wait(custReady)             # Try to acquire a customer - if none is available, go to sleep.
    wait(accessWRSeats)         # Awake - try to get access to modify # of available seats, otherwise sleep.
    numberOfFreeWRSeats += 1    # One waiting room chair becomes free.
    signal(barberReady)         # I am ready to cut.
    signal(accessWRSeats)       # Don't need the lock on the chairs anymore.
    # (Cut hair here.)
def Customer():
  while true:                   # Run in an infinite loop to simulate multiple customers.
    wait(accessWRSeats)         # Try to get access to the waiting room chairs.
    if numberOfFreeWRSeats > 0: # If there are any free seats:
      numberOfFreeWRSeats -= 1  #   sit down in a chair
      signal(custReady)         #   notify the barber, who's waiting until there is a customer
      signal(accessWRSeats)     #   don't need to lock the chairs anymore
      wait(barberReady)         #   wait until the barber is ready
      # (Have hair cut here.)
    else:                       # otherwise, there are no free seats; tough luck --
      signal(accessWRSeats)     #   but don't forget to release the lock on the seats!
      # (Leave without a haircut.)

============================

本人观点：
其中需要共享的数据应该只有可用的座椅数目(numberOfFreeWRSeats)，但是需要改动这个座椅数目的过程比较繁杂…原本以为N是用作信号量里面的，但是这个解决方案来看是把他作为额外的变量。
为什么N不能做信号量？后来想了一下..这个东西是共享的资源…明显不能拿来做信号量的吧。
文中3个信号量

Semaphore barberReady = 0
Semaphore accessWRSeats = 1     # if 1, the # of seats in the waiting room can be incremented or decremented
Semaphore custReady = 0         # the number of customers currently in the waiting room, ready to be served

其中barberReady是理发师就绪的信号量，barber讲客人请入理发室后，signal一下，然后示意客户可以开始理发了，客户那边wait这个信号量，等到了就开始理发过程。这个是一个同步的关系，因为肯定是要理发师先准备好，然后客人才可以开始理发，这两个动作有顺序要求，所以信号量初值设置成0.
第二个accessWRSeats是用来锁座椅数目改变的，锁住（=0）的时候，说明waitingroom内有人员变动中，要阻塞其他人对人员变动的尝试。显然这是一个互斥量（mutex），当客人进入理发室准备理发时、或者理发店外有人进入时，都要改变numberOfFreeWRSeats这个量，这种操作显然是独占的，同时只能有一方来修改这个值，所以引入此信号量协调。
第三个嘛..客人就绪的信号量，主要原因是barber空闲下来的时候需要睡大觉。这个与第一个信号量一样，是一个同步的问题。即客人先要准备好了，才能把理发师唤醒做事情，不然就别吵到他。
三个信号量理解了，后面的过程也就一目了然了。不知道我说的对不对…
这个问题应该有另一(或多)种解法，另一种解法是指会导致barber的starvation的解法，或者是权衡两者折中的办法，这个没有多想过。

Categories
不学无术 木有技术

【Android Camera】之 Preview

本文转载自：

http://blog.csdn.net/yiyaaixuexi/article/details/6455741

================================================================
实在不好复制过来，去原文看吧。

Categories
不学无术 木有技术

1042. Shuffling Machine (20)

Shuffling is a procedure used to randomize a deck of playing cards. Because standard shuffling techniques are seen as weak, and in order to avoid “inside jobs” where employees collaborate with gamblers by performing inadequate shuffles, many casinos employ automatic shuffling machines. Your task is to simulate a shuffling machine.
The machine shuffles a deck of 54 cards according to a given random order and repeats for a given number of times. It is assumed that the initial status of a card deck is in the following order:
S1, S2, …, S13, H1, H2, …, H13, C1, C2, …, C13, D1, D2, …, D13, J1, J2
where “S” stands for “Spade”, “H” for “Heart”, “C” for “Club”, “D” for “Diamond”, and “J” for “Joker”. A given order is a permutation of distinct integers in [1, 54]. If the number at the i-th position is j, it means to move the card from position i to position j. For example, suppose we only have 5 cards: S3, H5, C1, D13 and J2. Given a shuffling order {4, 2, 5, 3, 1}, the result will be: J2, H5, D13, S3, C1. If we are to repeat the shuffling again, the result will be: C1, H5, S3, J2, D13.
Input Specification:
Each input file contains one test case. For each case, the first line contains a positive integer K (<= 20) which is the number of repeat times. Then the next line contains the given order. All the numbers in a line are separated by a space.
Output Specification:
For each test case, print the shuffling results in one line. All the cards are separated by a space, and there must be no extra space at the end of the line.
Sample Input:

2
36 52 37 38 3 39 40 53 54 41 11 12 13 42 43 44 2 4 23 24 25 26 27 6 7 8 48 49 50 51 9 10 14 15 16 5 17 18 19 1 20 21 22 28 29 30 31 32 33 34 35 45 46 47

Sample Output:

S7 C11 C10 C12 S1 H7 H8 H9 D8 D9 S11 S12 S13 D10 D11 D12 S3 S4 S6 S10 H1 H2 C13 D2 D3 D4 H6 H3 D13 J1 J2 C1 C2 C3 C4 D1 S5 H5 H11 H12 C6 C7 C8 C9 S2 S8 S9 H10 D5 D6 D7 H4 H13 C5

===================================
本题目主要难度：英语阅读。
就是数组里面元素换来换去没啥好说的，就是发现自己数组指针这块了解的不是很清晰，以后得注意。
===================================

#include 
#include 
using namespace std;
const int SUFF_SIZE = 54;
int *cards = new int[SUFF_SIZE]; //扑克牌数组
int *results = new int[SUFF_SIZE];
int* suffle(int * src, int* rule)
{
	for(int i=0; i= 10)
	{
		result += "1";
		postfix = postfix%10;
	}
	result += (char)(postfix + 0x30);
	return result;
}
int rules[SUFF_SIZE]; //suffle规则
int main()
{
	int K;
	cin >> K;
	for(int i=0; i> rules[i];
	}
	while(K--)
	{
		suffle(cards, rules);
		for(int i=0; i
Categories
不学无术 木有技术

第二章 啊哈！算法

原文见：

http://blog.csdn.net/silenough/article/details/7040028

 
A. 给定一个最多包含40亿个随机排列的32位整数的顺序文件，找出一个不在文件中的32位整数(在文件中至少缺少一个这样的数—为什么？)。在具有足够内存的情况下，如何解决该问题？如果有几个外部的“临时”文件可用，但是仅有几百字节的内村，又该如何解决该问题？
因为2^32 大于40亿，所以文件中至少缺失一个整数。我们从表示每个整数的32位的视角来考虑二分搜索，算法的第一趟（最多）读取40亿个输入整数，并把起始位为0的整数写入一个顺序文件，把起始位为1的整数写入另一个顺序文件。这两个文件中，有一个文件最多包含20亿个整数，接下来将该文件用作当前输入并重复探测过程，但这次探测的是第二个位。如果原始的输入文件包含n个元素，那么第一趟将读取n个整数，第二趟最多读取n/2个整数，第三趟最多读取n/4个整数，依次类推，所以总的运行时间正比于n。
如果内存足够，采用位图技术，通过排序文件并扫描，也能够找到缺失的整数，但是这样做会导致运行时间正比于nlog(n).
1. 考虑查找给定输入单词的所有变位词的问题。仅给定单词和字典的情况下，如何解决该问题？如果有一些时间和空间可以在响应任何查询之前预先处理字典，又会如何？
首先计算给定单词的标识，若果不允许预处理，那么久只能顺序读取整个文件，计算每个单词的标识，并于给定单词的标识进行比较。
 

  1. //压缩一个单词，形成其标识,设定单词中相同字母不会超过99个
  2. void compress(char * pWord, int len, char * pFlag)
  3. {
  4.     sort(pWord, pWord+len); //对单词进行排序
  5.     int i = 0;
  6.     int nCount;            //计数重复字母的个数
  7.     char chCount[3];       //存放整数到字符的转换值，整数最大为99
  8.     while (*pWord != ‘’)
  9.     {
  10.         char chTemp = *pWord;
  11.         char *pTemp = pWord + 1;
  12.         nCount = 1;
  14.         while (true)
  15.         {
  16.             if (chTemp == *pTemp++)
  17.             {
  18.                 ++nCount;
  19.             }
  20.             else
  21.             {
  22.                 *(pFlag + i++) = *pWord;
  23.             //  ++i;
  24.                 memset(chCount, ‘’, 3);
  25.                 _itoa(nCount, chCount, 10);
  26.                 if (nCount >= 10)
  27.                 {
  28.                     *(pFlag + i++) = *(chCount + 0);
  29.                 //  i++;
  30.                     *(pFlag + i++) = *(chCount + 1);
  31.                 //  ++i;
  32.                 }
  33.                 else
  34.                 {
  35.                     *(pFlag + i++) = *(chCount + 0);
  36.                 //  ++i;
  37.                 }
  38.                 pWord = pWord + nCount;
  39.                 break;
  40.             }
  41.         }
  42.     }
  43. }

如果允许进行预处理，我们可以在一个预先计算好的结构中执行二分查找，该结构中包含按标识排序的(标识，单词)对。
2. 给定包含4300 000 000 个32位整数的顺序文件，如何找出一个出现至少两次的整数？
 方法一：
二分搜索通过递归搜索包含半数以上整数的子区间来查找至少出现两次的单词。因为4300000000  > 2^32，所以必定存在重复的整数，搜索范围从[0, 2^32）开始，中间值mid为2^31，若区间[0, 2^31)内的整数个数大于2^31个，则调整搜索区间为[0, 2^31)，反之则调整搜索区间为[2^31， 2^32)，然后再对整个文件再遍历一遍，直到得到最后的结果。这样一共会有log2(n)次的搜索，每次遍历n个整数（每次都是完全遍历），总体的复杂度为o(nlog2(n))。
 

  1. #include <iostream>
  2. using namespace std;
  4. int pow2(int n)   //求2的n次幂
  5. {
  6.     int i;
  7.     int r = 1;
  8.     for (i = 0; i < n; i++)
  9.     {
  10.         r *=2;
  11.     }
  12.     return r;
  13. }
  16. int _tmain(int argc, _TCHAR* argv[])
  17. {
  18.     int arr[] = {4,2,5,1,6,3,8,0,7,6,11,12,14,9,15,10,13};
  19.     int len = sizeof(arr) / sizeof(int);
  21.     int nCount = 0;
  22.     int bit = 4;
  23.     int low = 0;
  24.     int high = pow2(bit);
  25.     int mid = (low +high) / 2;
  26.     int i;
  28.     while (low <= high )
  29.     {
  30.         mid = (low + high) / 2;  //取中间值
  31.         nCount = 0;
  33.         for (i = 0; i < len; i++)    //计数[low, mid）范围内整数的个数
  34.         {
  35.             if (arr[i] < mid && arr[i] >= low)
  36.             {
  37.                 ++nCount;
  38.             }
  39.         }  //end for
  41.         if (nCount == 0)     //若nCount为0，则mid即为重复的整数
  42.         {
  43.             cout << mid<<endl;
  44.             break;
  45.         }
  46.         else
  47.         {
  48.             if (nCount > (mid – low))  //若大于mid与low的差值,
  49.             {                          //表明重复的整数落在区间[low, mid）
  50.                 high = mid;        //缩小区间
  51.             }
  52.             else
  53.             {
  54.                 low = mid;
  55.             }  //end if
  56.         } //end if （） else（）
  57.     }  //end while
  58. }

 
   方法二：
 

  1. #include <iostream>
  2. #include <algorithm>
  3. using namespace std;
  5. int _tmain(int argc, _TCHAR* argv[])
  6. {
  7.     int arr[] = {4,2,5,1,7,3,8,0,7,6,11,12,14,9,15,10,13};
  8.     int len = sizeof(arr) / sizeof(int);
  10.     sort(arr, arr + len);   //先进行排序
  11.     int i;
  12.     int increase = arr[0];
  13.     for (i = 0; i < len; i++)
  14.     {
  15.         if (arr[i] > (i + increase))
  16.         {
  17.             increase += (arr[i] – i – increase);
  18.             continue;
  19.         }
  21.         if (arr[i] < (i + increase))
  22.         {
  23.             cout << arr[i] << endl;
  24.             break;
  25.         }
  26.     }
  27. }

3. 前面涉及了两个需要精巧代码来实现的向量旋转算法，将其分别作为独立的程序实现。在每个程序中，i和n的最大公约数如何实现？
采用辗转相除法求两个整数的最大公约数。
 

  1. int gcd(int a, int b)
  2. {
  3.     int temp;
  4.     if (a < b)  //使a始终为最大数
  5.     {
  6.         temp = a;
  7.         a = b;
  8.         b = temp;
  9.     }
  11.     while (b != 0)
  12.     {
  13.         temp = a % b;
  14.         a = b;
  15.         b = temp;
  16.     }
  17.     return a;
  18. }

 
 
方法一：海豚算法
 

  1. void Shifting(char * pArry, int rotdistance, int len)
  2. {
  3.     int i, j;
  4.     char temp;
  5.     int igcd = gcd(rotdistance, len);
  6.     for (i = 0; i < igcd; i++)
  7.     {
  8.         temp = pArry[i];
  9.         j = i;
  10.         for (; 😉
  11.         {
  12.             int k = j + rotdistance;
  13.             k %= len;
  14.             if ( k == i)
  15.             {
  16.                 break;
  17.             }
  18.             pArry[j] = pArry[k];
  19.             j = k;
  20.         }
  21.         pArry[j] = temp;
  22.     }
  23. }

方法二：块交换算法
 

  1. #include <iostream>
  2. using namespace std;
  4. //交换pArry[a…a+m-1]和pArry[b…b+m-1]
  5. void myswap(char *pArry, int a, int b, int m)
  6. {
  7.     char temp;
  8.     for (int i = 0; i < m; i++)
  9.     {
  10.         temp = pArry[a + i];
  11.         pArry[a + i] = pArry[b + i];
  12.         pArry[b + i] = temp;
  13.     }
  15. }
  17. void Shifting(char * pArry, int rotdistance, int len)
  18. {
  19.     if (rotdistance == 0 || rotdistance == len)
  20.     {
  21.         return;
  22.     }
  24.     int i, j, p;
  25.     i = p = rotdistance;
  26.     j = len – p;
  28.     while (i != j)
  29.     {
  30.         if (i > j)
  31.         {
  32.             myswap(pArry, p – i, p, j);
  33.             i -= j;
  34.         }
  35.         else
  36.         {
  37.             myswap(pArry, p – i, p + j – i, i);
  38.             j -= i;
  39.         }
  40.     }
  41.     myswap(pArry, p – i, p, i);
  42. }
  44. int _tmain(int argc, _TCHAR* argv[])
  45. {
  46.     char arry[] = “abcdefghijklmn”;
  47.     int len = strlen(arry);
  48.     Shifting(arry, 10, len);
  49.     return 0;
  50. }

方法三：求逆算法
根据矩阵的转置理论，对于矩阵AB，要得到BA，则分别求A和B的转置A’, B’，然后对(A’B’)转置，即(A’B’)’ = BA。同理，可以得到另一种一维向量向左旋转的算法。将要被旋转的向量x看做两部分ab，这里a代表x中的前rotdistance个元素。首先对a部分进行反转，再对b部分进行反转，最后对整个向量x进行反转即可。
对于字符串“abcdefgh”, rotdistance = 3, len = 8:
reverse(1, rotdistance);          //cbadefgh
reverse(rotdistance+1, len);  //cbahgfed
reverse(1, len);                       //defghabc
 

  1. #include <iostream>
  2. using namespace std;
  4. //对字符串中第i个字符到第j个字符进行反转，i、j>=1
  5. void MyReverse(char * pArry, int i, int j)
  6. {
  7.     int front = i;
  8.     int tail = j;
  9.     char temp;
  10.     while (front != tail && front < tail)
  11.     {
  12.         temp = pArry[front – 1];
  13.         pArry[front – 1] = pArry[tail – 1];
  14.         pArry[tail – 1] = temp;
  15.         ++front;
  16.         –tail;
  17.     }
  18. }
  20. //将字符串左旋转rotdistance个字符
  21. void Shifting(char * pArry, int rotdistance, int len)
  22. {
  23.     if (rotdistance == 0 || rotdistance == len)
  24.     {
  25.         return;
  26.     }
  27.     MyReverse(pArry, 1, rotdistance);
  28.     MyReverse(pArry, rotdistance + 1, len);
  29.     MyReverse(pArry, 1, len);
  30. }
  32. int _tmain(int argc, _TCHAR* argv[])
  33. {
  34.     char arry[] = “abcdefgh”;
  35.     int len = strlen(arry);
  36.     Shifting(arry, 5, len);
  37.     cout << arry << endl;
  38.     return 0;
  39. }

 
5. 向量旋转函数将向量ab变为ba。如何将向量abc变成cba？(这个交换非相邻内存块的问题进行了建模)
可以将bc看做一个整体，然后运用向量旋转算法，得到bca。然后对bc运用向量旋转算法，得到cb。最后变换后的向量为即cba.
 

  1. //交换pArry[a…a+m-1]和pArry[b…b+m-1]
  2. void myswap(char *pArry, int a, int b, int m)
  3. {
  4.     char temp;
  5.     for (int i = 0; i < m; i++)
  6.     {
  7.         temp = pArry[a + i];
  8.         pArry[a + i] = pArry[b + i];
  9.         pArry[b + i] = temp;
  10.     }
  12. }

 
 

  1. //对向量pArry中起始于ibegainPos位置的irotdistance-ibegainPos个元素
  2. //与起始于ibegainPos+irotdistance位置到位置iendPos之前的元素进行交换
  3. void SuccessiveSwap(char * pArry, int ibegainPos, int irotdistance, int iendPos)
  4. {
  5.     int i, j;
  6.     i = irotdistance – ibegainPos;
  7.     j = iendPos – irotdistance;
  9.     while (i != j)
  10.     {
  11.         if (i > j)
  12.         {
  13.             myswap(pArry, irotdistance – i, irotdistance, j);
  14.             i -= j;
  15.         }
  16.         else
  17.         {
  18.             myswap(pArry, irotdistance – i, irotdistance + j – i, i);
  19.             j -= i;
  20.         }
  21.     }
  22.     myswap(pArry, irotdistance – i, irotdistance, i);
  23. }

6. 如何实现一个以名字的按键编码为参数，并返回所有可能的匹配名字的函数
用按键编码标识每一个名字，并根据标识排序，然后顺序读取排序后的文件并输出具有不同名字的相同标识。为了检索出给定按钮编码的名字，可以使用一种包含编码标识和其他数据的结构。然后对该结构排序，使用二分搜索查询按键编码。
7. 转置一个存储在磁带上的4000×4000的矩阵(每条记录的格式相同，为数十个字节)。如何将运行的时间减少到半个小时？
给每条记录插入列号和行号，然后调用系统的磁带排序程序先按列排序再按行排序，最后使用另一个程序删除列号和行号。
8. 给定一个n元实数集合、一个实数t和一个整数k，如何快速确定是否存在一个k元子集，其元素之和不超过t？
对n元实数集合先进行排序，然后计算前k个元素的和既可以确定是否存在这样一个子集。若采用快速排序，时间复杂度为nlog10(n)。
9. 顺序搜素和二分搜索代表了搜索时间和预处理时间之间的折中。处理一个n元表格时，需要执行多少次二分搜索才能弥补对表进行排序所消耗的预处理时间？
对于顺序搜索，搜索k次的时间复杂度为O(kn);若采用二分搜索则需要先排序，则二分搜索的时间复杂度为O(nlog10(n)+log2(n))
变位词程序的实现
 

  1. //对从文件中读入的每个单词调用qsort库函数排序，输出到新的文件中
  2. void mysign(FILE * pFile1, FILE * pFile2)
  3. {
  4.     char word[20];
  5.     char sig[20];
  7.     pFile1 = fopen(“..file1.txt”, “r”);
  8.     if ( NULL == pFile1)
  9.     {
  10.         cout << “Open file1 error!” << endl;
  11.         return ;
  12.     }
  14.     pFile2 = fopen(“..file2.txt”, “w”);
  15.     if (NULL == pFile2)
  16.     {
  17.         cout << “Open file2 error!” << endl;
  18.         return ;
  19.     }
  20.     while (!feof(pFile1))
  21.     {
  22.         memset(word, ‘’, 20);
  23.         memset(sig, ‘’, 20);
  24.         fscanf(pFile1, “%s”, word);
  25.         strncpy(sig, word, strlen(word));
  26.         qsort(sig, strlen(sig), sizeof(char), charcomp);
  27.         fprintf(pFile2, “%s   %sn”, sig, word);
  28.     }
  29.     fclose(pFile1);
  30.     fclose(pFile2);
  31. }


 
 
使用sort程序将具有相同标识的单词归拢到一起，形成一个新的文件。最后调用squash()函数将具有相同变位词的单词在同一行输出。
 

  1. //将具有相同变位词的单词在同一行输出
  2. void squash()
  3. {
  4.     FILE * pFile3 = fopen(“..file3.txt”, “r”);
  5.     if ( NULL == pFile3)
  6.     {
  7.         cout << “Open file3 error!” << endl;
  8.         return ;
  9.     }
  11.     FILE * pFile4 = fopen(“..file4.txt”, “w”);
  12.     if (NULL == pFile4)
  13.     {
  14.         cout << “Open file4 error!” << endl;
  15.     }
  17.     char word[20];
  18.     char sig[20];
  19.     char oldsig[20];
  20.     int linenum = 0;
  21.     memset(oldsig, ‘’, 20);
  22.     while (!feof(pFile3))
  23.     {
  24.         memset(word, ‘’, 20);
  25.         memset(sig, ‘’, 20);
  26.         fscanf(pFile3, “%s %s”, sig, word);
  28.         if (strncmp(sig, oldsig, strlen(sig)) != 0 )
  29.         {
  30.             fprintf(pFile4, “n”);
  31.         }
  32.         strncpy(oldsig, sig, strlen(sig));
  33.         fprintf(pFile4, “%s “, word);
  34.     }
  35.     fclose(pFile3);
  36.     fclose(pFile4);
  37. }

Categories
不学无术

SQL HAVING 子句

HAVING 子句

在 SQL 中增加 HAVING 子句原因是，WHERE 关键字无法与合计函数一起使用。

SQL HAVING 语法

SELECT column_name, aggregate_function(column_name)
FROM table_name
WHERE column_name operator value
GROUP BY column_name
HAVING aggregate_function(column_name) operator value

SQL HAVING 实例

我们拥有下面这个 “Orders” 表：

O_Id OrderDate OrderPrice Customer
1 2008/12/29 1000 Bush
2 2008/11/23 1600 Carter
3 2008/10/05 700 Bush
4 2008/09/28 300 Bush
5 2008/08/06 2000 Adams
6 2008/07/21 100 Carter

现在，我们希望查找订单总金额少于 2000 的客户。
我们使用如下 SQL 语句：

SELECT Customer,SUM(OrderPrice) FROM Orders
GROUP BY Customer
HAVING SUM(OrderPrice)<2000

结果集类似：

Customer SUM(OrderPrice)
Carter 1700

现在我们希望查找客户 “Bush” 或 “Adams” 拥有超过 1500 的订单总金额。
我们在 SQL 语句中增加了一个普通的 WHERE 子句：

SELECT Customer,SUM(OrderPrice) FROM Orders
WHERE Customer='Bush' OR Customer='Adams'
GROUP BY Customer
HAVING SUM(OrderPrice)>1500

结果集：

Customer SUM(OrderPrice)
Bush 2000
Adams 2000

 
http://www.w3school.com.cn/sql/sql_having.asp

Categories
不学无术 木有技术

1020. Tree Traversals (25)

Suppose that all the keys in a binary tree are distinct positive integers. Given the postorder and inorder traversal sequences, you are supposed to output the level order traversal sequence of the corresponding binary tree.
Input Specification:
Each input file contains one test case. For each case, the first line gives a positive integer N (<=30), the total number of nodes in the binary tree. The second line gives the postorder sequence and the third line gives the inorder sequence. All the numbers in a line are separated by a space.
Output Specification:
For each test case, print in one line the level order traversal sequence of the corresponding binary tree. All the numbers in a line must be separated by exactly one space, and there must be no extra space at the end of the line.
Sample Input:

7
2 3 1 5 7 6 4
1 2 3 4 5 6 7

Sample Output:

4 1 6 3 5 7 2

============================================================
传说中正确率比较高的一道题，有0.5哈哈
做起来却发现数据结构概念忘光光，后序遍历什么的一概忘掉了，百度百科了一下终于懂得了..
题目也没什么技巧，给定两种顺序，肯定能排出二叉树的
要求输出层次结构就更好办了…
因为题目简单所以多记下一点，怕自己万一碰到忘掉了。
============================================================
原理：
后序遍历的顺序是L-R-D，后面假定这个输入序列为A序列
中序遍历是L-D-R顺序，假定为B序列
序列遍历时其实是递归的感觉。
也就是说，后序遍历顺序的最后一个节点，肯定是D节点无误（一棵树不会没有根，除非是空树）
所以给定A、B序列，把A序列的最后一个节点放到B序列中，那么B序列就能被分割成左中右三个部分，
中间那个节点，中间节点的左子树、右子树。
于是也成为了个递归的过程，每次分割完成后，把左右字数再找他们对应的D节点（从序列A中看），就能到世界的尽头了。
============================================================
伪代码：

工作队列：W
输入序列：A, B
将B整个队列压入W
while(工作队列非空)
{
    取出工作队列的队首元素（也是一个队列）frontList
    弹出队首元素（c++里面取top()或者front()和pop()是两个过程）
    找出frontList中位于A列最后次序的元素m
    打印m
    将frontList中排在m元素左侧的那些元素组成新列表，压入W队列
    将frontList中排在m元素右侧的那些元素组成新列表，压入W队列
}

==============================================================
代码（高手勿喷，效率较低但是在PAT中耗时0ms,内存占用750k+-）：

#include 
#include 
using namespace std;
int N;
int* A; //后序遍历顺序
int* B; //中序遍历顺序
struct QueueElem
{
	//压到工作队列中的元素（其实也是个队列）
	int capacity;
	int curSize;
	int* elements;
	QueueElem(int _capacity)
	{
		capacity = _capacity;
		curSize = 0;
		elements = new int[capacity];
	}
	void addElem(int e)
	{
		if(curSize >= capacity )
		{
			cerr << "Fail to insert. Size exceeded!" << endl;
			return;
		}
		elements[curSize++] = e;
	}
};
queue W; //工作队列
int findLastOnePos(QueueElem e)
{
	//寻找QueueElem元素中处在A列次序最后的那个元素
	//返回值为该元素在【e列表】中的位置！
	//2层循环效率较低..
	int lastIndexA = -1;
	int lastIndexE = -1;
	for(int i=0; i lastIndexA)
			{
				lastIndexA = posA;
				lastIndexE = i;
				break;
			}
		}
	}
	return lastIndexE;
}
int main()
{
	cin >> N;
	A = new int[N];
	B = new int[N];
	QueueElem orig(N);
	for(int i=0; i>A[i];
	for(int i=0; i>B[i];
		orig.addElem(B[i]);
	}
	///////////
	W.push(orig);
	int count = N;
	while (count--)
	{
		QueueElem qe = W.front();
		W.pop();
		int posM = findLastOnePos(qe);
		cout << qe.elements[posM];
		if( count > 0)
			cout << " ";
		if(posM > 0)
		{
			//有左侧元素
			QueueElem L(posM);
			//左侧元素组成列压栈，务必保持原有顺序！
			for(int i=0; i 1)
		{
			//有右侧元素
			QueueElem R(qe.curSize - posM -1);
			//右侧元素组成列压栈，务必保持原有顺序！
			for(int i=posM +1; i