树状数组&查找&深度优先 2016-7-20

[SnackMen]

307. Range Sum Query - Mutable 35. Search Insert Position 39. Combination Sum 讲解：树状数组

[wolfogre]

参考维基百科－树状数组

// AC 307. Range Sum Query - Mutable
/**
 * @constructor
 * @param {number[]} nums
 */
var NumArray = function(nums) {
    this.bits = new Array(nums.length + 1);
    this.numbers = new Array(nums.length + 1);
    for (var i = 1; i <= nums.length; ++i)
    {
        this.bits[i] = this.numbers[i] = nums[i - 1];
        for (var j = i - 1; j > i - this.lowbit(i); --j)
            this.bits[i] += nums[j - 1];
    }
};

/**
 * @param {number} x
 * @return {number}
 */
NumArray.prototype.lowbit = function(x){
    return x & (-x);
}

/**
 * @param {number} i
 * @param {number} val
 * @return {void}
 */
NumArray.prototype.update = function(i, val) {
    var delta = val - this.numbers[i + 1];
    this.numbers[i + 1] = val;
    for (var j = i + 1; j <= this.numbers.length; j += this.lowbit(j))
        this.bits[j] += delta;
};

/**
 * @param {number} i
 * @param {number} j
 * @return {number}
 */
NumArray.prototype.sumRange = function(i, j) {
    return this.sum(j + 1) - this.sum(i);
};

/**
 * @param {number} k
 * @return {number}
 */
NumArray.prototype.sum = function(k){
    var ans = 0;
    for (var i = k; i > 0; i -= this.lowbit(i))
        ans += this.bits[i];
    return ans;
}

/**
 * Your NumArray object will be instantiated and called as such:
 * var numArray = new NumArray(nums);
 * numArray.sumRange(0, 1);
 * numArray.update(1, 10);
 * numArray.sumRange(0, 2);
 */

[dayang]

/**
 * [AC] LeetCode 35  Search Insert Position  二分法
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function(nums, target) {
    var low = 0, high = nums.length - 1;
    var mid;
    while(low <= high){
        mid = (low + high) >>> 1;
        if(target === nums[mid])
            return mid;
        if(target > nums[mid])
            low = mid + 1;
        else
            high = mid - 1;
    }
    if(target < nums[mid])
        return mid;
    else
        return mid + 1;
};

[SnackMen]

/* 307. Range Sum Query - Mutable
Time Limit Exceeded 
*/
public class NumArray {
    public int []sums;
    public int []nums;
    public NumArray(int[] nums) {
        this.nums=nums;
        if(nums==null)
            sums=null;
        else if(nums.length==0)
            sums=new int[0];
        else{
            sums = new int[nums.length];
            sums[0]=nums[0];
            for(int i=1;i<nums.length;i++){
                sums[i]=sums[i-1]+nums[i];
            }
        }
    }

    void update(int i, int val) {
        int len =val- nums[i];
        sums[i]=sums[i]-nums[i]+val;
        nums[i]=val;
        if(nums!=null){
            for(int j=i+1;j<nums.length;j++){
                sums[j]+=len;
            }
        }
    }

    public int sumRange(int i, int j) {
        if(i>j || i<0 || j<0 || j>=sums.length) 
            return 0;  
        return i==0 ? sums[j] : (sums[j] - sums[i-1]);
    }
}

// Your NumArray object will be instantiated and called as such:
// NumArray numArray = new NumArray(nums);
// numArray.sumRange(0, 1);
// numArray.update(1, 10);
// numArray.sumRange(1, 2);

/*AC 307. Range Sum Query - Mutable*/
public class NumArray {
    public int []sums;
    public int []num;

    public NumArray(int[] nums) {
        if(nums==null)
            sums=null;
        else if(nums.length==0)
            sums=new int[0];
        else{
            num=new int[nums.length+1];
            sums=new int[nums.length+1];
           for(int i=0;i<nums.length;++i){

               for(int j=i+1;j<=nums.length;j+=(j&-j)){
                   sums[j]+=nums[i];
               }
               num[i+1]=nums[i];
           }
        }
    }

    void update(int i, int val) {
        int len = val-num[i+1];
        if(num!=null){
            for(int j=i+1;j<num.length;j+=(j&-j)){
                sums[j]+=len;
            }
        }
        num[i+1]=val;
    }

    public int sumRange(int i, int j) {
       return getSum(j+1)-getSum(i);
    }

    public int getSum(int i){
        int res=0;
        for(int j=i;j>0;j-=(j&-j)){
            res+=sums[j];
        }
        return res;
    }
}

// Your NumArray object will be instantiated and called as such:
// NumArray numArray = new NumArray(nums);
// numArray.sumRange(0, 1);
// numArray.update(1, 10);
// numArray.sumRange(1, 2);

[dayang]

/**
 * [AC] LeetCode 307 Range Sum Query - Mutable  树状数组
 * @constructor
 * @param {number[]} nums
 */
var NumArray = function (nums) {
    this.arr = nums;
    this.tree = [0];
    for (var i = 0; i < nums.length; i++)
        this.tree.push(0);
    for (i = 0; i < nums.length; i++) {
        var index = i + 1;
        while (index <= this.arr.length) {
            this.tree[index] += nums[i];
            index += index & (-index);
        }
    }
    this.readSum = function (i) {
        var res = 0, index = i + 1;
        while (index > 0) {
            res += this.tree[index];
            index -= index & (-index);
        }
        return res;
    }
};

/**
 * @param {number} i
 * @param {number} val
 * @return {void}
 */
