leetcode算法记录 leetcode算法记录

数组中的第K个最大元素题目在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

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

解题思路

利用快排的思想，当排序到 k 后，停止排序，输出结果

public static int findKthLargest(int[] nums, int k) { fastSort(nums, 0, nums.length - 1); return nums[nums.length - k]; }public static void fastSort(int[] nums, int start, int end) { if (nums.length <= 1) { return; }if (start > end) { return; }if (end < 0 || start < 0 || end > nums.length - 1 || start > nums.length - 1) { return; }int left = start, right = end; int keyIndex = (left + right) / 2; while (left < right) { while (right > keyIndex && nums[right] > nums[keyIndex]) { right--; }if (right > keyIndex) { swap(nums, keyIndex, right); keyIndex = right; }while (left < keyIndex && nums[left] < nums[keyIndex]) { left++; }if (left < keyIndex) { swap(nums, left, keyIndex); keyIndex = left; } left++; }fastSort(nums, keyIndex + 1, end); fastSort(nums, start, keyIndex - 1); }

三数之和头条重点
题目给定一个包含 n 个整数的数组 nums ，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，满足要求的三元组集合为： [ [-1, 0, 1], [-1, -1, 2] ]

解题思路

将数组排序
固定一位数，然后通过两个指针对撞，寻找总和为 0 的三个数

public static List> threeSum(int[] nums) { if (nums.length < 3) { return Collections.emptyList(); }Set> res = new HashSet<>(); Arrays.sort(nums); int zCount = 0; for (int num : nums) { if (num == 0) { zCount++; } }for (int i = 0; i < nums.length && nums[i] < 0; i++) { int first = nums[I]; int j = i + 1; int k = nums.length - 1; while (j < k) { int t = nums[j] + nums[k] + first; if (t == 0) { List list = new ArrayList<>(); list.add(first); list.add(nums[j]); list.add(nums[k]); res.add(list); j++; k--; } else if (t > 0) { k--; } else { j++; } }}if (zCount >= 3) { List list = new ArrayList<>(); list.add(0); list.add(0); list.add(0); res.add(list); } return new ArrayList<>(res); }

环形链表 II 题目 【leetcode算法记录】给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。
解题思路

首先通过快慢指针确定链表是否有环
再使用一个指针从头节点与快慢指针相遇节点同步长前进，最终找到环的入口

public ListNode detectCycle(ListNode head) { ListNode fast = head, slow = head; ListNode meetNode = null; while (fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; if (fast == slow) { meetNode = fast; break; } }if (meetNode == null) { return meetNode; }while (head != meetNode) { head = head.next; if (head == meetNode) { break; }meetNode = meetNode.next; }return meetNode; }

两数相加头条重点
题目给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例：输入：(2 -> 4 -> 3) + (5 -> 6 -> 4) 输出：7 -> 0 -> 8 原因：342 + 465 = 807

解题思路

public ListNode addTwoNumbers(ListNode l1, ListNode l2) { if (l1 == null || l2 == null) { return null; }StringBuilder builder1 = new StringBuilder(); while (l1 != null) { builder1.append(l1.val); l1 = l1.next; }StringBuilder builder2 = new StringBuilder(); while (l2 != null) { builder2.append(l2.val); l2 = l2.next; }BigDecimal bigDecimal1 = new BigDecimal(builder1.reverse().toString()); BigDecimal bigDecimal2 = new BigDecimal(builder2.reverse().toString()); String resStr = bigDecimal1.add(bigDecimal2).toPlainString(); ListNode head = new ListNode(Integer.parseInt(String.valueOf(resStr.charAt(resStr.length() - 1)))); ListNode cur = head; for (int i = resStr.length() - 2; i >= 0; i--) { cur.next = new ListNode(Integer.parseInt(String.valueOf(resStr.charAt(i)))); cur = cur.next; }return head; }

反转链表头条重点
题目反转一个单链表。

示例:输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL

解题思路

三个指针进行反转

public ListNode reverseList(ListNode head) { if (head == null) { return head; }if (head.next == null) { return head; }ListNode pre = head; ListNode cur = head.next; while (cur != null) { ListNode next = cur.next; cur.next = pre; pre = cur; cur = next; }head.next = null; return pre; }

合并两个有序链表题目将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4

解题思路

public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if (l1 == null && l2 == null) { return null; }if (l1 == null) { return l2; }if (l2 == null) { return l1; }ListNode head; if (l1.val > l2.val) { head = l2; l2 = l2.next; } else { head = l1; l1 = l1.next; }ListNode res = head; while (true) { ListNode cur; if (l1 == null && l2 == null) { break; }if (l1 == null) { cur = l2; l2 = l2.next; } else if (l2 == null) { cur = l1; l1 = l1.next; } else if (l1.val > l2.val) { cur = l2; l2 = l2.next; } else { cur = l1; l1 = l1.next; }head.next = cur; head = head.next; }return res; }

