NEETcode-leetcode困难题目思路或伪代码集

leetcode困难题目思路或伪代码集
感觉题目很有意思但是因为实在是太懒了没实验过所以不一定正确。仅是思路。

4. 两个排序数组的中位数
给定两个大小为 m 和 n 的有序数组 nums1 和 nums2 。
请找出这两个有序数组的中位数。要求算法的时间复杂度为 O(log (m+n)) 。

解:
设k=(m+n)/2 b=(m+n)/2有余数 即m+n是否为奇数
设计函数f从两个有序数组的引用中shift掉其两个数组首位中小的一个
循环f k次
若b为true即(m+n)/2有余数
取两个数组首位中小的一个
否则
取结果为两个数组首位平均数
时间复杂度…大概是n/2吧…

10. 正则表达式匹配
给定一个字符串 (s) 和一个字符模式 (p)。实现支持 ‘.’ 和 ‘*’ 的正则表达式匹配。
‘.’ 匹配任意单个字符。
‘*’ 匹配零个或多个前面的元素。
匹配应该覆盖整个字符串 (s) ,而不是部分字符串。
说明:
s 可能为空,且只包含从 a-z 的小写字母。
p 可能为空,且只包含从 a-z 的小写字母,以及字符 . 和 *。

解:
这题真麻烦。
建立链表

.*ab.*cd.e*f
拆分为
.
*
ab
.
*
cd
.
e
*
f

设k=0 k最大限制为s.length-1

遍历链表 设遍历value为ct(checkType)
当ct==.时 k++
当ct==*时 设置flag(给我他妈的翻遍)为ture
else时 当flag为true时 在k后查询ct值 查找不到返回false
当flag为false时 在k位置验证ct值 不匹配返回false
最后返回ture

23. 合并K个排序链表
解:
呃。比较简单的方法是每次取最小重新排一个出来
不使用空间的话……类似于插入排序

25. k个一组翻转链表
说明 :
你的算法只能使用常数的额外空间。
你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。
解:
非常单纯的烧脑题。如果是双向链表就好做不少。和整个链表做倒序没区别。

30. 与所有单词相关联的字串
给定一个字符串 s 和一些长度相同的单词 words。在 s 中找出可以恰好串联 words 中所有单词的子串的起始位置。
注意子串要与 words 中的单词完全匹配,中间不能有其他字符,但不需要考虑 words 中单词串联的顺序。
解:
把words暴力map成一个词典然后indexsof可能会比较快吧。
在s中查询words中每个词的开始和结束位置的数组,然后开始排序吧。

32. 最长有效括号
给定一个只包含 ‘(‘ 和 ‘)’ 的字符串,找出最长的包含有效括号的子串的长度。
解:
(())这种也是有效的所以'()’这么直接查是不行的
(()(()))这种也是有效的
但是最短有效括号肯定是'()’
嗯…正常编程的话这是一个状态回溯栈吧.
先随便假设一个
(()(()))(()这个应该是8个
嗯…我如果把()替换一下替换成2的话
(2(2))(2
嗯…把(2)抹成4试试
(24)(2
2是() 4是(()) 这两个加起来是()(()) 所以满足结合律是6!
(6)(2
把(6)换成8
嗯结果出来了
嗯?还不知道怎么写吗?

37. 解数独
呃,老板 上图
懒得画……
每个格子都做成对象,包含result和mustnotbe数组
mustnotbe都标上横竖方向上所有数字和本九宫格已有的数字
mustnotbe上有数字是8个的就填上剩下那个然后把本九宫格的所有格子对象还有横竖的格子对象都刷新一下
多遍历几遍单解的数独应该就差不多了吧
如果遍历前后没有变化那就随便从canbe里面随便抽一个填填看的递归一层 然后重新运行算法 不行的话return回来再试下一个
_(:3」∠)_

41. 缺失的第一个正数
给定一个未排序的整数数组s,找出其中没有出现的最小的正整数n。
你的算法的时间复杂度应为O(n),并且只能使用常数级别的空间。
解:
快排平均logn了解一下。
来个set。
遍历一遍 遇到正整数n就和s[n-1]的位置互换 然后catch一下 反正大于length的正整数肯定有毛病。

42. 接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。
解:
建立二维数组然后看一下夹缝区域的大小然后加起来
幸好中间没有空隙不然又要出错了

44. 通配符匹配
给定一个字符串 (s) 和一个字符模式 (p) ,实现一个支持 ‘?’ 和 ‘*’ 的通配符匹配。
和10有什么区别吗

45. 跳跃游戏 II
给定一个非负整数数组,你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
4153421341
0000000000
第一步.因为是4所以
0111100000
第二步遍历所有1置位的
0111100000
因为是1
0111100000
因为是5
0111122200
因为是3
0111122200
因为是4
0111122220
第三步遍历所有2置位的
0111122220
因为是4
0111122223
到最后 结束。
最少三步

以上仅为三个小时到凌晨三点的脑力风暴 没有参考任何搜索引擎和答案所以可能完全不正确
下面还有做一些更多的但是感觉因为脑子进水了所以写的很水 就删掉了

发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.