京东2019春招编程题

以你之姓@ 2022-05-27 02:18 250阅读 0赞

转载链接：[https://www.nowcoder.com/discuss/72829?type=0&order=0&pos=12&page=1][https_www.nowcoder.com_discuss_72829_type_0_order_0_pos_12_page_1]

java实现参考: [https://www.nowcoder.com/discuss/72849?type=2&order=0&pos=9&page=1][https_www.nowcoder.com_discuss_72849_type_2_order_0_pos_9_page_1]

## 牛牛的括号匹配 ##

### 分析 ###

考虑如何判断一个串是否合法的过程： 依次处理字符，若是'('则入栈，若是')'则从栈中弹出一个'('. 若没有'('则不合法. 那么此题就是上述过程的变种，在处理过程中允许两次变换.可以只考虑')'->'('的方向. 1、如果当前是'('，直接入栈. 2、如果当前是')'，如果栈非空，则弹出一个'('; 如果栈空就把当前的')'变成'('入栈. (标记最多只能变化一次). 用flag标记是否有将')'变为'('的操作. 结果栈要么为空，要么全是'('.

1.  如果整个字串没有被处理完，那么肯定是"No".
2.  如果flag=0, 那么要求没有'('剩下.
3.  如果flag=1, 那么结果栈中的'('只能是两个. "((" -> "()".

### 时间复杂度 ###

O(len(s))

### 参考代码 ###

#include <bits/stdc++.h>
     
    using namespace std;
     
    const int maxn = 1e5 + 10;
     
    char str[maxn];
    stack<char> s;
     
    int main() {
        int t;
        cin >> t;
        while(t--) {
            while(!s.empty()) s.pop();
            scanf("%s", str);
            int n = strlen(str);
            if(n == 2) {
                if(str[0] == '(' && str[1] == ')') {
                    puts("No");
                    continue;
                }
            }
            int i;
            int flag1 = 0;
            for(i = 0; i < n; i++) {
                if(str[i] == '(') {
                    s.push('(');
                } else {
                    if(!s.empty()) s.pop();
                    else {
                        if(flag1) break;
                        flag1 = 1;
                        s.push('(');
                    }
                }
            }
            if(i == n) {
                if(!flag1) {
                    if(s.empty()) puts("Yes");
                    else puts("No");
                }
                else {
                    if(s.size() != 2) puts("No");
                    else puts("Yes");
                }
            }
            else puts("No");
        }
        return 0;
    }

## 分解整数 ##

### 分析 ###

范围巨大。。  
但是直觉上觉得可以很快出答案，  
于是答案枚举一个数,判断另外一个数的合法性。  
就跑过了。。

### 时间复杂度 ###

O(跑得过)

### 参考代码 ###

#include <bits/stdc++.h>
     
    int main() {
        int t;
        long long n, x, y;
        scanf("%d", &t);
        while(t--) {
            scanf("%lld", &n);
            if(n & 1)
                printf("No\n");
            else {
                for(y = 2; y <= n; y += 2) {
                    if(n % y == 0 && ((n / y) & 1)) {
                        x = n / y;
                        break;
                    }
                }
                printf("%lld %lld\n", x, y);
            }
        }
        return 0;
    }

## 生成回文串 ##

### 分析 ###

dp\[l\]\[r\]表示区间 \[l, r\] 内的回文串数目。  
于是dp\[l\]\[r\] = dp\[l\]\[r - 1\] + dp\[l + 1\]\[r\],  
根据s\[l\] ?= s\[r\], 来看是+1还是减掉重复的部分。

### 时间复杂度 ###

O(n^2)

### 参考代码 ###

#include <bits/stdc++.h>
     
    using namespace std;
    typedef long long LL;
    const int maxn = 50 + 5;
    LL dp[maxn][maxn];
    char s[maxn];
    int main() {
        scanf("%s", s + 1);
        int len = strlen(s + 1);
        memset (dp, 0, sizeof(dp));
        for(int i = 1; i <= len; i++) {
            for(int l = 1; l + i - 1 <= len; l++) {
                int r = l + i - 1;
                dp[l][r] += dp[l + 1][r];
                dp[l][r] += dp[l][r - 1];
                if (s[l] == s[r]) dp[l][r] += 1;
                else dp[l][r] -= dp[l + 1][r - 1];
            }
        }
        printf ("%lld\n", dp[1][len]);
        return 0;

[https_www.nowcoder.com_discuss_72829_type_0_order_0_pos_12_page_1]: https://www.nowcoder.com/discuss/72829?type=0&order=0&pos=12&page=1
[https_www.nowcoder.com_discuss_72849_type_2_order_0_pos_9_page_1]: https://www.nowcoder.com/discuss/72849?type=2&order=0&pos=9&page=1