算法04

题目：有一个矩形数组，第一行是1，2，3，4....,第二行是在第一行的末尾的数又开始逐渐加1，然后我们要回形打印这个数组

 1 #include<iostream>
 2 using namespace std;
 3 int arry[100][100];
 4 int col, row;
 5 void func2(int tR, int tC, int dR, int dC)
 6 {
 7     if (tR == dR)
 8     {
 9         for (int i = tC; i <= dC; i++)
10         {
11             cout << arry[tR][i] << " ";
12         }
13     }
14     else if (tC == dC)
15     {
16         for (int i = tR; i <= dR; i++)
17         {
18             cout << arry[i][tC] << " ";
19         }
20     }
21     else
22     {
23         int curC = tC;
24         int curR = tR;
25         while (curC != dC)
26         {
27             cout << arry[tR][curC] << " ";
28             curC++;
29         }
30         while (curR != dR)
31         {
32             cout << arry[curR][dC] << " ";
33             curR++;
34         }
35         while (curC != tC)
36         {
37             cout << arry[dR][curC] << " ";
38             curC--;
39         }
40         while (curR != tR)
41         {
42             cout << arry[curR][tC] << " ";
43             curR--;
44         }
45     }
46 }
47 void func1(int col, int row)
48 {
49     int tR = 0;
50     int tC = 0;
51     int dR = row;
52     int dC = col;
53     while (tR <= dR && tC <= dC)
54     {
55         func2(tR++, tC++, dR--, dC--);
56     }
57 }
58 int main()
59 {
60     printf("请输入行和列:");
61     cin >> row;
62     cin >> col;
63     int count_num = 0;
64     for (int i = 0; i < row; i++)
65     {
66         for (int j = 0; j < col; j++)
67         {
68             arry[i][j] = count_num;
69             count_num++;
70         }
71     }
72     for (int i = 0; i < row; i++)
73     {
74         for (int j = 0; j < col; j++)
75         {
76             cout << arry[i][j] << " ";
77         }
78         cout << endl;
79     }
80     func1(--col, --row);
81     return 0;
82 }

View Code

题目：现在有一个正方形，然后我们现在要将这个正方形上的数原地顺时针旋转90度，原地旋转不能借助于另一个数组

 1 #include<iostream>
 2 using namespace std;
 3 int arry[100][100];
 4 int col, row;
 5 void func2(int tR, int tC, int dR, int dC)
 6 {
 7     int tmp = 0;
 8     int item = dC - tC;
 9     for (int i = 0; i != item;i++)
10     {
11         tmp = arry[tR][tC + i];
12         arry[tR][tC + i] = arry[dR - i][tC];
13         arry[dR - i][tC] = arry[dR][dC - i];
14         arry[dR][dC - i] = arry[tR + i][dC];
15         arry[tR + i][dC] = tmp;
16     }
17 }
18 void func1(int col, int row)
19 {
20     int tR = 0;
21     int tC = 0;
22     int dR = row - 1;
23     int dC = col - 1;
24     while (tR <= dR)
25     {
26         func2(tR++, tC++, dR--, dC--);
27     }
28 }
29 int main()
30 {
31     printf("请输入行和列:");
32     cin >> row;
33     cin >> col;
34     int count_num = 0;
35     for (int i = 0; i < row; i++)
36     {
37         for (int j = 0; j < col; j++)
38         {
39             arry[i][j] = count_num;
40             count_num++;
41         }
42     }
43     func1(col, row);
44     for (int i = 0; i < row; i++)
45     {
46         for (int j = 0; j < col; j++)
47         {
48             cout << arry[i][j] << " ";
49         }
50         cout << endl;
51     }
52     return 0;
53 }

View Code

