标签 数据结构、算法与应用 下的文章

本页的练习在无特殊说明时一律按照 单右向循环 链表为准。

1. L=(a,b,c,d,e) 作图 pass

2. setSize

复杂度O(n)
template <class T>
void chain<T>::theSize( int n ){
    chainNode<T> current = firstNode();
    int i=0, max = _size < n ? _size : n;

    // 由于不是双向链表,所以需要先到达n的极点
    while( i < max ){
        current = current->next();
        i++;
    }

    chainNode<T> tmp;
    // 如果有多余的
    while( _size > n ){
        tmp = current->next();
        delete current; // 系统会执行element析构
        current = tmp;
    }

    _size = n;
}

3. set()

复杂度O(n) 在实际使用的时候,链表一般不用index表示法来获取或设置元素。因为每次都相当于O(n)的复杂度。

template <class T>
void chain<T>::checkIndex( int theIndex ){

    if( theIndex <0 || theIndex >= _size ){
        throw illegalIndex("Out of range");
    }
}

template <class T>
void chain<T>::set( int theIndex, T& theElement ){
    checkIndex(theIndex);
    chainNode<T>* current = firstNode();
    int i = 0;
    while( i < _size ){
        current = current->next();
    }
    current->element.~T(); // 析构
    current->element = theElement;
}

4. removeRange

复杂度O(n) 和上面的setSize类似,做一次遍历,之后将切割掉的部分接起来即可。

template <class T>
void chain<T>::setSize( int fromIndex, int toIndex ){
    checkIndex(fromIndex);
    checkIndex(toIndex);

    chainNode<T>* current = firstNode();
    int i=0;

    // fromIndex的极点
    while( i < fromIndex ){
        current = current->next();
        i++;
    }

    chainNode<T>* tmp;

    while( i < toIndex ){
        tmp = current->next();
        delete current; // 系统会执行element析构
        current = tmp;
    }

    _size -= toIndex-fromIndex +1; // 考虑左右闭区间
}

5. lastIndex()

复杂度O(n) 遍历元素并比对,不即时返回。

template <class T>
int chain<T>::lastIndex( T& theElement ) const{

    if( empty() ) return -1;

    chainNode<T>* current = firstNode();
    int i = 0, lastIndex = -1;

    while( i< _size ){
        if( current->element == theElement ){
            lastIndex = i;
        }
        current = current->next();
        i++;
    }
    return lastIndex;
}

6. 重载[]

复杂度O(n) 实际上重载应该包含两种,分别是提供左值,右值返回。

template <class T>
const T& chain<T>::operator[](int n) const{  } // 右值
T& chain<T>::operator[]( int n) const{ // 左值
    int i = 0;
    chainNode<T>* current = firstNode();

    while( i < n ){
        current = current->next();
    }
    return current->element;
}

7. 重载==

复杂度O(n) 同步遍历两个链表元素,一旦发现不同元素返回false。

template <class T>
bool chain<T>::operator==( chain<T>& c) const{

    if( size() != c.size() ) return false;
    chainNode<T>* current = firstNode();
    chainNode<T>* target  = c.firstNode();

    int i = 0;
    while( i < size() ){
        if( current->element !== target->element ) return false;
        current = current->next();
        target  = target->next();
    }
    return true;
}

8. 重载!=

复杂度O(n)

template <class T>
bool chain<T>::operator!=( chain<T>& c) const{
    return !*this == c;
}

9. 重载<

复杂度O(n) 略微需要注意的是,除了最后一项的值完全相等以外,其他的相等 都不能判断非<。 所以在遍历的靠前阶段,== 都应该算成功,只有最后一项相等判断非小于。

template <class T>
bool chain<T>::operator<( chain<T>& c) const{

    if( size() > c.size() ) return false;
    chainNode<T>* current = firstNode();
    chainNode<T>* target  = c.firstNode();

    int i = 0;
    while( i < size() ){
        if( current->element > target->element ){
            return false;
        }else{
            current = current->next();
            target  = target->next();
        }
    }
    if( current->element == target->element ) return false;
    return true;
}

- 阅读剩余部分 -

1### 2. L = (a,b,c,d,e) ... 做图

初始状态:

0 1 2 3 4 5 6 7 8 9
a b c d e  

insert(0,f)

0 1 2 3 4 5 6 7 8 9
f a b c d e  

