📣 Back to School开学季 - VIP通行证5折优惠!蓝莓、Offer多多同步优惠
查看: 1131| 回复: 1
跳转到指定楼层
上一主题 下一主题
收起左侧

[Leetcode] 339. Nested List Weight Sum 递归的base case是什么

全局:

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
大家好,这道题不好debug,因为好多写好的api
有一件事不明,就是如果输入是[[1,1],2,[ ]]的时候,这个递归的程序怎样处理空list的?返回的是null吗?
进而,这个recursion的base case是什么? 貌似不像是树那样if(root==null) return 逻辑:
  1. /**
  2. * // This is the interface that allows for creating nested lists.
  3. * // You should not implement it, or speculate about its implementation

  4. * public interface NestedInteger {
  5. *     // Constructor initializes an empty nested list.
  6. *     public NestedInteger();
  7. *
  8. *     // Constructor initializes a single integer.
  9. *     public NestedInteger(int value);
  10. *
  11. *     // [url=home.php?mod=space&uid=160137]@return[/url] true if this NestedInteger holds a single integer, rather than a nested list.
  12. *     public boolean isInteger();
  13. *
  14. *     // @return the single integer that this NestedInteger holds, if it holds a single integer
  15. *     // Return null if this NestedInteger holds a nested list
  16. *     public Integer getInteger();
  17. *
  18. *     // Set this NestedInteger to hold a single integer.
  19. *     public void setInteger(int value);
  20. *
  21. *     // Set this NestedInteger to hold a nested list and adds a nested integer to it.
  22. *     public void add(NestedInteger ni);
  23. *
  24. *     // @return the nested list that this NestedInteger holds, if it holds a nested list
  25. *     // Return null if this NestedInteger holds a single integer
  26. *     public List<NestedInteger> getList();
  27. * }
  28. */
  29. class Solution {
  30.     public int depthSum(List<NestedInteger> nestedList) {
  31.         if(nestedList == null) return 0;
  32.         return helper(nestedList,1);
  33.     }
  34.     public int helper(List<NestedInteger> nestedList, int level){
  35.         int sum=0;
  36.         for(NestedInteger nest: nestedList){
  37.             if(nest.isInteger()){
  38.                 sum+=nest.getInteger() * level;
  39.             }else{
  40.                 sum+= helper(nest.getList(),level+1);//所以这个recursion没有base case吗
  41.             }
  42.         }
  43.         return sum;
  44.     }
  45. }
复制代码


求教,谢谢

上一篇:求问关于最短路径树和最小生成树的边权值比较
下一篇:一道关于MST树的算法设计题
🔗
magicsets 2020-2-4 17:02:42 | 只看该作者
全局:
base case就是nestedList为空的情况,此时helper内的for循环不执行,直接返回sum = 0
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表