题目：有一个矩形，现在要之字形打印这个矩形(也称为蛇形打印)

 1 #include<iostream>
 2 using namespace std;
 3 int arry[100][100];
 4 int col, row;
 5 void func2(int aR, int aC, int bR, int bC,bool fromUp)
 6 {
 7     if (fromUp)
 8     {
 9         while (bR != aR - 1)
10         {
11             cout << arry[bR--][bC++];
12         }
13     }
14     else
15     {
16         while (aR != bR + 1)
17         {
18             cout << arry[aR++][aC--];
19         }
20     }
21     cout << endl;
22 }
23 void func1(int row, int col)
24 {
25     int aR = 0;
26     int aC = 0;
27     int bR = 0;
28     int bC = 0;
29     int endR = row - 1;
30     int endC = col - 1;
31     bool fromUp = true;
32     while (aR != endR + 1)
33     {
34         func2(aR,aC,bR,bC,fromUp);
35         aR = aC == endC ? aR+1 : aR;
36         aC = aC == endC ? aC : aC+1;
37         bC = bR == endC ? bC + 1 : bC;
38         bR = bR == endR ? bR : bR+1; //这四个表达式要有顺序
39         fromUp = !fromUp;
40     }
41 
42 }
43 int main()
44 {
45     printf("请输入行和列:");
46     cin >> row;
47     cin >> col;
48     int count_num = 0;
49     for (int i = 0; i < row; i++)
50     {
51         for (int j = 0; j < col; j++)
52         {
53             arry[i][j] = count_num;
54             count_num++;
55         }
56     }
57     for (int i = 0; i < row; i++)
58     {
59         for (int j = 0; j < col; j++)
60         {
61             cout << arry[i][j] << " ";
62         }
63         cout << endl;
64     }
65     cout << endl;
66     func1(col, row);
67     return 0;
68 }

View Code

题目：一个矩形，从左到右和从上到下都是逐渐增大的，我们要在这个数组中找到一个特定的数，并且将他的位置返回

 1 #include<iostream>
 2 using namespace std;
 3 int arry[100][100];
 4 int col, row;
 5 void func1(int col,int num)
 6 {
 7     int curR = 0;
 8     int curC = col - 1;
 9     while (arry[curR][curC] != num) //循环直到找到这个数才停止
10     { //循环内部只有两个步骤，向左走和向下走
11         while (arry[curR][curC - 1] >= num)  //记住要加上这个等于号
12         {
13             curC--;
14         }
15         curC--;
16         while (arry[curR + 1][curC] <= num)  //记住要加上这个等于号
17         {
18             curR++;
19         }
20     }
21     cout << curR << "   " << curC;
22 }
23 int main()
24 {
25     printf("请输入行和列:");
26     cin >> row;
27     cin >> col;
28     int count_num = 0;
29     for (int i = 0; i < row; i++)
30     {
31         for (int j = 0; j < col; j++)
32         {
33             arry[i][j] = count_num;
34             count_num++;
35         }
36     }
37     for (int i = 0; i < row; i++)
38     {
39         for (int j = 0; j < col; j++)
40         {
41             cout << arry[i][j] << " ";
42         }
43         cout << endl;
44     }
45     cout << endl;
46     int num; //要查找的数
47     cin >> num;
48     func1(col,num);  //可以从右上角开始找，也可以从左下角开始找，所有坐标只需要一个值
49     return 0;
50 }

View Code

题目：有一个链表，链表的单个结点就是一个数据域是一个整数的结构，然后我们要判断一个链表是否是回文结构

思路1：使用一个栈结构，将链表的每一个结点一次入栈，然后将链表和这个栈进行比较，时间复杂度 O(n) ,额外空间复杂度 O(n)

思路2：使用一个快指针辅助慢指针定位到链表的中间，然后将链表中间以后的结点翻转，然后从两头开始进行比较，此思路代码如下

#include <iostream>
using namespace std;

struct fun
{
    int num;
    fun *next;
};

void  Create(fun* &a)
{
    char ch;
    cin >> ch;
    a->num = ch - 48;
    a->next = NULL;
    cin >> ch;
    fun * b = a;
    while (ch != '#')
    {
        int num = ch - 48;
        b->next = new fun;
        b = b->next;
        b->num = num;
        b->next = NULL;
        cin >> ch;
    }
}

