ARTS-week23

发表于 | 分类于
本文字数： 2.9k | 阅读时长 ≈ 3 分钟

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，也就是更倾向于使用回收文件页。

0%