算法題復習(快排、鏈表、二分、哈希、雙指針)

目錄

    • 1、快速排序復習
    • 2、鏈表部分復習
      • 203. 移除鏈表元素
      • 707. 設計鏈表
      • 206. 反轉鏈表
      • 142.環形鏈表 II
    • 3、二分法復習
    • 4、哈希法復習
    • 5、雙指針復習
      • **15. 三數之和**
      • **18. 四數之和**
      • **27. 移除元素**
      • **344. 反轉字符串**,簡單，雙指針從兩側往中間靠攏，并隨時swap
      • **劍指 Offer 05. 替換空格**
      • **151. 翻轉字符串里的單詞**

1、快速排序復習

基本思想：
1、在當前的排序序列中任意選取一個元素，把該元素稱為基準元素或支點，把下雨等于基準元素的所有元素都移動到基準元素的前面，把大于基準元素的所有元素都移到基準元素的后面，這樣使得基準元素所處的位置 恰好就是排序的最終位置，并且把當前參加排序的序列分為前后兩個序列。
2、上述的過程稱為一趟快速排序，即快速排序的一次劃分
3、接下來分別對這兩個子序列重復上述的排序操作（如果子序列長度大于1的話），直到所有元素都被移動到排序后他們應處的最終位置上。
效率之所以高：每一次元素的移動都是跳躍的，不會像冒泡排序只能在相鄰元素之間進行，元素移動的間隔較大，因此總的比較和移動次數減少

具體步驟：

1、假設序列a，設置兩個變量i、j.分別指向首元素和尾元素，設定i指向的首元素為基準元素

2、反復執行i++，直到i指向的元素>=基準元素，或者i指向尾部

3、反復執行j–，直到指向的元素<基準元素，或者j指向頭部

4、若此時i<j，將i和j指向的元素進行交換。（大的元素在后面）

5、完成第一次交換后，重復執行步驟1、2，直到i>=j位置

6、此時i>=j，然后將基準元素與j指向的元素交換位置，至此完成了原序列的第一次劃分

7、接下來分別對基準元素前后的子序列中長度大于1的子序列重復執行上述操作。

步驟分析：

對于每個子序列的操作又是一次劃分，因此這個算法具有遞歸性質。

每次劃分過程的基準元素仍可設定為子序列的第一個元素

