• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            DraculaW

              C++博客 :: 首頁 :: 新隨筆 :: 聯系 :: 聚合  :: 管理 ::
              19 隨筆 :: 0 文章 :: 7 評論 :: 0 Trackbacks

            #

            手機的英文智能輸入法其實很簡單的想法 使用哈希來實現 呵呵

            1       2       3
            ,.    abc    def

            4       5       6
            ghi    jkl    mno

            7       8       9
            pqrs tuv   wxyz

            譬如說輸入 43
            進入這個哈希里面去尋找
            key[43] -> [if] -> [he] -> [id] -> [ie]-> [ge] -> [gf] -> 0
            還可以輸入更多的 呵呵。

            以此類推,如果是拼音輸入也是一樣,只不過要多進行一次哈希。從拼音哈希到具體的漢字里面去。

            不過拼音輸入的狀態機應該更復雜一些。因為拼音輸入可以根據前一個字來推斷可能出現的下一個字。

            其實 不只是手機,只要是使用數字鍵盤的機器都可以使用這樣子的輸入法。

            使用這種算法的變種還可以實現一個好玩的游戲:就是輸入一個單詞,然后輸出所有與它組成元素相同的單詞(就是輸入stop 它可以輸出tops等單詞)。具體也是使用哈希。哈希真是一個好算法
            posted @ 2007-11-15 20:37 DraculaW 閱讀(334) | 評論 (0)編輯 收藏

            template<typename T>
            void prefix(T* p, int m, int* next)
            {
                   int i, j;
                   i = 0;
                   j = next[0] = -1;
                   while (i < m) {
                       while (j > -1 && p[i] != p[j])
                                 j = next[j];
                       i++;
                       j++;
                       if (p[i] == p[j])
                                 next[i] = next[j];
                       else
                                 next[i] = j;
                   }
            }
            /* ---------- end of function prefix ---------- */

            /*****************************************************************************
            * Function : KMP                                                            *
            * T     *t : The string need be matching                                    *
            * int    n : The length of the string                                       *
            * T     *p : The sub string to matching                                     *
            * int    m : The length of the p                                            *
            * int *out : An array mark the string match where ( max length is m - n )   *
            *****************************************************************************/
            template<typename T>
            int KMP(T* t, int n, T* p, int m, int* out)
            {
                      int c = 0;
                int i, j, next[m];
                prefix(p, m, next);
                i = 0;
                j = 0;
                while(i < n)
                {
                    while( j > -1 && p[j] != t[i])
                        j = next[j];
                    i++; j++;
                    if( j >= m )
                    {       
                        out[c++] = i - m;
                        j = next[j];
                    }
                }
                      return c;
            }
            /* ---------- end of function KMP ---------- */

            // 這個算法 也研究了很久了。對于他的原理 我早已經清楚,但是快速的寫出他還是不是那么順利。也是因為我寫的程序太少了吧 呵呵。 理解中記憶。 嗯 不能死記硬背啊 呵呵。
            posted @ 2007-11-15 20:36 DraculaW 閱讀(91) | 評論 (0)編輯 收藏

            #ifndef _BIGNUM_HPP_
            #define _BIGNUM_HPP_

            #include <vector>
            #include <string>
            #include <iostream>

            using namespace std;

            class BigNum;

            BigNum operator+(const BigNum& lhs, const BigNum& rhs);

            ostream& operator<<(ostream& os, const BigNum& rhs);

            void Add(const BigNum& lhs, const BigNum& rhs, BigNum& res);

            class BigNum
            {
            public:
                BigNum(int n) : value(n){}
                BigNum(const string& s);
                friend BigNum operator+(const BigNum& lhs, const BigNum& rhs);
                friend ostream& operator<<(ostream& os, const BigNum& rhs);
                friend void Add(const BigNum& lhs, const BigNum& rhs, BigNum& res);
            private:
                vector<char> value;   
            };

            #endif

            #include "BigNum.hpp"

            BigNum::BigNum(const string& s):value(s.length())
            {
                int j = value.size();
                for(string::const_iterator it = s.begin(); it != s.end(); it++)
                {
                    j--;       
                    value[j] = *it;
                }
            }

            ostream& operator<<(ostream& os, const BigNum& rhs)
            {
                size_t i = rhs.value.size();
                bool zero = false;
                if( i == 1)
                    return os << rhs.value[0];

                if(rhs.value[ i - 1 ] == '0')
                    zero = true;
               
                while( i > 0 )
                {
                    i--;
                    while(zero == true)
                    {
                        i--;
                        if(rhs.value[i] != '0')
                            zero = false;
                    }
                    os << rhs.value[i];
                }
                return os;
            }

            void Add(const BigNum& lhs, const BigNum& rhs, BigNum& res)
            {
                int carry = 0;
                char c = 0;
                char tmp = 0;
                size_t i = 0;
                for( ; i < rhs.value.size(); i++)
                {
                    tmp = lhs.value[i] + rhs.value[i] + carry - '0';

                    if( tmp > '9' )
                    {
                        carry = 1;
                        tmp -= 10;
                    }
                    else
                    {
                        carry = 0;
                    }
                    res.value[i] = tmp;
                }

                while( carry != 0 && i < lhs.value.size() )
                {
                    tmp = lhs.value[i] + carry;
                    if( tmp > '9' )
                    {
                        carry = 1;
                        tmp = '0';
                    }
                    else
                    {
                        carry = 0;
                    }
                    res.value[i] = tmp;
                    i++;
                }

                if( carry > 0)
                    res.value[i] = '1';

            }

            BigNum operator+(const BigNum& lhs, const BigNum& rhs)
            {
                size_t lsize, rsize;
                lsize = lhs.value.size();
                       rsize = rhs.value.size();
                size_t n = lsize > rsize ? lsize : rsize;   
                BigNum res(n + 1);
                res.value[0] = '0';
               
                if( lsize > rsize )
                {
                         Add(lhs, rhs, res);
                }
                else
                {
                    Add(rhs, lhs, res);
                }
               
                return res;
            }

            //我自己實現的大數的加法的程序。。 終于驗證可以使用了 呵呵
            這個程序寫好了 也算可以了了我的心愿了的
            去年的某個時候 在杭州的UT斯達康面試 上機題就是這一道 我死活沒有憋出來,當時就很后悔 為什么不好好的看看論壇上的帖子 對上面的問題做做呢?那樣子的話 也許我就不會這么悲慘了,老是在哪里自怨自唉。
            總結起來 我其實是眼高手低,然后從來都被寵著沒有認清過自己。小學初中,老媽老師都說我數學學的還不錯,其實是有點小聰明,分數還是那么可憐的一點點;到高中,因 為學校比較一般,考的名次看起來很美,被假象迷惑了;大學,因為自己有點基礎,被給哥封為軟件最好,也有點沾沾自喜;到了這個公司,也許因為我身體的原 因,也有點面試時做題速度超快的原因,被經理說我程序不錯,還是沒有擺正自己的位子。
            受點挫折才好。嗯
            呵呵, 心態 , 心態才是一切。
            不要眼高手低
            posted @ 2007-11-15 20:35 DraculaW 閱讀(201) | 評論 (0)編輯 收藏


            // 給一個鏈表 list 將 list 倒置
            // 有很多種做法
            // 1 遞歸 (速度最慢)
            // 2 用個棧 (速度慢)
            // 3 三個指針遍歷 (大部分的做法)
            //

            // 具體就是一個 node*的數組 有三個元素
            // 每次都將 a[1]的放入a[0] a[2]的放入a[1] a[2]->next放入a[2]
            // 再將a[1]->next = a[0];
            //

            void resv_Linklist(Node* head)
            {
                Node* a[3];
                a[0] = a[1] = NULL;
                a[2] = head;
                while(a[2]->next)
                {
                    a[0] = a[1];
                    a[1] = a[2];
                    a[2] = a[2]->next;
                    a[1]->next = a[0];
                }
                *head = *(a[2]);
            }
            posted @ 2007-11-15 20:34 DraculaW 閱讀(428) | 評論 (0)編輯 收藏

            // 給一個數組 a[n] = {0, 1, 2, 3, 4, 5, 6} 一個k=3
            // 將 a[n]變為 a[n] = {3, 4, 5, 6, 0, 1, 2}
            // 具體的算法是
            // 先將 a[n] 變為{2, 1, 0, 6, 5, 4, 3}
            // 再把 a[n] 逆轉了

            void swap(int *a, int *b)
            {
                int t = *a;
                *a = *b;
                *b = t;
            }

            void resv(int* a, int start, int end)
            {
                end = end-1;

                while(start < end)
                {
                    swap(a+start, a+end);
                    start--, ed--;
                }
            }

            void resver(int *a, int size, int k)
            {
                resv(a, 0, k);
                resv(a, k, size);
                resv(a, 0, size);
            }
            posted @ 2007-11-15 20:33 DraculaW 閱讀(243) | 評論 (0)編輯 收藏


            // 給一個數組a[n]求其中 第k大的數值的算法
            // 基本的思想就是 使用quicksort的一個變種
            // 每次進行完part后 判斷它的返回值 是否為k
            // 如果為k 返回
            // 如果大于k 則在返回的位置的前面找
            // 如果小于k 則在返回的位置的后面找

            int part(int* a, int start, int end)
            {
                int t = a[end-1];
                int e = -2;
                while(start < e)
                {
                    while(a[start]<t) start++;
                    while(a[e]>t) e--;
                    int tmp = a[e];
                    a[e] = a[start];
                    a[start] = tmp;
                }
                return start;
            }



            int findK(int* a, int start, int end, int k)
            {
                int i = part(a, start, end);
                int rtn;

                if(i < k-1)
                {
                    rtn = findK(a, i+1, end);
                }

                else if(i > k-1)
                {
                    rtn = findK(a, start, i-1);
                }
                else
                {
                    rtn = a[i];
                }

                return rtn;
            }
            posted @ 2007-11-15 20:31 DraculaW 閱讀(852) | 評論 (1)編輯 收藏

            #ifndef _LINKEDLIST_H_

            #define _LINKEDLIST_H_



            #include <stdexcept>



            using namespace std;



            class EmptyListException : public logic_error {



            public:

                EmptyListException(const string& what_arg ) throw() :

                  logic_error ("Empty list exception: " + what_arg) {}}

            ;



            template <class T>

            class Node {

            private:

                T data;

                Node* next;



            public:

                Node(T d, Node* n = NULL) : data(d), next(n) {}

                T& getData() { return data;}

                Node*& getNext() { return next;}



            };



            template <class T>

            class LinkedList {



            protected:



                Node<T>* head; // Beginning of list

                Node<T>* tail; // End of list

                int count; // Number of nodes in list



            public:



                LinkedList(void) : head(NULL), tail(NULL), count(0) {}

                LinkedList(const LinkedList<T>& src); // Copy constructor

                virtual ~LinkedList(void); // Destructor



                virtual T& front(void) {



                    if (head == NULL) {

                        throw EmptyListException("front()");

                    }

                    return head->getData();

                }

                virtual T& back(void) {

                    if (tail == NULL) {

                        throw EmptyListException("back()");

                    }

                    return tail->getData();

                }

                virtual int size(void) {

                    return count;

                }

                virtual bool empty(void) {

                    return count == 0;

                }



                virtual void push_front(T); // Insert element at beginning

                virtual void push_back(T); // Insert element at end

                virtual void pop_front(void); // Remove element from beginning

                virtual void pop_back(void); // Remove element from end



                virtual void dump(void); // Output contents of list

            };



            // Copy constructor

            template <class T>

            LinkedList<T>::LinkedList(const LinkedList<T>& src) :

            count(0), head(NULL), tail(NULL) {



                Node<T>* current = src.head;

                while (current != NULL) {

                    this->push_back(current->getData());

                    current = current->getNext();

                }



            }



            // Destructor

            template <class T>

            LinkedList<T>::~LinkedList(void) {



                while (!this->empty()) {

                    this->pop_front();

                }

            }



            // Insert an element at the beginning

            template <class T>

            void LinkedList<T>::push_front(T d) {



                Node<T>* new_head = new Node<T>(d, head);



                if (this->empty()) {

                    head = tail = new_head;

                }

                else {

                    head = new_head;

                }

                count++;

            }



            // Insert an element at the end

            template <class T>

            void LinkedList<T>::push_back(T d) {



                Node<T>* new_tail = new Node<T>(d, NULL);



                if (this->empty()) {

                    head = new_tail;

                }

                else {

                    tail->getNext() = new_tail;

                }



                tail = new_tail;

                count++;

            }



            // Remove an element from the beginning

            template <class T>

            void LinkedList<T>::pop_front(void) {



                if (head == NULL) {

                    throw EmptyListException("pop_front()");

                }



                Node<T>* old_head = head;



                if (this->size() == 1) {

                    head = NULL;

                    tail = NULL;

                }

                else {

                    head = head->getNext();

                }



                delete old_head;

                count--;

            }



            // Remove an element from the end

            template <class T>

            void LinkedList<T>::pop_back(void) {



                if (tail == NULL) {

                    throw EmptyListException("pop_back()");

                }



                Node<T>* old_tail = tail;



                if (this->size() == 1) {

                    head = NULL;

                    tail = NULL;

                }

                else {



                    // Traverse the list

                    Node<T>* current = head;

                    while (current->getNext() != tail) {

                        current = current->getNext();

                    }



                    // Unlink and reposition

                    current->getNext() = NULL;

                    tail = current;

                }



                delete old_tail;

                count--;

            }



            // Display the contents of the list

            template <class T>

            void LinkedList<T>::dump(void) {



                cout << "(";



                if (head != NULL) {

                    Node<T>* current = head;

                    while (current->getNext() != NULL) {

                        cout << current->getData() << ", ";

                        current = current->getNext();

                    }

                    cout << current->getData();

                }



                cout << ")" << endl;

            }



            #endif



            #ifndef _ENHANCELINKLIST_H_

            #define _ENHANCELINKLIST_H_



            #include "LinkedList.h"



            template<typename T>

            class EnhancedLinkedList: public LinkedList<T>

            {

            public:

                T& find_first (const T& key);

                //Method find_first should search the EnhancedLinkedList for the first

                //occurrence of an item that matches the value in the parameter key.

                //It should return a reference to the first matching item.

                //If the invoking EnhancedLinkedList object is empty or no item is found

                //that matches the parameter, a ListItemNotFoundException should be thrown.

                //You will have to define this exception

                //(Hint: define this exception much the same way that the

                //EmptyListException exception is defined in LinkedList.h).



                EnhancedLinkedList find_all (const T& key);

                //Method find_all should search the invoking EnhancedLinkedList

                //for all elements that match the value in the parameter key.

                //It should return an EnhancedLinkedList object containing

                //copies of all the items that match the parameter key.

                //If the invoking EnhancedLinkedList object is empty or

                //no item is found that matches the parameter,

                //this function should return an empty EnhancedLinkedList.



                void remove_first (const T& key);

                //Method remove_first should remove the first element from the

                //invoking EnhancedLinkedList whose data item matches the parameter key.

                //If the invoking EnhancedLinkedList object is empty or no item is found

                //that matches the parameter, this function should do nothing.

                //Remember to leave no memory leaks.



                void remove_all (const T& key);

                //Method remove_all should remove all elements from the invoking

                //EnhancedLinkedList whose data items match the parameter key.

                //If the invoking EnhancedLinkedList object is empty or no item is found

                //that matches the parameter, this function should do nothing.

                //Remember to leave no memory leaks.

            };



            template<typename T>

            T& EnhancedLinkedList<T>::find_first(const T& key)

            {

                Node<T>* temp = this->head;

                if(temp == NULL)

                    throw EmptyListException("Find first emptylist");



                while(NULL != temp->getNext())

                {

                    if(temp->getData()==key)

                        return temp->getData();

                    else

                        temp=temp->getNext();

                }



                throw EmptyListException("Find first not found");

            }



            template<typename T>

            EnhancedLinkedList<T>

            EnhancedLinkedList<T>::find_all(const T& key)

            {

                EnhancedLinkedList<T> resualt;



                Node<T>* temp = this->head;



                while(NULL != temp)

                {

                    if(temp->getData()==key)

                        resualt.push_back(temp->getData());

                    temp=temp->getNext();

                }


            end:
                return resualt;

            }



            template<typename T>

            void

            EnhancedLinkedList<T>::remove_first(const T& key)

            {

                EnhancedLinkedList<T> list;



                while(NULL!=this->head)

                {

                    if(this->head->getData()!=key)

                        list.push_front(this->head->getData());

                    else{

                        T* temp = this->front();

                        this->pop_front();

                        delete temp;

                        break;

                    }

                    this->pop_front();

                }



                while(list.head!=NULL)

                {

                    this->push_front(list.front());

                    list.pop_front();

                }

            }



            template<typename T>

            void

            EnhancedLinkedList<T>::remove_all(const T& key)

            {

                EnhancedLinkedList<T> list;



                while(NULL!=this->head)

                {

                    if(this->head->getData()!=key){

                        list.push_front(this->head->getData());

                        this->pop_front();

                    }

                    else{

                        T* temp = this->front();

                        this->pop_front();

                        delete temp;

                    }

                }



                while(list.head!=NULL)

                {

                    this->push_front(list.front());

                    list.pop_front();

                }

            }



            #endif //_ENHANCELINKLIST_H_
            posted @ 2007-11-15 20:29 DraculaW 閱讀(282) | 評論 (0)編輯 收藏

            /////////////////////////////////////////////////////////////////////////////////

            // The Sort //

            // //

            /////////////////////////////////////////////////////////////////////////////////
            #ifndef _SORT_H_

            #define _SORT_H_
            /////////////////////////////////////////////////////////////////////////////////

            // The QuickSort //

            // //

            /////////////////////////////////////////////////////////////////////////////////
            template<typename T>

            int Quick(T* a, int s, int e)

            {

                T t = a[e];

                int i = s - 1;

                for(int j = s; j < e; j++ )

                    if(a[j] <= t)

                    {

                        i++;

                        swap(a[j],a[i]);

                    }



                    swap(a[i+1], a[e]);

                    return i+1;

            }
            template<typename T>

            void QuickSort(T* a, int s, int e)

            {

                if( s < e )

                {

                    int i = Quick(a, s, e);

                    //int i = part(a, s, e);

                    QuickSort(a, s, i-1);

                    QuickSort(a, i+1, e);

                }

            }
            /////////////////////////////////////////////////////////////////////////////////

            // The HeapSort //

            // //

            /////////////////////////////////////////////////////////////////////////////////

            inline int left(int i)

            {

                return 2*i+1;

            }
            inline int right(int i)

            {

                return 2*i+2;

            }
            template<typename T>

            void HeapHy(T* a, int n, int i)

            {

                int big = i;

                //first find the lage of i, left(i),right(i)

                if(left(i) < n)

                {

                    big = a[i]>a[left(i)]?(i):(left(i));

                    if(right(i) < n)

                        big = a[big]>a[right(i)]?(big):(right(i));

                }

                //and if the i not the biggest change pos i with the bigest

                if(i!=big)

                {

                    swap(a[i], a[big]);

                    //then HeapHy(a, n, bigest)

                    HeapHy(a, n, big);

                }

            }
            template<typename T>

            void BuildHeap(T* a, int n)

            {

                for(int i = n/2; i > -1; i--)

                    HeapHy(a, n, i);

            }
            template<typename T>

            void HeapSort(T* a, int n)

            {

                BuildHeap(a, n);

                for(int i=n-1; i>0; i--)

                {

                    swap(a[0], a[i]);

                    HeapHy(a, i, 0);

                }

            }
            /////////////////////////////////////////////////////////////////////////////////

            // The ShellSort //

            // //

            /////////////////////////////////////////////////////////////////////////////////
            template<typename T>

            void ShellSort(T* a, int s)

            {

                T t;

                int i,j,k;

                for(i=s/2; i>0; i=i/3)

                {

                    for(j=i; j<s; j++)

                    {

                        t = a[j];

                        for(k=j-i; k>-1; k-=i)

                        {

                            if(a[k]>t)

                                a[k+i] = a[k];

                        }

                        a[k+i] = t;

                    }

                }

            }
            #endif //_SORT_H_
            posted @ 2007-11-15 20:27 DraculaW 閱讀(140) | 評論 (0)編輯 收藏

            呵呵
            posted @ 2007-11-15 20:22 DraculaW 閱讀(472) | 評論 (5)編輯 收藏

            僅列出標題
            共2頁: 1 2 
            亚洲αv久久久噜噜噜噜噜| 精品久久久久久无码人妻热| 日韩中文久久| 久久综合久久自在自线精品自| 国产Av激情久久无码天堂| 国产ww久久久久久久久久| 久久午夜福利无码1000合集| 国产欧美久久一区二区| 国内精品久久久久国产盗摄| 日韩欧美亚洲综合久久| 91久久精品国产91性色也| 国产精品久久久香蕉| 国产美女久久久| 亚洲中文精品久久久久久不卡| 久久久青草青青亚洲国产免观| 伊人久久成人成综合网222| 国产精品美女久久久久AV福利| 亚洲精品国产美女久久久| 久久久噜噜噜久久| 99精品久久久久久久婷婷| 国产婷婷成人久久Av免费高清 | 夜夜亚洲天天久久| 中文成人久久久久影院免费观看| 久久99国产精品久久99果冻传媒| 久久精品国产亚洲AV蜜臀色欲 | 91性高湖久久久久| 久久天天躁狠狠躁夜夜avapp| 色综合久久中文字幕综合网| 国产巨作麻豆欧美亚洲综合久久| 久久亚洲精品中文字幕| 99精品国产99久久久久久97| 色综合久久夜色精品国产| 久久婷婷色综合一区二区| 99久久婷婷国产一区二区| 久久免费的精品国产V∧| 性欧美丰满熟妇XXXX性久久久 | 久久99国产亚洲高清观看首页| 无码久久精品国产亚洲Av影片| 麻豆久久久9性大片| 久久久久高潮综合影院| 三级片免费观看久久|