经典算法题总结

Posted on | In

基础知识

赋值运算符函数

知识点：

(1)类的成员函数可以直接访问作为其参数的同类型对象的私有成员。

(2) 一个类关键的函数包括 构造函数 拷贝构造 析构函数 运算符重载（=赋值重载）

(3) 在=赋值重载函数中 需要注意 返回值是引用 可以作为参数接着传递 以此实现多次赋值；需要判断传入参数是否是this
若是this 一旦释放内存 传入参数内存也会丢失 找不回需要赋值的内容了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
class MyString
{
public:
MyString(char *p_data=nullptr);
MyString(const MyString& other);
~MyString(void);

MyString& operator = (const MyString& other);
void print();
private:
char *m_data;
};

MyString::MyString(char *p_data){

if(p_data == nullptr)
{
    m_data = new char[1];
    m_data[0]='\0';
}else{

    int length = strlen(p_data);
    m_data = new char[length+1];
    strcpy(m_data, p_data);
}
}

MyString::MyString(const MyString &other)
{
int length = strlen(other.m_data);
m_data = new char[length+1];
strcpy(m_data, other.m_data);
}

MyString::~MyString()
{
delete []m_data;
}

MyString& MyString::operator =(const MyString& other)
{
if(this == &other)
    return *this;

delete []m_data;
m_data = nullptr;

int length = strlen(other.m_data);
m_data = new char[length+1];
strcpy(m_data, other.m_data);

return *this;
}

// 考虑安全性写法 new出现异常
MyString& MyString::operator =(const MyString& other)
{
    if(this != &other)
    {
        MyString str_tmp(other);
        char * ch_tmp = str_tmp.m_data;
        str_tmp.m_data = m_data;
        m_data = ch_tmp;
    }

    return *this;
}


void MyString::print()
{
cout<<m_data<<endl;
}

实现单例模式

在多线程环境下只存在一个实例

1
2
3
4
5
6
7
8
9
10
11
12
13
Class Singleton
{
private:
  Singleton();

public:
  static Singleton* getInstance()
  {
      static Singleton instance;
      return &instance;
  }

}

模板化后写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
template <class T>
class singleton
{
protected:
    singleton(){};
private:
    singleton(const singleton&){};//禁止拷贝
    singleton& operator=(const singleton&){};//禁止赋值
    static T* m_instance;
public:
    static T* GetInstance();
};


template <class T>
T* singleton<T>::GetInstance()
{
    return m_instance;
}

template <class T>
T* singleton<T>::m_instance = new T();

二维数组的查找

分析 查找时出现的三种情况 即可得到答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
bool find(int* matrix, int rows, int columns, int number)
{
    bool found = false;
    if(matrix!=nullptr && rows>0 && columns>0)
    {
        int row = 0;
        int column = columns-1;

        while(row<rows && column>=0)
        {
            if(matrix[row*column+column] == number)
            {
                found = true;
                break;
            }else if(matrix[row*column+column]>number)
                --column;
            else
                ++row;

        }
    }

    return found;
}

替换空格

从尾部开始替换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
void replace_blank(char str[], int length)
{
    if(str==nullptr || length<=0)
        return ;

    int origin_length = 0;
    int blank_length = 0;
    int i = 0;
    while(str[i]!='\0')
    {
        ++origin_length;
        if(str[i]==' ')
            ++blank_length;
        ++i;
    }

    int total = origin_length + blank_length*2;
    if(total > length)
        return;

    int index_origin = origin_length;
    int index_new = total;
    while(index_origin>=0 && index_new>index_origin)
    {
        if(str[index_origin]==' ')
        {
            str[index_new--] = '0';
            str[index_new--] = '2';
            str[index_new--] = '%';
        }else{
            str[index_new--] = str[index_origin];
        }

        --index_origin;
    }
}

从头到尾打印链表

使用栈或递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void print_listnode_reverse(ListNode *phead)
{

    stack<ListNode*> nodes;

    ListNode* node = phead;
    while(node!=nullptr)
    {
        nodes.push(node);
        node = node->next;
    }

    while(!nodes.empty())
    {
        node = nodes.top();
        cout<<node->key<<endl;
        nodes.pop();
    }

}

