发表更新linux21 分钟读完 (大约3098个字)

cha4.文件IO:通用的I/O模型

实现tee

tee命令是从标准输入中读取数据，直至文件结尾，随后将数据写入标准输出和命令行参数所指定的文件。(44.7节讨论FIFO时，会展示使用tee命令的一个例子。)请使用IO系统调用实现tee命令。默认情况下，若已存在与命令行参数指定文件同名的文件，tee命令会将其覆盖。如文件已存在，请实现-a命令行选项tee-a file在文件结尾处追加数据。(请参考附录B中对getopt)函数的描述来解析命令行选项。

预处理与函数声明

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
#include<string.h>

#include<sys/stat.h>
#include<fcntl.h>
#include<unistd.h>
#include<stdlib.h>

#include<errno.h> // 使用变量errno

#define bool char
#define false 0
#define true 1
#define strcmp(a,b) strcmp(a,b)==0

// exit code
#define UNSUPPORTED_ARG 1
#define FILE_OPEN_FAIL 2
#define STDOUT_WRITE_FAIL 3
#define STDERR_WRITE_FAIL 4
#define STDIN_READ_FAIL 5
#define PARTIAL_WRITE_OCCURED 6
#define FILE_CLOSE_FAIL 7
#define FILE_WRITE_FAIL 8

// 函数声明
void printHelp();
void printVersion();
void writeErr(const char* str);
void writeStdout(const char* str);
void exitErr(const char * err, int exitcode);
void release();

// 常量
#define MAX_FILE_COUNT 100
#define READ_BUFFER_SIZE 100

// 全局资源
char **files = NULL;
int *fds = NULL;
int fileCount = 0;

不引用c的库函数，直接使用系统调用对文件进行读写，不引入stdio.h

工具函数

阅读更多
发表更新LeetCode / 算法11 分钟读完 (大约1601个字)

LeetCode-24

1616. 分割两个字符串得到回文串

ac代码

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
class Solution {
public:
    bool checkPalindromeFormation(string a, string b) {
        int len = a.length();
        if(len == 1) return true;
        bool flaga = true, flagb = true;
        int i = 0;
        for(; i < len; i++) {
            if(a[i] == b[len-1-i]) {
            } else {
                break;
            }
        }
        for(int j = i; j < len-1-i; j++) {
            if(b[j] != b[len-1-j]) {
                flagb = false;
                break;
            }
        }
        for(int j = i; j < len-1-i; j++) {
            if(a[j] != a[len-1-j]) {
                flaga = false;
                break;
            }
        }
        if(flaga || flagb) return true;
        flaga = flagb = true;
        for(i = 0; i < len; i++) {
            if(a[len-1-i] == b[i]) {
            } else {
                break;
            }
        }
        for(int j = i; j < len-1-i; j++) {
            if(a[j] != a[len-1-j]) {
                flaga = false;
                break;
            }
        }
        for(int j = i; j < len-1-i; j++) {
            if(b[j] != b[len-1-j]) {
                flagb = false;
                break;
            }
        }
        return flaga || flagb;
    }
};

ab两个字符串在同一个位置分隔开，若 $ pre_a + suf_b $ 或 $ pre_b + suf_a $ 是回文串，则返回true，否则返回false
这个规则相当于ab截取相同且任意长的前缀并交换，看交换后是否存在回文
我的思路是先比较a的第i位与b的倒数第i位是否想等，找到第一次不相等的位置i，此时可以从第i位分割，判断b的剩余部分是否是回文，或者从len-i-1处分割，判断a的剩余部分是否是回文
若都不是，再比较b的第i位与a的倒数i位，找到第一个不满足的i，再比较a，b的剩余部分

优化行数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    bool checkPalindromeFormation(string a, string b) {
        int len = a.length();
        int paliA = len/2-1, paliB = len/2;
        while(paliA > 0 && a[paliA] == a[len-1-paliA]) paliA--;
        while(paliB > 0 && b[paliB] == b[len-1-paliB]) paliB--;
        int i, j;
        for(i = 0; i < len/2; i++) {
            if(a[i] != b[len-1-i]) {
                break;
            }
        }
        
        for(j = 0; j < len/2; j++) {
            if(b[j] != a[len-1-j]) {
                break;
            }
        }
        return min(paliA, paliB) < max(i, j);
    }
};
阅读更多
发表更新LeetCode / 算法12 分钟读完 (大约1759个字)

LeetCode-23