insert(3,g)

0 1 2 3 4 5 6 7 8 9
f a b g c d e  

insert(7,h)

0 1 2 3 4 5 6 7 8 9
f a b g c d e h  

earse(0)

0 1 2 3 4 5 6 7 8 9
a b g c d e h  

erase(4)

0 1 2 3 4 5 6 7 8 9
a b g c e h  

3. changeLength2D

二维数组的话要基于Array设计一个矩阵类,其中的每一行都是一个Array对象。

template <class T>
class ArrayMatrix: public Array{
    void changeLength2D( int x, int len );
}

template <class T>
void ArrayMatrix::changeLength2D( int rowIndex, int len ){
    checkIndex(x);
    get(rowIndex).changeLength(len);
}

3. 构造函数

好像题目描述有问题。 我自己写的是提供一个是否自动扩容的参数。如果配置为不自动扩容则在超出的时候抛出异常。

enum class ARRAY_AUTO_CAPACITY
{
    DISABLED = 0,ENABLED = 1
};

template <class T>
class Array{
public:
    Array(int initCapacity = ARRAY_DEFAULT_CAPACITY, ARRAY_AUTO_CAPACITY autoCapacity = ARRAY_AUTO_CAPACITY::DISABLED);
    void checkMax();
private:
    ARRAY_AUTO_CAPACITY _autoCapacity =  ARRAY_AUTO_CAPACITY::DISABLED;
}


template<class T>
inline void Array<T>::checkMax()
{
    if (_size >= _capacity) {

        switch (_autoCapcity)
        {
        case ARRAY_AUTO_CAPACITY::ENABLED:
            changeCapacityTo(_capacity << 1);
            break;
        case ARRAY_AUTO_CAPACITY::DISABLED:
            throw illegalInputData("Array is full.");
            break;
        default:
            break;
        }
    }
}

5. trimToSize()

实际上就是改变数组长度, 长度为size或1。 这里我基于我改写的 changeCapacityTo()来实现,实际上是一回事。

复杂度是O(n)

void trimToSize(){
    changeCapacityTo( _size>0 ? _size : 1 );
}

template<class T>
inline void Array<T>::changeCapacityTo(int newCapacity)
{
    T* newElements = new T[newCapacity];
    _capacity = newCapacity;
    _size = newCapacity < _size ? newCapacity : _size;

    for (int i = 0; i < _size; i++)
    {
        newElements[i] = _elements[i];
    }
    delete[] _elements;

    _elements = newElements;
}

6. setSize

这一题,同样题目描述是有问题的。 见上一题changeCapacityTo()

7. 重载[]

T& operator[]( int n){
    checkIndex(n);
    return _elements[n];
}

8. 重载==

template<class T>
bool operator==( const Array<T>& targetArray ) const{
    if( size()!= targetArray.size() ){
        return false;
    }
    for( int i=0; i<size();i++ ){
        if( get(i) != target.get(i) ){
            return false;
        }
    }
    return true;
}

9. 重载!=

template<class T>
bool operator!=( const Array<T>& targetArray ){
    return !*this == targetArray;
}

10. 重载<

见8 . 其中!= 替换为>

- 阅读剩余部分 -

SLT版本 string,queue


/*
 * 祖玛 Zuma
 * 
 * hello@shezw.com 2020.06.29
 */

#include <iostream>
#include <string>
#include <queue>

using namespace std;

struct opr{
    int t;
    char c;
    opr( int target, char color ){
        t = target;
        c = color;
    }
};

void checkElimination( string & balls, int cursor ){
    if( balls.empty() ){ return; }
    int i = 1; int l = cursor, r = cursor, len = balls.size();
    while( cursor-i > -1 ){
        if( balls[cursor-i] != balls[cursor] ) break;
        l = cursor - (i++);
    }
    i = 1;
    while( cursor+i < len ){
        if( balls[cursor+i] != balls[cursor] ) break;
        r = cursor + (i++);
    }
    if( r - l > 1 ){
        balls.erase( l,r-l+1 );
        if( balls.size()>2 ) checkElimination( balls, l ); // 删除[l,r]区间后 如果存在继续消除可能时,原右侧必不为空,右侧第一个将取代原L。
    }
}

