Eazow

Stay kind and positive

0%

Posted on In Reading time ≈ 1 mins.

How much of each year do spiders spend killing insects?

Why, you may wonder, should spiders be our friends? Because they destroy so many insects, and insects include some of the greatest enemies of the human race. Insects would make it impossible for us to live in the world; they would devour all our crops and kill our flocks and herds, if it were not for the protection we get from insect-eating animals. We owe a lot to the birds and beasts who eat insects but all of them put together kill only a fraction of the number destroyed by spiders. Moreover, unlike some of the other insect eaters, spiders never do the least harm to us or our belongings.

Spiders are not insects, as many people think, not even nearly related to them. One can tell the difference almost at a glance, for a spider always has eight legs and an insect never more than six.

How many spiders are engaged in this work on our behalf? One authority on spiders made a census of the spiders in a grass field in the south of England, and he estimated that there were more than 2,250,000 in one acre; that is something like 6,000,000 spiders of different kinds of a football pitch. Spiders are busy for at least half the year in killing insects. It is impossible to make more than the wildest guess at how many they kill, but they are hungry creatures, not content with only three meals a day. It has been estimated that the weight of all the insects destroyed by spiders in Britain in one year would be greater than the total weight of all the human beings in the country.

Posted on In Reading time ≈ 1 mins.

Why are legends handed down by storytellers useful?

We can read of things that happened 5,000 years ago in the Near East, where people first learned to write. But there are some parts of the world where even now people cannot write. The only way that they can preserve their history is to recount it as sagas—legends handed down from one generation of storyteller to another. These legends are useful because the can tell us something about migrations of people who lived long ago, but none could write down what they did. Anthropologist wondered where the remote ancestors of the Polynesian peoples now living in the Pacific Islands came from. The sagas of these people explain that some of them came from Indonesia about 2,000 years ago.

But the first people who were like ourselves lived so long ago that even their sagas, if they had any, are forgotten. So archaeologists have neither history nor legends to help them find out where the first “modern men” came from.

Fortunately, however, ancient men made tools of stone, especially flint, because this is easier to shape than other kinds. They may also have used wood and skins, but these have rotted away. Stone does not decay, and so the tools of lone ago have remained when even the bones of the men who made them have disappeared without trace.

Posted on In Reading time ≈ 1 mins.

Problem

Given a collection of integers that might contain duplicates, nums, return all possible subsets.
Note: The solution set must not contain duplicate subsets.
For example,
If nums = [1,2,2], a solution is:

1
2
3
4
5
6
7
8
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

方法