1144. 递减元素使数组呈锯齿状

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
class Solution {
public:
    int movesToMakeZigzag(vector<int>& nums) {
        int odd2less, even2less;
        odd2less = even2less = 0;
        int n = nums.size();
        if(n <= 1) return 0;
        for(int i = 1; i < n - 1; i++) {
            if(i%2 == 0) {
                if(nums[i] >= min(nums[i-1], nums[i+1])) {
                    even2less += nums[i] - min(nums[i-1], nums[i+1]) + 1;
                }
            } else {
                if(nums[i] >= min(nums[i-1], nums[i+1])) {
                    odd2less += nums[i] - min(nums[i-1], nums[i+1]) + 1;
                }
            }
        }
        if(nums[0] >= nums[1]) {
            even2less += nums[0] - nums[1] + 1;
        }
        if(nums[n-1] >= nums[n-2]) {
            if((n-1)%2 == 0) {
                even2less += nums[n-1] - nums[n-2] + 1;
            } else {
                odd2less += nums[n-1] - nums[n-2] + 1;
            }
        }
        return min(even2less, odd2less);

    }
};

遍历所有奇数，使其小于两端，记录操作数1
遍历所有偶数，使其小于两端，记录操作数2
返回最小值

优化代码行数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int movesToMakeZigzag(vector<int>& nums) {
        int op[2] = {0}, n = nums.size();
        if(n <= 1) return 0;
        for(int i = 1; i < n - 1; i++) {
            if(nums[i] >= min(nums[i-1], nums[i+1]))
                op[i&1] += nums[i] - min(nums[i-1], nums[i+1]) + 1;
        }
        if(nums[0] >= nums[1]) {
            op[0] += nums[0] - nums[1] + 1;
        }
        if(nums[n-1] >= nums[n-2]) {
            op[(n-1)&1] += nums[n-1] - nums[n-2] + 1;
        } 
        return min(op[0], op[1]);
    }
};

2325. 解密消息

阅读更多
发表更新LeetCode / 算法26 分钟读完 (大约3955个字)

LeetCode-22

2347. 最好的扑克手牌

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 {
public:
    string bestHand(vector<int>& ranks, vector<char>& suits) {
        vector<int> rank_count(13, 0), suits_count(4, 0);
        for(int i = 0; i < 5; i++) {
            rank_count[ranks[i]-1]++;
            suits_count[suits[i] - 'a']++;
        }
        int count = 0;
        for(int i = 0; i < 4; i++) {
            count = max(count, suits_count[i]);
        }
        if(count == 5) return "Flush";
        count = 0;
        for(int i = 0; i < 13; i++) {
            count = max(count, rank_count[i]);
        }
        if(count >= 3) {
            return "Three of a Kind";
        } else if (count == 2) {
            return "Pair";
        }
        return "High Card";
    }
};

1604. 警告一小时内使用相同员工卡大于等于三次的人

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
class Solution {
public:
    vector<string> alertNames(vector<string>& keyName, vector<string>& keyTime) {
        map<string, vector<int>> hour_count;
        int len = keyName.size();
        for(int i = 0; i < len; i++) {
            int h = (keyTime[i][0]-'0')*10 + keyTime[i][1] - '0', m = (keyTime[i][3] - '0') * 10 + keyTime[i][4] - '0';
            hour_count[keyName[i]].push_back(h*60+m);
        }
        vector<string> warning_list;
        for(auto ite = hour_count.begin(); ite != hour_count.end(); ite++) {
            bool warn = false;
            sort(ite->second.begin(), ite->second.end());
            int len = ite->second.size();
            for(int i = 0; i < len-2; i++) {
                if(ite->second[i+2] - ite->second[i] <= 60) {
                    warn = true;
                    break;
                }
            }
            if(warn) {
                warning_list.push_back(ite->first);
            }
        }
        return warning_list;
    }
};
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
class Solution {
public:
    vector<string> alertNames(vector<string>& keyName, vector<string>& keyTime) {
        map<string, priority_queue<int>> hour_count;
        int len = keyName.size();
        for(int i = 0; i < len; i++) {
            int h = (keyTime[i][0]-'0')*10 + keyTime[i][1] - '0', m = (keyTime[i][3] - '0') * 10 + keyTime[i][4] - '0';
            hour_count[keyName[i]].push(h*60+m);
        }
        vector<string> warning_list;
        for(auto ite = hour_count.begin(); ite != hour_count.end(); ite++) {
            int len = ite->second.size();
            if(len <= 2) continue;
            int a, b, c;
            a = ite->second.top();
            ite->second.pop();
            b = ite->second.top();
            ite->second.pop();
            c = ite->second.top();
            ite->second.pop();
            bool warn = a - c <= 60;
            while(!warn && !ite->second.empty()) {
                a = b;
                b = c;
                c = ite->second.top();
                ite->second.pop();
                warn = a - c <= 60;
            }
            if(warn) {
                warning_list.push_back(ite->first);
            }
        }
        return warning_list;
    }
};