重建二叉树

用两个站实现队列

旋转数组的最小数字

斐波那契数列

计算1出现的次数

第八章 新增试题

滑动窗口的最大值

使用双向队列 该队列保存当前滑动窗口的最大值 下一个数进来时
与当前值进行判断 大于 删除当前值 还需判断最大值是否在活动窗口内

矩阵中的路径

回溯法 判断当前节点的四周节点的数据与下一个数据是否相同 不同恢复原来状态。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
bool hasPathCore(char* matrix, int row, int col, int rows, int cols, char* str, bool *visited, int& length)
{
     cout<<"len"<<length<<" "<<row<<" "<<col<<endl;
    if(str[length] == '\0')
        return true;

    bool hasPath = false;


    if(row>=0 && row<rows && col>=0 && col<cols
            && matrix[row*cols+col] == str[length] && !visited[row*cols+col])
    {
        visited[row*cols+col] = true;
        cout<<"len"<<length<<" "<<matrix[row*cols+col]<<endl;
        ++length;
        cout<<length<<endl;

        hasPath = hasPathCore(matrix, row, col-1, rows, cols, str, visited, length)
                || hasPathCore(matrix, row-1, col, rows, cols, str, visited, length)
                || hasPathCore(matrix, row, col+1, rows, cols, str, visited, length)
                || hasPathCore(matrix, row+1, col, rows, cols, str, visited, length);

        if(!hasPath)
        {
            --length;
            visited[row*cols+col] = false;
        }
    }
    return hasPath;

}

bool hasPath(char* matrix, int rows, int cols, char* str)
{
    if(matrix == nullptr || rows<1 || cols<1 || str==nullptr)
        return false;
    bool *visited = new bool[rows*cols];
    int length = 0;
    memset(visited, 0, rows*cols);
    for(int i=0;i<rows;++i)
    {
        for(int j=0;j<cols;++j)
        {
            //hasPathCore(matrix, i,j,rows,cols, str,visited,length);
            if(hasPathCore(matrix, i,j,rows,cols, str,visited,length))
            {
               return true;
            }
        }
    }

    delete []visited;

    return false;

}

机器人的运动范围

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
// 67 robot moving
int get_digit_sum(int n)
{
    int sum = 0;
    while(n>0)
    {
        sum = sum+n%10;
        n/=10;
    }
    return sum;
}

bool check(int threshold, int row, int col, int rows, int cols, bool *visited)
{
    if(row>=0 && row<rows && col>=0 && col<cols &&
            get_digit_sum(row)+get_digit_sum(col) <= threshold && !visited[row*cols+col])
        return true;
    return false;
}
int move_count_core(int threshold, int row, int col, int rows, int cols, bool *visited)
{
    int count = 0;

    if(check(threshold, row, col, rows, cols, visited))
    {
        visited[row*cols+col] = true;
        //cout<<row<<" "<<col<<endl;
        count = 1 + move_count_core(threshold, row-1, col, rows, cols, visited)
                + move_count_core(threshold, row+1, col, rows, cols, visited)
                + move_count_core(threshold, row, col-1, rows, cols, visited)
                + move_count_core(threshold, row, col+1, rows, cols, visited);
    }

    return count;

}
int move_count(int threshold, int rows, int cols)
{

    bool *visited = new bool[rows*cols];
    memset(visited, 0, sizeof(bool)*rows*cols);

    int count  = move_count_core(threshold, 0, 0, rows, cols, visited);

    cout<<count<<endl;
    delete [] visited;

    return count;
}

void test_robot(char *name, int threshold, int rows, int cols, int expected)
{
    if(name != nullptr)
        cout<<name<<" ";
    int count = move_count(threshold, rows, cols);
    if(count == expected)
    {
        cout<<"passed"<<endl;
    }else{
        cout<<"Failed"<<endl;
    }
}

int main()
{
    test_robot("Test1", 5,10,10,21);
    test_robot("Test2", 15,20,20,359);
    test_robot("Test3", 10,1,100,29);
    test_robot("Test4", 10,1,10,10);

}