# long·pf

## 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. Example: Input: [0,1,0,2,1,0,1,3,2,1,2,1] Output: 6 解法1 这道题给出一个数组,每个元素是一个宽为1的bar,问这些bar组成的图行最多能装多少水,就是图上蓝色的部分.如果当前位置高度大于两边的高度,我们就认为当前位置对结果有贡献.当前位置的贡献值,为左边高度的最大值和右边高度的最大值,取其中最小的和当前的高度相减. class Solution { public: int trap(vector<int>& height) { int l=0,r=height.size()-1,level=0,water=0; while(l < r){ int lower = height[height[l]<height[r]?

## 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. Difficulty: Hard 这道题让我们找出数组中首个缺失的整数. 并且限定了时间负责度为O(n),空间复杂度为O(1),就是不让新建新的集合. 那这样只能在原数组上进行操作. 这里只能是把对应的数放到对应的索引上.比如例2中,3需要放到index为2的位置上,1要放到index为0的位置上.4和-1因为没有对应的索引被舍弃,-1本来就是负数,4越界了.这样先通过一次for循环排好数值对应的索引.再通过一次for循环找到第一个位置不对的就ok. class Solution { public: int firstMissingPositive(vector<int>& nums) { int n = nums.size(); if (n==0) return 1; for (int i=0;i<n;i++){ while (nums[i]>0 && nums[i]<=n && nums[i]!

## 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 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: 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:

## 39. Combination Sum 组合之和

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: Input: candidates = [2,3,6,7], target = 7, A solution set is: [ [7], [2,2,3] ] Example 2:

## 38. Count and Say 计数和读法

The count-and-say sequence is the sequence of integers with the first five terms as following: 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, generate the nth term of the count-and-say sequence. Note: Each term of the sequence of integers will be represented as a string.

## 37. Sudoku Solver 求数独的一个解

Write a program to solve a Sudoku puzzle by filling the empty cells. A sudoku solution must satisfy all of the following rules: Each of the digits 1-9 must occur exactly once in each row. Each of the digits 1-9 must occur exactly once in each column. Each of the the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid. Empty cells are indicated by the character ‘.

## 36. Valid Sudoku 验证数独

Determine if a 9x9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules: Each row must contain the digits 1-9 without repetition. Each column must contain the digits 1-9 without repetition. Each of the 9 3x3 sub-boxes of the grid must contain the digits 1-9 without repetition. The Sudoku board could be partially filled, where empty cells are filled with the character ‘.

## 35. Search Insert Position 搜索插入位置

Given a sorted array 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. You may assume no duplicates in the array. Example 1 : Input: [1,3,5,6], 5 Output: 2 Example 2 : Input: [1,3,5,6], 2 Output: 1 Example 3 : Input: [1,3,5,6], 7 Output: 4 Example 4 :

## 34. Search for a Range 搜索一个范围

Given an array of integers sorted in ascending order, find the starting and ending position of a given target value. Your algorithm’s runtime complexity must be in the order of O(log n). If the target is not found in the array, return [-1, -1]. For example, Given [5, 7, 7, 8, 8, 10] and target value 8, return [3, 4]. 解法1 这道题让我们在一个有序数组中查找与输入target相同的起始位置和结束位置,限定时间复杂度为O(logn),这个是典型的二分查找时间复杂度.这道题我们先采用二分法找到一个与target相同的index,再想index的左边和右边搜索. class Solution { public: vector<int> searchRange(vector<int>& nums, int target) { int index = search(nums,0,nums.