江苏快三开奖结果

2012年5月25日

1. 找出一個數組中,最大的一段連續的數的和。Find out the subarray which has the largest sum.
例如:[1, -3, 2, -4 , 5 , 6, -2, 6, 7] 最大的和就是 22 = 5 + 6 - 2 + 6 +7.
解法如下:
int subMax(int [] a)
{
    int best = 0;
    int sum = 0;
    for(int i = 0; i < a.length; i++)
    {
         sum = sum + a[i];
         if(sum < 0 )
             sum = 0;
         else if(sum > best)
             best = sum;
    }
    return best;
}
想法就是一直加接下來的數,如果小于零就變為0,大于最大的數就更新。其中一點就是,如果遇到負數, 如果和不小于零就不用使sum為零。如果數組全部為負數,上面的代碼有點問題,但不改了。如果想知道 這個最大的和的序列是什么,只要稍微改變就可以了,不說了。

2. Ugly Number: 找出第n個能被2,3,5整除的數
例如:2, 3, 4, 5, 6, 9,10, 12, 15, 20, 25 ... 第3個是4, 第4個是5,第5個是6 ... 第200是?
想法:首先是從 1開始,2,3,5分別乘1,最小的是2,接下來就是2,2的位置進1,3和5的位置不變 再來一次,最小的是3,3的位置進1,2和5位置進1,再來一次,最小的是4,3和5的位置不變。。。
int uglyNum( int n)
{
   
int a = new int[n+1]
   a[
0= 1;
   
int i2 = 0, i3 = 0, i5 = 0;
   
int n2 = 0; n3 = 0; n5 = 0;
   
int m = 0;
   
for(int i = 0; i <= n; i++)
   {
      n2 
= a[i2] * 2;
      n3 
= a[i3] * 3;
      n5 
= a[i5] * 5;
      m 
= min(n2, n3, n5);
      
if(m == n2)
      {
         a[i] 
= m;
         i2
++;
      }
      
//similar for i3 and i5
   }
   
return a[n];
}

3. 最后一個問題:給 i, j 兩個數,然后打印出 2^i ,5^j 的序列
例如: i = 3 j =4 就打印出:
2^0 * 5 ^0 = 1
2^1 * 5^0 = 2
2^2 * 5 ^0 = 4
2^0 * 5^1 = 5
2^3 * 5^0 = 8
2^1 * 5^1 = 10
...
解法:和上面一個解法很相似,不過注意要處理相等的情況,比如2 * 2^1 * 5 ^1 = 20 2^2 * 5^0 ^5 = 20, 代碼就不寫了。

posted @ 2012-05-25 12:06 MichaelCao| 編輯 收藏


2012年5月23日

什么是DP? 簡單地來說就是把一個問題分解成兩個或者多個小問題。然后先把小的問題解出來,最后利用已經得到的答案,把大的問題解決。
它和分而治之有點類似,但有所不同。DP所分解出來的小問題會相互依賴,因此就不知道從哪里分。而分而治之的小問題不相互依賴。先看
個小程序吧,生成第n個Fibnacci數,可能有人會這么寫
int fib ( int n ) {
  if ( n == 0 )
     return 1;
  if ( n == 1 )
     return 1;
  return fib ( n - 1 ) + fib ( n - 2 );
}
但這個函數是2^n的遞歸,所以很快堆棧就會被用完的。另外如果思考一下,你會發現 fib( n - 1 ) 也已經要用到fib ( n - 2 ), 可是在
算fib ( n ) 的時候,這個值又要算一遍,那為什么不把這個值存下來呢? 
好, 我們就換個DP的方式:
int fib ( int n ) {
   if ( n == 0 || n == 1 )
      return 1;
   int [] f = new int[ n ];
   f[ 0 ] = 1;
   f[ 1 ] = 1;
   forint i = 2; i < n; i++)
   {
        f[ i ] = f[ i-1 ] + f[ i-2 ];
   }
   return f[ n-1 ];
}
可能這個比較容易了。大家都明白,就是先把以前的值給算好,然后后面的計算就可以利用前面的值。嗯,那稍微換個難點的吧。給一個n*n的0,1 matrix,然后找到最大的全是1的submatrix的大小。比如:
00011
01111
11110
01110
這個最大的那個全是1的submatrix的大小就是3.看起來挺難,其實蠻容易的。
我們先用最平常的思路來解一下吧。
先初始化另外一個同樣大小的n*n的matrix
第一行和第一列很容易,和原先一樣的值
00011
0
0
1
0
接下來,算第二行,和其他的行。自己動手,你就知道其實就是
s[i][j] = min(s[i][j-1],s[i-1][j],s[i-1][j-1]) + 1
我們順便還可以加上一個max,記錄最大的值。
這樣這個就搞定了。DP介紹完畢。接下來開始關于String的DP

