今年下雨真是太不便了我哭声响彻天际

基础学习笔记，跟着w3school的教程

如果之后找到了更系统的教学视频也可能会跟着视频看

普适思想

1. coding style
2. 考虑全面各种情况（第一步永远是边界检测）
3. bug free
4. 交流-思考-渐进的过程

例题：strstr

重点：不要总想着kmp算法，因为它仅仅只是一个算法

第一步库函数(int pos = haystack.find(needle);)

第二步暴力解法 (for循环嵌套)

第三步优化

递归recursion的思想

重点：使用深度优先搜索DFS实现递归==使用回溯的思想。

递归的三个要素：

第一步：定义要用递归完成的事情

第二步： 如何将问题变为子问题

第三步： 什么时候退出递归（什么时候给返回值）

使用深度优先搜索的情境or排列组合模板总结：

• 适用范围：几乎所有的搜索问题
• 需要做出的改动：1. 什么时候输出；2. 哪些情况需要跳过
• 试着举例：
  • permutations/unique permutations
  • combination sum/letter combination of a phone number
  • palindrome partitioning
  • restore ip address

例题：subsets

两种解法需要掌握：

1. 递归实现DFS

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

   void helper(vector<vector<int> >& res, vector<int> tmp, vector<int>& nums, int level) { if (level >= nums.size()) { res.push_back(tmp); return; } tmp.push_back(nums[level]); helper(res, tmp, nums, level + 1); tmp.pop_back(); helper(res, tmp, nums, level + 1); } vector<vector<int>> subsets(vector<int>& nums) { vector<vector<int> > res; vector<int> tmp; helper(res, tmp, nums, 0); return res; }

2. 考虑层序遍历求解，每次加入一个元素就扩充res的长度，直到所有元素添加完毕

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

   class Solution { public: vector<vector<int>> subsets(vector<int>& nums) { vector<vector<int> > res(1); for(int i=0;i<nums.size();i++){ int cnt=res.size(); for(int j=0;j<cnt;j++){ vector<int> tmp=res[j]; tmp.push_back(nums[i]); res.push_back(tmp); } } return res; } };

3. 二进制位运算解法

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

   class Solution { public: vector<vector<int>> subsets(vector<int>& nums) { int S = nums.size(); int N = 1 << S; vector<vector<int> > res; for (int i = 0; i < N; ++i) { vector<int> v; for (int j = 0; j < S; ++j) if (i & (1 << j)) v.push_back(nums[j]); res.push_back(v); } return res; } };

基础算法问题的 Time Complexity

O(1) 极少

O(logn) 几乎都是二分法

O(n) 遍历

O(nlogn) 一般都需要排序

O(n²) 数组、枚举、动态规划

O(n^3)数组、枚举、动态规划

O(2^n) 与组合有关的搜索

O(n!) 与排列有关的搜索

二分法binary search的思想

二分法中的循环仅仅是为了缩小范围，而不是获得结果，二分法的核心就是将答案的范围缩小。

** 比O(n)更优的时间复杂度几乎只能是O(logn)的二分法**。

T(n) = T(n/2) + O(1) = O(logn)

通过O(1)的时间把规模为n的问题变为n/2=O(logn)

通过O(n)的时间把规模为n的问题变为n/2=O(n)

recursion or Loop？

一般使用loop，因为recursion涉及到了调用栈，占用内存较大，所以recursion不是常用解决办法。但如果recursion会更简单，可以先用recursion解决。

通用的二分法模板：

1. while (start + 1 < end)
   • 不用start < end 或 start <= end 或start + 1 <= end 是为了防止死循环，确保在只剩最后两个数时就开始做判断
2. int mid = start + (end - start)/2
   • 不用(start + end)/2是为了防止溢出，因为int型最大只有2^32-1
3. A[mid] == , < , >
   • 不管是否可以<=或>=，都先判断三种情况，以确保条件判断正确。
4. A[start] , A[end] ? target
   • first-pos-of-target时先判断start；last-pos时先判断end
5. start = mid
   • 不使用mid + 1是为了防止死循环（极端情况只有两个数时）
6. end = mid

例题：binary-search

/first-or-last-pos-of-target

/search-a-2d-matrix

/search-insert-pos

/search-in-a-infinite-sorted-array

