毕业半年, 平时工作总是关注业务、架构，而却越来越少关注性能, 也再也没有做过任何涉及算法的工作了
希望有时间把这些拉下的东西拾起来，毕竟不论是使用什么语言，从事什么行业，只要是程序员，算法才是真正的基础。
题目来自leetcode，代码语言通常为C/C++，后期可能个别题目会用Golang
每道题都会阐述尽可能多的思路及不同思路的效率对比，以及每种思路的代码实现
万事开头难，但坚持下去其实更难。
(2018.2.3)
题目1：给定和，获取加数
描述： 给定一个整数数组，以及一个整数，已知这个整数是数组内某两个元素的和，现在需要找到，并返回这两个元素的索引，例如：
整数数组：{11, 7, 12, 2}
整数 ：9
返回结果：{1, 3}
（假定结果一定存在于给定数组，并且不需要考虑存在多组结果）
题目链接：https://leetcode.com/problems/two-sum/description/
解答：
解法1：
最传统的方法就是挨个查找，判断结果，具体步骤是：
每一趟都从下图第一个元素(11)开始， 固定住第一个元素不变，计算当前元素与其后每个元素的值之和，判断是否等于目标整数
这种方法，最坏的情况下，数组内每一对元素都会被计算一次，因此时间复杂度为O(N * N)
代码：
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> ret;
int sz = nums.size();
for(size_t i = 0; i < sz - 1; ++i) {
for(size_t j = i + 1; j < sz; ++j) {
if(nums[i] + nums[j] == target) {
ret.push_back(i);
ret.push_back(j);
return ret;
}
}
}
return ret;
}解法2：
上面的贪婪法可以将步骤分解为两部分，外层循环和内层循环，每当外层循环执行一步，内层循环都需要逐个遍历剩下的元素，执行一趟时间复杂度为O(N)的过程，在整个过程中，外层循环是无法优化的，而内层的循环作为优化，可以考虑用空间换取时间的思路：即事先对整个数组建立索引，使得每一趟的内层循环不再是遍历，而是精确查找，使得算法的时间复杂度由O(N*N)变为O(N*1)
具体步骤是：
代码：
// O(n)
vector<int> twoSum_better1(vector<int>& nums, int target) {
int sz = nums.size();
map<int, int> dic_map;
// 先建立索引
for(size_t i = 0; i < sz; ++i) {
dic_map[nums[i]] = i;
}
vector<int> ret;
// 开始查找
for(size_t i = 0; i < sz; ++i) {
int pos_val = target - nums[i]; // 要查找的数据
int pos_key = dic_map[pos_val];
if(pos_key != i && (nums[i] + nums[pos_key]) == target ) { // 找到
ret.push_back(i);
ret.push_back(pos_key);
break;
}
}
return ret;
}解法3（建立索引的过程可以分解到外层循环的每一步当中）：
一开始无索引，每一步都在索引中查找目标元素，如果没有，则将当前元素存入索引，并迭代至下一步
代码：
// O(n), 速度最优, 但整体跟上一种方法在同一数量级内
vector<int> twoSum_better2(vector<int>& nums, int target) {
int sz = nums.size();
map<int, int> dic_map;
vector<int> ret;
// 开始查找
for(size_t i = 0; i < sz; ++i) {
int pos_val = target - nums[i]; // 要查找的数据
int pos_key = dic_map[pos_val];
if(pos_key != i && (nums[i] + nums[pos_key]) == target) {
ret.push_back(i);
ret.push_back(pos_key);
break;
}else {
dic_map[nums[i]] = i; // 添加索引
}
}
return ret;
}总结：
坑：
比较少
优化：
比较1、2、3方法，
1方法时间复杂度为O(N*N)，最低效,
2、3方法整体时间复杂度都是O(N)，区别在于 2方法是在一开始就建立了完整的索引，而3方法则是在迭代的过程中逐步建立索引
在悲观的情况下，2、3方法效率是相同的
在乐观的情况下，3方法只需要向索引中存放一个元素，因此相对来说更高效
题目2：链表求和
描述： 给定两个非空链表，每个链表代表一个整数，而链表的每个结点则代表每一位，此外规定链表为倒序排列，求两链表所代表的正数之和对应的链表。例如：
整数链表：( 2->4->3 ) + ( 5->6->4 ) (相当于 342 + 465 )
返回结果：(7->0->8) (相当于 807 )
链表结点：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/题目链接：https://leetcode.com/problems/add-two-numbers/description/
解答：
解法一：（不完全正确的方法）
step1：分别遍历两链表，按照倒序转化的规则将两个链表转化成两个整数 O(N) * 2 (借助栈)
step2: 两个整数相加 O(1)
step3: 相加之和转化为链表 O(N)
代码：
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
stack<int> s1;
stack<int> s2;
// l1、l2元素入栈
ListNode* p1 = l1;
ListNode* p2 = l2;
while(p1 != NULL) {
s1.push(p1->val);
p1 = p1->next;
}
while(p2 != NULL) {
s2.push(p2->val);
p2 = p2->next;
}
// 统计两加数之和
long count1 = 0;
long count2 = 0;
while(!s1.empty()) {
count1 = s1.top() + 10 * count1;
s1.pop();
}
while(!s2.empty()) {
count2 = s2.top() + 10 * count2;
s2.pop();
}
long sum = count1 + count2;
// 生成新链表
long res = sum;
ListNode* ret_node = NULL;
ListNode* pos = NULL;
if(res == 0) {
ListNode* ret_node = new ListNode(0);
return ret_node;
}
while(res != 0) {
int unit = res % 10;
res = res / 10;
if(ret_node == NULL) {
ret_node = new ListNode(unit);
pos = ret_node;
}else {
ListNode* next_node = new ListNode(unit);
pos->next = next_node;
pos = next_node;
}
}
return ret_node;
}总的时间复杂度为：
3 * O(N) + O(1) ~= O(N)
但是当两链表所表示的整数非常大，将会导致×××溢出，因此这种方法是有问题的
解法二：
同时遍历两个链表，遍历的同时进行相加，生成新的链表。思路就像笔算求解多位数之和的过程，比较简单，主要需要考虑下面几种情况即可：
进位问题；
当前位置两数都有值的情况；
当前位置一个数有值一个数没有值的情况；
代码：
ListNode* addTwoNumbers_better(ListNode* l1, ListNode* l2) {
ListNode* ret_head = NULL;
ListNode* pcur = NULL;
ListNode* p1 = l1;
ListNode* p2 = l2;
int addi = 0; // 进位符
while(p1 != NULL || p2 != NULL) {
int cur = addi;
if(p1 != NULL) {
cur += p1->val;
p1 = p1->next;
}
if(p2 != NULL) {
cur += p2->val;
p2 = p2->next;
}
if(cur > 9) {
addi = 1;
cur %= 10;
}else {
addi = 0;
}
ListNode* newNode = new ListNode(cur);
if(ret_head == NULL) {
ret_head = newNode;
pcur = newNode;
}else {
pcur->next = newNode;
pcur = pcur->next;
}
}
if(addi == 1) {
ListNode* newNode = new ListNode(1);
if(ret_head == NULL) {
ret_head = newNode;
pcur = newNode;
}else {
pcur->next = newNode;
pcur = pcur->next;
}
}
return ret_head;
}总结：
坑：
需要考虑到溢出问题，不然就踩坑了
优化：
O(N), 优化空间比较小
题目3：字符串获取最长无重复子串的长度
描述： 给定某个字符串，计算其中所有子串中，最长的那个无重复字符的字串的长度。例如：
给定字符串“abcabcbb”， 最长无重复子串是“abc”，长度为3
给定字符串“bbbbb”， 最长无重复子串是“b”，长度为1
给定字符串“pwwkew”， 最长无重复子串是“wke”，长度为3
题目链接：https://leetcode.com/problems/longest-substring-without-repeating-characters/description/
解答：
方法一：（穷举法）
思路就是列出给定的字符串的所有子串(两层循环即可)，然后筛选出其中的所有无重复的字串，然后取出其中最长的一条
简单粗暴，效率最低，时间复杂度O(N^2)
代码略
方法二：（贪婪法）
遍历一遍字符串，计算每个字符往后的最长无重复子串，统计出其中最大值。
具体分解成两层循环，外层循环遍历每个元素，
内层循环从当前元素开始往后遍历，计数，直到遇到第一个重复字符为止，为了性能，需要维护一个map供内层循环判断重复字符使用，下面是代码：
int lengthOfLongestSubstring(string s) {
// 贪婪法
map<char, int> s_map;
int max = 0;
int cur = 0;
for(string::iterator s_it = s.begin(); s_it != s.end(); ++s_it) {
for(string::iterator s_itn = s_it; s_itn != s.end(); ++s_itn) {
if(s_map[*s_itn] != 0) { // 有重复
if(cur > max) {
max = cur;
}
cur = 0;
s_map.clear();
break;// 结束循环
}else {
cur += 1;
s_map[*s_itn] = 1;
}
// (坑2)此处的判断是必须的
if(cur > max) {
max = cur;
}
}
}
return max;
}进一步优化
相比穷举法，这种方法的性能要高出不少，但是总的来说性能依然不够理想，主要体现在：
1、本质上还是内外两层循环
2、查找字符时用的集合是map，因此查找效率为O(logN)，而每个字符的范围是已知的(0~255)，因此可以用一个数组作为查找集合，查找效率将可以提升为O(1)
解法3（滑动窗口）：
首先采用一个长度为256的顺序表作为查找集合，这样就可以将查找的时间复杂度降低为O(1)
同时维护两个指针(或者说索引)，一前一后协同者往后遍历，遍历的过程中寻找两索引的最大距离，就好像一个可以伸缩的窗口在不断遍历，这样就可以将两层遍历减少为一层，时间复杂度由O(N*N) 降低为 O(N)
具体步骤如下图：
p(head)为窗口的前指针，q(tail)为窗口的后指针，窗口移动的过程循环可以分解成两步：
step1：先向前移动p，不断拉长窗口，直到遇到重复的字符； （扩大阶段）
step2：遇到重复的字符，这时候就需要向前移动q，逐步缩小窗口长度，直到将这个重复的元素剔除； （缩小阶段）
在移动的过程中记录保存p、q的间距(最大值)
这种方法的整体时间复杂度为 2 * O(N) ≈ O(N)
这种方法的实现代码如下：
int lengthOfLongestSubstring_better(string s) {
vector<int> s_vec(256, 0);
int max = 0;
int head = 0;
int tail = 0;
int length = s.length();
while(head < length && tail < length) {
char head_val = s[head];
char tail_val = s[tail];
if(0 == s_vec[head_val]) { // 扩大阶段
++s_vec[head_val];
++head;
max = (head - tail) > max ? (head - tail) : max;
}else { // 缩小阶段
s_vec[tail_val] = 0;
++tail;
}
}
return max;
}解法4（上一种解法的深度优化）：
上一种方法的缩小阶段其实是没必要的，我们可以直接在查找集合中存入相应的记录，这样每次缩小阶段，就可以直接将tail指针跳到上一次出现的该字符的位置，时间就能由O(N)缩减为O(1)了
代码如下：
int lengthOfLongestSubstring(string s) {
vector<int> s_vec(256, 0);
int length = s.length();
int max = 0;
for(size_t head = 0, tail = 0; head < length; ++head) {
char head_val = s[head];
tail = s_vec[head_val] > tail ? s_vec[head_val] : tail; // 跳转到head_val字符出现的下一个位置
max = (head - tail + 1) > max ? (head - tail + 1) : max;
s_vec[head_val] = head + 1; // (永远记录head_val字符出现的下一个位置)
}
return max;
}总结：
后面3种优化方法本质上其实都是贪婪法的思路，这个题目如果不仔细思考，很难一步到位得到最优算法~
坑：
坑比较少
优化：
优化空间较大
题目4：获取两排序数组的中值
描述： 给定两个排序好的数组（升序排序），计算两个数组内所有数的中值。例如：
给定数组1 : [1, 3], 数组2 : [2] , 计算结果为：2
给定数组1 : [1, 2], 数组2 : [3, 4] , 计算结果为：2.5
题目链接：https://leetcode.com/problems/median-of-two-sorted-arrays/description/
解答：
解法1：
最直接的做法就是对这两个数组进行排序，最直接的做法是创建一个临时数组（或者堆），将两个数组中的所有元素都存放进去，然后对这个数组进行排序，并找出中值，这种方法的时间复杂度为
采用临时数组方式：遍历一遍O(N) + 排序O(log2N) ，实现代码略
采用堆的方式： 遍历一遍 & 建堆O(N) + 查找O(log2N)
解法2（双指针一趟(半趟)遍历）：
已知两个数组都是排序好的，那么其实可以根据这个特性进行优化，将时间复杂度降低为O(N)
思路是：维护两个指针及一个计数器，按从小到大的顺序遍历两数组，每一步遍历计数器加1，直到计数器加到中值。
非递归实现代码如下：
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
// 中间位置的确定 (奇or偶 & 各自的位置)
int length2 = nums1.size();
int length3 = nums2.size();
int total = length2 + length3;
int pos1 = 0;
int pos2 = 0;
bool is_odd = true; // 奇数
int val1 = 0;
int val2 = 0;
if(total % 2 == 0) { // 总数为偶数, 取中间两位数的平均值
pos1 = total / 2 - 1;
pos2 = total / 2;
is_odd = false;
}else {
pos1 = total / 2;
is_odd = true;
}
int step = 0; // 步数
vector<int>::iterator p1 = nums1.begin();
vector<int>::iterator p2 = nums2.begin();
vector<int>::iterator cur = nums1.begin();
while(p1 != nums1.end() || p2 != nums2.end()) {
if(p1 != nums1.end() && (p2 == nums2.end() || *p1 < *p2)) {
cur = p1++;
}else {
cur = p2++;
}
if(is_odd && step == pos1){ // 找到奇数情况下的结果
return *cur;
}
if(!is_odd && step == pos1) {
val1 = *cur;
}else if(!is_odd && step == pos2) {
val2 = *cur;
return ((double)val1 + val2) / 2;
}
++step;
}
return 0;
}解法3：
leetcode提供了一种递归的方式，时间复杂度可以达到O(log2N)：
假如给定A、B两个排序数组， 在A中寻找一处索引 i， 在B中寻找一处索引 j， 分别将A、B数组分割成左右两部分 ；
合并A、B的左半部分；
合并A、B的右半部分；
假如左右两部分长度相同(总数为偶数时满足：i+j = (m-i) + (n-j) 总数为奇数时满足 i + j = (m - i) + (n - j) + 1)， 并且左半部分最大的元素比右半部分最小的元素小时（A[i - 1] <= B[j] && B[j - 1] <= A[i]）
当以上这两个条件均满足时 左半部分的最后一个元素和右半部分的第一个元素的平均值就是要求的结果。
将上面两个条件转化成：
条件1：j = (m+n+1)/2 - i = halfLen - i (要保证j为正数， 因此又多了一个条件： n >= m)
条件2：A[i - 1] <= B[j] && B[j - 1] <= A[i]
因此可以用二分查找的方式, 查找那个合适的i值
这种方法实质上是对元素的一次二分，因此时间复杂度为 O(log2N), 是这道题目已知的最优解
伪代码
m = A.length n = B.length // 确保左边的值更小 if m > n then swap(A, B) swap(m, n) end // 二分查找合适的i iMin = 0 IMax = m halfLen = (m + n + 1) / 2 while(iMin <= iMax) then i = (iMin + iMax) / 2 j = halfLen - i if i < iMax && B[j - 1] > A[i] then // 说明i太小了 iMin = iMin + 1 else if i > iMin && A[i - 1] > B[j] then // 说明i太大了 iMax = iMax - 1 else // 找到合适的i maxLeft = 0 if i == 0 then maxLeft = B[j - 1] else if j == 0 then maxLeft = A[i - 1] else maxLeft = max(A[i - 1], B[j - 1]) end if (m + n) % 2 == 1 then // 奇数，直接返回中值 return maxLeft end maxRight = 0 if i == m then maxRight = B[j] else if j == m then maxRight = A[j] else maxRigth = max(A[j], B[j]) end return (maxLeft + maxRight ) / 2.0 end end
总结：
不仔细推导很难得出最后一种方法...
坑：
坑比较少
优化：
存在优化空间
题目5：获取最长回文字符串
描述： 给定两个排序好的数组（升序排序），计算两个数组内所有数的中值。例如：
输入："babad" 输出："bab"
输入："cbbd" 输出："bb"
题目链接：https://leetcode.com/problems/median-of-two-sorted-arrays/description/
解答：
解法1：
最简单的思路，遍历的同时找对称点，一旦找到对称点（考虑，分别处理好aa aba aaa这三种情况），维护两个下标分别向前、向后遍历，找出所有对称点及每个对称点对应的字符串，返回最长的那个，代码如下：
string getDstStr(string s, size_t& ileft, size_t& iright, size_t sz, size_t pos, int& maxlen) {
string ret = "";
if(ileft >= 0 && iright < sz) {
while(ileft >= 0 && iright < sz ) { // 坑
if(s[ileft] == s[iright]) {
--ileft;
++iright;
}else {
break;
}
}
++ileft;
--iright;
}
int len = (iright == pos) ? 0 : 1;
string tmp = "";
if(len + 1 + iright - ileft > maxlen) {
for(size_t i = ileft; i <= iright; ++i) {
tmp += s[i];
}
ret = tmp;
maxlen = ret.size();
return ret;
}
return ret;
}
string longestPalindrome(string s) {
// 坑
if(s.size() == 1) {
return s;
}
size_t sz = s.size();
string ret = "";
int maxlen = 0;
for(size_t i = 0; i < sz; ++i) {
bool is_special = false; // 'bbb'这种情况
size_t ileft = 0;
size_t iright = 0;
if(i >= 1 && i < sz && s[i - 1] == s[i + 1]) { // 奇数的情况abcba
ileft = i - 1;
iright = i + 1;
}else if(i >= 1 && s[i] == s[i - 1]) { // 偶数的情况abba
ileft = i - 1;
iright = i;
}
if(i >= 1 && s[i] == s[i - 1] && s[i] == s[i + 1] ) { // 考虑'bbb'这种情况
is_special = true;
}
// 满足条件, 计算长度
if(iright > 0) {
if(is_special) {
ileft = i - 1;
iright = i + 1;
string tmp1 = getDstStr(s, ileft, iright, sz, i, maxlen);
ileft = i - 1;
iright = i;
string tmp2 = getDstStr(s, ileft, iright, sz, i, maxlen);
if(tmp1.size() > tmp2.size()) {
if(!tmp1.empty()) {
ret = tmp1;
}
}else {
if(!tmp2.empty()) {
ret = tmp2;
}
}
}else {
string tmp = getDstStr(s, ileft, iright, sz, i, maxlen);
if(!tmp.empty()) {
ret = tmp;
}
}
}
}
// 坑
if(ret.empty()) {
return s.substr(0, 1);
}
return ret;
}思路比较简单，但实现起来坑很多，时间复杂度O(N^2)
模板
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