1.找到兩個字符串的最大相同字串的長度
例如:abaabb aabbaa 最大的相同字串aabb長度就是4.
解法:給兩個串 p,q 我們有
c(i,j)  = 0 if p[i] != q[j]
c(i,j)  = c(i-1,j-1) + 1 if p[i] = q[j].
代碼和上面submatrix很相似。先初始化邊緣,然后算出其他的值
2.找到兩個字符串的最大subsequence的長度
例如:acbbab abbca 最大的subsequence is abba 長度是4.
解法:給兩個串 p,q 我們有
c(i,j) = max(c(i-1,j),c(i,j-1)) if p[i] != q[j]
c(i,j) = c(i-1,j-1) + 1 if p[i] = q[j]
3.找到一個字符串最大的Palindrom
例如: abcdedcbdsa 最大的Palindrom就是bcdedcb 長度是7
解法:給一個串p
c(i,j) = max(c(i+1,j),c(i,j-1)) if p[i] != q[j]
c(i,j) = c(i+1,j-1) + 2 if p[i] = q[j]


posted @ 2012-05-23 22:03 MichaelCao| 編輯 收藏


2010年11月15日

Here is the scripts:

rsync --progress --avze ssh --delete srcDir/  remoteName@remoteMachine:remoteDir/

-a quick way to specify the recursion and preserve everything.
-v verbose
-z compress

And then change ssh with no password:
Create the private keys for local machine:
ssh-keygen -t dsa
Copy the local keys to remote machine:

ssh-copy-id -i ~/.ssh/id_dsa.pub remoteuser@remotebox
Do not set the password.

After that, add an alias into your .bashrc
alias bp='. ~/backup.sh'
So you can run bp directly to backup all things.
Over ~~~

posted @ 2010-11-15 14:22 MichaelCao 閱讀(186) | 評論 (0)編輯 收藏


2009年11月5日

     摘要:   閱讀全文

posted @ 2009-11-05 13:26 MichaelCao 閱讀(385) | 評論 (0)編輯 收藏


2009年11月3日


很好的一篇文章,尤其是里面的禁用ipv6

posted @ 2009-11-03 19:38 MichaelCao 閱讀(291) | 評論 (0)編輯 收藏


2009年10月20日

     摘要: ssh ubuntu  閱讀全文

posted @ 2009-10-20 10:07 MichaelCao 閱讀(211) | 評論 (0)編輯 收藏


2009年10月7日

     摘要: MemoryFileSystem Java signal await  閱讀全文

posted @ 2009-10-07 14:31 MichaelCao 閱讀(511) | 評論 (0)編輯 收藏


2009年10月6日

     摘要: eclipse java heap size  閱讀全文

posted @ 2009-10-06 10:31 MichaelCao 閱讀(2806) | 評論 (0)編輯 收藏


2009年9月29日

     摘要: Hadoop eclipse 安裝  閱讀全文

posted @ 2009-09-29 21:21 MichaelCao 閱讀(1814) | 評論 (0)編輯 收藏


2009年9月28日

在編譯Hadoop后需要注意的幾點
1.各個節點上的版本要相同。需要注意的是,編譯后,程序運行就會從build文件夾里的class文件運行,所以即使你把jar包cp到根目錄底下,仍然沒用。刪除build目錄里面的jar包,還是沒用。辦法: ant clean
2.在使用一個新版本以后,可能會出現mapreduce能啟動,但是dfs無法啟動的情況。即使你format namenode還是不行。這個讓我郁悶了好久。mapreduce 都可以啟動,但就是dfs無法啟動。datanode就是啟動不了。想了好久,總算想明白了。因為datanode里面有數據,可是namenode里面卻格式化了。辦法:刪除所有datanode中的數據。

使用ssh 遠程執行命令
ssh gp09@***.comp.nus.edu.sg 'mkdir hadoop'
不過ssh有一個比較煩的地方,就是不能用cd命令。所以在使用的時候要小心。

在linux或者unix中安裝ant
編輯.bashrc 文件
添加:
export ANT_HOME=~/files/....
export JAVA_HOME=/usr/lib/jvm/java-6-sun/jre/bin/java
export PATH=$(PATH):$(ANT_HOME)/bin
期中$表示提取變量,:表示在后面添加。


posted @ 2009-09-28 13:32 MichaelCao 閱讀(259) | 評論 (0)編輯 收藏


