刷题10_30

1.数组中出现次数超过一半的数字

https://www.nowcoder.com/practice/e8a1b01a2df14cb2b228b30ee6a92163

解法1：使用unordered_map对每个数据的个数进行统计，在遍历map，找到出现次数大于一半的元素

代码实现：

#include 
class Solution {
  public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        unordered_map<int, int> map;
        int half = numbers.size() / 2;
        for(auto e : numbers)
        {
            map[e]++;
            //边插入边判断
            // if(map[e] > half)
            // {
            //     return e;
            // }
        }
        auto it = map.begin();
        while(it != map.end())
        {
            if(it->second > half)
            {
                return it->first;
            }
            it++;
        }
        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

思路2：先把整个数组排序，出现次数大于一半的元素一定是中间那个

#include 
class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        int half = numbers.size() / 2;
        sort(numbers.begin(), numbers.end());
        return numbers[half];
    }
};
1
2
3
4
5
6
7
8
9

思路三：不同的两个元素互相抵消，剩下的元素一定是超过一半的。

public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        int val = numbers[0];//先把val设定为数组第一个数
        int times = 1;//记录val可以抵消元素的个数
        for(int i = 1; i < numbers.size(); i++) 
        {
            if(times == 0)
            {
                val = numbers[i];//前面的元素已经抵消完了，重置val为当前元素，重置times为1.
                times = 1;
            }
            else if(numbers[i] == val)
            {
                times++;//遇到和自己相同的元素，可抵消不同元素的次数加一
            }
            else
            {
                times--;//遇到不同元素，抵消，times--；
            }
        }
        return val;  
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

2.替换空格

https://www.nowcoder.com/practice/4060ac7e3e404ad1a894ef3e17650423

解题思路：先统计空格的字数，则新字符串的长度len2=原字符串长度len1+2*空格数。然后定义old_index= len1 -1,new_index = len2 -1;如果old_index对应普通字符，则挪到new_index,若是空格，则在new_inde插入0,2，%；

代码实现：

class Solution {
public:
	void replaceSpace(char *str,int length) {
		int blank = 0;
		for(int i = 0; i < length; i++)
		{
			//统计空格个数
			if(str[i] == ' ')
			{
				blank++;
			}
		}
		int new_length = length + 2 * blank;
		int old_index = length-1;
		int new_index = new_length-1;
		while(old_index >= 0)
		{
			if(str[old_index] != ' ')
			{
				str[new_index] = str[old_index];
				old_index--;
				new_index--;
			}
			else
			{
				str[new_index--] = '0';
				str[new_index--] = '2';
				str[new_index--] = '%';
				old_index--;
			}
		}
	}
};
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

3.从尾到头打印链表

https://www.nowcoder.com/practice/d0267f7f55b3412ba93bd35cfa8e8035

解法1：看到这种相反顺序打印出来，我们很容易想到stack，入栈一遍在出栈即可。这种做法比较简单，代码省略

解法2：使用一个vector在逆置一下，也很简单，代码略

解法3：递归。打印任何一个节点之前，都要先打印他后面的所有节点。递归结条件：要打印当前节点为nullptr。

代码实现：

class Solution {
public:
    void _printListFromTailToHead(ListNode* head, vector<int>& ret)
    {
        if(head == nullptr)
        {
            return;
        }
        _printListFromTailToHead(head->next, ret);
        ret.push_back(head->val);
    }
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> ret;
        _printListFromTailToHead(head, ret);
        return ret;
     }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

4.重建二叉树

https://www.nowcoder.com/practice/8a19cbe657394eeaac2f6ea9b0f6fcf6

解题思路;

代码实现：

class Solution {
public:
    TreeNode* _reConstructBinaryTree(vector<int> pre, int pre_start, int pre_end,vector<int> vin, int vin_start, int vin_end)
    {
        if(pre_start > pre_end || vin_start > vin_end)
        {
            return nullptr;
        }
        int val = pre[pre_start];
        TreeNode* root = new TreeNode(val);
        int i = 0;
        for(i = vin_start; i <= vin_end; i++)
        {
            if(vin[i] == val)
            {
                root->left = _reConstructBinaryTree(pre, pre_start+1, pre_start+i-vin_start, vin, vin_start, i-1);
                root->right = _reConstructBinaryTree(pre, pre_start+1+i-vin_start, pre_end,vin, i+1, vin_end);
                break;
            }
        }
        
        return root;

    }
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        if(pre.size() == 0 || vin.size() == 0)
        {
            return nullptr;
        }
        return _reConstructBinaryTree(pre, 0, pre.size()-1, vin, 0, vin.size()-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

5.斐波那契数列

https://www.nowcoder.com/practice/c6c7742f5ba7442aada113136ddea0c3

解法1：递归方法，直接看代码

递归意味着多次的函数调用，n的值越大，递归的深度就越深，函数调用次数就越多，每一次函数调用都会建立栈帧，有可能出现栈溢出，这种方式效率低，不推荐

思路二：迭代。创建三个变量，分别用来保存第n个数，第n-1个数，第n-2个数。当n大于2，开始循环更新这个三个变量的值

class Solution {
public:
    int Fibonacci(int n) {
        if(n <= 2)
        {
            return 1;
        }
        int first = 1;
        int second = 1;
        int ret;
        while(n > 2)
        {
            ret = first + second;
            first = second;
            second = ret;
            n--;
        }
        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

通过对比我们可以发现，比递归方式快的多。

解法3：除了以上两种方法，我们还可以采用map进行剪枝。

代码实现：

#include 
class Solution {
public:
    unordered_map<int, int> filter;//first用来保存是第几个斐波那契数，second用来保存第几个斐波那契数的值
    int Fibonacci(int n) {
        if(n <= 2)
        {
            return 1;
        }
        int ppre = 0;//用来保存第n-2个斐波那契数
        if(filter.find(n-2) == filter.end())
        {
            //说明filter中找不到第n-2个斐波那契数，我们先把fib(n-2)计算出来，并将其插入到filter便于后序使用
            ppre = Fibonacci(n-2);
            filter.insert(make_pair(n-2, ppre));
        }
        else
        {
            ppre = filter[n-2];
        }

        int pre = 0;//用来保存第n-1个斐波那契数
        if(filter.find(n-1) == filter.end())
        {
            //说明filter中找不到第n-1个斐波那契数，我们先把fib(n-1)计算出来，并将其插入到filter便于后序使用
            pre = Fibonacci(n-1);
            filter.insert(make_pair(n-1, pre));
        }
        else
        {
            pre = filter[n-1];
        }
        //这里说一下为什么先求ppre，再求pre。
        //因为比如说我们求fib(10), 我们需要求fib(9)和fib(8),如果我们先把fib(8)求出来，我们再求fib(9)得时候就相对简单了，因为求fib(9)得时候需要用的fib(8),减少了计算量
        return pre + ppre;
    }
};
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