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

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

2018LeeCode算法题解一之Valid Palindrome

原题Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.For example"A man, a plan, a canal: Panama" is a palindrome."race a car" is not a palindrome.NoteHave you consider that the string might be empty? This is a good question to ask during an interview.For the purpose of this problem, we define empty string as valid palindrome.原题链接:https://... Read More

[开发中]基于树莓派的智能家居项目的设想与实现 Hestia

注:本文内容的准确性仅限于笔者写该篇文章时的情况,不保证后续与实际项目代码一致。实时内容还请关注Github项目托管页面:https://github.com/GenialX/hestia-serve树莓派,一个五脏俱全,集几乎所有功能于一身的微型计算器。大约一两月之前,屈屈300百大洋收入囊中。入手之后,出于对自动化的兴趣,慢慢地研究如何实现室内家电的智能自动化控制。在断断续续地,不断地摸索之后,有了若干想实现的点子,迄今为止也有所实践。点子利用红外线传感器智能控制空调、电视等基于红外遥控的家电设备;智能控制家中的灯泡设备(部分基于网络协议);方案硬件首先,除了树莓派之外,还需要如下硬件移动端设备 Android手机一台(iPhone手机当然也没问题,但是本案例中只基于Android手机做了实现外网可直接访问的服务器一台(本案例使用阿里云服务器基于树莓派(点我购买)的传感器若干基于光敏电阻的光线传感器一个... Read More

内网穿透工具的原理与开发实战

在我国,由于网民众多,运营商无法保证为每一个宽带用户提供全球唯一的公网IPv4地址。因此很多用户会发现通过路由器端查看到的WAN端IP与百度“IP”关键词所得到的IP不一致,并且前者的IP为一个私有IP。而还有一些情况下,公网IP比较昂贵,企业虽然本身也持有少量的独立的公网IP,但是由于成本限制无法为企业内每一台主机都提供一个公网IP,或者内网并不是所有服务都需要暴露到公网中进行访问,那么企业有可能就会使用NAT技术将大量的内网IP通过一定规则映射到公网IP上。而最常见的其中一种技术就是NAPT,也叫“网络端口地址转换”。因为一般一个服务都是通过一个端口来提供,因此通过这种方式可以将特定的服务通过特定的规则开放到少量的公网IP上。 Read More

从小白到机器学习算法工程师,我做了哪些准备?

一、方向选择都说选择比努力重要,这个鸡汤我觉得可以干了。起初接触人工智能领域是在硕士选择导师的时候,当时民叔推荐来到人工智能与机器人研究所,跟随现在的硕导做图像处理方面的研究,用到一些机器学习的算法做分类工作。在学校学习平台比较重要,它决定了你会见识什么人、什么样的黑科技、什么样的应用等,没有这些东西勾起你的好奇心,也就没有对未来的规划或者说期待。硕士期间,养成了看论文的习惯,专注领域顶级期刊论文,当然了首先是先把自己研究的课题相关知识看的透彻,这个在第二小节中会介绍:为什么硕士课题很重要。一些我认识是牛人的人说,看论文是在跟领域大牛在交流,这个确实刚开始体会不到,起初很排斥看论文,更加上我的英语那是一个...后来看多了,发现知识之间都是相通的,可能解决一个问题用的是同一个方法,这样看一篇论文的时间会大大缩短,有效率了,心里便更愿意去看论文。康奈尔大学图书馆网站每天更新世界上各个大牛写的论... Read More