leetcode算法题学习Java版（2）
283.Move Zeros(移动零) 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。 示例: 输入: [0,1,0,3,12] 输出: [1,3,12,0,0] 说明: 必须在原数组上操作，不能拷贝额外的数组。 尽量减少操作次数。 class Solution { public void moveZeroes(int[] nums) { int k = 0; for(int i = 0;i<nums.length;i++){ if(nums[i]!=0){ if(i!=k){ int temp = nums[k]; nums[k] = nums[i]; nums[i] = temp; } k++; } } } } 75.Sort Colors（颜色分类） 给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地**对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。 此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。 注意: 不能使用代码库中的排序函数来解决这道题。 示例:输入: [2,0,2,1,1,0]输出: [0,0,1,1,2,2]进阶： 一个直观的解决方案是使用计数排序的两趟扫描算法。 首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。 你能想出一个仅使用常数空间的一趟扫描算法吗？ 解题思路，本题共三个元素，非常适合三路快排的方法，并且仅需扫描数组一遍即可完成排序 class Solution { public void sortColors(int[] nums) { int zero = -1; // nums[0...zero]==0 int two = nums.length; //nums[two...n-1]==2 for (int i = 0; i < two;) { if(nums[i]==0){ int temp = nums[++zero]; nums[zero] = nums[i]; nums[i++] = temp; }else if(nums[i]==1){ i++; }else{ assert nums[i]==2; int temp = nums[--two]; nums[two] = nums[i]; nums[i] = temp; } } } } 88.Merged sorted Array（合并有序数组） 给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。 说明: 初始化 nums1 和 nums2 的元素数量分别为 m 和 n。 你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。 示例: 输入: nums1 = [1,2,3,0,0,0], m = 3 nums2 = [2,5,6], n = 3 输出: [1,2,2,3,5,6] 解题思路：这道题解决很简单，但是最大效率的算法却也比较难想，很巧妙，暴力解法就是把两个数组合并，然后快排。但是参照了leetcode上别人的代码，效率更高，思路就是不断比较二者的最大值，把最大值放在nums1数组的最后，知道排序成功。 class Solution { public void merge(int[] nums1, int m, int[] nums2, int n) { int count = m + n - 1; m--; n--; while (m != -1 && n != -1) { nums1[count--] = nums1[m] > nums2[n] ? nums1[m--] : nums2[n--]; } while (n != -1) { nums1[count--] = nums2[n--]; } } } 215.Kth Largest Element in an Array（数组中第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 总是有效的，且 1 ≤ k ≤ 数组的长度。 这道题很有趣，他的解法非常多，我也是在这道题感受到了自己与大佬之间的差距，就算用同一种解法，别人的代码也比我写的优雅的多。令人哭笑不得的是，自己写了半天的算法，其实运行下来比别人两行代码（Array.sort，调用jdk内置的函数）就搞定了还慢了很多倍。 解题思路：这道题用简单暴力的解法是非常容易的，同样是先对数组进行排序，最简单的办法是用jdk内置的Array.sort进行排序，然后从后往前取第k个元素，这种解法既简单，又由于jdk内置的快排效率非常高，在leetcode上这种解法只用了4ms，排名第二。当然更聪明的解法很多，例如，使用快排（分治算法），在快排的每一趟排完后，如果要找的k较大，则只对对应的一半继续进行快排，直到找到结果。还有使用堆的办法。 class Solution { public int findKthLargest(int[] nums, int k) { Queue<Integer> queue = new PriorityQueue<Integer>(); for (int i = 0; i < nums.length; i++) { if (i < k) { queue.add(nums[i]); } else if (queue.peek() < nums[i]) { queue.remove(); queue.add(nums[i]); } } return queue.peek(); } } class Solution { public int findKthLargest(int[] nums, int k) { int left = 0, right = nums.length - 1; while (true){ int pos = partition(nums, left, right); if(k - 1 == pos) return nums[pos]; else if(pos > k - 1) right = pos - 1; else left = pos + 1; } } public int partition(int[] nums, int left, int right){ int pivot = nums[left], l = left +1, r = right; while (l <= r){ if(nums[l] < pivot && nums[r] > pivot) swap(nums, l, r); if (nums[r] <= pivot) r--; if (nums[l] >= pivot) l++; } swap(nums, left, r); return r; } public void swap(int nums[], int left, int right){ int temp = nums[left]; nums[left] = nums[right]; nums[right] = temp; } } Two Sum II（两数之和） 给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。 函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。 说明: 返回的下标值（index1 和 index2）不是从零开始的。 你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。 示例: 输入: numbers = [2, 7, 11, 15], target = 9 输出: [1,2] 解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。 解题思路：这道题同样有多种思路，暴力解法是两次遍历该数组，找到相加等于target的索引，这种解法的时间复杂度是O(n^2)。利用二分法的思想来解这道题，时间复杂度是O(nlogn)。而利用对撞指针来解这道题，时间复杂度只有O（n），以下是对撞指针的解法。 class Solution { public int[] twoSum(int[] numbers, int target) { int i = 0,j = numbers.length-1; while(i<j){ if(numbers[i]+numbers[j]==target){ break; } if(numbers[i]+numbers[j]>target){ j--; } if(numbers[i]+numbers[j]<target){ i++; } } return new int[]{++i,++j}; } } 209.Minimum Size Subarray Sum（最小子数组） 给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组，返回 0。 示例: 输入: s = 7, nums = [2,3,1,2,4,3] 输出: 2 解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。 进阶: 如果你已经完成了O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。 解题思路：该题使用滑动窗口法解决只需要O（n）的时间复杂度 public class MSSubarraySum { public int minSubArrayLen(int s, int[] nums) { int i = 0, j = -1; int sum = 0; int result = nums.length+1; while(i<nums.length){ if(j<nums.length-1&&sum<s){ sum+=nums[++j]; }else{ sum-=nums[i++]; } if(sum>=s) result = Math.min(result,j-i+1); } if(result == nums.length+1){ result = 0; } return result; } } 3.Longest Substring Without Repeating Characters（无重复字符的最小子串） 给定一个字符串，找出不含有重复字符的最长子串的长度。 示例 1: 输入: "abcabcbb" 输出: 3 解释: 无重复字符的最长子串是 "abc"，其长度为 3。 示例 2: 输入: "bbbbb" 输出: 1 解释: 无重复字符的最长子串是 "b"，其长度为 1。 示例 3: 输入: "pwwkew" 输出: 3 解释: 无重复字符的最长子串是 "wke"，其长度为 3。 请注意，答案必须是一个子串，"pwke" 是一个子序列 而不是子串。 解题思路：这道题同样是使用滑动窗口的思想去解是最佳的。该题需要记录每个字符出现的频率，因此初始化一个长度为256的freq数组，根据字符的ASCII码来每个字符出现的频率。根据频率来进行窗口的滑动。 class Solution { public int lengthOfLongestSubstring(String s) { int[] freq = new int[256]; for (int f = 0; f < freq.length; f++) { freq[f] = 0; } int i = 0, j = -1; int result = 0; while (i < s.length()) { if (j < s.length() - 1 && freq[s.charAt(j + 1)] == 0) { freq[s.charAt(++j)]++; }else{ freq[s.charAt(i++)]--; } result = Math.max(result, j - i + 1); } return result; } } Minimum Window Substring（最小覆盖子串） 给定一个字符串 S 和一个字符串 T，请在 S 中找出包含 T 所有字母的最小子串。 示例： 输入: S = "ADOBECODEBANC", T = "ABC" 输出: "BANC" 说明： 如果 S 中不存这样的子串，则返回空字符串 ""。 如果 S 中存在这样的子串，我们保证它是唯一的答案。 解题思路：这道题我依然是使用滑动窗口的思想去解的，时间复杂度为O（2st），解题耗时较长，主要原因是每次都要遍历一遍结果集去判断结果是否正确，可以去参考leetcode 该题更好的解法。 class Solution { public String minWindow(String s, String t) { HashMap<Integer,Integer> target = new HashMap<>(); for(int i =0;i<t.length();i++){ if(target.get((int)t.charAt(i))==null){ target.put((int) t.charAt(i),1); }else{ int temp = target.get((int)t.charAt(i)); target.put((int) t.charAt(i),temp+1); } } int freq[] = new int[256]; for (int i = 0; i < freq.length; i++) freq[i] = 0; int i = 0, j = -1; int length = Integer.MAX_VALUE; String result = ""; while(i<s.length()){ if(j<s.length()-1&&!hasFound(freq,target)){ freq[s.charAt(++j)]++; }else{ freq[s.charAt(i++)]--; } if(hasFound(freq,target)){ if(length>j-i+1){ length = j-i+1; result = s.substring(i,j+1); } } } return result; } public static boolean hasFound(int[] arr1,HashMap<Integer,Integer> arr2){ // for(int i =0;i<arr2.length;i++){ // if(arr1[arr2[i]]<1) // return false; // } Iterator iter = arr2.entrySet().iterator(); while(iter.hasNext()){ Map.Entry<Integer,Integer> entry = (Map.Entry) iter.next(); if(arr1[entry.getKey()]<entry.getValue()){ return false; } } return true; } } 451.Sort Characters By Frequency(根据字符出现频率排序) 示例 1: 输入: "tree" 输出: "eert" 解释: 'e'出现两次，'r'和't'都只出现一次。 因此'e'必须出现在'r'和't'之前。此外，"eetr"也是一个有效的答案。 解题思路：这里我是用HashMap来解的，不过最后用了比较笨的办法来按顺序拼凑字符串。是通过类似选择排序的办法，每次比较map里的所有value值，将最大的值拿出来放在最前面。Leetcode上有更好的方法可以借鉴。 class Solution { public String frequencySort(String s) { Map<Character,Integer> map = new HashMap<>(); for(int i =0;i<s.length();i++){ map.put(s.charAt(i),map.getOrDefault(s.charAt(i),0)+1); } StringBuffer result = new StringBuffer(); int temp = -1; char tempKey=' '; int i = 0; while(i<s.length()){ for (Map.Entry<Character,Integer> entry:map.entrySet()) { if(temp<entry.getValue()){ tempKey = entry.getKey(); temp = entry.getValue(); } } map.remove(tempKey); while(temp>0){ result.append(tempKey); i++; temp--; } } return result.toString(); } } 15.3Sum（三数之和） 给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。 注意：答案中不可以包含重复的三元组。 例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]， 满足要求的三元组集合为： [ [-1, 0, 1], [-1, -1, 2] ] 解题思路：我用的是对撞指针的方式，遍历数组的过程中，对当前遍历的索引之后的数，采用对撞指针的方式，找到和等于0-nums【i】的两个数。我的代码略有瑕疵导致速度较慢，以下为leetcode上解题思路与我相同，但是做了细节优化的代码 class Solution { public List<List<Integer>> threeSum(int[] nums) { int len=nums.length; Arrays.sort(nums); List<List<Integer>> res = new ArrayList<>(); for(int i=0;i<len;i++){ if(nums[i]>0)break; //简化，如果>0则说明该三数之和不可能为0 if(i>0&&nums[i]==nums[i-1])continue; //去重 int target=0-nums[i]; int l=i+1,r=len-1; //此处必须对i后面的数字进行筛选，不能重复 while(l<r){ List<Integer> list=new ArrayList(); if(nums[l]+nums[r]==target){ list.add(nums[i]); list.add(nums[l]); list.add(nums[r]); res.add(list); while(r>l&&nums[l+1]==nums[l])l++; //这个地方改成l-1只会出现一个结果了 while(r>l&&nums[r]==nums[r-1])r--; l++;r--; }else if(nums[l]+nums[r]>target)r--; else l++; } } return res; } } 454.4SumII（四数相加II） 给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。 为了使问题简单化，所有的 A, B, C, D 具有相同的长度 N，且 0 ≤ N ≤ 500 。所有整数的范围在 -228 到 228 - 1 之间，最终结果不会超过 231 - 1 。 例如: 输入: A = [ 1, 2] B = [-2,-1] C = [-1, 2] D = [ 0, 2] 输出: 2 解释: 两个元组如下: (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0 (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0 解题思路：暴力解法为遍历四个数组所有情况，时间复杂度为O(n^4 )。本题我使用了查找表的方法，将数组A和B的所有和的情况置入查找表中，遍历C和数组D即可得到结果，时间复杂度为O(n^2) public int fourSumCount(int[] A, int[] B, int[] C, int[] D) { int result = 0; Map<Integer,Integer> map = new HashMap<>(); for(int i = 0;i<A.length;i++){ for(int j = 0;j<B.length;j++){ map.put(A[i]+B[j],map.getOrDefault(A[i]+B[j],0)+1); } } for(int i = 0;i<C.length;i++){ for(int j = 0;j<D.length;j++){ if(map.containsKey(0-C[i]-D[j])){ result+=map.get(0-C[i]-D[j]); } } } return result; } 206. Reverse Linked List 反转链表 反转一个单链表。 示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL 进阶: 你可以迭代或递归地反转链表。你能否用两种方法解决这道题？ 解题思路：对于链表题来说，一般不能直接操作链表节点的值，而是通过操作指针来改变链表。例如，扫描一遍链表，将值压入栈中，再第二次扫描链表，将值从栈中弹出，这种方式一般在面试的算法题中是不被允许的。因此，这道题我用了三个临时指针，只改变listNode的next指针的方向来改变链表。 public class ReverseLinkedList { public ListNode reverseList(ListNode head) { if(head == null) return head; ListNode pre = null, cur = head, next = head.next; while (cur != null){ cur.next = pre; pre = cur; cur = next; if(next!=null){ next = next.next; } } return pre; } } 92. Reverse Linked List II 反转链表 II 反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。 说明: 1 ≤ m ≤ n ≤ 链表长度。 示例: 输入: 1->2->3->4->5->NULL, m = 2, n = 4 输出: 1->4->3->2->5->NULL 这道题个人感觉还是挺难的，因为要处理的特殊情况较多，又不能直接更改节点的值，而是要通过指针来实现反转链表。这里还是以leetcode上大神写的更优美的代码为例吧 public ListNode reverseBetween_1(ListNode head, int m, int n) { if (head == null || m < 1 || m > n) return null; ListNode head1 = head; ListNode preTail = null;//需要逆置节点的前驱节点 //第一步：前进至第m节点，即行走m-1步;注意考虑m为1的情况，此时preTail=null int i = 1; while(head1 != null && i++ < m){ preTail = head1; head1 = head1.next; } //第二步：反转m->n节点 if(head1 == null) return head;//head1为null，不需要后翻转了 ListNode preNode = null; ListNode reverseListPreHead = head1; ListNode nextNode; while (head1 != null && m++ <= n) { nextNode = head1.next; head1.next = preNode; preNode = head1; head1 = nextNode; } //第三步：反转链表的头尾处理 reverseListPreHead.next = head1;//处理尾巴 if (preTail != null) {//处理头部 preTail.next = preNode; return head; }else{ return preNode;//若preTail为null,返回翻转链表段的最后一个节点 } } Remove Duplicates from Sorted List 删除排序链表中的重复元素 给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。 示例 1: 输入: 1->1->2 输出: 1->2 示例 2: 输入: 1->1->2->3->3 输出: 1->2->3 解题思路：这道题题意我理解错了，不知道是不是题目表达的问题，让我误以为要删除所有的不管是否相邻的具有重复值的节点。但看了leetcode上其他人的代码，都只是删除相邻的重复的节点。 if(head ==null) return null; if(head.next == null) return head; Set<Integer> set = new HashSet<>(); ListNode temp = new ListNode(-1); temp.next = head; while (temp!=null&&temp.next!=null){ ListNode next = temp.next; if(set.contains(next.val)) temp.next = temp.next.next; else{ set.add(next.val); temp = temp.next; } } return head; 86.Partition List 分隔链表 给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。 你应当保留两个分区中每个节点的初始相对位置。 示例: 输入: head = 1->4->3->2->5->2, x = 3 输出: 1->2->2->4->3->5 解题思路：感觉链表的题都好难啊……但是看了别人的解法有感觉很简单，这道题的思路就是把小的和大的分别依次链起来，最后整合。 public ListNode partition(ListNode head, int x){ ListNode head1 = new ListNode(0); ListNode head2 = new ListNode(0); ListNode phead1 = head1; ListNode phead2 = head2; ListNode temp = head; while (temp!=null){ if(temp.val<x){ phead1.next = temp; temp = temp.next; phead1 = phead1.next; phead1.next = null; }else{ phead2.next = temp; temp = temp.next; phead2 = phead2.next; phead2.next = null; } } phead1.next = head2.next; head = head1.next; return head; } 328. Odd Even Linked List 奇偶链表 给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。 请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。 示例 1: 输入: 1->2->3->4->5->NULL 输出: 1->3->5->2->4->NULL 示例 2: 输入: 2->1->3->5->6->4->7->NULL 输出: 2->3->6->7->1->5->4->NULL 说明: 应当保持奇数节点和偶数节点的相对顺序。 链表的第一个节点视为奇数节点，第二个节点视为偶数节点，以此类推。 解题思路：这道题和上一道题的解题思路基本一致。将奇偶数节点分别链起来，最后再整合即可。需要注意的是需要记录奇偶节点的首节点的位置，方便整合。 public ListNode oddEvenList(ListNode head) { ListNode temp = head; ListNode evenNode = new ListNode(-1); ListNode oddNode = new ListNode(-1); ListNode pEvenNode = evenNode; ListNode pfirOddNode = oddNode; int i = 1; while (temp != null){ if(i%2==0){ evenNode.next = temp; evenNode = evenNode.next; temp = temp.next; evenNode.next = null; }else { oddNode.next = temp; oddNode = oddNode.next; temp = temp.next; oddNode.next = null; } i++; } oddNode.next = pEvenNode.next; head = pfirOddNode.next; return head; } 2.Add Two Numbers 两数相加 给定两个非空链表来表示两个非负整数。位数按照逆序方式存储，它们的每个节点只存储单个数字。将两数相加返回一个新的链表。 你可以假设除了数字 0 之外，这两个数字都不会以零开头。 示例： 输入：(2 -> 4 -> 3) + (5 -> 6 -> 4) 输出：7 -> 0 -> 8 原因：342 + 465 = 807 解题思路：不得不说看别人的代码都赏心悦目，相比之下自己的代码不知道是哪个弱智写的。这道题同样不难，两两相加，遇到某个数字位数不够了补0就可以了。这里还是以leetcode上大佬写的代码为例 public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode next = new ListNode(0); ListNode result = next; int add = 0; while (l1 != null || l2 != null) { int l1val = (l1 != null) ? l1.val : 0; int l2val = (l2 != null) ? l2.val : 0; int value = l1val + l2val + add; add = value / 10; next.next = new ListNode(value % 10); next = next.next; l1 = (l1 != null) ? l1.next : null; l2 = (l2 != null) ? l2.next : null; } if (add > 0) { next.next = new ListNode(add); } return result.next; } 203. Remove Linked List Elements 移除链表元素 删除链表中等于给定值 val 的所有节点。 示例: 输入: 1->2->6->3->4->5->6, val = 6 输出: 1->2->3->4->5 解题思路： 利用虚拟头结点，删除所有重复元素即可。我的代码有些小瑕疵，应该释放删除掉节点的内存空间。 public ListNode removeElements(ListNode head, int val) { ListNode dummyNode = new ListNode(0); dummyNode.next = head; ListNode cur = dummyNode; while (cur.next!=null){ if(cur.next.val==val) cur.next = cur.next.next; else cur = cur.next; } return dummyNode.next; } 82. Remove Duplicates from Sorted List II 删除排序链表中的重复元素 II 给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。 示例 1: 输入: 1->2->3->3->4->4->5 输出: 1->2->5 示例 2: 输入: 1->1->1->2->3 输出: 2->3 解题思路：总感觉链表题都挺有难度的，可能是平常用的少的原因吧。这道题其实思路也很简单，就是遇到相同节点，就循环往下找下一个不同的节点，并链接。 public ListNode deleteDuplicates(ListNode head) { ListNode dummyHead = new ListNode(0); dummyHead.next = head; ListNode prev = dummyHead; while (prev.next != null) { ListNode cur = prev.next; if (cur.next == null || cur.val != cur.next.val) { prev = prev.next; continue; } while (cur.next != null && cur.next.val == cur.val) { cur.next = cur.next.next; } prev.next = cur.next; } return dummyHead.next; }
