一只青蛙跳出来的分治法、回溯法与动态规划

从2018年7月份开始,基础薄弱的我从0开始刷LeetCode题目。目的性很明确,也很简单——就是为了提高解决问题的思考实践能力,也为了提升自己的核心竞争力。也许,牛人会觉得这并不算什么竞争力。是的,我同意的。但,这是我目前能做的比较基础的事情罢了。迄今(2018年12月28日)为止,已经刷了108道题目。顺序基本上是按照出现的频率(Frequency)来刷的,这个频率在LeetCode上需要订阅后才可以看得到。那么在刷了108道题目后,有那么一些题目会觉得“似曾相识”了,也会有一种触类旁通的感觉了。所以,我觉得应该适当放慢刷题的速度,同时做做总结了。所以,计划了一项视频解说计划,在YouTubeh和B站都建立了《小旭解说算法之路》的频道,欢迎订阅,多多提建议。那么,进入正题。经过了108道题的历练之后,我来说说对于分治法、回溯法和动态规划的理解。我觉得他们三者是一个相互有交集的概念,并不... Read More

小旭讲解 LeetCode 53. 最大子序和 动态规划 分治策略

原题Given an integer arraynums, find the contiguous subarray(containing at least one number) which has the largest sum and return its sum.ExampleInput: [-2,1,-3,4,-1,2,1,-5,4]Output: Explanation:[4,-1,2,1] has the largest sum = 6.Follow upIf you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.题解动态规划哔哩哔哩 动态规划YouTube 动态规划通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。... Read More

[LeetCode]743. Network Delay Time

原题There are N network nodes, labelled 1 to N.Given times, a list of travel times as directed edges times[i] = (u, v, w), where u is the source node, v is the target node, and w is the time it takes for a signal to travel from source to target.Now, we send a signal from a certain node K. How long will it take for all nodes to receive the signal? If it is impossible, return -1.NoteN will be in the ... Read More

[LeetCode]893. Groups of Special-Equivalent Strings

原题You are given an array A of strings.Two strings S and T are special-equivalent if after any number of moves, S == T.A move consists of choosing two indices i and j with i % 2 == j % 2, and swapping S[i] with S[j].Now, a group of special-equivalent strings from A is a non-empty subset S of A such that any string not in S is not special-equivalent with any string in S.Return the number of groups o... Read More

[LeetCode]Valid Palindrome II

