Mrli
别装作很努力,
因为结局不会陪你演戏。
Contacts:
QQ博客园

华为春招4.29笔试题

2020/04/29
Word count: 1,636 | Reading time: 9min

4.29三道笔试题：

做了其他大厂的笔试题后，好像确实华为的稍微简单点。只不过其他的笔试题是有模拟题的，华为的这三道题基本上都是DFS

A：

带有重复元素的全排列问题，求不重复的排列数。以下做法50%, TLE了。正确做法是直接用公式计算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
'''
@Author: Mrli
@Date: 2020-04-29 20:23:34
@LastEditTime: 2020-04-29 21:24:40
@Description: 
'''
s = input().strip()
ans = list(s)
sz = len(s)
res = []
def dfs(depth):
    if depth > sz-1:
        return 
    if depth == sz-1:
        enter = ''.join(ans)
        if enter not in res:
            res.add(enter)
    
    for i in range(sz):
        swap(i, depth)
        dfs(depth+1)
        swap(i, depth)
    
def swap(x, y):
    tmp = ans[x]
    ans[x] = ans[y]
    ans[y] = tmp

dfs(0)
print(len(res))

B

求去掉K个字母，留下字典序最小的字符串。当时

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
'''
@Author: Mrli
@Date: 2020-04-29 19:01:55
@LastEditTime: 2020-04-29 22:31:07
@Description: 
'''
"""
# 看错题, 以为是从开头去掉k个。一分钟写的过了40%
"""
# s = input().strip()
# n = int(input().strip())
# print( s[n:])


'''
# 第一次尝试, ''->加n-k个->   过10%
'''
# 选择移除K个字母, 要使留下来的字符串字典序最小
# s = input().strip()
# n = int(input().strip())
# fans = s
# def dfs(ans, index, depth):
#     global fans
#     if index >= len(s): return 
#     if depth > n: return
#     if depth == n:
#         if ans <= fans:
#             fans = ans
#     print(ans + s[index])
#     dfs(ans + s[index], index+1, depth + 1)
#     dfs(ans, index+1, depth)
    
# dfs('', 0, 0)
# print(fans)


'''
当时dfs('', 0, 0)的写法报了点错, 以为不能这么写, 于是换成s中去k个
'''
# s = input().strip()
# sz = len(s)
# n = int(input().strip())
# fans = ''.join('z' for i in range(sz))
# def dfs(ans, index, depth):
#     global fans
#     if index >= sz: return 
#     if depth == n:
#         if ans <= fans:
#             fans = ans
#     # print(ans[0:index] + ans[index+1:])
#     dfs(ans[0:index] + ans[index+1:], index+1, depth + 1)
#     dfs(ans, index+1, depth)
# dfs(s, 0, 0)
# print(fans)



'''
第三次尝试, 重新接回第一种到n-k个数时结束的写法. 考完以后写出来的. 但不知道能不能过全部样例
'''
s = input().strip()
sz = len(s)
n = int(input().strip())

fans = ''.join('z' for i in range(sz))	# 初始化为最大

def dfs(ans, index):
    global fans
    if index == sz: return 
    if len(ans) == sz-n:
        # print(ans, fans, ans <= fans)
        if ans <= fans:
            fans = ans
    
    dfs(ans + s[index], index+1)
    dfs(ans, index+1)

dfs('', 0)
print(fans)

C:

k, n, r： 有k个硬币， n个城市， r条单向边

要求在硬币足够的情况下的最短距离

▲一开始以为是dijistra+硬币数(第二指标)判断，但是实际情况并不是在求最短距离的情况下的硬币数，而是在硬币充足的情况下最短距离是多少===>实际就变成了一个非常简单的DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
/*
 * @Author: Mrli
 * @Date: 2020-04-29 19:05:27
 * @LastEditTime: 2020-04-29 21:12:04
 * @Description: 
 */
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 105;
const int INF = 0x3f3f3f3f;

int dist[MAXN][MAXN];
int T[MAXN][MAXN];
bool visited[MAXN] = {false};

// int d[MAXN];
// int cost[MAXN];
int mans = INF;
bool haveans = false;

int k, n ,r;        // 硬币数、城市数、道路数

/* dijistra做法的尝试 */
// void dijistra(int s){
//     d[s] = 0;
//     cost[s] = 0;
//     for (int i = 1; i <= n; i++) {
//        int u = -1, MIN = INF;
//        for (int j = 1; j <= n; j++) {
//           if (visited[j] == false && d[j] < MIN){
//               u = j;
//               MIN = d[j];
//           }
//        }
//        if ( u == -1) return;
//        visited[u] = true;
//         // 保证路径最短, 再确定硬币
//     //    for (int v = 1; v <= n; v++) {
//     //       if (visited[v] == false && dist[u][v] != INF){
//     //           if ( dist[u][v] + d[u] < d[v] ){
//     //               d[v] = dist[u][v] + d[u];
//     //               cost[v] = T[u][v] + cost[u]; 
//     //           }else if (dist[u][v] + d[u] == d[v]){
//     //               if( cost[u] + T[u][v] < cost[v] ){
//     //                   cost[v] = cost[u] + T[u][v];
//     //               }
//     //           }
//     //       }
//     //    }

