wangyuquan-CSDN博客

原创开新博客啦

这个博客以后就不更新啦新博客地址：点击打开链接

2015-10-26 19:53:22 1642

原创 2015 找暑期实习总结

今年的暑期实习生应聘也差不多告一段落了，在此总结一下，也算个各个公司的面经：）投的第一家是阿里，因为阿里的实习生内推非常早，找figo内推之后快两个礼拜才开始了一面，虽然我投的是阿里云，但是被分配到了技术保障部，据说是比较底层的一个部门，一面面试主要考了一些概率题（机子出故障的概率），然后考了一些计算机基础知识，如进程线程，并行和并发的区别，也就考了十来分钟吧，然后面试官就和我聊人生聊了二十分

2015-05-10 11:28:39 2141 1

原创朴素贝叶斯实现垃圾邮件分类------matlab实现

之所以用matleb实现，是因为这是数据挖掘课的几个大作业之一，作业要求，不然也不会这么蛋疼用matlab....(因为我不会matlab...)朴素贝叶斯原理非常简单，最重要的就是概率公式：其余的内容介绍可以参考：http://zh.wikipedia.org/wiki/%E6%9C%B4%E7%B4%A0%E8%B4%9D%E5%8F%B6%E6%96%AF%E5%88%8

2013-11-30 22:55:24 10623 10

原创用python制造一条令人涨姿势的贪吃蛇

之前看了一副大涨姿势的贪吃蛇的图，甚为震精，可以再观赏一下：既然talk is cheap,show me the code ,我就按照http://hawstein.com/posts/snake-ai.html的教程写了一个，当然并没有能像上图那么令人涨姿势，但是让贪吃蛇自动跑很长时间还是做到了的首先是照教程所说，网上下了一个可以根据方向键来控制贪吃蛇的一个代码版本，直

2013-04-28 22:06:15 4275 1

原创 python 垃圾收集机制

pythonn垃圾收集方面的内容如果要细讲还是挺多的，这里只是做一个大概的概括python最主要和绝大多数时候用的都是引用计数,每一个PyObject定义如下：#define PyObject_HEAD \ Py_ssize_t ob_refcnt; \ struct _typeobject *ob_type;

2013-03-19 15:44:41 1162

原创《python源码剖析》之实现small python

基本上是照着《python源码剖析》里面的代码写的，当然它有一点细节的地方没有指出来，我也就补全了一下，先来看下运行的效果图：下面直接上代码：#include#include#include#include#include#include#include#includeusing namespace std;#define PyObject_HEAD

2013-03-09 19:51:24 3168

原创 LintCode-N皇后问题

