Eazow

Stay kind and positive

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

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

Posted on Reading time ≈ 1 mins.

1. 创建仓库

在github上创建名称为username.github.io仓库

2. Clone

将仓库clone到本地

1
$ git clone https://github.com/username/username.github.io

3. Hello World

创建index.html

1
2
$ cd username.github.io
$ echo "Hello World" > index.html

4. push

提交代码并push

1
2
3
$ git add --all
$ git commit -m "Initial commit"
$ git push -u origin master

5. 验证

访问username.github.io，这样就能看到Hello World了

6. 域名映射

将域名映射到username.github.io

1
2
3
$ echo "www.yourdomain.com" > CNAME
$ git commit -m "Create CNAME"
$ git push origin master

在域名管理添加一条CNAME记录，将www.yourdomain.com指向username.github.io

7. 安装Hexo

7.1 什么是Hexo

Hexo is a fast, simple and powerful blog framework. You write posts in Markdown (or other languages) and Hexo generates static files with a beautiful theme in seconds.

7.2 安装Git
7.3 安装Node.js
1
2
$ wget -qO- https://raw.github.com/creationix/nvm/master/install.sh | sh
$ nvm install 4
7.4 安装Hexo
1
2
3
4
5
$ npm install -g hexo-cli
$ hexo init <folder>
$ cd <folder>
$ npm install
$ hexo server

这样就可以通过localhost:4000访问了

7.5 部署到github

安装hexo-deployer-git

1
$ npm install hexo-deployer-git --save

修改_config.yml

1
2
3
deploy:
  type: git
  repo: <repository url>

部署到github

1
$ hexo deploy

但是部署后会覆盖掉github上的CNAME和README.md，需要在hexo的source目录添加CNAME和README.md，但是执行hexo generate后README.md会生成README.html，因此需要配置下，不让其渲染README.md。
修改Hexo目录下的_config.yml

1
skip_render: README.md

然后运行

1
2
$ hexo g
$ hexo d

这样就部署到github上了，并且不会覆盖掉已写好的CNAME和README.md了。

7.6 写blog
1
$ hexo new "Markdown"

会在source/_posts/目录下生成Markdown.md文件，编辑该文件后

1
2
$ hexo g
$ hexo d

参考

https://github.io
https://hexo.io

Posted on In Reading time ≈ 3 mins.

实验环境：Ubuntu 7.10 + Linux Kernel 2.6.23.12
耗时：约 2-3 小时（主要是编译时间）
难度：⭐⭐⭐

经过一两天的摸索，终于在 Ubuntu 虚拟机中成功完成了内核编译和系统调用添加实验。期间踩了不少坑，换了几个内核版本，重新编译了多次。现将完整步骤整理如下，希望能有所帮助！

📋 准备工作

系统要求

  • Ubuntu 7.10 或更高版本
  • 至少 20GB 磁盘空间
  • 4GB 以上内存（虚拟机建议分配 2GB+）

下载内核源码

访问 https://www.kernel.org 下载 Linux 内核源码包（本文使用 linux-2.6.23.12.tar.gz）

🔧 详细步骤

1. 解压内核源码

将内核包解压到 /usr/src 目录：

1
2
3
4
cd /usr/src
sudo tar jxvf linux-2.6.23.12.tar.bz2
# 或者如果是 .tar.gz 格式
sudo tar zxvf linux-2.6.23.12.tar.gz

2. 添加自定义系统调用

2.1 修改 sys.c 文件

在内核源码中添加系统调用实现：

1
2
cd /usr/src/linux-2.6.23.12
sudo vim kernel/sys.c

在文件末尾添加以下代码：

1
2
3
4
5
/* 自定义系统调用：打印消息并返回参数 */
asmlinkage int sys_mysyscall(int num) {
    printk(KERN_INFO "Hello from mysyscall! Received: %d\n", num);
    return num;
}

注意：asmlinkage 是必需的，表示参数通过栈传递。

2.2 修改系统调用表

编辑系统调用表文件：

1
2
3
cd /usr/src/linux-2.6.23.12/arch/i386/kernel
# 如果没有 i386 目录，尝试 x86 目录
sudo vim syscall_table.S

在文件末尾添加：

1
.long sys_mysyscall

2.3 添加系统调用号

修改系统头文件（用户空间）：

1
sudo vim /usr/include/asm-i386/unistd.h

在文件末尾添加：

1
#define __NR_mysyscall 325

修改内核头文件：

1
sudo vim /usr/src/linux-2.6.23.12/include/asm-i386/unistd.h

