文章 217
评论 6
浏览 143928
String - 344. Reverse String

String - 344. Reverse String

344. Reverse String Write a function that reverses a string. The input string is given as an array of characters char[]. Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory. You may assume all the characters consist of printable ascii characters. Example 1: Input: [“h”,“e”,“l”,“l”,“o”] Output: [“o”,“l”,“l”,“e”,“h”] 思路: two pointers 代码: java: class Solution { public void reverseString(char[]....

String - 383. Ransom Note

String - 383. Ransom Note

383. Ransom Note Given an arbitrary ransom note string and another string containing letters from all the magazines, write a function that will return true if the ransom note can be constructed from the magazines ; otherwise, it will return false. Each letter in the magazine string can only be used once in your ransom note. Note: You may assume that both strings contain only lowercase letters. canConstruct(“a”, “b”) -> false canConstruct(“aa”, “ab”) -> false canConstruct(“aa”, “aab”)....

String - 58. Length of Last Word

String - 58. Length of Last Word

58. Length of Last Word Given a string, find the first non-repeating character in it and return it’s index. If it doesn’t exist, return -1. Examples: s = “leetcode” return 0. s = “loveleetcode”, return 2. Note: You may assume the string contain only lowercase letters. 思路: 找出第一个不重复出现的字母,这题最容易想到的是用一个map记录下每个字母出现的次数,然后根据map去寻找只出现一次的字母的索引。这样做的时间消耗太多,采用另一种思路:题目中的字母默认只会有小写字母,那就可以以a - z来遍历字符串,如果第一次出现的索引下标和最后一次相同,就是结果,然后记录这其中下标最小的。 代码: java: class Solution { /*public int firstUniqChar(Stri....

String - 14. Longest Common Prefix

String - 14. Longest Common Prefix

14. Longest Common Prefix Write a function to find the longest common prefix string amongst an array of strings. If there is no common prefix, return an empty string "". Example 1: Input: [“flower”,“flow”,“flight”] Output: “fl” Example 2: Input: [“dog”,“racecar”,“car”] Output: "" Explanation: There is no common prefix among the input strings. Note: All given inputs are in lowercase letters a-z. 思路: leetcode 一共有四种解法,这里就只写第一种,就是以一个string为标准,不断的调用api接口判断子串是否在字符串开头(注意,这一题只用判断从索引为....

String - 28. Implement strStr()

String - 28. Implement strStr()

28. Implement strStr() Implement strStr(). Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack. Example 1: Input: haystack = “hello”, needle = “ll” Output: 2 Example 2: Input: haystack = “aaaaa”, needle = “bba” Output: -1 Clarification: What should we return when needle is an empty string? This is a great question to ask during an interview. For the purpose of this problem, we will return 0 when needle&nbs....

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

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