頭條算法題匯總

二叉樹的中序遍歷（Stack類型的寫法）

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        auto cur = root;
        vector<int> res;
        stack<TreeNode*> stk;
        while(cur||!stk.empty()){
            if(cur){
                stk.push(cur);
                cur = cur->left;
            }else{
                cur = stk.top();
                stk.pop();
                res.push_back(cur->val);
                cur = cur->right;
            }
        }
        return res;
    }
};

原題鏈接 https://leetcode.com/problems/binary-tree-inorder-traversal/

這里概括了所有的解法 https://leetcode.com/problems/binary-tree-postorder-traversal/discuss/45551/Preorder-Inorder-and-Postorder-Iteratively-Summarization

一個無序數(shù)組求第K大數(shù)

class Solution_1 {
  public:
    int partion(vector<int> &nums, int left, int right) {
        int pivot = nums[right], i = left;
        while (left < right) {
            if (nums[left] < pivot) {
                swap(nums[left], nums[i]);
                i++;
            }
            left++;
        }
        swap(nums[i], nums[right]);
        return i;
    }
    int partion2(vector<int> &nums, int left, int right) {//第二種partion的寫法
        int i = left, j = right + 1;
        int pivot = nums[left];
        while (i < j) {
            while (i < right && nums[++i] < pivot);
            while (j > left && nums[--j] > pivot);
            if (i >= j) {
                break;
            }
            swap(nums[i], nums[j]);
        }
        swap(nums[left], nums[j]);
        return j;
    }
    int findKthLargest(vector<int> &nums, int k) {
        int m = nums.size();
        k = m - k;
        return helper(nums, 0, m - 1, k);
    }
    int helper(vector<int> &nums, int left, int right, int k) {
        int pos = partion(nums, left, right);
        if (pos == k) {
            return nums[pos];
        }
        if (pos < k) {
            return helper(nums, pos + 1, right, k);
        }
        return helper(nums, left, pos - 1, k);
    }
};

原題鏈接： https://leetcode.com/problems/kth-largest-element-in-an-array

插入排序鏈表

// 鏈表排序 leetcode147
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
  public:
    ListNode *insertionSortList(ListNode *head) {
        ListNode result(0);
        ListNode *cur = head, *pre = &result;
        while (cur) {
            ListNode *temp = cur->next;
            pre = &result;
            ListNode *inp = pre->next;
            while (inp && inp->val < cur->val) {
                inp = inp->next;
                pre = pre->next;
            }
            cur->next = inp;
            pre->next = cur;
            cur = temp;
        }
        return result.next;
    }
};

歸并排序鏈表

// lc148 鏈表排序
class Solution_0 {
  public:
    ListNode *sortList(ListNode *head) {
        if (head == NULL || head->next == NULL) {
            return head;
        }
        ListNode *walker = head, *runner = head->next;
        while (runner && runner->next) {
            walker = walker->next;
            runner = runner->next->next;
        }
        ListNode *head_2 = sortList(walker->next);
        walker->next = NULL;
        ListNode *head_1 = sortList(head);
        return mergerList(head_1, head_2);
    }
    ListNode *mergerList(ListNode *head_1, ListNode *head_2) {
        if (head_1 == NULL) {
            return head_2;
        }
        if (head_2 == NULL) {
            return head_1;
        }
        if (head_1->val < head_2->val) {
            head_1->next = mergerList(head_1->next, head_2);
            return head_1;
        } else {
            head_2->next = mergerList(head_1, head_2->next);
            return head_2;
        }
    }
};

二叉樹轉(zhuǎn)中序鏈表

// 攀诎裕客劍指offer26題
class Solution {
  public:
    TreeNode *Convert(TreeNode *root) {
        if (root == nullptr) {
            return nullptr;
        }
        TreeNode *current = nullptr;
        helper(root, current);
        while (current->left) {
            current = current->left;
        }
        return current;
    }
    void helper(TreeNode *root, TreeNode *&pre) {
        if (root == nullptr) {
            return;
        }
        helper(root->left, pre);
        root->left = pre;
        if (pre) {
            pre->right = root;
        }
        pre = root;
        helper(root->right, pre);
    }
};

無序數(shù)組的中位數(shù)