#include<iostream>
#include <vector>
using namespace std;
//快速排序
void Quicksort(vector<int>& a, int s, int t)
{int i, j;if (s < t){//【1】設置兩個變量i、j.分別指向首元素和尾元素，設定i指向的首元素為基準元素i = s;j = t + 1;while (1){do i++;while (!(a[s] <= a[i] || i == t));               //【2】重復i++操作，直到i指向的元素>=基準元素，或者i指向尾部do j--;while (!(a[s] >= a[j] || j == s));              //【3】反復執行j--，直到指向的元素<基準元素，或者j指向頭部if (i < j)                                  //【5】若此時i<j，將i和j指向的元素進行交換。（大的元素在后面）{swap(a[j], a[i]);}else break;                                  //【5】完成第一次交換后，重復執行步驟1、2，直到i>=j位置}//【6】此時i>=j，然后將基準元素與j指向的元素交換位置，至此完成了原序列的第一次劃分swap(a[s], a[j]);//【7】接下來分別對基準元素前后的子序列中長度大于1的子序列重復執行上述操作。Quicksort(a, s, j - 1);                             //前半序列Quicksort(a, j + 1, t);                             //后半序列}
}
void show_sort_result(vector<int> a, int k)
{for (int f = 0;f < k;f++){cout << a[f] << "  ";}printf("\n");
}
int main()
{vector<int> a = { 98,76,109,34,67,190,80,12,14,89,1 };printf("快速排序\n");Quicksort(a,0,a.size() - 1);show_sort_result(a, a.size() - 1);return 0;
}

2、鏈表部分復習

鏈表定義

struct ListNode {int val;ListNode *next;ListNode() : val(0), next(nullptr) {}ListNode(int x) : val(x), next(nullptr) {}ListNode(int x, ListNode *next) : val(x), next(next) {}
};

203. 移除鏈表元素

不使用虛擬頭節點

class Solution {public:ListNode* removeElements(ListNode* head, int val) {//刪除頭節點while(head != nullptr && head->val == val){ListNode* temp = head;head = head->next;delete(temp);}//刪除非頭節點ListNode* cur = head;while(cur != nullptr && cur->next != nullptr){if(cur->next->val == val){ListNode* temp = cur->next;cur->next = cur->next->next;delete(temp);}else {cur = cur->next;}}return head;}
};

使用虛擬頭節點：
注意如果使用指針的話，沒有delete dummy會造成內存泄漏。


class Solution {public:ListNode* removeElements(ListNode* head, int val) {ListNode* dummyHead = new ListNode(0);dummyHead->next = head;ListNode* cur = dummyHead;while(cur->next != nullptr){if(cur->next->val == val){ListNode* temp = cur->next;cur->next = cur->next->next;delete temp;}else {cur = cur->next;}}ListNode* ret = dummyHead->next;delete dummyHead;return ret;}
};

707. 設計鏈表

注意虛擬頭節點的使用。

class MyLinkedList {
public://定義鏈表的結構體struct ListNode {int val;ListNode* next;ListNode(int val) : val(val) , next(nullptr) {}};
private://定義鏈表的虛擬頭節點ListNode* _dummyHead;int _size;
public:/** Initialize your data structure here. */MyLinkedList() {_dummyHead = new ListNode(0);_size = 0;  //記錄鏈表中已經存在的元素個數}/** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */int get(int index) {if(index < 0 || index > _size -1)return -1;ListNode* cur = _dummyHead->next;while(index--){cur = cur->next;}return (cur->val);}/** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */void addAtHead(int val) {ListNode* newNode = new ListNode(val);newNode->next = _dummyHead->next;_dummyHead->next = newNode;_size++;}/** Append a node of value val to the last element of the linked list. */void addAtTail(int val) {ListNode* newNode = new ListNode(val);ListNode* cur = _dummyHead; //注意cur從_dummy開始，防止鏈表一開始為空while(cur->next != nullptr){cur = cur->next;}//此時cur->next為空cur->next = newNode;_size++;}/** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */void addAtIndex(int index, int val) {if(index > _size) return ;if(index < 0){addAtHead(val);return ;} ListNode* newNode = new ListNode(val);ListNode* cur = _dummyHead;while(index--){cur = cur->next;}newNode->next = cur->next;cur->next = newNode;_size++;}/** Delete the index-th node in the linked list, if the index is valid. */void deleteAtIndex(int index) {if(index >= _size || index < 0){return ;}ListNode* cur = _dummyHead;while(index--)cur = cur->next;ListNode* temp = cur->next;cur->next = cur->next->next;delete temp;_size--;}
};/*** Your MyLinkedList object will be instantiated and called as such:* MyLinkedList* obj = new MyLinkedList();* int param_1 = obj->get(index);* obj->addAtHead(val);* obj->addAtTail(val);* obj->addAtIndex(index,val);* obj->deleteAtIndex(index);*/

206. 反轉鏈表

注意while循環的條件以及最后返回的是pre。

class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode* cur = head;ListNode* pre = nullptr;while(cur != nullptr){ListNode* temp = cur->next;cur->next = pre;pre = cur;cur = temp;}return pre;}
};

142.環形鏈表 II

在這里插入圖片描述

數學推導：
相遇時:
slow走過節點數：x+y
fast走過節點數：x+y+n(y+z)
并且有：
(x+y)*2 = x+y+n(y+z)
當n= 1時，x = z:
即：
從頭節點出發一個指針，從相遇節點也出發一個指針，這兩個指針每次只走一個節點，那么當這兩個指針相遇的時候就是環形入口的節點了。

class Solution {
public:ListNode *detectCycle(ListNode *head) {ListNode* fast = head;ListNode* slow = head;while(fast != nullptr && fast->next != nullptr) {slow = slow->next;fast = fast->next->next;//快慢指針相遇if(fast == slow){ListNode* index1 = fast;ListNode* index2 = head;while(index1 != index2){index1 = index1->next;index2 = index2->next;}return index2;}}return nullptr;}
};

3、二分法復習

二分法變種對于不完全有序的還需要再刷刷
在這里插入圖片描述

4、哈希法復習

242. 有效的字母異位詞
https://leetcode-cn.com/problems/valid-anagram/
349. 兩個數組的交集,注意set的使用，還是不太熟悉
https://leetcode-cn.com/problems/intersection-of-two-arrays/
202. 快樂數
https://leetcode-cn.com/problems/happy-number/
1. 兩數之和,注意map的使用，不是很熟悉，要熟悉map的insert操作
https://leetcode-cn.com/problems/two-sum/submissions/
454. 四數相加 II ，注意count加上的是該值上所有的頻次。
https://leetcode-cn.com/problems/4sum-ii/submissions/
383. 贖金信,注意在map中加哪個減哪個。如果ransomNote中出現了magazine不存在的字母，則失敗。
https://leetcode-cn.com/problems/ransom-note/

5、雙指針復習

15. 三數之和

https://leetcode-cn.com/problems/3sum/
需要注意三個地方：
1、第一次去重，在外層for循環中，如果遇到相同的相鄰元素continue
2、第二次去重,每一次找到一次三元組后也要進行一次去重，直到不再符合left < right
3、找到一個答案后，雙指針同時收縮

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {sort(nums.begin(),nums.end());vector<vector<int>> result;for(int i = 0; i < nums.size(); i++){if(nums[i] > 0) break;//第一次去重，在外層for循環中，如果遇到相同的相鄰元素continueif(i > 0 && nums[i] == nums[i-1]) continue;int left = i + 1;int right = nums.size() - 1;while(left < right) //不能取={int tmp_sum = nums[i] + nums[left] + nums[right];if(tmp_sum > 0) right--;else if(tmp_sum < 0) left++;else {result.emplace_back(vector<int>{nums[i],nums[left],nums[right]});//第二次去重,每一次找到一次三元組后也要進行一次去重，直到不再符合left < rightwhile(left < right && nums[right - 1] == nums[right]) right--;while(left < right && nums[left] == nums[left + 1]) left++;//找到一個答案后，雙指針同時收縮left++;right--;}}}return result;}
};

18. 四數之和

https://leetcode-cn.com/problems/4sum/
需要注意地方：
分為3重嵌套，比上一題多了一層循環。所以在最外層也多一個去重。
剪枝操作時錯誤的，不可以剪枝。
三數之和：

for{
剪枝；
去重；
while(再去重)；
}

四數之和：

for
{
去重；
for{去重；while(再去重)；
}
}

27. 移除元素

https://leetcode-cn.com/problems/remove-element/
重點在于fast每時每刻都在往后走(無論該元素是否==val),如果不等于的話slow也需要走。nums【fast】=val的時候slow不走，fast走。
接著到下一個 nums【fast】！=val時，將指向的元素向前移動。

class Solution {
public:int removeElement(vector<int>& nums, int val) {int slow = 0;for(int fast = 0; fast < nums.size(); fast++){if(nums[fast] != val){nums[slow] = nums[fast];slow++;}}return slow;}
};

344. 反轉字符串,簡單，雙指針從兩側往中間靠攏，并隨時swap

https://leetcode-cn.com/problems/reverse-string/

劍指 Offer 05. 替換空格

先計算擴充后大小，然后從后向前替換空格。數組填充類題均是這樣做。
https://leetcode-cn.com/problems/ti-huan-kong-ge-lcof/

class Solution {
public:string replaceSpace(string s) {int count = 0;  //記錄空格數int old_size = s.size();for(int i = 0; i < old_size; i++){if(s[i] == ' ') count++;}//擴充ss.resize(old_size + count * 2);int new_size = s.size();//定義兩個指針，指向兩個位置int new_index = new_size - 1;int old_index = old_size - 1;while(old_index < new_index) {if(s[old_index] != ' '){s[new_index] = s[old_index];} else{s[new_index] = '0';new_index--;s[new_index] = '2';new_index--;s[new_index] = '%';}new_index--;old_index--;}return s;}
};

151. 翻轉字符串里的單詞

,這一題還得多做幾遍。。
https://leetcode-cn.com/problems/reverse-words-in-a-string/
這一題對空格的處理操作更加繁瑣一點;
思路：
1、移除多余空格
2、將整個字符串反轉
3、將每個單詞反轉
如：
“the sky is blue” => “the sky is blue” => “eulb si yks eht” => “blue is sky the”
1、去除多余空格，使用雙指針

void removeExtraSpaces(string& s){//定義快慢指針int slow = 0;int fast = 0;//去除字符串前面的空格while(s.size() > 0 && fast < s.size() && s[fast] == ' ') fast++;//去除字符串中間的榮譽空格while(fast < s.size()){if(fast > 1 && s[fast] == ' ' && s[fast - 1] == ' ') {fast++;continue;}else{s[slow] = s[fast];slow++;fast++;}}//去除字符串末尾的空格,并重新設置字符串大小if(slow > 1 && s[slow - 1] == ' '){s.resize(slow - 1);}else{s.resize(slow);}}

2、反轉字符串，使用雙指針

    void reverse(string& s,int left,int right) {while(left <= right){swap(s[left],s[right]);left++;right--;}}

3、將字符串中的每個單詞反轉

string reverseWords(string s) {removeExtraSpaces(s);reverse(s,0,s.size() - 1);int fast = 0; int slow = 0;while(fast < s.size()){//如果遍歷到字符串中間一個單詞結束if(s[fast] == ' '){reverse(s,slow,fast - 1);//跳過空格slow = fast + 1;}//如果遍歷到最后一個單詞結束(此時沒有空格)if(fast == s.size() -1){reverse(s,slow,fast);}fast++;}return s;}

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/377329.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/377329.shtml
英文地址，請注明出處：http://en.pswp.cn/news/377329.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

Cassandra1.2文檔學習（7）—— 規劃集群部署

Cassandra1.2文檔學習（7）—— 規劃集群部署

數據參考&#xff1a;http://www.datastax.com/documentation/cassandra/1.2/webhelp/index.html#cassandra/architecture/architecturePlanningAbout_c.html 當規劃一個Cassandra集群部署時&#xff0c;關于你初始存儲的數據的數據量你應當有一個好的想法&#xff0c;并且對于…
閱讀更多...
虛擬機設置NAT

虛擬機設置NAT

需要開啟虛擬機網絡相關服務&#xff0c; 安裝虛擬網卡&#xff0c; 還有必須安裝 VMware ToolsVMware虛擬機下實現NAT方式上網1. 把你的虛擬網卡VMnet8設置為自動獲得IP、自動獲得DNS服務器&#xff0c;啟用。2. 把你虛擬機中操作系統的“本地連接”也設置為自動獲得IP、自動獲…
閱讀更多...
窗體震動 C# （不使用Timer控件，控制窗體震動）

窗體震動 C# （不使用Timer控件，控制窗體震動）

private static Point plocation new Point(); public static void StartVibration(Form form)//Form 傳入需要振動的窗體 { plocation form.Location; for (int i 1; i < 41; i)//41&#xff0c;可以理解為震動的時間。…
閱讀更多...
算法題復習（棧與隊列、二叉樹）

算法題復習（棧與隊列、二叉樹）

目錄棧與隊列棧用于匹配的問題隊列用于堆二叉樹系列深度遍歷&#xff0c;遞歸與迭代層序遍歷二叉樹屬性二叉樹修改與構造二叉搜索樹公共祖先二叉搜索樹的修改與構造棧與隊列 棧用于匹配的問題 20. 有效的括號 https://leetcode-cn.com/problems/valid-parentheses/ 不匹配的三…
閱讀更多...
bpsk_BPSK的完整形式是什么？

bpsk_BPSK的完整形式是什么？

bpskBPSK&#xff1a;二進制相移鍵控 (BPSK: Binary Phase Shift Keying) BPSK is an abbreviation of "Binary Phase Shift Keying". BPSK是“二進制相移鍵控”的縮寫 。 BPSK is also occasionally called phase reversal keying (PRK), or 2PSK, which is the el…
閱讀更多...
win7 下安裝oracle 10g

win7 下安裝oracle 10g

oracle 10g 在win7下安裝&#xff0c;提示程序異常終止&#xff0c;發生未知錯誤 在網上搜結果&#xff1a; 修改Oracle 10G\database\stage\prereq\db\refhost.xml 在 </SYSTEM> <CERTIFIED_SYSTEMS>后面添加 <!--Microsoft Windows 7--> <OPERAT…
閱讀更多...
poj 1703 Find them, Catch them

poj 1703 Find them, Catch them

題目鏈接&#xff1a;http://poj.org/problem?id1703 題目大意&#xff1a;警察抓獲N個罪犯&#xff0c;這些罪犯只可能屬于兩個團伙中的一個&#xff0c;現在給出M個條件&#xff08;D a b表示a和b不在同一團伙&#xff09;&#xff0c;對于每一個詢問(A a b)確定a&#xff0…
閱讀更多...
雙向a*搜索算法_雙向搜索算法

雙向a*搜索算法_雙向搜索算法

雙向a*搜索算法什么是雙音搜索&#xff1f; (What is bitonic search?) Searching a bitonic array is known as bitonic search. An array is said to be bitonic if it has an increasing sequence of integers followed immediately by a decreasing sequence of integers.…
閱讀更多...
關于LRU緩存簡單記錄以及代碼補全。

關于LRU緩存簡單記錄以及代碼補全。

目錄大概思路時間空間復雜度分析指針操作具體細節代碼雙向鏈表設計私有成員變量設計:構造函數和析構函數設計&#xff1a;get與put具體設計雙向指針的具體細節添加到頭節點函數刪除尾節點函數刪除節點函數刪除節點函數感想今天面試考到LRU&#xff0c;太緊張了&#xff0c;完全…
閱讀更多...
碼農干貨系列【4】--圖像識別之矩形區域搜索

碼農干貨系列【4】--圖像識別之矩形區域搜索

簡介 定位某個圖片的矩形區域是非常有用的&#xff0c;這個可以通過手動的選擇某個區域來實現定位&#xff0c;圖片相關的軟件都提供了這個功能&#xff1b;也可以像本篇一個通過程序來實現智能定位。前者會有誤差&#xff0c;效率低下&#xff1b;后者選區精度高&#xff0c;效…
閱讀更多...
算法題復習（回溯）

算法題復習（回溯）

目錄base code棋盤問題51. N 皇后37. 解數獨組合問題77. 組合未剪枝優化剪枝優化216. 組合總和 III未剪枝優化剪枝優化17. 電話號碼的字母組合39. 組合總和未剪枝優化剪枝優化40. 組合總和 II,挺重要的&#xff0c;涉及到去重了切割問題131. 分割回文串子集問題78. 子集90. 子集…
閱讀更多...
pfa是什么意思_PFA的完整形式是什么？

pfa是什么意思_PFA的完整形式是什么？

pfa是什么意思PFA&#xff1a;預測性故障分析 (PFA: Predictive Failure Analysis) PFA is an abbreviation of Predictive Failure Analysis. It is a technique of a mechanism of the computer that is used to predict impending failures of software or hardware compone…
閱讀更多...
SqlServer視圖（view）

SqlServer視圖（view）

--上節回顧--1.什么是事務--2.事務的特征--原子性、一致性、隔離性、持久性--3.與事務相關的t-sql命令--開啟事務&#xff1a;begin transaction--提交事務&#xff1a;commit transaction--回滾事務&#xff1a;rollback transaction ----------------視圖-------------------…
閱讀更多...
Android中的廣播Broadcast詳解

Android中的廣播Broadcast詳解

今天來看一下Android中的廣播機制&#xff0c;我們知道廣播Broadcast是Android中的四大組件之一&#xff0c;可見他的重要性了&#xff0c;當然它的用途也很大的&#xff0c;比如一些系統的廣播&#xff1a;電量低、開機、鎖屏等一些操作都會發送一個廣播&#xff0c;具體的And…
閱讀更多...
sql check約束_在SQL中使用CHECK約束

sql check約束_在SQL中使用CHECK約束

sql check約束Basically, CHECK constraint is used to LIMIT in columns for the range of values. We can use this constraint for single or multiple columns. 基本上&#xff0c; CHECK約束用于限制值范圍內的列 。 我們可以將此約束用于單列或多列。 In single column,…
閱讀更多...
.NET線程池

.NET線程池

摘要 深度探索 Microsoft .NET提供的線程池&#xff0c; 揭示什么情況下你需要用線程池以及 .NET框架下的線程池是如何實現的&#xff0c;并告訴你如何去使用線程池。 內容 介紹 .NET中的線程池 線程池中執行的函數 使用定時器 同步對象的執行 異步I/O操作 監視線程池 死鎖 有關…
閱讀更多...
折線分割平面

折線分割平面

Input輸入數據的第一行是一個整數C,表示測試實例的個數&#xff0c;然后是C 行數據&#xff0c;每行包含一個整數n(0<n<10000),表示折線的數量。Output對于每個測試實例&#xff0c;請輸出平面的最大分割數&#xff0c;每個實例的輸出占一行。Sample Input2 1 2Sample Ou…
閱讀更多...
《c++特性》

《c++特性》

目錄多態構造函數和析構函數存在多態嗎&#xff1f;虛函數表虛析構函數純虛函數和抽象類運行時多態和編譯時多態的區別繼承設計實例指針對象和普通對象的區別正確初始化派生類方式繼承和賦值的兼容規則protected 和 private 繼承基類與派生類的指針強制轉換如何用C實現C的三大特…
閱讀更多...
Scala中的while循環

Scala中的while循環

在Scala中的while循環 (while loop in Scala) while loop in Scala is used to run a block of code multiple numbers of time. The number of executions is defined by an entry condition. If this condition is TRUE the code will run otherwise it will not run. Scala中…
閱讀更多...
Linux操作系統啟動過程

Linux操作系統啟動過程

在做開發的過程中&#xff0c;突然發現&#xff0c;要對系統做一些有意義的改變&#xff0c;必須要對操作系統的啟動過程有一定的了解&#xff0c;不然就是修改你都不知道從哪里下手啊&#xff0c;然后就是找來資料看&#xff0c;去網上看別人的博客&#xff0c;有了前一周一些…
閱讀更多...
最新文章

Copyright @ 2022~2023