LeetCode - topics: Array (Part I)

1. Two Sum

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:

1
2
3

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

1 2	Input: nums = [3,2,4], target = 6 Output: [1,2]

Constraints:

2 <= nums.length <= 103
-109 <= nums[i] <= 109
-109 <= target <= 109
Only one valid answer exists.

Solution:

func twoSum(nums []int, target int) []int {
	mInt := make(map[int]int)
	for i := 0; i < len(nums); i++ {
		another := target - nums[i]
		if _, ok := mInt[another]; ok {
			return []int{mInt[another], i}
		}
		mInt[nums[i]] = i
	}
	return nil
}

Note:

牺牲空间换时间

2. Median of Two Sorted Arrays

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:

1
2
3

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

1 2	Input: nums = [3,2,4], target = 6 Output: [1,2]

Constraints:

2 <= nums.length <= 103
-109 <= nums[i] <= 109
-109 <= target <= 109
Only one valid answer exists.

Solution:

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
	if len(nums1) > len(nums2) {
		return findMedianSortedArrays(nums2, nums1)
	}
    low, high, middleMerg, midNum1, midNum2 := 0, len(nums1), (len(nums1)+len(nums2)+1)>>1, 0, 0
	for low <= high {
		midNum1 = low + (high-low)>>1
		midNum2 = middleMerg - midNum1
		if midNum1 > 0 && nums1[midNum1-1] > nums2[midNum2] {
			high = midNum1 - 1
		} else if midNum1 < len(nums1) && nums1[midNum1] < nums2[midNum2-1] {
			low = midNum1 + 1
		} else {
			break
		}
	}
	midL, midR := 0, 0
	if midNum2 == 0 {
		midL = nums1[midNum1-1]
	} else if midNum1 == 0 {
		midL = nums2[midNum2-1]
	} else {
		midL = max(nums1[midNum1-1], nums2[midNum2-1])
	}
	if (len(nums2)+len(nums1))&1 == 1 {
		return float64(midL)
	}
	if midNum1 == len(nums1) {
		midR = nums2[midNum2]
	} else if midNum2 == len(nums2) {
		midR = nums1[midNum1]
	} else {
		midR = min(nums1[midNum1], nums2[midNum2])
	}
	return float64(midR+midL) / 2
}
func min(i int, i2 int) int {
	if i < i2 {
		return i
	} else {
		return i2
	}
}

func max(i int, i2 int) int {
	if i > i2 {
		return i
	} else {
		return i2
	}
}

Note:

0004. Median of Two Sorted Arrays | LeetCode Cookbook

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 the line i is at (i, ai) and (i, 0). Find two lines, which, together with the x-axis forms a container, such that the container contains the most water.

Notice that you may not slant the container.

Example 1:

1
2
3

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

Example 2:

1 2	Input: height = [1,1] Output: 1

Constraints:

n = height.length
2 <= n <= 3 * 104
0 <= height[i] <= 3 * 104

Solution:

func maxArea(height []int) int {
	start := 0
	end := len(height) - 1
	tempMax := 0
	h := 0
	w := 0
	for start <= end {
		w = end - start
		if height[start] > height[end] {
			h = height[end]
			end--

		} else {
			h = height[start]
			start++
		}
		if h*w > tempMax {
			tempMax = h * w
		}
	}
	return tempMax
}

Note:

对撞指针，注意和连续面积的题目做区分。

15. 3Sum

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Notice that the solution set must not contain duplicate triplets.

Example 1:

1 2	Input: nums = [-1,0,1,2,-1,-4] Output: [[-1,-1,2],[-1,0,1]]

Example 2:

1 2	Input: nums = [] Output: []

Example 3:

1 2	Input: nums = [0] Output: []

Constraints:

0 <= nums.length <= 3000
-105 <= nums[i] <= 105

Solution:

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        res = []
        nums.sort()
        
        for i, a in enumerate(nums):
            if i > 0 and a == nums[i - 1]:
                continue
            
            l, r = i + 1, len(nums) - 1
            while l < r:
                threeSum = a + nums[l] + nums[r]
                if threeSum > 0:
                    r -= 1
                elif threeSum < 0:
                    l += 1
                else:
                    res.append([a, nums[l], nums[r]])
                    l += 1
                    while nums[l] == nums[l - 1] and l < r:
                        l += 1
        return res

Note:

先排序，方便移动左右’指针’,注意对排序后的数组进行剪枝;对结果重复项要注意

