Java 题解 | #牛圈围栏问题#

牛圈围栏问题

https://www.nowcoder.com/practice/4e3bb97bbc2b4382a745abe953f44aee

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     *
     * @param n int整型
     * @return string字符串一维数组
     */
    private List<String> res = new ArrayList<>();
    private StringBuilder path = new StringBuilder();

    private void dfs(int u, int l, int r, int idx) {
        if (path.length() == u * 2) {
            res.add(path.toString());
            return;
        }
        if (l > 0) {
            path.append('(');
            dfs(u, l - 1, r, idx + 1);
            path.deleteCharAt(path.length() - 1);
        }
        if (l < r) {
            path.append(')');
            dfs(u, l, r - 1, idx + 1);
            path.deleteCharAt(path.length() - 1);
        }
    }

    public String[] generateParenthesis(int n) {
        dfs(n, n, n, 0);
        String[] result = new String[res.size()];
        for (int i = 0; i < res.size(); i++) {
            result[i] = res.get(i);
        }
        return result;
    }
}

编程语言是Java。

该题考察的知识点包括:

  • 递归
  • 字符串操作
  • 列表(ArrayList)的使用

代码的文字解释如下:

  1. 定义一个字符串构建器 path,用于构建每种括号组合。
  2. 实现一个递归函数 dfs,接受四个参数:u 表示需要生成的括号对数,l 表示当前已有的左括号数,r 表示当前已有的右括号数,idx 表示当前所在位置的索引。
  3. 在递归函数 dfs 中,首先判断是否已经生成了指定数量的括号对(即 path.length() 是否等于 u * 2),如果是,则将当前括号组合添加到结果列表 res 中,并返回。
  4. 分别处理两种情况:如果左括号数还未达到指定数量,可以在当前位置添加一个左括号,并递归调用 dfs 函数增加左括号数;如果左括号数小于右括号数(即还有可以匹配的左括号),可以在当前位置添加一个右括号,并递归调用 dfs 函数增加右括号数。
  5. 在递归函数 dfs 中,完成每次递归后需要的清理工作,即将当前位置的括号删除(通过 path.deleteCharAt(path.length() - 1))。
  6. 实现 generateParenthesis 方法,接受一个整数 n 作为参数,并返回生成的括号组合数组。
  7. 在 generateParenthesis 方法中,调用递归函数 dfs 来生成括号组合。
全部评论

相关推荐

Twilight_m...:表格简历有点难绷。说说个人看法: 1.个人基本情况里好多无意义信息,什么婚姻状况、健康状况、兴趣爱好、户口所在地、身份证号码、邮政编码,不知道的以为你填什么申请表呢。 2.校内实践个人认为对找工作几乎没帮助,建议换成和测开有关的项目,实在没得写留着也行。 3.工作经历完全看不出来是干什么的,起码看着和计算机没啥关系,建议加强描述,写点你在工作期间的实际产出、解决了什么问题。 4.个人简述大而空,看着像AI生成,感觉问题最大。“Python,C,C++成为我打造高效稳定服务的得力工具”、“我渴望凭借自身技术知识与创新能力,推动人工智能技术的应用发展,助力社会实现智能化转型”有种小学作文的美感。而且你确定你个人简述里写的你都会嘛?你AI这块写的什么“深入研究”,发几篇顶会的硕博生都不一定敢这么写。而且你AI这块的能力和软测也完全无关啊。个人简述建议写你对哪些技术栈、哪些语言、哪些生产工具的掌握,写的有条理些,而且最好是和测开强相关的。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务