[数据结构与算法]【算法训练营】(day2)

核心考点: 数组使用，简单算法的设计

思路一：排序，出现次数最多的数一定在中间，检测中间出现的数是否符合要求。

class Solution {
public:
	int MoreThanHalfNum_Solution(vector<int> numbers) {
		sort(numbers.begin(), numbers.end());
		int target = numbers.size();
		int count = 0;
		for (int i = 0; i < numbers.size(); i++)
		{
			if (target == numbers[i]){
				count++;
			}
		}
		if (count>numbers.size() / 2){
			return target;
		}
		return 0;
	}
};

思路二：抵消，我们先定义一个数，然后循环比较，当数组中的数与目标数相等时，次数增加，不相同时次数减少，如果减为0，就进行下一个数的比较。

class Solution {
public:
	int MoreThanHalfNum_Solution(vector<int> numbers) {
		int number = numbers[0];
		int times = 1;
		for (int i = 0; i < numbers.size(); i++)
		{
			if (times = 0){
				number = numbers[i];
				times = 1;
			}
			else if (numbers[i] == number)
			{
				times++;
			}
			else{
				times--;
			}
		}
		int count = 0;
		for (int i = 0; i < numbers.size(); i++){
			if (numbers[i] == number)
			{
				count++;
			}
		}
		return count>numbers.size() / 2 ? number : 0;
	}
};

class Solution {
public:
	int MoreThanHalfNum_Solution(vector<int> numbers) {
		sort(numbers.begin(), numbers.end());
		int target = numbers[numbers.size()];
		int count = 0;
		for (int i = 0; i < numbers.size(); i++)
		{
			if (target == numbers[i]){
				count++;
			}
		}
		if (count>numbers.size() / 2){
			return target;
		}
		return 0;
	}
};

核心考点：字符串相关，特性观察，临界条件处理

虽然是替换问题，但是生成的字符串整体变长了.当遇到空格时，扩大长度，最后，定义新老指针，各自指向新老空间的结尾，然后进行old->new的移动。

class Solution {
public:
	void replaceSpace(char *str, int length) {
		int count = 0;
		const char *start = str;
		for (int i = 0; i < length; i++)
		{
			if (str[i]==" ")
			count++;
			start++;
		}
		
		int new_length = length + 2 * count;
		int old_index = length - 1;
		int new_index = new_length - 1;
		while (old_index >= 0 && new_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--;
			}
		}
	}
};

核心考点：链表相关，多结构混合使用，递归

class Solution {
public:
	vector<int> printListFromTailToHead(ListNode* head) {
		vector<int> v;
		while (head)
		{
			v.push_back(head->val);
			head = head->next;
		}
		reverse(v.begin(), v.end());
		return v;
	}
};