bool Distinguish(fun * h)
{
    fun *n1 = h;
    fun *n2 = h;
    while (n2->next != NULL && n2->next->next != NULL)
    {
        n1 = n1->next;
        n2 = n2->next->next;
    }
    n2 = n1->next;
    n1->next = NULL;
    fun *n3 = NULL;
    while (n2 != NULL)  //这个循环将链表后半部分翻转
    {
        n3 = n2->next;
        n2->next = n1;
        n1 = n2;
        n2 = n3;
    }
    n3 = n1; //保存最后一个结点
    n1 = h;
    n2 = n3;
    bool res = true;
    while (n1 != NULL)
    {
        if (n1->num != n2->num)
        {
            res = false;
            break;
        }
        n1 = n1->next;
        n2 = n2->next;
    }
    n2 = n3->next;
    n3->next = NULL;
    while (n2 != NULL)
    {
        n1 = n2->next;
        n2->next = n3;
        n3 = n2;
        n2 = n1;
    }
    return res;
}

int main()
{
    fun *a = new fun;
    Create(a);
    fun * b = a;
    while (b != NULL)
    {
        cout << b->num<<endl;
        b = b->next;
    }
    cout << "



";
    cout<<Distinguish(a)<<endl;
    return 0;
}

View Code

题目：将单向链表划分为左边小中间相等右边大的形式

思路1：将链表中的各个节点用一个数组存贮，然后将数组排好序，最后按照数组来重新组织这个链表

思路2：给三个节点数据类型，第一遍遍历链表，然后将第一个小于num的写入第一个节点，即将第一个等于num的写入第二个节点，将第一个大于num的写入第三个节点。

题目：有一个链表，这个链表的节点的指针域一个是next指针，另一个是random指针，next指针指向下一个，random指针随意指针次链表中一个结点，现在我们要深拷贝这个链表；

思路1：先复制一个链表，复制的链表仅满足原链表的next指针，然后使用一个类似于Python中的字典结构，我们将原链表和复制后的链表按照对应关系存入这个类似于Python中字典的哈希表结构，原链表的结点作为key，复制后链表的结点作为value，然后我们就可以根据这个哈希表的结构轻松的复制rando指针关系

思路2：思路1使用了一个额外的哈希表结构，然后我们可以巧妙地设计结构来省下这个哈希表的结构，我们可以将原结点的头结点的next指针指向复制后的链表的头结点，这样依次下去，也可以做到类似于Python中的字典结构。

题目：单链表可能有环也可能没有环。给定两个单链表的头结点，head1和和head2，两个链表可能相交也可能不相交。请实现一个函数，如果两个链表相交，则返回第一个相交的结点，如果不想交则返回null。要求：如果链表1的长度是N，链表2的长度是M，时间复杂度为O(M+N)，额外空间复杂度为O(1)。

这道题其实可以分解，首先来实现判断一个单链表是否有环：

思路1：我们可以从头结点还是遍历，将遍历的结点存入一个结构，每次遍历到新的结点都去这个结构中找是否已经存在，如果第一次找到某个节点已经在这个结构中存在，这个结点就是入环的头结点，如果遍历到链表的租后一个元素还没有找到说明这个链表没有环。

思路2：我们设置两个指针，一个快指针一个满指针，快指针一次走两步，满指针一次走一步，如果走的过程中，快指针遇到了空，则必然没有环，没有遇到则有环，如何找到这个环的入口结点呢？快指针一次走两步，满指针一次走一步，当快指针和满指针相遇的时候，快指针指向头结点，此时快指针一次走一步，当快指针和满指针相遇的时候，这个结点就是入环的结点，这个定理我不会证明。

现在有环无环的问题解决了，我们就根据有环无环分为三种情况

　　第一种，都没有环。我们可以先遍历一条链表，然后将他的每个结点存入map，在遍历另一条链表，如果有相等的结点，这个结点就是相交的结点，返回这个结点。这种方法借助了一个额外的map，我们也可以省去这个map结构，我们首先遍历第一条链表，得到len1长度和最后一个结点，然后遍历第二条链表，得到len2长度和最后一个结点，然后比较这两个最后结点的地址，如果不相等则没有相交，如果相等则有相交的结点，然后分别从头开始遍历两条链表，由于已经知道两条链表的长度，我们假设len1>len2,就先让第一条链表先走len1-len2步，然后一起走，遇到第一个相等的结点就返回。

　　第二种，一条链表有环一条链表没有环，则不可能相交

　　第三中，两条链表都有环，情况较为复杂，看视屏第四节