2023/10/11 LeetCode LeetCode P215数组中第K个最大元素 描述： 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。/** * P215数组中第k个最大元素(堆排序的做法) * @param nums * @param k * @return * 思路：堆排序只需要从堆顶取k-1个元素即是第k个最大元素值 */ public int findKthLargest(int[] nums, int k) { //构建堆，从最后一个没有叶子结点的开始 for (int i=nums.length/2-1;i>=0;i--) { maxHeapify(nums,nums.length,i); } System.out.println(Arrays.toString(nums)); for (int i=nums.length-1; i >= nums.length - k + 1;i--) { swap(nums,0,i); //将最大值放入数组最后 maxHeapify(nums,i,0); //删除最后一个节点重建堆 } return nums[0]; } /** * * @param nums 数组 * @param n 数组个数 * @param i 当前堆顶元素下标 */ public void maxHeapify(int[] nums,int n,int i) { int largeMax = i; int left = i*2+1; int right = i*2+2; if (left<n&&nums[left]>nums[largeMax]) { largeMax = left; } if (right<n&&nums[right]>nums[largeMax]) { largeMax = right; } if (largeMax!=i) { swap(nums,i,largeMax); //将最大值放入堆顶 maxHeapify(nums,n,largeMax); //重建堆 } } /** * 数组交换 * @param num * @param l * @param r */ public void swap(int[] num,int l,int r) { int temp = num[l]; num[l] = num[r]; num[r] = temp; }

2023/10/10 LeetCode LeetCode p11 盛最多水的容器描述： 给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i])。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。思路 :既然是要求当前可以存储的最大水量，那么按照常规思路，只需要定义两个指针指向首尾作为容器的边界，我们每次将最小的值的指针向另一指针移动，记录每次移动的容器中的大小值，即可找到最大的容器盛水量。代码 ： /** * P11盛最多水的容器 * @param height * @return */ public int maxArea(int[] height) { int result = 0; int heightMax = 0; for (int i=0,j=height.length-1;i<j;) { heightMax = Math.min(height[i], height[j]); //取最小的高度 int curMax = (j-i)*heightMax; //求当前面积 System.out.println("i="+i+",j="+j+",cur="+curMax); result = Math.max(result,curMax); if (height[i]>height[j]) { j--; } else { i++; } } return result; }LeetCode P160 相交链表 描述 ：给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null。思路： 按照题目所需要找到两个链表的交点，那么我们思考一下如果存在交点，那么这个交点后面的节点必是相同节点，既然如此，我们直接将短的一个链表与长链表进行一个右对齐，然后遍历连个链表，只要存在节点相等，即可说明该节点是两个节点的交点，如果链表遍历完成都未找到相等节点，即说明不存在交点，直接返回null值即可。 代码：/** * P160 相交链表 * @param headA * @param headB * @return */ public ListNode getIntersectionNode(ListNode headA, ListNode headB) { ListNode a = headA; ListNode b = headB; int aLength = 0; int bLength = 0; // 判断哪个链表比较长 while (a!=null) { aLength++; a = a.next; } while (b!=null){ bLength++; b = b.next; } ListNode longList; ListNode shortList; int sub; if (aLength>bLength){ longList = headA; shortList = headB; sub = aLength-bLength; } else { longList = headB; shortList = headA; sub = bLength - aLength; } //移动长链表与短链表进行对齐 while (sub>0) { longList = longList.next; sub--; } while (longList!=null) { if (longList==shortList) return longList; longList = longList.next; shortList = shortList.next; } return null; }

2023/10/4 LeetCode LeetCode P128最长连续序列描述：给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。请你设计并实现时间复杂度为 O(n) 的算法解决此问题。解题思路：因为时间复杂度为O(n)，所以不能够先排序在进行for遍历，所以考虑使用Hash集合，因为查询的时间复杂度为O(1)，我们直接利用HashSet进行去重，外层循环需要 O(n) 的时间复杂度，同时为了防止不必要的遍历，只有当一个数是连续序列的第一个数的情况下才会进入内层循环，然后在内层循环中匹配连续序列中的数，因此数组中的每个数只会进入内层循环一次。根据上述分析可知，总时间复杂度为 O(n)。详细代码如下： /** * P128最长连续序列 * @param nums * @return */ public int longestConsecutive(int[] nums) { //去重 HashSet<Integer> hashSet = new HashSet<>(); for (int num : nums) { hashSet.add(num); } int result = 0; for (Integer num : hashSet) { if (!hashSet.contains(num-1)) { int max = 1; int currentNum = num; while (hashSet.contains(currentNum+1)) { max++; currentNum++; } result = Math.max(result,max); } } return result; }