leetcode 中等题(部分二)

Miao先生
Miao先生
Miao先生
3
文章
0
评论
2020-04-1803:05:00 评论 1,319 4887字
摘要

小编为大家整理了一些leetcode题希望对大家有帮助! 

Minimum Size Subarray Sum

(给一个 n 个正数的数组和一个正整数 s,找到和大于等于 s 的最小长度的子数组,如果不存在,返回0) 举例说:给一个数组 [2,3,1,2,4,3] and s=7. 返回 [4,3]

(注意:子数组,是中间不能跳数的,只是整个数组的中间子集)

leetcode 中等题(部分二)

3Sum

(给一个n个整数的数组S,是否 S 里面有3个元素 a, b, c 使得 a + b+c=0,找到数组中所有唯一的三元组,使得其和为0) 这里我第一反应还是先排序,然后,用夹逼的方法去找结果

leetcode 中等题(部分二)

Largest Number

(给一组正整数,排列他们中所有的数,使整个数组形成最大的数,用字符串示出来最后的结果)

(这个题其实和AMCAT上的题有点类似)

leetcode 中等题(部分二)

Longest Substring Without Repeating Characters (给一个字符串,找出最长的不含重复元素的子串)

leetcode 中等题(部分二)

Maximum Product Subarray (在一个数组里面找到连续的一串子数组,使得他们相乘有最大的乘积)

leetcode 中等题(部分二)

Wiggle Sort ii(这个题目超级的重要,有好几个轮子在里面) (给一个未排序的数组,以nums[0]<nums[1]>nums[2]<nums[3]的方式排列)

Example: (1) Given nums = [1,5,1,1,6,4],one possible answer is [1,4,1,5,1,6] (2) Given nums = [1,3,2,2,3,1],one possible answer is [2,3,1,3,1,2]

leetcode 中等题(部分二)

1、字符串 (1)Is Subsequence(子串问题) 给一个字符串s 和 t,判断是否s 是 t 的子串:

【注意 t 可能是一个非常长的字符串,s 是一个比较短的字符串】 而子串是不改变字母的相对顺序,但是从母串中减去若干个字母形参的串。

leetcode 中等题(部分二)

(2)Additive Number 一个 Additive Number 是一个这样的字符串,在字符串里面前面的数字可以相加组成后面的数字: "112358" 是一个 additive number,因为这些数字可以形成一个递增的序列:1,1,2,3,5,8 "199100199" 也是一个 additive number,因为这些数字可以形成一个递增的序列:1,99,100,199 属于 additive 的数字中,不能含有0 比如:1,2,03 or 1,02,3 都是无效的。

leetcode 中等题(部分二)

stol:将字符串转换为 long 型

(3)Word Break [ 给一个字符串s和一个词典 dict,决定是否s能被拆分为 被空格分隔的一到多个序列 ] [ 精确到每个数的下标 ]

leetcode 中等题(部分二)

(4)Multiply Strings (字符串相乘:Given two numbers represented as strings, return multiplication of the numbers as a string.) (首先两个数相乘,长度最大为两个数长度相加,所以结果集的长度初始化为两个长度的和)

leetcode 中等题(部分二)

2、二叉树 (1)给一棵二叉查找树,写一个函数 kthSmallest 来找到第k小的元素: 注意,如果一棵二叉查找树被频繁(修改/删除),你需要找到第K小的元素

(这道题的老方法是用节点计数加中序遍历,但是这道题的新方法是用栈来记录中间值) (这个题的难点在于栈的基本元素是指针,而不是指针对应的值)

leetcode 中等题(部分二)

(2)Flatten Binary Tree to Linked List (给一棵二叉树,将它原地压扁成一棵单链表,这个地方是用前序遍历的方式)

// 我暂时想到的方式是,在前序遍历的过程中,用数组将中间的过程存起来,然后再输出;红色部分为前序遍历的代码,然后 vector 数组为记录中间的值。

leetcode 中等题(部分二)

这种方法调用了额外的空间,肯定是不好的,下面是进行原地的旋转和递归调用:

