文章 217
评论 6
浏览 143919
Array - 75. Sort Colors

Array - 75. Sort Colors

Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue.

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 - 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 - 56. Merge Intervals

Array - 56. Merge Intervals

Given a collection of intervals, merge all overlapping intervals.

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 - 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)....

Array - 334. Increasing Triplet Subsequence

Array - 334. Increasing Triplet Subsequence

334. Increasing Triplet Subsequence Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array. Formally the function should: Return true if there exists _i, j, k _ such that arr[i] < arr[j] < arr[k] given 0 ≤ i < j < k ≤ n-1 else return false. **Note: **Your algorithm should run in O(n) time complexity and O(1) space complexity. Example 1: Input: [1,2,....

Array - 42. Trapping Rain Water Hard

Array - 42. Trapping Rain Water Hard

42. Trapping Rain Water Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining. The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image! Example: Input: [0,1,0,2,1,0,1,3,2,1,2,1] Output: 6 思路: 题目意思是给定一个数组,数值代表了高度,求解可以装多少水,仔细分析可以发现,对于任意一位能存储多少水是取....

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 - 309. Best Time to Buy and Sell Stock with Cooldown

Array - 309. Best Time to Buy and Sell Stock with Cooldown

Design an algorithm to find the maximum profit.

Array - 188. Best Time to Buy and Sell Stock IV

Array - 188. Best Time to Buy and Sell Stock IV

188. Best Time to Buy and Sell Stock IV Say you have an array for which the _i_th element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete at most k transactions. Note: You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again). Example 1: Input: [2,4,1], k = 2 Output: 2 Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2. ....

Array - 123. Best Time to Buy and Sell Stock III

Array - 123. Best Time to Buy and Sell Stock III

123. Best Time to Buy and Sell Stock III Say you have an array for which the _i_th element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete at most two transactions. **Note: **You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again). Example 1: Input: [3,3,5,0,0,3,1,4] Output: 6 Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), pr....

Array - 122. Best Time to Buy and Sell Stock II

Array - 122. Best Time to Buy and Sell Stock II

122. Best Time to Buy and Sell Stock II Say you have an array for which the _i_th element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times). Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again). Example 1: Input: [7,1,5,3,6,4] Output: 7 Explanation: Buy on....

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