听说逆向思维能够降低时间复杂度?

  |  

以终为始在日常生活中指的是先确定目标,再做好计划。之前读管理学的书的时候,学到了这个概念。

而在算法中,以终为始指的是从结果反向推,直到问题的初始状态

那么什么时候适合反向思考呢?简单的原则就是:

  1. 正向思考的情况比较多
  2. 代码比较难写或者算法复杂度过高

这个时候我们可以考虑反向操作。

我的习惯是如果直接求解很难,我会优先考虑使用能力检测二分,如果不行我则会考虑反向思考。

关于能力检测二分,可以在我的公众号中找到,大家可以在《力扣加加》回复二分获取。

今天西法通过三道题来给大家聊聊到底怎么在写算法题的时候运用以终为始思想。

技术面试原来不止考技术?

  |  

大家好呀,狗头又出现啦~

我在 21 年的时候无相关背景转码上岸狗家,并且接到了一些中小厂的 offer。在我准备面试和面试的过程中,我总结了一些非技术相关的技巧和心得。这些技巧和心得在技术面试中往往能起到锦上添花的作用。这篇文章讨论的所有技巧都跟代码能力和工程能力无关~

背景

给一个两个数组,其中一个数组是 A [1,2,3,4],另外一个数组是 B [5,6,7,8]。让你求两个数组合并后的大数组的:

  • 最大值
  • 最小值
  • 总和

这题是不是很简单?我们直接可以很轻松地在 $O(m+n)$ 的时间解决,其中 m 和 n 分别为数组 A 和 B 的大小。

那如果我可以修改 A 和 B 的某些值,并且我要求很多次最大值,最小值和总和呢?

朴素的思路是原地修改数组,然后 $O(m+n)$ 的时间重新计算。显然这并没有利用之前计算好的结果,效率是不高的。 那有没有效率更高的做法?

有!线段树就可以解决。

经过了半年时间打磨,投入诸多人力,这本 LeetCode 题解书终于要和大家见面了。
💐💐💐💐💐。

实体版购书链接:https://union-click.jd.com/jdc?e=&p=JF8BANYJK1olXQcDUV9VDUMeBF8IGloXVAIGU1pdCUIVCl9MRANLAjZbERscSkAJHTdNTwcKBlMdBgABFksWAm0BH18SWQYDXVxUFxJSXzI4UixRNl1GVjc-ci1CQA5RUl5sHVhZAlJROEonA24JG1MQWgMEUW5tCEwnQgEMGV4WVTYDZF5aCkMWA2kBH1sUVQ8yU15UOBBCbWgIHghBDgVQAw4JXx4nM18LK2slXTYBZBwzDUIWBWpdSVNFVFJQUQ1fDkMWAToKG1xCX1QEB1sJW0wnAW4JH1Il

电子版购书链接:https://union-click.jd.com/jdc?e=&p=JF8BAL0JK1olXDYAVVhfD04UAl9MRANLAjZbERscSkAJHTdNTwcKBlMdBgABFkkWBW0PHlgUQl9HCANtcS0SdTFvWVt1X3BkVV4Kc0JxYRtPe1cZbQcyVF9cCEMSBGoOHmslXQEyHzBcOEonA2gKE1oVWwEKXV5cAXsQA2Y4QA57WgYHBwoOCxlAUztfTmslbQUyZG5dOEgnQQFaSQ5FWQYFB1cODhgSVDpaS1hFDwQLUlwJAU5DAWcJHWsXXAcGXW4

在线试读



博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本站使用 Material X 作为主题 。
载入天数...载入时分秒...