[数据结构与算法]Leetcode面试热题（一）

?如今不论是校招还是社招，大多数公司都会有笔试+面试的算法题，以此来考察候选人的数据结构和算法能力，因此我们面试前最好复习下算法，简单来说就是刷题呗！

? ? ? ? 以下是本人社招时在Leetcode和牛客网上的大厂的高频题，大概二三百道，此系列只列出最热门的一百来道，代码都是Leetcode上的，可以正常运行。大家可以根据下面推荐的题目来有选择的刷题，最好是进入Leetcode或牛客来刷，里面有许多优秀解法可以参考！

? ? ? ? 常见算法有背包、DFS、BFS、动态规划、数组、状态压缩、图优化、数学推导、字符串、链表二叉树、邻接表、图优化等等。

? ? ? ? 下面是正常的题目，大家可以参考一下：
?

//牛客网地址：https://www.nowcoder.com/ta/job-code-high

//2021.03.28

1、反转链表
/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        ListNode* pre = nullptr;
        ListNode* cur = pHead;
        while(pHead){
            ListNode* mid = pHead->next;
            pHead->next = pre;
            pre = pHead;
            pHead = mid;
        }
        return pre;
    }
};

2、排序算法
(1)快排
    void quickSort(vector<int>& arr,int low,int high){
        int left = low,right = high;
        if(left>=right)
            return;
        int flag = arr[low];             //哨兵
        while(left!=right){
            while(arr[right]>=flag && left<right)
                right--;
            while(arr[left]<=flag && left<right)
                left++;
            if(left<right)
                swap(arr[left],arr[right]);
        }
        swap(arr[low],arr[right]);
        
        quickSort(arr,low,right-1);
        quickSort(arr,right+1,high);
        
        return;
    };
	int main(){
		// write code here
		vector<int> arr = { 5, 2, 3, 1, 4 };
		int len = arr.size();
		quickSort(arr, 0, len - 1);
		for (int i = 0; i < len; i++)
			cout << arr[i] << "   ";
		return 0;
	}



//2021.03.29
3、实现LRU算法

哈希表+双向链表

class LRUCache {
public:
    LRUCache(int capacity) {
        size = capacity;
    }
    
    int get(int key) {
        auto it = ans.find(key);
        if(it == ans.end())
            return -1;
        res.splice(res.begin(),res,it->second);              // let it->second in begin
        return it->second->second;
    }
    
    void put(int key, int value) {
        auto it = ans.find(key);
        if(it != ans.end())
            res.erase(it->second);
        if(res.size()==size){
            int k = res.rbegin()->first;
            res.pop_back();
            ans.erase(k);                                   //map can erase or insert by key
        }    
        res.push_front(make_pair(key,value));
        ans[key] = res.begin();
    }

private:
    int size;                                                 //LRU size;
    list<pair<int,int>> res;                                  // store <key:value>
    unordered_map<int,list<pair<int,int>>::iterator > ans;    // <key,<key:value>::iterator> 
};


4、判断链表是否存在环
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if(head == nullptr || head->next == nullptr)
            return false;
        ListNode* slow = head;
        ListNode* fast = head->next;
        while(slow!=fast){
            if(fast == nullptr ||fast->next == nullptr)
                return false;
            slow = slow->next;
            fast = fast->next->next;
        }
        return true;
        
    }
};

//2021.03.30
5、二叉树
 struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 };
 
（1）二叉树的前序遍历  ： 按照访问根节点——>左子树——>右子树的方式遍历这棵树

<1>递归
class Solution {
public:
    void preorder(TreeNode *root, vector<int> &res) {
        if (root == nullptr) {
            return;
        }
        res.push_back(root->val);
        preorder(root->left, res);
        preorder(root->right, res);
    }

    vector<int> preorderTraversal(TreeNode *root) {
        vector<int> res;
        preorder(root, res);
        return res;
    }
};

<2>栈调用
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        if (root == nullptr) {
            return res;
        }

        stack<TreeNode*> stk;
        TreeNode* node = root;
        while (!stk.empty() || node != nullptr) {
            while (node != nullptr) {
                res.emplace_back(node->val);
                stk.emplace(node);
                node = node->left;
            }
            node = stk.top();
            stk.pop();
            node = node->right;
        }
        return res;
    }
};

（2）二叉树的中序遍历  ： 按照访问左子树——>根节点——>右子树的方式遍历这棵树

<1>递归
class Solution {
public:

