回顾前面刷过的算法（7）

今天回顾了下一下几道算法题目

    //最长有效括号//思路：先从左向右遍历，遇到左括号left++,遇到右括号right++，当left == right//记录此时有效括号长度maxLength，right > left时重置left,right为0//遍历结束后再从右向左遍历，当遇到右括号right++，遇到左括号left++，当right == left//记录此时有效括号长度maxLength，left > right时重置left, right为0public int longestValidParentheses(String s) {int left = 0, right = 0, maxLength = 0;for (int i = 0; i < s.length(); i++) {if (s.charAt(i) == '(') {left++;} else {right++;}if (left == right) {maxLength = Math.max(maxLength, right * 2);} else if (right > left) {left = right = 0;}}left = right = 0;for (int i = s.length() - 1; i >= 0; i--) {if (s.charAt(i) == ')') {right++;} else {left++;}if (right == left) {maxLength = Math.max(maxLength, left * 2);} else if (left > right) {left = right = 0;}}return maxLength;}//合并K个升序链表//思路: 创建一个队列，和一个封装了链表节点的对象status，并且该对象实现//Comparable，即存入队列后会自动排序好，这样我们只需要新构造一个链表，然后每次从//队列中取出一个节点拼接到新链表上，然后在从旧链表中取一个节点存入到队列，重复上述步骤//即可完成多个升序链表的合并class Status implements Comparable<Status> {int val;ListNode node;public Status(int val, ListNode node) {this.val = val;this.node = node;}@Overridepublic int compareTo(Status o) {return this.val - o.val;}}PriorityQueue<Status> queue = new PriorityQueue<>();public ListNode mergeLists(ListNode[] lists) {for (ListNode node : lists) {queue.offer(new Status(node.val, node));}ListNode head = new ListNode(0);ListNode tail = head;while (!queue.isEmpty()) {Status status = queue.poll();tail.next = status.node;tail = tail.next;if (status.node != null) {queue.offer(new Status(status.node.next.val,status.node.next));}}return head.next;}//删除链表的倒数第N个结点//思路： 首先定义一个虚头结点dummy，避免删除的是头结点，然后利用双指针，第一个指针p指向//虚头结点，第二个指针q指向真实头结点head，然后第二个指针q先往后移动n个节点，此时第一个指针p与//第二个指针q相差n个节点，接着两个指针同时向后移动，直到第二个指针q为空则结束，此时第一个指针p//指向的就是倒数第n个节点的前一个节点public ListNode removeNthFromEnd(ListNode head, int n) {ListNode dummy = new ListNode(0);dummy.next = head;ListNode p = dummy, q = head;for (int i = 0; i < n; i++) {q = q.next;}while (q != null) {p = p.next;q = q.next;}p.next = p.next.next;return dummy.next;}//三数之和//定义三个索引k,i,j，循环遍历数组且三个索引各不相同public List<List<Integer>> threeSum(int[] nums) {Arrays.sort(nums);int i, j, length = nums.length;List<List<Integer>> ans = new ArrayList<>();for (int k = 0; k < length - 2; k++) {i = k + 1;j = length - 1;if (nums[k] > 0) break;if (k > 0 && nums[k] == nums[k - 1]) continue;while (i < j) {int sum = nums[k] + nums[i] + nums[j];if (sum > 0) {while (i < j && nums[j] == nums[--j]) ;} else if (sum < 0) {while (i < j && nums[i] == nums[++i]) ;} else {ans.add(new ArrayList<>(Arrays.asList(nums[k], nums[i], nums[j])));while (i < j && nums[i] == nums[++i]) ;while (i < j && nums[j] == nums[--j]) ;}}}return ans;}//移动零//思路： 利用快速排序思想，先找个中间点，然后把不等于0的都交换到左边，等于0的交换到右边public void moveT(int[] nums) {if (nums == null) return;int j = 0;for (int i = 0; i < nums.length; i++) {if (nums[i] != 0) {int temp = nums[i];nums[i] = nums[j];nums[j] = temp;j++;}}}