60天带你刷完Leetcode【第1天】676-667

2017-09-21 CS学渣、学酥小编 北美加群小助手Jogchat 北美加群小助手Jogchat

每天30分钟 关注【北美加群小助手Jogchat.com】60天就能刷完Leetcode,学渣学酥也能跻身一线公司、升职加薪、当上总经理、出任CEO、迎娶白富美、从此走上人生巅峰!想想还有点小激动😏

初次见面,请多关照!

676.

作者(CS学酥小编)

题目:设计一个magic dictionary以实现一个特殊的search功能:如果一个单词换掉一个字母之后能在这个dictionary里,那么认为这个单词在这个字典里。要求实现两个funcitons: buildDict and search, 分别是construct一个data structure(input为a list of words)和实现上述的特殊search功能。

Example:

Input: buildDict(["hello", "leetcode"]), Output: Null
Input: search("hello"), Output: False
Input: search("hhllo"), Output: True
Input: search("hell"), Output: False
Input: search("leetcoded"), Output: False


思路

Brute Force: buildDict就把给的words作为key存在map里;search就把每个字母换成其他25个字母看在不在map里。running time: word length * 25 * word length(map的access time)

Better: 省时间那必须减少查找时间,无法知道哪个字母被替换但可以仅仅判断被替换的那个字母是不是和字典里的词对应位置的字母一样。这样running time缩小为25之1。为此,可以构建特殊的map。key为word去掉一个字母,value为那个字母以及在word里的位置。

675.

作者(CS学渣小编)


题目: 砍树。Matrix 里 0 代表 obstacle, 1代表可以走的ground, >1的都是树。从(0,0)开始走。砍的时候要从最低的树开始砍,问最少多少步砍完。

Input:      
[
[1,2,3],
[0,0,0],
[7,6,5]
]
Output: -1  不能砍完回复-1

Input:
[
[2,3,4],
[0,0,5],
[8,7,6]
]
Output: 6  最短6步砍完 2->3->4->5->6->7->8

题解:

Step 1. 每个tree搞成一个tuple来represent: {height[i][j], i, j}. 然后 sort base on tree height in ascending order.

Step 2.loop 这个sorted list, 然后对于height上相邻的两颗数, 我们想得到它们之间的step数(call step3写的function)。把这些step加起来就是题目答案。loop的running time是O(mxn)

Step 3.怎么得到相邻两颗数直接的距离呢,我们写一个help function, 这个function是用BSF找两点之间最短距离。如果找不到返回-1. Running time是 O(mxn)

总体running time O(mxn) x O(mxn)


674.

作者: CS学酥小编

题目:Longest Continuous Increasing Subsequence。求最长增序列的长度,注意subsequence是连续的

Loop一遍 keep 当前increasing subsequence的length和global的length(就是要return的value)并更新就好

O(n)


673.

作者:CS学渣小编

题目:Longest Increasing Subsequence的个数。一个数字数组,找最长subsequence的个数,注意subsequence是可以选不相邻的数的哦。

Input: [1,3,5,4,7] which is num[] Output:2

two longest increasing subsequence are [1, 3, 4, 7] and [1, 3, 5, 7]

题解:用dp, 存两个array,

一个len[i]: 用来存以num[i]结尾的最长的subsequence的length.

一个count[i] 用来存以num[i]结尾的最长的subsequence的个数.

Outer loop:从i=0到 i = num.length loop一遍,//意思是每多走一个i,保证i的 len[i], count[i]都fill了。

Inner loop 在i 的loop 中套一个j的loop, j=0 到 j=i-1 loop一遍,通过 len[0] ~len[i-1] 来 build len[i]以及通过 count[0]~count[i-1]来build count[i].

最后答案是最大len[i]对应的所有count[i]全部加起来。


672.

作者:CS学酥小编

题目:有n个灯,开始都亮着,然后熊孩子按了m次电钮,问有多少种可能灯on/off的可能。一共四个电钮分别可以:Flip all the lights, Flip lights with even numbers, Flip lights with odd numbers, Flip lights with (3k + 1) numbers, k = 0, 1, 2, … (就是编号为3,6,9等的灯啦)

这个题颇似重点中学入学测验。关键是看出来周期性,或者说按m次按钮肯定能等效于有限种类的操作。实验发现按下按钮1并且按下按钮2等效于按下按钮3, 按下1,3等效于按下2, 按下2,3等效于按下1,按下两个相同的按钮等于没按。所以只有以下8种等效操作。不按、按下1,按下2,按下3、按下4、按下1,4、按下2,4、按下3,4。再看灯的数量,发现只有灯数大于2按钮4才能发挥作用。进一步,只要n>2 && m>2的情况,8种case都是可能的。(如果n>2&&m=2, 出不来按下4)。根据规律分情况return即可

