60天带你刷完Leetcode【第2天】666-657

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


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


这次的题目中有一道很难,jogchat.com小助手团队特别请到竞赛大神亲笔撰写~。大家继续加油刷题呦


666

作者:学酥小编

题目:给一个三位数list,每个数代表一个tree node,百位数代表depth,十位数代表在当前深度的position,个位数代表value。list是sort的。比如下面这棵树的3由323代表。

          1
        /   \
       3     2
      / \      \  
     5   3     9

解: 正常的题目用TreeNode这种结构关键是可以找到children在哪(next pointer)并traverse。这里三位数之间可以用depth确定是不是在一层,然后如果在下一层position又和上一层node position有*2或*2+1的关系,那么这个node是children,可以traverse on that。

Follow-up:如果乱序没有sort,那可以建一个map,key是height和position,value是node value。这样避免需要在整个list里面找child。

Running time O(n)


665

作者:学渣小编

题 目:给一个n个数的array, 问能不能改变最多一个element, 使得这个array呈现没有decreasing的状态f array[i] <= array[i + 1] holds for every i (1 <= i < n).

Input: [4,2,3] Output: True 可以把4改成1,就是[1,2,3]

Input: [4,2,1] Output: False. 做不到.

题解:

记 录一个count,用来存需要修改数的个数。loop一遍这个array,如果nums[i-1] > nums[i]。如果nums[i-1]为起始位置,我们可以缩小它,使得nums[0]<=nums[1]。如果nums[i-2]> nums[i]我们只能改nums[i]的值(改成nums[i-1]的值), 使得nums[i-2]<=nums[i] && nums[i-1]<=nums[i],其余情况可以改把nums[i-1]改成nums[i]的值来达到目的。


664

作者:则博

题目:有一台printer可以打印字符串,一次只能打一种letter,可以从任意起始位置打印到任意结束位置。比如aaccb可以先打一次aaa再打一次bb成为aaabb,再最后从位置2到位置3打一次cc(打印机可以覆盖原来的letter)。求打印一个字符串的最小次数。

题解:

定 义状态dp[l][r]为从l到r的最小打印次数。每打印一次,就会产生新的状态,比如从l打印k会产生dp[l][k]和dp[k+1][r]两个新的 状态。这样可以对所有可能的l,r,找出新的状态,recurse on新的状态,再取return结果的最小值就OK了。running time O(n^3)。因为printer只能打一种letter,所以上面的例子只需要看i和l对应letter相等的情况。用公式表达:

For all l and r, find min dp[l][r], where

dp[l][r] = min_k {dp[l][k] + dp[k+1][r]}, for all k such that dp[k]==dp[l].

但是,这种方法实际是错的,leetcode讨论区都是这种方法,恰好能过而已。原因如下:

对[l, r) 这样一个区间的print,不仅跟区间位置有关,还跟上一次print之后的状态有关。例如,如果上一次[l, r)已经被 print 上了 'a', 这样这个区间的状态就跟初始不同了,因为我们不用重新 print 区间里面的 'a' 了。也就是说没法用一个二维数组来标记状态并且进行递归。

我的思路是用一个三维dp:

dp[i][l][r] := the minimum prints need to cover the interval [l, r) if this interval has been printed by the ith letter in a-z,

ch[i] := (char)('a' + i - 1) (i == 0 表示还没有被print过)

这样我们要考虑 index j, s.t. s[j] == s[l] || s[j] == ch[i], 然后进行递归,并且要考虑区间里面的 ch[i] 是不用被重新print的,可以跳过。此题最初以竞赛题出现时高分选手的答案和我们一致。

具体解法如下:

class Solution {

   int dp [27][105][105], pos[27][105];

   string st;

   int n;

   int cnt(int ic,int i,int j){

       if(i>j) return 0;

       if(dp[ic][i][j] >= 0) return dp[ic][i][j];

       if(ic == (int)(st[i]-'a' + 1)) return dp[ic][i][j] = cnt(ic,i+1,j);

       if(ic == (int)(st[j]-'a' + 1)) return dp[ic][i][j] = cnt(ic,i,j-1);

       int kc = (int)(st[i]-'a' + 1), k = min(pos[kc][i],  pos[ic][i]);

       dp[ic][i][j] = n;

       while(true){

           k = min(j+1, k);

           dp[ic][i][j] = min(dp[ic][i][j], 1 + cnt(kc,i+1,k-1) + cnt(ic,k+1,j));

           if(k >= j) break;

           k = min(pos[kc][k],  pos[ic][k]);

       }

       return dp[ic][i][j];

   }

public:

