[2022-08-31]Three programming questions in Huawei Autumn Recruitment Written Test

Congrats on finding the treasure! Search the public account [TechGuide] to reply to the company name, unlock more fresh and good articles and the pens and facebooks of Internet giants, which have been updated to Meituan, Microsoft…
Author @TechGuide [same name on the whole network]
Like and watch again, form a habit, you move your fingers to the original author of great significance 🤝

Question 1: String Compression

Topic description

Given an English sentence and a list of English words. English sentences contain English words and punctuation, where:

  1. English words only contain characters in the range [a-zA-Z];
  2. Punctuation includes commas, periods, and double quotation marks (with at least one space on both sides of the double quotation marks).

If there is a word in the list that exists in the sentence (case-insensitive) and the word is not enclosed by double quotes, use the index value of the word in the list (index value starts from 0) instead of the word in the sentence, if English If there is a repeated English word in the word list, it will be replaced with the index value of the last occurrence of the word.

enter description

The first line: an English sentence
Second line: English word list
hint:
The length of each English word is in the range of [150].
The length of the input English sentence is in the range [0,10000].
The length of the input English word list is in the range [0,100000]. There will be no double-quote mismatch in English sentences.

Hello world.
Good Hello LOOP

Explanation: If hello exists in an English sentence, use the index value of hello to replace it, and the result is 1w
orld.

output description

replaced english sentence

1world.

code

CPP version

#include<bits/stdc++.h>
using namespace std;
map<string,int>aa;
void change(string &s){
 for(int i=0;i<s.length();i++){
  if(s[i]>='a' &&s[i]<='z'){
   s[i]-=32;
  }
 }
}
bool check(char aa){
 if(aa>='A' && aa<='Z')return true;
 if(aa>='a' && aa<='z')return true;
 return false;
}
int main(){
 string s;
 getline(cin,s);
 string s1;
 int tt=1;
 while(cin>>s1){
//  string s2;
  change(s1);
//  cout<<s1<<' '<<tt<<endl;
  aa[s1]=tt;
  tt++;
  //if(tt>=8)break;//For debugging
 }
 string ans;
 int begin1=0;
 for(int i=0;i<s.length();i++){
  if(s[i]=='"'){
   i++;
   while(i<s.length() &&s[i]!='"')i++;
//   ans+='"';
  }
  while(i<s.length() &&check(s[i])){
   i++;
  }
  if(i==s.length())break;
  string tl=s.substr(begin1,i-begin1);
  begin1=i+1;
  string ts=tl;
  change(tl);
//  cout<<"start"<<tl<<' '<<aa[tl]<<endl;
  if(aa[tl]!=0)ans+=to_string(aa[tl]-1);
  else ans+=ts;
  ans+=s[i];
 }
 cout<<ans<<endl;
 return 0;
}
// vx official account pays attention to TechGuide real-time question bank Lightning Express

JS version

//I forgot the code given by Huawei before and after, and wrote the core directly

//Work with sentences and dictionaries
var sentence = inputArrays[0].split(" ")
var dictionary = inputArrays[1].split(" ")
//Case insensitive, change the dictionary to uppercase, there are special characters in the sentence, can't be changed
dictionary = Array.from(dictionary,item=>item.toUpperCase())
//To deal with quotation marks, the idea is to define a switch. At that time, I forgot how to spell the words in quotation marks. .
var isInside = false
for(let i in sentence){
    if(sentence[i]=='"'){
        isInside = !isInside    //switch
        continue    //Quotes do not do dictionary lookup
    }
    var str = sentence[i].replace(/[^a-zA-Z]/,"")
    //If there are special characters, toUpperCase() will report an error. It has been stuck here for a long time. It belongs to the knowledge of the examination room.
    if(dictionary.includes(str.toUpperCase())){
        //I used the for loop to look up the dictionary in reverse order, and the rest timed out after 80%, so I optimized it, first check if there is any
        var j = sentence[i] = dictionary.lastIndexOf(str.toUpperCase())
        //The last index, of course lastIndexOf()
        str.length==sentence[i].length? sentence[i]=j:sentence[i]=j+sentence[i][sentence[i].length-1]
        //By comparing the length to see if there is a period comma, if there is, take it over
    }
}
console.log(sentence.join(" ")) 
// vx official account pays attention to TechGuide real-time question bank Lightning Express

Question 2: Soldier's Mission 2

Topic description

The soldier performs the task in the maze, the maze is full of dangers, and he needs to reach the designated position in the shortest time. Can you tell the soldier how long it takes him at least?
Enter a n*m maze, where 0 is the road, 1 is the wall, 2 is the starting point, 3 is the ending point, 4 is the trap, and 6 is the bomb. Soldiers can only move in four directions, up, down, left, and right. If the path is a wall, they cannot move. It is known that each step takes 1 unit of time, and it takes 3 units to walk to the trap. Walking to the bomb will activate the bomb and blow the bomb up, down, left, and right walls into roads.

be careful:

  1. Bombs can only blow up places, not traps
  2. Bombs and traps can only work once
  3. Myth is up to 25*25
  4. The use case ensures that the ten soldiers must have a way to reach the end

enter
output
Example 1
Copy Input: 44
1021

enter description

First row: n and m
Second row starts: n*m matrix

4 4
1 1 1 1
1 6 2 1
1 1 0 1
1 3 1 1

output description

Minimum required unit time

3

explain:
Soldier is in position 2, move left to the bomb, it will blow up the wall around the bomb, go two steps down
reach the end

ideas

code

CPP version