n皇后问题是将n个皇后放置在n*n的棋盘上，皇后彼此之间不能相互攻击。给定一个整数n，返回所有不同的n皇后问题的解决方案。每个解决方案包含一个明确的n皇后放置布局，其中“Q”和“.”分别表示一个女王和一个空位置。您在真实的面试中是否遇到过这个题？ Yes样例对于4皇后问题存在两种解决的方案：[ [".Q..", // Solution

2015-08-20 19:49:42 2234

原创 LintCode-数组划分

给出一个整数数组nums和一个整数k。划分数组（即移动数组nums中的元素），使得：所有小于k的元素移到左边所有大于等于k的元素移到右边返回数组划分的位置，即数组中第一个位置i，满足nums[i]大于等于k。您在真实的面试中是否遇到过这个题？ Yes样例给出数组nums=[3,2,2,1]和 k=2，返回 1注意

2015-08-19 11:23:36 2945

原创 LintCode-交叉字符串

给出三个字符串:s1、s2、s3，判断s3是否由s1和s2交叉构成。您在真实的面试中是否遇到过这个题？ Yes样例比如 s1 = "aabcc" s2 = "dbbca" - 当 s3 = "aadbbcbcac"，返回 true. - 当 s3 = "aadbbbaccc"，返回 false.挑战要求时间复杂度为O(

2015-08-19 11:00:47 4150

原创 LintCode-第k大元素

在数组中找到第k大的元素您在真实的面试中是否遇到过这个题？ Yes样例给出数组[9,3,2,4,8]，第三大的元素是4给出数组 [1,2,3,4,5]，第一大的元素是5，第二大的元素是4，第三大的元素是3，以此类推注意你可以交换数组中的元素的位置挑战要求时间复杂度为O(n），空间复杂度为O(1）标签 Exp

2015-08-18 20:17:22 5602

原创 LintCode-A + B 问题

给出两个整数a和b, 求他们的和, 但不能使用 + 等数学运算符。您在真实的面试中是否遇到过这个题？ Yes样例如果 a=1 并且 b=2，返回3注意你不需要从输入流读入数据，只需要根据aplusb的两个参数a和b，计算他们的和并返回就行。挑战显然你可以直接 return a + b，但是你是否可以挑战一下不这样做？

2015-08-18 17:50:47 5490 3

原创 LintCode-丑数

设计一个算法，找出只含素因子3，5，7 的第 k 大的数。符合条件的数如：3，5，7，9，15......您在真实的面试中是否遇到过这个题？ Yes样例如果k=4，返回 9挑战要求时间复杂度为O(nlogn)或者O(n)标签 Expand 相关题目 Expand 分析：分别设三个指针，表明乘以3，5，7

2015-08-18 17:42:15 1995

原创 LintCode-买卖股票的最佳时机

假设有一个数组，它的第i个元素是一支给定的股票在第i天的价格。如果你最多只允许完成一次交易(例如,一次买卖股票),设计一个算法来找出最大利润。您在真实的面试中是否遇到过这个题？ Yes样例给出一个数组样例 [3,2,3,1,2], 返回 1 标签 Expand 相关题目 Expand 分析：对于每一天来说，它能得到的最大利益

2015-08-13 21:05:22 4255

原创 LintCode-加油站

在一条环路上有 N 个加油站，其中第 i 个加油站有汽油gas[i]，并且从第_i_个加油站前往第_i_+1个加油站需要消耗汽油cost[i]。你有一辆油箱容量无限大的汽车，现在要从某一个加油站出发绕环路一周，一开始油箱为空。求可环绕环路一周时出发的加油站的编号，若不存在环绕一周的方案，则返回-1。您在真实的面试中是否遇到过这个题？ Yes样例现在有4个

2015-08-13 19:04:45 2769

原创 LintCode-赋值运算符重载

实现赋值运算符重载函数，确保：新的数据可准确地被复制旧的数据可准确地删除/释放可进行 A = B = C 赋值您在真实的面试中是否遇到过这个题？ Yes样例如果进行 A = B 赋值，则 A 中的数据被删除，取而代之的是 B 中的数据。如果进行 A = B = C 赋值，则 A 和 B 都复制了 C 中的数据。挑战充分考虑

2015-08-12 21:39:29 816

原创 LintCode-两个整数相除

将两个整数相除，要求不使用乘法、除法和 mod 运算符。如果溢出，返回 2147483647 。您在真实的面试中是否遇到过这个题？ Yes样例给定被除数 = 100 ，除数 = 9，返回 11。标签 Expand 相关题目 Expand 分析：既然不能乘法和除法，那肯定就只能位操作了，然后如果用减法的话，太慢了，必须想点二进

2015-08-12 21:26:02 3191

原创 LintCode-最长回文子串

给出一个字符串（假设长度最长为1000），求出它的最长回文子串，你可以假定只有一个满足条件的最长回文串。您在真实的面试中是否遇到过这个题？ Yes样例给出字符串 "abcdzdcab"，它的最长回文子串为 "cdzdc"。挑战O(n2) 时间复杂度的算法是可以接受的，如果你能用 O(n) 的算法那自然更好。标签 Expand

2015-08-12 20:20:49 1768

原创 LintCode-分糖果

有 N 个小孩站成一列。每个小孩有一个评级。按照以下要求，给小孩分糖果：每个小孩至少得到一颗糖果。评级越高的小孩可以得到更多的糖果。需最少准备多少糖果？您在真实的面试中是否遇到过这个题？ Yes样例给定评级 = [1, 2], 返回 3.给定评级 = [1, 1, 1], 返回 3.给定评级 = [1, 2, 2], 返回

2015-08-11 20:52:16 2542

原创 LintCode-和大于S的最小子数组

给定一个由 n 个整数组成的数组和一个正整数 s ，请找出该数组中满足其和 ≥ s 的最小长度子数组。如果无解，则返回 -1。您在真实的面试中是否遇到过这个题？ Yes样例给定数组 [2,3,1,2,4,3] 和 s = 7, 子数组 [4,3] 是该条件下的最小长度子数组。挑战如果你已经完成了O(n)时间复杂度的编程，请再试试 O(n

2015-08-11 20:28:02 2558 1

Given an array A of integer with size of n( means n books and number of pages of each book) and k people to copy the book. You must distribute the continuous id books to one people to copy. (You can g

2015-08-10 20:07:36 4211

原创 LintCode-通配符匹配

判断两个可能包含通配符“？”和“*”的字符串是否匹配。匹配规则如下：'?' 可以匹配任何单个字符。'*' 可以匹配任意字符串（包括空字符串）。两个串完全匹配才算匹配成功。函数接口如下:bool isMatch(const char *s, const char *p)您在真实的面试中是否遇到过这个题？ Yes样例一些例子：isMatch("a

2015-08-09 19:05:13 2457

原创 LintCode-最大子数组 III

给定一个整数数组和一个整数k，找出k个不重叠子数组使得它们的和最大。每个子数组的数字在数组中的位置应该是连续的。返回最大的和。您在真实的面试中是否遇到过这个题？ Yes样例给出数组[-1,4,-2,3,-2,3]以及k=2，返回 8注意子数组最少包含一个数挑战要求时间复杂度为O(n)标签 Exp

2015-08-09 16:48:00 3590 1

原创 LintCode-k数和

给定n个不同的正整数，整数k（k 在这n个数里面找出K个数，使得这K个数的和等于目标数字，求问有多少种方案？您在真实的面试中是否遇到过这个题？ Yes样例给出[1,2,3,4]，k=2， target=5，[1,4] and [2,3]是2个符合要求的方案标签 Expand 相关题目 Expand 分析：看到这种题目想肯

2015-08-09 15:52:02 3346

原创 LintCode-分割回文串 II

给定一个字符串s，将s分割成一些子串，使每个子串都是回文。返回s符合要求的的最少分割次数。您在真实的面试中是否遇到过这个题？ Yes样例比如，给出字符串s = "aab"，返回 1，因为进行一次分割可以将字符串s分割成["aa","b"]这样两个回文子串标签 Expand 相关题目 Expand 分析：一开始写了个n的

2015-08-09 14:34:36 5089

原创 LintCode-硬币排成线

有 n 个硬币排成一条线。两个参赛者轮流从右边依次拿走 1 或 2 个硬币，直到没有硬币为止。拿到最后一枚硬币的人获胜。请判定第一个玩家是输还是赢？您在真实的面试中是否遇到过这个题？ Yes样例n = 1, 返回 true.n = 2, 返回 true.n = 3, 返回 false.n = 4, 返回 true.n = 5, 返回

2015-08-08 19:47:10 2612 6

原创 LintCode-带环链表 II

给定一个链表，如果链表中存在环，则返回到链表中环的起始节点的值，如果没有环，返回null。您在真实的面试中是否遇到过这个题？ Yes样例给出 -21->10->4->5, tail connects to node index 1，返回10挑战不使用额外的空间标签 Expand 相关题目 Expand 分析：

2015-08-08 16:57:26 2466 1

原创 LintCode-排序列表转换为二分查找树

给出一个所有元素以升序排序的单链表，将它转换成一棵高度平衡的二分查找树您在真实的面试中是否遇到过这个题？ Yes样例标签 Expand 相关题目 Expand 分析：就是一个简单的递归，只是需要有些链表的操作而已代码：/** * Definition of ListNode * class ListNode { *

2015-08-08 16:15:31 1964

原创 LintCode-删除排序链表中的重复数字 II

给定一个排序链表，删除所有重复的元素只留下原链表中没有重复的元素。您在真实的面试中是否遇到过这个题？ Yes样例给出1->2->3->3->4->4->5->null，返回1->2->5->null给出1->1->1->2->3->null，返回 2->3->null标签 Expand 分析：因为是排序链表，所以每次判断

2015-08-08 15:54:59 2985

原创 LintCode-旋转链表

给定一个链表，旋转链表，使得每个节点向右移动k个位置，其中k是一个非负数您在真实的面试中是否遇到过这个题？ Yes样例给出链表1->2->3->4->5->null和k=2返回4->5->1->2->3->null标签 Expand 相关题目 Expand 分析：感觉很直观，直接把分割点找出来就行，记得k可能大于len,要取

2015-08-08 15:44:05 814

原创 LintCode-LRU缓存策略

为最近最少使用（LRU）缓存策略设计一个数据结构，它应该支持以下操作：获取数据（get）和写入数据（set）。获取数据get(key)：如果缓存中存在key，则获取其数据值（通常是正数），否则返回-1。写入数据set(key, value)：如果key还没有在缓存中，则写入其数据值。当缓存达到上限，它应该在写入新数据之前删除最近最少使用的数据用来腾出空闲位置。您在真实的面试中是

2015-08-08 13:46:09 2084

原创 LintCode-编辑距离

给出两个单词word1和word2，计算出将word1 转换为word2的最少操作次数。你总共三种操作方法：插入一个字符删除一个字符替换一个字符您在真实的面试中是否遇到过这个题？ Yes样例给出 work1="mart" 和 work2="karma"返回 3标签 Expand 相关题目 Expand

2015-06-27 16:48:09 2220 1

原创 LintCode-排序矩阵中的从小到大第k个数

在一个排序矩阵中找从小到大的第 k 个整数。排序矩阵的定义为：每一行递增，每一列也递增。您在真实的面试中是否遇到过这个题？ Yes样例给出 k = 4 和一个排序矩阵：[ [1 ,5 ,7], [3 ,7 ,8], [4 ,8 ,9],]返回 5。挑战使用O(k log n)的方法，n为矩阵的宽度和高度中的最大值。

2015-06-27 15:56:00 4382

原创 LintCode-最大子数组差

给定一个整数数组，找出两个不重叠的子数组A和B，使两个子数组和的差的绝对值|SUM(A) - SUM(B)|最大。返回这个最大的差值。您在真实的面试中是否遇到过这个题？ Yes样例给出数组[1, 2, -3, 1]，返回 6注意子数组最少包含一个数挑战时间复杂度为O(n)，空间复杂度为O(n)标签

2015-06-26 19:42:33 3641

原创 LintCode-搜索区间

给定一个包含 n 个整数的排序数组，找出给定目标值 target 的起始和结束位置。如果目标值不在数组中，则返回[-1, -1]您在真实的面试中是否遇到过这个题？ Yes样例给出[5, 7, 7, 8, 8, 10]和目标值target=8,返回[3, 4]挑战时间复杂度 O(log n)标签 Expand

2015-06-25 23:14:16 1398

原创 LintCode-搜索旋转排序数组 II

跟进“搜索旋转排序数组”，假如有重复元素又将如何？是否会影响运行时间复杂度？如何影响？为何会影响？写出一个函数判断给定的目标值是否出现在数组中。您在真实的面试中是否遇到过这个题？ Yes样例给出[3,4,4,5,7,0,1,2]和target=4，返回 true标签 Expand 分析：有重复数据还是很蛋疼的，重点在于消

2015-06-25 22:03:11 1895 1

原创 LintCode-搜索旋转排序数组

假设有一个排序的按未知的旋转轴旋转的数组(比如，0 1 2 4 5 6 7 可能成为4 5 6 7 0 1 2)。给定一个目标值进行搜索，如果在数组中找到目标值返回数组中的索引位置，否则返回-1。你可以假设数组中不存在重复的元素。您在真实的面试中是否遇到过这个题？ Yes样例给出[4, 5, 1, 2, 3]和target=1，返回 2给出[4, 5

2015-06-25 21:03:54 2630

原创 LintCode-二叉树的层次遍历 II

给出一棵二叉树，返回其节点值从底向上的层次序遍历（按从叶节点所在层到根节点所在的层遍历，然后逐层从左往右遍历）您在真实的面试中是否遇到过这个题？ Yes样例给出一棵二叉树 {3,9,20,#,#,15,7}, 3 / \ 9 20 / \ 15 7按照从下往上的层次遍历为：[ [15,7], [9,20]

2015-06-25 19:18:18 2198

原创 LintCode-寻找峰值

你给出一个整数数组(size为n)，其具有以下特点：相邻位置的数字是不同的A[0] A[n - 1]假定P是峰值的位置则满足A[P] > A[P-1]且A[P] > A[P+1]，返回数组中任意一个峰值的位置。您在真实的面试中是否遇到过这个题？ Yes样例给出数组[1, 2, 1, 3, 4, 5, 7, 6]返回1, 即数值 2 所在位置

2015-06-25 19:03:51 2908 4

原创 LintCode-最长公共前缀

给k个字符串，求出他们的最长公共前缀(LCP)您在真实的面试中是否遇到过这个题？ Yes样例在 "ABCD" "ABEF" 和 "ACEF" 中, LCP 为 "A"在 "ABCDEFG", "ABCEFG", "ABCEFA" 中, LCP 为 "ABC"标签 Expand 分析：就是直接两两计算前缀。。。代码：cl

2015-06-25 18:55:33 7392 1

原创 LintCode-最长公共子串

给出两个字符串，找到最长公共子串，并返回其长度。您在真实的面试中是否遇到过这个题？ Yes样例给出A=“ABCD”，B=“CBCE”，返回 2注意子串的字符应该连续的出现在原字符串中，这与子序列有所不同。标签 Expand 相关题目 Expand 分析：注意是子串，不是子序列，当然做法肯定也是动态

2015-06-25 18:49:35 2267 1

空空如也

空空如也