Problem:

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

Solutions:

1-Two-Sum 的改动版,有序的数组就可以考虑使用二分搜索进行查找,偷懒写了递归版,本以为使用 slice 写二分查找会比较赞,但是实际上并没有简化的感觉。

Problem:

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution.

Example:

The returned answers should be zero-based.

Solutions:

Brute Force 不值一提,本该用 HashTable 解决的问题在遇到了 Go 自带的 map 后就变得十分简单了,虽然写一个开地址哈希表也并不费事。

 

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 递减,若出现了未记录的数,则继续如上的计算。

代码如下:

 

One way that the police finds the head of a gang is to check people’s phone calls. If there is a phone call between A and B, we say that A and B is related. The weight of a relation is defined to be the total time length of all the phone calls made between the two persons. A “Gang” is a cluster of more than 2 persons who are related to each other with total relation weight being greater than a given threshold K. In each gang, the one with maximum total weight is the head. Now given a list of phone calls, you are supposed to find the gangs and the heads.

Input Specification:

Each input file contains one test case. For each case, the first line contains two positive numbers N and K (both less than or equal to 1000), the number of phone calls and the weight threthold, respectively. Then N lines follow, each in the following format:

Name1 Name2 Time

where Name1 and Name2 are the names of people at the two ends of the call, and Time is the length of the call. A name is a string of three capital letters chosen from A-Z. A time length is a positive integer which is no more than 1000 minutes.

Output Specification:

For each test case, first print in a line the total number of gangs. Then for each gang, print in a line the name of the head and the total number of the members. It is guaranteed that the head is unique for each gang. The output must be sorted according to the alphabetical order of the names of the heads.

Sample Input 1:

Sample Output 1:

Sample Input 2:

Sample Output 2:

用 disjoint set 来确定 Gang ,在 union 的过程中更新数据,同时在 find 的过程中确定 Head 是谁。偷懒直接用一个数组储存了姓名信息……

注意一下,输入共有 N 组数据,但是,最多可以有 2*N 的人。一开始犯二了,没想到……测试点 3 就段错误了……

代码如下:

继续阅读

An AVL tree is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. Figures 1-4 illustrate the rotation rules.

    
    
Now given a sequence of insertions, you are supposed to tell the root of the resulting AVL tree.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive integer N (<=20) which is the total number of keys to be inserted. Then N distinct integer keys are given in the next line. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print ythe root of the resulting AVL tree in one line.

Sample Input 1:

Sample Output 1:

Sample Input 2:

Sample Output 2:

偷懒写了递归版……

代码如下:

继续阅读

拍集体照时队形很重要,这里对给定的N个人K排的队形设计排队规则如下:

  • 每排人数为N/K(向下取整),多出来的人全部站在最后一排;
  • 后排所有人的个子都不比前排任何人矮;
  • 每排中最高者站中间(中间位置为m/2+1,其中m为该排人数,除法向下取整);
  • 每排其他人以中间人为轴,按身高非增序,先右后左交替入队站在中间人的两侧(例如5人身高为190、188、186、175、170,则队形为175、188、190、186、170。这里假设你面对拍照者,所以你的左边是中间人的右边);
  • 若多人身高相同,则按名字的字典序升序排列。这里保证无重名。

现给定一组拍照人,请编写程序输出他们的队形。

输入格式:

每个输入包含1个测试用例。每个测试用例第1行给出两个正整数N(<=10000,总人数)和K(<=10,总排数)。随后N行,每行给出一个人的名字(不包含空格、长度不超过8个英文字母)和身高([30, 300]区间内的整数)。

输出格式:

输出拍照的队形。即K排人名,其间以空格分隔,行末不得有多余空格。注意:假设你面对拍照者,后排的人输出在上方,前排输出在下方。

输入样例:

输出样例:

PAT-A-1109-Group Photo 的中文版。

代码如下:

继续阅读