/search-a-rotated-sorted-array

/Find-peak-element

二叉树

T(n) = 2T(n/2) + O(1) = O(n)

T(n) = 2T(n/2) + O(n) = O(nlogn)

前中后序遍历

1. 递归方法

   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

   typedef struct BiTNode{ TElemType data;//数据 struct BiTNode *lchild, *rchild;//左右孩子指针 } BiTNode, *BiTree; /*二叉树的前序遍历递归算法*/ void PreOrderTraverse(BiTree T) { if(T==NULL) return; printf("%c", T->data); /*显示结点数据，可以更改为其他对结点操作*/ PreOrderTraverse(T->lchild); /*再先序遍历左子树*/ PreOrderTraverse(T->rchild); /*最后先序遍历右子树*/ } /*二叉树的中序遍历递归算法*/ void InOrderTraverse(BiTree T) { if(T==NULL) return; InOrderTraverse(T->lchild); /*中序遍历左子树*/ printf("%c", T->data); /*显示结点数据，可以更改为其他对结点操作*/ InOrderTraverse(T->rchild); /*最后中序遍历右子树*/ } /*二叉树的后序遍历递归算法*/ void PostOrderTraverse(BiTree T) { if(T==NULL) return; PostOrderTraverse(T->lchild); /*先后序遍历左子树*/ PostOrderTraverse(T->rchild); /*再后续遍历右子树*/ printf("%c", T->data); /*显示结点数据，可以更改为其他对结点操作*/ }

2. 非递归方法-利用栈进行遍历

   前序

   1 2 3 4 5 6 7 8 9 10

   栈S; p= root; while(p || S不空){ while(p){ 访问p节点； p的右子树入S; p = p的左子树; } p = S栈顶弹出; }

   1 2 3 4 5 6 7 8 9 10 11 12 13 14

   vector<int> preorderTraversal(TreeNode* root) { stack<TreeNode*> S; vector<int> v; TreeNode* rt = root; while(rt || S.size()){ while(rt){ S.push(rt->right); v.push_back(rt->val); rt=rt->left; } rt=S.top();S.pop(); } return v; }

   后序

   1 2 3 4 5 6 7 8 9 10 11

   栈S; p= root; while(p || S不空){ while(p){ 访问p节点； p的左子树入S; p = p的右子树; } p = S栈顶弹出; } 结果序列逆序;

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

   vector<int> postorderTraversal(TreeNode* root) { stack<TreeNode*> S; vector<int> v; TreeNode* rt = root; while(rt || S.size()){ while(rt){ S.push(rt->left); v.push_back(rt->val); rt=rt->right; } rt=S.top();S.pop(); } reverse(v.begin(),v.end()); return v; }

   中序

   1 2 3 4 5 6 7 8 9 10 11

   栈S; p= root; while(p || S不空){ while(p){ p入S; p = p的左子树; } p = S.top 出栈; 访问p; p = p的右子树; }

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

   vector<int> inorderTraversal(TreeNode* root) { stack<TreeNode*> S; vector<int> v; TreeNode* rt = root; while(rt || S.size()){ while(rt){ S.push(rt); rt=rt->left; } rt=S.top();S.pop(); v.push_back(rt->val); rt=rt->right; } return v; }

层次遍历（BFS-Queue）

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

typedef struct Node{						//定义二叉链
	struct Node *lchild;					//指向左孩子节点
	char data;								//数据元素
	struct Node *rchild;					//指向右孩子节点 
}BTNode;									//struct Node 的别名						 

typedef struct Quene{						//定义顺序队 
	int front;								//队头指针 
	BTNode *data[MaxSize];					//存放队中元素 
	int rear;								//队尾指针 
}SqQueue; 									//struct Queue 的别名 

//初始化队列 
void initQueue(SqQueue * &q){
	q=(SqQueue *)malloc(sizeof(SqQueue));	//分配一个空间 
	q->front=q->rear=-1;					//置 -1 
}

//判断队列是否为空
bool emptyQueue(SqQueue * &q){
	if(q->front==q->rear){					//首指针和尾指针相等，说明为空 
		return true;						//返回真 
	}
	else{
		return false;						//返回假 
	}
}

//进队列
bool enQueue(SqQueue * &q,BTNode * &BT){
	if(q->rear==MaxSize-1){					//判断队列是否满了 
		return false;						//返回假 
	}
	q->rear++;								//头指针加 1 
	q->data[q->rear]=BT;					//传值 
	return true;							//返回真 
}

//出队列 
bool deQueue(SqQueue * &q,BTNode * &BT){
	if(q->front==q->rear){					//判断是否空了 
		return false;						//返回假 
	}
	q->front++;								//尾指针加 1 
	BT=q->data[q->front];					//取值 
	return true;							//返回真 
}

void levelOrder(BTNode * &BT){
	SqQueue *q;									//定义队列 
	initQueue(q);								//初始化队列 
	if(BT!=NULL){
		enQueue(q,BT);							//根节点指针进队列 
	} 
	while(emptyQueue(q)!=true){					//队不为空循环 
		deQueue(q,BT);							//出队时的节点 
		printf("%c",BT->data);					//输出节点存储的值 
		if(BT->lchild!=NULL){					//有左孩子时将该节点进队列 
			enQueue(q,BT->lchild);
		}
		if(BT->rchild!=NULL){					//有右孩子时将该节点进队列 
			enQueue(q,BT->rchild);
		}										//一层一层的把节点存入队列 
	} 											//当没有孩子节点时就不再循环 
}

maxlength/minlength of B-tree : Traverse or Divide-Conquer

• 分治的方法优于遍历的方法

  这是因为分治不会一直传结果，而遍历会把结果当成参数传下去，造成冗余。

  

动态规划

链表 linked-list

声明：

1
2
3
4
5
6
7

//
struct CacheNode {
    int key;
    int value;
    CacheNode *pre, *next;
    CacheNode(int key, int value):key(key), value(value), pre(NULL), next(NULL){}
};

Dummy Node

1
2

ListNode* result = new ListNode(0);
result->next = head;

两两翻转链表

主体：

1
2
3
4
5
6
7
8

while (p != NULL && p->next != NULL){
    q = p->next;
    p->next = q->next;
    q->next = p; //q->next = pre->next;
    pre->next = q;
    pre = p;
    p = p->next;     
}

k个一组翻转链表

主体：

1
2
3
4
5
6
7
8
9
10
11
12

for (i = 0; i < loopNum; i++){
    for (j = 0; j < k-1; j++){
        if (p != NULL && p->next != NULL){
            q = p->next;
            p->next = q->next;
            q->next = pre->next;
            pre->next = q;
        }
     }
     pre = p;
     p = p->next;
}

全部：

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

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        if (head == NULL || k <= 0){
            return nullptr;
        }
        int count = 0;
        
        ListNode* cur = head;
        
        while (cur != NULL){
            count++;
            cur = cur->next;
        }
        
        int loopNum = count/k;
        int i, j;
        ListNode* result = new ListNode(0);
        result->next = head;
        ListNode* pre = result;
        ListNode* p = head;
        ListNode* q = head;
        for (i = 0; i < loopNum; i++){
            for (j = 0; j < k-1; j++){
                if (p != NULL && p->next != NULL){
                    q = p->next;
                    p->next = q->next;
                    q->next = pre->next;
                    pre->next = q;
                    }
            }
            pre = p;
            p = p->next;
        }
      
        return result->next;
    }
};

