“Better code, better life. ”
ARTS打卡第一周
Algorithm
[题目] ：leetcode第53题
[题解] ：https://github.com/SimonZgx/note/blob/master/src/leetcode/dp/53/main.cpp
[总结] ：
这是一道出现在《算法导论》上的经典题目，书上给的是分冶的解法，这里也尝试用分冶算法解决。拿到题目很容易想到的是暴力求解，即对于每一个下标为i的数字nums[i]，遍历以其作为首元素的所有连续数组并求和，以此算出最大连续子数组的和，该方法复杂度为O(n*n!)，空间复杂度为O(1)。
其次是分冶解法。首先尝试把该问题转化成更简单的子问题：如果将该数组一分为2，那么最长子数组有三种情况：
-
最大连续和子数组在左侧。
-
最大连续和子数组在右侧。
-
最大连续和子数组跨过原数组的终点。
对于以上三种情况，我们分别记为： \(Sum_l,Sum_r,Sum_$\) 显然我们要求的结果为： \(Sum = max\{Sum_l, Sum_r,Sum_c\}\) 另外，如果一个数组长度为1，那么显然其最大连续子数组就是其本身。所以有： \(Sum= \begin{cases} max\{Sum_l, Sum_r,Sum_c\}& \text{length>0}\\ nums[0]& \text{length=0} \end{cases}\)
剩下的就是写代码了：
#include <iostream> #include <vector> #include <queue> #include <cstdlib> using namespace std; class Solution { public: static int crossSum(vector<int> nums, int left, int right, int p) { if (left == right)return nums[left]; int sum = 0, leftSum = INT_MIN, rightSum = INT_MIN; for (int i = p; i >= left; --i) { sum += nums[i]; leftSum = max(sum, leftSum); } sum = 0; for (int i = p + 1; i <= right; ++i) { sum += nums[i]; rightSum = max(sum, rightSum); } return leftSum + rightSum; } int helpers(vector<int> nums, int left, int right) { if (left == right)return nums[left]; int p = (left + right) / 2; int leftMax = helpers(nums, left, p); int rightMax = helpers(nums, p + 1, right); int crossMax = crossSum(nums, left, right, p); return max(leftMax, max(rightMax, crossMax)); } int maxSubArray(vector<int> nums ) { return helpers(nums, 0, nums.size() - 1); } }; int main() { vector<int> nums{8, -19, 5, -4, 20}; Solution s; cout << s.maxSubArray(nums) << endl; }
Review
[文章链接] ：http://www.wangafu.net/~nickm/libevent-book/Ref1_libsetup.html
[笔记] :
这是Libevent官方教程中的第二篇，主要介绍了一些Libevent提供的全局接口。
-
使用自定义的Logger代替Libevent默认的日志
libevent提供了如下接口:
#define EVENT_LOG_DEBUG 0
#define EVENT_LOG_MSG 1
#define EVENT_LOG_WARN 2
#define EVENT_LOG_ERR 3
/* Deprecated; see note at the end of this section */
#define _EVENT_LOG_DEBUG EVENT_LOG_DEBUG
#define _EVENT_LOG_MSG EVENT_LOG_MSG
#define _EVENT_LOG_WARN EVENT_LOG_WARN
#define _EVENT_LOG_ERR EVENT_LOG_ERR
typedef void (*event_log_cb)(int severity, const char *msg);
void event_set_log_callback(event_log_cb cb);
其中event_set_log_callback可以传入自定义Logger函数，但是应满足event_log_cb所声明的格式。
-
自定义处理程序崩溃的函数
libevent默认的处理意料之外的程序错误的方法是直接exit()推出程序，我们可以使用下面的接口，来使用我们自定义的异常处理函数：
typedef void (*event_fatal_cb)(int err);
void event_set_fatal_callback(event_fatal_cb cb);
注意，执行完自定义的异常处理后，libevent依然会调用exit()方法，所以在异常处理函数中不应该继续再调用Libevent，诸如此类的行为可能导致未定义行为的发生。
-
自定义的内存管理函数
libevent使用的C语言内置的malloc,realloc,free方法来做内存管理，同时也提供了如下接口：
void event_set_mem_functions(void *(*malloc_fn)(size_t sz),
void *(*realloc_fn)(void *ptr, size_t sz),
void (*free_fn)(void *ptr));
来让我们设置自定义的内存分配、回收函数。比如我们可以再malloc/free的基础上座一层封装，把分配/回收的内存的大小记录下来，然后据此来发现内存泄漏问题。
注意，这个设置时针对libevent全局的，一旦生效，libevent中所有涉及到内存分配回收的方法都会收到影响。
-
线程和锁
对于线程和互斥锁，libevent依然提供了接口让用户能够自定义实现：
#ifdef WIN32
int evthread_use_windows_threads(void);
#define EVTHREAD_USE_WINDOWS_THREADS_IMPLEMENTED
#endif
#ifdef _EVENT_HAVE_PTHREADS
int evthread_use_pthreads(void);
#define EVTHREAD_USE_PTHREADS_IMPLEMENTED
#endif
前提是你要实现一整套pthread里所提供的接口，所以并不推荐使用这个功能！
Tips
使用宏来减少代码量
本周的工作中，我需要实现一个从A对象的一些字段的值构造出B对象，所以我在B类中加了一个fromA的方法，类似这样：
struct A{
//fields
}
struct B{
//fields
void fromA(const A& a);
}
在fromA中根据A的一些成员变量的值，来给B对象的成员变量赋值，但是我发现我不得不写一些类似这样的代码：
void B::fromA(const A& a){
if(a.field_a > 0){
this->field_a = a.field_a;
}else{
...
}
if(a.field_b > 0){
this->field_b = a.field_b;
}else{
...
}
...
}
如何减少这种代码量呢？我是这么干的：
#define VALUE_COPY(field) \
if(a.field > 0){ \
this->field = a.field; \
}else{ \
... \
} \
void B::fromA(const A& a){
VALUE_COPY(field_a);
VALUE_COPY(field_b);
...
}
代码量一下子降下来了。但是！！！C++规范并不推荐这么做，因为在很多编译器上，宏定义是没有类型检查的，并且这么做只是降低了明面上的代码量，宏定义在预编译阶段依然会在所有使用的地方展开，所以实际的代码量并没有因此减少。综上，这只是一个奇淫技巧，并不很推荐使用。
Share
本周学习了C++11中的bind和function两个模板类\函数，写了一篇博客如下
