文章 212
评论 0
浏览 119900
Array - 508. Wiggle Sort

Array - 508. Wiggle Sort

508. Wiggle Sort Given an unsorted array nums, reorder it in-place such that nums[0] <= nums[1] >= nums[2] <= nums[3].... Example Example 1: Input: [3, 5, 2, 1, 6, 4] Output: [1, 6, 2, 5, 3, 4] Explanation: This question may have multiple answers, and [2, 6, 1, 5, 3, 4] is also ok. Example 2: Input: [1, 2, 3, 4] Output: [2, 1, 4, 3] Notice Please complete the problem in-place. 思路: 仔细分析输出数组,可以发现下标索引为奇数的数是极大值点,下标索引是偶数的是极小值点,只要遍历数组的时候,移动相邻两个数,就可以。 代码: java: public c....

Array - 376. Wiggle Subsequence

Array - 376. Wiggle Subsequence

376. Wiggle Subsequence A sequence of numbers is called a wiggle sequence if the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with fewer than two elements is trivially a wiggle sequence. For example, [1,7,4,9,2,5] is a wiggle sequence because the differences (6,-3,5,-7,3) are alternately positive and negative. In contrast, [1,4,7,....

Array - 4. Median of Two Sorted Arrays

Array - 4. Median of Two Sorted Arrays

4. Median of Two Sorted Arrays There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)). You may assume nums1 and nums2 cannot be both empty. Example 1: nums1 = [1, 3] nums2 = [2] The median is 2.0 思路: 最优解是O(min(m, n)),采用二分的思想,来找到两个有序数组的中间切分位置。 代码: java: class Solution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { i....

Array - 283. Move Zeroes

Array - 283. Move Zeroes

283. Move Zeroes Given an array nums, write a function to move all 0’s to the end of it while maintaining the relative order of the non-zero elements. Example: Input: [0,1,0,3,12] Output: [1,3,12,0,0] Note: You must do this in-place without making a copy of the array. Minimize the total number of operations. 思路: 把零放到数组最后,使用two points做,就是使用一个指针记录0和非零的数的分界线,另一个指针去寻找非零的数来和这个分界线的数进行交换。 代码: java: class Solution { public void moveZeroes(int[] nums) { if (nums == null || ....

Array - 88. Merge Sorted Array

Array - 88. Merge Sorted Array

88. Merge Sorted Array Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array. Note: The number of elements initialized in nums1 and nums2 are m and n respectively. You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. Example: Input: nums1 = [1,2,3,0,0,0], m = 3 nums2 = [2,5,6],....

Array - 228. Summary Ranges

Array - 228. Summary Ranges

Summary Ranges Given a sorted integer array without duplicates, return the summary of its ranges. Example 1: Input: [0,1,2,4,5,7] Output: [“0->2”,“4->5”,“7”] Explanation: 0,1,2 form a continuous range; 4,5 form a continuous range. Example 2: Input: [0,2,3,4,6,8,9] Output: [“0”,“2->4”,“6”,“8->9”] Explanation: 2,3,4 form a continuous range; 8,9 form a continuous range. 思路: 把一个数组连续的字串变成0->3,单独的间断点就没有->这样一个字符串有序表。思路就是遍历数组,记录数组连续的开始点(间断点的下一位)。然后判断间断点加入链表就可以。 代码: jav....

Array - 152. Maximum Product Subarray

Array - 152. Maximum Product Subarray

152. Maximum Product Subarray Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product. Example 1: Input: [2,3,-2,4] Output: 6 Explanation: [2,3] has the largest product 6. Example 2: Input: [-2,0,-1] Output: 0 Explanation: The result cannot be 2, because [-2,-1] is not a subarray. 思路: 这一题是让找出一个字串的乘积最大,因为负数乘负数就是正数,所以在遍历数组找乘积最大的时候同时找一个最大的正数和一个最小的负数,同时记录过程中最大的数,就是结果。 代码: class Solution { publi....

Array - 238. Product of Array Except Self

Array - 238. Product of Array Except Self

238. Product of Array Except Self Given an array nums of n integers where n > 1,  return an array output such that output[i] is equal to the product of all the elements of numsexcept nums[i]. Example: Input: [1,2,3,4] Output: [24,12,8,6] Note: Please solve it without division and in O(n). Follow up: Could you solve it with constant space complexity? (The output array does not count as extra space for t....

Array - 209. Minimum Size Subarray Sum

Array - 209. Minimum Size Subarray Sum

209. Minimum Size Subarray Sum Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn’t one, return 0 instead. **Example: ** Input: s = 7, nums = [2,3,1,2,4,3] Output: 2 Explanation: the subarray [4,3] has the minimal length under the problem constraint. Follow up: If you have figured out the O(n) solution, try coding another solution of which the time compl....

Array - 53. Maximum Subarray

Array - 53. Maximum Subarray

53. Maximum Subarray Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum. Example: Input: [-2,1,-3,4,-1,2,1,-5,4], Output: 6 Explanation: [4,-1,2,1] has the largest sum = 6. Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle. 思路: 找出数组中最大字串和,使用动态规划求解,转移方程是:f[i] = f[i-1] > 0 ? nums[i] + f[i-1] : nums....

Array - 295. Find Median from Data Stream

Array - 295. Find Median from Data Stream

295. Find Median from Data Stream Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value. For example, [2,3,4], the median is 3 [2,3], the median is (2 + 3) / 2 = 2.5 Design a data structure that supports the following two operations: void addNum(int num) - Add a integer number from the data stream to the data structure. double findMedian() - Return the median of all eleme....

Array - 11. Container With Most Water

Array - 11. Container With Most Water

11. Container With Most Water Given n non-negative integers a1, a2, …, _an _, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water. **Note: **You may not slant the container and n is at least 2. Example: Input: [1,8,6,....

Array - 45. Jump Game II

Array - 45. Jump Game II

45、Jump Game II Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Your goal is to reach the last index in the minimum number of jumps. Example: Input: [2,3,1,1,4] Output: 2 Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index. Note: You can assume that you can always reach the last in....

Array - 41. First Missing Positive

Array - 41. First Missing Positive

41、First Missing Positive Given an unsorted integer array, find the smallest missing positive integer. Example 1: Input: [1,2,0] Output: 3 Example 2: Input: [3,4,-1,1] Output: 2 Example 3: Input: [7,8,9,11,12] Output: 1 Note: Your algorithm should run in O(n) time and uses constant extra space. 思路: 寻找消失的正数,使用桶排序的思想,对数组排完序之后,比对对应位置与位置上的值,就能找出结果。 代码: java: class Solution { public int firstMissingPositive(int[] nums) { if (nums == null || nums.length <= 0) return 1; // 1. sort fo....

Array - 27. Remove Element

Array - 27. Remove Element

27、 Remove Element 相似题型:83(list), 26,80 Given an array nums and a value val, remove all instances of that value in-place and return the new length. Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory. The order of elements can be changed. It doesn’t matter what you leave beyond the new length. Example 1: Given _nums_ = [3,2,2,3], _val_ = 3, Your function should return length = 2, with....

Array - 26. Remove Duplicates from Sorted Array

Array - 26. Remove Duplicates from Sorted Array

26、Remove Duplicates from Sorted Array 相似题型:83(list), 26,80 Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length. Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory. Example 1: Given nums = [1,1,2], Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn't m....

关于leetcode刷题顺序和刷题思路的声明

关于leetcode刷题顺序和刷题思路的声明

1. 刷题顺序:我leetcode的刷题顺序是根据刷题3000题的Edward老师在Youtube上的视频推荐的400题基础来刷的。 该老师有自己的网站和全程课(因为YouTube上老师只开放了50题,后面的要付费),网址:https://cspiration.com 。如果有需要购买全程课的同学可以去加老师他的微信去买全程课。 2. 代码及思路:因为Edward老师的视频在YouTube上只开放了前50,我又没买课,所以后面的有些题目思路还参考学习了花花酱老师和花嫂的视频。还有就是参考国内的博客和leetcode的Discuss。 花花酱老师的YouTube:https://www.youtube.com/user/xxfflower Edward老师的YouTube:https://www.youtube.com/channel/UCTWuRL33U8xBPqk3LehXjFw

Array - 239. Sliding Window Maximum

Array - 239. Sliding Window Maximum

239. Sliding Window Maximum Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the _k_numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window. Example: Input: nums = [1,3,-1,-3,5,3,6,7], and k = 3 Output: [3,3,5,5,6,7] Explanation: Window position Max [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 ** 5** 1 3 -....

Array - 164. Maximum Gap

Array - 164. Maximum Gap

164. Maximum Gap Given an unsorted array, find the maximum difference between the successive elements in its sorted form. Return 0 if the array contains less than 2 elements. Example 1: Input: [3,6,9,1] Output: 3 Explanation: The sorted form of the array is [1,3,6,9], either   (3,6) or (6,9) has the maximum difference 3. Example 2: Input: [10] Output: 0 Explanation: The array contains less than 2 elements, therefore return 0. Note: You may assume all elements in the array are non-....

Array - 128. Longest Consecutive Sequence

Array - 128. Longest Consecutive Sequence

128. Longest Consecutive Sequence Given an unsorted array of integers, find the length of the longest consecutive elements sequence. Your algorithm should run in O(n) complexity. Example: Input: [100, 4, 200, 1, 3, 2] Output: 4 Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4. 思路: 题目提示必须跑在O(n),可以使用set或者map来做,就是online和offline,offline非常简单直接,就是利用set的O(1)操作来解。 代码: java: class Solution { // online public int longestConsecutive(int[] nums)....

Nothing just happens, it's all part of a plan.