最新要闻

广告

手机

iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?

iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?

警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案

家电

快报:刷题疑惑2

来源:博客园

1、整数除法:先转化为unsigned int ;通过逆向乘法,使除数左移至不大于被除数的最左位,再相减;此时的商就是1 左移对应的位数,继续循环判断左移,商 用或 逻辑相加,最终判断此值是否超过       INT_MAX INT_MIN;

2、只出现一次的数字,其余为三次:DFA,有限状态自动机,

3、单词长度的最大乘积:利用位运算,将原string都转化为 二进制位,相同的string则 相与之后不会为0,直接跳过;


(资料图)

4、前n 个数字二进制中1的个数:动态规划+最高有效位、动态规划+最低有效位、n&n-1若为0,则此时最高位为1,且只有一个1;

5、和为0的三个数:排序+双指针,注意去重操作------两层循环中都有判断,下一个数不与上一数相同,再者左指针一直小于右指针,若右指针所在下标已经大于目标值,则缩小右指针;

6、和大于等于target的最短子数组:前缀和判断(得益于数组都是非负整数,具有连续性)、或者 滑动窗口双指针,缩小左指针扩大右指针;

7、乘积小于k的子数组个数:双指针,从左往右遍历,不断累乘,若大于,则不断除去左指针所指的数,并且每次循环都 加上左右指针之间的个数(不理解相 减的原理);

8、和为k的连续子数组: 使用unordered_map记录前缀和为 sum-k的键值,利用前缀和的性质,mp[ 0] = 1, i - j 区间和为 : sum[ i] - k = sum[ j -1 ] 变换得: sum[ i] - k == sum[ j -1];(二刷还是没做出)

9、0和1个数相同的子数组:同上述问题8,将0记为-1,前缀和为0的最大下标差,初始时,mp[ 0] == -1;

10、二维子矩阵的和:使用二维前缀和,利用以(i,j)为下标的二维矩阵和相加减,减去左侧矩阵,上侧矩阵,加上一次以(i-1,j-1)结尾的矩阵数组和;

11、最长不包含重复字符的子串:动规+线性遍历;(三刷 不会);

12、API函数: isalnum:该字符是否包含字母或数字; toupper :转大写; tolower:转小写;

13、回文子字符串的个数:双循环、Manacher 马拉车算法(没看懂)(还没看):

14、含所有字符的最短字符串:滑动窗口 类型 多写写;

15、最多删除一个字符得到回文:有一个方法没通过(问题未解决);

16、链表中环的入口:边界判断条件 看看;

17、重排链表:思路一:线性表,使用vector存储节点,重构链表;思路二:快慢指针寻找链表中点 + 翻转链表后半段 + 合并链表;

18、链表两数相加:方法一:翻转链表,循环边界判断条件;方法二:辅助栈使用,逆序相加;两种方法都新建节点构成链表;

19、回文链表: 使用 递归方法,很巧妙;利用全局一个指针,多写写;

20、扁平化多级双向链表:多写写;dfs递归方法;

21、std::funtion包装类的使用;(41条消息) C++11 function类模板_c++ function模板_xqs_123的博客-CSDN博客

22、srand(unsigned int)time(NULL) :随机数种子, int ran = random()%100;

23、插入、删除、随机访问都是O(1)的容器:vector和哈希;删除时将最后一个值赋值到删除的下标处;然后再pop_back();

24、最近最少使用缓存:哈希+链表,自己实现链表,该方法多写写,熟练 自己实现链表容器的操作,双端链表;

25、变位词组:使用 排序加哈希 或者 计数法:自建哈希函数,限制于单词长度,学习一下操作方法;

26、字典序排序 规则 : 哈希 + 排序;

27、后缀表达式: 使用栈操作;switch 操作,表达式只能是整形;

28、小行星碰撞:使用vector操作,设置一个变量,判断行星是否爆炸;while条件判断,

29、直方图最大矩形面积:使用单调栈,从左到右记录左边界,从右到左记录右边界;或者一次循环,记录左右边界;二刷的困难题;

30、矩阵中的最大矩形:(二刷题目,没想起来用上题的思路);按层遍历,我单独写一个api接口函数, 就不超时,但是写在一起会超时;官解用的按列遍历 写一起就不超时,不明白为什么?

思路:将矩阵按层遍历,每一行的值相当于上题中的矩形高度,求最大值;

31、往完全二叉树添加节点:使用队列添加节点,左右子树都存在的情况;规定节点的左右孩子均存在时才将它们一起先后压入队列;插入操作时,检查队列头部的节点的左右子节点,插入;

32、二叉树每层的最大值:方法一: dfs、先序遍历,深度与当前vector同样大小就入栈,然后遍历左右子节点,不相等时,比较当前节点和对应深度的已入栈的节点值,取大值;

方法二:bfs、广度优先遍历、使用队列,先入先出的特性、先设置一个变量 = =当前深度的vector大小,循环出栈并将其子节点入栈;

33、二叉树最底层最左边的值:双端队列+bfs; 先右后左; dfs遍历,先左后右;也是设置一个变量,记录当前深度,当大于根节点的深度时就开始赋值;赋值情况只会在叶子节点处;

34、二叉树的右侧视图:bfs、按层遍历好写,记录每一层最后一个节点的值;dfs、深度优先搜索、根结点之后,先右后左,当深度与当前vector大小相同时记录节点值;

35、二叉树剪枝:dfs+后序遍历;先处理左右子节点,再处理根节点;

36、子集的数目:递归解决,回溯解决、选或不选 、、或者枚举;(美丽子集的数目、<递推、动规没看>337周赛);这个题的边界判断,再想一想;78. 子集 - 力扣(LeetCode)

37、执行操作后的最大MEX(数组中缺失的最小非负整数):知识点:同余:若(x - y)mod m == 0;则称 x 与 y 对模m 同余,记作 x≡ y (mod m) ;若为负数,则执行 (xmodm+m);

用map记录同余的个数,map的键值范围肯定为 [ 0 , m - 1]; 对于同处于一个类别的每一个数(可以统计为个数),可以变成 i + v、i + 2v、、对于非负整数,从零开始加,并对m取模,

判断这个类别的数在map中 ,是否能够生成这个数;

38、从根节点到叶子节点的路径数字之和:无返回值的dfs已经能做,有返回值的dfs和bfs还没做;

39、

关键词: