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;
}