知能科技 软件开发 笔试

#软件开发2023笔面经#

随便投的一个公司,发现居然也要在牛客上笔试

A. cf原题

https://codeforces.com/contest/1802/problem/B

#include<bits/stdc++.h>

int A[100005];

void solve() {
  int n;
  std::cin >> n;
  for (int i = 1; i <= n; i++) {
    std::cin >> A[i];
  }
  int x = 0, y = 0, unknown = 0, pre = 0, ans = 0;
  for (int i = 1; i <= n; i++) {
    if (A[i] == 1) {
      ++unknown;
    } else if (A[i] == 2) {
      pre += unknown;
      unknown = 0;
    }
    std::cerr << i << ' ' << ans << ' ' << unknown << ' ' << pre << ' ' << unknown + pre / 2 + 1 << '\n';
    if (pre) {
      ans = std::max(ans, unknown + pre / 2 + 1);
    } else {
      ans = std::max(ans, unknown);
    }
  }
  std::cout << ans << '\n';
}

int main() {
  std::cin.tie(nullptr) -> sync_with_stdio(false);
  int T = 1;
  //std::cin >> T;
  while (T--) {
    solve();
  }
  return 0;
}

B. 构造题

定义美丽值为矩阵相邻数字的绝对值大小种类,例如:

[1 2

4 3]

有|1 - 4| = 3, |1 - 2| = 1, |2 - 3| = 1, |4 - 3| = 1, 有两种。

给定一个n <= 150, 构造 n * n矩阵使得美丽值最大。

构造思路:

n为奇数:

1, n, 2, n - 1, 3

n -2, 4, n - 3....

..........

n为偶数:

1, n, 2, n - 1, 3

....n - 3, 4, n - 2

...................

不难看出这样构造是可以达到最优值的。

#include<bits/stdc++.h>

int A[2222][2222];
int dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};

int n;
void solve(int cas) {
  std::cin >> n;
  if (n == 2) {
    std::cout << "1 3\n4 2\n";
    return ;
  }
  if ((n & 1)) {
    int flag = 0;
    int x = 1, y = n * n;
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
        if (!flag) {
          A[i][j] = x++;
        } else {
          A[i][j] = y--;
        }
        flag ^= 1;
      }
    }
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
        std::cout << A[i][j] << " \n"[j == n];
      }
    }
  } else {
    std::map<int, int> mp;
    int flag = 1;
    int x = 1, y = n * n;
    for (int i = 1; i <= n; i++) {
      if (i & 1) {
        for (int j = 1; j <= n; j++) {
          if (!flag) {
            A[i][j] = x++;
          } else {
            A[i][j] = y--;
          }
          flag ^= 1;
        }
      } else {
        for (int j = n; j >= 1; j--) {
          if (!flag) {
            A[i][j] = x++;
          } else {
            A[i][j] = y--;
          }
          flag ^= 1;
        }
      }
    }
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
        std::cout << A[i][j] << " \n"[j == n];
      }
    }
  }
}
void solve() {
  // std::cin >> n;
  // for (int i = 1; i <= n; i++) {
  //   for (int j = 1; j <= n; j++) {
  //     std::cin >> A[i][j];
  //   }
  // }
  std::set<int> st;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      for (int k = 0; k < 4; k++) {
        int nx = i + dir[k][0], ny = j + dir[k][1];
        if (nx >= 1 and ny >= 1 and nx <= n and ny <= n) {
          st.emplace(std::abs(A[i][j] - A[nx][ny]));
          //std::cerr << i << ' ' << j << ' ' << A[i][j] << ' ' << A[nx][ny] << '\n';
        }
      }
    }
  }
  std::cerr << "debug: "  << st.size() << '\n';
}

int main() {
  std::cin.tie(nullptr) -> sync_with_stdio(false);
  int T = 1;
  //std::cin >> T;
  while (T--) {
    solve(T);
    solve();
  }
  return 0;
}

附加题:求一个长度为n(n <= 200000) 的序列中,长度不小于k的最大中位数,只需要给出思路

思路:二分答案,原数组可以转化成-1,1,那么求一个前缀和,对于每个位置 i,我都考查一下 [1, i - k + 1] 中是否存在一个Sum[j],使得 Sum[i] - Sum[j] >= 0 即可,这个可以维护前缀最小值去实现。

时间复杂度 O(nlogn), 空间复杂度 O(n)。

全部评论
好厉害,感觉自己是笨蛋
1 回复 分享
发布于 2023-04-17 13:46 北京
点赞 回复 分享
发布于 2023-04-04 19:27 广东
请问您去这个公司了吗?这个公司怎么样呢
点赞 回复 分享
发布于 2023-06-04 08:33 美国

相关推荐

03-13 15:32
已编辑
安徽理工大学 Java
1.自我介绍2.Redis相关:&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;缓存穿透:什么是缓存穿透&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;介绍存空值与布隆过滤器的方案&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;缓存击穿:什么是缓存击穿&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;介绍解决缓存击穿的方案&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;缓存过期的原理(惰性删除+定期删除,面试时说成内存淘汰策略了)3.spring:&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;spring核心特性&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;介绍一下IOC和AOP&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;AOP的使用场景&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;AOP的原理&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;什么时候使用cglib代理而不使用jdk(忘了)4.MySQL&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;索引的作用&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;索引的弊端及原理&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;索引失效的场景&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;你说了索引会在区分度小的时候会走全表扫描,那该索引优化出现在哪个阶段&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;如何查看索引的使用情况&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;MySQL索引的数据结构&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;b+树的特性与优点&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;为什么b+树层低会使查询效率很高5.算法题:LeetCode108:将有序数组转换为二叉搜索树(还是不熟,太fw了我,一开始看成搜索树转有序数组了。写了五分钟让说思路,面试官说思路大概对了)6.反问:建议:面试准备的还可以,简历挺喜欢的(写了两个烂大街项目竟然还得到了面试官认可),对相关原理都有一定了解,对一些点可以更深入学习。全长35min,面试官非常友好,经常对回答进行补充,对没答出来的点也详细解答了,小厂面试体验最好的一集另外附上目前实习oc情况,除了这家还有昨天一家没出结果,求🐮u们建议2.21&nbsp;&nbsp;挂#面试体验感最好的是哪家?# #哪些公司面试官让你印象深刻?# &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
点赞 评论 收藏
分享
评论
2
3
分享

创作者周榜

更多
牛客网
牛客企业服务