int main()
{
    string balls; int count;    // 主要变量
    int t; char c;              // 缓存变量

    cin>>balls;                 // 读取初始化彩球
    cin>>count;                 // 读取初始化数量

    queue<opr> oprs;            // 操作队列

    while( cin >> t ){          // 读取数字
        cin >> c;               // 读取颜色
        oprs.push( opr(t,c) );  // 压入队列
    }

    while( !oprs.empty() ){
        // cout<< oprs.front().t << " " << oprs.front().c << endl;
        t = oprs.front().t;
        c = oprs.front().c;
        balls.insert( t, 1, c );
        checkElimination( balls, t );
        oprs.pop();
        cout << (balls.empty() ? "-" : balls) << endl;
    }
    // cout << oprs.size() << endl;
    // cout<< balls << endl << count << endl << oprs.front().c << endl;
}

由于清华judge是不允许使用SLT的,所以使用自建QUEUE来完成。

非SLT版

/*
 * 祖玛 Zuma
 * 
 * hello@shezw.com 2020.06.29
 */

#include <iostream>
#include <string>

using namespace std;


struct opr{
    int t;
    char c;
    opr(){}
    opr( int target, char color ){
        t = target;
        c = color;
    }
};

template <typename T>
struct qe{
    qe<T>* prev;
    qe<T>* next;
    T data;
    qe(){}
    qe( T d, qe<T>* p = NULL, qe<T>* n = NULL ){
        data = d; prev = p; next = n;
    }
}; 

template <typename T>
class queue{ // 专为本算法特别定制队列,简化版
private:
    int _size = 0;
public:
    qe<T>* _head;
    qe<T>* _tail;

    queue(){
        _size = 0;
        _head = new qe<T>;
        _tail = new qe<T>;
        _head->next = _tail; _head->prev = NULL;
        _tail->prev = _head; _tail->next = NULL;
    }
    ~queue(){
    }
    int size(){return _size;}

    void push( T data ){

        qe<T>* newQe = new qe<T>( data, _tail->prev, _tail );
        _tail->prev->next = newQe;
        _tail->prev = newQe;
        _size++;
    }

    void pop(){

        if( empty() ) return;

        _head->next = _head->next->next;
        delete _head->next->prev;
        _head->next->prev = _head;
        _size--;
    }

    bool empty(){
        return _size == 0;
    }

    const T & front(){
        return _head->next->data;
    }

};



void checkElimination( string & balls, int cursor ){
    if( balls.empty() ){ return; }
    int i = 1; int l = cursor, r = cursor, len = balls.size();
    while( cursor-i > -1 ){
        if( balls[cursor-i] != balls[cursor] ) break;
        l = cursor - (i++);
    }
    i = 1;
    while( cursor+i < len ){
        if( balls[cursor+i] != balls[cursor] ) break;
        r = cursor + (i++);
    }
    if( r - l > 1 ){
        balls.erase( l,r-l+1 );
        if( balls.size()>2 ) checkElimination( balls, l ); // 删除[l,r]区间后 如果存在继续消除可能时,原右侧必不为空,右侧第一个将取代原L。
    }
}

int main()
{
    string balls; int count;    // 主要变量
    int t; char c;              // 缓存变量

    cin>>balls;                 // 读取初始化彩球
    cin>>count;                 // 读取初始化数量

    queue<opr> oprs;            // 操作队列

    while( cin >> t ){          // 读取数字
        cin >> c;               // 读取颜色
        oprs.push( opr(t,c) );  // 压入队列
    }

    while( !oprs.empty() ){
        // cout<< oprs.front().t << " " << oprs.front().c << endl;
        t = oprs.front().t;
        c = oprs.front().c;
        balls.insert( t, 1, c );
        checkElimination( balls, t );
        oprs.pop();
        cout << (balls.empty() ? "-" : balls) << endl;
    }
    // cout << oprs.size() << endl;
    // cout<< balls << endl << count << endl << oprs.front().c << endl;
}

编译结果 95/100 最坏结果 204ms 14388KB。

这样看来还需要进一步优化。 20200629

格雷码

数据结构、算法与应用 第一张练习 26

两个代码之间的 海明距离 (Hamming distance) 是对应位不等的数量。 例如:100和010的海明距离是2。 一个(二进制)格雷码是一个代码序列,其中任意相邻的两个代码之间的海明距离是1。 子集生成的序列 000,100,010,001...111 不是格雷码,因为100,010海明距离是2。 而三位代码序列 000,100,110,010,011,111,101,001是格雷码。