leetcode 中等题(部分二)

(3)Insertion Sort List (这里要注意,如果涉及到链表相关的题目,需要返回一个头节点,最好重新设一个节点)

leetcode 中等题(部分二)

(4)Lowest Common Ancestor of a Binary Tree(这种题看上去挺简单,但是其实,应用的场景很多) // 对高度进行降维,分别降到 左边 和 右边。

leetcode 中等题(部分二)

(5)Count Complete Tree Nodes (给一棵完全二叉树,统计完全二叉树的结点)

(在一个完全二叉树的每一层中,除了可能的最后一层外,其他的都是完全填满的,而且最后一层(h 层)的结点都是尽可能左移的)

(它能拥有1到2^h个结点)最后求有多少个结点

(通过二分的方法来算就好了) (父结点是第0层,依次往下数)

leetcode 中等题(部分二)

3、匹配题(1)Generate Parentheses (给你 n 对括弧,写一个功能来产生所有括弧的合理组合)

(不管是怎么样的组合,只要遵循先左再右的方式就可以了。同时把左右的数量保持一致就行) (这种解题模式很重要)

leetcode 中等题(部分二)

(2)Combination Sum III (给一个目标值 n,然后找到k个数字的和为n的所有组合,所有数都是从[1 2 3 4 5 6 7 8 9])

这个题我觉得和上面这个题的解决方法很相似了,因为都是可以用深度递归的方式去做。

(有两种解法,一种是先入后出法,入了之后,所有与它有关的解都应该能够被找出来,而出来了之后,的所有解将不包含它;第二种是标记法,如果集合不大,就用一维的布尔数组进行标记凡是标记过的,都不进行遍历,而没有被标记的元素,依次进行遍历。)

leetcode 中等题(部分二)

leetcode 中等题(部分二)

Combinations (Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.) (这种模式比较重要,很多的题目,只要通过这种模式,都能够做出来)

leetcode 中等题(部分二)

(3)Single Number ii (这个题目,考的比较多,因为数值题是最容易考的,一组数,里面除了一个数只出现了1次以外,其他的数都各自出现了3次,找出这个数)。 这道题因为不能用数组

leetcode 中等题(部分二)

(4)Search Insert Position [Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.] (二分查找的唯一准则,就是进行划分时,一定是将真正的答案留下,而不是被划走了)

leetcode 中等题(部分二)

(5)Maximal Square (给予一个2D的二进制矩阵,填满0和1,找到包含1的最大的正方形,然后返回它的面积)

leetcode 中等题(部分二)

4、新题型(1)Flatten Nested List iterator 这种题应该在很多应用场景中都会出现,给一个嵌套的数字的列表,用一个迭代器来压扁它: 其中,每一个元素要么是一个整数,要么是一个嵌套着整数的列表.

Example 1:Given the list [[1,1],2,[1,1]]. 最后变为 [1,1,2,1,1] Example 2:Given the list [1,[4,[6]]]. 最后变为 [1,[4,[6]]]

leetcode 中等题(部分二)

(2)Subsets ii (求子集的题,应该还是比较容易出) (给一个可能包含重复整数的集合,返回它不包含重复子集的结合)

If nums = [1,2,2], a solution is: [ [2], [1], [1,2,2], [2,2], [1,2], [] ] (思考方式:不能包含重复子集,那么也就是说如果有几个相同的数重复出现,那么需要跳过)

leetcode 中等题(部分二)

(3)Range Sum Query - Mutable (这是一道设计题,设计功能的实现方式,虽然有很多种实现的方式,但是如果考虑到性能,就没法实现) (给一个整数数组,返回下标从 i 到 j 的所有元素的和)

update(i,val) 函数将下标为 i 的元素修改为 val.

(4)Add and Search Word - Data structure design(这个题要用到前缀树) (这也是一道设计题,支持两个功能:addWord(word);search(word);) void addWord(word) bool search(word)

支持通配符".",这个通配符可以代表任何一个字母;这里与字母相关的,是前缀树 前缀树有个基本的节点:TrieNode