2008年12月10日

  這個是在是應該糾正一下.因為以前什么都不知道.恩,看完linux 0.11的源代碼后,順便又看了Robert Love寫的Linux Development,這里還是先推薦一下這本書吧.首先作者是大牛.不信的話,打開linux的2.6內核源代碼,然后找sche.c.我想應該就能發現他的大名了.實在是令我崇拜阿.然后內容寫的,整體來說還不錯.尤其是前面那一部分.對于內核調度以及中斷之類的分析.寫的很好.后面的話,恩,個人覺得就有點不如前面的,思考的少了一點,應用多了一點.對于內核講的就少了.而如何寫驅動之類就多了.但不管怎么樣,這本書真的是一本很不錯的書.有看過linux 0.11源代碼并且喜歡內核的可以看看.
  廢話不多說了.首先從自旋鎖的來源來看吧.說到這個就要說SMP,linux 在2.2的內核之后就加入了SMP的支持.一直到2.6越來越好.有SMP就有多個cpu的隊列.每一個cpu都有一個自己的調度隊列.這樣在有些時候就需要平衡這些隊列.這個時候就要用到鎖,讓其他cpu什么也不做.讓一個cpu來更新這些隊列.這個時候肯定是不能用信號量的(?).這樣就出現了自旋鎖.當然自旋鎖的用途不止這里.比如說在中斷中,進入臨界區.信號量也是不能用的(?).這個時候就要用自旋鎖,其他方面的話,我再回去看看.這樣的話應該就很清楚了.信號量只是在進程中使用的.一般來說,應用級程序,你根本不用考慮自旋鎖.沒有SMP,也不用考慮了.因為代碼編譯以后只是禁止了內核搶占.這也就是說,這段代碼不會被搶占,sleep什么的根本沒用.如果是開發驅動方面的話,這個在必要的時候還是應該考慮一下.什么是必要的時候呢?就是上面我說的,進入中斷臨界區且有多個cpu.
 

posted @ 2008-12-10 20:49 MichaelCao 閱讀(1988) | 評論 (2)編輯 收藏


2008年9月30日

    指針應該都是4個字節,指向32位的地址.可以尋訪4GB的內存.如果是64位就再說.所以對函數指針來說這個應該就有了很大的好處.因為指針大家都是4個字節不論是什么種類的函數,它肯定都是4字節.這樣賦值就沒問題.在這里你也可以將指針直接看成是一個整數.這樣會更明白些.而對于另外一個問題.函數參數和返回值,則完全由函數的定義來決定.嗯.這樣就可以有很大的自由空間.來段代碼.
 1#include<iostream>
 2using namespace std ;
 3
 4typedef void (*pfn) (void);
 5union msg
 6{
 7    pfn first ;
 8    int (* ifn)(int a ,int b );
 9    void(*vfn)(int ,int );
10}
;
11int OnInt(int a ,int b )
12{
13    cout<<a<<"    "<<b<<endl;
14    return a ;
15}

16void OnVoid(int a ,int b )
17{
18    cout<<<<"    "<<b<<endl;
19}

20int main()
21{
22    pfn p=(pfn)(int (*)(int ,int ))OnInt;
23    msg m;
24    m.first=p;
25    cout<<(m.ifn)(5,6)<<endl;
26
27    p=(pfn)(void (*)(intint ))OnVoid;
28    m.first=p;
29    m.vfn(10,15);
30    return 0;
31}
看了這段代碼會讓人想到什么呢?想到的應該是MFC中那些消息函數吧.不同的消息,參數不一樣,返回值也不一樣.而在定義的時候只是一個指針,可是在調用的時候卻有各種各樣的方式.另外這段代碼最有意思的就是打破常規,就用了union同時只有一個變量在起作用,平時書上總是說其他變量都不能用,今天就用給你看看,用的還很牛...

posted @ 2008-09-30 11:26 MichaelCao 閱讀(4643) | 評論 (0)編輯 收藏


2008年7月6日

      我總算有點眉目了.原來在fork()之后系統就有兩個一樣的進程了.以前一直暈,兩個一樣的進程?那有什么用啊?其實是fork()這個函數會返回兩次而已.對于子進程,得到的是0,而對于父進程,得到卻是子進程的pid,這樣根據得到不同的pid,然后兩個進程就可以進行不一樣的運行了.并且子進程繼承了父進程的數據段,代碼段,這個也就是說變量阿還是有的,代碼阿還是會運行的.
    貼點代碼稍稍解釋一下:
#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <errno.h>