Running time: o(1)


671.

作者:CS学渣小编

题目:一个二叉树,每个node有0或者2个children,children的数值都会>=parent的值 。问这个树中第二大的值是什么?

Input:
   2
  / \
 2   5
    / \
   5   7

Output: 5第二大的值为5

Input:
   2
  / \
 2   2

Output: -1没有第二大的值,返回-1

题解:

记录两个global variable, 最小值 和 次小值。

写一个recursion helper function. Take 一个root node。

直接上代码

Gloabal minVal, secondMinVal

private void recursiveHelper(TreeNode root){
       if (root.val != minVal){
           secondMinVal = Math.min(second, root.val);
           return;
       }
       if (root.left != null)
           recursiveHelper(root.left);
       if (root.right != null)
           recursiveHelper(root.right);
   }

670.

作者:CS学酥小编

题目:一个数,可以交换一次两个digit,求交换后的最大数。比如2736换7跟2得到7236。

Brute force:全部可能试一遍,O(n)

Better:明显有不用试的,就是大的数在高位,那换了反而小,所以可以从高位到低位对每个数找第一个比他大的并交换(只要找到就可以停)。不过还是O(n)

Even better: instead of在数组里找,可以看比当前digit大的digit是不是在低位出现。这样最多找8次因为只有9个digit,但为此要预先存一个以digit为index,出现的最高位为value的数组。running time O(n)+O(n)*8 = O(n). extra space O(9)=O(1)



669.

作者:CS学渣小编

题目:binary search tree, 给定一个range[L R]按照这个range把这个tree减枝。

Example 1:
Input:
   3
  / \
 0   4
  \
   2
  /
 1

 L = 1
 R = 3

Output:
     3
    /
  2   
 /
1


题解:写一个recursive function

trimTree(root)

  1. Root.left.val<L, 减掉左分支(same as return trimTree(root.right))

  2. Root.right.val>R, 减掉左分支(same as return trimTree(root.left))

  3. 如果上面两个条件都不满足:

       root.left = trimTree(root.left, L, R);
       root.right = trimTree(root.right, L, R);
       return root;

Running time: O(n), n 为 node的个数


668.

作者:CS学酥小编

题目:给出乘法表的长、宽,找出这个表里面的kth element。

比如2*3的乘法表第一行是1*1,1*2,1*3,第二行是2*1,2*2,2*3

Brute force:O(mn)建表,O(mn*log(mn))sort

Masterpiece: 搜索问题用binary search,binary search的精髓是drop half.只要能找出可以drop的half,就不用sort(所以别把常见情况的见到sort用binary sort和binary sort requires array sorted混淆)。那么如何能找到可以drop的half/值得继续搜索的half呢。

注意乘法表的每一行都是sort的,所以我们可以算出来某一个数字是乘法表里的第几大:逐行除以行号得到列号,再累加起来,比如2在3*2乘法表里是第3+2大的数。(当然2也可以是第4大的数,这个细节下面会讲)。这样我们可以对一个数判断在乘法表里这个数是小于第k个数还是大于第k个数,也就是说,可以对乘法表做binary search。

但是,在运行binary search的过程中,会产生mid(mid = (high + low) / 2)而这个mid不一定是乘法表里的数,算法会不会return一个不在表里的数呢?一般而言mid是index的mid,而这里的mid直接是对应的数了。不过这不是问题,因为mid不是第kth大的数,所以不会被return。听上去像废话,但是亲自试几个例子之后相信你能确定这个算法是对的。同样的,因为算法一定能return kth,不会出现之前2出现在两个位置的问题。

算法对整个表binary search,每次判断是大于还是小于kth number要看每一行。Running time O(log(mn)*m)


667.

作者:CS学渣小编

题目:

给一个n, 代表长度的array [1 to n], 和一个数k.

返回一个array的重新排列方式,使得 [|a1 - a2|, |a2 - a3|, |a3 - a4|, ... , |an-1 - an|]有k个不同的数。

Input: n = 3, k = 2
Output: [1, 3, 2]

|1-3| =2, |3-2|=1, 两个不同,符合 k=2.

题解:

我们来construct 这样k个不同差值的array.

1-k可以construct出k-1个不同差值的排列,如下:

1, k, 2, k-1, 3, k-2, 4

差:k-1, k-2, k-3, k-4, k-5, k-6 …

Base on k的奇偶性质,剩下n-k个数按照递增或者递减的顺序来排列, 它们差值都是1

举个栗子:

k为偶数,最后递减;k= 2, n = 5, 这样排:1, 5, 4, 3, 2  

k为奇数,最后递赠;k= 3, n = 5, 这样排:1, 5, 2, 3, 4

Running time: O(n)


长按扫码关注吧!

 
















阅读

微信扫一扫
关注该公众号