0%

发表于 更新于

牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。例如，“student. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a student.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？

全翻转，再翻转单词

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
class Solution {
public:
    void swap(string &text, const int a, const int b)
    {
        int x = a, y = b - 1;
        while (x < y)
        {
            char temp = text[x];
            text[x] = text[y];
            text[y] = temp;
            x++;
            y--;
        }
    }
    string ReverseSentence(string str) {
        const int l = str.length();
        int a = 0;
        for (int i = 0; i < l; i++)
        {
            if (str[i] == ' ')
            {
                swap(str, a, i);
                a = i + 1;
            }
            else if (i == l - 1)
            {
                swap(str, a, i + 1);
                a = i + 1;
            }
        }
        if (a != 0)
        {
            swap(str, 0, l);
        }
        return str;
    }
};

发表于 更新于

汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。是不是很简单？OK，搞定它！

翻转3次

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
class Solution {
public:
    void swap(string &text, const int a, const int b)
    {
        int x = a, y = b - 1;
        while (x < y)
        {
            char temp = text[x];
            text[x] = text[y];
            text[y] = temp;
            x++;
            y--;
        }
    }
    string LeftRotateString(string str, int n) {
        const int length = str.length();
        if (length <= 1)
        {
            return str;
        }
        n %= length;
        if (n == 0)
        {
            return str;
        }
        swap(str, 0, n);
        swap(str, n, length);
        swap(str, 0, length);
        return str;
    }
};

发表于 更新于

输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。

两端向内，小了挪大，大了挪小

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
class Solution {
public:
    vector<int> FindNumbersWithSum(vector<int> array,int sum) {
        vector<int> result;
        if (array.size() > 1)
        {
            auto start = array.begin(), end = array.end() - 1;
            while (start < end)
            {
                if (*start + *end == sum)
                {
                    result.push_back(*start);
                    result.push_back(*end);
                    break;
                }
                else if (*start + *end < sum)
                {
                    start++;
                }
                else
                {
                    end--;
                }
            }
        }
        return result;
    }
};

发表于 更新于

所有和为S的连续正数序列（至少有2个数）

1~2开始，小了挪右端点，大了挪左端点

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
class Solution {
public:
    vector<vector<int> > FindContinuousSequence(int sum) {
        vector<vector<int>> results;
        if (sum >= 3)
        {
            int a = 1, b = 2, current_sum = 3, mid = sum / 2;
            while (a <= mid)
            {
                if (current_sum < sum)
                {
                    b++;
                    current_sum += b;
                }
                else
                {
                    if (current_sum == sum)
                    {
                        vector<int> r;
                        for (int i = a; i <= b; i++)
                        {
                            r.push_back(i);
                        }
                        results.push_back(r);
                    }
                    current_sum -= a;
                    a++;
                }
            }
        }
        return results;
    }
};

发表于 更新于

一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

异或2次即为0，数组异或和中1位即为两数相异的bit，以最右的1（取反+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
class Solution {
public:
    void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
        switch (data.size())
        {
            case 0:
                return;
            case 1:
                *num1 = data[0];
                return;
            case 2:
                *num1 = data[0];
                *num2 = data[1];
                return;
            default:
                int sum = 0;
                for (const int number: data)
                {
                    sum ^= number;
                }
                sum = sum & (~sum + 1);
                *num1 = 0;
                *num2 = 0;
                for (const int number: data)
                {
                    if (sum & number)
                    {
                        *num1 ^= number;
                    }
                    else
                    {
                        *num2 ^= number;
                    }
                }
        }
    }
};

发表于 更新于

输入一棵二叉树，判断该二叉树是否是平衡二叉树。

