Eazow

Stay kind and positive

0%

Posted on In Reading time ≈ 4 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.

📖 文章主题

探讨人类如何通过文字记录、口头传说和考古发现来了解古代人类的历史。

🎯 核心问题回答

Why are legends handed down by storytellers useful?

答案：传说之所以有用，是因为它们能告诉我们关于古代人类迁徙的信息，尤其是那些生活在很久以前、没有文字记录能力的人群。

原文依据：

“These legends are useful because they can tell us something about migrations of people who lived long ago, but none could write down what they did.”

📝 段落解析

第一段：三种了解历史的方式

核心内容

  1. 文字记录（5,000年前开始）

    • 近东地区最早学会书写
    • 可以读到5000年前发生的事情

  2. 口头传说（无文字地区）

    • 通过讲故事的方式代代相传
    • 称为 sagas（传奇故事）

  3. 传说的价值

    • 帮助了解古代人类的迁徙
    • 例如：波利尼西亚人的祖先来自印度尼西亚（约2000年前）

重点句型

1
2
3
4
5
The only way that they can preserve their history is to recount it as sagas.
他们保存历史的唯一方式就是把它当作传说讲述出来。

结构：The only way (that)... is to do sth.
唯一的方法是...

第二段：最早人类的困境

核心内容

  • 最早的”现代人”生活得太久远
  • 即使有传说也已被遗忘
  • 考古学家既没有历史记录，也没有传说可以依靠

关键表达

1
2
3
4
But the first people who were like ourselves lived so long ago that...
但是最早像我们这样的人生活得如此久远，以至于...

结构：so... that...（如此...以至于...）

第三段：考古学的希望——石器

核心内容

  1. 古人制作石器

    • 主要用燧石（flint），因为容易塑形
    • 也可能用木头和兽皮，但已腐烂

  2. 石头的优势

    • 不会腐烂（decay）
    • 即使制作者的骨头都消失了，石器仍然保留

重点对比

材料 特点 结果
木头、兽皮 会腐烂（rot away） 已消失
石头 不会腐烂（does not decay） 保存至今
人骨 会消失（disappear without trace） 无踪迹

📚 重点词汇详解

1. recount /rɪˈkaʊnt/

  • 词性：动词
  • 含义：详细叙述，讲述
  • 例句：
    1
    2
    She recounted her adventures in Africa.
    她详细讲述了在非洲的冒险经历。

2. saga /ˈsɑːɡə/

  • 词性：名词
  • 含义：传奇故事；长篇冒险故事
  • 例句：
    1
    2
    The saga of their journey across the desert fascinated everyone.
    他们穿越沙漠的传奇故事让所有人着迷。

3. anthropologist /ˌænθrəˈpɒlədʒɪst/

  • 词性：名词
  • 含义：人类学家
  • 词根：anthropo-（人类）+ -logist（学家）
  • 相关词：
    • anthropology（人类学）
    • archaeology（考古学）

4. Polynesian /ˌpɒlɪˈniːʒən/

  • 词性：形容词/名词
  • 含义：波利尼西亚的/波利尼西亚人
  • 地理：太平洋岛屿地区

5. flint /flɪnt/

  • 词性：名词
  • 含义：燧石（一种坚硬的石头）
  • 用途：古代制作工具和生火

6. rot /rɒt/

  • 词性：动词
  • 含义：腐烂，腐朽
  • 短语：rot away（完全腐烂）
  • 例句：
    1
    2
    The wood had rotted away over the years.
    木头经年累月已经腐烂了。

7. decay /dɪˈkeɪ/

  • 词性：动词/名词
  • 含义：腐烂；衰败
  • 区别：
    • rot：强调有机物质的腐烂
    • decay：更广泛，可指任何形式的衰败

8. trace /treɪs/

  • 词性：名词/动词
  • 含义：痕迹；追踪
  • 短语：without trace（无影无踪）
  • 例句：
    1
    2
    The plane vanished without trace.
    飞机消失得无影无踪。

🔑 重点语法结构

1. 定语从句

1
2
3
4
5
We can read of things that happened 5,000 years ago.
我们可以读到5000年前发生的事情。

The only way that they can preserve their history is...
他们保存历史的唯一方式是...

2. 被动语态

1
2
3
4
legends handed down from one generation to another
代代相传的传说

（完整形式：legends that are handed down...）

3. so…that…结构

1
2
lived so long ago that even their sagas are forgotten
生活得如此久远，以至于即使他们的传说也被遗忘了

4. neither…nor…结构

1
2
archaeologists have neither history nor legends to help them
考古学家既没有历史也没有传说来帮助他们

💡 文章逻辑结构

1
2
3
4
5
6
7
8
9
10
11
12
13
了解古代人类历史的三种方式：

1. 文字记录 ✓
   └─ 5000年前开始
   └─ 有限制：只在某些地区

2. 口头传说 ✓
   └─ 无文字地区的方式
   └─ 有限制：最早的人类连传说都没留下

3. 考古发现 ✓✓✓
   └─ 石器工具
   └─ 最可靠：石头不会腐烂

🎓 学习要点

理解层面

  1. 人类历史研究的三个来源
  2. 为什么石器对考古学如此重要
  3. 不同材料的保存性差异

语言层面

  1. 定语从句的使用
  2. 因果关系的表达（because, so…that）
  3. 对比结构（but, however）

词汇层面

  1. 历史考古相关词汇
  2. 材料特性描述词汇
  3. 时间表达方式

✍️ 写作可借鉴的表达

  1. 引出话题：

    1
    2
    We can read of things that happened...
    我们可以读到...发生的事情

  2. 转折对比：

    1
    2
    But there are some parts of the world where...
    但是世界上有些地方...

  3. 强调唯一性：

    1
    2
    The only way that... is to...
    ...的唯一方式是...

  4. 表达幸运：

    1
    2
    Fortunately, however,...
    然而，幸运的是...

这篇文章展示了说明文的典型结构：提出问题→分析问题→给出答案，语言简洁清晰，逻辑严密，非常适合学习英语写作！

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 ≈ 2 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;
}

Posted on Reading time ≈ 1 mins.

Markdown is a text-to-HTML conversion tool for web writers. Markdown allows you to write using an easy-to-read, easy-to-write plain text format, then convert it to structurally valid XHTML (or HTML).

用markdown写东西感觉很赞，方便简洁，给人带来一种想写东西的快感

基本语法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 一级标题
## 二级标题
...
###### 六级标题

> 这是一句引用

*斜体*
**粗体**
***斜粗体***

* 列表1
* 列表2
* 列表3

***  // 分割线

// 上标，下标
num^2^
num~i~

// Image
![Image](https://eazow.com/imgs/demo.jpg)
对应效果如下

一级标题

二级标题

六级标题

这是一句引用

  • 列表1
  • 列表2
  • 列表3

斜体
粗体
斜粗体

num^2^
numi

Demo