60天带你刷完Leetcode【第3天】656-647

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

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

第三天来啦!这次的题目思路都比较有意思,欢迎评论指正哦!


656

作者:则博

题目:有一个数组A长为n,这时有一个人想从第1位跳到第n位,当跳到第i位时要支付A[i]个coin。如果A[i]==-1,则第i位不能跳。求使得支付coin 数最小的path。(且path要lexicographically最小。)

输入:数组A

输出:使所需coin最少的lexicographically最小的path,如果不存在,输出[]

题 解:很老套的dp,唯一需要注意的是,这道题需要输出的是path,不是所需最小coin的数目。解决方法很简单,在dp进行更新的时候把 next 的 index 记录下来即可。dp 更新的时候index 从小到大,update条件是严格小于,就自动能保证lexicographically最小,所以基本不用担心这条。复杂度:O(n)


655

作者:学渣小编

把一个binary tree用m*n matrix打印出来. Root放中间,左子树和右子树对称地放左右两边。

Input:
    1
   / \
  2   3
   \
    4
Output:
[["", "", "", "1", "", "", ""],
["", "2", "", "", "", "3", ""],
["", "", "4", "", "", "", ""]]

题解:

打印出来的array行数是2^(height - 1)。打印的时候我们会把每个node放在以这个node为root的subtree的横向范围中间。比如打印 root 的时候,我们 把它放在 mid = ( left + right )/2。之后到下一层,我们把root.left放在 left 和 mid -1 中间, 把root.right放在mid+1和right中间。使用level order traversal来打印,可以做一个structure,里面包含 {node, left, right},每次把pop当前node打印好后塞入{node.left, left, mid-1}和{node.right,mid+1,right}


654

作者:学酥小编

题目:有一种binary tree叫maximum binary tree 可以从一串代表TreeNode value的数字中构建。规则如下: 比如input为[3,2,1,6,0,5],那么root的value为最大数6,left subtree为其左边的数3,2,1构建的maximum tree,right subtree为其右边的数0,5构建的maximum tree。最后构造的树为
      6
    /    \
  3      5
   \      /
    2   0   
      \
       1
题解:可以按照规则直接recursively构造,每一次recursive call找到最大数,设为node,再分别recurse on左右。running time O(n^2)

Better: 尝试loop一遍input数组看能不能把树构造出来。从左往右loop,下一个数代表的node一定在右边,我们需要判断的是下一个数是当前的parent还是child。设定当前数对应node为root,如果下一个数大,那一定是parent,当前root为parent的left,设定parent为新的root;如果下一个数小,那一定是child,往右traverse,如果没有比下一个数小的数,那直接作为最右child,如果有则与之交换使其成为这下一个数的left child(这个case在上面例子的6 0 5部分可以看到)。running time O(n) best (数组sorted in ascending order), O(n^2) worst (数组sorted in descending order)


653

作者:学酥小编

题目:在一棵bst上找2sum。比如给一个sum7,找有没有value和为7的两个node在一个bst里

题解:可以用in order traversal从bst得到sorted array,在这个array上跑2sum。也可以用hash table记录traverse过程中的node value,看有没有sum-value已经存在map里了。这两种办法running time都是O(n)但都用了O(n) extra space。

实际上我们可以直接在bst上模拟2sum。用两个stack分别记录从root一路向左subtree走和从root一路向右subtree走。以这两个stack顶的数作为left和right,如果sum大于要找的,那么要把right更新为第一个较之小的数,对于bst是right 对应的node的左子树的most right child;如果sum小于要找的,那么要把left更新为第一个较之大的数,对于bst是left对应的node的右子树的most left child。而找到most left/right child可以使用上述两个stack。这样space是O(log n)或O(tree height)。


652

作者:学酥小编

题目:求一个binary tree的完全一致的(duplicate)subtree,要求返回所有duplicate subtree的root

题解:关键是一个把subtree信息收集到root再以这种信息作为key来记录出现次数并判断是否duplicate。所以采用post-order traverse,把root对应subtree的所有node的value都记录下来作为key。如果traverse过程中key已存在则当前root对应的subtree有duplicate。running time O(n)


651

作者:学渣小编

题目:有一种特殊的打印机可以打印字符串。有4个按键可以使用:

Key 1: 打印1个'A'  

Key 2:选中屏幕上所有character.

Key 3:把选中的copy到buffer

Key 4: 把buffer打印出来

现在可以做n种操作,问最多能打印多少字母A?

题解:用dp, 定义一个dp[n+1]数组,赋值为0-n,为只使用key 1打印出的个数。dp[i] = max (dp[i], dp[j] * dp[i-j-1])  for all 1 < j <= i-3, 0 <  i < n, 最后打印dp[n]。Running time O(n^2)