添加以下内容：

1
#define __NR_mysyscall 325

同时将原有的：

1
#define NR_syscalls 325

修改为：

1
#define NR_syscalls 326

提示：如果要添加多个系统调用，依次递增调用号（326, 327…）

3. 编译内核

3.1 配置内核

1
2
cd /usr/src/linux-2.6.23.12
sudo make menuconfig

在菜单中保持默认配置即可，直接保存退出。

3.2 编译内核镜像

1
sudo make bzImage

耗时：约 30-60 分钟

3.3 编译内核模块

1
sudo make modules

耗时：约 1-2 小时（虚拟机会更慢）
建议：此时可以休息一下，喝杯咖啡或打打球 😊

3.4 安装模块

1
sudo make modules_install

执行后会在 /lib/modules/ 下生成 2.6.23.12 目录。

3.5 安装内核

1
2
3
4
5
# 复制内核镜像
sudo cp arch/i386/boot/bzImage /boot/vmlinuz-2.6.23.12

# 生成 initramfs
sudo mkinitramfs -o /boot/initrd.img-2.6.23.12 2.6.23.12

4. 配置 GRUB 引导

4.1 编辑 GRUB 配置文件

1
2
3
sudo vim /boot/grub/menu.lst
# 或者
sudo vim /boot/grub/grub.conf

4.2 添加新内核启动项

在文件中找到类似以下的配置：

1
2
3
4
5
title Ubuntu 7.10, kernel 2.6.22-14-generic
root (hd0,0)
kernel /boot/vmlinuz-2.6.22-14-generic root=UUID=e2478f9d-7f5d-458f-b017-43458a8f62ea ro quiet splash
initrd /boot/initrd.img-2.6.22-14-generic
quiet

仿照格式添加新内核配置：

1
2
3
4
5
title Ubuntu 7.10, kernel 2.6.23.12 (Custom)
root (hd0,0)
kernel /boot/vmlinuz-2.6.23.12 root=UUID=e2478f9d-7f5d-458f-b017-43458a8f62ea ro quiet splash
initrd /boot/initrd.img-2.6.23.12
quiet

注意：UUID 需要替换为你自己的分区 UUID，可通过 sudo blkid 查看。

4.3 显示 GRUB 菜单

注释掉隐藏菜单选项（如果有）：

1
#hiddenmenu

保存并退出。

5. 重启系统

1
sudo reboot

在 GRUB 启动菜单中选择新编译的内核 kernel 2.6.23.12 (Custom) 启动。

🧪 测试自定义系统调用

编写测试程序

创建 test.c 文件：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <stdio.h>
#include <unistd.h>
#include <sys/syscall.h>

#define __NR_mysyscall 325

int main() {
    int result;
    
    printf("调用自定义系统调用 mysyscall...\n");
    result = syscall(__NR_mysyscall, 42);
    
    printf("系统调用返回值: %d\n", result);
    
    return 0;
}

编译并运行

1
2
gcc -o test test.c
./test

预期输出：

1
2
调用自定义系统调用 mysyscall...
系统调用返回值: 42

查看内核日志

1
dmesg | tail

应该能看到类似输出：

1
[12345.678901] Hello from mysyscall! Received: 42

常见问题及解决方案

问题 1：找不到 i386 目录

解决方案：新版本内核可能使用 x86 目录，修改路径为：

1
cd /usr/src/linux-2.6.23.12/arch/x86/kernel

问题 2：make modules 非常慢

解决方案：

  • 使用多核编译：sudo make -j4 modules（4 为 CPU 核心数）
  • 虚拟机分配更多 CPU 和内存

问题 3：编译报错缺少依赖

解决方案：安装必要的编译工具：

1
2
sudo apt-get update
sudo apt-get install build-essential libncurses5-dev

问题 4：系统调用返回 -1

解决方案：

  • 检查系统调用号是否正确
  • 确认 NR_syscalls 已更新
  • 查看 dmesg 输出是否有错误信息

✅ 总结与建议

关键要点

  1. 耐心：内核编译耗时较长，尤其是 make modules
  2. 备份：修改前备份重要文件
  3. 版本匹配：确保内核版本与教程一致
  4. 日志查看：善用 dmesg 调试

学习收获

  • 理解 Linux 内核编译流程
  • 掌握系统调用添加方法
  • 熟悉内核模块机制
  • 提升 Linux 系统底层认知

📚 参考资料

祝各位实验顺利！如有问题欢迎交流讨论！ 🎉