常用算法及题解

背包问题

https://zhuanlan.zhihu.com/p/93857890?utm_source=wechat_session

数字找规律——分治

https://blog.nowcoder.net/n/f5703527172e480fa830275e521e356f

排序算法动图

http://tools.jb51.net/aideddesign/paixu_ys

快速排序

快速排序
可以用递归实现。
在上图的一次递归中，取右侧第一个数字a为标准，从左到右遍历，设当前被遍历数为x。

若x大于a，则从右侧端点开始寻找第一个小于a的数字b，将其于x进行位置交换。
若x小于a，则位置不变。
重复以上操作，直到左右两个遍历指针相交。
此时再分别将已经分好的两块数据进行递归操作即可。

堆排序

这是一个二叉树，存储在一个一维数组上。
二叉树的根为该数组中最大的值，root->left、root->right都比root小。
直接上代码吧，下面的代码实现了一个最大堆，和最大堆排序：

#include <vector>
#include <iostream>
#include <string>
#include <algorithm>


using namespace std;


template<typename _T>
class BigHeapTree : public vector<_T>
{
public:
    class TreeNode {
    public:
        TreeNode(BigHeapTree& tree, int idx):tree(tree), idx(idx) {}

        TreeNode parent() { return TreeNode(tree, (idx-1)/2); }
        TreeNode sibling() { return TreeNode(tree, idx % 2 ? idx+1 : idx-1); }
        TreeNode child_left(){ return TreeNode(tree, idx*2+1); }
        TreeNode child_right(){ return TreeNode(tree, idx*2+2); }

        inline void swap(TreeNode& node) {
            _T tmp = node.value();
            node.value() = this->value();
            this->value() = tmp;
        }

        inline bool is_root()const { return !idx; }
        inline bool is_right()const { return !is_left(); }
        inline bool is_left()const { return idx % 2; }
        inline bool has_sibling()const { return tree.size()-1 != idx; }
        inline bool is_valid()const { return idx < tree.size(); }

        inline const _T& value()const { return tree[idx]; }
        inline _T& value() { return tree[idx]; }
        inline bool operator<(const TreeNode& node)const { return value() < node.value(); }

        BigHeapTree& tree;
        int idx;
    };

    BigHeapTree(const vector<_T>& vec) {
        this->reserve(vec.size());
        for(auto& val : vec)
            this->insert(val);
    }

    inline void insert(const _T& val) {
        this->push_back(val);
        this->come_up(this->last());
    }
    inline void insert(_T&& val) {
        this->push_back(val);
        this->come_up(this->last());
    }

    inline TreeNode root(){ return TreeNode(*this, 0); }
    inline TreeNode last(){ return TreeNode(*this, this->size()-1); }

    static void sort(vector<_T>& vec) {
        BigHeapTree tree(vec);
        for(auto& val : vec) {
            TreeNode root = tree.root(), last = tree.last();
            val = root.value();
            root.swap(last);

            tree.resize(tree.size()-1);
            tree.come_down(root);
        }
    }

protected:
    void come_up(TreeNode node) {
        //  将元素进行上浮操作
        auto parent = node.parent();
        if(parent < node) {
            parent.swap(node);
            return come_up(parent);
        }
    }
    void come_down(TreeNode node) {
        //  将node进行下沉操作
        TreeNode big = node.child_left();
        if(big.is_valid()) {
            //  找到俩子元素中最大的big
            TreeNode right = node.child_right();
            if(right.is_valid() && big < right)
                big.swap(right);

            //  将big与当前node比较，并排序
            if(node < big)  {
                node.swap(big);
                this->come_down(big);
            }
        }
    }
};


int main() {
    vector<int> vec = {435,436,5545,4785,576,54,67,8987565,46,7897654,467,876,54,67898,57654,86,67687977,654354,4458};
    cout << "unsort array:\t";
    for(auto val : vec)
        cout << val << " ";
    cout << endl;

    BigHeapTree<int>::sort(vec);
    cout << "sorted array:\t";
    for(auto val : vec)
        cout << val << " ";
    cout << endl;

}

上面我继承了vector类，但该算法依然有可以优化的地方：

在构造函数中可以用从下而上的迭代方法inplace构造一个最大堆
在排序函数中可以通过将“删除”的元素放到末尾，来inpalce排序数组
结合以上两种方式，可以构造出一个inpalce排序，且复杂度仅为N*log(N)的排序算法

春招时间不够，以上代码将不再优化，直接开搞下一个！

归并排序

常用数据结构分析

二叉树

图左为完全二叉树，其节点顺序排列；图右为满二叉树，其深为k，有 $2^k-1$ 个节点

动态规划

求最长升序序列

https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/pythondong-tai-gui-hua-si-xiang-shi-pin-shi-fan-by/

#include <vector>
#include <iostream>
#include <string>
#include <algorithm>


using namespace std;


class LevelArray : public vector<int>
{
public:
    void append(int val) {
        this->push_back(val);
        this->max_val = max(val, this->max_val);
    }

    int max_val = INT32_MIN;
};


int main() {
    vector<int> nums = {1,3,6,7,9,4,10,5,6};
    vector<int> dp(nums.size());
    vector<LevelArray> ar;

    //
    LevelArray tmp;
    tmp.append(nums[nums.size()-1]);
    ar.push_back(tmp);
    for(int i=nums.size()-2; i>=0; --i) {
        int cur_val = nums[i];
        for(int j=0; j < ar.size(); ++j) {
            if(cur_val >= ar[j].max_val) {  //  当>=时结果不含鞍点，否则含鞍点
                ar[j].append(cur_val);
                break;
            }else if(j+1==ar.size()) {
                LevelArray x;
                x.append(cur_val);
                ar.push_back(x);
                break;
            }
        }
    }


    for(auto& a : ar){
        for(auto& val : a)
            cout << val << " ";
        cout << endl;
    }
}

数据结构面试总结