快慢指针

删除倒数第k个节点

数组 array

声明：

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

//type arrayname[arraysize];
int array[10] = {1000.0, 2.0, 3.4, 7.0, 50.0};
//vector容器
vector<int> a1;
vector<int> a2(2, -1);  //2个int元素值均初始化为-1
vector<int> a3(10);  //10个int元素值均初始化为0
vector<string> svec1 ={"the", "three", "kingdoms"};
vector<string> svec2(10);  //10个string对象初始化为空

v.push_back(temp);  //向vector中添加元素
v.empty();  //检查是否为空
v.capacity();  //返回当前vector中最大可以存储数据的容量
v.begin();v.end();  //
v.size();  //返回v中元素的个数
v[n];  //获取v中第n个元素
//特别注意：对于一个空的vector,不能使用下标向其中添加元素。只能使用push_back. 只能对确知已存在的元素执行下标操作。
vector<int>::iterator it;  //it是能读写的vector中的元素
string::iterator it1;  //it1是能读写的string对象中的字符

//字符串
char string[10] = {'h', 'e', 'l', 'l', 'o','\0'};
char string2[] = {"hello"};

strcpy(s1,s2);  //复制s2到s1
strcat(s1,s2);  //连接s2到s1末尾
strlen(s1);  //长度 
strcmp(s1,s2);  //比较

