写在前面
华为面试题库刷题第五次整理。
582. 杀死进程
给 n 个进程，每个进程都有一个独一无二的 PID （进程编号）和它的 PPID （父进程编号）。
每一个进程只有一个父进程，但是每个进程可能会有一个或者多个孩子进程。它们形成的关系就像一个树状结构。只有一个进程的 PPID 是 0 ，意味着这个进程没有父进程。所有的 PID 都会是唯一的正整数。
我们用两个序列来表示这些进程，第一个序列包含所有进程的 PID ，第二个序列包含所有进程对应的 PPID。
现在给定这两个序列和一个 PID 表示你要杀死的进程，函数返回一个 PID 序列，表示因为杀这个进程而导致的所有被杀掉的进程的编号。
当一个进程被杀掉的时候，它所有的孩子进程和后代进程都要被杀掉。
你可以以任意顺序排列返回的 PID 序列。
示例 1:
输入:
pid = [1, 3, 10, 5]
ppid = [3, 0, 5, 3]
kill = 5
输出: [5,10]
解法：
dfs（超时）
搜，就嗯搜，O(N^N)，不超时就有鬼了。
代码：
class Solution {
private:
vector<int> res;
public:
void helper(vector<int>& a, vector<int>& b, int k){
res.push_back(k);
for(int i=0; i<b.size(); i++){
if(b[i]==k)
helper(a,b,a[i]);
}
return;
}
vector<int> killProcess(vector<int>& pid, vector<int>& ppid, int kill) {
helper(pid,ppid, kill);
return res;
}
};
哈希+dfs
其实上一种做法是可行的，只是每一次递归的时候都需要遍历数组找儿子，很费时间，所以用哈希表存一下，查找的时间就剩下来了。
代码：
class Solution {
private:
vector<int> res;
public:
void helper(unordered_map<int,vector<int>>& m, int kill){
auto pos = m.find(kill);
if(pos!=m.end()){
for(auto id : m[kill]){
res.push_back(id);
helper(m,id);
}
}
}
vector<int> killProcess(vector<int>& pid, vector<int>& ppid, int kill) {
unordered_map<int,vector<int>> m;
for(int i=0; i<ppid.size(); i++){
if(ppid[i]>0){
m[ppid[i]].push_back(pid[i]);
}
}
res.clear();
res.push_back(kill);
helper(m,kill);
return res;
}
};
哈希+bfs
存储阶段和上一种方法一样，不过用队列模拟了bfs过程。
代码：
class Solution {
private:
vector<int> res;
public:
vector<int> killProcess(vector<int>& pid, vector<int>& ppid, int kill) {
unordered_map<int,vector<int>> m;
for(int i=0; i<ppid.size(); i++){
if(ppid[i]>0){
m[ppid[i]].push_back(pid[i]);
}
}
res.clear();
queue<int> q;
q.push(kill);
while(!q.empty()){
int r = q.front();
q.pop();
res.push_back(r);
auto pos = m.find(r);
if(pos!=m.end()){
for(auto id : m[r])
q.push(id);
}
}
return res;
}
};
539. 最小时间差
给定一个 24 小时制（小时:分钟）的时间列表，找出列表中任意两个时间的最小时间差并已分钟数表示。
示例：
输入: [“23:59”,”00:00”]
输出: 1
备注:
- 列表中时间数在 2~20000 之间。
- 每个时间取值在 00:00~23:59 之间。
解法：排序，然后求差就行了。注意最后一个时间和第一个也要作差。
代码：
class Solution {
public:
struct time{
int min;
int hour;
};
int findMinDifference(vector<string>& a) {
sort(a.begin(),a.end());
int res = INT_MAX;
string c1,c2;
int tt;
time t1,t2;
for(int i=1; i<a.size(); i++){
c1 = a[i-1].substr(0,2);
c2 = a[i-1].substr(3,2);
t1.hour= stoi(c1);
t1.min = stoi(c2);
c1 = a[i].substr(0,2);
c2 = a[i].substr(3,2);
t2.hour= stoi(c1);
t2.min = stoi(c2);
if(t1.hour==t2.hour) tt = t2.min-t1.min;
else tt = (60-t1.min) + t2.min + 60 * (t2.hour-t1.hour-1);
res = min(res,tt);
}
c1 = a[a.size()-1].substr(0,2);
c2 = a[a.size()-1].substr(3,2);
t1.hour= stoi(c1);
t1.min = stoi(c2);
c1 = a[0].substr(0,2);
c2 = a[0].substr(3,2);
t2.hour= stoi(c1);
t2.min = stoi(c2);
tt = 60*(24-t1.hour-1) + (60-t1.min) + t2.hour * 60 + t2.min;
return min(res,tt);
}
};
881. 救生艇
第 i 个人的体重为 people[i]，每艘船可以承载的最大重量为 limit。
每艘船最多可同时载两人，但条件是这些人的重量之和最多为 limit。
返回载到每一个人所需的最小船数。(保证每个人都能被船载)。
示例 3：
输入：people = [3,5,3,4], limit = 5
输出：4
解释：4 艘船分别载 (3), (3), (4), (5)
提示：
- 1 <= people.length <= 50000
- 1 <= people[i] <= limit <= 30000
解法：
贪心+双指针
先排序，然后两个指针，从数组两段开始走，如果最轻和最终的可以一起，就一起坐船，否则胖子自己坐，因为那已经是最轻的了。
代码：
class Solution {
public:
int numRescueBoats(vector<int>& a, int limit) {
sort(a.begin(),a.end());
int res = 0;
int i(0),j(a.size()-1);
while(i<=j){
if(a[i]+a[j]<=limit){
++res;
++i;
--j;
}
else{
++res;
--j;
}
}
return res;
}
};
227. 基本计算器 II
实现一个基本的计算器来计算一个简单的字符串表达式的值。
字符串表达式仅包含非负整数，+， - ，*，/ 四种运算符和空格 。 整数除法仅保留整数部分。
示例:
输入: “3+2*2”
输出: 7
说明：
- 你可以假设所给定的表达式都是有效的。
- 请不要使用内置的库函数 eval。
栈
表达式计算最经典的做法，就是栈，符号是* /就直接计算，符号是+ -就先存起来，最后会只剩下一个只有+ -的算式，算一遍就行了。
代码：
class Solution {
public:
int calculate(string s) {
vector<int> a;//存放数字
vector<char> b;//存放运算符
string t = "";
for(char c : s)
if(isdigit(c) || c=='+' || c=='-' || c=='*' || c== '/')
t += c;
int i=0;
string curr = "";
while(i<t.length() && isdigit(t[i])){
curr += t[i];
++i;
}
int currn = stoi(curr);
a.push_back(currn);
while(i<t.length()){
b.push_back(t[i]);
++i;
curr.clear();
while(i<t.length() && isdigit(t[i])){
curr += t[i];
++i;
}
currn = stoi(curr);
if(b.back()=='*' || b.back()=='/'){
if(b.back()=='*')
currn *= a.back();
else
currn = a.back()/currn;
b.pop_back();
a.pop_back();
a.push_back(currn);
}
else{
a.push_back(currn);
}
}
for(int i=0; i<a.size(); i++)
cout<<a[i]<<' ';
cout<<endl;
for(int i=0; i<b.size(); i++)
cout<<b[i]<<' ';
cout<<endl;
int res = a[0];
for(int i=1; i<a.size(); i++){
if(b[i-1]=='+')
res+=a[i];
else
res-=a[i];
}
return res;
}
};
1139. 最大的以 1 为边界的正方形
给你一个由若干 0 和 1 组成的二维网格 grid，请你找出边界全部由 1 组成的最大 正方形 子网格，并返回该子网格中的元素数量。如果不存在，则返回 0。
示例 1：
输入：grid = [[1,1,1],[1,0,1],[1,1,1]]
输出：9
提示：
- 1 <= grid.length <= 100
- 1 <= grid[0].length <= 100
- grid[i][j] 为 0 或 1
解法：用两个数组分别存放横向和竖向的连续1的长度，然后在每个有1的位置，向左上方判断。（有点蠢）
代码：
class Solution {
public:
int largest1BorderedSquare(vector<vector<int>>& a) {
if(a.empty()) return 0;
int m = a.size();
int n = a[0].size();
vector<vector<int>> dp1(m+1,vector<int>(n+1,0));
vector<vector<int>> dp2(m+1,vector<int>(n+1,0));
for(int i=0; i<m; i++)
dp1[i][0] = a[i][0];
for(int i=0; i<m; i++)
for(int j=1; j<n; j++)
if(a[i][j])
dp1[i][j] = dp1[i][j-1] + 1;
for(int i=0; i<n; i++)
dp2[0][i] = a[0][i];
for(int j=0; j<n; j++)
for(int i=1; i<m; i++)
if(a[i][j])
dp2[i][j] = dp2[i-1][j] + 1;
int res = 0;
for(int i=0; i<m; i++){
for(int j=0; j<n; j++)
cout<<dp1[i][j]<<' ';
cout<<endl;
}
cout<<"---------"<<endl;
for(int i=0; i<m; i++){
for(int j=0; j<n; j++)
cout<<dp2[i][j]<<' ';
cout<<endl;
}
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
if(a[i][j]){
int s = 1;
int x = i;
int y = j;
int t = dp1[i][j]-1;
res = max(res,1);
while(t>0){
if(y-s>=0 && x-s>=0 && dp1[x-s][y]>s && dp2[x][y]>s && dp2[x][y-s]>s){
res = max(res,s+1);
}
++s;
--t;
}
}
}
}
return res*res;
}
};