// https://www.cnblogs.com/shizhh/p/5746151.html
class Solution_1 {
  public:
    double median(vector<int> nums) {
        priority_queue<int> max_heap;
        int m = nums.size();
        int size = m / 2 + 1;
        for (int i = 0; i < size; i++) {
            max_heap.push(nums[i]);
        }
        for (int i = size; i < m; i++) {
            if (max_heap.top() > nums[i]) {
                max_heap.pop();
                max_heap.push(nums[i]);
            }
        }
        double res = 0;
        if (m & 1 == 1) {
            return max_heap.top();
        } else {
            res += max_heap.top();
            max_heap.pop();
            res += max_heap.top();
            return res;
        }
    }
};

// lc 215 類似 不過是找第k大的位數(shù)
class Solution_1 {
  public:
    int partion(vector<int> &nums, int left, int right) {
        int pivot = nums[right], i = left;
        while (left < right) {
            if (nums[left] < pivot) {
                swap(nums[left], nums[i]);
                i++;
            }
            left++;
        }
        swap(nums[i], nums[right]);
        return i;
    }
    int findKthLargest(vector<int> &nums, int k) {
        int m = nums.size();
        k = m - k;
        return helper(nums, 0, m - 1, k);
    }
    int helper(vector<int> &nums, int left, int right, int k) {
        int pos = partion(nums, left, right);
        if (pos == k) {
            return nums[pos];
        }
        if (pos < k) {
            return helper(nums, pos + 1, right, k);
        }
        return helper(nums, left, pos - 1, k);
    }
};

LRU Cache數(shù)據(jù)結(jié)構(gòu)

#include <bits/stdc++.h>
using namespace std;

class LRUCache {
  public:
    LRUCache(int capacity) { this->capacity = capacity; }

    int get(int key) {
        if (dir.count(key)) {
            vistied(key);
            return dir[key]->second;
        }
        return -1;
    }

    void put(int key, int value) {
        if (dir.count(key)) {
            vistied(key);
        } else {
            if (capacity <= dir.size()) {
                dir.erase(cacheList.back().first);
                cacheList.pop_back();
            }
            cacheList.push_front(make_pair(key, value));
            dir[key] = cacheList.begin();
        }
        dir[key]->second = value;
    }
    void vistied(int key) {
        auto p = *dir[key];
        cacheList.erase(dir[key]);
        cacheList.push_front(p);
        dir[key] = cacheList.begin();
    }

  private:
    unordered_map<int, list<pair<int, int>>::iterator> dir;
    list<pair<int, int>> cacheList;
    int capacity;
};

旋轉(zhuǎn)數(shù)組最小值

#include <bits/stdc++.h>
using namespace std;
/**
 * 原題鏈接
 * https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/description/
 */
