首页 > 2021英礡Improbable笔试题2道
头像
煎饼果子w
编辑于 2021-04-19 11:38
+ 关注

2021英礡Improbable笔试题2道

2021 Improbable Intern Online Test
英礡的题都是英文题面,需要注意一下。

第一题:有效的括号 / Match Brackets

签到题,直接用栈做,不过这里有点坑的是给的字符串还包含了其他的字符,不止有“()[]{}”这些。
同:20. 有效的括号 - 力扣(LeetCode)​https://leetcode-cn.com/problems/valid-parentheses/

代码

public static boolean validString(String s) {
    // write code here
    char[] sc = s.toCharArray();
    int n = sc.length;
    char[] stack = new char[n];
    int top = -1;

    Map<Character, Character> map = new HashMap<>(3);
    map.put(')', '(');
    map.put(']', '[');
    map.put('}', '{');

    for (int i = 0; i < n; ++i) {
        if(map.containsKey(sc[i])) {
            if(top == -1 || stack[top] != map.get(sc[i])) {
                return false;
            }
            top--;
        } else if(sc[i] == '(' || sc[i] == '[' || sc[i] == '{') {
            stack[++top] = sc[i];
        }
    }
    return top == -1;
}

第二题:循环移除卡牌 / Remove Cards in Circle

给定一个数N和K,表示现在有1,2,3,...,N张编号的卡牌,现在摆成一个圆,从第一张开始间隔K张进行
移除,直到最后只剩下一张牌为止,给出牌的编号。

其实就是约瑟夫环的问题。

输入输出

Input:
N=10,K=3
Output:
4
// 移除过程中的卡牌编号依次为3->6->9->2->7->1->8->5->10

用模拟法能做,但时间复杂度过高,这里需要用递推的方法。
见 约瑟夫环——公式法(递推公式)https://blog.csdn.net/u011500062/article/details/72855826

代码

public static int solution(int N, int K) {
    // write code here
    int t = 0;
    for (int i = 2; i <= N; ++i) {
        t = (t + K) % i;
    }
    return t + 1;
}

全部评论

(1) 回帖
加载中...
话题 回帖

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