设定返回的列表的列表为result。先对数组排序，如果nums[i]!=nums[i-1]，那么就遍历result，复制每个列表为tempList，加入nums[i]，然后将该列表加入result中；如果nums[i]==nums[i-1]，那么记录下加入nums[i-1]前返回列表的大小resultIndex，resultSize为加入nums[i-1]后的大小，对result中从resultIndex至resultSize的列表加入nums[i]，然后将新生成的列表加入result

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution(object):
    def subsetsWithDup(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        result = [[]]
        nums.sort()
        i = 0
        resultSize = 0
        while i < len(nums):
            num = nums[i]
            resultIndex = 0
            if i>0 and nums[i]==nums[i-1]:
                resultIndex = resultSize;
            resultSize = len(result)
            while resultIndex < resultSize:
                tempList = result[resultIndex][:]
                tempList.append(num)
                result.append(tempList)
                resultIndex += 1
            i += 1
        return result

assert Solution().subsetsWithDup([1,2,2]) == [[],[1],[2],[1,2],[2,2],[1,2,2]]

Posted on Reading time ≈ 1 mins.

Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.

For example, given the range [5, 7], you should return 4.

方法

直接对所有数按位与，会超时，因此只能采用别的方法。
对于[1,3], 对应二进制位01,010,011，按位与为0；对于[5,7]，对应二进制为0101,0110,0111，按位与为0100。
对于[m,n]，如果m!=n，那么m和n最右一位按位与必然为0；同时将m,n都右移一位，用bits记录移位数，如果m!=n，继续将m,n右移一位。最后m==n时，将m<<bits位即可，此时m可以为0或为其他值。如果m为0，n也为0,那么m和n的位数并不相同，因此结果为0；如果m不为0，那么m和n前几位必然相同，用m<<bits就可以得到最后结果。

C代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <assert.h>

int rangeBitwiseAnd(int m, int n) {
    int bits = 0;
    while(m != n) {
        m >>= 1;
        n >>= 1;
        bits++;
    }
    return m<<bits;
}

/**
int rangeBitwiseAnd(int m, int n) {
    int bitwiseAnd = m;
    while(m <= n) {
        bitwiseAnd &= m;
        m++;
    }
    return bitwiseAnd;
}
*/

int main() {
    assert(rangeBitwiseAnd(5,7) == 4);
    assert(rangeBitwiseAnd(1,3) == 0);

    return 0;
}

Posted on Reading time ≈ 2 mins.

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

C代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <assert.h>
#include <stdlib.h>

/**
 * Return an array of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    int left = 0, right = numsSize-1;
    int* returnNums = NULL;
    int sum = 0;
    while(left < right) {
        sum = nums[left]+nums[right];
        if(sum == target) {
            returnNums = (int *)malloc(sizeof(int)*2);
            returnNums[0] = left+1;
            returnNums[1] = right+1;
            *returnSize = 2;
            break;
        }
        else if(sum > target)
            right--;
        else
            left++;
    }
    return returnNums;
}

/**
int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    int i = 0, j = i+1;
    int* returnNums = NULL;
    for(i=0, j=i+1; i < numsSize-1;) {
        if(nums[i] + nums[j] == target) {
            returnNums = (int *)malloc(sizeof(int) * 2);
            returnNums[0] = i+1;
            returnNums[1] = j+1;
            *returnSize = 2;
            return returnNums;
        }
        else if(nums[i] + nums[j] < target) {
            j++;
            if(j == numsSize) {
                i++;
                j = i+1;
            }
        }
        else {
            i++;
            j = i+1;
        }
    }
    return returnNums;
}
*/

int main() {
    int nums[3] = {2,3,4};
    int returnSize = 0;
    int* returnNums = twoSum(nums, 3, 6, &returnSize);
    assert(returnNums[0] == 1);
    assert(returnNums[1] == 3);

    return 0;
}

Posted on In Reading time ≈ 1 mins.

Problem

Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
The same repeated number may be chosen from C unlimited number of times.

Note:

  • All numbers (including target) will be positive integers.

  • The solution set must not contain duplicate combinations.
    For example, given candidate set [2, 3, 6, 7] and target 7,
    A solution set is:

    1
    2
    3
    4
    [
      [7],
      [2, 2, 3]
    ]

难度

Medium

思路

利用栈，如果要入栈的数加上已入栈的数的和小于target, 则入栈；如果等于target，则复制该栈，加入返回结果，然后从栈取出一个数，取其下一个数准备入栈；如果大于target, 则从栈取出一个数，取其下一个数准备入栈。注意一些边界条件的判断

Python代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution(object):
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type tatget: int
        :rtype List[List[int]]
        """
        nums = []
        indexes = []
        returnLists = []
        sum = 0
        i = 0
        candidates.sort()
        while True:
            while i >= len(candidates):
                if len(nums) == 0:
                    return returnLists
                sum -= nums.pop()
                i = indexes.pop()+1
            if sum + candidates[i] < target:
                nums.append(candidates[i])
                indexes.append(i)
                sum += candidates[i]
            elif sum + candidates[i] > target:
                if len(nums) > 0:
                    sum -= nums.pop()
                    i = indexes.pop()+1
                else:
                    return returnLists
            elif sum + candidates[i] == target:
                newNums = nums[:]
                newNums.append(candidates[i])
                returnLists.append(newNums)
                if len(nums) > 0:
                    sum -= nums.pop()
                    i = indexes.pop()+1
                else:
                    i += 1


assert Solution().combinationSum([2,3,4], 7)==[[2,2,3], [3,4]]
assert Solution().combinationSum([2,3,6,7], 7)==[[2,2,3], [7]]
assert Solution().combinationSum([2], 1) == []

Posted on Reading time ≈ 1 mins.

Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.

Example:

1
2
3
4
5
6
7
8
9
10
11
12
nums = [1, 2, 3]
target = 4
The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
Note that different sequences are counted as different combinations.
Therefore the output is 7.
思路

假设给定的nums为num1, num2...numn，用results[i]表示组成i的组合个数，如果i>=numj, 那么

1
results[i] = results[i-num1]+results[i-num2]+...results[i-numj]

从0开始计算至target，就能获得target的组合个数

C代码

里面递归的方法会超时，因此被注释掉

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <assert.h>
#include <stdlib.h>

/**
int combinationSum4(int* nums, int numsSize, int target) {
    if(target == 0)
        return 1;
    int i = 0;
    int result = 0;
    for(i = 0; i < numsSize; i++) {
        if(target >= nums[i])
            result += combinationSum4(nums, numsSize, target-nums[i]);
    }
    return result;
}
*/

int combinationSum4(int* nums, int numsSize, int target) {
    int* results = (int *)malloc(sizeof(int) * (target+1));
    int i = 0;
    int j = 0;
    results [0] = 1;
    for(i = 1; i <= target; i++)
        results[i] = 0;
    for(i = 0; i <= target; i++) {
        for(j = 0; j < numsSize; j++) {
            if(i >= nums[j])
                results[i] += results[i-nums[j]];
        }
    }
    return results[target];
}
int main() {
    int nums[3] = {1,2,3};
    assert(combinationSum4(nums, 3, 4) == 7);

    return 0;
}

Posted on Reading time ≈ 2 mins.

Given a binary tree, return the preorder traversal of its nodes’ values.

For example:
Given binary tree {1,#,2,3},

1
2
3
4
5
1 
 \
  2
 / 
3

return [1,2,3].

Note: Recursive solution is trivial, could you do it iteratively?

方法

前序遍历二叉树，不用递归的方法，就需要借助栈了。
首先将root入栈，然后取出，先将右子节点压入栈，再讲左子节点压入栈。然后取出栈的节点，压入该节点的右、左子节点，循环直到栈为空即可。

c代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <assert.h>
#include <stdlib.h>

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

/**
 * Return an array of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    if(root == NULL)
        return NULL;

    int *vals = (int *)malloc(sizeof(int) * 1000);
    int valsTop = 0;
    struct TreeNode* node = root;
    struct TreeNode** nodes = (struct TreeNode **)malloc(sizeof(struct TreeNode *) * 1000);
    int nodesTop = 0;
    nodes[nodesTop++] = root;

    while(nodesTop > 0) {
        node = nodes[--nodesTop];
        vals[valsTop++] = node->val;

        if(node->right)
            nodes[nodesTop++] = node->right;
        if(node->left)
            nodes[nodesTop++] = node->left;
    }
    *returnSize = valsTop;
    return vals;
}

int main() {
    struct TreeNode* root = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    root->val = 1;
    struct TreeNode* node1_2 = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    node1_2->val = 2;
    root->left = NULL;
    root->right = node1_2;
    struct TreeNode* node2_3 = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    node2_3->val = 3;
    node1_2->left = node2_3;
    node1_2->right = NULL;
    node2_3->left = NULL;
    node2_3->right = NULL;

    int returnSize = 0;
    int* vals = preorderTraversal(root, &returnSize);
    assert(returnSize == 3);
    assert(vals[0] == 1);
    assert(vals[1] == 2);
    assert(vals[2] == 3);

    return 0;
}

Posted on Reading time ≈ 1 mins.

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].

题目

给定一个非负整数num，计算出从0到num的每个数的二进制中包含1的个数

方法

对于数字n，它二进制表示形式中1的个数bits[n] = bits[n>>1]+n&1

c代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <assert.h>
#include <stdlib.h>

/**
 * Return an array of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* countBits(int num, int* returnSize) {
    int i = 0;
    int* bits = (int *)malloc(sizeof(int) * (num+1));
    bits[0] = 0;
    for(i = 0; i <= num; i++) {
        bits[i] = bits[i>>1] + (i&1);
    }
    *returnSize = num+1;
    return bits;
}

int main() {
    int returnSize = 0;
    int* bits = countBits(5, &returnSize);
    assert(bits[0] == 0);
    assert(bits[1] == 1);
    assert(bits[2] == 1);
    assert(bits[3] == 2);
    assert(bits[4] == 1);
    assert(bits[5] == 2);
    assert(returnSize == 6);

    return 0;
}

Posted on In Reading time ≈ 2 mins.

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:

1
2
3
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Solution

对数组排序后，第一个数字从数组开始遍历，二分查找满足条件的第二个数字，返回2个数字的位置。
由于排序导致数字位置发生了变换，因此需要一个数组记录变化后第i个数字之前的位置numsLocation[i]。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <assert.h>
#include <stdlib.h>

int* sort(int* nums, int numsSize) {
    int *numsLocations = (int *)malloc(sizeof(int) * numsSize);
    int i = 0, j = 0;
    for(i = 0; i < numsSize; i++)
        numsLocations[i] = i;

    for(i = 0; i < numsSize; i++) {
        int sorted = 1;
        for(j = 0; j < numsSize-1; j++) {
            if(nums[j] > nums[j+1]) {
                int temp = nums[j];
                nums[j] = nums[j+1];
                nums[j+1] = temp;
                sorted = 0;
                temp = numsLocations[j];
                numsLocations[j] = numsLocations[j+1];
                numsLocations[j+1] = temp;
            }
        }
        if(sorted)
            break;
    }
    return numsLocations;
}

int find(int* nums, int num, int start, int end) {
    if(start > end)
        return -1;
    int i = (start+end)/2;
    if(num > nums[i])
        return find(nums, num, i+1, end);
    else if(num < nums[i])
        return find(nums, num, start, i-1);
    return i;
}

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* twoSum(int* nums, int numsSize, int target) {
    int *numsLocations = sort(nums, numsSize);
    int i = 0;
    int num;
    int *locations = (int *)malloc(sizeof(int) * 2);
    int j;
    for(i = 0; i < numsSize; i++) {
        num = nums[i];
        if((j=find(nums, target-num, i+1, numsSize-1)) >= 0) {
            locations[1] = numsLocations[j];
            locations[0] = numsLocations[i];
            return locations;
        }
    }
    return NULL;
}

int main() {
    int nums[4] = {2, 7, 11, 15};
    int *locations = twoSum(nums, 4, 9);
    assert(locations[0] == 0);
    assert(locations[1] == 1);

    int nums2[3] = {5, 75, 25};
    locations = twoSum(nums2, 3, 100);
    assert(locations[0] == 2);
    assert(locations[1] == 1);

    return 0;
}