ChunNote
0%

发表于 更新于 分类于

问题描述

给定一个整数，范围是-2^31 ~ 2^32-1，要求返回这个整数的逆序整数。如果得到的逆序整数超过整形的范围-2^31 ~ 2^32-1，则返回0。题目链接：**点我**

阅读全文 »

发表于 更新于 分类于

问题描述

给出一个待匹配的字符串A和匹配的字符串B，要求判断B是否是A的子字符串。如果是则输出匹配的A字符串的起始下标，如果不是子字符串则输出-1。

注意：如果B字符串是空的，返回 0 ，这与String.indexOf函数效果相同

阅读全文 »

发表于 更新于 分类于 
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
74
75
76
77
78
79
80
81
82
83
84
85
#include <iostream>
using namespace std;

//  维护堆排序，采用下调的方式
void downAdjust(int k, int* a, int n) 
{
    int tem;
    if (2 * k + 1 >= n)  //  如果该结点是叶结点
        return;
    //  如果该结点只有左孩子
    if (2 * k + 2 >= n) 
    {
        //  如果该结点的值比左孩子的值小，则交换，然后继续下调操作
        //  否则停止下调操作
        if (a[k] < a[2 * k + 1]) 
        {
            tem = a[k];
            a[k] = a[2 * k + 1];
            a[2 * k + 1] = tem;
            downAdjust(2 * k + 1, a, n);
        }
        else
        {
            return;
        }
    } 
    else 
    {
        //  如果该结点值比左右孩子的值都大，则下调操作结束
        if (a[k] >= a[2 * k + 1] && a[k] >= a[2 * k + 2])
            return;
        //  如果该结点和左孩子都比右孩子小，则将该结点与右孩子交换，然后继续下调操作
        if (a[2 * k + 1] < a[2 * k + 2]) 
        {
            tem = a[k];
            a[k] = a[2 * k + 2];
            a[2 * k + 2] = tem;
            downAdjust(2 * k + 2, a, n);
        } 
        else 
        {
            tem = a[k];
            a[k] = a[2 * k + 1];
            a[2 * k + 1] = tem;
            downAdjust(2 * k + 1, a, n);
        }
    }
}

//  堆排序的函数
void heapsort(int* a, int n) 
{
    int tem;
    // 先把所有的值按照完全二叉树排好，然后运用下调方式维护堆，从而建立一个堆
    for (int i = n - 1; i >= 0; i--)
        downAdjust(i, a, n);
    //  将堆顶元素与最后一个元素交换，然后运用下调方式维护堆，直至排序完成
    for (int i = n - 1; i >= 0; i--) 
    {
        tem = a[0];
        a[0] = a[i];
        a[i] = tem;
        downAdjust(0, a, i);
    }
}

int main()
{
    int n;
    cout << "本程序采用堆排序对整数进行排序，以升序结果输出" << endl;
    cout << "请输入要排序的整数个数：";
    cin >> n;
    int* a = new int[n];
    cout << "请输入您要排序的数据:" << endl;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    heapsort(a, n);
    cout << "排序后的结果是：" << endl;
    for (int i = 0; i < n; i++)
        cout << a[i] << " ";
    cout << endl;
    delete []a;
    return 0;
}

发表于 更新于 分类于 
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
#include <iostream>
using namespace std;

void swap(int& a, int& b)
{
    int temp;
    temp = a;
    a = b;
    b = temp;
}

void quick_sort(int* a, int start, int end)
{
    if (start >= end)
        return;
    int key = a[(start + end) / 2];
    int i = start, j = end;
    while (i <= j)  // the '=' can remove
    {
        // the '<' can not change to '<=', or it will wrong
        // for example, the array is 3, 3, 3, 3. In this way, the key is 3
        // if the condition is a[i] <= key, then i will increase to 4 which is out of the range of array
        while (a[i] < key)
            i++;
        // the '>' can not change to '>=', or it will wrong
        // for example, the array is 3, 3, 3, 3. In this way, the key is 3
        // if the condition is a[j] >= key, then i will decrease to -1 which is out of the range of array
        while (a[j] > key)
            j--;
        // must have this if condition, or it will wrong
        // for example, the array is 3, 5, 7, 1, 8, 6, 4, 2
        // if don't have the if condition, then the 5 will come to the left one and j will be -1
        // after that, the 5 will be in left one always, which is wrong obviously
        // must have "=", considerate the array 2, 3. if not "=", it will loop and can't stop
        if (i <= j)  
        {
            swap(a[i], a[j]);
            i++;
            j--;
        }
    }
    quick_sort(a, start, j);
    quick_sort(a, i, end);
}

int main()
{
    int n;
    cout << "please input the number count you want to sort: ";
    cin >> n;
    int* a = new int[n];
    cout << "please input the number, seperate with space" << endl;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    quick_sort(a, 0, n - 1);
    cout << "the sort result is: ";
    for (int i = 0; i < n; i++)
        cout << a[i] << " ";
    cout << endl;
    delete []a;
    system("pause");
    return 0;
}