包子小道消息
- Baoke Zhang这个小伙子最近火了，惊动了FBI。包子君猜想可能是为了占点小便宜，结果没想到结果有点严重。大家都是技术宅，武功高强，尽量不作恶吧。https://www.justice.gov/opa/pr/software-engineer-charged-washington-covid-relief-fraud
- 据说爱彼迎409A股票腰斩了？非常良心的公司，希望疫情过去一切都会好起来，反正包子君是宅的有点受不了(这不都开始做Google Code Jam了嘛。。)，结束了肯定要用airbnb旅游一下。
- Uber 北美又一波裁员落下帷幕，其他region受制于各地法律，慢慢来过。3000名优秀的工程师，数据科学家，产品经理和运维收到了影响。Uber这几年也有点Amazon的意思，硅谷 的黄埔军校，真的没有调侃，真有点马爸爸说的给社会输出人才的意思。其中不乏包子君认识的朋友，坚信大家都会挺过去，一切都会好起来的。It seems the worst of times, it could very well be the best of times as well！
- 在程序员圈子里混，长得高大帅气像美国队长一样也还是好的。Tiktok收了Kevin Mayer，师夷长技以制夷，吹响咱们中国企业征服西方世界的号角！
Google Code Jam 2020 Qualification Round: Nesting Depth Solution
Blogger: http://blog.baozitraining.org/2020/05/google-code-jam-2020-qualification-nesting-depth.html
Youtube: https://youtu.be/JqNCQlnvVRQ
博客园: https://www.cnblogs.com/baozitraining/p/12866793.html
B站: https://www.bilibili.com/video/BV1uz411B7eH/
Problem Statement
Problem
tl;dr: Given a string of digits S, insert a minimum number of opening and closing parentheses into it such that the resulting string is balanced and each digit d is inside exactly d pairs of matching parentheses.
Let the nesting of two parentheses within a string be the substring that occurs strictly between them. An opening parenthesis and a closing parenthesis that is further to its right are said to match if their nesting is empty, or if every parenthesis in their nesting matches with another parenthesis in their nesting. The nesting depth of a position p is the number of pairs of matching parentheses m such that p is included in the nesting of m.
For example, in the following strings, all digits match their nesting depth: 0((2)1), (((3))1(2)), ((((4)))), ((2))((2))(1). The first three strings have minimum length among those that have the same digits in the same order, but the last one does not since ((22)1) also has the digits 221 and is shorter.
Given a string of digits S, find another string S’, comprised of parentheses and digits, such that:
- all parentheses in S’ match some other parenthesis,
- removing any and all parentheses from S’ results in S,
- each digit in S’ is equal to its nesting depth, and
- S’ is of minimum length.
Input
The first line of the input gives the number of test cases, T. T lines follow. Each line represents a test case and contains only the string S.
Output
For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the string S' defined above.
Limits
Time limit: 20 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
1 ≤ length of S ≤ 100.
Test set 1 (Visible Verdict)
Each character in S is either 0 or 1.
Test set 2 (Visible Verdict)
Each character in S is a decimal digit between 0 and 9, inclusive.
Sample
Input
Output
4
0000
101
111000
1Case #1: 0000
Case #2: (1)0(1)
Case #3: (111)000
Case #4: (1)
The strings ()0000(), (1)0(((()))1) and (1)(11)000 are not valid solutions to Sample Cases #1, #2 and #3, respectively, only because they are not of minimum length. In addition, 1)( and )(1 are not valid solutions to Sample Case #4 because they contain unmatched parentheses and the nesting depth is 0 at the position where there is a 1.
You can create sample inputs that are valid only for Test Set 2 by removing the parentheses from the example strings mentioned in the problem statement.
Problem link
Video Tutorial
You can find the detailed video tutorial here
- Youtube
- B站
Thought Process
Simple simulation. Key points
- An integer could be used for depth to record how many parentheses we need to append. (I used a stack in the code during the competition
- We could use a dummy node as the depth is 0 instead of starting from index 1.
Solutions
Simulation solution
1 import java.io.BufferedReader;
2 import java.io.InputStreamReader;
3 import java.util.Scanner;
4 import java.util.Stack;
5
6 public class Solution {
7 public static void main(String[] args) {
8 Scanner s = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
9
10 int testCases = s.nextInt();
11 s.nextLine(); // skip to next line
12 int caseNum = 1;
13 Solution nestingDepth = new Solution();
14
15 while (caseNum <= testCases) {
16 String n = s.nextLine();
17 System.out.println(String.format("Case #%d: %s", caseNum, nestingDepth.minBrackets(n)));
18 caseNum++;
19 }
20 }
21
22 private String minBrackets(String s) {
23 int[] digits = new int[s.length()];
24 for (int i = 0; i < s.length(); i++) {
25 digits[i] = s.charAt(i) - '0';
26 }
27 if (digits == null || digits.length == 0) {
28 return null;
29 }
30
31 Stack<Character> stack = new Stack<>();
32 StringBuilder sb = new StringBuilder();
33 for (int i = 0; i < digits[0]; i++) {
34 stack.push('(');
35 sb.append("(");
36 }
37
38 sb.append(digits[0]);
39
40 for (int i = 1; i < digits.length; i++) {
41 if (digits[i] > digits[i - 1]) {
42 for (int k = 0; k < digits[i] - digits[i - 1]; k++) {
43 stack.push('(');
44 sb.append("(");
45 }
46 } else if (digits[i] < digits[i - 1]) {
47 for (int k = 0; k < digits[i - 1] - digits[i]; k++) {
48 stack.pop();
49 sb.append(")");
50 }
51 }
52
53 sb.append(digits[i]);
54 }
55
56 while (!stack.isEmpty()) {
57 stack.pop();
58 sb.append(")");
59 }
60
61 return sb.toString();
62 }
63 }Time Complexity: O(N)
Space Complexity: O(N) since we used extra extra space to store the output
References
- Google Code Jam official solution
