-
每周算法:两整数相除
leetcode算法题第29道,难度为medium。从题目描述上来看,这道题考察两数相除的计算,貌似很简单,但如果仔细研究下来,就会发现这道题所考察的知识很综合。
-
在EMACS中对目录进行独立配置
如果你曾经同时维护多个软件项目,每个软件项目的代码风格都有各自的偏好。举个常见的例子,项目A要求使用
tab
进行缩进,而项目B要求使用空格进行缩进,虽然这样的代码风格问题看起来无关紧要,但这确实是代码编写中实实在在的问题。本文无意于讨论两者风格的优劣,而是想介绍在EMACS中优雅地解决这个问题的方法。 -
每周算法:删去有序数组中的重复元素
leetcode算法题第26道,难度为easy,这是非常基础的一道题。
-
每周算法:调换链表中节点
leetcode算法第24题,难度为medium。将链表中的节点成对翻转,考察链表结构的理解和节点的操作。
-
每周算法:生成有效的括号组合
leetcode 算法题第22道,难度为medium,对指定数量的括号进行排列组合,列举出其中有效的结果。对括号的处理通常出现在表达式分析中,这道题目是了解括号表达式特性的很好切入点。
-
路由、调制解调器和交换机
路由、调制解调器和交换机,这三个是我们经常使用的网络设备。它们在网络中的作用是什么?它们工作在网络模型的哪一层?本篇文章将带你了解他们的原理与和区别。
-
每周算法:删去单向链表倒数第n个节点
leetcode算法题第19道,难度为medium,考察链表的基本操作。
-
IP协议(RFC791)
本文是IPv4协议的摘要和笔记,IPv4协议格式由RFC791规定,RFC791协议的原文可以在 这里 找到。
-
网络通信协议
本文总结了两种常见的网络模型,OSI模型和TCP/IP模型,并比较了二者之间的区别。
-
每周算法:四数之和
Description
Given an array
nums
of n integers and an integertarget
, are there elements a, b, c, and d innums
such that a + b + c + d =target
? Find all unique quadruplets in the array which gives the sum oftarget
.Note:
The solution set must not contain duplicate quadruplets.Example:
Given array nums = [1, 0, -1, 0, -2, 2], and target = 0. A solution set is: [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]
Solution
Apporach 1 暴力解法
将所有的组合穷举出来,与目标进行逐一比对,将满足条件的组合收集起来,就能得到结果。需要注意的是去除结果中的重复项。
vector<vector<int>> fourSum(vector<int>& nums, int target) { set<vector<int>> ans; for (size_t i = 0; i < nums.size(); ++i) { for (size_t j=i+1; j < nums.size(); ++j) { for (size_t k=j+1; k < nums.size(); ++k) { for (size_t m=k+1; m < nums.size(); ++m) { if (nums[i] + nums[j] + nums[k] + nums[m] == target) { vector<int> t({nums[i], nums[j], nums[k], nums[m]}); sort(t.begin(), t.end()); ans.insert(t); } } } } } return vector<vector<int>>(ans.begin(), ans.end()); }
Approach 2 拓展3sum算法
这道题的与之前的 3 sum 十分类似,通过简单的拓展就能得到该问题的解法。
vector<vector<int>> fourSum(vector<int>& nums, int target) { vector<vector<int>> ans; std::sort(nums.begin(), nums.end()); for (size_t i = 0; i < nums.size();) { int n1 = nums[i]; int target_1 = target - n1; for (size_t j=i+1; j<nums.size();) { int n2 = nums[j]; int target_2 = target_1 - n2; int front = j+1; int end = nums.size() - 1; while (front < end) { int n3 = nums[front]; int sum = n3 + nums[end]; if (sum == target_2) { ans.push_back(vector<int> ({n1, n2, n3, nums[end]})); do { ++front; } while(front < end && nums[front] == n3); } else if (sum > target_2) { --end; } else { ++front; } } do { ++j; } while (j<nums.size() && nums[j] == n2); } do { ++i; } while (i < nums.size() && nums[i] == n1); } return ans; }
Approach 3 优化的拓展3sum算法
在 approach 2 的基础上,增加一些边界条件判断,能够很大程度上提升算法的速度。下面的代码截取自leetcode,通过增加边界条件的判断,可以明显缩短代码的运行耗时。其中注释的代码是令一种较慢边界条件的判断方法,该代码的作者进一步优化了边界条件的判断逻辑。可以说,这种解法就是压榨算法的性能。这种优化方法是值得思考和学习的。
vector<vector<int>> fourSum(vector<int>& nums, int target) { vector<vector<int>> res; if (nums.size() < 4) return res; sort(nums.begin(), nums.end()); int len = nums.size(); for (int i = 0; i < len-3; i++) { //avoid duplicate if (i > 0 && nums[i] == nums[i-1]) continue; // if (nums[i] + nums[i+1] + nums[i+2] + nums[i+3] > target) break; // if (nums[i] + nums[len-3] + nums[len-2] + nums[len-1] < target) continue; //version3: less tight pruning if (4 * nums[i] > target) break; if (nums[i] + 3 * nums[len-1] < target) continue; for (int j = i+1; j < len-2; ++j) { if (j > i+1 && nums[j] == nums[j-1]) continue; // if (nums[i] + nums[j] + nums[j+1] + nums[j+2] > target) break; // if (nums[i] + nums[j] + nums[len-2] + nums[len-1] < target) continue; //version3: less tight pruning if (nums[i] + 3* nums[j] > target) break; if (nums[i] + nums[j] + 2 * nums[len-1] < target) continue; //now the problems becomes 3 sum problem and only two other elements only to be considered int left = j+1, right = len-1; int sofar = nums[i] + nums[j]; while (left < right) { if (sofar + nums[left] + nums[right] == target) { res.push_back(vector<int>({nums[i], nums[j], nums[left], nums[right]})); //how to skip the duplicate left and right //version1: my own version // left++; // right--; // while (left < right && nums[left-1] == nums[left]) ++left; // while (right > left && nums[right+1] == nums[right]) --right; //version2: refer others do{left++;} while (left < right && nums[left] == nums[left-1]); do{right--;} while (right > left && nums[right] == nums[right+1]); } else if (sofar + nums[left] + nums[right] < target) left++; else right--; } } } return res; }
-
广度优先搜索
引言
在求解 leetcode 17 时,我遇到了BFS(广度优先搜索)这个概念。在深入了解后发现,BFS是图(graph)的一个知识点,我对这一知识点进行展开学习,并将找到的资料汇总起来。本文主要整理了图和广度优先搜索的相关知识点。
图的存储方式
研究图就需要使用计算机语言对其进行描述。图的存储结构除了要存储图中各个顶点的本身的信息外,同时还要存储顶点与顶点之间的所有关系(边的信息)。因此,图的结构比较复杂,很难以数据元素在存储区中的物理位置来表示元素之间的关系,但也正是由于其任意的特性,故物理表示方法很多。常用的图的存储结构有邻接矩阵、邻接表、十字链表和邻接多重表。
相邻矩阵(adjacency martix)
对于一个具有
n
个顶点的图,可以使用n*n
的矩阵(二维数组)来表示它们间的邻接关系。下图中,矩阵A(i,j)=1
表示图中存在一条边(Vi,Vj)
,而A(i,j)=0
表示图中不存在边(Vi,Vj)
。实际编程时,当图为不带权图时,可以在二维数组中存放bool值,A(i,j)=true
表示存在边(Vi,Vj)
,A(i,j)=false
表示不存在边(Vi,Vj)
;当图带权值时,则可以直接在二维数组中存放权值,A(i,j)=null
表示不存在边(Vi,Vj)
。左图所示的是无向图的邻接矩阵表示法,可以观察到,矩阵延对角线对称,即
A(i,j)=A(j,i)
。无向图邻接矩阵的第i
行或第i
列非零元素的个数其实就是第i
个顶点的度。这表示无向图邻接矩阵存在一定的数据冗余。右图所示的是有向图邻接矩阵表示法,矩阵并不延对角线对称,
A(i,j)=1
表示顶点Vi
邻接到顶点Vj
;A(j,i)=1
则表示顶点Vi
邻接自顶点Vj
。两者并不象无向图邻接矩阵那样表示相同的意思。有向图邻接矩阵的第i
行非零元素的个数其实就是第i
个顶点的出度,而第i
列非零元素的个数是第i
个顶点的入度,即第i
个顶点的度是第i
行和第i
列非零元素个数之和。由于存在
n
个顶点的图需要n^2
个数组元素进行存储,当图为稀疏图时,使用邻接矩阵存储方法将出现大量零元素,照成极大地空间浪费,这时应该使用邻接表表示法存储图中的数据。邻接表(adjacency list)
邻接表(adjacency list)是一种常用的表示图的数据结构。邻接表是许多链表的集合,每个链表描述了一个顶点(
vectex
)的相邻元素(Neighbor
)。更形象地讲,邻接表是一个二维容器,第一维描述某个点,第二维描述这个点所对应的边集们。
图的邻接矩阵存储方法跟树的孩子链表示法相类似,是一种顺序分配和链式分配相结合的存储结构。邻接表由表头结点和表结点两部分组成,其中图中每个顶点均对应一个存储在数组中的表头结点。如这个表头结点所对应的顶点存在相邻顶点,则把相邻顶点依次存放于表头结点所指向的单向链表中。如下图所示,表结点存放的是邻接顶点在数组中的索引。对于无向图来说,使用邻接表进行存储也会出现数据冗余,表头结点A
所指链表中存在一个指向C
的表结点的同时,表头结点C
所指链表也会存在一个指向A
的表结点。有向图的邻接表有出边表和入边表(又称逆邻接表)之分。出边表的表结点存放的是从表头结点出发的有向边所指的尾顶点;入边表的表结点存放的则是指向表头结点的某个头顶点。如下图所示,图(b)和(c)分别为有向图(a)的出边表和入边表。
以上所讨论的邻接表所表示的都是不带权的图,如果要表示带权图,可以在表结点中增加一个存放权的字段,其效果如下图所示。
观察上图可以发现,当删除存储表头结点的数组中的某一元素,有可能使部分表头结点索引号的改变,从而导致大面积修改表结点的情况发生。可以在表结点中直接存放指向表头结点的指针以解决这个问题(在链表中存放类实例即是存放指针,但必须要保证表头结点是类而不是结构体)。在实际创建邻接表时,甚至可以使用链表代替数组存放表头结点或使用顺序表存代替链表存放表结点。本节所有的图片摘自 cnblogs.com - abatei
图的遍历
和树的遍历类似,在此,我们希望从图中某一顶点出发访遍图中其余顶点,且使每一个顶点仅被访问一次,这一过程就叫做图的遍历(traversing graph)。如果只访问图的顶点而不关注边的信息,那么图的遍历十分简单,使用一个
foreach
语句遍历存放顶点信息的数组即可。但如果为了实现特定算法,就需要根据边的信息按照一定顺序进行遍历。图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的基础。图的遍历要比树的遍历复杂得多,由于图的任一顶点都可能和其余顶点相邻接,故在访问了某顶点之后,可能顺着某条边又访问到了已访问过的顶点,因此,在图的遍历过程中,必须记下每个访问过的顶点,以免同一个顶点被访问多次。为此给顶点附设访问标志
visited
,其初值为false
,一旦某个顶点被访问,则其visited
标志置为true
。图的遍历方法有两种:一种是深度优先搜索遍历(depth first search 简称DFS),另一种是广度优先搜索遍历(breadth first search 简称BFS)。
广度优先搜索(breadth first search)
图的广度优先搜索遍历算法是一个分层遍历的过程,和二叉树的广度优先搜索遍历类同。它从图的某一顶点
Vi
出发,访问此顶点后,依次访问Vi
的各个未曾访问过的邻接点,然后分别从这些邻接点出发,直至图中所有已有已被访问的顶点的邻接点都被访问到。对于无向连通图,若顶点Vi
为初始访问的顶点,则广度优先搜索遍历顺序如下所示。广度优先搜索的伪代码如下:
BFS (G, s) // Where G is the graph and s is the source node let Q be queue. Q.enqueue( s ) // Inserting s in queue until all its neighbour vertices are marked. mark s as visited. while ( Q is not empty ) // Removing that vertex from queue, whose neighbour will be visited now v = Q.dequeue( ) // processing all the neighbours of v for all neighbours w of v in Graph G if w is not visited Q.enqueue( w ) // Stores w in Q to further visit its neighbour mark w as visited.
时间复杂度
BFS的时间复杂度为O(V+E)
,其中V
是节点的数量,E
是边的数量。BFS的应用场景
- 最短路径问题
- P2P网络,网络广播
- GPS导航系统
- 搜索引擎的网络爬虫
- 最短路径问题
-
每周算法:拨号键盘上的字符组合
Description
Given a string containing digits from
2-9
inclusive, return all possible letter combinations that the number could represent.A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.
1 2abc 3def 4ghi 5jkl 6mno 7pqrs 8tuv 9wxyz Example:
Input: "23" Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.Solution
Approach 1
借助加法计算进位的思想,下面是我的解法。我首次提交时并没有注意输入字符串为空的情况,对于输入参数的检查还是太容易忽略了。
vector<string> letterCombinations(string digits) { vector<string> ans; if (digits.empty()) { return ans; } vector<string> letters {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; vector<int> carry(nums.size(), 0); vector<int> nums; for (char ch : digits) { int n = ch - '0'; nums.push_back(n); } do{ string str; for (size_t i=0; i<carry.size(); ++i) { str += letters[nums[i]] [carry[i]]; } ans.push_back(str); int c = 1; for (int i=carry.size()-1; i >= 0; --i) { int d = carry[i] + c; if (d >= letters[nums[i]].size()) { carry[i] = 0; c = 1; } else { carry[i] = d; c = 0; break; } } if ( 1 == c) { break; } } while (1); return ans; }
我在想的是这个算法的时间复杂度是多少,感觉它的时间复杂度应该是O(n2)。
Approach 2 recursive
使用递归完成字符串的拼接,在每次递归,都会增加一个字符。终止递归的条件是字符串长度达到输入参数的长度。递归方法符合生活中的使用场景,还是比较容易理解的。
class Solution { char mMap[8][4] = { {'a', 'b', 'c', '#'}, {'d', 'e', 'f', '#'}, {'g', 'h', 'i', '#'}, {'j', 'k', 'l', '#'}, {'m', 'n', 'o', '#'}, {'p', 'q', 'r', 's'}, {'t', 'u', 'v', '#'}, {'w', 'x', 'y', 'z'}, }; public: vector<string> letterCombinations(string digits) { vector<string> result; backTrack(digits, result, "", 0); return result; } void backTrack(string &digits, vector<string> &result, string combination, int index) { if (index >= digits.length()) { if (combination.empty()) { return; } result.push_back(combination); return; } for (char c : mMap[digits[index] - '2']) { if (c == '#') continue; combination += c; backTrack(digits, result, combination, index+1); // 这里为什么要删去最后一个呢? // 因为之前在尾部追加了一个c combination.erase(combination.end() - 1); } } };
如何评估递归算法的时间复杂度和空间复杂度呢?Approach 3 BFS
宽度优先搜索,breadth-first search(BFS),是一种对树(tree)或图(graph)的遍历算法,下面就是这种算法的解法,代码使用java编写。
public List<String> letterCombinations(String digits) { LinkedList<String> ans = new LinkedList<String>(); if(digits.isEmpty()) { return ans; } String[] mapping = new String[] {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; ans.add(""); for(int i=0; i<digits.length(); i++) { int x = Character.getNumericValue(digits.charAt(i)); while(ans.peek().length() == i) { String t = ans.remove(); // remove是从头部删去一个元素 for(char s : mapping[x].toCharArray()) { ans.add(t+s); // add是向尾部添加一个元素 } } } return ans; }
下面是另外一种使用BFS算法实现的解法
public List<String> letterCombinations(String digits) { LinkedList<String> ans = new LinkedList<String>(); if(digits.isEmpty()) { return ans; } String[] mapping = new String[] {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; ans.add(""); while(ans.peek().length() != digits.length()){ String remove = ans.remove(); String map = mapping[digits.charAt(remove.length())-'0']; for(char c: map.toCharArray()){ ans.addLast(remove+c); } } return ans; }
Reference