2331. 计算布尔二叉树的值

阅读更多
发表更新LeetCode / 算法21 分钟读完 (大约3190个字)

LeetCode-21

1234. 替换子串得到平衡字符串

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
class Solution {
public:
    bool isBalance(int* count, int avg) {
        return count['Q'] <= avg && count['R'] <= avg && count['E'] <= avg && count['W'] <= avg;
    }
    int balancedString(string s) {
        int count[128] = {0};
        for (char c : s) {
            count[c]++;
        }
        int len = s.length();
        int avg = len / 4;

        if (isBalance(count, avg)) {
            return 0;
        }
        int res = len;
        for (int l = 0, r = 0; l < len; l++) {
            while (r < len && !isBalance(count, avg)) {
                count[s[r]]--;
                r++;
            }
            if (!isBalance(count, avg)) {
                break;
            }
            res = min(res, r - l);
            count[s[l]]++;
        }
        return res;
    }
};

1138. 字母板上的路径

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
class Solution {
public:
    string alphabetBoardPath(string target) {
        int x = 0, y = 0;
        string res = "";
        for(char c : target) {
            int next_x = getX(c), next_y = getY(c);
            char step_x = 'L', step_y = 'U';
            int diff_x = x - next_x, diff_y = y - next_y;
            
            if(next_x > x) {
                step_x = 'R';
                diff_x = -diff_x;
            }
            if(next_y > y) {
                step_y = 'D';
                diff_y = - diff_y;
            }
            if(next_y == 5) {
                for(int i = 0; i < diff_x; i++) {
                    res += step_x;
                }
                for(int i = 0; i < diff_y; i++) {
                    res += step_y;
                }

            } else {
                for(int i = 0; i < diff_y; i++) {
                    res += step_y;
                }
                for(int i = 0; i < diff_x; i++) {
                    res += step_x;
                }
            }
            
            res += "!";
            x = next_x;
            y = next_y;
        }
        return res;
    }
    int getX(char c) {
        return (c - 'a') % 5;
    }
    int getY(char c) {
        return (c - 'a') / 5;
    }
};

如果默认先纵向走，再横向走，那么当从外部到z时，需要先横向走再纵向走
如果默认先横向走，再纵向走，那么当从z到外部时，需要先纵向走再横向走

2335. 装满杯子需要的最短总时长

阅读更多
发表更新misc10 分钟读完 (大约1556个字)

geth搭建私链

主要工作

参考go-ethereum官网的Private Networks文档搭建了一个私有链，并总结出几个脚本，可以半自动化地实现geth网络的搭建，脚本已上传至github仓库DLCCB

setup.sh

  • 这一步使用了以下几个工具
    • geth命令，用于生成初始两个节点的账户，使用创世块配置文件对两个账户进行初始化
    • puppeth 用于生成创世块的配置文件，这个命令是交互式的，编写了一个puppeth.txt作为其输入，默认生成一个基于pow的区块链
    • bootnode 用于生成启动bootnode
  • 这一步使用了以下几个linux命令
    • sed 非交互式的文本编辑器，用于读取生成的账户的区块链地址，写入puppeth.txt中，使得puppeth工具能为初始的两个节点分配一定的以太币
    • awk，用于对文本的处理
setup.sh
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
mkdir node1 node2
geth --datadir node1 account new < password.txt
geth --datadir node2 account new < password.txt

sed -i "5i$(cat node1/keystore/UTC--* | awk '{split($0, arr, "\""); print arr[4]}')" puppeth.txt 
sed -i "5i$(cat node2/keystore/UTC--* | awk '{split($0, arr, "\""); print arr[4]}')" puppeth.txt 
puppeth < puppeth.txt
sed -i "5d" puppeth.txt
sed -i "5d" puppeth.txt

geth init --datadir node1 tianer.json
geth init --datadir node2 tianer.json

cat password.txt | head -n 1 | tee node1/password.txt
cat password.txt | head -n 1 | tee node2/password.txt