leetcode 中等题(部分二)

leetcode 中等题(部分二)

(5)Basic Calculator ii (实现一个基本的计算器来计算一个简单的字符串表达式) (这个字符串表达式中只包含非负的整数,+、-、*、/ 运算符,以及空格)

leetcode 中等题(部分二)

leetcode 中等题(部分二)

5、数学推理题(1)给你一个单项链表,然后判断是否有环,如果有环,返回环的起点:

leetcode 中等题(部分二)

(2)Water and Jug Problem(有两个不同容量的壶,然后要倒出指定容量的水出来) **Example 1: ** Input: x = 3, y = 5, z = 4 Output: True Example 2: Input: x = 2, y = 6, z = 5 Output: False

两个瓶子可能量出的水是两个瓶子容量最大公约数的倍数。所以只要判断z是否可以被x,y的最大公约数整除即可。 造轮子:求两个数的公约数

leetcode 中等题(部分二)

(3)Decode Ways (一条包含从"A~Z" 字母的信息,通过以下的 mapping 方式进行编码) "A" -> 1 "B" -> 2 ... "Z" -> 26

(给你一个字符串,来判断有多少种编码方式) (主要是对0的处理,以及)

leetcode 中等题(部分二)

(4)Permutation Sequence (The set [1,2,3,…,n] contains a total of n! unique permutations.) By listing and labeling all of the permutations in order, We get the following sequence (ie, for n = 3): "123" "132" "213" "231" "312" "321" Given n and k, return the kth permutation sequence.

leetcode 中等题(部分二)

6、动态规划题型

(1)Triangle 【给一个三角形,找到里面从top到bottom和最小的路径,每一步你都可以移动到下一行的相邻的数字】

leetcode 中等题(部分二)

(2)Jump Game 【给一组正整数的数组,你被初始化于一个数组头节点的位置,数组中的每一个元素都代表你能跳跃的最大的距离,判断是否能从头节点到末节点】

方法就是只要判断出能到的位置的最大值大于等于最后一个数就行了

leetcode 中等题(部分二)

(3)Gas Station (环形的数据结构,总是相对比较难一点)

[围绕着一个圆形的路径,有N个加油站,每个加油站的油的量为gas[i],你有一个无限制油量大小的油桶,并且从站i 到 下一个站i+1,需要花费cost[i],你以空油量从任何一个站加油出发,问能否围绕所有油站一次]

(首先,如果能绕一个圈,那么总存量为正数,否者为负数,在为正数的情况下,要去找那个起点,那么,就从0开始,然后,找到单段存量为负数的位置,从下一个开始就好。

leetcode 中等题(部分二)

(4)Coin Change [这个题目比较重要] [给你不同面额的足量硬币以及一个钱的总额,写一个函数来计算你需要的最少的硬币来构成指定的面额,如果该面额数不能被任何面额的硬币构成,返回-1]

Example 1: coins = [1,2,5], amount = 11 return 3(11 = 5+5+1) Example 2: coins = [2], amount = 3 return -1

leetcode 中等题(部分二)

(5)Decode Ways (一条包含从"A~Z" 字母的信息,通过以下的 mapping 方式进行编码) (这个题,最麻烦的是,对0的处理) "A" -> 1 "B" -> 2 ... "Z" -> 26 (给你一个字符串,来判断有多少种编码方式)

leetcode 中等题(部分二)

(6)Word Ladder (给两个单词(begin_word to end_word)和一个字典词序列,找到从起点到终点转换的最短路径,每次转换一个单词)

Given: beginWord = "hit" endWord = "cog" wordList = ["hot","dot","dog","lot","log"] As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog", return its length 5. (这里 unordered_set 用的是哈希表,所以用inset都是ok的)

leetcode 中等题(部分二)

作者:我是小居居

来源:简书

文均已和作者授权,如转载请与作者联系。
  • 我的微信公众号
  • 微信扫一扫
  • weinxin
  • 我的微信公众号
  • 微信扫一扫
  • weinxin
匿名

发表评论

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: