KK's blog

LeetCode 001 Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

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

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

题目大意：

给定一个整数数组，从中找出两个数的下标，使得它们的和等于一个特定的数字。可以假设题目有唯一解。

解题思路：

1. 最简单的思路是暴力法，两重循环试遍所有组合。
2. 先排序，再用两指针法，若指针指向的数和小于target则左指针右移，反之亦然。注意，为了保持原数组的下标，要预先保留下标及值对到Node中。
3. 遍历数组，同时查看target-该数是否在HashMap中，否则加入到HashMap中。

Python代码：

1
2
3
4
5

def twoSum(self, nums: List[int], target: int) -> List[int]:
	for i in range(len(nums)):
		for j in range(i + 1, len(nums)):
			if nums[i] + nums[j] == target:
				return [i, j]

1
2
3
4
5
6
7
8
9
10

def twoSum(self, nums: List[int], target: int) -> List[int]:
	temp.sort()
	i, j = 0, len(temp) - 1
	while i < j:
		if temp[i][0] + temp[j][0] < target:
			i += 1
		elif temp[i][0] + temp[j][0] > target:
			j -= 1
		else:
			return [temp[i][1], temp[j][1]]

1
2
3
4
5
6

def twoSum(self, nums: List[int], target: int) -> List[int]:
	nums_dict = {}
	for i, n in enumerate(nums):
		if target - n in nums_dict:
             return [nums_dict[target - n], i]
		nums_dict[n] = i

第二种方法，Python的tuple相当于Java的自定义Node，但节省了很多代码。每种方法都大概节省了2/3的代码。

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13