双指针问题（Two Sum）

• two sum可以用hash做，也可以用相向双指针做

• three-sum/two-sum-closest 用相向双指针

• partition-array 思想和快排类似，典型题可以分为两部分和三部分

  1 2 3 4 5 6 7 8 9 10 11 12 13 14

  while (i <= j) { while (i <= j && a[i] < target) { i++; } while (i <= j && a[j] >= target) { j--; } if (i <=j) { swap(a[i], a[j]); i++; j--; } } return j+1;

SubArray

• best time to buy and sell stock/数飞机/Maximum Array
  • prefix sum问题

Sorted Array

• merge-two-sorted-array

  • 一是可以开辟新空间的
  • 二是存在同一个数组中的，反向比较

• 两个有序数组中的中位数/第k个数

  • 一是O(m+n)的双指针寻找

  • 二是O(logn)的二分法，两个数组的前k/2

    1 2 3 4

    比较nums1[k/2]和nums2[k/2]的大小 小的那个数组count+k/2； k = k - k/2; 直到取到第k个

• 数组内积（点乘）
• intersection-可以用哈希

数据结构

Queue == BFS

支持操作：O(1) push; O(1) pop; O(1) top

Stack == DFS

支持操作：O(1) push; O(1) pop; O(1) top

数据结构实现题/非递归问题（DFS问题）/单调栈问题

例题：min stack

构造一个存放最小值的栈，同步更新

例题：largest rectangle in histogram

例题：两个栈做一个队列两个队列做一个栈

HASH

实现原理，减小冲突： array+list形式；多个hash function；

rehashing很复杂所以要避免！

支持操作：O(1) insert; O(1) find; O(1) delete

构造：

1
2
3
4
5
6
7
8
9

// 定义一个map对象
map<int, string> mapStudent; 
// 第一种 用insert函數插入
pairmapStudent.insert(pair<int, string>(000, "student_zero")); 
// 第二种 用insert函数插入value_type数据
mapStudent.insert(map<int, string>::value_type(001, "student_one")); 
// 第三种 用"array"方式插入
mapStudent[123] = "student_first";
mapStudent[456] = "student_second";

查找：

1
2
3
4
5
6
7

map<int,CacheNode*>::iterator it = mp.find(key);
// find 返回迭代器指向当前查找元素的位置否则返回map::end()位置
iter = mapStudent.find("123"); 
if(iter != mapStudent.end())       
    cout<<"Find, the value is"<<iter->second<<endl;
else   
    cout<<"Do not Find"<<endl;

删除：

1
2
3
4
5
6
7
8
9

//迭代器刪除
iter = mapStudent.find("123");
mapStudent.erase(iter); 
//用关键字刪除
int n = mapStudent.erase("123"); 
//如果刪除了會返回1，否則返回0 
//用迭代器范围刪除 : 把整个map清空
mapStudent.erase(mapStudent.begin(), mapStudent.end());
//等同于mapStudent.clear()

其他基本函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

C++ maps是一种关联式容器，包含“关键字/值”对

begin()         返回指向map头部的迭代器
empty()         如果map为空则返回true
end()           返回指向map末尾的迭代器
size()          返回map中元素的个数
count()         返回指定元素出现的次数
    
equal_range()   返回特殊条目的迭代器对
get_allocator() 返回map的配置器
key_comp()      返回比较元素key的函数
lower_bound()   返回键值>=给定元素的第一个位置
max_size()      返回可以容纳的最大元素个数
rbegin()        返回一个指向map尾部的逆向迭代器
rend()          返回一个指向map头部的逆向迭代器
swap()           交换两个map
upper_bound()    返回键值>给定元素的第一个位置
value_comp()     返回比较元素value的函数

Hash Table/Hash Map/Hash Set的区别是什么？

hash table支持多线程

多线程的producer/ consumer模式

LRU-cache算法

hashmap<key, DoublyListNode>;