在代码序列的一些应用中,从一个代码到下一个代码的代价取决于它们的海明距离。因此我们希望这个代码序列是格雷码。格雷码可以用代码变化的位置序列简洁地表示。 对于上面的格雷码,位置序列是1,2,1,3,1,2,1.

令g(n)是一个n元素的格雷码的位置变化序列。以下是g的递归定义:

    1                   n=1
    g(n-1),n,g(n-1)     n>1

注意这个是位置变化序列,并不是格雷码生成。

以下为算法

递归版:

#include <iostream>
#include <cmath>
/*
 *  格雷码序列数量是 2^n,相应的变化序列数量是 2^n - 1
 */
int * GrayCodeChangeSequence( int n ){
    int len   = pow(2,n)-1;
    int * arr = new int[len];
    if( n<2 ){ arr[0]=1; return arr; }

    int half  = (len-1)>>1;
    int * half_arr = GrayCodeChangeSequence( n-1 );

    for( int i=0; i<half; i ++ ){
        arr[i] = half_arr[i];
    }
    arr[half] = n;
    for( int i=0; i<half; i ++ ){
        arr[i+half+1] = half_arr[i];
    }

    return arr;
}

void testGCCS( int n ){

    int * b = GrayCodeChangeSequence(n);
    for( int i = 0; i< pow(2,n)-1 ; i++ ){
        std::cout << b[i] << ' ';
    }
    std::cout << endl;
    delete[] b;
}

int main()
{
    testGCCS(1);
    testGCCS(2);
    testGCCS(3);
    testGCCS(4);
    testGCCS(5);
}

测试分别输出:

1
1 2 1
1 2 1 3 1 2 1
1 2 1 3 1 2 1 4 1 2 1 3 1 2 1
1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1

优化

实际上格雷码修改序列生成和斐波那契数列的生成效率是需要进一步优化的,原因在于每一次收到递归结果,都需要遍历一次结果并且覆盖到当前的序列中。从渐进意义上来说,复杂度是O(n2) 而且相对于序列的长度增长渐进意义上远大于n,这个时候如果能够在一次遍历的情况下配合少量计算那么可以将复杂度降低至O(n)

- 阅读剩余部分 -

数据结构、算法与应用 第一张练习 23

当两个非负整数x和y都是0的时候,他们的最大公约数是0. 当两者至少有一个不是0的时候,他们的最大公约数是可以除尽二者的最大整数。 因此gcd(0,0)=0, gcd(10,0)=gcd(0,10)=10,而gcd(20,30)=10.

