本站首页 返回顶部 关于博主

(1/500)找出和等于给定值的两个数

给定一个整型数组,数组未排序,请找出一对数,使这两个数的和等于一个给定的值。
例如,
输入:

arr = [8, 7, 2, 5, 3, 1]
sum = 10

输出:
Pair found at index 0 and 2 (8 + 2)

Pair found at index 1 and 4 (7 + 3)

 

1. 傻瓜式方法

傻瓜式方法比较粗暴,通过遍历给定数组中的所有两个数字组成的组合,只要发现一个组合的和等于期望中的数字,就返回它们。

C语言实现:


#include

// Naive method to find a pair in an array with given sum
void findPair(int arr[], int n, int sum)
{
// consider each element except last element
for (int i = 0; i < n - 1; i++) { // start from i'th element till last element for (int j = i + 1; j < n; j++) { // if desired sum is found, print it and return if (arr[i] + arr[j] == sum) { printf("Pair found at index %d and %d", i, j); return; } } } // No pair with given sum exists in the array printf("Pair not found"); } // main function int main() { int arr[] = { 8, 7, 2, 5, 3, 1 }; int sum = 10; int n = sizeof(arr)/sizeof(arr[0]); findPair(arr, n, sum); return 0; } [/c] 下载代码 运行代码

Java语言实现:


class FindPair
{
// Naive method to find a pair in an array with given sum
public static void findPair(int arr[], int sum)
{
// n is length of the array
int n = arr.length;

// consider each element except last element
for (int i = 0; i < n - 1; i++) { // start from i'th element till last element for (int j = i + 1; j < n; j++) { // if desired sum is found, print it and return if (arr[i] + arr[j] == sum) { System.out.println("Pair found at index " + i + " and " + j); return; } } } // No pair with given sum exists in the array System.out.println("Pair not found"); } // main function public static void main (String[] args) { int arr[] = { 8, 7, 2, 5, 3, 1 }; int sum = 10; findPair(arr, sum); } } [/java] 下载代码 运行代码

输出:
Pair found at index 0 and 2

这种解决方案的时间复杂度是 O(n2),空间复杂度是 O(1)

 

2. 使用排序复杂度为O(nlogn)的方法

这种方法的观点是,先对数组进行排序,然后通过两个索引index(高high和低low)来进行搜索。在初始状态时,这两个索引index分别指向数组的首尾(假设数组长度为n,low指向第0个元素,high指向第n-1个元素)。然后我们不断地逼近low和high的值来搜索数组arr[low…high],直到low大于或等于high。在这个过程中,我们计算arr[high]与arr[low]之和,并与给定的数字比较,如果和小于给定数字,就增加low的值,反之则减少high的值。最后,如果在数组中找到了这一对数字,返回它们即可。

C++语言实现:


#include

// Function to find a pair in an array with given sum using Sorting
void findPair(int arr[], int n, int sum)
{
// sort the array in ascending order
std::sort(arr, arr + n);

// maintain two indexes pointing to end-points of the array
int low = 0;
int high = n – 1;

// reduce search space arr[low..high] at each iteration of the loop

// loop till low is less than high
while (low < high) { // sum found if (arr[low] + arr[high] == sum) { std::cout << "Pair found"; return; } // increment low index if total is less than the desired sum // decrement high index is total is more than the sum (arr[low] + arr[high] < sum)? low++: high--; } // No pair with given sum exists in the array std::cout << "Pair not found"; } // main function int main() { int arr[] = { 8, 7, 2, 5, 3, 1}; int sum = 10; int n = sizeof(arr)/sizeof(arr[0]); findPair(arr, n, sum); return 0; } [/cpp] 下载代码 运行代码

java语言实现:


import java.util.Arrays;

class FindPair
{
// Naive method to find a pair in an array with given sum
public static void findPair(int arr[], int sum)
{
// sort the array in ascending order
Arrays.sort(arr);

// maintain two indexes pointing to end-points of the array
int low = 0;
int high = arr.length – 1;

// reduce search space arr[low..high] at each iteration of the loop

// loop till low is less than high
while (low < high) { // sum found if (arr[low] + arr[high] == sum) { System.out.println("Pair found"); return; } // increment low index if total is less than the desired sum // decrement high index is total is more than the sum if (arr[low] + arr[high] < sum) low++; else high--; } // No pair with given sum exists in the array System.out.println("Pair not found"); } // main function public static void main (String[] args) { int arr[] = { 8, 7, 2, 5, 3, 1 }; int sum = 10; findPair(arr, sum); } } [/java] 下载代码 运行代码

输出:
Pair found

这种解决方案的时间复杂度是 O(nlogn),空间复杂度是 O(1)。

 

3. 使用Map复杂度为O(n)的方法

其实,我们可以在线性的时间内解决问题,解决方案的关键在于使用map。算法就是把数组中的元素arr[i]插入到map中。在遍历数组过程中,我们需要查找sum – arr[i]是否在数组中。如果能找到,就打印出arr[i]和sum-array[i],返回。

C++语言实现:


#include
using namespace std;

// Function to find a pair in an array with given sum using Hashing
void findPair(int arr[], int n, int sum)
{
// create an empty map
unordered_map map;

// do for each element
for (int i = 0; i < n; i++) { // check if pair (arr[i], sum-arr[i]) exists // if difference is seen before, print the pair if (map.find(sum - arr[i]) != map.end()) { cout << "Pair found at index " << map[sum - arr[i]] << " and " << i; return; } // store index of current element in the map map[arr[i]] = i; } // we reach here if pair is not found cout << "Pair not found"; } // main function int main() { int arr[] = { 8, 7, 2, 5, 3, 1}; int sum = 10; int n = sizeof(arr)/sizeof(arr[0]); findPair(arr, n, sum); return 0; } [/cpp] 下载代码 运行代码

java语言实现:


import java.util.HashMap;
import java.util.Map;

class FindPair
{
// Naive method to find a pair in an array with given sum
public static void findPair(int arr[], int sum)
{
// create an empty Hash Map
Map map = new HashMap();

// do for each element
for (int i = 0; i < arr.length; i++) { // check if pair (arr[i], sum-arr[i]) exists // if difference is seen before, print the pair if (map.containsKey(sum - arr[i])) { System.out.println("Pair found at index " + map.get(sum - arr[i]) + " and " + i); return; } // store index of current element in the map map.put(arr[i], i); } // No pair with given sum exists in the array System.out.println("Pair not found"); } // main function public static void main (String[] args) { int arr[] = { 8, 7, 2, 5, 3, 1 }; int sum = 10; findPair(arr, sum); } } [/java] 下载代码 运行代码

输出:
Pair found at index 0 and 2

这种方案的时间复杂度和空间复杂度都是O(n)。

 

练习: 打印出数组中所有和等于给定值的数字对。

Problem B. Cookie Clicker Alpha解答

这题的小数据8分,大数据11分,共19分。
 
在分析解题思路之前,我们先看一下题目中的例子。
假设方案一从来都不买form,那就意味着产生cookie的速率一直都是2个/秒;按照方案二,当买了第一个form之后,速率由2个/秒增加到了6个/秒,买了第n个form之后,速率变成(2+4n)个/秒。
如果以时间为横轴,cookie的数目为纵轴,那么时间和cookie的关系如下图。

Cookie数目和时间关系图

从上图中,我们可以看出,第一种方案需要1000秒,第二种方案需要500多秒。
从折现的斜率来看,买的form数目越多,产生cookie的速度越快。但每当买一个form之后,虽然速率增加了,但是cookie的数目马上就减少了。同不买form的那种方案相比,需要一定的时间才能赶上它。
也就是说,我们应当尽量地多买form才能保证多产cookie,但form的数目存在一个临界值,当form的数目多余这个数字时,我们不必买form就能更快地达到要求的cookie数目X。
 
那这个form数目的临界值是多少呢?
 
当第一次达到500个cookie时,假设此时的时刻为0,如果不买form,那么再过t秒,cookie数目为 500 + 2t。如买一个form,那么在t时刻的form数目为(2+4)t,也就是6t,那么方案二追上方案一随需的时间是多少呢? 500 + 2t >= 6t,得出t>=125,也就是说,在125秒之前,方案二中cookie的数目小于方案一的数目,这个临界数目是500 + 2t = 750。当产生cookie的数目小于750时,方案一更快,大于750时,方案二更快。
在当前例子中,X的数目为2000,大于750,所以应该采取方案二。
 
继续产生cookie,当cookie数达到500时,假设我们目前已经有了n个form,如果不买form,再过t秒的cookie数目为500 + (4n+2)t,如果买form,那么再过t秒,cookie数为 (4n+2)t + 4t。我们可以算出,t恒为125,也就是说如果500 + (4n + 2) * 125>=2000,那么应该采用方案一,否则采用方案二。
我们算出n>= 2.5,取整之后form的数目n>=3。
把C,F,X放到公式里,那就是  ( 2 + nF) * C/F  >=  X – C,然后得到 n的值是 X / C – 1 – 2 / F。那么算上买n次form的时间,加上最后一次的时间 X / ( 2 + n * F ),就是我们所需的结果了。
时间复杂度o(1)。
 
源代码:CookieClicker.java

Problem A. Magic Trick解答

原题链接:Problem A. Magic Trick

这一题6分,题目要求可简化如下:
前提条件:
1. 给定A和B两个4 x 4 的矩阵,两个矩阵中都填充了1 ~ 16这16个数字(每个矩阵中的数字都唯一)。
2. 取出矩阵A中指定某一行的4个数字;
3 .取出矩阵B中指定某一行(可能与第2步中行数相同)的4个数字。
要求:
判断步骤2中的数字与步骤3中的数字是否包含相同的数字。如果有且只有一个相同数字,那么输出这个相同的数字;如果没有相同的数字,则输出“Volunteer cheated!“;如果相同的数字个数大于或等于2,则输出“Bad magician!”。

解答:
把两组数字分别放到两个数组中,逐个比较这两个数组,然后把相同的数字放到一个list中,最后判断list.size()即可。函数实现如下

private List processTrickPair( String[] values1, String[] values2)
{
List ret = new ArrayList();
for( int i = 0; i < values1.length; i ++ ) { for( int j = 0; j < values2.length; j ++ ) { if( values1[i].equals( values2[j])) { ret.add( values1[i] ); } } } return ret; } [/java]

源代码下载:MagicTrick.java

Google Code Jam 2014资格赛题目解答

周六闲来无事,正好碰上Google Code Jam 2014的资格赛,于是就尝试着做了做比赛的题目,权当练习一下好久没有动过的脑子。
这两天准备陆续地把自己的答案整理出来。

1.Problem A. Magic Trick
2.Problem B. Cookie Clicker Alpha
3.Problem C. Minesweeper Master
4.Problem D. Deceitful War