A
LeetCode:
14. Longest Common Prefix
Write a function to find the longest common prefix string amongst an array of strings.
If there is no common prefix, return an empty string "".
Example 1:
Input: ["flower","flow","flight"]
Output: "fl"
Example 2:
Input: ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.
Note:
All given inputs are in lowercase letters a-z.
思路：选出一个标准项（第一项），将每一项分别与标准项比较，得出标准项与每一项的公共前缀，再从中找出最短公共前缀。
我的代码如下：
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
if (strs.empty()) {
return "";
}
if (strs.size() == 1) {
return strs[0];
}
string result;
int len_min = 0, len = 0, count = 0;
vector<string>::iterator i, j, k = strs.begin();
vector<int> num;
len_min = (*k).length();
for (i = strs.begin() + 1; i != strs.end(); i++) {
len = (*i).length();
len_min = min(len_min, len);
}
if (len_min == 0) {
return result;
}
for (j = strs.begin() + 1; j != strs.end(); j++) {
for (int n = 0; n < len_min; n++) {
if ((*k)[n] == (*j)[n]) {
count++;
} else {
break;
}
}
num.push_back(count);
count = 0;
}
vector<int>::iterator l = num.begin();
count = *l;
for (l = num.begin(); l != num.end(); l++) {
count = min(count, *l);
}
if (count == 0) {
return result;
} else {
for (int m = 0; m < count; m++) {
result = result + (*k)[m];
}
}
return result;
}
};
运行结果：
Runtime: 8 ms, faster than 97.06% of C++ online submissions for Longest Common Prefix.
Memory Usage: 9.3 MB, less than 97.62% of C++ online submissions for Longest Common Prefix.
此题还有另外一种思路：遍历每一项，将每一项的字符按顺序依次比较，最终得出结果。这种思路的解法显然比上述思路要更稳定。
他人的代码：
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
if(strs.empty()) return "";
for(int i = 0; i < strs[0].size(); i++) {
for(int j = 0; j < strs.size(); j++) {
if(i >= strs[j].size() || strs[j][i] != strs[0][i]) {
return strs[0].substr(0, i);
}
}
}
return strs[0];
}
};
该方法速度明显提升，而作者用的方法也非常好。作者还使用了string中的substr()函数，该函数的作用是得出原字符串的一个子序列；
substr()函数用法：string substr(size_t pos = 0, size_t len = npos)const;返回值为由原字符串的pos位置开始，跨越len个字符的子字符串，其中size_t为无符号整数类型。
R
Robots Learn to Speak Body Language
- 本文讲述的是卡内基梅隆大学的研究者开发的一种能够跟踪人类身体行为的一种系统，名为OpenPose。它能够利用计算机视觉以及机器学习处理视频的帧。该功能可以简化人机交互。
- 该系统的主要特点：不仅能够跟踪人的头部、躯干、四肢，他还能跟踪人的手指。研究人员利用了CMU的Panoptic Studio，以各种角度拍摄身体姿势，构建了一个数据集。之后，他们通过关键点检测器传递这些图像，识别并标记特定的身体部位。该软件还会学着去将人体的不同部位与个体连接在一起。如：一个人的手总是与肘部相连。这一点能帮助他一次性跟踪许多人。
- 图像是2D捕获的，但是研究者利用跟踪得到的关键点，并在3D中进行角度测量，这能帮助身体跟踪算法理解不同姿势在不同角度是如何出现的。对这些数据处理之后，该系统就能决定手在某一特定位置的形状，即使部分手指被遮挡。
- 现在的已绘制了数据集的系统能够在仅仅使用一台摄像机与一台笔记本的情况下使用，实现了该技术的移动与可用性。研究者已公布了他们的代码。
- 这项技术可以在人机交互中发挥作用，如VR等，而并不需要如粘贴式传感器或手套等物理设备。将来的人机交互必将更为自然，如：当你掩面时，机器人可能会给你递上一张纸巾。
T
最近学动态规划的时候，发现了一篇讲得比较简单的文章：漫画：什么是动态规划？（整合版）
- 总结：
以斐波那契数列为基础理解：
F(1) = 1;
F(2) = 2;
F(n) = F(n-1)+F(n-2)（n>=3）思路：递归 --> 备忘录算法（哈希表）--> 自下而上（动态规划）;
求解三要素：最优子结构、边界、状态转移方程（核心）;
最优子结构：F(n) = F(n-1)+F(n-2)（n>=3），因此F(n-1)与F(n-2)是F(n)的最优子结构；
边界：F(1)与F(2)是边界；
状态转移方程：F(n) = F(n-1)+F(n-2)是状态转移方程。
S
分享一个比较好的总结：动态规划总结