AVL子树深度差小于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
class Solution {
public:
    int get_depth(const TreeNode* pRoot)
    {
        if (pRoot == nullptr)
        {
            return 0;
        }
        else
        {
            const int left = get_depth(pRoot->left);
            if (left == -1)
            {
                return -1;
            }
            else
            {
                const int right = get_depth(pRoot->right);
                if (right == -1)
                {
                    return -1;
                }
                else
                {
                    if (abs(left - right) > 1)
                    {
                        return -1;
                    }
                    else
                    {
                        return max(left, right) + 1;
                    }
                }
            }
        }
    }
    bool IsBalanced_Solution(TreeNode* pRoot) {
        return get_depth(pRoot) != -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
/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
public:
    int TreeDepth(TreeNode* pRoot)
    {
        if (pRoot == nullptr)
        {
            return 0;
        }
        else
        {
            queue<TreeNode*> q;
            int depth = 0;
            int kids_finished = 0;
            int total_kids = 1;
            q.push(pRoot);
            while (q.size() > 0)
            {
                TreeNode* current = q.front();
                q.pop();
                kids_finished++;
                if (current->left != nullptr)
                {
                    q.push(current->left);
                }
                if (current->right != nullptr)
                {
                    q.push(current->right);
                }
                if (kids_finished == total_kids)
                {
                    depth++;
                    kids_finished = 0;
                    total_kids = q.size();
                }
            }
            return depth;
        }
    }
};

发表于 更新于

统计一个数字在排序数组中出现的次数。

二分找n和n+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
class Solution {
public:
    int bin_search(const vector<int> &data, const int k)
    {
        int left = 0, right = data.size();
        while (left < right)
        {
            const int mid = (left + right) / 2;
            if (data[mid] > k)
            {
                right = mid;
            }
            else if (data[mid] == k)
            {
                right = mid;
            }
            else
            {
                left = mid + 1;
            }
        }
        return left;
    }
    int GetNumberOfK(vector<int> data ,int k) {
        int left = bin_search(data, k);
        int right = bin_search(data, k + 1);
        return right - left;
    }
};

发表于 更新于

输入两个链表，找出它们的第一个公共结点。

长度差、快慢指针

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
/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    int get_length(const ListNode* pHead)
    {
        int len = 0;
        while (pHead != nullptr)
        {
            pHead = pHead->next;
            len++;
        }
        return len;
    }
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        int a = get_length(pHead1);
        int b = get_length(pHead2);
        if (a < b)
        {
            int d = b - a;
            for (int i = 0; i < d; i++)
            {
                pHead2 = pHead2->next;
            }
        }
        else
        {
            int d = a - b;
            for (int i = 0; i < d; i++)
            {
                pHead1 = pHead1->next;
            }
        }
        while (pHead1 != pHead2)
        {
            if (pHead1 == nullptr || pHead2 == nullptr)
            {
                return nullptr;
            }
            else
            {
                pHead1 = pHead1->next;
                pHead2 = pHead2->next;
            }
        }
        return pHead1;
    }
};

发表于 更新于

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007

自左向右归并，数逆序数

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
class Solution
{
public:
    vector<int>::iterator it;
    int InversePairs(vector<int> &data)
    {
        it = data.begin();
        if (data.empty())
        {
            return 0;
        }
        vector<int> temp(data);
        return merge_sort(data.begin(), data.end(), temp.begin());
    }
    int merge_sort(const vector<int>::iterator data_begin, const vector<int>::iterator data_end, const vector<int>::iterator temp_begin)
    {
        int data_len = data_end - data_begin;
        if (data_len < 2)
        {
            return 0;
        }
        int mid_len = (data_len + 1) >> 1;
        auto data_mid = data_begin + mid_len, temp_mid = temp_begin + mid_len, temp_end = temp_begin + data_len;
        long long pair_counter = merge_sort(temp_begin, temp_mid, data_begin) + merge_sort(temp_mid, temp_end, data_mid), current_counter = 0;
        auto left = data_mid - 1, right = data_end - 1;
        for (auto dst = temp_end - 1; left >= data_begin && right >= data_mid; dst--)
        {
            if (*left > *right)
            {
                *dst = *left;
                current_counter += right - data_mid + 1;
                left--;
            }
            else
            {
                *dst = *right;
                right--;
            }
        }
        if (left >= data_begin)
        {
            copy(data_begin, left + 1, temp_begin);
        }
        else if (right >= data_mid)
        {
            copy(data_mid, right + 1, temp_begin);
        }
        return (pair_counter + current_counter) % 1000000007;
    }
};