Hack Note (old posts, page 7)

Oct 18, 2018
gdb图形化调试

gdb是linux下很强大的调试工具，它使用命令行进行交互。相比于windows下visual studio的图形化调试界面，gdb的命令行方式操作起来不是很方便，从用户友好度上二者难以相提并论。不过gdb也有许多配套的前端组件，提供了图形化界面展示调试过程中的信息，这样就比传统命令行方式要方便很多。本文介绍了使用图形化的gdb前端让调试变得便捷高效，建议再阅读本文之前先掌握一些gdb的基础知识。
Oct 17, 2018
每周算法：下一个组合

leetcode算法题第31道，难度为medium。这道题考察题意理解的准确性和思路的全面性，对于题目所包含规律的总结也很重要。
Oct 11, 2018
每周算法：两整数相除

leetcode算法题第29道，难度为medium。从题目描述上来看，这道题考察两数相除的计算，貌似很简单，但如果仔细研究下来，就会发现这道题所考察的知识很综合。
Oct 10, 2018
在EMACS中对目录进行独立配置

如果你曾经同时维护多个软件项目，每个软件项目的代码风格都有各自的偏好。举个常见的例子，项目A要求使用 tab 进行缩进，而项目B要求使用空格进行缩进，虽然这样的代码风格问题看起来无关紧要，但这确实是代码编写中实实在在的问题。本文无意于讨论两者风格的优劣，而是想介绍在EMACS中优雅地解决这个问题的方法。
Oct 09, 2018
每周算法：删去有序数组中的重复元素

leetcode算法题第26道，难度为easy，这是非常基础的一道题。
Oct 04, 2018
每周算法：调换链表中节点

leetcode算法第24题，难度为medium。将链表中的节点成对翻转，考察链表结构的理解和节点的操作。
Sep 30, 2018
每周算法：生成有效的括号组合

leetcode 算法题第22道，难度为medium，对指定数量的括号进行排列组合，列举出其中有效的结果。对括号的处理通常出现在表达式分析中，这道题目是了解括号表达式特性的很好切入点。
Sep 27, 2018
路由、调制解调器和交换机

路由、调制解调器和交换机，这三个是我们经常使用的网络设备。它们在网络中的作用是什么？它们工作在网络模型的哪一层？本篇文章将带你了解他们的原理与和区别。
Sep 26, 2018
每周算法：删去单向链表倒数第n个节点

leetcode算法题第19道，难度为medium，考察链表的基本操作。
Sep 24, 2018
IP协议（RFC791）

本文是IPv4协议的摘要和笔记，IPv4协议格式由RFC791规定，RFC791协议的原文可以在这里找到。
Sep 21, 2018
网络通信协议

本文总结了两种常见的网络模型，OSI模型和TCP/IP模型，并比较了二者之间的区别。

Sep 21, 2018

每周算法：四数之和

Description

Given an array nums of n integers and an integer target , are there elements a, b, c, and d in nums such that a + b + c + d = target ? Find all unique quadruplets in the array which gives the sum of target .

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;
}