NumArray.prototype.update = function (i, val) {
    var diff = val - this.arr[i];
    this.arr[i] = val;
    var index = i + 1;
    while (index <= this.arr.length) {
        this.tree[index] += diff;
        index += index & (-index);
    }
};

/**
 * @param {number} i
 * @param {number} j
 * @return {number}
 */
NumArray.prototype.sumRange = function (i, j) {
    return this.readSum(j) - this.readSum(i-1);
};

/**
 * Your NumArray object will be instantiated and called as such:
 * var numArray = new NumArray(nums);
 * numArray.sumRange(0, 1);
 * numArray.update(1, 10);
 * numArray.sumRange(0, 2);
 */

[SnackMen]

/*
[AC] LeetCode 35  Search Insert Position  二分法
*/
public class Solution {
    public int searchInsert(int[] nums, int target) {
        if(nums.length == 0 || nums == null) 
            return 0;
        int low=0;
        int heigh=nums.length-1;
        while(low<=heigh){
            if(low==heigh){
                if(nums[low]==target)
                    return low;
                else
                    break;
            }
            int mid=(low+heigh)/2;
            if(target==nums[mid])
                return mid;
            if(target<nums[mid]){
                heigh=--mid;
            }else{
                low=++mid;
            }
        }
        if(target<nums[low])
            return low;
        else
            return low+1;

    }
}

/*
[Time Limit Exceeded] LeetCode 35  Search Insert Position  二分法
*/
public class Solution {
    public int searchInsert(int[] nums, int target) {
        if(nums.length == 0 || nums == null) 
            return 0;
        int low=0;
        int heigh=nums.length-1;
        while(low<=heigh){
            if(low==heigh){
                if(nums[low]==target)
                    return low;
                else
                    break;
            }
            int mid=(low+heigh)/2;
            if(target==nums[mid])
                return mid;
            if(target<nums[mid]){
                heigh=mid--;
            }else{
                low=mid++;
            }
        }
        if(target<nums[low])
            return low;
        else
            return low+1;

    }
}

[zhaokuohaha]

307 - 树状数组 - C

public class NumArray
{
    int[] _nums;//原数组, 保留每一位的置
    int[] _arrTree;//树状数组
    //构造
    public NumArray(int[] nums)
    {
        _nums = new int[nums.Length + 1];
        _arrTree = new int[nums.Length+1];
        for(int i = 1; i<=nums.Length; i++)
        {
            _nums[i] = nums[i - 1];
            Add(i,_nums[i]);
        } 
    }

    //对原数组_nums[i]加上x, 树状数组相应很多位置加上x
    private void Add(int i,int x)
    {
        while(i < _arrTree.Length)
        {
            _arrTree[i] += x;
            i += lowbit(i);
        }
    }

    //i的二进制最低位1
    private int lowbit(int i)
    {
        return i & (-i);
    }

    //前n项和
    private int Sum(int i)
    {
        int sum = 0;
        while(i > 0)
        {
            sum += _arrTree[i];
            i -= lowbit(i);
        }
        return sum;
    }

    public void Update(int i, int val)
    {
        i++;
        Add(i, val - _nums[i]);//更新树状数组
        _nums[i] = val;//更新原数组
    }

    public int SumRange(int i, int j)
    {
        i++;
        j++;
        return Sum(j) - Sum(i - 1);
    }
}

[zhaokuohaha]

35 - 二分法 - C

public class Solution {
    public int SearchInsert(int[] nums, int target) {
        if(nums.Length == 0) return 0;
        int hgt = nums.Length-1;
        int low = 0;
        int mid = (hgt+low)/2;
        while(low < hgt-1){
            mid = (hgt+low)/2;
            if(nums[mid] == target){
                break;
            }
            if(nums[mid] < target){
                low = mid;
            }else{
                hgt = mid;
            }
        }
        if(nums[mid]==target) return mid;
        return nums[low] >= target ? low : nums[hgt] >= target ? hgt : hgt+1;
    }
}

[zhaokuohaha]

39 - 回溯法 - C

public class Solution
{
    public List<IList<int>> result;
    public List<int> combination;
    public int[] _candidates;
    public IList<IList<int>> CombinationSum(int[] candidates, int target)
    {
        result = new List<IList<int>>();
        combination = new List<int>();
        _candidates = candidates;
        Array.Sort(_candidates);
        combinate(0, target);
        return result;
    }

    public void combinate(int start, int target)
    {
        if (target == 0)
        {
            result.Add(new List<int>(combination));
            return;
        }

        for (int i = start; i < _candidates.Length && target >= _candidates[i]; i++)
        {
            combination.Add(_candidates[i]);
            combinate( i, target - _candidates[i]);
            combination.Remove(_candidates[i]);
        }
    }
}

多走一步 更好理解一点

public class Solution
{
    public List<IList<int>> result;
    public List<int> combination;
    public int[] _candidates;
    public IList<IList<int>> CombinationSum(int[] candidates, int target)
    {
        result = new List<IList<int>>();
        combination = new List<int>();
        _candidates = candidates;
        Array.Sort(_candidates);
        combinate(0, target);
        return result;
    }

    public void combinate(int start, int target)
    {
        if(target < 0) return;
        if (target == 0)
        {
            result.Add(new List<int>(combination));
            return;
        }

        for (int i = start; i < _candidates.Length; i++)
        {
            combination.Add(_candidates[i]);
            combinate( i, target - _candidates[i]);
            combination.Remove(_candidates[i]);
        }
    }
}