int main(void)
{
        pid_t pid=fork();
        if(pid==0)
        {
                int j ;
                for(j=0;j<10;j++)
                {
                        printf("child: %d\n",j);
                        sleep(1);
                }
        }
        else if (pid>0)
        {
                int i;
                for(i=0;i<10;i++)
                {
                        printf("parent: %d\n",i);
                        sleep(1);
                }
        }
        else
        {
                fprintf(stderr,"can't fork ,error %d\n",errno);
                exit(1);
        }
        printf("This is the end !");
}
    運行了這段代碼,我想應該所有人都應該了解fork了吧.運行的時候可以查看進程(ps -aux),會發現有兩個一樣的進程,運行結束后最后一句printf會運行兩次,因為每個進程都會運行一次.中間的交替就是進程的調度了.我也是剛剛明白,還有很多東西要深刻理解.總算有點眉目了.很爽.

posted @ 2008-07-06 23:40 MichaelCao 閱讀(8997) | 評論 (8)編輯 收藏


2008年4月30日

    覺得昨天的思考似乎還是不怎么過癮,有些問題還不是很清楚.到底應用方面兩個有什么區別呢?
自己學著別人小小的動了下手.
先貼信號量的代碼.
#include<pthread.h>
#include<stdio.h>
#include<sys/time.h>

#define MAX 10
pthread_t thread[2];
pthread_mutex_t mut;
int number=0,i;

void * thread1()
{
    printf("thread1: I'm thread 1 \n");
    for(i =0;i<MAX ;i++)
    {
        printf("thread 1: number=%d \n",number);
        pthread_mutex_lock(&mut);
        number++;
        pthread_mutex_unlock(&mut);
        sleep(2);
    }
    printf("thread1: 主函數在等我完成任務嗎?\n");
    pthread_exit(NULL);
}
void *  thread2()
{
    printf("thread2: I'm thread 2 \n");
    for(i =0; i<MAX;i++)
    {
        printf("thread2 : number=%d\n",number);
        pthread_mutex_lock(&mut);
        number++;
        pthread_mutex_unlock(&mut);
        sleep(3);
    }
    printf("thread2 : 主函數在等我完成任務么?\n");
    pthread_exit(NULL);

}

void thread_create(void)
{
    /*創建線程*/
    pthread_create(&thread[0],NULL,thread1,NULL);
    printf("線程1被創建!\n");
    pthread_create(&thread[1],NULL,thread2,NULL);
    printf("線程2被創建!\n");
}
void thread_wait(void)
{
    /*等待線程結束*/
    pthread_join(thread[0],NULL);
    printf("線程1已經結束!\n");
    pthread_join(thread[1],NULL);
    printf("線程2已經結束!\n");
}
int main()
{
    /*用默認屬性初始化互斥鎖*/
    pthread_mutex_init(&mut,NULL);
    printf("我是主函數,我正在創建線程!\n");
    thread_create();
    printf("我是主函數,我正在等待線程完成任務!\n");
    thread_wait();
}

執行的結果是:
我是主函數,我正在創建線程!
thread1: I'm thread 1
thread 1: number=0
線程1被創建!
thread2: I'm thread 2
thread2 : number=1
線程2被創建!
我是主函數,我正在等待線程完成任務!
thread 1: number=2
thread2 : number=3
thread 1: number=4
thread 1: number=5
thread2 : number=6
thread 1: number=7
thread2 : number=8
thread 1: number=9
thread2 : number=10
thread1: 主函數在等我完成任務嗎?
線程1已經結束!
thread2 : 主函數在等我完成任務么?
線程2已經結束!

 重要:這個執行的過程大概要10秒!!!!!!
而我們用自旋鎖,代碼:
/*
 * time :2008.4.30
 * author:will cao
 * Email:sei_michael@126.com
 * 探索自旋鎖與信號量的區別
 */
#include<pthread.h>
#include<stdio.h>

pthread_t thread[2];
pthread_spinlock_t lock ;

#define MAX 10

int number=0,i;

void * thread1()
{
    printf ("thread 1 :I began to run !");
    for(i=0;i<MAX;i++)
    {
        printf("thread 1 :number=%d \n",number);
        pthread_spin_lock(&lock);
        number++;
        pthread_spin_unlock(&lock);
    }
    printf("ok ,I am over !\n");
    pthread_exit(NULL);
}
void * thread2 ()
{
    printf("thread2 : I start !!!\n");
    for(i=0;i<MAX;i++)
    {
        printf("thread2 : number = %d \n",number);
        pthread_spin_lock(&lock);
        number++;
        pthread_spin_unlock(&lock);
    }
    printf("thread 2: I am over!!!");
    pthread_exit(NULL);
}

