Description

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:

1
2

Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

Difficulty: Hard

Code:

1
2
3
4
5

class Solution {
    public int trap(int[] height) {
        
    }
}

题意

收集雨水，给定n个非负整数代表宽为1不同高度柱子的容器，求它能收集多少雨水。

Description

Given an unsorted integer array, find the smallest missing positive integer.

Example 1:

1
2

Input: [1,2,0]
Output: 3

Example 2:

1
2

Input: [3,4,-1,1]
Output: 2

Example 3:

1
2

Input: [7,8,9,11,12]
Output: 1

Note:

Your algorithm should run in O(n) time and uses constant extra space.

Difficulty: Hard

Code:

1
2
3
4
5

class Solution {
    public int firstMissingPositive(int[] nums) {
        
    }
}

题意

给定一个未排序的整数数组，找出首个缺失的正数。时间复杂度要求O(n)，空间复杂度为O(1)。

Description

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

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

Note:

• All numbers (including target) will be positive integers.
• The solution set must not contain duplicate combinations.

Example 1:

1
2
3
4
5
6
7
8

Input: candidates = [10,1,2,7,6,1,5], target = 8,
A solution set is:
[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

Example 2:

1
2
3
4
5
6

Input: candidates = [2,5,2,1,2], target = 5,
A solution set is:
[
  [1,2,2],
  [5]
]

Difficulty: Medium

Code:

1
2
3
4
5

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        
    }
}

题意

给定一系列候选数字candidates和目标值target，找出所有的不重复组合使得候选数字组合的和等于目标值。

一个组合中每个候选数字元素只能使用一次，所有数字均为正整数，不能包含重复的组合。

Description

Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

The same repeated number may be chosen from candidates unlimited number of times.

Note:

• All numbers (including target) will be positive integers.
• The solution set must not contain duplicate combinations.

Example 1:

1
2
3
4
5
6

Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
  [7],
  [2,2,3]
]

Example 2:

1
2
3
4
5
6
7

Input: candidates = [2,3,5], target = 8,
A solution set is:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

Difficulty: Medium

Code:

1
2
3
4
5

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        
    }
}

题意

给定几个不重复的候选正整数和一个目标数，求所有不重复组合使得候选数相加等于目标值，候选数可以多次选择。

Description

The count-and-say sequence is the sequence of integers with the first five terms as following:

1
2
3
4
5

1.     1
2.     11
3.     21
4.     1211
5.     111221

1 is read off as “one 1” or 11.

11 is read off as “two 1s” or 21.

21 is read off as “one 2, then one 1” or 1211.

Given an integer n where 1 ≤ n ≤ 30, generate the nth term of the count-and-say sequence.

Note: Each term of the sequence of integers will be represented as a string.

Example 1:

1
2

Input: 1
Output: "1"

Example 2:

1
2

Input: 4
Output: "1211"

Difficulty: Easy

Code:

1
2
3
4
5

class Solution {
    public String countAndSay(int n) {
        
    }
}

题意

对于前一个数，找出其对应字符串中相同数字都个数，并将其个数和数字一起存到新都字符串中作为当前数字的对应结果。