long·pf

do your good at,challenge what do you want to do

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.

url到内容返回经历了蛇

目录 url到内容返回经历了蛇 dns解析过程 CDN的基本工作过程 url到内容返回经历了蛇 1 把url分割成几个部分: 协议,网络地址,资源路径.其中网络地址只是该链接网络上哪一台计算机,可以使域名或者ip地址,可以包括端口号;协议是从该计算机获取资源的方式,常见的HTTP,FTP,不同的协议有不同的通讯内容格式;资源路径指示从服务器上获取哪一项资源. 例如: http://www.guokr.com/question/554991/ 协议部分 http 网络地址 www.guokr.com 资源路径 /question/554991/ 2 如果地址不是一个ip地址,通过DNS(域名系统)将该地址解析成ip地址.ip地址对应着网络上一台计算机,DNS服务器本身也有IP,你的网络设置包含DNS服务器的ip. 例如 www.guokr.com不是一个ip,向DNS询问请求www.guokr.com对应的ip: 111.13.57.142.这个过程里,你的电脑直接询问DNS服务器可能没www.guokr.com对应的ip,就会想他的上级服务器学问,上级服务器同样可能没有,就一次一层层向上找,最高可达根结点,找到或者全部找不到位置 3 如果地址不包括端口号,根据协议的偶人端口号确定一个.端口号之于计算机就想窗口号之于银行. 例如www.guokr.com不包括端口号,http协议默认端口号是80.如果输入的url是http://www.guokr.com:8080/那表示不适用默认的端口号, 4 向第2和第3步确定的ip和端口号发起网络连接 列入向111.13.57.142的80端口发起连接 5 根据http协议要求,组织一个请求的数据包,包含大量请求信息.包括请求的资源路径,你的身份. 例如: 用自然语言来表达这个数据包,大概就是:请求/question/554991/d我的身份是xxxxx 6 服务器响应请求.将数据返回给浏览器.数据可能是页面,页面的布局,文字,图片,脚本等.如果资源路径只是的资源不存在,服务器就会返回注明的404错误. 7 如果第6步返回的是一个页面,根据页面里的一些外链的URL,例如图片的地址,按照1~6再次获取. 8 根据资源的类型,将资源组织成屏幕上显示的图像.这个过程叫渲染. 9 将渲染好的页面图像显示出来,并开始响应用户的操作. dns解析过程 1. 在浏览器中输入www.qq.com域名,操作系统会先检查自己本地的hosts文件是否有这个网址映射关系,如果有,就先调用合格ip地址映射,完成域名解析 2. 如果hosts没有,则查找dns解析器缓存,是否有这个网址映射关系,如果有,返回 3. 如果没有,首先会找tcp/ip参数中设置的首选dns服务器,在此我们叫他本地dns服务器,此服务器收到查询时,如果要查询的域名,包含在本地配置区域资源中,则返回解析结果给客户机,此解析具有权威性 如果要查询的域名,不由本地dns服务器区域解析,但改服务器已缓存了此网址映射关系,则返回该ip,此解析不具有权威性. 5.