class Solution {
  public:
    int findMin(vector<int> &rotateArray) {
        int left = 0, right = rotateArray.size() - 1;
        while (left < right) {
            int mid = (left + right) / 2;
            if (rotateArray[mid] < rotateArray[right]) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return rotateArray[left];
    }
};

旋轉(zhuǎn)數(shù)組最小值（有重復的數(shù)）

#include <bits/stdc++.h>
using namespace std;
/**
 * 原題鏈接
 * https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/description/
 */
class Solution {
  public:
    int findMin(vector<int> &nums) {
        int m = nums.size();
        int left = 0, right = m - 1;
        while (left < right) {
            int middle = (left + right) / 2;
            if (nums[middle] < nums[right]) {
                right = middle;
            } else if (nums[middle] > nums[right]) {
                left = middle + 1;
            } else {
                // if里面能找到真正的旋轉(zhuǎn)點旧困，而不是最小值
                if (nums[right - 1] > nums[right]) {
                    left = right;
                    break;
                }
                right--;
            }
        }
        return nums[left];
    }
};

旋轉(zhuǎn)數(shù)組的某個值(無重復值)

#include <bits/stdc++.h>
using namespace std;
/**
 * https://leetcode.com/problems/search-in-rotated-sorted-array/discuss/14425/Concise-O(log-N)-Binary-search-solution
 *
 */
class Solution_2 {
  public:
    int find_min_in_rotateArr(vector<int> &nums) {
        int m = nums.size();
        int left = 0, right = m - 1;
        while (left < right) {
            int mid = (left + right) / 2;
            if (nums[mid] < nums[right]) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
    int search(vector<int> &nums, int target) {
        int m = nums.size();
        int min_index = find_min_in_rotateArr(nums);
        int left = 0, right = m - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            int real_mid = (mid + min_index) % m;
            if (nums[real_mid] == target) {
                return real_mid;
            } else if (nums[real_mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }
};

class Solution_0 {
  public:
    int search(vector<int> &nums, int target) {
        if (nums.empty()) {
            return -1;
        }
        int m = nums.size();
        int left = 0, right = m - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[mid] < nums[right]) {
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            } else {
                if (nums[mid] > target && nums[left] <= target) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
        }
        return -1;
    }
};

旋轉(zhuǎn)數(shù)組的某個值(有重復值)

/**
 * leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/discuss/48808/My-pretty-simple-code-to-solve-it/48840
 */
class Solution {
  public:
    int find_min_in_rotateArr(vector<int> &nums) {
        int m = nums.size();
        int left = 0, right = m - 1;
        while (left < right) {
            int mid = (left + right) / 2;
            if (nums[mid] < nums[right]) {
                right = mid;
            } else if (nums[mid] > nums[right]) {
                left = mid + 1;
            } else {
                // if里面能找到真正的旋轉(zhuǎn)點狱窘，而不是最小值
                if (nums[right - 1] > nums[right]) {
                    left = right;
                    break;
                }
                right--;
            }
        }
        return left;
    }
    bool search(vector<int> &nums, int target) {
        int m = nums.size();
        int min_index = find_min_in_rotateArr(nums);
        int left = 0, right = m - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            int real_mid = (mid + min_index) % m;
            if (nums[real_mid] == target) {
                return true;
            } else if (nums[real_mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return false;
    }
};

// https://leetcode.com/problems/search-in-rotated-sorted-array-ii/
class Solution {
  public:
    bool search(vector<int> &nums, int target) {
        int left = 0, right = nums.size() - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) {
                return true;
            }
            if (nums[left] == nums[mid] && nums[right] == nums[mid]) {
                left++;
                right--;
            } else if (nums[left] <= nums[mid]) {
                if (nums[left] <= target && nums[mid] > target)
                    right = mid - 1;
                else
                    left = mid + 1;
            } else {
                if (nums[right] >= target && nums[mid] < target) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return false;
    }
};

二叉樹右視圖

#include <bits/stdc++.h>
using namespace std;
/**
 * 原題鏈接
 * https://leetcode.com/problems/binary-tree-right-side-view/description/
 */

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
  public:
    vector<int> rightSideView(TreeNode *root) {
        vector<int> res;
        helper(root, 0, res);
        return res;
    }
    void helper(TreeNode *root, int level, vector<int> &res) {
        if (root == NULL)
            return;
        if (res.size() == level)
            res.push_back(root->val);
        helper(root->right, level + 1, res);
        helper(root->left, level + 1, res);
    }
};

數(shù)據(jù)流的中位數(shù)

class MedianFinder {
  public:
    /** initialize your data structure here. */
    MedianFinder() {}

    void addNum(int num) {
        min_heap.push(num);
        max_heap.push(min_heap.top());
        min_heap.pop();
        if (min_heap.size() < max_heap.size()) {
            min_heap.push(max_heap.top());
            max_heap.pop();
        }
    }

    double findMedian() {
        int m = max_heap.size() + min_heap.size();
        if (m & 1 == 1) {
            return min_heap.top();
        }
        return (max_heap.top() + min_heap.top()) / 2.0;
    }

  private:
    priority_queue<int, vector<int>, less<int>> max_heap;
    priority_queue<int, vector<int>, greater<int>> min_heap;
};

合并兩個有序的鏈表

// https://leetcode.com/problems/merge-two-sorted-lists/description/
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(l1==NULL){
            return l2;
        }
        if(l2==NULL){
            return l1;
        }
        ListNode *result;
        if(l1->val<l2->val){ 
            l1->next = mergeTwoLists(l1->next,l2);
            return l1;
        }else{
            l2->next = mergeTwoLists(l1,l2->next);
            return l2;
        }
    }
};

合并K個有序鏈表

#include <bits/stdc++.h>
using namespace std;
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};
/**
 * https://leetcode.com/problems/merge-k-sorted-lists/description/
 */
class Solution {
  public:
    struct compare_listNode {
        bool operator()(const ListNode *p, const ListNode *q) {
            return p->val > q->val;
        }
    };
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        ListNode result(0);
        ListNode *pre = &result;
        priority_queue<ListNode *, vector<ListNode *>, compare_listNode>
            min_heap;
        int m = lists.size();
        for (int i = 0; i < m; i++) {
            if (lists[i]) {
                min_heap.push(lists[i]);
            }
        }
        while (!min_heap.empty()) {
            ListNode *cur = min_heap.top();
            min_heap.pop();
            pre->next = cur;
            if (cur->next) {
                min_heap.push(cur->next);
            }
            pre = pre->next;
        }
        return result.next;
    }
};

Swap Nodes in Pairs

#include <bits/stdc++.h>
using namespace std;

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

/**
 * https://leetcode.com/problems/swap-nodes-in-pairs/description/
 */
class Solution {
  public:
    ListNode *swapPairs(ListNode *head) {
        ListNode **cur = &head, *a, *b;
        while ((a = *cur) && (b = a->next)) {
            a->next = b->next;
            b->next = a;
            cur = &(a->next);
        }
    }
};

class Solution_1 {
  public:
    ListNode *swapPairs(ListNode *head) {
        if (head == NULL || head->next == NULL) {
            return head;
        }
        ListNode *first = head, *second = head->next;
        ListNode *tail = swapPairs(second->next);
        second->next = first;
        first->next = tail;
        return second;
    }
};

入棧和出棧

#include <bits/stdc++.h>
using namespace std;
class Solution {
  public:
    bool IsPopOrder(vector<int> pushV, vector<int> popV) {
        stack<int> stk;
        int j = 0;
        for (int i = 0; i < pushV.size(); i++) {
            stk.push(pushV[i]);
            while (!stk.empty() && stk.top() == popV[j]) {
                stk.pop();
                j++;
            }
        }
        return j == popV.size();
    }
};

兩個有序數(shù)組找中位數(shù)

// lc4
class Solution {
public:
    double findMedianSortedArrays(vector<int> &nums1, vector<int> &nums2) {
        int m = nums1.size(), n = nums2.size();
        int left = (m + n + 1) / 2, right = (m + n + 2) / 2;
        return (find_kth(nums1.begin(), m, nums2.begin(), n, left) +
                find_kth(nums1.begin(), m, nums2.begin(), n, right)) /
               2.0;
    }
    int find_kth(vector<int>::iterator a, int m, vector<int>::iterator b, int n,
                 int k) {
        if(m>n){
            return find_kth(b,n,a,m,k);
        }
        if(m==0){
            return b[k-1];
        }
        if(k==1){
            return min(a[0],b[0]);
        }
        int i = min(m,k/2),j = k - i;
        if(a[i-1]<b[j-1]){
            return find_kth(a+i,m-i,b,j,k-i);
        }else if(a[i-1]>b[j-1]){
            return find_kth(a,i,b+j,n-j,k-j);
        }
        return a[i-1];
    }
};

LRU的設計

class LRUCache {
  public:
    LRUCache(int capacity) { this->capacity = capacity; }

