Algorithms
Two Sum II - Input array is sorted
思路:题目中提到数组已经升序排列，两个数之和sum就是target，所以是小数在前，大数在后，用两个指针来搞定，一个指向开头，一个指向末尾，然后向中间遍历即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
int i = 0;
int j = numbers.size() - 1;
vector<int> res(2);
while (i < j) {
int tmp = numbers[i] + numbers[j];
if (tmp < target) {
++i;
} else if (tmp > target) {
--j;
} else {
res[0] = i + 1;
res[1] = j + 1;
return res;
}
}
return res;
}
};
|
Majority Element
思路：用哈希的方式循环遍历，计算值为相同数字的个数，如果超过n/2，则元素tmp为众数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
int majorityElement(vector<int>& nums) {
unordered_map<int,int> map;
int len = nums.size();
for(int i = 0;i < len; i++) {
int tmp = nums[i];
if(map.find(tmp) == map.end()) {
map[tmp] = 0;
}
else {
map[tmp]++;
}
if(map[tmp] >= len/2) {
return tmp;
}
}
}
};
|
在Solution中看到Boyer-Moore Voting Algorithm，该算法先将第一个数设为众数，并将计数器设为1，然后将此数与下一个数进行比较是否相等，若相等计数器加一，反之减一，直到遍历数组结束。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
int majorityElement(vector<int>& nums) {
vector<int> &tmp = nums;
int n = tmp.size();
int res = tmp[0], cnt = 1;
for (int i = 1; i < n; ++i) {
if (res == tmp[i]) {
++cnt;
}else if (cnt == 1) {
res = tmp[i];
}else {
--cnt;
}
}
return res;
}
};
|
Review
本周阅读英文文章 The 6 most useful Machine Learning projects of the past year (2018)
Technique
本周在看深入理解C指针一书中学习到的关于RAII(Resource Acquisition Is Initialization, 资源获取即初始化)在C中的使用。
GNU编译器提供了非标准的扩展来支持这个特性，要用到RAII_VARIABLE宏，它声明一个变量，然后给变量关联如下属性：
- 一个类型；
- 创建变量时执行的函数；
- 变量超出作用域时执行的函数。
举个栗子：
1
2
3
| #define RAII_VARIABLE(vartype,varname,initval,dtor) \
void _dtor_ ## varname (vartype * v) { dtor(*v); } \
vartype varname __attribute__((cleanup(_dtor_ ## varname))) = (initval)
|
具体使用：
1
2
3
4
5
6
| void raiiExample()
{
RAII_VARIABLE(char*, name, (char*)malloc(32), free);
strcpy(name,"RAII Example");
printf("%s\n",name);
}
|
但是这种方法如果要遇到多维数组，还需要再具体实现针对多维数组的处理，使用起来貌似不是很方便。
Share
关于swappiness
内存回收机制包括文件页和匿名页：
- 对于文件页的回收，就是直接回收缓存，或者把脏页写回磁盘后再回收。
- 对于匿名页的回收，是通过Swap机制，把他们写入磁盘后再释放内存。
Linux提供了/proc/sys/vm/swappiness选项，用来调整使用Swap的积极程度。swappiness的范围是0-100(此处不是指内存的百分比，而是调整Swap积极程度的权重，即使设置为0，当剩余内存+文件页小于页高阈值时，还是会发生Swap)，数值越大，越积极使用Swap，也就是更倾向于回收匿名页；数值越小，越消极使用Swap，也就是更倾向于使用回收文件页。