核心考點: 陣列使用，簡單演算法的設計
思路一：排序，出現次數最多的數一定在中間，檢測中間出現的數是否符合要求，
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;
}
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/297836.html
標籤：其他
上一篇：【演算法】邏輯十分縝密，思路清晰的帶大家一次性學會常見的排序演算法系列。（一）冒泡排序
下一篇：動態記憶體管理（上）