原题Given a non-empty string s, you may delete at most one character. Judge whether you can make it a palindrome.Example 1Input: "aba"Output: TruExample 2Input: "abca"Output: TruExplanation: You could delete the character 'c'.NoteThe string will only contain lowercase characters a-z. The maximum length of the string is 50000.思路水题。判断是否是回文字符串最简单的方式就是从左右两端逐步向中心逼近(双指针),如下代码[code lang="cpp"for (in... Read More

[LeetCode 889]Construct Binary Tree from Preorder and Postorder Traversal

原题Return any binary tree that matches the given preorder and postorder traversals.Values in the traversalspreandpostare distinctpositive integers.Example 1Input: pre = [1,2,4,5,3,6,7], post = [4,5,2,6,7,3,1Output: [1,2,3,4,5,6,7Note1 <= pre.length == post.length <= 30pre[]andpost[]are both permutations of1, 2, ..., pre.length.It is guaranteed an answer exists. If there exists multiple an... Read More

[LeetCode]Sum of Subarray Minimums

原题Given an array of integers A, find the sum of min(B), where B ranges over every (contiguous) subarray of A.Since the answer may be large, return the answer modulo 10^9 + 7.Example 1Input: [3,1,2,4Output: 1Explanation: Subarrays are [3], [1], [2], [4], [3,1], [1,2], [2,4], [3,1,2], [1,2,4], [3,1,2,4].Minimums are 3, 1, 2, 4, 1, 1, 2, 1, 1, 1.  Sum is 17.Note1 <= A.length <1 <= A[i] <... Read More

[LeetCode]Fruit Into Baskets

原题In a row of trees, the i-th tree produces fruit with type tree[i].You start at any tree of your choice, then repeatedly perform the following stepsAdd one piece of fruit from this tree to your baskets.  If you cannot, stop.Move to the next tree to the right of the current tree.  If there is no tree to the right, stop.Note that you do not have any choice after the initial choice of starting tree... Read More

[LeetCode]Remove Nth Node From End of List

原题Given a linked list, remove the n-th node from the end of list and return its head.ExampleGiven linked list: 1->2->3->4->5, and n = 2.After removing the second node from the end, the linked list becomes 1->2->3->5.NoteGiven n will always be valid.Follow upCould you do this in one pass思路首先,明确题意。题目给出了一个只有后继(successor),没有前驱(predecessor)的一个单向链表。要求删除倒数第n个节点。那么,思路自然会想到的就是在一次遍历就搞定题目要求。所以,我们自然要在遍历的过程中保存一... Read More

[LeetCode]4Sum

原题Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.NoteThe solution set must not contain duplicate quadruplets.ExampleGiven array nums = [1, 0, -1, 0, -2, 2], and target = 0.A solution set is[-1, 0, 0, 1][-2, -1, 1, 2][-2, 0, 0, 2题解本题的... Read More

[LeetCode]3Sum Closest

原题Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.ExampleGiven array nums = [-1, 2, 1, -4], and target = 1.The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).思路本题目的解题思路和3Sum很像,区别在于3Sum求解的是三个数字和为target(即为0),然而3Su... Read More

结构化您的Python工程

我们对于“结构化”的定义是您关注于怎样使您的项目最好地满足它的对象性,我们 需要去考虑如何更好地利用Python的特性来创造简洁、高效的代码。在实践层面, “结构化”意味着通过编写简洁的代码,并且正如文件系统中文件和目录的组织一样, 代码应该使逻辑和依赖清晰。哪个函数应该深入到哪个模块?数据在项目中如何流转?什么功能和函数应该组合 或独立?要解决这些问题,您可以开始做个一计划,大体来说,即是您的最终产品 看起来会是怎样的。在这一章节中,我们更深入地去观察Python的模块和导入系统,因为它们是加强您 的项目结构化的关键因素,接着我们会从不同层面去讨论如何去构建可扩展且测试 可靠的的代码。 Read More

Python socket网络编程之阻塞与非阻塞模式

在智能家居项目hestia中,遇到一个关于python socket编程的小问题。发现在python socket客户端一端,在服务端断开时,没有抛出异常。[code lang="python"trymsg = _sFile.readline(except socket.error, elogging.info("socket exception" + e.message_reconnect([/code翻阅文档后,发现python socket分为阻塞式和非阻塞式。默认初始化的socket是阻塞式的,在阻塞式下,如果socket断开链接,将会返回空串。官方解释如下socket.setblocking(flagSet blocking or non-blocking mode of the socket: if flag is 0, the socket is set to... Read More

Python语言中循环引用(import)失败的解决方案

最近在开发智能家居项目hestia-rpi项目中,由于代码结构层级划分不合理,导致了循环引用(import)module失败的问题,错误如下[code lang="shell"Traceback (most recent call last)File "./main.py", line 8, in &amp;amp;lt;module&amp;amp;gt;from hestiarpi.library.server import serveFile "/home/pi/server/hestiarpi/library/server/server.py", line 4, in &amp;amp;lt;module&amp;amp;gt;from hestiarpi.library.brain import handleFile "/home/pi/server/hestiarpi/... Read More

Android O后台持续获取地理位置的简单调研过程

这几天打算重新捡起之前的智能家居项目,由于近期换了安卓设备,所以要重新开发一款安卓APP。但是其功能很简单---可以在后台稳定地上报地理位置到服务器。首先,考虑到用LocationManager方式获取地理位置,但是根据官方文档声明,很大程度上限制了后台获取位置的能力。重要说明:作为起点,我们只允许后台应用每小时接收几次位置更新。我们将在整个预览版阶段继续根据系统影响和开发者的反馈优化位置更新间隔。当然,根据官方解释,可以通过在通知区持续地显示一项通知信息,以提高后台获取位置更新的频率。但是由于自身对于安卓开发并不熟悉,而且网上高德提供的SDK已经很好地解决了该问题,索性直接高德定位SDK来解决吧。项目代码:https://github.com/GenialX/hestia-android/tree/v0.0.1_bet文章来源:胡小旭 => Android O后台持续获取地理位置... Read More

[LeetCode]3Sum

原题Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.Note: The solution set must not contain duplicate triplets.For example, given array S = [-1, 0, 1, 2, -1, -4]A solution set is[-1, 0, 1][-1, -1, 2题解暴力解法因为需要计算三个数字的总和,所以需要进行3层的遍历,故时间复杂度需要O(n^3),看来不可取,果断放弃。毕竟是medium难度的题,不至于这么个解法。two-pointes solutio... Read More

[LeetCode]Two Sum

原题Given an array of integers, return indices of the two numbers such that they add up to a specific target.You may assume that each input would have exactly one solution, and you may not use the same element twice.ExampleGiven nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].题解暴力解法暴力解法使用两层for循环,遍历每一种存在的情况。[code lang="cpp"class Solution publicvector<int... Read More

[LeetCode]Palinkdrom Number

ProbleDetermine whether an integer is a palindrome. Do this without extra space.Some hints[code lang="shell" collapse="true"Could negative integers be palindromes? (ie, -1If you are thinking of converting the integer to string, note the restriction of using extra space.You could also try reversing an integer. However, if you have solved the problem "Reverse Integer", you know that th... Read More

[LeetCode]Roman to Integer

ProbleGiven a roman numeral, convert it to an integer.Input is guaranteed to be within the range from 1 to 3999.IdeaFinding the Law of Changing Roman Numbers into Arabic Numbers。Solutio[code lang="cpp"class Solution publicint romanToInt(string s) int l = s.length(), a = 0;for (int i = 0; i < l; ++iif (i < l - 1 && char2int(s[i]) < char2int(s[i + 1])) a -= char2int(s[i]);} else a += char2int(s[i]);... Read More

Mac(Linux)下解压(Unzip)文件时出现乱码解决方案

由于zip格式中并没有指定编码格式,Windows下生成的zip文件中的编码是GBK/GB2312等,因此,导致这些zip文件在Linux下解压时出现乱码问题,因为Linux下的默认编码是UTF8。Python方案这个方案很简单,因为如果你是*nix系统,那么python环境很有可能已经装好了。如果没有安装的话,可以到下面地址下载对应的安装包https://wiki.python.org/moin/BeginnersGuide/Downloa然后,创建python脚本文件myunzip.py,并写入如下内容[code lang="python"#作者:Latm Ak#链接:https://www.zhihu.com/question/20523036/answer/3522592#来源:知乎#著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。#!/usr/bin/env pytho... Read More

微软工程师:蔡克贺与他的Leetcode刷题之道

YoukYouTub相关资源到底该如何刷LeetCode: https://qoogle.top/how-to-brush-leetcode/ [视频] 如何找实习:https://tinyurl.com/y8fzjzaf[视频] 如何刷题:https://tinyurl.com/yazujcb3[视频] 如何社交:https://tinyurl.com/yavh53qb[视频] 一对一职场资讯:https://tinyurl.com/yb6pfwo视频来源:https://www.youtube.com/watch?v=Z3KrtEaw0v Read More