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

(2/500)打印出和为0的所有子数组

给定一个整型数组，请打印出元素和为0的所有子数组。
例如，
输入:
{ 4, 2, -3, -1, 0, 4 }
输出:
Sub-arrays with 0 sum are
{ -3, -1, 0, 4 }
{ 0 }

输入:
{ 3, 4, -7, 3, 1, 3, 1, -4, -2, -2 }
输出:
Sub-arrays with 0 sum are
{ 3, 4, -7 }
{ 4, -7, 3 }
{ -7, 3, 1, 3 }
{ 3, 1, -4 }
{ 3, 1, 3, 1, -4, -2, -2 }
{ 3, 4, -7, 3, 1, 3, 1, -4, -2, -2 }

1. 傻瓜式方法

傻瓜式方法的想法很简单，遍历数组的所有子数组，并计算它们的和。如果子数组的和等于0，那么就打印它。它的时间复杂度是 O(n3)，因为一共有 n(n+1)/2(注：原文n2不对)个子数组，花费的时间是O(n2)，然后还要花费 O(n)的时间求元素的和。当然，如果在找子数组的同时计算元素的和，那么这种方法可以优化成O(n2)时间。

C++语言实现：

#include <iostream>
#include <unordered_map>
using namespace std;
 
// Function to print all sub-arrays with 0 sum present
// in the given array
void printallSubarrays(int arr[], int n)
{
    // consider all sub-arrays starting from i
    for (int i = 0; i < n; i++)
    {
        int sum = 0;
 
        // consider all sub-arrays ending at j
        for (int j = i; j < n; j++)
        {
            // sum of elements so far
            sum += arr&#91;j&#93;;
 
            // if sum is seen before, we have found a sub-array 
            // with 0 sum
            if (sum == 0)
                cout << "Subarray &#91;" << i << ".." << j << "&#93;\n";
        }
    }
}
 
