Blog of Samperson

五天准备清华九推机考

2018-09-08

本科阶段对于java比较熟练，但是C++接触的非常少，算法接触的也非常少。但是根据学长的经验，虽然机考占比只有20%，但是面试大家的成绩大多数差不多，因此机考还是蛮重要的。


收到清华复试通知之前一直都没有准备（比较懒……），因此准备机考和面试的时间很短，只有周日到周四5天的时间。所以只是做完了往年的机考题，并挑选了一些Leetcode上典型问题准备了下。

C++与Java对应关系

[1] vector -> ArrayList
[2] list -> LinkedList
[3] map -> TreeMap 有序图
[4] unordered_map -> HashMap 无序图
[5] set -> TreeSet 有序集合
[6] unordered_set -> 无序集合
[7] queue -> Queue
[8] stack -> Stack
[9] prioriry_queue -> PriorityQueue (c++ 默认是最大堆， java是最小堆)


常用基本操作

[1] const char *c_str()
c_str()函数返回一个指向正规C字符串的指针, 内容与本字符串相同.


[2] find()函数 (同理：find_first_of / find_last_of)
返回str在字符串中第一次出现的位置（从index开始查找）。如果没找到则返回string::npos,
返回str在字符串中第一次出现的位置（从index开始查找，长度为length）。如果没找到就返回string::npos,
返回字符ch在字符串中第一次出现的位置（从index开始查找）。如果没找到就返回string::npos



[3] 负数(变为正数)

1
2
3
4
5
if (st[0] != '-') 
       //… …
   else
	char *s2 = s1 + 1;
	//… …



[4] 内存拷贝函数
原型：void* memcpy(void* dest, const void* src, unsigned int count);
功能：由src所指内存区域复制count个字节到dest所指内存区域。
说明：src和dest所指内存区域不能重叠，函数返回指向dest的指针
其中size_t是number of bytes(字符的个数)，用strlen(src)，不能用sizeof(src)，sizeof(src)计算的是开辟src占用的总的byte数。


[5] memset
头文件：<string.h>或 <memory.h>
函数原型：void *memset(void *s, int ch, size_t n)
函数解释：将s中的前n个字节用ch替换并且返回s
函数作用：在一段内存块中填充某一个给定的值，常用于较大的对结构体和数组的清零操作。
例如：memset(tmp, 0, sizeof(tmp)); //把整个tmp char数组填满0


[6] #include < algorithm>
（1）sort(a.begin(), a.end()); //对a中的从a.begin()（包括它）到a.end()（不包括它）的元素进行从小到大排列
（2）reverse(a.begin(), a.end()); //对a中的从a.begin()（包括它）到a.end()（不包括它）的元素倒置，但不排列，如a中元素为1,3,2,4,倒置后为4,2,3,1
（3）copy(a.begin(), a.end(), b.begin()+1); //把a中的从a.begin()（包括它）到a.end()（不包括它）的元素复制到b中，从b.begin()+1的位置（包括它）开始复制，覆盖掉原有元素
（4）find(a.begin(), a.end(), 10); //在a中的从a.begin()（包括它）到a.end()（不包括它）的元素中查找10，若存在返回其在向量中的位置


[7] 初始化数组

1
2
const int NMAX = 10;
int mat[NMAX][NMAX] = {}; //全部赋值为0s



[8] 字符串中出现个数

1
2
#include <string>
count(s.begin(), s.end(), c);

first是容器的首迭代器，last是容器的末迭代器，value是询问的元素


[9] 数字、字符串转化
(1) string s = to_string(int i);
(2) 

1
2
3
4
ostringstream os; //构造一个输出字符串流，流内容为空
int i = 12;
os << i; //向输出字符串流中输出int整数i的内容
cout << os.str() << endl; //利用字符串流的str函数获取流中的内容

(3) int a = stoi(s1);
(4)

1
2
3
istringstream is("12"); //构造输入字符串流，流的内容初始化为“12”的字符串
int i;
is >> i; //从is流中读入一个int整数存入i中


动态规划DP

动态规划是利用存储历史信息使得未来需要历史信息时不需要重新计算， 从而达到降低时间复杂度， 用空间复杂度换取时间复杂度目的的方法。 把动态规划分为以下几步：
[1] 确定递推量。 这一步需要确定递推过程中要保留的历史信息数量和具体含义， 同时也会定下动态规划的维度；
[2] 推导递推式。 根据确定的递推量， 得到如何利用存储的历史信息在有效时间（通常是常量或者线性时间）内得到当前的信息结果；
[3] 计算初始条件。 有了递推式之后， 我们只需要计算初始条件， 就可以根据递推式得到我们想要的结果了。 通常初始条件都是比较简单的情况， 一般来说直接赋值即可
动态规划的时间复杂度是O（（维度）×（每步获取当前值所用的时间复杂度））

[一维] 最长递增子序列

状态转移方程：d(i) = max{1, d(j)+1},其中j<i,A[j]<=A[i]

1
2
3
4
5
6
7
8
9
10
11
int d[n];
   int len = 1;
   for (int i = 0; i < n; ++i) {
       d[i] = 1;
       for (int j = 0; j < i; ++j)
           if (right[j] <= right[i]) {
               d[i] = max(d[j] + 1, d[i]);
           }
       if (d[i] > len) len = d[i];
   }