650

作者:学酥小编

题目:用一个键盘打印只包含A的字符串,而这个键盘只有两个键,一个copy可以copy整个字符串,一个paste可以paste所有copy的字符串,copy了新的内容就会把旧的内容overwrite,copy的内容可以一直用来paste。一开始有一个A,问最少几次按键就可以得到整个字符串。

题解:策略是尽量copy paste多一点字符, 也就是把原字符串分成尽量少的chunk。最差情况是每个字母都是一个chunk每次copy paste一个字母。因而从i=2开始loop,每次看长度能不能被整除也就是能不能分成i个chunk,如果能看能被分成几个chunk,有几个chunk就要几次按键(copy一次chunk,paste出剩下的n-1个chunk)。然后在一个chunk的长度上继续循环。

Running time: O(n) worst case (质数的情况,分成的chunk只能length为1)


649

作者:则博

题目:有一队参议员分属两个阵营, i.e. "Radiant" 和 "Dire",并排成一排,依次进行投票。每个参议员投票时可以选择 "Ban" 掉对方阵营一名参议员的投票权,这样被 "Ban" 参议员相当于被踢出了队列。投票按队列顺序依次进行,一遍之后再从头继续(已经被踢掉的参议员不能加入)。当一个阵营的参议员被全部踢出队列时,另一方胜利。初始状态由一个字符串组成,且该字符串只包含'R','D',代表每个参议员在队列中的位置,及其所属阵营。当双方都采取最优策略进行投票时,求最终的胜利方。

输入:字符串  i.g. "RRDRD"

输出:胜者阵营:"Radiant" or "Dire"

题解:最优策略很显然,每个人"Ban"对方阵营中与自己最近的下一个Senaor。这样我们可以用两个队列 qR, qD(分别存有两个阵营的参议员)进行模拟,当轮到某个人进行投票时,这个人从队前排到队末,对方阵营的队前被踢掉。为了保持原来的次序,队列中存放着每个参议员在原队列中的位置(index),每次投完票,这个index增加原序列的length,这样他就自动排到了所有人之后。每次只要比较两个队列的队前大小就可判断应该轮到那边进行投票了。时间复杂度: 每个人最多进出队列两次,所以是O(n). 我们发现 n <= 10000, 所以n^2 <= 1E8, 所以完全不用考虑overflow.


#include<cassert>
class Solution {
public:
  string predictPartyVictory(string senate) {
      int n = (int)senate.size();
      assert(n>0);
      queue<int> qR,qD;
      for(int i=0;i<n;++i){
          if(senate[i]=='R') qR.push(i);
          else qD.push(i);
      }
      while(!qR.empty() && !qD.empty()){
          if(qR.front() < qD.front()){
              qD.pop();
              qR.push(qR.front()+n);
              qR.pop();
          }
          else{
              qR.pop();
              qD.push(qD.front()+n);
              qD.pop();
          }
      }
      return qR.empty()? "Dire":"Radiant";
  }
};



648

作者:学酥小编

题目:给一句话,以及一些word代表可能的前缀,让你把句子中的单词换成前缀,如果那个单词是以前缀开头的话。如果有多个前缀可以替换,选择最短的那个。比如前缀有["cat", "bat", "rat"]句子是"the cattle was rattled by the battery",那么比如可以把cattle换成cat,最后Output: "the cat was rat by the bat"

题解:典型的prefix search。可以根据前缀的单词建trie然后把句子里的每个词在tree里面找,替换成第一个找到的前缀。关于trie有专门的题目,在这里不赘叙了。


647

作者:则博

题目:Palindromic Substrings

计算给定string 的Palindromic substring 的个数

输入:string S, 长度不超过1000

输出:Palindromic substring 的个数

思路:很无脑的一个二维dp,dp[i][j] = 1 if S.substr(i, j-i) 是Palindrom;= 0 otherwise,且 i < j。这样只要把所有的1统计一遍就够了。

复杂度: O(n^2)


646

作者:学酥小编

题目:给出一列区间,比如[[1,2], [2,3], [3,4]],如果两个区间头尾差1或以上,则认为两个区间可以连起来形成一个区间链。比如[1,2]和[3,4]。求最长的区间链。

题解:根据区间的头排序之后,根据能不能形成链作为subsequence是否increasing的判据,run  Longest Increasing Subsequence。这是一个经典的DP问题。

Running time: O(n^2)


查看所有题目:

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



【长按关注北美加群小助手Jogchat.com】



阅读 5777

微信扫一扫
关注该公众号