2015华为机试题

前天下午参加了华为机试，总体来说答得不好，完整做出来的就只有一题，第三题在leetcode上面看到过，唉，不废话了，分享出来互相参考一下吧。

一、单词首字母大写

输入：字符串，单词以空格隔开
输出：单词首字符大写的字符串

求解思路：
我的想法是使用ASCII码值来求解。

代码如下：

#include <string>
#include <iostream>

using namespace std;

void main()
{
string word;
while(cin>>word)
    {
        word[0] -= 32;
cout<<word<<" ";
    }
}

二、笨笨熊搬家

大致题意：有一个指定的R行、C列的矩阵地图，矩阵由’B’、’H’、’-‘、’#’四种字符构成，其中

B：代表笨笨熊现在的旧房子
H：代表笨笨熊即将前往的新房子
-：代表可以走通的道路
#：代表走不通的障碍

输入：R行C列的矩阵地图，然后判断笨笨熊的旧房子到新房子是否有可行的道路。
输出：若有则输出Y，否则输出N。

求解思路：
首先，根据输入的矩阵地图找到B和H的位置（Bi, Bj）、（Hi, Hj）
然后对于每一位置（x, y），下一步有四个方向，因此可能有四种走向：

往左：（x - 1，y）
往右：（x + 1，y）
往上：（x，y + 1）
往下：（x，y - 1）

注意，这里需要考虑此位置是否为边界的地方。
然后我们对于每个位置进行考虑，查看其字符是否为’H’，如是，则返回Y，否则，如果这个字符为’#’，则放弃，直接考虑下一个位置；如果这个字符为’-‘，则将此位置入栈，进入考虑字符队列。

代码如下：

#include <iostream>
#include <stack>
#include <vector>
#include <utility>

using namespace std;

const int rr[4] = {-1, 1, 0, 0};  //四个方向（左右上下）
const int cc[4] = {0, 0, 1, -1};
int R, C;  //行和列数

bool go(vector< vector<char> > &map, int i, int j)
{
bool ans = false;
stack<pair<int, int>> s;
    s.push(make_pair(i, j));

while(!s.empty())  
    {
int ii = s.top().first;
int jj = s.top().second;
        s.pop();
map[ii][jj] = '*';
for(int i = 0; i < 4; i++)
        {
int tr = ii + rr[i];
int tc = jj + cc[i];
if(tr >= 0 && tc >= 0 && tr < R && tc < C && map[tr][tc] == 'H')  //找到豪宅
            {
                ans = true;
return ans;
            }
if(tr >= 0 && tc >= 0 && tr < R && tc < C && map[tr][tc] == '-')  //如果找到的是可行的路，则存入到栈中
            {
map[tr][tc] = '*';  //将入栈的道路换成*，防止重复入栈
                s.push(make_pair(tr, tc));
            }
        }
    }
return ans;
}

void main()
{
while(cin>>R>>C)
    {
vector< vector<char> > map(R, vector<char>(C));
int Bi, Bj, Hi, Hj;  //（Bi, Bj）、（Hi, Hj）分别为旧房子B和新房子H的位置坐标
for(int i = 0; i < R; i++)
        {
for(int j = 0; j < C; j++)  //找到新旧房子的位置
            {
cin>>map[i][j];
if(map[i][j] == 'B'){Bi = i; Bj = j;}
if(map[i][j] == 'H'){Hi = i; Hj = j;}
            }
        }
bool ans = go(map, Bi, Bj);
if(ans) cout<<"Y"<<endl;
else cout<<"N"<<endl;
    }
}

三、最大只包含1的矩形

其实这个是leetcode上面的一个题目，唉，时间来不及了，没写出来。

输入：一个M*N的矩阵，矩阵元素只有0或者1；
输出：最大矩阵面积；

求解思路：

代码转载自：http://blog.csdn.net/jiyanfeng1/article/details/8068676



int maximalRectangle(vector<vector<char> > &matrix) {
// max rectangle in a 0-1 matrix

if(matrix.size()==0) return 0;

int* hist = new int[matrix[0].size()];
memset(hist, 0, sizeof(int)*matrix[0].size());

int max_ = 0;

for(int i=0; i<matrix.size(); i++)
 {
for(int j=0; j<matrix[0].size(); j++)
 {
if(matrix[i][j]=='1')
 *(hist+j) += 1;
else
 *(hist+j) = 0;
 }

 max_ = max(max_, maxRectInHistogram(hist, matrix[0].size()) );
 }

return max_;
 }

int maxRectInHistogram(int hist[], int n) 
// hist: contains the heights of the bars 
// n: the number of the bars in the histogram. 
 { 
int* arr = new int[n];// 申请一个额外的数组 
 arr[0] = hist[0]; 
int max = hist[0]; // 最大面积 

for(int i=1; i<n; i++) 
 { 
 arr[i] = hist[i]; 
for(int j=i-1; j>=0; j--) 
if(arr[j]>arr[i]){ 
if(arr[j]*(i-j)>max) 
 max = arr[j]*(i-j); 
 arr[j] = arr[i]; 
 } 
else break; 
//数组arr里的元素，保持非递减的顺序。 
 } 

//重新扫描一边，以更新最大面积 
for(int i=0; i<n; i++) 
if(arr[i]*(n-i)>max) 
 max = arr[i]*(n-i); 
return max; 
 }

秒客网

2015华为机试题

相关文章