#include <iostream>
#include <queue>
using namespace std;
struct node
{
    int x, y, t;
    node() {}
    node(int a, int b, int c) : x(a), y(b), t(c) {}
    bool operator<(const node &a) const
    {
        return t > a.t;
    }
};

int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
int g[30][30], vis[30][30];
int n, m, ans = 0;
priority_queue<node> q;

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            cin >> g[i][j];
            if (g[i][j] == 2)
            {
                vis[i][j] = 1;
                q.push(node(i, j, 0));
            }
        }
    }
    while (!q.empty())
    {
        node cur = q.top();
        q.pop();
        for (int i = 0; i < 4; ++i)
        {
            int tx = cur.x + dx[i];
            int ty = cur.y + dy[i];
            if (tx < 0 || ty < 0 || tx >= n || ty >= n || vis[tx][ty] || g[tx][ty] == 1)
                continue;
            if (g[tx][ty] == 3)
            {
                ans = cur.t + 1;
                break;
            }
            vis[tx][ty] = 1;
            if (g[tx][ty] == 4)
                q.push(node(tx, ty, cur.t + 3));
            else if (g[tx][ty] == 6)
            {
                q.push(node(tx, ty, cur.t + 1));
                for (int j = 0; j < 4; ++j)
                {
                    int xx = tx + dx[j];
                    int yy = ty + dy[j];
                    if (g[xx][yy] == 1)
                        g[xx][yy] = 0;
                }
            }
            else
                q.push(node(tx, ty, cur.t + 1));
        }
        if (ans)
            break;
    }
    cout << ans;
    return 0;
}
// vx official account pays attention to TechGuide real-time question bank Lightning Express

Question 3: Charging Planning for Expressway Rest Stops (Partial AC)

Topic description

Zhang San purchased a self-driving new energy vehicle with a cruising range of 1,000 kilometers. After the vehicle is fully charged on a certain day, it is necessary to start from City A to City B, which is a distance of D kilometers, and take the high-speed the whole way.

The on-board navigation prompts that there are N rest stops along the way that can provide charging services, and each rest stop can provide the current charging queuing time (hours) in real time.
Please assist in planning the optimal rest stop charging solution to return the shortest travel time.

For the convenience of calculation, the driving speed on the expressway is fixed at 100 km/h. When planning, there is no need to consider keeping the safe cruising range. The car can run out of electricity completely, and a car with a cruising range of 1,000 kilometers can drive for 10 hours at 100 km/h. Each charging time is fixed at 1 hour, and the battery is fully charged after completion. The charging queuing time at each site will not change, and the charging queuing process does not consume power.

enter description

The first line represents the distance D between cities A and B, in kilometers;
The second line represents the number N of rest stops along the way;
From the third line onwards, there are 2 data in each line, representing the distance between the rest station and the city, and the time required for charging and queuing (hours).
0<=D<=1000000, D is an integer multiple of 100
0<=N<=10000

1500
4
300 2
600 1
1000 0
1200 0

output description

Minimum time spent in total journey (hours)
Returns -1 if the end point cannot be reached

16

explain:
Best solution: only charge at the 3rd rest stop (position 1000)
1500km journey time: 15 hours
Queue for 0 hours for charging, 1 hour for charging
The fastest journey takes a total of 16 hours

Alternative: Recharge at the 2nd rest stop (location 600) for a total of 17 hours
Alternative: Charging at rest stop 2 (location 600) and rest stop 4 (location 1200) for a total of 19 hours

ideas

Utilize dynamic programming + plus fallback search
Set the starting point to 0, and every time you reach a new site, perform a fallback search until you reach the farthest charging site k within 1000 kilometers, and then start traversing from site k to the current site, and find The shortest time to reach the current site, and then save it to the time array ans of the current site, traverse continuously, and finally traverse to the end point.

code

#define DEBUG 1
#if DEBUG
#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;


int main(void) {
	int n, m;
	//parameter input
	cin >> n;
	cin >> m;

	//Initialize the station array, including the start and end points in the array as well
	vector<vector<int>> f(m+2, vector<int>(2));

	//The distance from the starting point and the waiting time are both set to 0
	f[0][0] = 0;
	f[0][1] = 0;
	//The distance to the end point is set to n, and the waiting time is set to 0
	f[m+1][0] = n;
	f[m+1][1] = 0;

	//Start joining various sites
	for (int i = 1; i < m+1; i++) {
		cin >> f[i][0];
		cin >> f[i][1];
		cout << f[i][0] << ' ';
		cout << f[i][1] << ' ';

	}

	//Initialize the time of arrival at the station, including the start and end points into the array as well
	vector<int> ans(m + 2);
	ans[0] = 0;

	//Start counting individual sites
	for (int i = 1; i < m + 2; i++) {
		//Find all stations within 1000 distance
		int k = i - 1;
		while (k > 0 && (f[i][0] - f[k][0] < 1000)){
			k--;
		}
		//In addition to the starting site, there is one more site, so k needs to be increased by one
		if (k != 0) {
			k++;
		}
		//Traverse each directly reachable station to find the smallest time station
		int min_time = INT_MAX;
		for (; k < i; k++) {
			int cur_time = (f[i][0] - f[k][0]) / 100 + ans[k] + f[i][1];
			if (k != 0) {
				cur_time++;
			}
			min_time = min(min_time, cur_time);
		}

	}
	getchar();
	cout << ans[m+1] << endl;

	getchar();

}
// vx official account pays attention to TechGuide real-time question bank Lightning Express

Posted by markyoung1984 on Thu, 01 Sep 2022 22:40:51 +0530