# long·pf

## 146. LRU Cache 最近最少使用置换缓存器

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put. get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1. put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

## 43. Multiply Strings 字符串相乘

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string. Example 1: Input: num1 = "2", num2 = "3" Output: "6" Example 2: Input: num1 = "123", num2 = "456" Output: "56088" Note: The length of both num1 and num2 is < 110. Both num1 and num2 contain only digits 0-9. Both num1 and num2 do not contain any leading zero, except the number 0 itself.

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