本文介绍: 数字 n 代表生成括号的对数,请你设计一个函数用于能够生成所有可能的并且 有效的 括号组合示例 1:示例 1:输入:n = 3 输出:[“((()))”,“(()())”,“(())()”,“()(())”,“()()()”]示例 2:输入:n = 1 输出:[“()”]解题思路回溯算法。这一类问题是在一棵隐式的树上求解可以深度优先遍历,也可以用广度优先遍历。一般用深度优先遍历原因是:1.代码好写,使用递归方法,直接借助系统栈完成状态的转移;

括号生成

数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合
示例 1:

示例 1:
输入:n = 3 输出:[“((()))”,“(()())”,“(())()”,“()(())”,“()()()”]

示例 2:
输入:n = 1 输出:[“()”]

解题思路:回溯算法。这一类问题是在一棵隐式的树上求解可以用深度优先遍历,也可以用广度优先遍历。一般用深度优先遍历原因是:1.代码好写,使用递归方法,直接借助系统栈完成状态的转移;2.广度优先遍历自己编写结点类和借助队列

   public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        if (n == 0) {
            return res;
        }
        // 执行深度优先遍历,搜索可能结果
        dfs("", n, n, res);
        return res;
    }


     /**
     * @param curStr 当前递归得到的结果
     * @param left   左括号还有几个可以使用
     * @param right  右括号还有几个可以使用
     * @param res    结果集
     */
    private void dfs(String curStr, int left, int right, List<String&gt; res) {
        // 因为每一次尝试,都使用新的字符串变量,所以无需回溯
        // 在递归终止时候,直接把它添加到结果集即可,注意与「力扣」第 46 题、第 39 题区分
        if (left == 0 &amp;&amp; right == 0) {
            res.add(curStr);
            return;
        }

        // 剪枝如图,左括号可以使用的个数严格大于右括号可以使用的个数,才剪枝,注意这个细节
        if (left &gt; right) {
            return;
        }

        if (left > 0) {
            dfs(curStr + "(", left - 1, right, res);
        }


        if (right > 0) {
            dfs(curStr + ")", left, right - 1, res);
        }
    }

合并K个升序链表

给定一个链表数组每个链表都已经按升序排列。请将所有链表合并一个升序表中返回合并后的链表。

示例 1: 输入:lists = [[1,4,5],[1,3,4],[2,6]] 输出:[1,1,2,3,4,4,5,6]
解释:链表数组如下: [ 1->4->5, 1->3->4, 2->6 ] 将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6
示例 2: 输入:lists = [] 输出:[]
示例 3: 输入:lists = [[]] 输出:[]

解题思路:借助分治的思想,把K个有序链表两两合并即可

 public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }

        ListNode ans = null;
        for (int i = 0; i < lists.length; ++i) {
            ans = mergeTwoLists(ans, lists[i]);
        }
        return ans;
    }

     public ListNode mergeTwoLists(ListNode a, ListNode b) {
        if (a == null || b == null) {
            return a != null ? a : b;
        }
        ListNode head = new ListNode(0);
        ListNode tail = head, aPtr = a, bPtr = b;
        while (aPtr != null &amp;&amp; bPtr != null) {
            if (aPtr.val < bPtr.val) {
                tail.next = aPtr;
                aPtr = aPtr.next;
            } else {
                tail.next = bPtr;
                bPtr = bPtr.next;
            }
            tail = tail.next;
        }
        tail.next = (aPtr != null ? aPtr : bPtr);
        return head.next;
    }

两两交换链表中的节点

给你一个链表,两两交换其中相邻节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。

示例 1:
在这里插入图片描述

输入:head = [1,2,3,4] 输出:[2,1,4,3]

示例 2: 输入:head = [] 输出:[]

示例 3: 输入:head = [1] 输出:[1]

  public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode next = head.next;
        head.next = swapPairs(next.next);
        next.next = head;
        return next;
    }

K个一组翻转链表

给你链表的头节点 head ,每 k 个节点一组进行翻转,请你返回修改后的链表。k一个正整数,它的值小于或等于链表的长度。如果节点总数不是 k整数倍,那么请将最后剩余的节点保持原有顺序。你不能只是单纯的改变节点内部的值,而是需要实际进行节点交换

示例 1: 输入:head = [1,2,3,4,5], k = 2 输出:[2,1,4,3,5]
示例 2: 输入:head = [1,2,3,4,5], k = 3 输出:[3,2,1,4,5]

解题思路:要求k个相邻的元素翻转链表
步骤分解:

  1. 链表分区为已翻转部分+待翻转部分+未翻转部分
  2. 每次翻转前,要确定翻转链表的范围这个必须通过 k 次循环来确定
  3. 记录翻转链表前驱和后继,方便翻转完成后把已翻转部分和未翻转部分连接起来
  4. 初始需要两个变量 preendpre代表待翻转链表的前驱,end 代表待翻转链表的末尾
  5. 经过k此循环,end 到达末尾记录待翻转链表的后继 next = end.next
  6. 翻转链表,然后将三部分链表连接起来,然后重置 pre 和 end 指针然后进入下一次循环
  7. 特殊情况,当翻转部分长度不足 k 时,在定位end 完成后,end==null,已经到达末尾说明题目已完成,直接返回即可

 public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;

        ListNode pre = dummy;
        ListNode end = dummy;

        while (end.next != null) {
            for (int i = 0; i < k &amp;&amp; end != null; i++) {
                end = end.next;
            }
            if (end == null) {
                break;
            }
            ListNode start = pre.next;
            ListNode next = end.next;
            end.next = null;
            pre.next = reverse(start);
            start.next = next;
            pre = start;

            end = pre;
        }
        return dummy.next;

    }

    private ListNode reverse(ListNode head) {
        ListNode pre = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = pre;
            pre = curr;
            curr = next;
        }
        return pre;
    }

删除有序数组中的重复

给你一个严格递增排列数组 nums ,请你原地删除重复出现的元素,使每个元素只出现一次 ,返回删除后数组的新长度元素相对顺序应该保持 一致 。然后返回nums唯一元素个数
考虑 nums唯一元素的数量为 k ,你需要做以下事情确保你的题解可以被通过
更改数组 nums ,使 nums 的前 k 个元素包含唯一元素,并按照它们最初在 nums 中出现的顺序排列nums 的其余元素nums 的大小不重要。返回 k 。

解题思路:这里数组的删除并不是真的删除,只是将删除的元素移动数组的后面,然后返回数组实际剩余的元素个数。


 public int removeDuplicates(int[] nums) {
        if(nums == null || nums.length == 0) {
            return 0;
        }
        int p = 0;
        int q = 1;
        while(q < nums.length) {
            if(nums[p] != nums[q]) {
                nums[p + 1] = nums[q];
                p++;
            }
            q++;
        }
        return p + 1;
    }

原文地址:https://blog.csdn.net/javaJasonjava/article/details/134750449

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任

如若转载,请注明出处:http://www.7code.cn/show_32538.html

如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱suwngjj01@126.com进行投诉反馈,一经查实,立即删除!

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注