   int strangePrinter(string s) {

       if(s.empty()) return 0;

       st += s[0];

       for(int i=1;i<s.size();++i) if(s[i]!=s[i-1]) st+=s[i];

       n = st.size();

       memset(dp,-1,sizeof(dp));

       memset(pos,0,sizeof(pos));

       map<char,int> mp;

       for(int i=0;i<27;++i) pos[i][n-1] = n;

       for(int j=n-2;j>=0;--j) for(int i=0;i<27;++i){

           if(i == (int)(st[j+1]- 'a' + 1)) pos[i][j] = j+1;

           else pos[i][j] = pos[i][j+1];

       }

       return cnt(0,0,n-1);

   }

};

复杂度: 最坏 O(27*n^3), 平均 O(n^3), 考虑到规模不超过100,这样27*n^3 < 10^8,这个在比赛中也是可以被接受的。


663

作者:学酥小编

题目:给一个binary tree,判断是否能够去掉一个edge使得产生的两棵树的value的sum相等。比如   
   5
  / \
 10 10
   /  \
  2   3

可以分成两个sum相同的subtree
   5    10   
  /      /   \
 10   2    3
题 解:要判断能不能分,就要看去掉的edge所连接的subtree是不是sum to 整个树sum的一半。所以可以先traverse一遍,收集subtree的sum到对应root上并得到total sum,再traverse第二遍看有没有哪个node代表的subtree的sum是total的一半。Running time O(n)

Follow-up: 如果不能修改node,那就用一个map来keep sum,extra space O(n)


662

作者:学酥小编

题目:求binary tree max width,width定义为某一level从最左到最右的node个数,包括中间的null,比如

          1
        /   \
       3     2
      / \     \  
     5   3     9 ← max width = 4

解:level order traversal。trick是queue要把null也要包括进来,因为中间是null的情况是算在width里的。不过要把最前最后的null去掉 以保证是node开头结尾的,为此要用deque以取得从两端pop都是O(1)的efficiency。这样每一层开始时的queue的size就是这 一层的max width


661

作者:学渣小编

题目:用一个matrix表示一个image,对这个image做smothing的操作,即用一个数(pixel)周围的数的平均值代替这个数。

解法:straightfoward做循环。

Follow-up:此种简单操作其实在image processing和computer vision领域有很多应用且有奇效。


660

作者:学酥小编

题目:从所有整数中去掉带9的数字,比如9, 19, 29,求这些个整数中的第n个。

解法:实际上就是逢9进位,比如1到8然后进位到10(跳过9),这和二进制逢2进位十进位逢10进位都是一样的。所以从高位开始用%9取当前digit再不断/9去掉当前digit。

Running time: O(number of digits)


659.

作者:学渣小编

题目:给一个数组,把它分割诚consecutive sequences,要求每个sequence的长度大于等于三。

example1:

Input: [1,2,3,3,4,5]
Output: True
Explanation:
You can split them into two consecutive subsequences :
1, 2, 3
3, 4, 5

example2:

Input: [1,2,3,3,4,4,5,5]
Output: True
Explanation:
You can split them into two consecutive subsequences :
1, 2, 3, 4, 5
3, 4, 5

example3:

Input: [1,2,3,4,4,5]
Output: False


题解:

用贪心,记录一个array,用来存相同数的frequency。take example 1, [1,2,3,3,4,5] -> [1,1,2,1,1], 下面开始选组合,我们只选count是 mono increasing的数,这里选count为 1,1,2的。所以[1,2,3] 为一组。为什么我们不选count 2后面那个为count 1的呢?因为,如果选了count 2就会剩下一个落单了。选完之后count变为[0,0,1,1,1],所以剩下一组选[3,4,5]. Take example [1,2,3,3,4,4,5,5]
->[1,1,2,2,2] 选count [1,1,2,2,2]。[1,2,3,4,5]。剩下count [0,0,1,1,1,],选 [3,4,5]剩返回true. 【此处谢谢欣宇小盆友修正】


658

作者:学酥小编

题目:给一个sorted list 和一个target number 求list里面和target number大小最接近的k个element

解:直接binary search找到closet target 再往左往右一共找k个,注意一下左或右没有element的情况就好。


657

作者:学酥小编

题目:用U D L R 分别代表给robot行走的指令 up down left 和right。现有一个由这些指令组成的字符串,比如RUDUL,要求判断robot根据指令行走后能否回到原点。

解:Straightforward。keep一个左右移动的flag 一个上下移动的flag 顺序读入指令flip对应flag 最后判断是否有flip即可

Running time O(n)


查看所有题目:

打开Wechat微信->Contacts[联系人]->Official Accounts[公众号]->北美加群小助手Jogchat->每日播报->Leetcode总入口


 长按扫码关注吧!

 


阅读 5777

微信扫一扫
关注该公众号