    void inorderTraversal(TreeNode* root,vector<int> &res){
        if(root == nullptr)
            return;
        inorderTraversal(root->left,res);
        res.push_back(root->val);
        inorderTraversal(root->right,res);
    }

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

（3）二叉树的后序遍历  ： 按照访问左子树——>右子树——>根节点的方式遍历这棵树

<1>递归
class Solution {
public:

    void inorderTraversal(TreeNode* root,vector<int> &res){
        if(root == nullptr)
            return;
        inorderTraversal(root->left,res);
        inorderTraversal(root->right,res);
		res.push_back(root->val);
    }

    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        if(root == nullptr)
            return res;
        inorderTraversal(root,res);
        return res;
        
    }
};

<2>栈调用
class Solution {
public:
    vector<int> postorderTraversal(TreeNode *root) {
        if (!root) return {};
        vector<int> vec;
        stack<TreeNode *> stk;
        TreeNode *prev = nullptr;
        auto node = root;
        while (!stk.empty() || node) {
            // 1.遍历到最左子节点
            while (node) {
                stk.emplace(node);
                node = node->left;
            }
            node = stk.top(); stk.pop();
            // 2.遍历最左子节点的右子树(右子树存在 && 未访问过)
            if (node->right && node->right != prev) {
                // 重复压栈以记录当前路径分叉节点
                stk.emplace(node);
                node = node->right;      
            } else {
                // 后序：填充vec在node->left和node->right后面
                // 注意：此时node的左右子树应均已完成访问
                vec.emplace_back(node->val);
                // 避免重复访问右子树[记录当前节点便于下一步对比]
                prev = node;
                // 避免重复访问左子树[设空节点]
                node = nullptr;
            }
        }
        return vec;
    }
};




6、求数组中最小的K个数（大根堆）

class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        vector<int> vec(k, 0);
        if (k == 0) { // 排除 0 的情况
            return vec;
        }
        priority_queue<int> Q;
        for (int i = 0; i < k; ++i) {
            Q.push(arr[i]);
        }
        for (int i = k; i < (int)arr.size(); ++i) {
            if (Q.top() > arr[i]) {
                Q.pop();
                Q.push(arr[i]);
            }
        }
        for (int i = 0; i < k; ++i) {
            vec[i] = Q.top();
            Q.pop();
        }
        return vec;
    }
};


//2021.03.31
7、二叉树的层序遍历
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int> > ans;
        vector<int> res;
        
        deque<TreeNode*> mid1,mid2;
        if(root == nullptr)
            return ans;

        mid1.push_back(root);
        while(!mid1.empty()||!mid2.empty()){
            
            while(!mid1.empty()){

                TreeNode* mid = mid1.front();
                res.push_back(mid->val);

                if(mid->left)
                    mid2.push_back(mid->left);
                if(mid->right)
                    mid2.push_back(mid->right);

                mid1.pop_front();
            }
            ans.push_back(res);
            res.clear();
            swap(mid1,mid2);
        }

        return ans;
    }
};

8、寻找数组中的第K大树
class Solution {
public:
    int findKth(vector<int> a, int n, int K) {
        // write code here
        priority_queue<int,vector<int>,greater<int>> res;
        
        for(int i = 0; i<n; i++){
            if(i<K)
                res.push(a[i]);
            else{
                if(a[i]>res.top()){
                    res.pop();
                    res.push(a[i]);
                }
            }
        }
        return res.top();
    }
};

9、两数之和
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
	vector<int> num;
	if (nums.empty()) {
		return num;
	}
	num.push_back(0);
	num.push_back(0);
	int left = 0, right = nums.size()-1;

	for (; left < right;) {
		if (nums[left] + nums[right] > target) {
			right--;
		}
		else if (nums[left] + nums[right] < target) {
			left++;
		}
		else if (nums[left] + nums[right] == target) {
			num[0]=left;
			num[1]=right;
			break;
		}
	}

	return num;
    }
};

10、合并两个有序链表

/**
 * Definition for singly-linked list.
 * 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) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {

        ListNode* ans = new ListNode(-1);
        ListNode* res = ans;

        while(l1!=nullptr&&l2!=nullptr){
            if(l1->val < l2->val){
                ans->next = l1;
                l1 = l1->next;
                ans = ans->next;
            }else{
                ans->next = l2;
                l2 = l2->next;
                ans = ans->next;
            }
        }
        if(l1!=nullptr)
            ans->next = l1;
        if(l2!=nullptr)
            ans->next = l2;            

        return res->next;
    }
};