    int get(int key) {
        if(dir.count(key)){
            vistied(key);
            return dir[key]->second;
        }
        return -1;
    }

    void put(int key, int value) {
        if(dir.count(key)){
            vistied(key);
            dir[key]->second = value;
        }else{
            if(cacheList.size()>=capacity){      
                dir.erase(cacheList.back().first);
                cacheList.pop_back();
            }
            cacheList.push_front(make_pair(key,value));
            dir[key] = cacheList.begin();
        }
    }
    void vistied(int key) {
        auto it = *dir[key];
        cacheList.erase(dir[key]);
        cacheList.push_front(it);
        dir[key] = cacheList.begin();
    }

  private:
    unordered_map<int, list<pair<int, int>>::iterator> dir;
    list<pair<int, int>> cacheList;
    int capacity;
};

問答題

n個人編號從1->n, 對應n個座位編號從1->n询筏，問每個人都不做在自己的位置上有多少中可能性狼牺？

參考的帖子

https://leetcode.com/problemset/all/
https://www.nowcoder.com/discuss/101763?type=0&order=0&pos=34&page=1

最后編輯于：2018.10.12 19:46:08

?著作權歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者

人面猴
序言：七十年代末到推，一起剝皮案震驚了整個濱河市底循，隨后出現(xiàn)的幾起案子踱卵，更是在濱河造成了極大的恐慌嘉裤，老刑警劉巖郑临，帶你破解...
沈念sama閱讀 216,470評論 6贊 501
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件，死亡現(xiàn)場離奇詭異屑宠，居然都是意外死亡厢洞，警方通過查閱死者的電腦和手機，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 92,393評論 3贊 392
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進店門典奉，熙熙樓的掌柜王于貴愁眉苦臉地迎上來躺翻，“玉大人，你說我怎么就攤上這事卫玖」悖” “怎么了？”我有些...
開封第一講書人閱讀 162,577評論 0贊 353
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵假瞬，是天一觀的道長陕靠。經(jīng)常有香客問我，道長笨触，這世上最難降的妖魔是什么懦傍？我笑而不...
開封第一講書人閱讀 58,176評論 1贊 292
?港島之戀（遺憾婚禮）
正文為了忘掉前任，我火速辦了婚禮芦劣，結(jié)果婚禮上，老公的妹妹穿的比我還像新娘说榆。我一直安慰自己虚吟，他們只是感情好，可當我...
茶點故事閱讀 67,189評論 6贊 388
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布签财。她就那樣靜靜地躺著串慰，像睡著了一般。火紅的嫁衣襯著肌膚如雪唱蒸。梳的紋絲不亂的頭發(fā)上邦鲫，一...
開封第一講書人閱讀 51,155評論 1贊 299
城市分裂傳說
那天，我揣著相機與錄音神汹，去河邊找鬼庆捺。笑死，一個胖子當著我的面吹牛屁魏，可吹牛的內(nèi)容都是我干的滔以。我是一名探鬼主播，決...
沈念sama閱讀 40,041評論 3贊 418
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼氓拼，長吁一口氣：“原來是場噩夢啊……” “哼你画！你這毒婦竟也來了抵碟？” 一聲冷哼從身側(cè)響起，我...
開封第一講書人閱讀 38,903評論 0贊 274
萬榮殺人案實錄
序言：老撾萬榮一對情侶失蹤坏匪，失蹤者是張志新（化名）和其女友劉穎拟逮，沒想到半個月后，有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體适滓，經(jīng)...
沈念sama閱讀 45,319評論 1贊 310
?護林員之死
正文獨居荒郊野嶺守林人離奇死亡敦迄，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點故事閱讀 37,539評論 2贊 332
?白月光啟示錄
正文我和宋清朗相戀三年，在試婚紗的時候發(fā)現(xiàn)自己被綠了粒竖。大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片颅崩。...
茶點故事閱讀 39,703評論 1贊 348
活死人
序言：一個原本活蹦亂跳的男人離奇死亡，死狀恐怖蕊苗，靈堂內(nèi)的尸體忽然破棺而出沿后，到底是詐尸還是另有隱情，我是刑警寧澤朽砰，帶...
沈念sama閱讀 35,417評論 5贊 343
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布尖滚，位于F島的核電站，受9級特大地震影響瞧柔，放射性物質(zhì)發(fā)生泄漏漆弄。R本人自食惡果不足惜，卻給世界環(huán)境...
茶點故事閱讀 41,013評論 3贊 325
男人毒藥：我在死后第九天來索命
文/蒙蒙一造锅、第九天我趴在偏房一處隱蔽的房頂上張望撼唾。院中可真熱鬧，春花似錦哥蔚、人聲如沸倒谷。這莊子的主人今日做“春日...
開封第一講書人閱讀 31,664評論 0贊 22
一樁弒父案糙箍，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽渤愁。三九已至，卻和暖如春深夯，著一層夾襖步出監(jiān)牢的瞬間抖格，已是汗流浹背。一陣腳步聲響...
開封第一講書人閱讀 32,818評論 1贊 269
情欲美人皮
我被黑心中介騙來泰國打工咕晋，沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留雹拄，地道東北人。一個月前我還...
沈念sama閱讀 47,711評論 2贊 368
代替公主和親
正文我出身青樓捡需，卻偏偏與公主長得像办桨，于是被迫代替她去往敵國和親。傳聞我的和親對象是個殘疾皇子站辉，可洞房花燭夜當晚...
茶點故事閱讀 44,601評論 2贊 353

頭條算法題匯總

問答題

參考的帖子

推薦閱讀更多精彩內(nèi)容