算法題常用API

std::accumulate

函數原型：

template< class InputIt, class T >
T accumulate( InputIt first, InputIt last, T init );

一般求和的，代碼如下：

int sum = accumulate(vec.begin() , vec.end() , 0);

詳細用法參考

lower_bound()

int lower_bound(起始地址，結束地址，要查找的數值) 返回的是數值 第一個等于某元素 的位置。

int index = upper_bound(vec.begin(), vec.end(), target) - vec.begin()

功能：函數lower_bound()在first和last中的前閉后開區間進行二分查找，返回大于或等于target的第一個元素位置。如果所有元素都小于target，則返回last的位置，因為是前閉后開因此這個時候的last會越界，要注意。

找不到返回nums.end()

upper_bound()

int upper_bound(起始地址，結束地址，要查找的數值) 返回的是數值 第一個大于某個元素 的位置。

int index = upper_bound(vec.begin(), vec.end(), target) - vec.begin();

功能：函數upper_bound()返回的在前閉后開區間查找的關鍵字的上界，返回大于target的第一個元素位置。注意：返回查找元素的最后一個可安插位置，也就是“元素值>查找值”的第一個元素的位置。同樣，如果target大于數組中全部元素，返回的是last。(注意：數組下標越界)

binary_search()

bool binary_search(起始地址，結束地址，要查找的數值) 返回的是 是否存在 這么一個數，是一個bool值。

功能： 在數組中以二分法檢索的方式查找，若在數組(要求數組元素非遞減)中查找到indx元素則真，若查找不到則返回值為假。

priority_queue

template<class T,class Container = std::vector<T>,class Compare = std::less<typename Container::value_type>
> class priority_queue;

默認container是vector。

默認compare策略是less。因為默認是大頂堆，首先輸出最大元素，所以最開始來的元素最后才輸出。記住大頂堆比較策略是std::less<T>，小頂堆的比較策略是std::greater<T>

atoi

int atoi( const char *str );

將char*的字符串轉化成整數

min和max

包含在c++標準庫中頭文件<algorithm>中

std::min(const T& a, const T& b);
std::max(const T& a, const T& b);
//或者自己寫comp函數
const T& min (const T& a, const T& b, Compare comp);//自定義compare函數如下
static bool compare(const string& s1, const string& s2)
{string ab = s1 + s2;string ba = s2 + s1;return ab < ba; //升序排列。如改為ab > ba, 則為降序排列
}

數據結構

鏈表類型

234. 回文鏈表

**思路：**回文串是對稱的，所以正著讀和倒著讀應該是一樣的，這一特點是解決回文串問題的關鍵。單鏈表無法倒著遍歷，無法使用雙指針技巧。

• 方法一，把鏈表節點放入棧中再拿出和原來的鏈表比較。算法的時間和空間復雜度都是 O(N)

  class Solution {
  public:bool isPalindrome(ListNode* head) {  stack<int> rec;ListNode *temp = head;while(temp){rec.push(temp->val);temp = temp->next;}while(!rec.empty()||head){if(head->val == rec.top()){head = head->next;rec.pop();}else{return false;}  }return true;}
  };
  

• 方法二

  **利用雙指針的快慢指針的思想，找出鏈表的中間節點。**雙指針的條件是while(fast!=null && fast->next!=null)

  然后要分清楚鏈表是雙數還是單數。如果fast==null，表明是偶數鏈表，否則是奇數鏈表

  雙指針找中點+反轉一部分節點

bool isPalindrome(ListNode* head) {  ListNode* slow = head;ListNode* fast = head;while(fast && fast->next){slow = slow->next;fast = fast->next->next;}//fast=nullptr說明是偶數鏈表//fast!=nullptr說明是奇數鏈表ListNode* tail = reverse(slow);ListNode* front = head;while(tail || tail == slow){if(front->val == tail->val){front = front->next;tail = tail->next;}else{return false;}}return true;
}
ListNode* reverse(ListNode* node){if(!node || !node->next){return node;}ListNode* tmp = reverse(node->next);node->next->next = node;node->next = nullptr;return tmp;
}