0%

发表于 更新于

在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.

哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int FirstNotRepeatingChar(string str) {
        array<int, 256> table = {0};
        for (const char character: str)
        {
            table[character]++;
        }
        for (int i = 0; i < str.length(); i++)
        {
            if (table[str[i]] == 1)
            {
                return i;
            }
        }
        return -1;
    }
};

发表于 更新于

把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

类质数筛法

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
class Solution {
public:
    int GetUglyNumber_Solution(int index) {
        if (index <= 0)
        {
            return 0;
        }
        else
        {
            vector<int> numbers = {1};
            int i2 = 0, i3 = 0, i5 = 0;
            while (numbers.size() < index)
            {
                int max_number = min({numbers[i2] * 2, numbers[i3] * 3, numbers[i5] * 5});
                numbers.push_back(max_number);
                while (numbers[i2] * 2 <= max_number)
                {
                    i2++;
                }
                while (numbers[i3] * 3 <= max_number)
                {
                    i3++;
                }
                while (numbers[i5] * 5 <= max_number)
                {
                    i5++;
                }
            }
            return *numbers.rbegin();
        }
    }
};

发表于 更新于

输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。

1
struct::bool operator()(const string a, const string b) const
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    struct {
        bool operator()(const string a, const string b) const
        {   
            return a + b < b + a;
        }   
    } compare;
    string PrintMinNumber(vector<int> numbers) {
        vector<string> strings;
        ostringstream oss;
        for (const int number: numbers)
        {
            strings.push_back(to_string(number));
        }
        sort(strings.begin(), strings.end(), compare);
        for (const string number: strings)
        {
            oss << number;
        }
        return oss.str();
    }
};

发表于 更新于

求出任意非负整数区间中1出现的次数（从1 到 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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
public:
    int power(const int base, const int n)
    {
        int number = 1;
        for (int i = 0; i < n; i++)
        {
            number *= base;
        }
        return number;
    }
    int NumberOf1Between1AndN_Solution(int n)
    {
        if (n <= 0)
        {
            return 0;
        }
        else if (n <= 9)
        {
            return 1;
        }
        else if (n <= 10)
        {
            return 2;
        }
        else
        {
            const string text = to_string(n);
            int base_part = power(10, text.length() - 1);
            int base_part_counter = (text.length() - 1) * power(10, text.length() - 2); // count to e.g 999
            if (text[0] == '1')
            {
                const int left_part = n - base_part; // e.g. 234 for 1234
                return base_part_counter + 1 + left_part + NumberOf1Between1AndN_Solution(left_part);
            }
            else
            {
                const int left_digit = text[0] - '0';
                return base_part_counter * left_digit + base_part + NumberOf1Between1AndN_Solution(n - left_digit * base_part);
            }
        }
    }
};

发表于 更新于

计算连续子向量的最大和,向量中包含负数。例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是1)

连续累加，小于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
class Solution {
public:
    int FindGreatestSumOfSubArray(vector<int> array) {
        int sum = 0;
        int max_sum = INT_MIN;
        for (const int number : array)
        {
            if (sum < 0)
            {
                sum = 0;
            }
            sum += number;
            if (sum > max_sum)
            {
                max_sum = sum;
            }
        }
        if (max_sum == INT_MAX)
        {
            max_sum = 0;
        }
        return max_sum;
    }
};

发表于 更新于

输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。

partition、堆、红黑树

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
class Solution {
public:
    void swap(vector<int> &input, const int a, const int b)
    {
        int temp = input[a];
        input[a] = input[b];
        input[b] = temp;
    }
    int partition(vector<int> &input, const int start, const int end)
    {
        if (input.size() == 0)
        {
            return 0;
        }
        else
        {
            const int mid_value = input[0];
            int left = start;
            int right = end;
            while (left < right)
            {
                while (input[right] >= mid_value && left < right)
                {
                    right--;
                }
                swap(input, right, left);
                while (input[left] <= mid_value && left < right)
                {
                    left++;
                }
                swap(input, right, left);
            }
            return left;
        }
    }
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        if (k == 0 || k > input.size())
        {
            return vector<int>();
        }
        else
        {
            int current_k = -1;
            while (current_k != k)
            {
                if (current_k < k)
                {
                    current_k = partition(input, current_k + 1, input.size() - 1);
                }
                else
                {
                    current_k = partition(input, 0, current_k - 1);
                }
            }
            return vector<int>(input.begin(), input.begin() + current_k);
        }
    }
};

