Tag name:C++

[LeetCode] Reverse Words in a String

03/10/2014 / 1 Comment

在进入正题之前先扯点别的,微软campus interview就被问的这题,当时写的不够好,主要面试官要求是char *参数,然后我std::string用多了之后根本搞不清,连strlen都忘了,然后竟然以为sizeof字符串/sizeof char 之后再减一能得到结果…实际上如果字符串是用char数组的话就可以,是char *的话sizeof一下得出的是指针的长度肯定不行,并且注意下面的代码

得出的结果, b为5,而c为3. 原因是char[]是会被编译器解析为char *的,所以参数类型 []和*并没有区别,都是当做*来看待,可以试试重载某一个函数,将其中的*换成[],或者[]换成*, 编译器会告诉你俩函数是同一个函数,func xxx already has a body.
再扯几个别的:(感觉其实都是特基础的东西,当时没学好啊!)
为什么写成5[a]也能访问到a[5]呢?忘记在什么地方看到了,后来自己试了一下果然可以,原因是x[y]会被解析成*(x+y),而[y]x自然就是*(y+x)所以就不会有区别了
可能有人觉得x[y]应该是*(&x[0]+y)才对,但实际上,数组本身作为右值的时候,被解析为数组第一个元素的指针,但左值则还是指整个数组的存储空间。可以看以下例子:

Ok下面完整的题(我面试的时候面试官也只给了模糊的条件,得确认string是什么string, 要不要删多余空格等等)
Given an input string, reverse the string word by word.

For example,
Given s = “the sky is blue”,
return “blue is sky the”.

Clarification:
What constitutes a word?
A sequence of non-space characters constitutes a word.
Could the input string contain leading or trailing spaces?
Yes. However, your reversed string should not contain leading or trailing spaces.
How about multiple spaces between two words?
Reduce them to a single space in the reversed string.

这里我写成了俩函数,java里的string有个trim()所以我就想着也写一个,实际上,在trim的时候,对于空格的位置已经是查找过的了,所以在第二次reverse的时候完全可以借用位置信息,当然这又是空间换时间的问题了。
由于LeetCode上给的输入参数是std::string,所以我也就偷个懒直接调用std::reverse了,有时间再写个偏纯C的,不过纯C挺蛋疼!

OpenCV:Meet Lena

03/06/2014 / 2 Comments

opencv第一讲,为大家带来OpenCV配置,图片读取、显示、存储,以及摄像头的调用。为了各路大神都能参考,我尽量使用鲁棒性较高的说法。

Step1: 配置OpenCV

OpenCV是Open Source Computer Vision Library的简称,SDK可从其官方网站下载,OpenCV SDK最新版本下载地址

windows的环境配置:下载完成后,我将其解压到D盘,右键点击计算机-属性-高级系统设置-环境变量-添加用户变量Path,值D:\opencv\build\x86\vc12\bin (如果已有Path变量的话,就直接在现有值的后面加个; 然后加上D:\opencv\build\x86\vc12\bin)这个值根据不同情况调整,如果是64位的就x64,如果是vs2010就是vc10,vs2012就是vc11,搞定这些之后就可以开始配置vs里面的开发环境了。

vs20xx环境配置:新建一个win32 控制台程序(win32 console application)或者 win32项目(win32 project)—控制台应用程序&空项目—完成。右键项目名称—属性—vc++目录—在包含目录(include directory)中加上D:\opencv\build\include D:\opencv\build\include\opencv D:\opencv\build\include\opencv2三项,在库目录(library directory)中加上D:\opencv\build\x86\vc12\lib。 然后选择链接器(linker)—输入(input)-加上opencv_core248d.lib opencv_highgui248d.lib。

include directory

library directory

linker-input

Step2: 测试OpenCV

测试:新建一个cpp文件,加入以下代码。然后下载lena.jpg,放到cpp所在目录下,ctrl+F5。

Step3: 

接下来讲一下怎么利用摄像头自拍

下期预告:opencv实现滤镜

[LeetCode Summary] Remove Duplicates

02/19/2014 / No Comments

先看最简单的Remove Element:
Given an array and a value, remove all instances of that value in place and return the new length.

The order of elements can be changed. It doesn’t matter what you leave beyond the new length.
这里需要理解的是给的是数组,所以新长度以后的元素都不用管了,例如给[1,2,3,4,5]要remove 3,那么结果只要是[1,2,4,5,x],并且返回新长度4就行,x是什么并不重要

下面是Remove Duplicates From Array
Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

For example,
Given input array A = [1,1,2],

Your function should return length = 2, and A is now [1,2].

然后变形成可以允许duplicate出现2次,把超过2次的删掉,这个也非常简单,这回用multiset
Follow up for “Remove Duplicates”:
What if duplicates are allowed at most twice?