cout << len;

[二维] 捡苹果

状态转移方程：S[i][j]=A[i][j] + max(S[i-1][j], if i>0 || S[i][j-1], if j>0)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int tmp[MAX][MAX] = {};

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            int a = 0, b = 0;
            if (i > 0) {
                a = tmp[i - 1][j];
            }
            if (j > 0) {
                b = tmp[i][j - 1];
            }
            tmp[i][j] = mat[i][j] + max(a, b);
        }
    }
    cout << tmp[m - 1][n - 1];


最短路径

[1] 自定义比较函数

1
2
3
4
5
struct pair_comparator {
    bool operator()(pair<int, int> &a, pair<int, int> &b) const {
        return a.second > b.second;
    }
};

[2] 读入unordered_map

1
2
3
4
5
6
7
8
9
10
11
12
inline void put_map(int source, int target, int distance, 
unordered_map<int, vector<pair<int, int>>>& edges){
        pair<int, int> edge(target, distance);
        if(edges.find(source) == edges.end()){
            vector<pair<int, int>> cur;
            cur.push_back(edge);
            edges[source] = cur;
        }
        else{
            edges[source].push_back(edge);
        }
    }

[3] 优先队列

1
2
#include <vector>
#include <queue>;

基本：priority_queue<int, vector<int>, greater/less<int> > que;
less 表示数字大的优先级高，而 greater 表示数字小的优先级高
重载：priority_queue<pair<int, int>, vector<pair<int, int>>, pair_comparator> next_vertex;


[4] 主要逻辑

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
int networkDelayTime(unordered_map<int, vector<pair<int, int>>> edges, int N, int K) {
    // 构建能到达的点的距离的最小堆  pair的内容是 name of the vertex -> distance
    priority_queue<pair<int, int>, vector<pair<int, int>>, pair_comparator> next_vertex;
    next_vertex.push(pair<int, int>(K, 0));
    // 记录已经到达的点及其距离
    unordered_map<int, int> reached;

    // 用于保存最远距离
    int last = 0;
    while (!next_vertex.empty()) {
        pair<int, int> cur = next_vertex.top();
        next_vertex.pop();
        // 已经遍历到了这个点  则舍去
        if (reached.find(cur.first) != reached.end()) {
            continue;
        }

        reached[cur.first] = cur.second;
        last = cur.second;
        // 如果这个点没有边，则找下一个点
        // c++ 的这个pointer 里面是一个pair (key, value) 在这里就是 pair (int, vector<pair<int, int>>)
        auto pointer = edges.find(cur.first);
        if (pointer == edges.end()) {
            continue;
        }

        for (pair<int, int> &next : (*pointer).second) {
            next_vertex.push(pair<int, int>(next.first, cur.second + next.second));
        }
    }

    if (reached.size() != N) {
        return -1;
    }

    return last;
}


Leetcode刷题小结

[1] Hamming Distance

比较两个数字的二进制不同位数的个数: Integer.bitCount(nums[i] ^ nums[j])


[2] Total Hamming Distance

For each bit position 1-32 in a 32-bit integer, we count the number of integers in the array which have that bit set. Then, if there are n integers in the array and k of them have a particular bit set and (n-k) do not, then that bit contributes k*(n-k) hamming distance to the total

1
2
3
4
5
6
7
8
9
for (int i = 0; i < 32; i++) {
    int bitCount = 0;
    for (int num : nums) {
        if (((num >> i) & 1) == 1) {
            bitCount++;
        }
    }
}
output += bitCount * (nums.length - bitCount);


[3] Counting Bits

numbers of 1 in i: f[i] = f[i / 2] + i % 2.


[4] Two Sum

Error: reference binding to null pointer of type 'value_type'
1.数组越界，在对vector初始化的时候没有初始化到合适大小，而在接下来的使用中使用了越界的下标。
2.对于vector构建出来的二维数组没有进行空间的申请,比如有些返回类型为vector>类型的函数，对于这个返回值vector表示的二维数组要先申请大小，否则就会报这类错误。
3.对于数组长度为0的情况没有进行判断


[5] Sum of two integers

Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.

1
2
3
4
5
6
while(a) {
            int x = a ^ b;
            a = (a & b) << 1;
            b = x;
        }
        return b;


[6] Find mode in binary search tree

1
2
3
4
5
6
7
8
9
10
11
12
void findMode(TreeNode* root, unordered_map<int, int> &map) {
       if(root == NULL) {
           return;
       }
       map[root -> val]++;
       if(root -> left != NULL) {
           findMode(root -> left, map);
       }
       if(root -> right != NULL) {
           findMode(root -> right, map);
       }
   }


参考资料

[1] vector: https://www.cnblogs.com/Nonono-nw/p/3462183.html
[2] unorderd_map: https://blog.csdn.net/hk2291976/article/details/51037095
[3] string: https://www.cnblogs.com/aminxu/p/4686320.html
[4] 动态规划: http://www.hawstein.com/posts/dp-novice-to-advanced.html
[5] 动态规划: https://blog.csdn.net/linhuanmars/article/details/38468361

← 卷积神经网络 清华九推 | 上交夏令营 | 南大夏令营面经 →