首页 > 8.19华为笔试AC,附代码
头像
cuber~
编辑于 2020-08-20 11:32
+ 关注

8.19华为笔试AC,附代码

代码写的比较乱,勉强AC了

Q1

题目大意:输出M N,表示M*N行的一个队伍,然后从外层到内层进行顺时针报数(下边矩阵所示),需要输出报的数 个位数是7,十位数是奇数的人所在的位置[[x1,y1], [x2,y2]...]。

1 2 3 4
10 11 12 5
9 8 7 6

直接模拟就好,坑点:m n的范围超出给的范围直接给0

def helper(n):
    a = n % 10
    b = (n // 10) % 10
    return a == 7 and b % 2


tmp = input().split()

try:
    M = int(tmp[0])
    N = int(tmp[1])
    assert 10<=M<=1000 and 10 <=N <=1000
    up, right, down, left = 0,N-1,M-1,0
    idx = 0
    res = []
    while up <= down and left <= right:
        for i in range(left, right+1, 1):
            idx += 1
            x = up
            y = i
            if helper(idx):
                res.append([x, y])

        up += 1

        for i in range(up, down+1, 1):
            idx += 1
            x = i
            y = right
            if helper(idx):
                res.append([x, y])

        right -= 1

        if left == right or up == down:
            break

        for i in range(right, left-1, -1):
            idx += 1
            x = down
            y = i
            if helper(idx):
                res.append([x, y])

        down -= 1

        for i in range(down, up-1,-1):
            idx += 1
            x = i
            y = left
            if helper(idx):
                res.append([x, y])

        left += 1

    res = str(res).replace(" ", "")
    print(res)
except:
    print("[]")

Q2

题目大意:二叉树有n个节点,每个节点的深度已知(代码中depth),让你计算该树总共有多少种可能的形状。
例如 depth为[0, 1]可能两种情况: 父节点和左孩子 、 父节点和右孩子
坑点: 下一层的个数可能会大于上一层个数的两倍,return 0

import os

n = int(input())
depth = [int(d) for d in input().split()]

M = 10 ** 9 + 7


def combination(n, k):
    if k == 0 or k == n:
        return 1
    k = min(k, n - k)

    top = 1
    for i in range(n, n - k, -1):
        top *= i

    down = 1
    for i in range(1, k + 1):
        down *= i

    return (top // down) % M


def helper():
    if n == 0:
        return 0

    max_depth = max(depth)
    depth_count = [0] * (max_depth + 1)

    for d in depth:
        depth_count[d] += 1

    for i in range(max_depth):
        if 2 * depth_count[i] < depth_count[i + 1]:
            return 0

    r = 1
    for i in range(1, max_depth + 1):
        r *= combination(2 * depth_count[i - 1], depth_count[i])
        r %= M

    return r


print(helper())

Q3

简化版俄罗斯方块
输出两个字符串s1,s2
s1相当于下边的情况,例如1221表示目前下边是(忽略\,怎么打空格来着):

\ ++
++++

s2相当于新来的小块, 例如121表示
+++
++

让你把新来的小块左右平移到合适的地方落下,问你最总最少剩下多少行?
俄罗斯方块一行满了就会消掉,就像s1=1221,其实最下边一行可以消掉了
我给的用例,最终剩下一行。

暴力模拟即可,给的测试用例相当友好
(经13楼指出,代码不对,官方的测试用例比较弱,能够AC)

#include<iostream>
#include<vector>
#include<queue>
#include<unordered_map>
#include<unordered_set>
#include<algorithm>
#include<string>
#include<stack>
#include<cmath>
#include<set>
#include<ctime>
#include<map>
#include<istream>
#define LL long long
using namespace std;



int helper(vector<int>& frame, vector<int>& brick)
{
    int frame_n = frame.size(), brick_n = brick.size();

    int res = 1000000;

    for (int i = 0;i < frame_n - brick_n + 1;i++)
    {
        int max_h = 0, total_max_h;
        for (int j = 0;j < brick_n;j++)
            max_h = max(max_h, brick[j] + frame[i + j]);
        total_max_h = max_h;
        int r = 100000;
        for (int j = 0;j < frame_n;j++)
        {
            total_max_h = max(total_max_h, frame[j]);
            if (j < i)
                r = min(r, frame[j]);
            else if (j >= (i + brick_n))
                r = min(r, frame[j]);
            else
            {
                int tmp1 = frame[j], tmp2 = brick[j - i];
                if (tmp1 + tmp2 == max_h)
                    r = min(r, max_h);
                else
                    r = min(r, tmp1);
            }
        }
        res = min(res, total_max_h - r);
    }
    return res;
}

int main()
{
    string s1, s2;
    cin >> s1 >> s2;
    vector<int> frame(s1.size()), brick(s2.size());
    for (int i = 0;i < s1.size();i++) frame[i] = s1[i] - '0';
    for (int i = 0;i < s2.size();i++) brick[i] = s2[i] - '0';

    cout << helper(frame, brick);

    return 0;
}

全部评论

(30) 回帖
加载中...
话题 回帖
历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