// main function
int main()
{
    int arr&#91;&#93; = { 3, 4, -7, 3, 1, 3, 1, -4, -2, -2 };
    int n = sizeof(arr)/sizeof(arr&#91;0&#93;);
 
    printallSubarrays(arr, n);
 
    return 0;
}
&#91;/cpp&#93;


Java语言实现：
&#91;java&#93;class PrintallSubarrays
{
    // Function to print all sub-arrays with 0 sum present
    // in the given array
    public static void printallSubarrays(int arr&#91;&#93;)
    {
        // n is length of the array
        int n = arr.length;
 
        // consider all sub-arrays starting from i
        for (int i = 0; i < n; i++)
        {
            int sum = 0;
     
            // consider all sub-arrays ending at j
            for (int j = i; j < n; j++)
            {
                // sum of elements so far
                sum += arr&#91;j&#93;;
     
                // if sum is seen before, we have found a sub-array with 0 sum
                if (sum == 0)
                    System.out.println("Subarray &#91;" + i + ".." + j + "&#93;");
            }
        }
    }
 
    // main function
    public static void main (String&#91;&#93; args)
    {
        int arr&#91;&#93; = { 3, 4, -7, 3, 1, 3, 1, -4, -2, -2 }; 
        printallSubarrays(arr);
    }
}&#91;/java&#93;

<strong>输出：</strong><span style="font-family: consolas; font-size: small;">
Subarray [0..2]
Subarray [0..9]
Subarray [1..3]
Subarray [2..5]
Subarray [3..9]
Subarray [5..7]</span>

<br>
<div style="background-color: #99CCFF; height: 1px;"></div>
<h3>2. 使用map打印子数组</h3>
我们可以使用map打印所有和为0的子数组，子数组信息存放在另外的数组中并作为map的value。开始，我们创建一个空map存放所有和等于给定值的子数组的的结束下标。其中，key是和，value就是之前提到的另外一个数组，此数组中存放的就是和等于key的所有子数组的结束下标。我们遍历给定数组，在遍历程中维护目前所遍历过的元素的和。如果元素的和在之前见过，那就意味着至少存在一个子数组和为0，子数组的结束下标就是当前遍历的下标，这样我们就能打印出所有的子数组。

C++语言实现：
[cpp]
#include <iostream>
#include <unordered_map>
using namespace std;
 
// Function to print all sub-arrays with 0 sum present
// in the given array
void printallSubarrays(int arr[], int n)
{
    // create an empty multi-map to store ending index of all
    // sub-arrays having same sum
    unordered_multimap<int, int> map;
 
    // insert (0, -1) pair into the map to handle the case when
    // sub-array with 0 sum starts from index 0
    map.insert(pair<int, int>(0, -1));
 
    int sum = 0;
    
    // traverse the given array
    for (int i = 0; i < n; i++)
    {
        // sum of elements so far
        sum += arr&#91;i&#93;;
 
        // if sum is seen before, there exists at-least one 
        // sub-array with 0 sum
        if (map.find(sum) != map.end())
        {
            auto it = map.find(sum);
 
            // find all sub-arrays with same sum
            while (it != map.end() && it->first == sum)
            {
                cout << "Subarray &#91;" << (it->second + 1) << ".." << i << "&#93;\n";
                it++;
            }
        }
 
        // insert (sum so far, current index) pair into multi-map
        map.insert(pair<int, int>(sum, i));
    }
}
 
// main function
int main()
{
    int arr[] = { 3, 4, -7, 3, 1, 3, 1, -4, -2, -2 };
    int n = sizeof(arr)/sizeof(arr[0]); 
    printallSubarrays(arr, n); 
    return 0;
}

java语言实现：

import java.util.HashMap;
import java.util.Map;
import java.util.ArrayList;
 
class PrintallSubarrays
{
    // Utility function to insert <key, value> into the Multimap
    private static void insert(Map<Integer, ArrayList> hashMap, 
                                Integer key, Integer value) 
    {
        // if key is already present
        if (hashMap.containsKey(key))
        {
            hashMap.get(key).add(value);
        }else
        // key is seen for the first time
        {
            ArrayList<Integer> list = new ArrayList<Integer>();
            list.add(value); 
            hashMap.put(key, list);
        }
    }
 
    // Function to print all sub-arrays with 0 sum present
    // in the given array
    public static void printallSubarrays(int arr[])
    {
        // n is length of the array
        int n = arr.length;
        
        // create an empty Multi-map to store ending index of all
        // sub-arrays having same sum
        Map<Integer, ArrayList> hashMap = new 
                                    HashMap<Integer, ArrayList>();
 
        // insert (0, -1) pair into the map to handle the case when
        // sub-array with 0 sum starts from index 0
        insert(hashMap, 0, -1);
     
        int sum = 0;
        
        // traverse the given array
        for (int i = 0; i < n; i++)
        {
            // sum of elements so far
            sum += arr&#91;i&#93;;
     
            // if sum is seen before, there exists at-least one 
            // sub-array with 0 sum
            if (hashMap.containsKey(sum))
            {
                ArrayList<Integer> list = hashMap.get(sum);
 
                // find all sub-arrays with same sum
                for (Integer value: list) {
                    System.out.println("Subarray [" + (value + 1) + ".." +  i + "]");
                }
            }
 
            // insert (sum so far, current index) pair into the Multi-map
            insert(hashMap, sum, i);
        }
    }
 
    // main function
    public static void main (String[] args)
    {
        int A[] = { 3, 4, -7, 3, 1, 3, 1, -4, -2, -2 }; 
        printallSubarrays(A);
    }
}

输出:
Subarray [0..2]
Subarray [1..3]
Subarray [2..5]
Subarray [5..7]
Subarray [3..9]
Subarray [0..9]

这样，只需遍历一次数组就能求出所有的子数组。

练习： 打印出和为非0的所有子数组。

2017年05月08日   06:55:06 阅读全文 评论(0)

(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)。


 


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



    

 2017年05月05日   22:13:21    
    阅读全文
      

	评论(0)
 




   

     

     

    	
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



    

 2014年04月17日   23:33:10    
    阅读全文
      

	评论(1)
 




   

     

     

    	
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



    

 2014年04月14日   21:20:34    
    阅读全文
      

	评论(0)
 




   

  
  

   
« 上一页