void thread_create(void)
{
    /*create the threads */
    pthread_create(&thread[0],NULL,thread1,NULL);
    printf("create the thread 1\n ");
    pthread_create(&thread[1],NULL,thread2,NULL);
    printf("create the thread 2 \n");
}
void thread_wait(void )
{
    /*wait for the thread to be over */
    pthread_join(thread[0],NULL);
    printf("the thread 1 is over !\n");
    pthread_join(thread[1],NULL);
    printf("the thread 2 is over ! \n");
}
int main()
{
    /* init the spin lock */
    pthread_spin_init(&lock,0);
    printf("i am the main,and I am creating the threads ");
    thread_create();
    printf("i am the main,and I am wait for the thread to be over!");
    thread_wait();
}
 執行結果為:
i am the main,and I am creating the threads thread 1 :I began to run !thread 1 :number=0
thread 1 :number=1
thread 1 :number=2
thread 1 :number=3
thread 1 :number=4
thread 1 :number=5
thread 1 :number=6
thread 1 :number=7
thread 1 :number=8
thread 1 :number=9
ok ,I am over !
create the thread 1
 thread2 : I start !!!
create the thread 2
i am the main,and I am wait for the thread to be over!thread2 : number = 10
thread2 : number = 11
thread2 : number = 12
thread2 : number = 13
thread2 : number = 14
thread2 : number = 15
thread2 : number = 16
thread2 : number = 17
thread2 : number = 18
thread2 : number = 19
thread 2: I am over!!!the thread 1 is over !
the thread 2 is over !
   執行時間:我沒用系統調用,但肯定是用不了0.1秒的...
總結:從表面上來看,很明顯的區別是當我們用的是信號量的時候,這個時候是有調度的.因為從運行結果上來看,主線程在創建其他兩個線程后,其他線程開始運行.并且主線程也在運行.但怎么運行這個是無法確定的,這是一個并發的過程.
    當使用自旋鎖后,這個就不一樣了.當運行到臨界區的時候,它是直接的過去,不是會產生一個等待,或者一個調度.
不知道編譯器是怎么編譯的.很想知道編譯后二進制代碼有什么區別.但這個好像有點太難....不過我覺得從運行結果上來看這么多,應該差不多了.


posted @ 2008-04-30 16:45 MichaelCao 閱讀(851) | 評論 (4)編輯 收藏

   剛剛開始想這個問題的時候,覺得好像這個根本就不是一個問題.學操作系統的進程間的通信時,就是先說用互斥鎖解決兩個進程同時訪問臨界區的方法.但是后來Dijkstra對于哲學家進餐的問題的解答使用了信號量,于是我們接受了信號量.在看pthread的時候,發現還有個自旋鎖.于是有點暈,這兩個不都是控制對臨界區的訪問的么?怎么都上來了?他們之間有什么區別,他們又都是怎么實現的?
   首先說自旋鎖.這個實現基本上是和TSL相同.TSL指令,首先是要共享一個lock,當進入臨界區時,首先將lock復制到寄存器,然后將lock置為1,接下來看寄存器中的值是否為0,為0進入.不為0返回.而最重要的是它能保證指令執行的不可分割性,也就是說在這條指令結束之前,其他指令不允許訪問內存.實現的是方式是在指令執行之前將內存總線禁止.結束后在打開內存總線.而自旋鎖實現就是這個樣子.只不過多循環了幾次.為了更好的讓cpu調度,在嘗試一定次數后返回.因為他是一直在那邊循環所以叫做自旋鎖.可見這種鎖很耗資源.但是速度上來說很快.一旦鎖釋放,立刻可以得到資源.
   再來看看信號量,信號量的實現就不這般精準了.如果使用一個信號量來控制一個臨界區的話.就會有很多情況,首先最明顯的是讀者-寫者問題.可以有多個讀者,寫者只可以有一個.并且信號量的實現也和自旋鎖有者一定的區別.當一個信號量不能訪問后.進程不會在那里循環,會被睡眠掉.當信號量可以使用的時候,調度器會從可以調度的進程選擇一個.
   基本上就這個樣子.

posted @ 2008-04-30 01:32 MichaelCao| 編輯 收藏


2008年4月28日

   回首,大學三年已經過去,人生最精華的部分也在漸漸的流逝.時常想到什么,學到什么總會在這寫寫,在那畫畫,雖然歷經許多,但不成系統,總之似乎想抓住些什么,但總有滑過,故在此建一小屋.
                      望多思,多想,多記.珍惜青春.

posted @ 2008-04-28 00:13 MichaelCao 閱讀(169) | 評論 (0)編輯 收藏


posts - 16, comments - 16, trackbacks - 0, articles - 0

江苏快三开奖结果Copyright © MichaelCao