相交链表题目编写一个程序，找到两个单链表相交的起始节点。
解题思路

首先将两个链表中长的一个向前遍历，直到两个链表长度一致
两个链表同时向前遍历，便可找到交点

public ListNode getIntersectionNode(ListNode headA, ListNode headB) { if (headA == null || headB == null) { return null; }if (headA == headB) { return headA; }int lenA = 1; int lenB = 1; ListNode temp = headA; while (temp.next != null) { temp = temp.next; lenA++; }ListNode tailA = temp; temp = headB; while (temp.next != null) { temp = temp.next; lenB++; }ListNode tailB = temp; if (tailB != tailA) { return null; }if (lenA > lenB) { for (int i = 0; i < lenA - lenB && headA != null; i++) { headA = headA.next; }} else if (lenA < lenB) { for (int i = 0; i < lenB - lenA && headB != null; i++) { headB = headB.next; } }while (!headA.equals(headB)) { headA = headA.next; headB = headB.next; }return headA; }

合并K个排序链表头条重点
题目合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例:输入: [ 1->4->5, 1->3->4, 2->6 ] 输出: 1->1->2->3->4->4->5->6

解题思路

通过小根堆，将所有元素放入小根堆
从小根堆依次取出数据

public ListNode mergeKLists(ListNode[] lists) { if (lists == null) { return null; }Queue set = new PriorityQueue<>(Comparator.comparingInt(o -> o.val)); for (ListNode node : lists) { while (node != null) { set.add(node); node = node.next; } }ListNode head = new ListNode(-1); ListNode res = head; ListNode cur; while ((cur = set.poll()) != null) { head.next = cur; head = head.next; }head.next = null; return res.next; }

翻转字符串里的单词题目给定一个字符串，逐个翻转字符串中的每个单词。

示例 1：输入: "the sky is blue" 输出: "blue is sky the"

说明：

无空格字符构成一个单词。
输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

解题思路

按空格拆分字符串为字符串数组 t
逆序遍历字符串数组 t，并组成新的字符串

public String reverseWords(String s) { String trimed = s.trim(); String[] split = trimed.split(" "); StringBuilder builder = new StringBuilder(); for (int i = split.length - 1; i >= 0; i--) { String t = split[I]; if (t.trim().isEmpty()) { continue; }builder.append(t).append(" "); }return builder.toString().trim(); }

无重复字符的最长子串头条重点
题目给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。

输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

解题思路

用 Map 记录字符所在位置，当遇到重复字符时，移动 start 指针
替换 Map 中下标，并计算子串长度

public int lengthOfLongestSubstring(String str) { if (str == null || str.length() == 0) return 0; HashMap temp = new HashMap<>(); char[] chars = str.toCharArray(); int res = 0, start = 0; for (int i = 0; i < chars.length; i++) { if (temp.containsKey(chars[i])) { start = Math.max(temp.put(chars[i], i) + 1, start); }temp.put(chars[i], i); res = Math.max(res, i - start + 1); }return res; }

排序链表头条重点
题目在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

示例 1:输入: 4->2->1->3 输出: 1->2->3->4 示例 2:输入: -1->5->3->4->0 输出: -1->0->3->4->5

解题思路

通过快慢指针将链表拆分
递归进行拆分，再通过合并两个排序链表的方式进行合并
类似于归并排序

public ListNode sortList(ListNode head) { if (head == null || head.next == null) { return head; }ListNode slow = head, fast = head; while (fast.next != null && fast.next.next != null) { fast = fast.next.next; slow = slow.next; }ListNode mid = slow.next; slow.next = null; ListNode l1 = sortList(head); ListNode l2 = sortList(mid); return merge(l1, l2); }private ListNode merge(ListNode l1, ListNode l2) { if (l1 == null) { return l2; }if (l2 == null) { return l1; }ListNode head,res; if (l1.val > l2.val) { head = l2; l2 = l2.next; } else { head = l1; l1 = l1.next; } res = head; //head.next = null; while (l1 != null || l2 != null) { if (l1 == null) { head.next = l2; l2 = l2.next; } else if (l2 == null) { head.next = l1; l1 = l1.next; } else { if (l1.val > l2.val) { head.next = l2; l2 = l2.next; } else { head.next = l1; l1 = l1.next; } } head = head.next; }return res; }