找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 6577|回复: 6
收起左侧

[米群网刷题小分队] [LintCode] Subarray Sum

[复制链接]

75

主题

6

精华

536

积分

超级会员

Rank: 4

积分
536
发表于 12-12-2014 09:30 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x

Given an integer array, find a subarray where the sum of numbers iszero. Your code should return the index of the first number and the index ofthe last number. Example, given [-3, 1, 2, -3, 4], return [0, 2] or [1, 3].

Solution: The idea is based on the prefix sum: Iterate through the array and for every element array【i】, calculate sum of elements form 0 to i (this can simply be done as sum += arr【i】). If the current sum has been seen before, then there is a zero sum array, the start and end index are returned.

Note, the capacity of the hash table should be set to reduce the memory usage.

public class Solution {
    /**
     * @param nums: A list of integers
     * @return: A list of integers includes the index of the first number
     *          and the index of the last number
     */
    public ArrayList<Integer> subarraySum(int[] nums) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>(nums.length); // <prefix sum, index>
        ArrayList<Integer> indexes = new ArrayList<Integer>(2);
        int sum = 0;
        map.put(0, -1);  // The subarray starts for the first element
        for (int i = 0; i < nums.length; ++i) {
            sum += nums【i】;
            if (map.containsKey(sum)) {
                indexes.add(map.get(sum) + 1);
                indexes.add(i);
                break;
            }
            map.put(sum, i);
        }
        return indexes;
    }
}

本帖被以下淘专辑推荐:

75

主题

6

精华

536

积分

超级会员

Rank: 4

积分
536
 楼主| 发表于 12-12-2014 09:39 PM | 显示全部楼层

[LintCode] Subarray Sum Closest


Subarray Sum Closest

Given an integer array, find a subarray with sum closest to zero.Return the indexes of the first number and last number. Example, given [-3, 1,1, -3, 5], return [0, 2] or [1, 3].
Challenge: O(nlogn) time


Solution: Calculate the prefix sum arrays[], where s【i】 = nums[0]+nums[1]+...+nums【i】. And then sort this s with its original index, tofind subarray sum closest to 0, just iterate the s array and do the diff of the twoneighboring values and update the minimum absolute diff.


  
public class Solution {
  
    private static  class Element implements Comparable<Element> {
  
         private int value;
  
         private int index;
  
        public  Element(int sum, int i) {
  
             value = sum;
  
             index = i;
  
        }
  
        public  int compareTo(Element e){
  
            return this.value - e.value;
  
        }
  
        public  int getValue() {
  
             return value;
  
        }
  
        public  int getIndex() {
  
             return index;
  
        }
  
    }
  
  
    /**
  
     * @param  nums: A list of integers
  
     *  @return: A list of integers includes the index of the first number
  
     *          and the index of the last number
  
     */
  
    public  ArrayList<Integer> subarraySumClosest(int[] nums) {
  
        Element[]  sums = new Element[nums.length + 1]; // prefix sums with index
  
        int  sum = 0;
  
         sums[0] = new Element(0, -1); // for the possible start index from 0
  
        for  (int i = 0; i < nums.length; ++i) {
  
             sum += nums【i】;
  
            sums[i + 1] = new Element(sum, i);
  
        }
  
         Arrays.sort(sums);
  
         ArrayList<Integer> indexes = new ArrayList<Integer>(2);
  
        int  minDiff = Integer.MAX_VALUE;
  
        int  startIndex = 0;
  
        int  endIndex = 0;;
  
        for  (int i = 1; i < sums.length; ++i) {
  
            if  (Math.abs(sums【i】.getValue() - sums[i - 1].getValue()) < minDiff) {
  
                 minDiff = Math.abs(sums【i】.getValue() - sums[i - 1].getValue());
  
                 startIndex = Math.min(sums【i】.getIndex(), sums[i - 1].getIndex()) + 1;
  
                 endIndex = Math.max(sums【i】.getIndex(), sums[i - 1].getIndex());
  
            }
  
        }
  
         indexes.add(startIndex);
  
         indexes.add(endIndex);
  
        return  indexes;
  
    }
  
}
  

回复 支持 反对

使用道具 举报

75

主题

6

精华

536

积分

超级会员

Rank: 4

积分
536
 楼主| 发表于 12-13-2014 10:49 PM | 显示全部楼层

[LintCode] Majority Number III

Majority Number III

Given anarray of integers and a number k, the majority number is the number that occursmore than 1/k of the size of the array. Find it. Note, there is only onemajority number in the array.  Example, for[3,1,2,3,2,3,3,4,4,4] and k = 3, return 3.

Solution: the basic idea is to reduce the k different numbers at the same time, which will not affect the "majority" feature.

  1. public class Solution {
  2.     /**
  3.      * @param nums: A list of integers
  4.      * @param k: As described
  5.      * @return: The majority number
  6.      */
  7.     public int majorityNumber(ArrayList<Integer> nums, int k) {
  8.         Map<Integer, Integer> map = new HashMap<Integer, Integer>();  // <num, counter>
  9.         for (Integer num : nums) {
  10.             if (map.containsKey(num)) {
  11.                 map.put(num, map.get(num) + 1);
  12.             } else {
  13.                 if (map.size() == k) {  // decrease each element value and remove entries with 0.
  14.                     Iterator<Map.Entry<Integer, Integer>> iter = map.entrySet().iterator();
  15.                     while (iter.hasNext()) {
  16.                         Map.Entry<Integer, Integer> entry = iter.next();
  17.                         if (entry.getValue() - 1 == 0) {
  18.                             iter.remove();
  19.                         } else {
  20.                             map.put(entry.getKey(), entry.getValue() - 1);
  21.                         }
  22.                     }
  23.                 } else {
  24.                     map.put(num, 1);
  25.                 }
  26.             }
  27.         }
  28.         int max = 0;
  29.         int result = 0;
  30.         for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
  31.             if (entry.getValue() > max) {
  32.                 max = entry.getValue();
  33.                 result = entry.getKey();
  34.             }
  35.         }
  36.         return result;
  37.     }
  38. }
复制代码


回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表