文章 217
评论 6
浏览 143930
Dynamic Progamming - 198. House Robber

Dynamic Progamming - 198. House Robber

198. House Robber You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night. Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob....

Dynamic Programming - 221. Maximal Square

Dynamic Programming - 221. Maximal Square

221. Maximal Square Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containing only 1’s and return its area. Example: Input: 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0 Output: 4 思路: 题目意思是给一个矩阵,找出矩阵中最大的正方形面积,正方形里面全是1。使用动态规划的思想做,子问题就是对于任意一个值为1的网格,去比较网格上一个格和左边一格和左上角的网格所记录的最大正方形边长。然后当前格的最小正方形边长就等于前面三者最小值加一,所以状态转移方程就是dp[i][j] = min{dp[i-1][j-1], dp[i][j-1], dp[i-1][j]}, dp[i][j]代表了第i行第j列位置为正方形的右下角,所能表示的最大正方形边长。初始条件和边界条件是第一行和第一列。 代码: go: func maximalSquare(matrix [][]by....

Dynamic Programming - 174. Dungeon Game

Dynamic Programming - 174. Dungeon Game

174. Dungeon Game The demons had captured the princess (P) and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of M x N rooms laid out in a 2D grid. Our valiant knight (K) was initially positioned in the top-left room and must fight his way through the dungeon to rescue the princess. The knight has an initial health point represented by a positive integer. If at any point his health point drops to 0 or below, he dies immediately. Some of the rooms are guarded by....

Dynamic Programming - 97. Interleaving String

Dynamic Programming - 97. Interleaving String

97. Interleaving String Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2. Example 1: Input: s1 = “aabcc”, s2 = “dbbca”, s3 = “aadbbcbcac” Output: true Example 2: Input: s1 = “aabcc”, s2 = “dbbca”, s3 = “aadbbbaccc” Output: false 思路: 题目意思是指如果用s1和s2可以拼出s3就返回true,但注意拼接的时候是存在顺序的,就是用来拼接s1和s2的字符在s3中顺序需要和原来一样。考虑最后一步是s3的最后一个字母该来自于谁,之前的拼接出来的结果是否合法,就等价于一个拼接合法字符串加上s1或者s2最后一个字符等于最终结果,这就把问题退化为求上一个合法字符串拼接的问题,很明显,可以用动态规划来做. 如图: ( )s1....

Dynamic Programming - 72. Edit Distance

Dynamic Programming - 72. Edit Distance

72. Edit Distance Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2. You have the following 3 operations permitted on a word: Insert a character Delete a character Replace a character Example 1: Input: word1 = “horse”, word2 = “ros” Output: 3 Explanation: horse -> rorse (replace ‘h’ with ‘r’) rorse -> rose (remove ‘r’) rose -> ros (remove ‘e’) Example 2: Input: word1 = “intention”, word2 = “e....

Dynamic Programming - 64. Minimum Path Sum

Dynamic Programming - 64. Minimum Path Sum

64. Minimum Path Sum Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path. Note: You can only move either down or right at any point in time. Example: Input: [   [1,3,1], [1,5,1], [4,2,1] ] Output: 7 Explanation: Because the path 1→3→1→1→1 minimizes the sum. 思路: 题目意思是给一个网格,找出左上角到右下角最短路径和,和62、63、120题很像,都是经典dp最值问题,子问题就是走到当前位置从哪个方向过来的数值最小。 代码: go: // time:....

Dynamic Programming - 322. Coin Change

Dynamic Programming - 322. Coin Change

322. Coin Change You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1. Example 1: Input: coins = [1, 2, 5], amount = 11 Output: 3 Explanation: 11 = 5 + 5 + 1 Example 2: Input: coins = [2], amount = 3 Output: -1 Note: You may assume that you have an infinite number of each ....

计网 - tcp和udp(一)

计网 - tcp和udp(一)

传输层为应用层提供通信服务,使用网络层的服务。 传输层的功能: 1. 传输层提供进程和进程之间的逻辑通信,而网络层提供主机之间的逻辑通信。 2. 复用和分用。 3. 传输层对收到的报文进行差错检测。 传输层的两种协议: TCP : 面向连接的传输控制协议TCP 传输数据之前必须建立连接,数据传送结束后要释放连接。不提供广播或多播服务。由于TCP要提供可靠的面向连接的传输服务,因此不可避免的增加了许多开销,确认、流量控制、计时器以及连接管理等。 可靠、面向连接、时延大,适用于大文件 UDP: 无连接的用户数据报协议 传输数据之前不需要建立连接,收到UDP报文后也不需要给出任何确认。 不可靠,无连接,时延小,适用于小文件 传输层的寻址与端口 复用:应用层的所有应用进程都可以通过传输层再传输到网络层。 分用:传输层从网络层收到数据后交付给指明的应用进程。 逻辑端口/软件端口 是传输层的SAP(server access point),标识主机中的应用进程。 端口号长度为两个字节16bit,能表示65536各不同的端口号。 在网络中采用发送方和接收方的套接字组合来识别端口,套接字唯一标识了网络....

操作系统 - 进程

操作系统 - 进程

系统为每一个运行的程序配置一个数据结构,称为进程控制块(PCB),用来描述进程的各种信息(如程序代码存放位置) 进程定义 为了方便操作系统管理多道程序,完成各程序并发执行,引入进程、进程实体的概念。 PCB、程序段、数据段三部分构成进程实体(进程映像) 程序段只要存放的是程序代码,数据段主要存放的是程序运行时使用、产生的运算数据。如全局变量、局部变量、宏定义的常量就存放在数据段内。 一般情况下,把进程实体就简称为进程,例如所谓创建进程,实质上就是创建进程实体中的PCB;而撤销进程,实质就是撤销进程实体中的PCB。注意:PCB是进程存在的唯一标志! 也就是说,进程可以定义为:进程是进程实体的运行过程,是系统进行资源分配和调度的一个独立单位。 PCB: 进程的组织方式 进程的组织讨论的是多个进程之间的组织方式,主要有链接方式和索引方式。 - 链接方式:按照进程状态将PCB分成多个队列,操作系统持有指向各个队列的指针 - 索引方式:根据进程状态的不同,建立几张索引表,操作系统持有指向各个索引表的指针。 进程的特征 进程和程序是两个截然不同的概念,相比 程序,进程有以特征: 进程的状态和转....

Dynamic Programming - 279. Perfect Squares

Dynamic Programming - 279. Perfect Squares

279. Perfect Squares Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n. Example 1: Input: n = 12 Output: 3 Explanation: 12 = 4 + 4 + 4. Example 2: Input: n = 13 Output: 2 Explanation: 13 = 4 + 9. 思路: 题目意思是求能用最少的完全平方表示一个数,有一个四平方和定理,可以在O(n)内解决问题,但是这里选择用动态规划来做,子问题就是一个数是由另一个数加上一个平方数,也就是比如A = B + x^2, 而B由是子问题求解,这样的话,能表示A的最少组合就是B最少组合加一,所以动态转移方程就是:dp[i] = min{dp[ i - j*j] + 1}, (j*j <= i),初始条件是dp[0] = 0....

Dynamic Programming - 120. Triangle

Dynamic Programming - 120. Triangle

120. Triangle Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below. For example, given the following triangle [ [2], [3,4], [6,5,7], [4,1,8,3] ] The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11). Note: Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle. 思路: 题目意思是给一....

