10000 auto commit · githubclj/InterviewNotes@3f06771 · GitHub
[go: up one dir, main page]
Skip to content

Commit 3f06771

Browse files
CyC2018CyC2018
committed
auto commit
1 parent 4596b42 commit 3f06771

File tree

2 files changed

+14
-28
lines changed

2 files changed

+14
-28
lines changed

‎notes/Leetcode 题解.md

Lines changed: 7 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -1769,8 +1769,7 @@ public int minPathSum(int[][] grid) {
17691769

17701770
定义一个数组 dp 存储上楼梯的方法数（为了方便讨论，数组下标从 1 开始），dp[i] 表示走到第 i 个楼梯的方法数目。第 i 个楼梯可以从第 i-1 和 i-2 个楼梯再走一步到达，走到第 i 个楼梯的方法数为走到第 i-1 和第 i-2 个楼梯的方法数之和。
17711771

1772-
<div align="center"><img src="https://latex.codecogs.com/gif.latex?dp[i]=dp[i-1]+dp[i-2]"/></div>
1773-
1772+
<div align="center"><img src="https://latex.codecogs.com/gif.latex?dp[i]=dp[i-1]+dp[i-2]"/></div> <br>
17741773

17751774
dp[N] 即为所求。
17761775

@@ -1799,8 +1798,7 @@ public int climbStairs(int n) {
17991798

18001799
第 i 年成熟的牛的数量为：
18011800

1802-
<div align="center"><img src="https://latex.codecogs.com/gif.latex?dp[i]=dp[i-1]+dp[i-3]"/></div>
1803-
1801+
<div align="center"><img src="https://latex.codecogs.com/gif.latex?dp[i]=dp[i-1]+dp[i-3]"/></div> <br>
18041802

18051803
**强盗抢劫**
18061804

@@ -1810,8 +1808,7 @@ public int climbStairs(int n) {
18101808

18111809
定义 dp 数组用来存储最大的抢劫量，其中 dp[i] 表示抢到第 i 个住户时的最大抢劫量。由于不能抢劫邻近住户，因此如果抢劫了第 i 个住户那么只能抢劫 i - 2 和 i - 3 的住户，所以
18121810

1813-
<div align="center"><img src="https://latex.codecogs.com/gif.latex?dp[i]=max(dp[i-2],dp[i-3])+nums[i]"/></div>
1814-
1811+
<div align="center"><img src="https://latex.codecogs.com/gif.latex?dp[i]=max(dp[i-2],dp[i-3])+nums[i]"/></div> <br>
18151812

18161813
O(n) 空间复杂度实现方法：
18171814

@@ -1891,8 +1888,7 @@ private int rob(int[] nums, int s, int e) {
18911888

18921889
综上所述，错误装信数量方式数量为：
18931890

1894-
<div align="center"><img src="https://latex.codecogs.com/gif.latex?dp[i]=(i-1)*dp[i-2]+(i-1)*dp[i-1]"/></div>
1895-
1891+
<div align="center"><img src="https://latex.codecogs.com/gif.latex?dp[i]=(i-1)*dp[i-2]+(i-1)*dp[i-1]"/></div> <br>
18961892

18971893
dp[N] 即为所求。
18981894

@@ -1908,8 +1904,7 @@ dp[N] 即为所求。
19081904

19091905
因为在求 dp[n] 时可能无法找到一个满足条件的递增子序列，此时 {S<sub>n</sub>} 就构成了递增子序列，因此需要对前面的求解方程做修改，令 dp[n] 最小为 1，即：
19101906

1911-
<div align="center"><img src="https://latex.codecogs.com/gif.latex?dp[n]=max\{1,dp[i]+1|S_i<S_n\&\&i<n\}"/></div>
1912-
1907+
<div align="center"><img src="https://latex.codecogs.com/gif.latex?dp[n]=max\{1,dp[i]+1|S_i<S_n\&\&i<n\}"/></div> <br>
19131908

19141909
对于一个长度为 N 的序列，最长子序列并不一定会以 S<sub>N</sub> 为结尾，因此 dp[N] 不是序列的最长递增子序列的长度，需要遍历 dp 数组找出最大值才是所要的结果，即 max{ dp[i] | 1 <= i <= N} 即为所求。
19151910

@@ -2050,8 +2045,7 @@ public int lengthOfLCS(int[] nums1, int[] nums2) {
20502045

20512046
综上，0-1 背包的状态转移方程为：
20522047

2053-
<div align="center"><img src="https://latex.codecogs.com/gif.latex?dp[i][j]=max(dp[i-1][j],dp[i-1][j-w]+v)"/></div>
2054-
2048+
<div align="center"><img src="https://latex.codecogs.com/gif.latex?dp[i][j]=max(dp[i-1][j],dp[i-1][j-w]+v)"/></div> <br>
20552049

20562050
```java
20572051
public int knapsack(int W, int N, int[] weights, int[] values) {
@@ -2075,8 +2069,7 @@ public int knapsack(int W, int N, int[] weights, int[] values) {
20752069

20762070
在程序实现时可以对 0-1 背包做优化。观察状态转移方程可以知道，前 i 件物品的状态仅由前 i-1 件物品的状态有关，因此可以将 dp 定义为一维数组，其中 dp[j] 既可以表示 dp[i-1][j] 也可以表示 dp[i][j]。此时，
20772071

2078-
<div align="center"><img src="https://latex.codecogs.com/gif.latex?dp[j]=max(dp[j],dp[j-w]+v)"/></div>
2079-
2072+
<div align="center"><img src="https://latex.codecogs.com/gif.latex?dp[j]=max(dp[j],dp[j-w]+v)"/></div> <br>
20802073

20812074
因为 dp[j-w] 表示 dp[i-1][j-w]，因此不能先求 dp[i][j-w] 防止将 dp[i-1][j-w] 覆盖。也就是说要先计算 dp[i][j] 再计算 dp[i][j-w]，在程序实现时需要按倒序来循环求解。
20822075

‎notes/计算机网络.md

Lines changed: 7 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -156,17 +156,15 @@
156156

157157
主机或路由器发送数据帧所需要的时间。
158158

159-
<div align="center"><img src="https://latex.codecogs.com/gif.latex?delay=\frac{l(bit)}{v(bit/s)}"/></div>
160-
159+
<div align="center"><img src="https://latex.codecogs.com/gif.latex?delay=\frac{l(bit)}{v(bit/s)}"/></div> <br>
161160

162161
其中 l 表示数据帧的长度，v 表示发送速率。
163162

164163
### 2. 传播时延
165164

166165
电磁波在信道中传播一定的距离需要花费的时间，电磁波传播速度接近光速。
167166

168-
<div align="center"><img src="https://latex.codecogs.com/gif.latex?delay=\frac{l(m)}{v(m/s)}"/></div>
169-
167+
<div align="center"><img src="https://latex.codecogs.com/gif.latex?delay=\frac{l(m)}{v(m/s)}"/></div> <br>
170168

171169
其中 l 表示信道长度，v 表示电磁波在信道上的传播速率。
172170

@@ -261,18 +259,15 @@ TCP/IP 协议族是一种沙漏形状，中间小两边大，IP 协议在其中
261259

262260
为每个用户分配 m bit 的码片，并且所有的码片正交，对于任意两个码片 <img src="https://latex.codecogs.com/gif.latex?\vec{S}"/> 和 <img src="https://latex.codecogs.com/gif.latex?\vec{T}"/> 有
263261

264-
<div align="center"><img src="https://latex.codecogs.com/gif.latex?\vec{S}\cdot\vec{T}=0"/></div>
265-
262+
<div align="center"><img src="https://latex.codecogs.com/gif.latex?\vec{S}\cdot\vec{T}=0"/></div> <br>
266263

267264
为了方便，取 m=8，设码片 <img src="https://latex.codecogs.com/gif.latex?\vec{S}"/> 为 00011011。在拥有该码片的用户发送比特 1 时就发送该码片，发送比特 0 时就发送该码片的反码 11100100。
268265

269266
在计算时将 00011011 记作 (-1 -1 -1 +1 +1 -1 +1 +1)，可以得到
270267

271-
<div align="center"><img src="https://latex.codecogs.com/gif.latex?\frac{1}{m}\vec{S}\cdot\vec{S}=1"/></div>
272-
273-
274-
<div align="center"><img src="https://latex.codecogs.com/gif.latex?\frac{1}{m}\vec{S}\cdot\vec{S'}=-1"/></div>
268+
<div align="center"><img src="https://latex.codecogs.com/gif.latex?\frac{1}{m}\vec{S}\cdot\vec{S}=1"/></div> <br>
275269

270+
<div align="center"><img src="https://latex.codecogs.com/gif.latex?\frac{1}{m}\vec{S}\cdot\vec{S'}=-1"/></div> <br>
276271

277272
其中 <img src="https://latex.codecogs.com/gif.latex?\vec{S'}"/> 为 <img src="https://latex.codecogs.com/gif.latex?\vec{S}"/> 的反码。
278273

@@ -671,13 +666,11 @@ TCP 使用超时重传来实现可靠传输：如果一个已经发送的报文
671666

672667
一个报文段从发送再到接收到确认所经过的时间称为往返时间 RTT，加权平均往返时间 RTTs 计算如下：
673668

674-
<div align="center"><img src="https://latex.codecogs.com/gif.latex?RTTs=(1-a)*(RTTs)+a*RTT"/></div>
675-
669+
<div align="center"><img src="https://latex.codecogs.com/gif.latex?RTTs=(1-a)*(RTTs)+a*RTT"/></div> <br>
676670

677671
超时时间 RTO 应该略大于 RRTs，TCP 使用的超时时间计算如下：
678672

679-
<div align="center"><img src="https://latex.codecogs.com/gif.latex?RTO=RTTs+4*RTT_d"/></div>
680-
673+
<div align="center"><img src="https://latex.codecogs.com/gif.latex?RTO=RTTs+4*RTT_d"/></div> <br>
681674

682675
其中 RTT<sub>d</sub> 为偏差，它与新的 RRT 和 RRTs 有关。
683676

0 commit comments

Comments
 (0)
0