- 博客(53)
- 收藏
- 关注
RSS订阅原创 博客搬家
决定换个地方写博客了。[我的简书博客地址] http://www.jianshu.com/users/00f160f2edca/latest_articles
2016-03-21 22:57:46
508
原创 [leetcode] Burst Balloons
题目描述：Given n balloons, indexed from 0 to n-1. Each balloon is painted with a number on it represented by array nums. You are asked to burst all the balloons. If the you burst balloon i you wil
2016-02-25 00:00:17
806
原创 [leetcode] Divide and Conquer
下面简单聊聊leetcode中的两道类似的DC的题目。之所以来写博客，是因为它们的思路确实与以往遇到的简单的DC有所不同。1. Count of range sumGiven an integer array nums, return the number of range sums that lie in [lower, upper] inclusive.Ra
2016-02-24 23:55:46
1502
原创 [leetcode] Implement Trie (Prefix Tree)
Problem Description:Implement a trie with insert, search, and startsWith methods.Note:You may assume that all inputs are consist of lowercase letters a-z.继续我的每天水题之路。这是一道小的设计题，设计一个字典树
2015-11-04 22:37:48
572
原创 [leetcode] Isomorphic Strings
Problem Description:Given two strings s and t, determine if they are isomorphic.Two strings are isomorphic if the characters in s can be replaced to get t.All occurrences of a character
2015-11-03 00:24:36
421
原创 [leetcode] Summary of Linked List (1)
今天总结leetcode上那些与Linked List有关的题目。1. Reverse Linked List题目大意：将单链表反转（可以分别考虑递归和迭代的方式）基本思路：（1）递归方式，对于某个待反转的list，先递归调用函数得到list->next的反转，然后将list节点加到list->next节点之后即可。注意递归出口会返回反转后的链表的头指针，原始链表的头指针变
2015-10-29 22:01:04
549
原创 [leetcode] Summary of Bit Manipulation
今天刷了几道题，发现leetcode现在都有分类了，所以顺便把以前刷过的bit manipulation相关的题目都看了一遍，下面简单总结一下。1. Single Number题目大意：在给定的整数数组中，除了一个数字之外，其他数字都出现了两次，现让求出只出现一次的那个数字。基本思想：遍历数组一次，将所有数字依次进行异或运算，结果即为所求的数字。因为其他数字都恰好出现了两次，异或得0。
2015-10-28 00:25:39
628
原创 [leetcode] Number of Islands
Problem Description:Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vert
2015-10-25 23:04:55
576
原创 [leetcode] Binary Tree Right Side View
Problem Description:Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.For example:Given the followin
2015-10-25 01:32:54
385
原创 [leetcode] House Robber
Problem Description: You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them
2015-10-24 01:05:00
342
原创 [leetcode] Rotate and Reverse
今天刷了两道比较简单的题目，恰好都与reverse有关，所以就一起简单说说了。（1）字符串的反转。“abcd”反转后变成“dcba”，这是最最基础的reverse了，也有文章分享过多种方法。但基本思路都差不多，就是依次把第一个元素与倒数第一个交换，第二个与倒数第二个交换，...，直至第n/2个为止。（2）Reverse Integer。将整数反转，如123变成321。可以把整数转换成字符串
2015-10-22 22:38:28
688
原创 [leetcode] Best Time to Buy and Sell Stock IV
Problem Description:Say you have an array for which the ith element is the price of a given stock on day i.Design an algorithm to find the maximum profit. You may complete at most k transact
2015-10-20 23:50:23
501
原创 [leetcode] Repeated DNA Sequences
Problem Description: All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: "ACGAATTCCG". When studying DNA, it is sometimes useful to identify repeated seque
2015-10-19 22:53:11
458
原创 [leetcode] Largest Number
Problem Description:Given a list of non negative integers, arrange them such that they form the largest number.For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330.
2015-10-19 00:26:33
601
原创 硕士学位论文多级标题编号与图表编号
尽管自己对word并不陌生，但是折腾起硕士学位论文来还是费了九牛二虎之力才明白这些，下面就自己遇到的问题，说说一些疑难问题的解决方案。1. 多级标题编号的问题由于我们的学位论文要求章节按照汉语数字“一、二、三...”来编号，其他小标题则依旧是"1.1, 1.2, ...1.2.1, ..."这种编号，而直接运用word中的多级标题编号会出现“一.1”这种异类。所以，如何实现这种
2015-04-22 22:12:45
37686
4
原创 Yale开放课程博弈论24
24. 拍卖和获奖者的诅咒（最后一节课）在之前所讲的博弈中，我们都知道对手是什么样的人，双方的收益如何。这节所讲的不一样的是，未知对手收益的博弈。如拍卖，在竞争被拍卖的商品时，你不知道别人认为被拍卖的商品的价值。关于拍卖，一个极端是它具有公共价值V，另一个极端是私人价值Vi。其中公共价值表示，被出售商品的价格对所有的人来说都是一样的，如油井的开采权。而私人价值，表示每个人认为的价值
2015-03-29 18:40:08
639
1
原创 Yale开放课程博弈论23
23. 沉默，信令和苦难教育1. 信息能够被证实的情况我们来重新看看古诺博弈，有两家企业A和B竞争同一产品的产量，假设对于B，边际成本是Cm，企业A有三种情况：Ch（比Cm更高一点）、Cm、Cl（Cm-eps）。现在B的成本Cm是公开的，A有机会选择是否把自己的成本告诉B（无需任何额外开销）。问题是，A是否应该告诉B自己的成本？我们可以对照古诺曲线来分析这一
2015-03-21 21:17:46
962
2
原创 STL map内存释放的问题
今天在程序里面有这么一段糟糕的代码：while() // cout << Memory1: Type *a = new Type[MAX_N]; // cout << Memory2: map > m; for() m.insert(...); // cout << Memory3: delete[
2015-02-07 22:00:01
5420
原创 [Python]Windows下安装PIL遇到的问题
以下来说说艰难的安装PIL的过程，中途遇到一些问题，虽然网上很多类似的问题解答，可都是一样的只告诉很简单的“如何处理”一下就可以了，但是我就是完成不了这一步！先介绍一下最终完成时我的环境，windows 7 64位系统、python 2.7.9 32位和Pillow-2.7.0.win32-py2.7。首先，菜鸟学习PIL，直接按照廖雪峰老师的python教程上写的方法安装
2015-01-08 18:37:09
18692
8
原创 [Python] collections — High-performance container datatypes
python中基础的数据结构除了str, int, float等超简单类型外，还提供了类似于C++中STL库里的一些较高级的数据结构，如tuple, list, dict和set。而collections则是Python中内建的一个集合模块，提供了一些更加高级的集合类。namedtuple (factory function for creating tuple subcl
2015-01-06 19:44:38
693
原创 Yale开放课程博弈论22
22. 作弊、惩罚和外包 假设我和杰克进行持续的交易，我给他提供水果，他给我提供蔬菜。按照上节课讲的扳机策略，一旦我背叛他，那么在之后的交易中他会一直背叛我。 那么对于今天我是选择合作还是欺骗？有下面这样一个公式：今天我欺骗杰克的动机小于 （明天我和杰克合作的前景）-(明天杰克欺骗我的惩罚) gain if cheat today ≤ （value ofrelati
2015-01-02 14:20:41
573
原创 Yale开放课程博弈论21
21. 合作与结局这节课围绕的问题是Repeated interaction。在一个正在进行的关系中，对于将来奖励的承诺和未来惩罚的威胁，可能会激励现在产生“好行为”。从囚徒困境开始讲起，这个双人博弈中，双方可选的策略是合作或者背叛。 cooperationdefectcooperation2,2-1,3d
2014-12-28 11:23:46
980
原创 Yale开放课程博弈论20
20. 战争的消耗今天讨论的博弈问题是：2个参与者，每个阶段每个参与者各自选择攻击或者退出（同时选择），当博弈中有一方退出则游戏结束。好消息：如果另一方先退出，你将获得奖励V；坏消息：每个阶段，如果参与者双方都攻击，每人都要付出代价C；（假设V > C）为了使得游戏更有趣，我们加入一个条件：两人同时退出，他们都会得到0。老师在同学们当中选择了三组同学进行实验，得到的结果
2014-11-22 19:23:10
717
原创 尼姆（Nim）游戏
不用博弈论的概念，通俗地讲一下尼姆（Nim）游戏现有若干堆石子，每堆石子的数量都是有限的，双人进行游戏，每个人在每次行动的时候可以“选择一堆石子并拿走若干颗，不能不拿”，没有石子可拿的人为输。是否有先手必胜的策略？直接考虑这个问题有点难度，我们还是从最简单的只有两堆石子来讲起吧！（a）当只有两堆石子，若两堆石子的数目一样多，那么先手必输。因为不管先手选择那一堆拿多少个，后手
2014-10-31 22:55:10
1708
2
原创 Yale开放课程博弈论19
19. 招商引资和战略投资 上一讲我们讲了太多概念，今天主要讲三个案例。案例一 把全班同学分成两组进行游戏，大部分同学的选择趋向于[U, l, u]。逆向归纳法分析：参与者1有第二次选择的机会的话，会选择u，因为4（选择u）比3（选择d）好。对于参与者2，如果他选择r的话游戏结束，其收益为2，而他根据逆向归纳法他知道若自己选择l的话参与者1肯定会选择u，那时自己的收益是
2014-10-25 11:13:15
1212
原创 Yale开放课程博弈论18
18. 信息集合和子博弈完美 回顾一下我们之前介绍的博弈论，我们先介绍了同步决策，即当我做决策时并不知道你会做什么决策，参与者同时做出决策。之后又介绍了序贯博弈，即参与者按照顺序做出决策，且我做决策之前能够知道你将会有那些应对策略。而今天我们介绍的博弈中则会包含这两种情况。 上图所示即为我们今天要介绍的一种博弈，它与之前唯一的不同在于中间出现了一条红色的虚线。现在我们引入“信息
2014-10-22 21:23:15
731
原创 将一根木棍分成三段，求这三段构成三角形的概率
题目：将一根木棍分成三段，求这三段构成三角形的概率。方法一：设线段长度为a，任意分成三段长分别为x，y和a-x-y，显然有x>0，y>0，a-x-y>0，将这三个约束条件画到(x,y)二维平面坐标系上，这三条直线围成了一个直角三角形即为可行域，其面积为(1/2)a^2。 而这三段长能构成三角形的条件是：任意两边之和大于第三边，也就是下面三个不等式得同时成立：x
2014-10-22 12:55:12
33858
10
原创 关于数组的面试题总结(二)
1.给定一个无序的整型数组，求出最小的k个数两种思路：（1）如果所有的数组可以全部装入内存的话，采用快速排序的思想进行划分，不断向第k个小的数靠近，当得到第k小的数(key）时就相当于得到了最小的k个数，因为划分的时候保证了比key小的数全部放在了左边。平均时间复杂度为O(N)。（2）当数组太大无法一次性装入内存时，上面的方法失效，可以维持一个大小为k的大顶堆，取前k个数建堆后依次
2014-09-30 11:33:28
620
原创 多重继承与虚继承
以下部分内容摘抄自《C++primer 中文版 4》多重继承（multiple inheritance）是从多于一个直接基类派生类的能力，多重继承的派生类继承其所有父类的属性。简而言之，就是采用多重继承的派生类有至少两个父类。多重继承的方式：至于C++中该不该使用多重继承，也一直是个备受争议的问题，《Effective C++》作者也没有正面上给出选择，而是说要
2014-09-29 18:07:02
584
原创 Yale开放课程博弈论17
17. 最后通牒和议价（utimatumsand bargaining） 一个简单的模型，两个参与人，参与者1给出提供分配1美元的条件（自己得到S，对方1-S），参与者2可以接受这个条件（1得到S，2得到1-S），或者拒绝（两者收益都是0）。 老师在班上随机选择了三组同学进行这个实验，其中提出给参与者2的是1美分和30美分的都被拒绝了，而给出50美分的被接受了。现实中很多人会拒
2014-09-28 21:57:38
750
原创 Yale开放课程博弈论16
16. 落后的感应------声誉与决斗回顾上节课最后的例子，垄断者与欲进入市场者的博弈，经过我们的分析可以得到2个纳什均衡(in, NF)和(out, F)，下面我们来做个游戏：现在假设埃里同学有家连锁的匹萨店垄断着市场，另外10个同学都伺机进入该市场，老师依次问这10个同学选择是否进入市场，然后问埃里是否会对他们进行打击。结果是1选择进入，被打击；2、3、4、5、6选择不进入，7、8选
2014-09-18 20:43:24
586
原创 关于数组的面试题总结(一)
关于数组的面试题总结(一)：1. 二维数组中的查找在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。 2. 采用递归的方法求数组所有元素的和3. 求数组中出现次数超过一半的数字4. 旋转数组（包括重复元素）的最小数字
2014-09-16 21:41:13
2275
2
原创 Yale开放课程博弈论15
15. 落后的感应------国际象棋、战略和可信的威胁 通过上节课最后的小游戏尼姆博弈（Nim Game）来承上启下。这个游戏的结论是当两堆石子数目一致时，后行者每次选择与先行者对称的策略（先行者选择A堆的x个，后行者就选择B堆的x个）来取胜。当两堆石子数目不一致时，先行者选择较多的那堆石子将两堆数目变得一致，即先行优势可以在自己进行一轮后将局势转换成后行优势。 这里要介绍策梅洛
2014-09-16 19:15:11
904
原创 Yale开放课程博弈论14
14. 落后的感应-------承诺，间谍和先行者优势 复习古诺模型，两家厂商的产量竞争，今天我们以序贯博弈的角度再来看看这个问题。如果厂家1先采取行动，厂家2根据厂家1的选择再坐决定，结果会怎样？这是典型的斯塔克伯模型。 这里是先决定的有优势，还是后决定的有优势？如何解决，逆向归纳法，从结果开始倒推。由于厂家1知道厂家2对于厂家1的决策的最优应对策略，所以厂家1应该生
2014-09-13 23:05:31
761
原创 笔试题next_permutation & Largest Rectangle in Histogram
看了看去年有道的2013年10月北邮站的笔试题，第一题很简单但unicode字符的输出没实现成功（题目见http://www.cnblogs.com/dancingrain/p/3405186.html），后两道编程题都很经典，在leetcode上遇到过，但是还是记不清了，所以决定写一写，争取把思路说清楚，把方法变成自己的。 第二道，对于给定的正整数n，1至n个数的全排列有n!个，对于任意
2014-09-12 23:36:34
920
原创 [算法]子数组之和问题
问题描述：给定一个含有n个元素的整形数组a，再给定一个和target，求出数组中满足给定和的所有元素组合的数目。举个例子，设有数组a[5] = { 1, 2, 3, 4, 5}，sum = 8，则满足和为8的组合数为3，即{1,2,5}, {1,3,4}, {3, 5}。http://www.cnblogs.com/graphics/archive/2011/07/14/2105195.htm
2014-09-10 22:39:22
1176
原创 Yale开放课程博弈论13
贯序博弈，道德风险、奖励和饥饿的狮子 与之前的博弈游戏都不同的是，这节课要讲的借方与贷方的博弈是贯序博弈（sequential move game）。 不同于之前的是，这里是行为有顺序的博弈，关键是在博弈中参与者2在做决定之前可以看到参与者1的决定，而且参与者1知道这种情况。 我们对这种博弈的分析方式也不再是画矩阵，而是画树形图。 一个关于借方和贷方博弈的小游戏，这
2014-09-10 22:32:33
1004
原创 [算法]Fibonacci数列O(n)和O(lgn)的解法
九度oj题目1387：斐波那契数列大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。斐波那契数列的定义如下：输入：输入可能包含多个测试样例，对于每个测试案例，输入包括一个整数n(1输出：对应每个测试案例，输出第n项斐波那契数列的值。样例输入：3样例输出：2
2014-09-09 22:24:48
1814
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人