bootnode -genkey boot.key
bootnode -nodekey boot.key -addr :30305

两个输入文件的内容

阅读更多
发表更新LeetCode / 算法7 分钟读完 (大约1111个字)

LeetCode-20

1758. 生成交替二进制字符串的最少操作数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int minOperations(string s) {
        int len = s.size();
        return min(cal(s, len, true), cal(s, len, false));
    }
    int cal(const string& s, int len, bool flag) {
        int count = 0;
        for(int i = 0; i < len; i++) {
            if(flag && s[i] == '0' || !flag && s[i] == '1') {
                count++;
            }
            flag = !flag;
        }
        return count;
    }
};

813. 最大平均值和的分组

超时暴搜

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int len = 0;
    vector<int> sum;
    double largestSumOfAverages(vector<int>& nums, int k) {
        len = nums.size();
        sum = vector<int>(len+1, 0);
        for(int i = 1; i <= len; i++) {
            sum[i] = nums[i-1] + sum[i-1];
        }
        return search(nums, k, 1, 1, 0, 0);
    }
    double search(vector<int>& nums, int k, int i, int K, double left_value, int last_j) {
        if(k == K || i == len) {
            return left_value + (sum[len] - sum[last_j] + 0.0) / (len - last_j);
        }
        return max(search(nums, k, i+1, K+1, left_value + (sum[i] - sum[last_j] + 0.0)/(i-last_j), i), search(nums, k,i+1, K, left_value, last_j));
    }

    double max(double a, double b) {
        return a > b ? a : b;
    }
};

昨天第一个思路是用排序，找出最大的m个数，这m个数恰好将数组分成k个部分，发现不可行。
然后暴力搜索，超时了，暴搜时考虑添加隔板，其中left_value表示当前搜索下标i之前的分组平均值

阅读更多
发表更新LeetCode / 算法3 分钟读完 (大约387个字)

LeetCode-19

1710. 卡车上的最大单元数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int maximumUnits(vector<vector<int>>& boxTypes, int truckSize) {
        sort(boxTypes.begin(), boxTypes.end(), [](vector<int>& x, vector<int>& y)->bool {
            return x[1] > y[1];
        });
        int n = boxTypes.size();
        int ret = 0;
        for(int i = 0; i < n; i++) {
            if(truckSize) {
                ret += min(truckSize, boxTypes[i][0])*boxTypes[i][1];
                truckSize -= min(truckSize, boxTypes[i][0]);
            } else {
                break;
            }
        }
        return ret;
    }
};
// 50 + 27 + 14 = 91

简单题，排个序就行

775. 全局倒置与局部倒置

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    bool isIdealPermutation(vector<int>& nums) {
        for (int i = 0; i < nums.size(); i++) {
            if (abs(nums[i] - i) > 1) {
                return false;
            }
        }
        return true;
    }
};

最开始想复杂了，想用差分数组统计个数

阅读更多
发表更新LeetCode / 算法30 分钟读完 (大约4482个字)

LeetCode-dp

leetcode 101的动态规划专题

基本动态规划：一维

70. 爬楼梯

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int climbStairs(int n) {
        int a=1,b=2;
        if(n<2) return 1; 
        for(int i = 2; i <n ; i++) {
            int c = a+b;
            a=b;
            b=c;
        }
        return b;
    }
};

dp数组表示上n层楼有几种可能
转移方程是 $ dp[i] = dp[i-1] + dp[i-2] $
上到第i层有可能从第i-1层或i-2层上来，则上到i层的可能数目就是 $ dp[i-1] + dp[i-2] $
由于dp[i]只需要前两个数的数据，所以可以优化掉dp数组，用两个变量代替，节省数组空间

198. 打家劫舍

阅读更多
关注我

链接

分类

最新文章

归档

标签

6.8242
Android1
Android FrameWork1
Android 高级开发瓶颈突破系列课11
Android-官方文档1
Android-官方源码5
Android面试查漏补缺2
C/C++1
Flutter1
Java基础1
Kotlin-Android21
Kotlin-Android 实习25
LeetCode45
LeetCode 1013
LeetCode周赛1
Linux/UNIX系统编程手册38
OI KIWI2
OS4
PAT-(Advanced-Level)-Practice2
PAT-(Basic-Level)-Practice44
blockchain1
fedfab13
gallery1
geth1
git1
gradle1
hexo2
linux2
misc1
projects1
shell2
刷题2
动态规划1
多线程1
排序1
数据库2
牛客2
算法43
×