牛客网算法——名企面试的笔试（1）

22. 括号生成

题目描述

给出n对括号，请编写一个函数来生成所有的由n对括号组成的合法组合。

例如，给出n=3，解集为：

"((()))", "(()())", "(())()", "()()()", "()(())",

package 牛客网名气面试笔试问题2021;

import org.junit.Test;
import 牛客网练习题.Solution;

import java.util.ArrayList;
import java.util.List;

/**
 * @Classname 括号的生成
 * @Description TODO
 * @Date 2021/2/25 20:54
 * @Created by xjl
 */
public class 括号的生成 {


    @Test
    public void test(){
        generateParenthesis(2);
    }

    public ArrayList generateParenthesis2 (int n) {
        ArrayList ans = new ArrayList();
        dfs(ans, new StringBuilder(), 0, 0, n);
        return ans;
    }

    public List generateParenthesis(int n) {
        List ans = new ArrayList();
        dfs(ans, new StringBuilder(), 0, 0, n);
        return ans;
    }
    /**
     * @description TODO  使用的是的回溯的思想来构造这样的一个  就是一个二叉树的的剪枝思想
      * @param: ans
      * @param: cur
      * @param: left
      * @param: right
      * @param: max
      * @date: 2021/2/25 21:32
      * @return: void
      * @author: xjl
    */
    public void dfs(List ans, StringBuilder cur, int left, int right, int max) {
        //判断是的字符串的长度的以便于终止函数的跳出
        if (cur.length() == max * 2) {
            //添加到结果集中
            ans.add(cur.toString());
            return;
        }
        //左边的小于最大值得时候就加入左括号
        if (left < max) {
            cur.append('(');
            dfs(ans, cur, left + 1, right, max);
            //这里使用了回溯的方法 删除最后的一个
            cur.deleteCharAt(cur.length() - 1);
        }
        //当右边的小于左边的时候加入右边括号
        if (right < left) {
            cur.append(')');
            dfs(ans, cur, left, right + 1, max);
            cur.deleteCharAt(cur.length() - 1);
        }
    }
}

25. K 个一组翻转链表

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

package 牛客网名气面试笔试问题2021;

import java.util.List;

/**
 * @Classname 链表k个翻转
 * @Description TODO
 * @Date 2021/2/25 22:20
 * @Created by xjl
 */
public class 链表k个翻转 {

    public class ListNode{
        int val;
        ListNode next;
        public ListNode (int val){
            this.val=val;
        }
    }
    /**
     * @description TODO  将给出的链表中的节点每 k\ k k 个一组翻转，返回翻转后的链表  如果链表中的节点数不是 k\ k k 的倍数，将最后剩下的节点保持原样  你不能更改节点中的值，只能更改节点本身
     *
      * @param: head
     * @param: k
     * @date: 2021/2/25 22:24
     * @return: 牛客网名气面试笔试问题2021.链表k个翻转.ListNode
     * @author: xjl
    */
    public ListNode reverseKGroup (ListNode head, int k) {
        //边界情况的
        if (head==null||head.next==null||k