前言
BAT常见的算法面试题解析：
程序员算法基础——动态规划
程序员算法基础——贪心算法
工作闲暇也会有在线分享，算法基础教程----腾讯课堂地址。
今天继续LeetCode专场练习。
正文
1、Binary Tree Right Side View
题目链接：https://leetcode.com/problems/binary-tree-right-side-view/
题目大意：给出一颗二叉树，找出每个深度最右边的节点。
题目解析：
右边优先的深度遍历，保证每次是最右边；
遍历的时候加入深度这一个变量，判断当前深度是否存在节点即可。
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
vector<int> rightSideView(TreeNode* root) {
vector<int> ret;
if (root) {
dfs(root, ret, 0);
}
return ret;
}
void dfs(TreeNode* root, vector<int> &ret, int dep) {
if (ret.size() <= dep) {
ret.push_back(root->val);
}
if (root->right) {
dfs(root->right, ret, dep + 1);
}
if (root->left) {
dfs(root->left, ret, dep + 1);
}
}
};
2、Valid Parentheses
题目链接
题目大意：
给出一个字符串，只包含'(', ')', '{', '}', '[' and ']' 六类字符；
问给出的字符串是否满足：
1、所有括号都是匹配的；（左右括号数量一致）
2、匹配的括号是合法的；（没有交错）
Example 1:
Input: "()"
Output: true
Example 2:
Input: "()[]{}"
Output: true
Example 3:
Input: "(]"
Output: false
Example 4:
Input: "([)]"
Output: false
Example 5:
Input: "{[]}"
Output: true
题目解析：
根据题目的要求，可以用栈来实现，从左到右遍历字符串：
1、遇到一个字符，先看栈是否为空，如果为空则直接入栈；如果栈不为空，则看当前字符是左括号还是右括号；
2、如果是左括号，直接入栈；
3、如果是右括号，则看栈顶元素是否为左括号，并且匹配；
4、最后看栈是否为空。
class Solution {
public:
bool isValid(string s) {
stack<char> stk;
for (int i = 0; i < s.length(); ++i) {
int c = s[i];
if (stk.size() == 0) {
stk.push(c);
}
else {
if (c == '[' || c == '{' || c == '(') {
stk.push(c);
}
else {
char top = stk.top();
stk.pop();
if ((c == ']' && top != '[') || (c == '}' && top != '{') || (c == ')' && top != '(')) {
return false;
}
}
}
}
return stk.size() == 0;
}
}leetcode;
3、Letter Combinations of a Phone Number
题目链接
题目大意：
输入一个字符串，仅包含2-9的数字；
数字代表的是键盘上的输入，如图
问对于这个输入，可能有哪些字符串。
Example:
Input: "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
题目解析：
对于每个数字，代表3或者4个字母；
于是可以用搜索的思想解决问题，枚举每一种可能。
class Solution {
public:
void dfs(string &digits, int i, string &tmp, vector<string> &ret) {
if (i >= digits.length()) {
ret.push_back(tmp);
return;
}
else {
int nums[10] =
{
0,
0, 3, 3,
3, 3, 3,
4, 3, 4,
};
int index = digits[i] - '0';
int start = 0;
for (int i = 2; i < index; ++i) {
start += nums[i];
}
int end = start + nums[index];
for (int j = start; j < end; ++j) {
tmp.push_back('a' + j);
dfs(digits, i + 1, tmp, ret);
tmp.pop_back();
}
}
}
vector<string> letterCombinations(string digits) {
vector<string> ret;
string tmp;
if (digits.length()) {
dfs(digits, 0, tmp, ret);
}
return ret;
}
}leetcode;
小trick，如果输入的是空串，那么返回的是空值；
4、Shortest Palindrome
题目链接
题目大意：
给出一个字符串s，在s的左边添加字符串，使得s变成一个回文串；
要求s的字符串长度尽可能短，返回最后的s串。
题目解析：
对于字符串s中的每个位置x，判断以str[x]为中心，形成回文串的长度有多长；
如果位置能覆盖到最左边，那么右边剩下的字符串翻转后贴在最左边，就能得到回文串。
难点：如果回文串是偶数如何处理？（此时没有中心字符）
在每个字符的右边插入'#'，abcd=>a#b#c#d。
class Solution {
public:
string shortestPalindrome(string s) {
vector<char> str(s.length() * 2 + 5);
vector<int> p(str.size());
str[0] = '@';
int i, j;
for(i = 0, j = 1; s[i]; i++){
str[j++] = '#';
str[j++] = s[i];
}
str[j++] = '#';
int n = j;
manachar(str, p, n);
int ans = 0, pos = 0;
for(i = 1; i < n; i++) { // @#a#b#a#a#
if (p[i] == i) { // 能覆盖到最左边
pos = i;
ans = p[i] - 1; // 回文串长度
}
}
string add = string(s.begin() + ans, s.end());
reverse(add.begin(), add.end());
return add + s;
}
void manachar(vector<char> &str, vector<int> &p, int n){
int id = 0, mx = 0;
for(int i = 1; i < n; i++){
if(mx > i) p[i] = min(p[2 * id - i], mx - i);
else p[i] = 1;
while(str[i + p[i]] == str[i - p[i]]) p[i]++;
if(p[i] + i > mx) mx = p[i] + i, id = i;
}
}
}leetcode;
优化：
用manachar算法找出每个位置的回文串长度，时间和空间都能优化到O(N)。
5、Dungeon Game
题目链接
题目大意：
n*m的网格，每个网格有一个数字，要从左上角到右下角（只能向右或者向左）；
起始点是左上角，并且初始状态有个体力值，每次经过网格时体力值会发生该网格上数字的变化：
如果是数字是x，那么体力值Hnew = Hold + x;
问最少需要多少体力值，才能保证从左上角到右下角，体力值不小于1；
题目解析：
题目的意思可以理解为：求左上到右下的路径数字和最大；
这是一个经典的动态规划，注意点1：如果和是正整数，那么体力值为1即可。
但是，一个hard题目是否这么简单呢？
这种做法忽略了一种情况：题目要求保证路径上，体力值一直不小于1。
即使求出来的路径和是正整数，路上仍旧可能出现负数的情况。
对题目进行思考，发现体力值符合线性特征：
如果体力值H可行，那么体力值H+1必然也可以。
于是改用二分，对每个二分的体力值我们判断其是否通过。
int calculateMinimumHP(vector<vector<int>>& dungeon) {
int left = 1, right = inf, ans = 0;
while (left <= right) {
int mid = (left + right) / 2;
if (canPass(dungeon, mid)) {
ans = mid;
right = mid - 1;
}
else {
left = mid + 1;
}
}
return ans;
}
canPass的思路就是：在n*m的网格中，遍历所有能到达的点，看是否能到达右下角；
时间复杂度是O(N * M * logK) K为数字最大值，N、M为行列数量。
思考：
这里，其实还是可以用动态规划来解决，核心就是：逆序。
假设到达右下角的体力值是1，在此基础上从右下往左上dp，保持状态转移过程中体力值不小于1即可。
总结
这些都是面试常见的题目，尤其是第一个，是电面的常见问题。
面试过程中，遇到这类算法题有两大难点：
1、如果想到合适的解法；
2、把解法用合适的代码表达出来；
这两个点都只能通过多练去解决，一定是要掌握算法题的核心思路，这样才能在遇到类似题目时游刃有余。
已经到8月中旬，越来越不好招人，这时候找工作一定要慎重。