//         // 保证硬币足够的情况下
//         for (int v = 1; v <= n; v++) {
//           if (visited[v] == false && dist[u][v] != INF){
//               if ( T[u][v] + cost[u] < cost[v] ){   
//                   if ( dist[u][v] + d[u] < d[v] ){
//                        d[v] = dist[u][v] + d[u];
//                   }
//                   cost[v] = T[u][v] + cost[u]; 
//               }else if ( T[u][v] + cost[u] == cost[v] ){
//                   if( dist[u][v] + d[u] < d[v] ){
//                         d[v] = dist[u][v] + d[u];
//                         // cost[v] = T[u][v] + cost[u]; 
//                   }
//               }
//           }
//        }
//     }
// }


/* 思考过用BFS */
// void bfs(int s){
//     queue<int> q;
//     q.push(s);
//     visited[s] = true;
//     while (!q.empty()){
//         int u = q.front();
//         q.pop();
//         for (int v = 0; v < n; v++) {
//            if ( visited[v] == false && dist[u][v] != INF){

//            }
//         }
//     }
// }

void dfs(int u, int ans, int q){
    if ( u == n ){
        if ( q <= k){
            if (ans <= mans){
                mans = ans;
            }
            haveans = true;
        }
    }

    for (int v = 2; v <= n; v++) {
        if ( visited[v] == false && dist[u][v] != INF){
            visited[v] = true;
            // cout << "next: " <<v <<endl; 
            dfs(v, ans + dist[u][v], q + T[u][v]);
            visited[v] = false;
        }
    }
}


void init(){
    fill(dist[0], dist[0] + MAXN* MAXN, INF);
    fill(T[0], T[0] + MAXN* MAXN, INF);
    // fill(d, d+MAXN, INF);
    // fill(cost, cost+MAXN, INF);
}

int main(){
    cin >> k >> n >> r;
    init();

    for (int i = 0; i < r; i++) {
       int s, d, w, cost;
       cin >> s >> d >> w >> cost;
       dist[s][d] = w;
       T[s][d] = cost;
    }

    dfs(1, 0, 0);
    if (haveans) cout << mans <<endl;
    else cout << -1 <<endl;

    // for (int i = 1; i <= n; i++) {
    //    for (int j = 1; j <= n; j++) {
    //       cout << dist[i][j] <<" ";
    //    }
    //    cout << endl;
    // }
    // visited[1] = true;

    // for (int i = 1; i <= n; i++) {
    //    for (int j = 1; j <= n; j++) {
    //       cout << T[i][j] <<" ";
    //    }
    //    cout << endl;
    // }

    // dijistra(1);
    // for (int i = 1; i <= n; i++) {
    //     cout << d[i] << endl;
    // }
    // cout <<"---" <<endl;
    // for (int i = 1; i <= n; i++) {
    //     cout << cost[i] << endl;
    // }
    // cout << d[n] << endl;
    // if ( cost[n] <= k){
    //     cout << d[n] <<endl;
    // }else{
    //     cout << -1 <<endl;
    // }
    return 0;
}

牛客网华为练习题

合并表记录

1
2
3
4
5
6
7
8
odict = dict()
n = int(input().strip())
for i in range(n):
    ids, val = map(int, input().split())
    odict[ids]  = odict.setdefault(ids, 0) + val
slist = sorted(odict.items(), key= lambda d: d[0], reverse=True)
for k, v in odict.items():
    print(k, v)

Python 中字典的有序无序针对的是插入顺序而不是键值大小顺序,要想根据key或value排序可以直接用sort后再输出。而如果输出要保持输入的顺序，则使用 collections下的 OrderedDict(‘记住插入顺序的字典’)

Python逆序输出

1
2
3
4
5
6
7
8
9
10
11
# reverse
n = input().strip()
# for i in range()
rev = reversed(n)
for i in rev:
    print(i)

# range(-1)
s = 'hello'
for i in range(len(s)-1, -1, -1):
    print(s[i])

Author: Mrli

Link: https://nymrli.top/2020/04/29/华为春招4-29笔试题/

Copyright: All articles in this blog are licensed under CC BY-NC-SA 3.0 unless stating additionally.

< PreviousPost
重拾Java笔记NextPost >
剑指Offer_leetcode刷题记录
CATALOG
  1. 1. 4.29三道笔试题：
    1. 1.1. A：
    2. 1.2. B
    3. 1.3. C:
  2. 2. 牛客网华为练习题
    1. 2.1. 合并表记录