16. 3Sum Closest

Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

Example 1:

1
2
3

Input: nums = [-1,2,1,-4], target = 1
Output: 2
Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Constraints:

3 <= nums.length <= 10^3
-10^3 <= nums[i] <= 10^3
-10^4 <= target <= 10^4

Solution:

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums.sort()
        diff = 1<<31
        for i, a in enumerate(nums):
            l, r = i + 1, len(nums) - 1
            while l < r:
                threeSum = a + nums[l] + nums[r]
                if abs(target - threeSum) < abs(diff):
                    diff = target - threeSum
                if diff == 0:
                    return target
                if threeSum > target:
                    r -= 1
                else:
                    l += 1
        return target - diff

Note:

[3Sum](#15. 3Sum)的兄弟题，判断离target最近的一个组合，先排序，然后进行三数加和，通过加和结果与target的大小比较，移动指针（排序的意义)

18. 4Sum

Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Notice that the solution set must not contain duplicate quadruplets.

Example 1:

1 2	Input: nums = [1,0,-1,0,-2,2], target = 0 Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

Example 2:

1 2	Input: nums = [], target = 0 Output: []

Constraints:

0 <= nums.length <= 200
-109 <= nums[i] <= 109
-109 <= target <= 109

Solution:

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        twoSumDict = {}
        result = []
        mark = []

        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                n1 = nums[i]
                n2 = nums[j]
                others = twoSumDict.get(target - n1 - n2)

                if others is not None:
                    for item in others:
                        n3, n4, i3, i4 = item
                        if len(set([i, j, i3, i4])) == 4:
                            res = [n1, n2, n3, n4]
                            res.sort()

                            if res not in mark:
                                result.append(res)
                                mark.append(res)

                if n1 + n2 not in twoSumDict:
                    twoSumDict[n1 + n2] = [(n1, n2, i, j)]
                else:
                    twoSumDict[n1 + n2].append((n1, n2, i, j))

        return result

Note:

[Two Sum](#1. Two Sum)的扩展，原来是一个和一个相对应，现在两两一组去进行判断，注意返回结果对重复值的剔除，对判断细节要注意。

26. Remove Duplicates from Sorted Array

Given a sorted array nums, remove the duplicates in-place such that each element appears only once and returns 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:

1
2
3

Input: nums = [1,1,2]
Output: 2, nums = [1,2]
Explanation: Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn't matter what you leave beyond the returned length.

Example 2:

1
2
3

Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4]
Explanation: Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively. It doesn't matter what values are set beyond the returned length.

Constraints:

0 <= nums.length <= 3 * 104
-104 <= nums[i] <= 104
nums is sorted in ascending order.

Solution:

//一般解法可能是直接set,remove啥的
func removeDuplicates(nums []int) int {
	if len(nums) == 0 {
		return 0
	}
	point := 0
	for i := 1; i < len(nums); i++ {
		if nums[i] != nums[i-1] {
			point++
			nums[point] = nums[i]
		}
	}
	return point + 1
}

Note:

不要直接用builtin函数，注意It doesn't matter what values are set beyond the returned length.,就可以用以上的解法，只要找到所有的不重复数字，然后一个一个覆盖填充，剩下的部分无需理会。

27. Remove Element

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:

Input: nums = [3,2,2,3], val = 3
Output: 2, nums = [2,2]
Explanation: Your function should return length = 2, with the first two elements of nums being 2.
It doesn't matter what you leave beyond the returned length. For example if you return 2 with nums = [2,2,3,3] or nums = [2,3,0,0], your answer will be accepted.

Constraints:

0 <= nums.length <= 100
0 <= nums[i] <= 50
0 <= val <= 100

Solution:

func removeElement(nums []int, val int) int {
	sort.Ints(nums)
	start := 0
	end := 0
	for i := 0; i < len(nums); i++ {
		if nums[i] == val {
			start = i
			i++
			for i < len(nums) && nums[i] == val {
				i++
			}
			end = i
			break
		}
	}
    time.Sleep(3)

	len := len(nums) - (end - start)
	nums = append(nums[:start], nums[end:]...)

	return len
}

Note:

………看不到用什么好方法，直接剔除重复部分，再把重复部分的两边粘起来:pensive:

33. Search in Rotated Sorted Array

You are given an integer array nums sorted in ascending order, and an integer target.

Suppose that nums is rotated at some pivot unknown to you beforehand (i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

If target is found in the array return its index, otherwise, return -1.

Example 1:

1 2	Input: nums = [4,5,6,7,0,1,2], target = 0 Output: 4

Example 2:

1 2	Input: nums = [4,5,6,7,0,1,2], target = 3 Output: -1

Example 3:

1 2	Input: nums = [1], target = 0 Output: -1

Constraints:

1 <= nums.length <= 5000
-10^4 <= nums[i] <= 10^4
All values of nums are unique.
nums is guranteed to be rotated at some pivot.
-10^4 <= target <= 10^4

Solution:

func search(nums []int, target int) int {
	if len(nums) == 0 {
		return -1
	}
	left := 0
	right := len(nums) - 1
	for left <= right {
		mid := (right + left) >> 1

		if nums[mid] == target {
			return mid
		}
		if nums[mid] >= nums[left] { //left is sorted
			if target > nums[mid] || target < nums[left] {
				left = mid + 1
			} else {
				right = mid - 1
			}
		} else { //right is sorted
			if target < nums[mid] || target > nums[right] {
				right = mid - 1
			} else {
				left = mid + 1
			}
		}
	}
	return -1
}

Note:

由于数组无论怎么打乱也是有序的，所以需要判断当前中点是否可能出在一个有序的半边，判断出哪个半边有序，随后再用target对其进行判断，再决定左右指针的移动。

34. Find First and Last Position of Element in Sorted Array

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

Follow up: Could you write an algorithm with O(log n) runtime complexity?

Example 1:

1 2	Input: nums = [5,7,7,8,8,10], target = 8 Output: [3,4]

Example 2:

1 2	Input: nums = [5,7,7,8,8,10], target = 6 Output: [-1,-1]

Example 3:

1 2	Input: nums = [], target = 0 Output: [-1,-1

Constraints:

0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums is a non-decreasing array.
-109 <= target <= 109

Solution:

func searchRange(nums []int, target int) []int {
	if len(nums) == 0 {
		return []int{-1, -1}
	}
	left := 0
	right := len(nums) - 1
	mid := (left + right) >> 1
	start := -1
	end := -1
	for left <= right {
		mid = (left + right) >> 1
		if nums[mid] == target {
			start = mid
			end = mid
			for start >= 1 && nums[start-1] == target {
				start--
			}
			for end < len(nums)-1 && nums[end+1] == target {
				end++
			}
			return []int{start, end}
		} else if nums[mid] > target {
			right = mid - 1
		} else {
			left = mid + 1
		}
	}
	return []int{start, end}
}

Note:

没有什么有趣的方法，采用binary search进行搜索，只要一找到目标值，就以当前坐标为起点，利用左右指针开始移动，探求出左右边界值，得出结果

35. Search Insert Position

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

Example 1:

1 2	Input: nums = [1,3,5,6], target = 5 Output: 2

Example 2:

1 2	Input: nums = [1,3,5,6], target = 0 Output: 0

Example 3:

1 2	Input: nums = [1], target = 0 Output: 0

Constraints:

1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums contains distinct values sorted in ascending order.
-104 <= target <= 104

Solution:

func searchInsert(nums []int, target int) int {
	if len(nums) == 0 {
		return 0
	}
	l, r := 0, len(nums)-1
	mid := (l + r) >> 1
	for l <= r {
		mid = (l + r) >> 1
		if nums[mid] == target {
			return mid
		}
		if nums[mid] < target {
			l = mid + 1
		} else {
			r = mid - 1
		}
	}
	if nums[mid] < target {
		return mid + 1
	}
	return mid
}

Note:

采用binary search进行搜索，找到就返回，没找到判断一下插入位置

39. Combination Sum

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

It is guaranteed that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

Example 1:

1 2	Input: candidates = [2,3,5], target = 8 Output: [[2,2,2,2],[2,3,3],[3,5]]

Solution:

func combinationSum(candidates []int, target int) [][]int {
	//var res [][]int
	res := make([][]int, 0)
	comb := make([]int, 0)
	if len(candidates) == 0 {
		return res
	}
	backTrace(candidates, 0, target, 0, comb, &res)
	return res
}

func backTrace(candidates []int, startIndex int, target int, count int, comb []int, res *[][]int) {
	if count == target { // each candidate > 1, omitting the situation of 0
		temp := make([]int, len(comb))
		copy(temp, comb)
		*res = append(*res, temp)
	}
	for i := startIndex; i < len(candidates) && count < target; i++ {
		count += candidates[i]
		comb = append(comb, candidates[i])
		backTrace(candidates, i, target, count, comb, res)
		count -= candidates[i]
		comb = comb[:len(comb)-1]
	}
}

Note:

back-tracing方法，一件件拿，一件件放回，一开始觉得像是完全背包，后来又觉得不太对劲。另外注意golang里的append和传参指针操作

40. Combination Sum II

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target.

Each number in candidates may only be used once in the combination.

Note: The solution set must not contain duplicate combinations.

Example 1:

Input: candidates = [2,5,2,1,2], target = 5
Output: 
[
[1,2,2],
[5]
]

Solution:

func combinationSum2(candidates []int, target int) [][]int {
	//var res [][]int
	sort.Ints(candidates)
	res := make([][]int, 0)
	comb := make([]int, 0)
	if len(candidates) == 0 {
		return res
	}
	backTrace(candidates, 0, target, 0, comb, &res)
	return res
}

func backTrace(candidates []int, startIndex int, target int, count int, comb []int, res *[][]int, ) {
	if count == target { // each candidate > 1, omitting the situation of 0
		temp := make([]int, len(comb))
		copy(temp, comb)
		*res = append(*res, temp)
	}
	for i := startIndex; i < len(candidates) && count < target; i++ {
		if i == startIndex || candidates[i] != candidates[i-1] {
			count += candidates[i]
			comb = append(comb, candidates[i])
			backTrace(candidates, i+1, target, count, comb, res)
			count -= candidates[i]
			comb = comb[:len(comb)-1]
		}

	}
}

Note:

back-tracing方法。但是每个candidate不是无限制取用了，所以跟上一题相比，每次recursive都要+1；另外，题目注明不得有重复结果，所以需要在操作时给出合适的判断条件，剔除重复值。

首先保证重复值相互邻近，方便判断，所以需要extra overhead去排序

使用排序后的Int[]去做类似的上题的操作，但是需要这么一条语句去判断if i == startIndex || candidates[i] != candidates[i-1]

该条语句可以这样理解，可以把i == startIndex的情况想成本轮起点的第一次，也即是之前组合与本轮第一个数字所形成的的组合，是第一次形成的组合，需要保证。而重复值的剔除则需要candidates[i] != candidates[i-1]。举例，candidates=[1,2,2,2,5]，target=5。开始时以数字1作为起点开始for循环，首先判断了i == startIndex，随后开始放入1，开始下一个递归，到了数字2，2此时也符合条件，进入到下一个2，这个时候结果满足了target，开始放入结果集，此时count已经不满足小于target,所以本次第二个2开始的递归结束了，回到上一个2，此时comb里面是[1,2]，继续向后遍历，此时第二个2和第三个2由于candidates[i] != candidates[i-1]的限制，都被剔除了。也即是，如果现在已有1,2，那么距离target只有一个2的差距，那么根据递归的特性，本轮肯定是在满足了target而又返回到这里的，所以如果满足的时候使用的是第二个2，那么回到这一轮的时候，第二个2以及后面重复的2都不应该在作为新的结果放入结果集中。

我一开始的判断语句武断地写为if i>0 && candidates[i] != candidates[i-1],导致结果错误。如果使用这条错误语句，那么上面例子中的[1,2,2]就不会出现，这是因为2,2就会重复。所以i == startIndex很好的保证了某轮for循环的第一个数字一定是可以被拿入来做进行组合的，在满足条件之后递归回到上一轮的时候，此时就不需要重复值了，因为如果是需要多个重复的x值去满足一个target，那么最深处的某一轮一定是完全拿到了自己想要组合，余下的x只是重复的多余选择而已，不再需要。candidates[i] != candidates[i-1]也就在此时发挥作用。

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 can trap after raining.

Example 1:

1
2
3

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) 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.

Example 2:

1 2	Input: height = [4,2,0,3,2,5] Output: 9

Constraints:

n == height.length
0 <= n <= 3 * 104
0 <= height[i] <= 105

Solution:

func trap(height []int) int {
	l, r, curHigh, curLow := 0, len(height)-1, 0, 0
	trappedWater := 0
	for l < r {
		if height[l] < height[r] {
			curLow = height[l]
			l++
		} else {
			curLow = height[r]
			r--
		}
		curHigh = max(curHigh, curLow)
		trappedWater += curHigh - curLow
	}
	return trappedWater
}

func max(a int, b int) int {
	if a > b {
		return a
	}
	return b
}

Note:

受到LeetCode Discuss的教导，在上面贴上这种很巧妙地解题代码

curHigh：当前的可行蓄水高度

curLow：当前最低处高度

注意图上的y轴是无法作为墙的,所以[0,1….]这里没有办法蓄积到水

思路如下，左右各有一个指针。根据题目描述，囤积的雨水数量一定与最低的一边有关，所以开始遍历时，先判断左右两边指针所指向的的高度孰高孰低。用以下数据为例[9, 8, 2, 6],一开始指针指向9和6,此时6比9小，6就赋给了curHigh和curLow，此时curHigh可以安全地置为6，这是因为6属于小的一方，以6为最大高度囤积雨水，另一侧一定有一个更高的高度来兜底，导致雨水可以被囤积；r指针随后移动到了数字2，2与9比较，还是2小，所以2现在是整个数组中的最低洼，curLow=2，而当前curHigh=6，所以此时的水囤积为4，这里只考虑当前低洼处单体所可以积蓄的水量，而不用考虑两边的延伸。当r继续移动后，值8就要比当前的curHigh要大了，所以需要进行一次数值更新，而由于更新后l已经等于了r，本次计算就结束了。

再以[2, 1, 5, 4, 1, 3]为例，一开始左右比较，值2比4小，从左指针向右靠拢，2变成最高处与最低处，l指针移动到1，1与2形成的积水量为1，总量加1，再继续移动到值5，5比3要大，此时也就代表以2为左起点的蓄水面积已经到头了，也即高度为2的蓄水部分此时已经无法漫过当前的l指针指向的高度。所以实际上此时的左起点高度变为5，需要从右指针开始向左靠拢。当前可蓄水高度变为3，低洼处也被置为3；进入下一轮，l处值还是比r处大，curLow被置为1，此时高度1与高度3形成了单位2的蓄水量，总量再加2；最后一轮，r指针指向4，4依旧小于5，4重新被置为最低处值，从代码上来考虑，curHigh = max(curHigh, curLow)又保证了一旦low大于或等于原先的high，low与high就会相等，他们的差值就会变为0，不会影响到总结果;从实际上考虑，此时右边的起点也就换了，因为3为高度的蓄水区域依旧无法漫过高度4这个位置了，所以4将会成为新的右边界，而此时l与r指针已经相遇，4与5又是紧贴，2个高度是无法蓄积到水的，所以本次循环结束。

总结：该思路通过左右指针的移动找到当前数组里的蓄水池可行高度，并且将目标着眼于每个遍历到的高度与当前可行高度的差值，继而得出当前高度可以贡献多少的蓄水量，可以形象的想象成，他只考虑每个高度上现在能存多少水，如同空中楼阁一般立在那里，等到整个遍历结束，每个空中楼阁合在一起就变成了完整的蓄水池。

45. Jump Game II

Given an array of non-negative integers nums, 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.

You can assume that you can always reach the last index.

Example 1:

1
2
3

Input: nums = [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.

Example 2:

1 2	Input: nums = [2,3,0,1,4] Output: 2

Constraints:

1 <= nums.length <= 3 * 104
0 <= nums[i] <= 105

Solution:

func jump(nums []int) int {
	curFar, curEnd, jump := 0, 0, 0
	for i, step := range nums {
		if curEnd == len(nums)-1 {
			return jump
		}
		curFar = max(i+step, curFar)
		if i == curEnd {
			jump++
			curEnd = curFar
		}
	}
	return jump
}

Note:

Related Topics提示是greedy，但是巧妙的思路应该是这样的，遍历数组，对每一个遍历到每一个点所可以跳跃的最远距离做一次比较记录，而不去逐一考虑该点的每种情况。

以[2,3,1,1,4]为例，开始时首先在2的位置，此时可以选择跳2步，或者跳1步，根据以上思想，我们只看现在的位置可以到达的最远距离，值为i+step=0+2=2,也即是当前点最远可以到index=2的1处，而此时i == curEnd，jump就需要加1，也即代表从2到3,1这些范围的区域，最少只需要一步，curEnd此时也等于2(index)；之后遍历到第二个点，此时curFar = max(i+step, curFar)得出的值是3+1=4, (4就是最后的终点)。但是此时的index并没有等于curEnd，所以此轮只更新curFar，到第三轮的时候，i=curEnd，此时我们可以发现，curFar==4，这表示在该点之前，就已经有一个点可以跳到终点，而由于那个点的index肯定小于当前index，所以那个点一定是在当前的jump数内可达的，但是此时curEnd的值并不等于终点，也即所以要想跳到终点，总的jump数一定是先到达那个点，随后再通过那个点跳到终点，所以jump++

if curEnd == len(nums)-1 {...}保证jump不会多计数（针对开头一步就跳到终点的情况

每个jump下的curEnd一定是当前jump时，所能够达到的最远距离，也是最接近终点的距离

48. Rotate Image

You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).

You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

Example 1:

1 2	Input: matrix = [[1,2,3],[4,5,6],[7,8,9]] Output: [[7,4,1],[8,5,2],[9,6,3]]

Constraints:

matrix.length == n
matrix[i].length == n
1 <= n <= 20
-1000 <= matrix[i][j] <= 1000

Solution:

func rotate(matrix [][]int) {
	if len(matrix) == 0 {
		return
	}
	xRange, yRange := len(matrix), len(matrix[0])
	for x := 0; x < xRange; x++ {
		for y := x; y < yRange; y++ {
			if x == y {
				continue
			}
			matrix[x][y], matrix[y][x] = matrix[y][x], matrix[x][y]
		}
	}
	for x := 0; x < xRange; x++ {
		for y := 0; y < yRange>>1; y++ {
			matrix[x][yRange-y-1], matrix[x][y] = matrix[x][y], matrix[x][yRange-y-1]
		}
	}
}

Note:

90度顺时针旋转可以由分解为以下过程（建立在n x n的matrix的基础上) ，沿对角线的对应元素置换，即i==j的对角线上的元素不动，x行y列与y行x列元素相交换，随后沿着垂直中心轴，再镜像翻转，倒数第一列与第一列置换，倒数第二列与第二列置换

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.

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.

Example 1:

1
2
3

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Given an array of non-negative integers nums, 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.

You can assume that you can always reach the last index.

Example 1:

1
2
3

Input: nums = [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.

Example 2:

1 2	Input: nums = [2,3,0,1,4] Output: 2

Constraints:

1 <= nums.length <= 3 * 104
0 <= nums[i] <= 105

Solution:

func maxSubArray(nums []int) int {
    if len(nums) == 0{
        return 0
    }
    dp:=make([]int,len(nums))
    maxV := nums[0]
    dp[0] = nums[0]
    for i:=1;i<len(nums);i++{
        if dp[i-1] > 0{
             dp[i]=nums[i]+dp[i-1]
        }else{
             dp[i]=nums[i] //omitting +0
        }
        maxV = max(maxV, dp[i])
    }
    return maxV
}

func max(a int, b int) int {
    if a > b{
        return a
    }
    return b
}

Note:

dp思想，dp[i]等于前i个元素中所可以组成的连续序列的最大值，一开始dp[0] （index为0，实则为第一个元素)它的最大值就是它本身，注意题目要求必须选择有一个元素，所以dp[0]赋值为nums[0]就是为了确保nums只有一个元素的情况下也可以正确返回结果，随后我们要判断dp[i-1]与0的大小，也即是当前的dp[i]需要参考i-1个元素形成的结果，如果他们形成的最大值是负数，那么舍去负数一定是正确的，负的dp[i-1]对之后的结果不会存在正向帮助，任何组合加上负数一定会变小，此时需要重新以nums[i]开始一个新的序列。

一个nums里如果全部是负数，那么最大的序列就是找到最小的负数，并且它们在上面的for循环中也无法形成任何一个连续的序列。

Page View

Prev Home Next

LeetCode-Array-I

LeetCode - topics: Array (Part I)

1. Two Sum

Solution:

Note:

2. Median of Two Sorted Arrays

Solution:

Note:

11. Container With Most Water

Solution:

Note:

15. 3Sum

Solution:

Note:

16. 3Sum Closest

Solution:

Note:

18. 4Sum

Solution:

Note:

26. Remove Duplicates from Sorted Array

Solution:

Note:

27. Remove Element

Solution:

Note:

33. Search in Rotated Sorted Array

Solution:

Note:

34. Find First and Last Position of Element in Sorted Array

Solution:

Note:

35. Search Insert Position

Solution:

Note:

39. Combination Sum

Solution:

Note:

40. Combination Sum II

Solution:

Note:

42. Trapping Rain Water

Solution:

Note:

45. Jump Game II

Solution:

Note:

48. Rotate Image

Solution:

Note:

53. Maximum Subarray

Solution:

Note: