腾讯微信
腾讯微信面试题--实现时间复杂度为O(1)的栈 2013-02-26
去面试微信实习，遇到这道算法题，当时被卡住，故今天把它写出来做下知识整理，
原题：实现一个栈，满足min() pop() push()方法的时间复杂度都为O(1).( min()返回栈中最小元素 )
思路1：用一个变量minItem记录栈中的最小值，在push()中 每次加入一个item就跟minItem对比，item更小，只item赋给minItem，然后再min() 中直接return minItem;
这种思路没考虑在pop()过程中，对minItem的影响，当栈顶元素是minItem，执行pop() 后minItem就不知道指向谁了，因为栈只记录最小值而起，至于最小值之前那些大小关系都没记录
正确思路：为了实现更低的时间复杂度，我们都会想到用空间去换时间，所有这里增加一个数组来nextMinItem[index] 元素大小关系。如果当前最小值是 对象 item1 当push进来的item2比 item1更小，且元素个数从原本的a增加到a+1 这时候我们用我们就应该把item2这个更小的item赋给minItem 然后用nextMinItem[a+1] = item1 来记录 item2 后面的次小值，这样一来当item2 这个栈顶被pop()掉的话，我们就可以minItem = nextMinItem[a+1]，来恢复minItem。
package 腾讯面试题;
public class Stack {
private int itemCount = 0 ;
private Item minItem = null ;
private Item[] nextMinItem;
private Item stackTop = null ;
private int maxSize = 100 ;
public Stack() {
nextMinItem = new Item[maxSize];
}
class Item {
int Data;
Item nextItem;
public Item( int data) {
this .Data = data;
}
}
public boolean push(Item item) {
if (itemCount == maxSize) {
System.out.println( "栈已满" );
return false ;
}
itemCount++;
if (minItem == null ) {
minItem = item;
} else {
if (item.Data < minItem.Data) {
nextMinItem[itemCount] = minItem;
minItem = item;
}
}
item.nextItem = stackTop;
stackTop = item;
return true ;
}
public boolean pop() {
if (itemCount == 0 ) {
System.out.println( "栈是空的，无法出栈" );
return false ;
}
if (stackTop == minItem) {
minItem = nextMinItem[itemCount];
}
stackTop = stackTop.nextItem;
itemCount--;
return true ;
}
public Item min() {
if (itemCount == 0 ) {
System.out.println( "栈是空的，无最小值" );
return null ;
}
return minItem;
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Stack stack = new Stack();
stack.push(stack. new Item( 5 ));
System.out.println( "push:min=" + stack.min().Data+ " itemCount=" +stack.itemCount);
stack.push(stack. new Item( 4 ));
System.out.println( "push:min=" + stack.min().Data+ " itemCount=" +stack.itemCount);
stack.push(stack. new Item( 3 ));
System.out.println( "push:min=" + stack.min().Data+ " itemCount=" +stack.itemCount);
stack.push(stack. new Item( 2 ));
System.out.println( "push:min=" + stack.min().Data+ " itemCount=" +stack.itemCount);
stack.push(stack. new Item( 1 ));
System.out.println( "push:min=" + stack.min().Data+ " itemCount=" +stack.itemCount);
stack.pop();
System.out.println( "pop :min=" + stack.min().Data+ " itemCount=" +stack.itemCount);
stack.pop();
System.out.println( "pop :min=" + stack.min().Data+ " itemCount=" +stack.itemCount);
stack.pop();
System.out.println( "pop :min=" + stack.min().Data+ " itemCount=" +stack.itemCount);
stack.pop();
System.out.println( "pop :min=" + stack.min().Data+ " itemCount=" +stack.itemCount);
stack.pop();
System.out.println( "栈结构为：\n|____1_____|\n|____2_____|\n|____3_____|\n|____4_____|\n|____5_____|\n" );
}
}
运行结果：
push:min= 5 itemCount= 1
push:min= 4 itemCount= 2
push:min= 3 itemCount= 3
push:min= 2 itemCount= 4
push:min= 1 itemCount= 5
pop :min= 2 itemCount= 4
pop :min= 3 itemCount= 3
pop :min= 4 itemCount= 2
pop :min= 5 itemCount= 1
栈结构为：
|____1_____|
|____2_____|
|____3_____|
|____4_____|
|____5_____|
Lock不住的BUG，神一般无解的BUG（XX正由另一进程使用，因此该进程无法访问该文件）
对于运行中的 秋色园 站点，偶尔的不经常，我都会做以下的几件开发者该常做的事：
1 ：查看网站的事件日志（看看有没有网站未发现的异常，有的话要处理）。
2 ：查看被捕获的异常日志（看看都是什么情况引发的，有的话要处理）。
3 ：查看数据库执行语句异常日志（看看都有啥情况）。
今天早些时候，看了下日志，对于一条比较熟悉，但一直没怎么处理的日志，突然有了想处理掉它的想法：
log:http://www.cyqdata.com/search/cnblogs/finger+print
------------------------
[WriteException]:文件“D:\*\TableSchema\CYQ.Data.TableSchema_Sql.qblog.Blog_User.ts”正由另一进程使用，因此该进程无法访问该文件。:
在 System.IO.__Error.WinIOError(Int32 errorCode, String maybeFullPath)
在 System.IO.FileStream.Init(String path, FileMode mode, FileAccess access, Int32 rights, Boolean useRights, FileShare share, Int32 bufferSize, FileOptions options, SECURITY_ATTRIBUTES secAttrs, String msgPath, Boolean bFromProxy)
在 System.IO.FileStream..ctor(String path, FileMode mode, FileAccess access, FileShare share, Int32 bufferSize, FileOptions options)
在 System.IO.StreamWriter.CreateFile(String path, Boolean append)
在 System.IO.StreamWriter..ctor(String path, Boolean append, Encoding encoding, Int32 bufferSize)
在 System.IO.StreamWriter..ctor(String path, Boolean append)
在 CYQ.Data.Tool.IOHelper.Save(String fileName, String text, Boolean isAppend)
在 System.IO.__Error.WinIOError(Int32 errorCode, String maybeFullPath)
在 System.IO.FileStream.Init(String path, FileMode mode, FileAccess access, Int32 rights, Boolean useRights, FileShare share, Int32 bufferSize, FileOptions options, SECURITY_ATTRIBUTES secAttrs, String msgPath, Boolean bFromProxy)
在 System.IO.FileStream..ctor(String path, FileMode mode, FileAccess access, FileShare share, Int32 bufferSize, FileOptions options)
在 System.IO.StreamWriter.CreateFile(String path, Boolean append)
在 System.IO.StreamWriter..ctor(String path, Boolean append, Encoding encoding, Int32 bufferSize)
在 System.IO.StreamWriter..ctor(String path, Boolean append)
在 CYQ.Data.Tool.IOHelper.Save(String fileName, String text, Boolean isAppend)
关于这个错误的小小解释：
这个错误，其实就是对IO写文件操作加了try catch ，然后记录了下来，根据错误的直观提示：
既然是进程性错误，理想当然的推想是应用程序池在回收时，产生的另一个进程，刚好写文件时和另一个未回收完成的进程同时写引发的异常，被记录了。
我就想了一个，通过增加进程间的互斥量，来解决多进程间并发解决方案：
static System.Threading.Semaphore _mutex = new System.Threading.Semaphore( 1 , 1 , " IOHelper.Save " );
private static bool Save( string fileName, string text, bool isAppend)
{
try
{
if (_mutex.WaitOne( 2000 , false )) // 进程间同步。
{
using (StreamWriter writer = new StreamWriter(fileName, isAppend))
{
writer.Write(text);
}
}
return true ;
}
catch (Exception err)
{
Log.WriteLogToTxt(err);
}
finally
{
try
{
_mutex.Release();
}
catch
{
}
}
return false ;
}
写完代码，我建了个项目，写个Demo，测试下多进程的并发问题， 代码很简单，一个按钮点击，开一个线程，运行以下这段代码：
string path = AppDomain.CurrentDomain.BaseDirectory + " a.ts " ;
while ( true )
{
IOHelper.Save(path, " test " , true );
}
线程一开，一个死循环，不停写文件。
运行了一下，我查看文件是否正常创建，于是我打开那文件，看日志写进了没有，发现很正常写进了，于是又回到代码处。
然后又开了一个软件，又点了运行，一个神奇的BUG就这样被我触发了：
刷的一下，抛出异常：
"文件“F:\\*\\bin\\Debug\\a.ts”正由另一进程使用，因此该进程无法访问该文件。"
神奇的BUG的被触发后，神一般的无解：
1 ：不管我怎么写代码，仅单线程，Lock，双重Lock，还是Mutex，还是混合用，运行几秒后，都抛这个异常。
2 ：然后我加了线程休眠，发现加到Thread.Slee( 100 )以下又正常，这个正常让我怀疑，难道文件关闭，还有延时功能？
3 ：通过Reflect看源码，查了几个基类，也没见着特殊。。。怀疑得不到解决，纳闷升级。。。
3 ：之后我在闪存里了点条闪存说这问题，也在QQ群发了点相似的内容。。。反正就有点纳闷中无解。
4 ：几小时之后，我放弃了，你妹夫的，不弄了。。神一般的简直无解。
5 ：感觉东西开的太多了，我就关掉了一些，其中包括文件夹。
6 ：写代码的天性，问题不解决，又回头折腾。
问题失踪了？？？？
这回运行，一切正常了，产生多少并发也没报那错。。。你妹的咋回事，这么神奇？？？？
于是我又去看了那个创建的文件有没有问题。。。。
回头一运行。。你妹夫的，又抛异常了。。。
突然意识到了什么，经过几个抛异常，不抛异常的轮回折腾，终发现这个神般无解的的BUG：
原来是查看文件时，等于该文件被鼠标focus选定了原因,处于被forcus状态的文件，频繁的写入就抛那异常了。
这BUG多无解，你妹：
版权声明：本文原创发表于 博客园 ，作者为 路过秋天 本文欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则视为侵权。
分类: 记录点滴
标签: IO写异常 , 正由另一进程使用
作者： Leo_wl
出处： http://www.cnblogs.com/Leo_wl/
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。
版权信息