本题的基本要求非常简单:给定N个实数,计算它们的平均值。但复杂的是有些输入数据可能是非法的。一个“合法”的输入是[-1000,1000]区间内的实数,并且最多精确到小数点后2位。当你计算平均值的时候,不能把那些非法的数据算在内。

输入格式:

输入第一行给出正整数N(<=100)。随后一行给出N个正整数,数字间以一个空格分隔。

输出格式:

对每个非法输入,在一行中输出“ERROR: X is not a legal number”,其中X是输入。最后在一行中输出结果:“The average of K numbers is Y”,其中K是合法输入的个数,Y是它们的平均值,精确到小数点后2位。如果平均值无法计算,则用“Undefined”替换Y。如果K为1,则输出“The average of 1 number is Y”。

输入样例1:

输出样例1:

输入样例2:

输出样例2:

PAT-A-1108. FINDING AVERAGE 的中文版

这道题需要注意的是最多精确到 2 位,同时只有 0 个或 1 个合法数字时的输出。(似乎和测试点 3 有关

In case the average cannot be calculated, output “Undefined” instead of Y. In case K is only 1, output “The average of 1 number is Y” instead.

其他的就没有什么问题,就是发现自己的思路好不清晰,写第一遍时没有 AC ,然后偷懒直接 sscanf 反而过了……

本来打算写一个基于正则表达式的,但不知 regex.h 能不能用,回来有空尝试一下。

代码如下:

继续阅读

在不打扰居民的前提下,统计住房空置率的一种方法是根据每户用电量的连续变化规律进行判断。判断方法如下:

  • 在观察期内,若存在超过一半的日子用电量低于某给定的阈值e,则该住房为“可能空置”;
  • 若观察期超过某给定阈值D天,且满足上一个条件,则该住房为“空置”。

现给定某居民区的住户用电量数据,请你统计“可能空置”的比率和“空置”比率,即以上两种状态的住房占居民区住房总套数的百分比。

输入格式:

输入第一行给出正整数N(<=1000),为居民区住房总套数;正实数e,即低电量阈值;正整数D,即观察期阈值。随后N行,每行按以下格式给出一套住房的用电量数据:

K E1 E2 … EK

其中K为观察的天数,Ei为第i天的用电量。

输出格式:

在一行中输出“可能空置”的比率和“空置”比率的百分比值,其间以一个空格分隔,保留小数点后1位。

输入样例:

输出样例:

(样例解释:第2、3户为“可能空置”,第4户为“空置”,其他户不是空置。)

水题一道,“可能空置”与“空置”互斥,看题时没注意到……看数据才发现。

代码如下:

继续阅读

萌萌哒表情符号通常由“手”、“眼”、“口”三个主要部分组成。简单起见,我们假设一个表情符号是按下列格式输出的:

现给出可选用的符号集合,请你按用户的要求输出表情。

输入格式:

输入首先在前三行顺序对应给出手、眼、口的可选符号集。每个符号括在一对方括号[]内。题目保证每个集合都至少有一个符号,并不超过10个符号;每个符号包含1到4个非空字符。

之后一行给出一个正整数K,为用户请求的个数。随后K行,每行给出一个用户的符号选择,顺序为左手、左眼、口、右眼、右手——这里只给出符号在相应集合中的序号(从1开始),数字间以空格分隔。

输出格式:

对每个用户请求,在一行中输出生成的表情。若用户选择的序号不存在,则输出“Are you kidding me? @\/@”。

输入样例:

输出样例:

这道题,也有坑……

之后一行给出一个正整数K,为用户请求的个数。随后K行,每行给出一个用户的符号选择,顺序为左手、左眼、口、右眼、右手——这里只给出符号在相应集合中的序号(从1开始),数字间以空格分隔。

从 1 开始,但是测试数据被没有被限制在该范围内,所以应过滤输入,第 1 2 测试点就针对是这种情况吧。

代码如下:

继续阅读