牛客882265878号

分类

题解(5)

/ 注册

全部文章（共5篇）

题解 | #设计LRU缓存结构#

使用的结构是hash表+双链表，重点是掌握hash表和双链表的构造以及this指针的运用。 struct DListNode{ int key,val;//hash表 DListNode *pre;//双链表 DListNode *next; DListNode(in...

C++ 哈希表双向链表

2021-09-16

0 232

题解 | #最长递增子序列#

首先需要两个数组：temp存储原数组内容的最长递增子序列（长度同最终结果，但并非要求的最长递增子序列，需要通过nums数组进行判断）；nums存储原数组内容进入temp时的“虚拟”下标（所谓虚拟，指的是并非原数组所有内容都能进入temp，这是肯定的，但nums记录的内容确实与原数组一一对应，目的是通...

C++ 贪心二分查找数组

2021-09-16

0 346

题解 | #判断回文#

回文串是指以中心对称的字符串，即以中心字符对折，前后元素对应相等。基于此定义，可采用双指针方法，分别指向字符串的起始和末尾元素，然后进行比较，若不等则返回false，若相等则同时向中间移动。当左指针大于等于右指针时结束比较，若此前元素均对应相等，则返回true。（左右指针相等时说明原字符串为奇数串，...

C++ 字符串双指针

2021-09-15

0 253

题解 | #最大正方形#

动态规划：第一，使用二维数组dp，确定其元素含义，此处dp[i][j]表示原二维数组第i行第j列位置元素作为正方形右下角构成的最大正方形边长，即该元素必然为‘1’，若为‘0’则无法构成正方形；第二，建立状态转移方程：若matrix[i][j]为'1'时，需要检查其左、上、左上角在dp数组中的值，要构...

C++ 动态规划

2021-09-15

0 213

题解 | #最长公共子串#

动态规划方法：首先使用二维数组dp，确定其元素dp[i][j]的含义（此处指str1的第i个元素和str2的第j个元素为结尾的最长公共子串长度，注意最后一个元素必然是相同的）。然后找到状态转移方程：若新加入元素相同，则在原长度加一，即dp[i][j]=dp[i-1][j-1]+1,否则为0。接着考虑...

C++ 动态规划

2021-09-15

0 383