public int[] twoSum0(int[] nums, int target) {
	int[] re = new int[2];
	for(int i=0;i<nums.length;i++)
		for(int j=i+1;j<nums.length;j++){
			if(nums[i]+nums[j]==target){
				re[0] = i;
				re[1] = j;
				return re;
			}
				
		}
	return re;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

public int[] twoSum2(int[] nums, int target) {
	Node[] ary = new Node[nums.length];
	for(int i=0;i<nums.length;i++){
		ary[i] = new Node(i, nums[i]);
	}
	
	Arrays.sort(ary, new Comparator<Node>() {
		@Override
		public int compare(Node o1, Node o2) {
			return o1.value - o2.value;
		}
	});
	int[] re = new int[2];
	int start=0, end=nums.length-1;
	while(start<end){
		if(ary[start].value+ary[end].value==target){
			re[0] = ary[start].index;
			re[1] = ary[end].index;
			return re;
		}
		else if(ary[start].value+ary[end].value<target)
			start++;
		else
			end--;
	}
	return re;
}

class Node {
	Node(int i, int v){
		this.index = i;
		this.value = v;
	}
	int index;
	int value;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

public int[] twoSum(int[] nums, int target) {
	HashMap<Integer,Integer> h  = new HashMap<Integer,Integer>();
	
	int[] re = new int[2];
	for(int i=0;i<nums.length;i++){
		Integer index = h.get(target-nums[i]);
		if(index!=null){
			re[0]=index;
			re[1]=i;
			return re;
		}
		h.put(nums[i],i);
	}
	return re;
}

TypeScript代码：

1
2
3
4
5
6
7
8
9
10

function twoSum(nums: number[], target: number): number[] {
    for(let i=0; i<nums.length; i++) {
        for(let j=i+1; j<nums.length; j++) {
            if(nums[i] + nums[j] === target) {
                return [i, j]
			}
        }
    }
    return []; // throw new Error("No solution");
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

function twoSum(nums: number[], target: number): number[] {
    const arr = nums.map((value, index) => ({value, index}));
    arr.sort((a, b) => (a.value - b.value))
    let i = 0, j = arr.length-1;
    while(i<j) {
        if(arr[i].value + arr[j].value === target) {
            return [arr[i].index, arr[j].index];
        } else if(arr[i].value + arr[j].value < target) {
            i++;
        } else {
            j--;
        }
    }
    return []; // throw new Error("No solution");
};

1
2
3
4
5
6
7
8
9
10
11

function twoSum(nums: number[], target: number): number[] {
    const val2Index = new Map<number, number>();
    for(let i=0; i<nums.length; i++) {
        if(val2Index.has(target-nums[i])) {
            return [i, val2Index.get(target-nums[i])!];
        } else {
            val2Index.set(nums[i], i);
        }
    }
    return []; // throw new Error("No solution");
};

算法分析：

1. 时间复杂度为O(n2)，空间复杂度O(1)。
2. 时间复杂度为O(nlogn)，空间复杂度O(n)。
3. 时间复杂度为O(n)，空间复杂度O(n)。

LeetCode 2079 Watering Plants

You want to water n plants in your garden with a watering can. The plants are arranged in a row and are labeled from 0 to n - 1 from left to right where the i<sup>th</sup> plant is located at x = i. There is a river at x = -1 that you can refill your watering can at.

Each plant needs a specific amount of water. You will water the plants in the following way:

• Water the plants in order from left to right.
• After watering the current plant, if you do not have enough water to completely water the next plant, return to the river to fully refill the watering can.
• You cannot refill the watering can early.

You are initially at the river (i.e., x = -1). It takes one step to move one unit on the x-axis.

Given a 0-indexed integer array plants of n integers, where plants[i] is the amount of water the i<sup>th</sup> plant needs, and an integer capacity representing the watering can capacity, return the number of steps needed to water all the plants.

Example 1:

**Input:** plants = [2,2,3,3], capacity = 5
**Output:** 14
**Explanation:** Start at the river with a full watering can:
- Walk to plant 0 (1 step) and water it. Watering can has 3 units of water.
- Walk to plant 1 (1 step) and water it. Watering can has 1 unit of water.
- Since you cannot completely water plant 2, walk back to the river to refill (2 steps).
- Walk to plant 2 (3 steps) and water it. Watering can has 2 units of water.
- Since you cannot completely water plant 3, walk back to the river to refill (3 steps).
- Walk to plant 3 (4 steps) and water it.
Steps needed = 1 + 1 + 2 + 3 + 3 + 4 = 14.

Example 2:

**Input:** plants = [1,1,1,4,2,3], capacity = 4
**Output:** 30
**Explanation:** Start at the river with a full watering can:
- Water plants 0, 1, and 2 (3 steps). Return to river (3 steps).
- Water plant 3 (4 steps). Return to river (4 steps).
- Water plant 4 (5 steps). Return to river (5 steps).
- Water plant 5 (6 steps).
Steps needed = 3 + 3 + 4 + 4 + 5 + 5 + 6 = 30.

Example 3:

**Input:** plants = [7,7,7,7,7,7,7], capacity = 8
**Output:** 49
**Explanation:** You have to refill before watering each plant.
Steps needed = 1 + 1 + 2 + 2 + 3 + 3 + 4 + 4 + 5 + 5 + 6 + 6 + 7 = 49.

Constraints:

• n == plants.length
• 1 <= n <= 1000
• 1 <= plants[i] <= 10<sup>6</sup>
• max(plants[i]) <= capacity <= 10<sup>9</sup>

题目大意：

x坐标上分别是浇每棵植物需要的水量，用数组plants表示，-1上为河水可以打水，capacity是容器大小。若发现水不够，就要回到河里将容器打满水。问浇完所有植物的总步数

解题思路：

此题类似于Leetcode 2073，可以按部就班按每个plant计算，但是为了提高效率，一般采取归结为更高一层次计算。
这题更高层次是每次去洒水再回去河边作为一个循环。最后一个循环不用回河边所以是单程。

解题步骤：

1. 计算一次来回的距离，条件为剩余的水不够浇该次的植物
2. 退出循环后，计算单程距离

注意事项：

1. 如果满足capacity也要递归到下一轮再计算，也就是Line 5取等号

Python代码：

1
2
3
4
5
6
7
8
9
10
11

def wateringPlants(self, plants: List[int], capacity: int) -> int:
	sum, steps = 0, 0
	for i, n in enumerate(plants):
		sum += plants[i]
		if sum <= capacity:
			continue
		steps += i * 2  # back to river
		sum = plants[i]
	if sum > 0:
		steps += len(plants)
	return steps

算法分析：

时间复杂度为O(n)，空间复杂度O(1)。

LeetCode 493 Reverse Pairs

Given an integer array nums, return the number of reverse pairs in the array.

A reverse pair is a pair (i, j) where 0 <= i < j < nums.length and nums[i] > 2 * nums[j].

Example 1:

**Input:** nums = [1,3,2,3,1]
**Output:** 2

Example 2:

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

Constraints:

• 1 <= nums.length <= 5 * 10<sup>4</sup>
• -2<sup>31</sup> <= nums[i] <= 2<sup>31</sup> - 1

题目大意：

求数组的逆序数

解题思路：

1. Merge sort模板
2. merge分两部分写，一个部分比较求个数，另一部分排序

注意事项：

1. merge分两部分写，一个部分比较，另一部分排序
2. 计算个数由两部分组成，两指针部分和剩余元素部分。若以后半数组为主，就是前半数组指针i的后面个数(程序用此)
   若以前半数组为主(加入到res时候)，就是后半数组指针j的前面个数
3. nums[start:end+1] = res，前面是nums不是res

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

def reversePairs(self, nums: List[int]):
	if not nums:
		return 0
	return self.m_sort(nums, 0, len(nums) - 1)

def m_sort(self, nums, start, end):
	if start >= end:
		return 0
	mid = start + (end - start) // 2
	count = 0
	count += self.m_sort(nums, start, mid)
	count += self.m_sort(nums, mid + 1, end)
	count += self.merge(nums, start, mid, end)
	return count

def merge(self, nums, start, mid, end):
	i, j, res, count = start, mid + 1, [], 0
	while i <= mid and j <= end:
		if nums[i] <= 2 * nums[j]:
			i += 1
		else:
			count += mid - i + 1
			j += 1

	while i <= mid:
		i += 1
	while j <= end:
		count += mid - i + 1
		j += 1

	i, j, res = start, mid + 1, []
	while i <= mid and j <= end:
		if nums[i] <= nums[j]:
			res.append(nums[i])
			i += 1
		else:
			res.append(nums[j])
			j += 1

	while i <= mid:
		res.append(nums[i])
		i += 1
	while j <= end:
		res.append(nums[j])
		j += 1

	nums[start:end + 1] = res
	return count

算法分析：

时间复杂度为O(nlogn)，空间复杂度O(n)。

LeetCode 503 Next Greater Element II

Given a circular array (the next element of the last element is the first element of the array), print the Next Greater Number for every element. The Next Greater Number of a number x is the first greater number to its traversing-order next in the array, which means you could search circularly to find its next greater number. If it doesn’t exist, output -1 for this number.

Example 1:

Input: [1,2,1]
Output: [2,-1,2]
Explanation: The first 1's next greater number is 2;   
The number 2 can't find next greater number;   
The second 1's next greater number needs to search circularly, which is also 2.

Note: The length of given array won’t exceed 10000.

题目大意：

给定一个循环数组（末尾元素的下一个元素为起始元素），输出每一个元素的下一个更大的数字（Next Greater Number）。Next Greater Number是指位于某元素右侧，大于该元素，且距离最近的元素。如果不存在这样的元素，则输出-1。

注意：给定数组长度不超过10000。

解题思路：

最直接的思路是遍历每个元素，对每个元素，遍历它的后面所有元素。最差情况是递减数列，时间复杂度为O(n2)。
这题关于局部递增数组，所以考虑用递减栈。首先不考虑循环数组的情况，例如8,5,4,6,栈存入8,5,4，当6准备进栈时，5,4比6小，它们都出栈且它们的结果集为6。
循环数组其实只要将原数组复制一倍，按原算法处理，结果集取前n个元素即可。

1. 栈不为空，准入栈元素逼出比其小的元素且赋予其结果。
2. 该元素入栈。、
3. 栈剩下元素的结果集赋值为-1

注意事项：

1. 栈存储元素下标，结果集存储元素值。
2. 栈剩下元素的结果集赋值为-1

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13

def nextGreaterElements(self, nums: List[int]) -> List[int]:
	num_list = nums * 2
	result, stack = [0] * len(num_list), []
	for i in range(len(num_list)):
		while stack and num_list[i] > num_list[stack[-1]]:
			index = stack.pop()
			result[index] = num_list[i]
		stack.append(i)

	while stack:
		index = stack.pop()
		result[index] = -1
	return result[:len(nums)]

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

public int[] nextGreaterElements(int[] nums) {
	Stack s = new Stack();
	int[] nums2 = new int[nums.length*2];
	int[] re2 = new int[nums2.length];
	for(int i=0;i<nums2.length;i++){
		nums2[i] = nums[i%nums.length];
	}
	for(int i=0;i<nums2.length;i++){
		while(!s.isEmpty() && nums2[i]>nums2[(int)s.peek()]){
			int topIdx = (int)s.pop();
			re2[topIdx] = nums2[i];
		}
		s.add(i);
	}
	while(!s.isEmpty()){
		int topIdx = (int)s.pop();
		re2[topIdx] = -1;
	}
	int[] re = new int[nums.length];
	for(int i=0;i<nums.length;i++)
		re[i] = re2[i];
	return re;
}

算法分析：

时间复杂度为O(n)，空间复杂度O(n)。

有人考虑用TreeMap，
2
1 3
但TreeMap不能保留顺序，如这个TreeMap可以对应两种数组,[2,1,3], [2,3,1]并非一一对应。

Follow-up:

1. Given an integer array, print the Next Greater Number for every element.先从不循环数组考起。
   3,8,5,4,6,7 => 8,-1,6,6,7,-1
2. 先让其写出暴力法brute force
3. 再优化，第0个提示是考虑用一些数据结构，第一个提示为Stack。第二个提示，给定两个stack，怎么排序一个数组。如1,4,3,2.
   一个stack用于维护当前递增栈，另一个用于缓冲。过程：栈1从底到顶14，3准入，因为比4小，不能维持递增顺序，4入栈2，然后3入栈1，再把栈2所有元素入栈1。同理4,3入栈2,2入栈1。
4. 最后如果是循环数组circular array，如果解决。
   3,8,5,4,6,7 => 8,-1,6,6,7,8
5. 第一个层次暴力法，第二层次思路从第二个提示到联系到此题解法，Meets bar。最后能实现且解决follow-up，raise bar。

LeetCode 104 Maximum Depth of Binary Tree

Given the root of a binary tree, return its maximum depth.

A binary tree’s maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Example 1:

**Input:** root = [3,9,20,null,null,15,7]
**Output:** 3

Example 2:

**Input:** root = [1,null,2]
**Output:** 2

Example 3:

**Input:** root = []
**Output:** 0

Example 4:

**Input:** root = [0]
**Output:** 1

Constraints:

• The number of nodes in the tree is in the range [0, 10<sup>4</sup>].
• -100 <= Node.val <= 100

题目大意：

求二叉树高度。

解题思路：

公式dfs(root)=1+max(dfs(root.left),dfs(root.right))

Python代码：

1
2
3
4

def maxDepth(self, root: TreeNode) -> int:
	if not root:
		return 0
	return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))

算法分析：

时间复杂度为O(n)，空间复杂度O(1)。