Heap == Priority Queue

支持操作：O(logn) add; O(logn) remove; O(1) min or max

例题：ugly-number

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

O(n)
heap + hashmap O(nlogn)
queue<long> Q;
vector<long> primes;
primes = {3,5,7};
hashmap<long,Boolean> mp;
for (int i = 0; i < 3; i++){
    Q.add(primes[i]);
    mp.put(primes[i],true);
}
long number = long.value?;
for (int i = 0; i < n; i++){
    number = Q.?();
    for (int j = 0; j < 3; j++){
        if (!mp.containskey(primes[j]*number){
            Q.add(number*primes[j]);
            mp.put(number*primes[j],true);
        }
    }
}
return number;

例题：top-k-largest-numbers

例题：data-stream-median

例题：merge-k-sorted-list/array

堆排序

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
49
50
51

#include <stdio.h>

void heapify (int tree[], int n, int i){
    if (i >= n) {
        return;
    }
    int max = i;
    int c1 = 2*i + 1;
    int c2 = 2*i + 2;
    if (c1 < n && tree[c1] > tree[max]) {
        max = c1;
    } 
    if (c2 < n && tree[c2] > tree[max]) {
        max = c2;
    }
    if (max != i) {
        swap(tree, max, i);
        heapify(tree, n, max);
    } 
}    

void build_heap (int tree[], int n) {
    int last_node = n - 1;
    int parent = (last_node-1)/2;
    int i;
    for (i = parent; i >= 0; i--) {
        heapify(tree, n, i);
    }
}

void heap_sort (int tree[], int n) {
    build_heap(tree,n);
    int i;
    for (i = n-1; i >= 0; i--) {
        swap(tree, i, 0);
        heapify(tree, i, 0);
    }
}

int main() {
    int tree[] = {10,6,5,4,1,3};
    int n = 6;
    // heapify(tree, n, 0);
    // build_heap(tree, n);
    // heap_sort(tree, n);
    int i;
    for (i = 0; i < n; i++) {
        printf(“%d\n”,tree[i]);
    }
    return 0;
}

本文献给跟我一样虽然屁都不会但是谜一样的自信地投了软开岗位的旁友们

希望我们都能获得尘世间的幸福

编程基础和操作系统

所有我还记得的知识点

今日考卷题

选择

1. 执行命令chmod 746 file.txt该文件的权限是？

   r：4

   w：2

   c：1

   rwc_r–_rw-

2. 需要找出/etc/my.conf文件属于哪个包（package）可以执行？

3. 新用户创建主目录时自动复制的文件目录是？

   /etc/

4. 在bash中，在一条命令后加入“1>&2”意味着？

5. 哪个命令可以压缩部分文件？

   tar-

6. 定义bash环境的用户文件是？

7. 具有很多C语言功能，又称过滤器的是？

8. 取ls -l输出结果的第5列的值的正确写法是？

9. shell程序里，判断文件不存在的写法是？

填空

1. linux系统中，以文件方式访问设备。

2. linux系统有根分区和交换分区两种分区类型。

3. DNS实际上是分布在Inernet上的主机信息的数据库，其作用是实现IP和主机名之间的转换。

4. 文件权限为d-rw-_r—_r—，用数值形式表示该权限，则该八进制数为：644，该文件属性是655。

5. vi编辑器有命令和文本输入两种工作模式。

6. 进程和程序的区别在于其动态性，动态的产生和终止，从产生到终止进程可以具有的基本状态为：运行态、就绪态和阻塞态。

7. 硬链接只能建立对文件链接，软链接即符号链接可以跨越不同文件系统。

8. 手工方法配置网络时，可以通过修改/etc/hostname文件来修改主机名，如果要配置计算机的域名解析客户端，需要配置/etc/reslov.conf文件

9.可以用ls -al命令来观察文件的权限，每个文件的权限都用10位表示，并分为4段，其中第一段占1位，表示文件类型，第二段占3位，表示文件所有者对该文件的权限。

问答

1. linux系统优化的一些步骤。

2. 写一个脚本，脚本名dellog.sh，脚本放在/data/scripts目录下，要求是清理目录/data/logs下的7天前的以.log结尾的文件。创建定时任务，每天凌晨1点30执行。

简陋，并且随时增加