发表于 更新于

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。

该数存在，等价于，删去该数的个数恰为子数组长度一半的子数组，将其余部分为新数组，则该数在新数组中的个数依然过半，即

freq>12len⇔freq−12subLen>12(len−subLen)freq>\frac{1}{2}len \Leftrightarrow freq - \frac{1}{2} subLen > \frac{1}{2}(len - subLen) 

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
class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        if (numbers.size() == 0)
        {
            return 0;
        }
        else
        {
            int target = numbers[0];
            int counter = 0;
            for (const int number: numbers)
            {
                if (number == target)
                {
                    counter++;
                }
                else
                {
                    counter--;
                    if (counter == -1)
                    {
                        target = number;
                        counter = 1;
                    }
                }
            }
            if (counter > 0)
            {
                int real_counter = 0;
                for (const int number: numbers)
                {
                    if (number == target)
                    {
                        real_counter++;
                    }
                }
                if (real_counter > numbers.size() / 2)
                {
                    return target;
                }
                else
                {
                    return 0;
                }
            }
            else
            {
                return 0;
            }
        }
    }
};

发表于 更新于

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

排列树，依次交换。字符重复则不交换。

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
class Solution {
public:
    string text;
    vector<string> result;
    void swap(const int a, const int b)
    {
        if (a != b)
        {
            const char char_a = text[a];
            text[a] = text[b];
            text[b] = char_a;
        }
    }
    void DoPermutation(const int start)
    {
        if (start == text.length() - 1)
        {
            result.push_back(text);
        }
        else
        {
            for (int i = start; i < text.length(); i++)
            {
                if (i == start || text[i] != text[start])
                {
                    swap(start, i);
                    DoPermutation(start + 1);
                    swap(start, i);
                }
            }
        }
    }
    vector<string> Permutation(string str) {
        text = str;
        DoPermutation(0);
        sort(result.begin(), result.end());
        return result;
    }
};

发表于 更新于

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

左子树即链表的左边，右子树同理。多返回值以避免冗余的迭代。

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
/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution
{
public:
    void DoConvert(TreeNode *root, TreeNode *&head, TreeNode *&tail)
    {
        if (root != nullptr)
        {
            if (root->left)
            {
                DoConvert(root->left, head, root->left);
                root->left->right = root;
            }
            else
            {
                head = root;
            }
            if (root->right)
            {
                DoConvert(root->right, root->right, tail);
                root->right->left = root;
            }
            else
            {
                tail = root;
            }
        }
    }
    TreeNode *Convert(TreeNode *root)
    {
        if (root == nullptr)
        {
            return nullptr;
        }
        else
        {
            TreeNode *head, *tail;
            DoConvert(root, head, tail);
            return head;
        }
    }
};

发表于 更新于

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

先复制不复杂（无支链）的链表，将新节点连接在旧节点后，再复制新节点的支链，最后拆分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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/*
struct RandomListNode {
    int label;
    struct RandomListNode *next, *random;
    RandomListNode(int x) :
            label(x), next(NULL), random(NULL) {
    }
};
*/
class Solution {
public:
    RandomListNode* Clone(RandomListNode* pHead)
    {
        if (pHead == nullptr)
        {
            return pHead;
        }
        else
        {
            RandomListNode* result;
            for (RandomListNode* current = pHead; current != nullptr; current = current->next->next)
            {
                RandomListNode* new_current = new RandomListNode(current->label);
                new_current->next = current->next;
                current->next = new_current;
            }
            result = pHead->next;
            for (RandomListNode* current = pHead; current != nullptr; current = current->next->next)
            {
                if (current->random != nullptr)
                {
                    current->next->random = current->random->next;
                }
            }
            for (RandomListNode* current = pHead; current != nullptr;)
            {
                RandomListNode* new_current = current->next;
                current->next = new_current->next;
                current = current->next;
                if (current != nullptr)
                {
                    new_current->next = current->next;
                }
            }
            return result;
        }
    }
};