求最大公约数的欧几里得算法(Euclid's Algorithm)是一个递归算法:

    x                       (y=0)
    gcd(y,x mode y)         (y>0)

其中mod是模数运算子(modulo operator),相当于C++取余操作符%.

以下为算法

递归版:

int GCD( int x, int y ){

    if( y==0 ){
        return x;
    }
    return GCD( y, x%y );
}

数据结构、算法与应用 第一张练习 19,20

阶乘 n! Factorial

阶乘是非常常见的数学计算以及算法入门问题。 其中 0,1,2,6,24,120... fn = n ( n<=1 ) fn = n * fn(n-1) (n>1) 使用递归实现是非常直观和简单的:

递归版本
int factorial( int n ){
    return n>1 ? n*factorial(n-1) : n;
}
迭代版本
int factorial( int n ){
    int res = n;
    while( n>1 ){
        res *= --n;
    }
    return res;
}

斐波那契 Fibonacci

1.斐波那契数

斐波那契数列是算法里最基础的概念了。

其中 0,1,1,2,3,5,8... fn = n ( n<=1 ) fn = fn(n-2) + fn(n-1) ( n>1 )

同样递归版本是简单而直观的:

递归版:
int fabonacci( int n ){
    return n>1 ? fabonacci( n-1 ) + fabonacci( n-2 ) : n;
}

递归版的Fibonacci效率是有严重缺陷的,主要是由于在合并两次之和时,两边进行了重复的计算,而每次重复计算也都是包含了更多迭代版本中更多的重复。这里由于递归而造成的重复计算复杂度为 O( 2∧n )

迭代版:
/*
 * n>0 当n<=0时,默认不考虑
 * 使用双指针缓存本次和上次结果,并进一步迭代
 */
int fabonacci( int n ){
    int l = 1;
    int r = 1;
    for( int i = 2; i <= n; i ++ ){
        r = l + r;
        l = r - l;
    }
    return r;
}

迭代版的斐波那契数的复杂度仅为O(n)

2.Fibonacci数列

/*
 * 返回数组首元素,数组长度为n n>0
 */
#include <iostream>
#include <cstdlib>
int * fabonacci( int n ){
    int * a = new int[n];
    a[0] = 1;
    if( n<2 ) return a;
    a[1] = 1;
    for( int i = 2; i < n; i++ ){
        a[i] = a[i-1] + a[i-2];
        a[i-1] = a[i] - a[i-2];
    }
    return a;
}

int main()
{
    int n   = 8;
    int * b = fabonacci(n);
    for( int i = 0; i<n; i++ ){
        std::cout << b[i] << std::endl;
    }
}

这段代码会输出:

1
1
2
3
5
8
13
21

最长公共子序列是一个经典的基础算法问题 在两个序列中 如果序列1中的元素a也存在于序列2,则认为a是1,2的公共元素。 当序列3中的每一个元素都能够满足在不改变次序的情况下依次属于1,2,那么则认为3是1,2的公共子序列。多个公共子序列中,元素最多的即为最长公共子序列。

在学堂在线的算法课程中,有比较详细的课程讲述这个算法的构思。但是没有给出具体的实现,这里来自己实现一下。

首先使用表格模拟排列组合的所有情况: 以{a,b,c,d,e},{a,b,q,c,b}为例:

A\B a b q c b
a 1 1 1 1 1
b 1 2 2 2 2
c 1 2 2 3 3
d 1 2 2 3 3
e 1 2 2 3 3

实际上看到这样的填充,直觉上就应该反应出来,使用二维数组来解决。 其中当 A[i]!=B[j]时,取左方或者上方更大的,而A[i]==B[j]的时候,取T[i-1][j-1] + 1。这里i=0或j=0的时候就不方便了,所以给矩阵默认增加一行 0 行。即

A\B 0 a b q c b
0 0 0 0 0 0 0
a 0 1 1 1 1 1
b 0 1 2 2 2 2
c 0 1 2 2 3 3
d 0 1 2 2 3 3
e 0 1 2 2 3 3

- 阅读剩余部分 -

数据结构、算法与应用 C++语言描述

第一章 习题25

子集生成法(Subset Generation)

三元素集{a,b,c}的子集是:{},{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}。 这些子集又可以使用01序列来表示,分别是000,100,010,001,110,101,011,111。 0/1分别代表着 含有/不含 原集合中的对应元素。

输出n个元素的所有子集(以01序列的形式)。

在网上看了一下基本上最终输出的都是数组,但并没有按照题目输出01序列。所以我这里严格按照题目来解。

分析

子集生成是一个完全排列组合问题,包括退化情况空集,以及极限情况自身。 其他的情况分别是[1,n)个元素的任意组合。 所以如果递归的话,也就是每一次元素数量+1 或者是-1,如果不是输出01序列,那么输出的元素个数就刚好等于递归中的n。输出序列的时候,只需要在其他位置补0即可。而补0逻辑也可以反过来考虑,即默认是n个0 e.g. 0000,随着循环的i改变,在不同的位置上填1e.g. 0001,0010,0100,1000,这样更加便捷。

至此,已经有了算法的模型了:

/* Subset Generation */
#include <iostream>
#include <string>

using namespace std;

template <typename T>
void subsetGeneration( T* const A, int len, string code = "", int focus = 0 ){

    if( focus > len ) return;
    if( focus == len ){ cout << string(len,'1') << endl; return; }
    if( focus == 0 ){ cout << string(len,'0') << endl; }

    if( code == "" ){ code = string(len,'0'); }

    code[focus] = '1';
    for( int i = focus; i<len; i++ ){
        code[i] = '1';
        cout << code << endl;
        code[i] = '0';
    }

    subsetGeneration( A, len, code, focus + 1 );
}
int main(){

    subsetGeneration( "abcd", 4 );
    return 0;
}

思考1 上述算法已经成功解题,但是思维略显复杂,直觉上就感觉不是一个优质解。

- 阅读剩余部分 -