寫在前面：
LeetCode每周五道題(初階)系列部落格介紹
ps.我為什麼要每周做五道題，那當然是為了讓這個世界上少一個菜雞。
目标：每周刷五道題
題目範圍：不限
題目構成：4+1(四道簡單題目加一道中等題目)
注：後續的題目數量以及難易程度會慢慢調整
題目大綱
- 兩數之和（leetcode 題号：1，難度：簡單）
- 回文數（leetcode 題号：9，難度：簡單）
- 删除有序數組中的重複項（leetcode 題号：29，難度：簡單）
- 隻出現一次的數字 （leetcode 題号：136， 難度：簡單）
- 重排連結清單 （leetcode 題号：143， 難度：中等）
1.兩數之和 （leetcode 題号：1，難度：簡單）
1.1 題目描述
給定一個整數數組 nums 和一個整數目标值 target，請你在該數組中找出 和為目标值 target 的那 兩個 整數，并傳回它們的數組下标。
你可以假設每種輸入隻會對應一個答案。但是，數組中同一個元素在答案裡不能重複出現。
你可以按任意順序傳回答案。
示例 1：
輸入：nums = [2,7,11,15], target = 9
輸出：[0,1]
解釋：因為 nums[0] + nums[1] == 9 ，傳回 [0, 1] 。
示例 2：
輸入：nums = [3,2,4], target = 6
輸出：[1,2]
示例 3：
輸入：nums = [3,3], target = 6
輸出：[0,1]
1.2 解法：暴力周遊循環
首先在不考慮時間和空間複雜度的情況下，可以直接使用雙循環周遊的方法，從數組的下标0開始，向後周遊，判斷之和等于target時将兩個元素的下标傳回即可。
代碼示例：
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int i = 0;
int len = nums.size();
vector<int> vctResult;
for (i = 0; i < len; i++)//雙層周遊即可，目前元素自身不需要和自己比較
{
int j = 0;
if (i + 1 == len)
{
break;
}
for (j = i + 1; j < len; j++)
{
if ((nums[i] + nums[j]) == target)
{
vctResult.push_back(i);
vctResult.push_back(j);
}
}
}
return vctResult;
}
};
執行結果：
2.回文數（leetcode 題号：9，難度：簡單）
2.1 題目描述
給你一個整數 x ，如果 x 是一個回文整數，傳回 true ；否則，傳回 false 。
回文數是指正序（從左向右）和倒序（從右向左）讀都是一樣的整數。例如，121 是回文，而 123 不是。
示例 1：
輸入：x = 121
輸出：true
示例 2：
輸入：x = -121
輸出：false
解釋：從左向右讀, 為 -121 。 從右向左讀, 為 121- 。是以它不是一個回文數。
示例 3：
輸入：x = 10
輸出：false
解釋：從右向左讀, 為 01 。是以它不是一個回文數。
示例 4：
輸入：x = -101
輸出：false
2.2 解法：先将整數的 [個十百千…位] 上的數字取出來，存入vector中然後進行前後逐個比較即可
代碼示例：
class Solution{
public:
bool isPalindrome(int x) {
vector<int> v;
if (x < 0)//負數直接傳回False
{
return false;
}
if ((x>=0)&&(x<10))//個位數直接傳回true
{
return true;
}
while (x > 0)//取出來每個位置的數字
{
int temp = x % 10;
x /= 10;
v.push_back(temp);
}
int k = 0;
int end = v.size()-1;
for (k = 0; k < v.size()/2; k++)//首尾逐個進行比較
{
if (v[k] != v[end])
{
return false;
}
end--;
}
return true;
}
};
執行結果：
3.删除有序數組中的重複項（leetcode 題号：29，難度：簡單）
3.1 題目描述
給你一個有序數組 nums(升序) ，請你 原地 删除重複出現的元素，使 每個元素 隻出現一次 ，傳回删除後數組的新長度。
題目解析，這裡是傳引用的方式進行傳參，意思是需要在原數組上進行修改，删除多餘的元素，傳回一個數組的長度，leetcode背景會根據你傳的數組的長度對數組進行取元素，例如長度為1，就選取數組中的第一個元素(下标為0),然後用測試用例的結果進行比對，判斷是否通過測試用例。
不要使用額外的數組空間，你必須在 原地 修改輸入數組 并在使用 O(1) 額外空間的條件下完成。
不允許申請新的空間，隻可以在原數組修改
示例 1：
輸入：nums = [1,1,2]
輸出：2, nums = [1,2]
解釋：函數應該傳回新的長度 2 ，并且原數組 nums 的前兩個元素被修改為 1, 2 。不需要考慮數組中超出新長度後面的元素。
示例 2：
輸入：nums = [0,0,1,1,1,2,2,3,3,4]
輸出：5, nums = [0,1,2,3,4]
解釋：函數應該傳回新的長度 5 ， 并且原數組 nums 的前五個元素被修改為 0, 1, 2, 3, 4 。不需要考慮數組中超出新長度後面的元素。
3.2 解法：使用雙下标循環法，将不同的元素依次放在數組的[0,1,2,…]下标處的位置即可。
代碼示例：
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int k = 0;
int temp = k + 1;
int count = 1;
if (nums.size()==1||nums.size()==0)//特殊值處理
{
return nums.size();
}
while (k < nums.size())
{
while (nums[k] == nums[temp])
{
if (temp == nums.size() - 1)//當已經走到最後一個元素直接傳回
{
return count;
}
if (temp + 1 != nums.size())//注意越界
{
temp++;
}
}
if (nums[k] != nums[temp])//找到不重複的元素
{
nums[k + 1] = nums[temp];//指派
count++;//計數
if (temp == nums.size() - 1)
{
return count;
}
else
{
k++;
temp++;//下标繼續向後移動
}
}
}
return count;
}
};
執行結果：
注意的點：
1.首先要注意數組的越界通路問題，因為有兩個數組下标，且兩個下标是互動的進行跳躍的，是以很容易出現越界的情況.
2.還要注意以下邊界值的情況，考慮數組為空的情況，且對一些特殊的數組，例如隻有一個元素的數組直接傳回1即可。
4.隻出現一次的數字 （leetcode 題号：136， 難度：簡單）
4.1 題目描述
給定一個非空整數數組，除了某個元素隻出現一次以外，其餘每個元素均出現兩次。找出那個隻出現了一次的元素。
說明：
你的算法應該具有線性時間複雜度。 你可以不使用額外空間來實作嗎？
示例 1:
輸入: [2,2,1]
輸出: 1
示例 2:
輸入: [4,1,2,1,2]
輸出: 4
4.2 解法：按位異或
因為隻有一個元素是不重複的，其他的元素都是兩個兩個相同的，根據按位異或的知識可以知道，兩個相同的元素按位異或為0，而任何一個數與0異或都是這個數本身。
代碼示例：
class Solution {
public:
int singleNumber(vector<int>& nums) {
int i = 0;
for (i = 1; i < nums.size(); i++)
{
nums[0] ^= nums[i];
}
return nums[0];
}
};
執行結果：
5.重排連結清單 （leetcode 題号：143， 難度：中等）
5.1題目描述
給定一個單連結清單 L 的頭節點 head ，單連結清單 L 表示為：
L0 → L1 → … → Ln-1 → Ln
請将其重新排列後變為：
L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …
不能隻是單純的改變節點内部的值，而是需要實際的進行節點交換。
示例1：
LeetCode每周五道題：1、9、29、136、143。 輸入: head = [1,2,3,4]
輸出: [1,4,2,3]
示例2：
LeetCode每周五道題：1、9、29、136、143。 輸入: head = [1,2,3,4,5]
輸出: [1,5,2,4,3]
5.2 解法：
首先需要明白這個是要進行結點插入，将倒數第一個結點插入到第一個結點之後，将倒數第二個結點插入到第二個結點的後面(更準确的來說是第三個結點的後面，因為前面已經插入了一個結點）
那麼整體的思路就是：
1.依次找到最後一個結點，将這個結點儲存下來，用于後面的插入。
2.将結點在正确的結點後面進行插入
代碼示例：
class Solution {
public:
void reorderList(ListNode* head) {
if(head->next == nullptr||head->next->next==nullptr )//對隻有一個結點或者兩個結點的情況進行處理
{
//不做任何處理
}
else
{
ListNode* curNode = head;//記錄目前節點的位置
while((curNode->next!=nullptr)&&(curNode->next->next)!=nullptr)//插入結點的結束條件并且判空
{
ListNode* pNext = head;
ListNode* pLast = nullptr;
while(pNext->next->next!=nullptr)//找到尾結點的前一個結點
{
pNext = pNext->next;
}
pLast = pNext->next;//最後一個節點
pNext->next = nullptr;//将倒數第二個結點的next置為nullptr
ListNode* tempNode = curNode->next;//儲存插入節點的下一個結點
curNode->next = pLast;//插入并連結前後結點
pLast->next = tempNode;
curNode = tempNode;//設定下一次插入的位置(後插入)
}
}
}
};
執行結果：
注意的點：
1.首先這道題需要理清解題的思路，即插入的結點是什麼，插入的位置是什麼，什麼時候結束插入。
2.注意邊界值的判斷，并且注意尾結點的next的置空，對結點的判空，否則就會出現崩潰，非法通路，導緻不能通過所有的測試用例。
本地測試代碼：
#include<vector>
#include<iostream>
using namespace std;
//1.兩數之和（leetcode 題号：1）
class Solution1 {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int i = 0;
int len = nums.size();
vector<int> vctResult;
for (i = 0; i < len; i++)//暴力雙循環
{
int temp = 0;
int j = 0;
if (i + 1 == len)
{
break;
}
for (j = i + 1; j < len; j++)
{
if ((nums[i] + nums[j]) == target)
{
vctResult.push_back(i);
vctResult.push_back(j);
}
}
}
return vctResult;
}
};
//2.回文數（leetcode 題号：9）
class Solution2 {
public:
bool isPalindrome(int x) {
vector<int> v;
if (x < 0)//負數直接傳回false
{
return false;
}
if ((x >= 0) && (x < 10))//個位數直接傳回true
{
return true;
}
while (x > 0)
{
int temp = x % 10;//先取個位數，再取百位，千位....依次類推
x /= 10;
v.push_back(temp);
}
int k = 0;
int end = v.size()-1;
for (k = 0; k < v.size()/2; k++)//從頭部和尾部依次開始比較
{
if (v[k] != v[end])
{
return false;
}
end--;
}
//int j = 0;
//for (j = 0; j < v.size(); j++)
//{
// cout << v[j] << " " << endl;
//}
return true;
}
};
void PrintResult(vector<int> vct)//列印數組元素函數
{
int j = 0;
for (j = 0; j < vct.size(); j++)
{
cout << vct[j] << " " << endl;
}
}
//3.删除有序數組中的重複項（leetcode 題号：29）
class Solution3 {
public:
int removeDuplicates(vector<int>& nums) {
int k = 0;
int temp = k + 1;//這個變量是一直存在的 而不是每次循環位置被重新改變
int count = 1;
if (nums.size()==1||nums.size()==0)//判斷邊界值或者隻有一個元素的情況
{
return nums.size();
}
while (k < nums.size())
{
while (nums[k] == nums[temp])
{
if (temp == nums.size() - 1)//周遊到了最後一個元素
{
return count;
}
if (temp + 1 != nums.size())
{
temp++;//遇到相同元素位置++
}
}
if (nums[k] != nums[temp])//找到不重複的元素
{
nums[k + 1] = nums[temp];//指派
temp++;
count++;//計數器++
if (temp == nums.size() - 1)
{
return count;
}
else
{
k++;//下一個開始比較的位置
}
}
}
return count;
}
};
//4.隻出現一次的數字 (leetcode 題号 136)
class Solution4 {
public:
int singleNumber(vector<int>& nums) {
int i = 0;
for (i = 1; i < nums.size(); i++)
{
nums[0] ^= nums[i];
}
return nums[0];
}
};
int main()
{
vector<int> v;
v.push_back(1);
v.push_back(1);
//v.push_back(1);
v.push_back(2);
v.push_back(2);
//v.push_back(2);
v.push_back(3);
//Solution1 s;
//s.twoSum(v, 6);
//PrintResult(s.twoSum(v, 6));
//Solution2 s2;
//s2.isPalindrome(121);
//Solution3 s3;
//cout << s3.removeDuplicates(v) << endl;
Solution4 s4;
cout<<s4.singleNumber(v);
return 0;
}