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://...阅读全文

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

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

3年PHPer的面试总结

之前看到一篇文章《八年phper的高级工程师面试之路》,然后最近我也在面试,面了有百度、360、滴滴、小米、微博、58赶集、搜狗、瓜子二手车等公司,最后也进了心仪的公司,面试过程中学到了很多东西,所以也想和大家分享一下,虽然我的工作经验才3年左右。 注:下面题目的答案只是我思考和查询资料的结果,并不代表完全准确,有错误的地方大家可以指正,有更好的方案可以提出,大家一起讨论。算法1.反转函数的实现2.两个有序int集合是否有相同元素的最优算法3.将一个数组中的元素随机(打乱4.给一个有数字和字母的字符串,让连着的数字和字母对应5.求n以内的质数(质数的定义:在大于1的自然数中,除了1和它本身意外,无法被其他自然数整除的数思路: 1.(质数筛选定理)n不能够被不大于根号n的任何质数整除,则n是一个质数 2.除了2的偶数都不是质数 代码如下6.约瑟夫环问题相关题目:一群猴子排成一圈,按1,...阅读全文

ZigZag Conversion(math)

QuestioThe string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibilityP A H A P L S I I Y I And then read line by line: "PAHNAPLSIIGYIR"Write the code that will take a string and make this conversion given a number of rowsstring convert(string text, int nRows);convert("PAYPAL...阅读全文

翻转整型数(水题)

正题Reverse digits of an integer.Example1: x = 123, return 32Example2: x = -123, return -32思考改题为简单难度(水题),根据题意可以依次取到给定的整型数x的最高位到最低的数,然后依次将其乘10的x次幂后进行累加即可得到结果。这里,要知道32位的整型一共有九个0,故声明i=1000000000;代码原题:https://leetcode.com/problems/reverse-integer/description阅读全文

最长回文字符串题解(动态规划)

LeetCode正题Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.ExampleInput: "babad"Output: "bab"Note: "aba" is also a valid answer.ExampleInput: "cbbd"Output: "bb"思考回文字符串即正向顺序和反向顺序的字幕排序是一致的字段串。题的大意为寻找一个指定字符串中的最长的回文字符串。首选,暴力解法需要遍历所有子串并判断子串是否为回文字符串。假设给定字符串长度n,那么子串的总数为​n(n+1)/2(即1 2 3 ... n的和),即需要O(n^2),然后判断每个子串是否为回文字符串的时间复杂度为O(n),即总共需要...阅读全文

最长不重复子字符串问题(动态规划)

问题Given a string, find the length of the longest substring without repeating characters.ExamplesGiven "abcabcbb", the answer is "abc", which the length is 3.Given "bbbbb", the answer is "b", with the length of 1.Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequenceand not a substring.分析首先,这种题肯定不能暴力来解决,否则肯定会超时。所以,考虑用一个哈希表(Map&l...阅读全文

Rabin-Karp 算法(字符串快速查找)

Go 语言的 strings 包(strings.go)中用到了 Rabin-Karp 算法。Rabin-Karp 算法是基于这样的思路:即把字符串看作是字符集长度进制的数,由数值的比较结果得出字符串的比较结果。朴素的字符串匹配算法为什么慢?因为它太健忘了,前一次匹配的信息其实有部分可以应用到后一次匹配中去,而朴素的字符串匹配算法只是简单的把这个信息扔掉,从头再来,因此,浪费了时间。好好的利用这些信息,自然可以提高运行速度。由于完成两个字符串的比较需要对其中包含的字符进行逐个比较,所需的时间较长,而数值比较则一次就可以完成,那么我们首先把“搜索词”中各个字符的“码点值”通过计算,得出一个数值(这个数值必须可以表示出字符的前后顺序,而且可以随时去掉某个字符的值,可以随时添加一个新字符的值),然后对“源串”中要比较的部分进行计算,也得出一个数值,对这两个数值进行比较,就能判断字符串是否匹配。对...阅读全文

Codeforces Round #345 (Div. 1) C. Table Compression

原题C. Table Compressiotime limit per tes4 secondmemory limit per tes256 megabyteinpustandard inpuoutpustandard outpuLittle Petya is now fond of data compression algorithms. He has already studied gz, bz, zip algorithms and many others. Inspired by the new knowledge, Petya is now developing the new compression algorithm which he wants to name dis.Petya decided to compress tables. He is give...阅读全文

深度优先搜索之栈解迷宫(C++)

在之前的一篇关于搜索的文章中《广度优先搜索算法队解迷宫问题》有提到深度优先搜索(dfs)算法,其中有一种就是本篇文章提到的实现方法:利用栈解迷宫;《广度优先搜索算法队解迷宫问题》中利用栈解迷宫有一个bug,比如:在x点出发,向右走直到尽头回到x点,此时在向其他方向(比如上),那么不能再走曾经向右走过的路(坐标)。这次,我们增加一个direct_mark数组,来标记在每一个坐标上曾经走过的方向。程序范例时间复杂度在一个m*n的迷宫中,最糟糕的情况是每个点的四个方向均探索了,即o(m*n文章来源:胡旭博客 => 深度优先搜索之栈解迷宫(C转载请注明出处,违者必究阅读全文

分治法解矩阵乘积

题目假设有A,B两个矩阵,且其均为n*n维矩阵,n为2的幂(n>=2)。求A与B的乘积。通过上图我们可以看到书中的利用分治法解决的伪代码。解决思路一暴力解法时间复杂度O(n^3程序范例解决思路二利用分治法解决矩阵乘积程序范例时间复杂度其时间复杂度不等式为:T(n) = 8*T(n/2) + Θ(n^2),所以其时间复杂度为O(n^3测试假设A,B均为521*521的矩阵,并利用0-99的随机数初始化。分别利用暴力解法和分治法进行求解。程序如下测试结果# ./a.out :( ...阅读全文

动态规划解决最大子数组问题

问题Find the contiguous subarray within an array (containing at least one number) which has the largest sum.For example, given the array [−2,1,−3,4,−1,2,1,−5,4]the contiguous subarray [4,−1,2,1] has the largest sum = 6.问题来自于Leetcode:Maximum Subarra解决方式利用动态规划思想来解决最大子数组问题。之前的文章有写过有关动态规划的思路。如果你对动态规划不清楚可以通过这篇文章来简单了解下,里面有相应的视频还是不错的:拆分集合为两个和相等的子集合问题(动态规划)。该方法相对于分治法策略解决最大子数组问题来解决的时间复杂度中会有很大提升。时间复杂度O(n程序范例...阅读全文

分治法策略解决最大子数组问题

问题描述Find the contiguous subarray within an array (containing at least one number) which has the largest sum.For example, given the array [−2,1,−3,4,−1,2,1,−5,4]the contiguous subarray [4,−1,2,1] has the largest sum = 6.问题来自于Leetcode:Maximum Subarra解决方式利用分治策略来解决最大子数组问题时间复杂度O(nlgn程序范例总结分治法的主要细想即三部曲:分解(divide)、解决(conquer)与合并(combine)。掌握大致这三个步骤,再加上对递归的使用,即可利用分治策略来解决一些问题。这样往往时间复杂度会比暴力解决问题效率高的多。对于分治法...阅读全文