最长不含重复字符的子串
剑指 Offer 48. 最长不含重复字符的子字符串
请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符串的长度。
示例 1:
输入: "abcabcbb"输出: 3 解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
示例 2:
输入: "bbbbb"输出: 1解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
示例 3:
输入: "pwwkew"输出: 3解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。 请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。
解题思路
双指针 + set查重
class Solution {public: int lengthOfLongestSubstring(string s) { set<int> temp; int len = s.size ...
把数字翻译成字符串
剑指 Offer 46. 把数字翻译成字符串
给定一个数字,我们按照如下规则把它翻译为字符串:0 翻译成 “a” ,1 翻译成 “b”,……,11 翻译成 “l”,……,25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数,用来计算一个数字有多少种不同的翻译方法。
示例 1:
输入: 12258输出: 5解释: 12258有5种不同的翻译,分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"
解题思路
解题详解:题目解析–把数字翻译成字符串
class Solution {public: int translateNum(int num) { string s = to_string(num); int len = s.size(); vector<int> res(len+1); for(int i = 0; i <= len; i++) ...
比特位计数
比特位计数
给你一个整数 n ,对于 0 <= i <= n 中的每个 i ,计算其二进制表示中 1 的个数 ,返回一个长度为 n + 1 的数组 ans 作为答案。
示例 1:
输入:n = 2输出:[0,1,1]解释:0 --> 01 --> 12 --> 10
示例 2:
输入:n = 5输出:[0,1,1,2,1,2]解释:0 --> 01 --> 12 --> 103 --> 114 --> 1005 --> 101
解题思路
计算整数转化为二进制数后1的个数,大致有三种方法:除二取余、移位和与运算。
第一种方法:除二取余
int Count_one(int value){ int count = 0; value = abs(value); while (value) { if (value % 2 == 1) count++; value /= 2; } return count;}
第二种方法:移位
int Count_one(int ...
礼物的最大价值
剑指 Offer 47. 礼物的最大价值
在一个 m*n 的棋盘的每一格都放有一个礼物,每个礼物都有一定的价值(价值大于 0)。你可以从棋盘的左上角开始拿格子里的礼物,并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值,请计算你最多能拿到多少价值的礼物?
示例 1:
输入: [ [1,3,1], [1,5,1], [4,2,1]]输出: 12解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物
提示:
0 < grid.length <= 200
0 < grid[0].length <= 200
相关标签
数组 动态规划 矩阵
解题思路
这是一道简单的动态规划问题,相对于其他简单的动态规划问题,这个题目的变化为二维DP,不是简单的线性DP。
该题的关键为确立准确的状态转移方程,在我解答过程中,也是因为线性转移方程建立失误,只考虑了普通的情况,并没有考虑单行转移或者单列转移的情况。
起初我想的是从后面开始计算,到后面发现从前面开始计算似乎更合理。
class Solution & ...
把字符串转换为整数
剑指 Offer 67. 把字符串转换成整数
写一个函数 StrToInt,实现把字符串转换成整数这个功能。不能使用 atoi 或者其他类似的库函数。
首先,该函数会根据需要丢弃无用的开头空格字符,直到寻找到第一个非空格的字符为止。
当我们寻找到的第一个非空字符为正或者负号时,则将该符号与之后面尽可能多的连续数字组合起来,作为该整数的正负号;假如第一个非空字符是数字,则直接将其与之后连续的数字字符组合起来,形成整数。
该字符串除了有效的整数部分之后也可能会存在多余的字符,这些字符可以被忽略,它们对于函数不应该造成影响。
注意:假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时,则你的函数不需要进行转换。
在任何情况下,若函数不能进行有效的转换时,请返回 0。
说明:
假设我们的环境只能存储 32 位大小的有符号整数,那么其数值范围为 [−231, 231 − 1]。如果数值超过这个范围,请返回 INT_MAX (231 − 1) 或 INT_MIN (−231) 。
示例 1:
输入: "42"输出: 42
示例 2:
输入 ...
滑动窗口的最大值
滑动窗口最大值
给你一个整数数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
示例 1:输入:nums = [1,3,-1,-3,5,3,6,7], k = 3输出:[3,3,5,5,6,7]解释:滑动窗口的位置 最大值--------------- -----[1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7
示例 2:输入:nums = [1], k = 1输出:[1]
解题思路
1、暴力法(超时)
基本思路就是 双重循环,在每次滑动的时候找到每 ...
TCP连接的释放
Tcp连接的释放
TCP连接的释放过程通常称为 四次握手。
第一步:客户机打算关闭连接,向其TCP发送连接释放报文段,并停止发送数据,主动关闭TCP连接,该报文段的终止位FIN=1,序号seq=u,它等于前面已传送过的数据的最后一个字节的序号加1,FIN报文段即使不携带数据,也消耗一个序号。(TCP是全双工的,即可以想象为一条TCP连接上有两条数据通路,发送FIN的一端不能再发送数据,即关闭了其中一条数据通路,但对方还可以发送数据)。
第二步:服务器收到连接释放报文段后即发送确认,确认号ack=u+1,序号seq=v,等于他前面已传送过的数据的最后一个字节的序号加上1。此时,从客户机到服务器这个方向的连接就释放了,TCP连接处于半关闭状态。但服务器若发送数据,客户机仍要接收,即从服务器到客户机这个方向的连接并未关闭。
第三步:若服务器已没有要向客户机发送的数据,就通知TCP释放连接,此时其发送FIN=1的连接释放报文段。设该报文段的序号为w(在半关闭状态下服务器可能有发送了一些数据),还须重复上次已发送的确认号ack=u+1。
第四步:客户机收到连接释放报 ...
TCP连接的建立和SYN洪泛攻击
Tcp连接的建立及SYN洪泛攻击
Tcp连接的建立(三次握手)
连接建立前,服务器进程处于LISTEN状态,等待客户的连接请求。
一: 客户端发送tcp连接请求报文段,Tcp首部SYN=1,seq=x。(Tcp规定,SYN报文段不能携带数据,但要消耗掉一个序号)
二: 服务器的Tcp收到连接请求报文段后,如果同意建立连接,则向客户端发回确认,并为该Tcp连接分配缓存和变量。确认报文段中,SYN=1,ACK=1,ack=x+1,seq=y(自己选择的一个初始序号y)。(确认报文段中不能携带数据,但也要消耗一个序号)
三: 客户端收到确认报文段之后,还要向服务器给出确认,并为该Tcp连接分配缓存和变量。ACK=1,ack=y+1,seq=x+1。该报文段可以携带数据,若不携带数据,则不消耗序号。
建立连接总结:
① SYN=1,seq=x
② SYN=1,ACK=1,seq=y,ack=x+1
③ ACK=1,seq=x+1,ack=y+1
服务器端的资源是在完成第二次握手时分配的,而客户端的资源是在完成第三次握手时分配的,这就使得服务器易于 ...
解忧杂货店
解忧杂货店读后感
故事人物: 女击剑运动员静子 -> 业余歌手克郎 -> 家境落败浩介 -> 幸运之女晴美
作者借助杂货店巧妙地连接过去与未来,却在文末三人绑架晴美处时间合二为一,想想更觉得神奇。期间三人在杂货店帮过许多有着不同烦恼的人顺利地找到了人生的目标和动力,包括晴美;帮助她又伤害到她,三人觉得很过不去,并决定自首,再也不碰别人的东西。
从开始的三人逃亡,到文末渐渐拨开逃亡的原因,以及在杂货店中帮助过去时空有着烦恼的人,读完全文之后,却发觉文中全部人物都有着千丝万缕的联系;而杂货店作为极为重要的纽带,带给全文奇幻而温馨的感觉。
文中人物对烦恼做出的选择,有关于爱情的,关于亲情的,关于金钱的以及关于回报感恩的。在讲述他们的故事的同时,也在提醒我们在人生岔道口时的抉择;在领略爱情的美好时,也在教会我们如何爱与成长;在遇见多形形色色的人后,依然感叹世界的渺小。
合上书本,可能就是这样一本书,能够从内心深处感受到一丝慰藉和温暖,需要静坐细细聆听他们的故事,就像浪矢先生一样。