For example,
Given sorted array A = [1,1,1,2,2,3],

Your function should return length = 5, and A is now [1,1,2,2,3].

下面看看链表,由于题目都是单链表,所以删除某一个元素需要指向该元素前一个元素的指针,这样的话头节点就比较蛋疼了,解决方法是自己定义一个头节点,使其next等于原来的头节点,这样的话原来的头节点就跟普通节点一样的操作了。
Given a sorted linked list, delete all duplicates such that each element appear only once.

For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3

最后这题是要求一旦有duplicates,就删掉所有的instance,我的办法是用两个set,然后对链表扫两遍,好像有点耗时间又有点耗空间,待改进
Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

[LeetCode] Best Time to Buy and Sell Stock I, II and III

02/18/2014 / 3 Comments

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.

I: If you were only permitted to complete at most one transaction
这个非常简单,扫一遍记录下当前最小价格,以及当前能获得的最大利润就行。
这里有个小小的代码风格问题,有人喜欢把minPrice设为数组第一个数,然后从数组第二个数开始迭代,我就喜欢设成INT_MAX, 可以看到我这样就不用判断数组是否为空,但是需要从数组第一个数开始迭代。

II: You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
这个需要想通的一点就是,假设股票每天都在涨价,那么每天买入/隔天卖出的总收益,是和第一天买入最后一天卖出的收益等价的。假设股票跌价了的话(第i+1天的价格比第i天的高),那就不买,就不计入总收益了。(一开始比较糊涂,一直在想跌价的时候要等到跌到最低再买入等问题,后来发现这其实根本就不是买股票的问题,股票哪有预先就知道接下来30天的价格的!所以所有的股票策略都不适用啊)

III: You may complete at most two transactions, but you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
第三题必须要读清题,题目说是最多可以完成两笔交易,就是说买入2次卖出2次,并且买第2次之前必须卖掉第一次买的(我一开始还想复杂了,忽略了这个条件)。 既然买入第二次之前必须卖掉第一次买的,那么实际上问题就变成了我需要找到一个i,使得0到i天内那笔交易的最大收益与i到n-1天内那笔交易的最大收益之和最大。这样的话每个单独区间的最大收益在问题I中就已经解决了。接下来就需要考虑效率问题,这里有个神奇的地方是参考别人来的(Link)。 我第一遍的代码特别蛋疼,是O(n^2)的,而这个神奇的方法是O(n)。 这里需要扫三遍:
第一遍从前往后扫,得出在第i天之前进行的那笔交易一共能赚多少
第二遍从后往前扫,注意第i天到第n天最多能赚多少,反过来就是从第n天倒回去到第i天最多能亏多少
第三遍扫之前存下的俩数组,得出最大利润

[LeetCode Summary] Tree Traversal欧冠购彩yabo88

02/10/2014 / 1 Comment

写一下树的各种遍历以及用遍历结果建树之类的总结
首先前提是树的数据结构就是像下面这样的,后面所有的解法都不考虑在数据结构上做改变(加指向父节点的指针之类的)

递归的方法是最intuitive和readable的,例如中序遍历就是访问一个节点之前要先访问其左子树,然后访问该节点,然后再访问右子树。
前序和后续也是类似,只要交换访问语句的顺序就可以。递归方法时间复杂度都是O(n),空间复杂度则是递归深度,即树的高度O(h)

非递归方法的话,比较容易想到的是用栈+迭代
非递归前序遍历:
方法1是从Programming Interview Exposed看到的,其思路是:
1 先把根节点进栈
2 当栈不为空时,取顶部节点出栈
2.1 访问该节点
2.2 如果右孩子存在,将右孩子压入栈
2.3 如果左孩子存在,将左孩子压入栈

方法1我一开始没想通它是怎么模拟的递归,因为当我想把他套用到中序的非递归遍历的时候,发现是行不通的。之后分析了一下,由于前序遍历根节点遍历完之后,就不再需要使用了,而上面的方法1正是抓住了这个特点,根节点访问完就出栈
而下面这种方法2也是用栈来完成非递归前序遍历,但方法2稍加修改就可以适用于中序遍历(实际上这个方法就是我写中序遍历的时候想到的)
并且这个方法的思路看起来才最接近递归的过程
1 先访问当前节点,再将当前节点压入栈
2 若当前节点有左孩子,对其左孩子重复第一步,直到左孩子为空
3 从栈中取出前一个访问的节点,将其右孩子设为当前节点

未完待续

[LeetCode] Sort List

01/30/2014 / 4 Comments