Dynamic Programming - 63. Unique Paths II

Dynamic Programming - 63. Unique Paths II

63. Unique Paths II A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below). The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below). Now consider if some obstacles are added to the grids. How many unique paths would there be? An obstacle and empty space is marked as 1 and 0 respectively in the gri....

Dynamic Programming - 62. Unique Paths

Dynamic Programming - 62. Unique Paths

62. Unique Paths A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below). The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below). How many possible unique paths are there? Above is a 7 x 3 grid. How many possible unique paths are there? Note: m and n will be at most 100. Example 1: Input: m = 3, ....

Dynamic Programming - 70. Climbing Stairs

Dynamic Programming - 70. Climbing Stairs

70. Climbing Stairs You are climbing a stair case. It takes n steps to reach to the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top? Note: Given n will be a positive integer. Example 1: Input: 2 Output: 2 Explanation: There are two ways to climb to the top. 1. 1 step + 1 step 2. 2 steps Example 2: Input: 3 Output: 3 Explanation: There are three ways to climb to the top. 1. 1 step + 1 step + 1 step 2. 1 step + 2....

LinkedList - 86. Partition List

LinkedList - 86. Partition List

86. Partition List Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x. You should preserve the original relative order of the nodes in each of the two partitions. Example: Input: head = 1->4->3->2->5->2, x = 3 Output: 1->2->2->4->3->5 思路: 题目意思是给一个链表和一个数字,将链表前半部分变成小于这个数字后半部大于等于这个数字。考的是链表基本操作。使用两个指针,记录下比输入小的链表和大于等于该数字的链表,再把两个链表接起来。 代码: java: /** * Definition for sing....

LinkedList - 148. Sort List

LinkedList - 148. Sort List

148. Sort List Sort a linked list in O(n log n) time using constant space complexity. Example 1: Input: 4->2->1->3 Output: 1->2->3->4 Example 2: Input: -1->5->3->4->0 Output: -1->0->3->4->5 思路: 题目意思很明确,给一个链表排序,排序的方式有很多,这里写一下归并排序。 代码: java: /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode sortList(ListNode head) { ....

Array - 188. Best Time to Buy and Sell Stock IV

Array - 188. Best Time to Buy and Sell Stock IV

188. Best Time to Buy and Sell Stock IV Say you have an array for which the _i_th element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete at most k transactions. Note: You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again). Example 1: Input: [2,4,1], k = 2 Output: 2 Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2. ....

LinkedList - 61. Rotate List

LinkedList - 61. Rotate List

61. Rotate List Given a linked list, rotate the list to the right by k places, where k is non-negative. Example 1: Input: 1->2->3->4->5->NULL, k = 2 Output: 4->5->1->2->3->NULL Explanation: rotate 1 steps to the right: 5->1->2->3->4->NULL rotate 2 steps to the right: 4->5->1->2->3->NULL Example 2: Input: 0->1->2->NULL, k = 4 Output: 2->0->1->NULL Explanation: rotate 1 steps to the right....

LinkedList - 143. Reorder List

LinkedList - 143. Reorder List

143. Reorder List Given a singly linked list L: L_0→_L_1→…→_L__n-1→_L_n, reorder it to: L_0→_L__n_→_L_1→_L__n-1→_L_2→_L__n_-2→… You may not modify the values in the list’s nodes, only nodes itself may be changed. Example 1: Given 1->2->3->4, reorder it to 1->4->2->3. Example 2: Given 1->2->3->4->5, reorder it to 1->5->2->4->3. 思路: 题目意思是给一个链表,然后重新按照一个前一个后的顺序重新排序。题目主要是考链表的操作,比如找到链表的终点,然后翻转链表,然后交换链表的节点,考的就是链表操作基本功。注意找中点的时候,找到的....

LinkedList - 160. Intersection of Two Linked Lists

LinkedList - 160. Intersection of Two Linked Lists

160. Intersection of Two Linked Lists Write a program to find the node at which the intersection of two singly linked lists begins. For example, the following two linked lists: begin to intersect at node c1. Example 1: ``` Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3 Output: Reference of the node with value = 8 Input Explanation: The intersected node’s value is 8 (note that this must not be 0 if the two lists intersect). From the head of A, it r....

Nothing just happens, it's all part of a plan.