华为笔试-矩阵相邻

这个题首先需要一个原始矩阵的“数字到索引的反查表，即给出1要查出下标(0, 0);

 //存储索引的自定义结构
    private static class Index {
        private int x;
        private int y;

        Index(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    //定义并初始化反查表，共25行，省略
    private static HashMap<Integer, Index> map = new HashMap<Integer, Index>() {
        {
            put(1, new Index(0, 0));
            put(2, new Index(0, 1));
            ...省略23行...
        }
    };

判断两个索引之间是否相连的函数

 private static boolean link(Index i1, Index i2) {
        return i1.x == i2.x + 1 && i1.y == i2.y
                || i1.x == i2.x - 1 && i1.y == i2.y
                || i1.x == i2.x && i1.y == i2.y - 1
                || i1.x == i2.x && i1.y == i2.y + 1;
    }

解题函数，一个未连接数字集合unLinked，一个已连接数字集合linked，循环条件是只要unLinked非空，如果某一次循环，没有发现unLinked中有数字可以和linked中的任一数字相连，直接返回0

 private static int solve(int[] nums) {
        HashSet<Integer> unLinked = new HashSet<>();
        for (int i = 1; i < nums.length; i++) {
            unLinked.add(nums[i]);
        }
        HashSet<Integer> linked = new HashSet<>();
        linked.add(nums[0]);
        while (!unLinked.isEmpty()) {
            HashSet<Integer> tmp = new HashSet<>();
            for (Integer i : unLinked) {
                for (Integer j : linked) {
                    if (link(map.get(i), map.get(j))){
                        tmp.add(i);
                    }
                }
            }
            if (tmp.isEmpty()) {
                return 0;
            }
            for (Integer i: tmp){
                unLinked.remove(i);
                linked.add(i);
            }
        }
        return 1;
    }

可惜大部分时间用来想第三题剩下那50%了，差那么5分钟，没写完这题。

#华为##笔试题目##笔经#

全部评论

推荐最新楼层

Thfril

西北大学 Java

阿瞒牛逼

点赞回复分享

发布于 2019-08-28 22:00

只是个废柴

中国矿业大学 golang

华为ak A.cpp #include <bits/stdc++.h> using namespace std; int n; typedef long long ll; inline bool ok(ll i, ll j, ll k) { ll a = i*i+j*j; ll b = k*k; return a == b; } int main() { while (cin >> n) { // cout << ok(20, 48, 52) <<endl; int cnt = 0; for(int i=1; i<=n/3; i++) { for(int j=i; i+j+j<=n; j++) { int k = n-i-j; if(i+j > k && ok(i,j,k)) { cnt++; //cout << i <<" " << j <<" " << k<<endl; } } } printf("%d\n", cnt); } return 0; } B.cpp #include <bits/stdc++.h> using namespace std; int mp[10][10]; int s[10]; int fa[100]; void init() { for(int i=0; i<60; i++) fa[i] = i; } int _fi(int x) { return fa[x] == x ? x : fa[x] = _fi(fa[x]); } void _merge(int u, int v) { int fu = _fi(u); int fv = _fi(v); fa[fu] = fv; return ; } bool ok(int u, int v) { if(u -1 == v || u + 1 == v || u-10 == v || u+10 == v) return true; return false; } int main() { while(~scanf("%d %d %d %d %d %d", &s[1], &s[2], &s[3], &s[4], &s[5], &s[6])) { init(); for(int i=1; i<=6; i++) { for(int j=i+1; j<=6; j++) { int u = s[i], v = s[j]; if(ok(u,v)) { // cout << u <<" " << v <<endl; _merge(i, j); } } } bool f = true; for(int i=2; i<=6; i++) { if(_fi(i) != _fi(i-1)) { f = false; break; } } if(f) puts("1"); else puts("0"); } return 0; } C.cpp 就是个LIS变形把 #include <bits/stdc++.h> using namespace std; const int N = 1e5+10; const int INF = 0x3f3f3f3f; int n; int s1[N], s2[N]; int pos[N]; unordered_map<int, int> mp1, mp2; int dp[N]; int main() { while(~scanf("%d", &n)) { mp1.clear(); mp2.clear(); memset(pos, 0, sizeof(pos)); for(int i=1; i<=n; i++) { scanf("%d", &s1[i]); mp1[s1[i]] = i; } for(int i=1; i<=n; i++) { scanf("%d", &s2[i]); mp2[s2[i]] = i; } for(int i=1; i<=n; i++) { pos[i] = mp2[s1[i]]; } fill(dp, dp+n, INF); // pos[i] lis for(int i=1; i<=n; i++) { *lower_bound(dp, dp+n, pos[i]) = pos[i]; } printf("%d\n", n - (lower_bound(dp, dp+n, INF) - dp)); } return 0; }

点赞回复分享

发布于 2019-08-28 21:48