这个在LeetCode上有两题,一题要求用insertion sort,一提要求用O(nlogn)的方法
做insertion sort的时候脑子进水想成了selection sort,虽然写的没bug,但输入稍微大点的时候OJ说Time Limit Exceeded. 但按理selection sort和 insertion sort都是n^2的,咋会超时呢,先贴代码上来吧,想不通
最蛋疼的就是single linked list, 拿删除来说,你要删除当前节点是没办法做到的,你只能删除当前节点的next节点。所以每次都要去检查cur->next这个节点,若需要删除再把cur->next->next赋值给cur->next。
3/10 更新:忘记来更新这个了,插入排序前几周写好了,具体的话必须把list分成排序和未排序的两段,最开始的时候没有注意将第一段的末尾元素next置空导致cyclic蛋疼的好久

[LeetCode] Spiral Matrix II

01/28/2014 / 4 Comments

Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.

For example,
Given n = 3,

You should return the following matrix:
[
[ 1, 2, 3 ],
[ 8, 9, 4 ],
[ 7, 6, 5 ]
]

这种题感觉刚学C++的时候就做过,而且很心烦。我的办法还是先画个图
matrix

因为我的想法是代码肯定是在给当前格子赋值的时候,再去对i或j做增减来到达下一个格子(改变方向),所以图中显示的是对当前格子赋值的时候,目前的行走方向是怎样的。

根据这个图,我第一个想法是设一个direction来判断下一步怎么走。然后的问题是如何判断何时应该改变direction,于是我又观察了一下,最开始一个direction走了n-1步,之后分别是n-2,n-2,n-3,n-3,n-4,n-4这样子,也就是说只有当当前direction为向左和向右的时候,下一个direction走的步数会变少。于是我设了一个step来记录当前走了多少步和一个maxStep记录最大布数。这样就是我第一个解法。

这个做法太烦了,后来又想到个简单点的,这次的图里表示的是赋值完后应该进行什么操作,例如黄色区域都是i++。放到坐标系里画几条线的话,不同区域的i,j就符合一定的条件
matrix

[LeetCode] Median of Two Sorted Arrays

01/26/2014 / No Comments

There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

这题的做法肯定只能先合并两个sorted array然后再找中位数才能保证线性的时间复杂度

[LeetCode] Maximum/Minimum Depth of Binary Tree

01/25/2014 / No Comments

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

先做的maximum,maximum实际上就是树的深度或者层数level, 想的比较直接,节点为空depth为0,否则返回左右子树depth中较大的那个+1

然后是minimum depth了,题是这样的
Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

一拿到感觉是一样的,节点为空返回0,否则返回左右子树中depth较小的那个+1

然后问题来了,像这样一棵树,当有一边的子树为空的时候,由于空节点返回0,那函数就认为下面这棵树的minimum depth 为1,而实际应该是4

                                        0

                                 /

                            1

                        /

                   2

                        \

                            3

所以在发现有一边的子树为空的时候,就应该去找另一边的最小长度,因为这一边是没有叶子节点的。

[LeetCode] Climbing Stairs (Fibonacci Sequence)

01/23/2014 / 2 Comments

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

假设N级阶梯有F(N)种走法,每种走法的最后一步是1步或者2步,那么F(N)可以看成是先走F(N-1)种走法,然后再走最后一步,以及先走F(N-2)种走法,然后再走最后两步,于是F(N)=F(N-1)+F(N-2),实际上就是另外一个斐波那契数列,只不过F(1)=1,F(2)=2

问题其实很简单就能想通了,关键是如何实现最佳,经典的递归实现如下:

这个实现似乎是最糟糕的一种,时间复杂度中n在指数位置。(以上代码放到LeetCode上绝对是Runtime Err)他的坑爹之处就在于,对于同一个输入N,递归调用了好多次。例如要计算F(5),由于F(5)=F(4)+F(3),于是开始先算F(4)了,在算F(4)的过程中,F(3)肯定是被算过了,但实际上我们在F(4)的调用栈跑完之后,又还要去跑一遍F(3)

改进之后的想法是建一个数组把之前的结果都存起来,这样就可以回头lookup而不用再算了:

这个做法时间复杂度O(n),但空间复杂度似乎还不是最优,实际上在算完F(k)之后,F(k-2)就再也用不到了,让他出队就行了,这里就不用队列了,只有两个元素,迭代一下就OK:

最后,还可以直接用通项公式来做,不过由于double的精度问题,比较大的输入可能会有误差,推导过程我Google了一下,似乎感觉高中学过,对第一步构造等比数列有印象

不知道math里面的pow是怎么实现的,如果是乘法实现的话那时间复杂度也得是N在指数位置的级别,所以面试要真遇上这题,我决定就说一下知道有通项公式,就不这么写代码了。