数据科学 算法

算法学习

Posted by BUAADreamer on 2021-07-10
Words 6.7k and Reading Time 32 Minutes
Viewed Times

算法学习笔记，本篇主要是一些基本的知识整理

Leetcode高频算法实战学习·

一、数组·

数组理论·

使用静态数组实现的方法：每次大小不够时将新的静态数组长度增大一倍，这样就可以将拷贝数值的复杂度降到$O(n)$

不同遍历方式差别很大，以下三种从上到下时间依次上升。

参考博客：https://blog.csdn.net/xiewuquan/article/details/50492096

1
2
3
4
5
6
7
8
9
10
vector<int> a;
for(int i=0;i<a.size();i++){
	print(a[i]);
}
for(int x:a){
    print(x);
}
for(vector<int>::iterator it:a.begin();it!=a.end();it++){
    print(it);
}

emplace_back效果和push_back一致，最好使用前者，节省空间开销

如果已经确定了数组长度，就直接先使用vector<int> ans(n);初始化好再直接用下标索引直接赋值，比一个个push_back快

扫描数组技巧·

求数组区间和，区间方差，二位数组矩阵区域和方法：记录从0到每个序号的和，然后用sum[j]-sum[i-1]的方式求出区间[i,j]的和

序列问题·

下一个排列·

  1. 数组长度小于2直接返回原数组
  2. 从后往前扫描找到一个序号i使得nums[i]<nums[i+1]
  3. 在nums[i+1,n-1]之间找到一个大于nums[i]且最小的数的序号mini，将mini和i处的数交换
  4. 将i位置之后的数组逆序（由从大到小变为从小到大）

前一个排列·

  1. 数组长度小于2直接返回原数组
  2. 从后往前扫描找到一个序号i使得nums[i]>nums[i+1]
  3. 在nums[i+1,n-1]之间找到一个小于nums[i]且最大的数的序号maxi，将maxi和i处的数交换
  4. 将i位置之后的数组逆序（由从小到大变为从大到小）

逆序过程可以用sort函数

1
2
3
4
5
sort(nums+i,nums+n-1,cmp); //n=nums.size()
sort(nums.begin()+i,nums.end(),cmp); //另一种写法
static bool cmp(const int a,const int b){
    return a>b; //从大到小排序 a<b则是从小到大
}

最大子序和·

最大连续子数组和·

先求出从0到每个位置的和，用sums记录，在这个遍历过程中同时记录在每个位置之前的位置中sum最小的位置，也用另一个数组存储。

之后对每个位置i，计算sums[i]-sums[minPos[i]]的最大值

环形数组最大连续子数组和·

用一个普通数组表示环形数组

分为两种情况

case1:最大的子数组在原数组中间，此时等价于之前普通的数组情况

1
**+++**

case2:最大子数组在原数组两边，此时等价于求最小连续子数组和

1
++***++

有序数组查找问题·

两数之和·

有序数组中，两个指针l,r记录。两个位置数字和与目标值比较，一样的话返回，大了就r–，小的话就l++。

三数之和·

三个指针i j k(i<=j<=k)

定死一个位置i，看是否存在nums[j]+nums[k]=target-nums[i]

二分查找·

1
2
3
4
5
6
7
8
9
10
11
12
13
int n=nums.size();
int l=0,r=n-1;
while(l<=r){
    int mid=(l+r)/2;
    if(nums[mid]==target){
        return mid;
    } else if(nums[mid]<target){
        l=mid+1;
    } else {
        r=mid-1;
    }
}
return -1;

搜索旋转排序矩阵·

类似二分查找的思路，加一些判定

假设左边的数位置是 L，右边位置是 R：

  1. 如果当前数组的长度小于等于 2 的话，我们按边界条件处理。

  2. 否则，取中间的位置 M，先判断目标值和 M 位置值的关系，如果相等直接返回 M。

  3. 然后，如果 M 位置的值大于 L 位置的值:

    • 如果目标值在 L 到 M 之间，我们递归左边部分。

    • 其他情况，递归右边部分。

  4. 如果 M 位置的值小于 L 位置的值:

    • 如果目标值在 M 到 R 之间，递归右边部分。

    • 其他情况，递归左边部分。

搜索二维矩阵·

每次从左下角的指针开始判断

对于m*n矩阵，初始化指针为x=m-1,y=0

之后nums[x][y]>target就x–

相等就返回

小于就y++

二、栈·

后进先出

需要实现top() size() pop() push(x)四个操作

括号匹配·

表达式计算·

三、队列·

先进先出

滑动窗口最大值·

方法2：使用单调双向队列解决问题·

原理：如果在k个数中存在一个编号i<j,nums[i]<=nums[j]则nums[i]必定不可能是最大的那个数，因此将这样的数出队。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> q; //q为原数组的序号队列，相当于同时存储了数值和编号两个值
        int n=nums.size();
        for(int i=0;i<k;i++){ //初始化先将前k个数中降序的编号存到队列中
            while(!q.empty()&&nums[q.back()]<=nums[i]){
                q.pop_back();
            }
            q.push_back(i);
        }
        vector<int> ans={nums[q.front()]};
        for(int i=k;i<n;i++){
            while(!q.empty()&&nums[q.back()]<=nums[i]){
                q.pop_back();
            }
            q.push_back(i);
            if(q.front()<i-k+1){
                q.pop_front();
            }
            ans.push_back(nums[q.front()]);
        }
        return ans;
    }
};

方差计算：$D(x)=\sum x_i^2-((\sum x_i)/n)^2$

求岛屿最大面积·

遍历每一个土地，是1则开始广度搜索，同时将搜索到的土地标记为0，即不能再次访问，直到队列为空。

四、链表·

反转链表·

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//递归解法
ListNode* recurseWay(ListNode* head) {
    if(!head||!head->next){
    	return head;
    }
    ListNode * newHead=recurseWay(head->next);
    head->next->next=head;
    head->next=nullptr;
    return newHead;
}

//非递归解法
ListNode* noRecurseWay(ListNode* head) {
    ListNode* newHead=nullptr;
    while(head){
        ListNode* nt=head->next;
        head->next=newHead;
        newHead=head;
        head=nt;
    }
    return newHead;
}

五、树·

前序遍历：根节点–>左子树–>右子树

中序遍历：左子树–>根节点–>右子树

后序遍历：左子树–>右子树–>根节点

根据前序遍历和中序遍历结果构造二叉树·

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
//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 mySolution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if(preorder.empty()){
            return nullptr;
        }
        int rootval=preorder[0];
        int n=inorder.size();
        TreeNode* root=new TreeNode(rootval);
        int r=find(inorder.begin(),inorder.end(),rootval)-inorder.begin();
        vector<int> preorder1;
        vector<int> preorder2;
        vector<int> inorder1;
        vector<int> inorder2;
        for(int i=0;i<r;i++){
            preorder1.push_back(preorder[1+i]);
            inorder1.push_back(inorder[i]);
        }
        for(int i=r+1;i<n;i++){
            preorder2.push_back(preorder[i]);
            inorder2.push_back(inorder[i]);
        }
        root->left=buildTree(preorder1,inorder1);
        root->right=buildTree(preorder2,inorder2);
        return root;
    }
};
class officalSolution {
private:
    unordered_map<int,int> index;
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int n=inorder.size();
        for(int i=0;i<n;i++){
            index[inorder[i]]=i;
        }
        return myBuildTree(preorder,inorder,0,n-1,0,n-1);
    }
    TreeNode* myBuildTree(vector<int>& preorder,vector<int>& inorder,int prel,int prer,int inl,int inr){
        if(prel>prer){
            return nullptr;
        }
        TreeNode* root=new TreeNode(preorder[prel]);
        int rooti=index[preorder[prel]];
        int leftLen=rooti-inl;
        root->left=myBuildTree(preorder,inorder,prel+1,prel+leftLen,inl,inl+leftLen-1);
        root->right=myBuildTree(preorder,inorder,prel+leftLen+1,prer,rooti+1,inr);
        return root;
    }
};

根据中序和后序遍历结果构造也是同理，只需要对上述做法微调即可。

层序遍历·

普通递归或者BFS都可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
private:
    vector<vector<int>> ans;
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        dfsLevelOrder(root,1);
        return ans;
    }
    void myLevelOrder(TreeNode* root,int level){ //me
        if(root!=nullptr){
            if(level>ans.size()){
                vector<int> ls;
                ls.push_back(root->val);
                ans.push_back(ls);
            } else {
                ans[level-1].push_back(root->val);
            }
            myLevelOrder(root->left,level+1);
            myLevelOrder(root->right,level+1);
        }
    }
    vector<vector<int>> bfsLevelOrder(TreeNode* root) { //Leetcode official
        vector <vector <int>> ret;
        if (!root) {
            return ret;
        }
        queue <TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            int currentLevelSize = q.size();
            ret.push_back(vector <int> ());
            for (int i = 1; i <= currentLevelSize; ++i) { 
                //这里的bfs与一般的不同，每次将当前循环中所有元素全部处理并出队，相当于处理完【一层】
                auto node = q.front(); q.pop();
                ret.back().push_back(node->val);
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
        }
        return ret;
    }
};

寻找最近公共祖先·

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root==p||root==q){ //root和p或q中某个相等直接返回root
            return root;
        }
        TreeNode* ansl=nullptr;
        TreeNode* ansr=nullptr;
        if(root->left!=nullptr){
            ansl=lowestCommonAncestor(root->left,p,q); //查询左子树
        }
        if(root->right!=nullptr){
            ansr=lowestCommonAncestor(root->right,p,q);//查询右子树
        }
        if(ansl!=nullptr&&ansr!=nullptr){
            return root; //都不为空，则一个在左子树，一个在右子树
        } else if(ansl!=nullptr){
            return ansl; //只有一个为空则返回那个结果
        } else {
            return ansr;
        }
    }
};

树上最接近的两部分·

删除一条边使得分开的两部分节点之和最接近（差的绝对值最小）

思路：先求出每个子树的和并记录在对应节点的val中，再遍历每个节点找出答案

最优子结构特性

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int similarTwoParts(TreeNode* root) {
        getSum(root);
        int s=root->val;
        int minsum=0x3fffff;
        findMax(root,minsum,s);
        return minsum;
    }
    void findMax(TreeNode* root,int &minsum,int rootsum){
        if(root==nullptr){
            return;
        }
        if(root->val!=rootsum&&abs(rootsum-2*root->val)<minsum){
            minsum=abs(rootsum-2*root->val);
        }
        findMax(root->left,minsum,rootsum);
        findMax(root->right,minsum,rootsum);
    }
    int getSum(TreeNode* root){
        if(root==nullptr){
            return 0;
        }
        root->val=getSum(root->left)+getSum(root->right)+root->val;
        return root->val;
    }
};

六、堆（优先队列）·

堆：完全二叉树，且每个子树的根节点的值都是这个子树的最大值或者最小值

判断二叉树是否为堆·

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
private:
    vector<int> index;
public:
    bool isLegalHeap(TreeNode* root) {
        //判断是否为完全二叉树
        getIndex(root,0);
        sort(index.begin(),index.end());
        for(int i=1;i<index.size();i++){
            if(index[i]>index[i-1]+1){
                return false;
            }
        }
        //判断是否符合堆的性质
        return isBiggestLegalHeap(root)||isLeastLegalHeap(root); //两个函数也可以增加一个变量来合并
    }
    void getIndex(TreeNode* root,int i){ //遍历二叉树获取每个非空元素的在堆中的序号
        if(root==nullptr){
            return;
        }
        index.push_back(i);
        getIndex(root->left,i*2+1);
        getIndex(root->right,i*2+2);
    }
    bool isBiggestLegalHeap(TreeNode* root) {
        if(root==nullptr){
            return true;
        }
        if(root->left!=nullptr&&root->left->val>root->val||root->right!=nullptr&&root->right->val>root->val){
            return false;
        }
        return isBiggestLegalHeap(root->left)&&isBiggestLegalHeap(root->right);
    }
    bool isLeastLegalHeap(TreeNode* root) {
        if(root==nullptr){
            return true;
        }
        if(root->left!=nullptr&&root->left->val<root->val||root->right!=nullptr&&root->right->val<root->val){
            return false;
        }
        return isLeastLegalHeap(root->left)&&isLeastLegalHeap(root->right);
    }
};

将二叉树转换为堆·

改进的BFS层序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<int> transferHeapToList(TreeNode* root) {
        vector<int> heap;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()){
            int sz=q.size();
            for(int i=0;i<sz;i++){
                TreeNode* node=q.front();q.pop();
                heap.push_back(node->val);
                if(node->left!=nullptr){
                    q.push(node->left);
                }
                if(node->right!=nullptr){
                    q.push(node->right);
                }
            }
        }
        return heap;
    }
};

合并k个有序链表 ※※※·

维护这k个有序链表的头节点的优先队列（即最小堆）,每次从最小堆里弹出最小的节点并将他的链表后继节点加入堆中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * 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 { //LeetCode-Solution
public:
    struct Status {
        int val;
        ListNode *ptr;
        bool operator < (const Status &rhs) const { //重载运算符构造最小堆
            return val > rhs.val;
        }
    };

    priority_queue <Status> q;

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        for (auto node: lists) {
            if (node) q.push({node->val, node});
        }
        ListNode head, *tail = &head; //head.next指向总链表的头 tail为尾部
        while (!q.empty()) {
            auto f = q.top(); q.pop();
            tail->next = f.ptr; 
            tail = tail->next;
            if (f.ptr->next) q.push({f.ptr->next->val, f.ptr->next});
        }
        return head.next;
    }
};

合并k个最小堆·

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
public:
    struct Status {
        int i;
        int val;
        bool operator < (const Status &rhs) const { //重载运算符构造最小堆
            return val > rhs.val;
        }
    };
    priority_queue <Status> q; //将每个最小堆的首元素维护一个最小堆
    vector<int> mergeKHeaps(vector<vector<int>>& heaps) {
        vector<int> ans;
        for(int i=0;i<heaps.size();i++){
            q.push({i,heaps[i][0]});
        }
        while(!q.empty()){
            ans.push_back(extractMin(heaps));
        }
        return ans;
    }
    int extractMin(vector<vector<int>>& heaps){ //返回一个堆顶的值，并做相应的各个堆的维护
        /* 以下写法错误，注意避免
        	vector<int> heap=heaps[top.i];
        	heap.pop_back();
        	这样相当于新建了一个heap变量，没有对原heaps做修改
        */
        struct Status top=q.top();q.pop();
        int n=heaps[top.i].size(); 
        int tmp=heaps[top.i][n-1];heaps[top.i][n-1]=heaps[top.i][0];heaps[top.i][0]=tmp;
        heaps[top.i].pop_back();
        if(!heaps[top.i].empty()){
            minHeapify(heaps[top.i],0);
            q.push({top.i,heaps[top.i][0]});
        }
        return top.val;
    }
    void minHeapify(vector<int>& heap,int i){ //维持最小堆
        int n=heap.size();
        int l=i*2+1;
        int mini=i;
        if(l<n&&heap[l]<heap[mini]){
            mini=l;
        }
        int r=i*2+2;
        if(r<n&&heap[r]<heap[mini]){
            mini=r;
        }
        if(mini!=i){
            int tmp=heap[i];heap[i]=heap[mini];heap[mini]=tmp;
            minHeapify(heap,mini);
        }
    }
};

七、二叉查找树·

八、图·

广度优先搜索遍历 DFS

深度优先搜索遍历 BFS

九、设计类问题·

十、贪心与分治·

问题拆解与相应原则 ※※※·

如果子问题最优则原问题最优，贪心算法。

如果子问题需要全部求解才能求解原问题，子问题互相独立，分治算法。

如果子问题最优不能保证原问题最优，但是子问题之间不会循环（所谓循环，是指从问题 A 拆解出子问题 B，然后子问题 B 又能拆解出子问题 A），考虑动态规划算法。

更加复杂的情况，我们总是可以考虑暴力搜索解决。

分发饼干·

先将需求数组g和尺寸数组s排序，然后对于每一个孩子的需求都寻找到最小的符合需求的饼干进行满足

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(),g.end());
        sort(s.begin(),s.end());
        int n=g.size();
        int m=s.size();
        int i=0,j=0;
        for(;i<n&&j<m;i++){
            if(s[j]<g[i]){
                i--;
            }
            j++;
        }
        return i;
    }
};

用最少数量的箭引爆气球·

遇到区间类的贪心问题，都先考虑排序，一般按照左端点或者右端点排序，控制复杂度为 $O(n\lg n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public:
    typedef struct node{
        int point;//坐标
        int type; //0:begin 1:end
        int pos;  //编号
    } Node;
    static bool cmp(Node x,Node y){ //将所有节点进行排序，坐标小的靠前，坐标一致将起点置于前
        return x.point<y.point?true:
               x.point>y.point?false:
               x.type==0?true:false;
    }
    int findMinArrowShots(vector<vector<int>>& points) {
        vector<Node> nodes;
        int n=points.size();
        vector<int> exist(n,0); //表示每个编号的气球是否已经被射爆
        queue<int> targets; //当前可以被一次射中的全部气球编号
        int ans=0;
        for(int i=0;i<n;i++){
            nodes.push_back({points[i][0],0,i});
            nodes.push_back({points[i][1],1,i});
        }
        sort(nodes.begin(),nodes.end(),cmp);
        for(auto node:nodes){
            if(node.type==0){
                targets.push(node.pos); //起点，直接进队
            } else {
                if(!exist[node.pos]){   //终点且这个气球没被射爆
                    ans++;
                    while(!targets.empty()){ //全部出队并设置为已射爆
                        exist[targets.front()]=1;
                        targets.pop();
                    }
                }
            }
        }
        return ans;
    }
};

快速幂·

例子：$3^{15}$ $15=(1111)_2 $ $3{15}=3{1+2+4+8}$

分治算法的经典例子

可以延申求矩阵快速幂，用于动态规划的加速

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    double myPow(double x, int n) {
        long long N=n;
        return n>=0?quickMul_recursion(x,n):1/quickMul_recursion(x,-N);
    }
    double quickMul_recursion(double x,long long n){ 
        if(n==0) return 1;
        double y=quickMul_recursion(x,n/2);
        return n%2==1?y*y*x:y*y;
    }
    double quickMul(double x,long long n){
        double x_exp=x;
        double ans=1;
        while(n){
            if(n%2==1) ans*=x_exp;
            x_exp*=x_exp;
            n/=2;
        }
        return ans;
    }
};

排序链表·

$O(n\lg n)$ 时间复杂度与常数空间复杂度情况下完成链表排序

分治算法，先拆分再合并，类似归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
/**
 * 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* sortList(ListNode* head) {
        ListNode* odd=nullptr;
        ListNode* even=nullptr;
        ListNode* podd=nullptr;
        ListNode* peven=nullptr;
        ListNode* p=head;
        int i=0;
        //先将原链表拆分成奇数位置链表和偶数位置链表两个链表
        while(p){
            if(i%2==0) {
                if(!even) even=p;
                else peven->next=p;
                peven=p;
            } else {
                if(!odd) odd=p;
                else podd->next=p;
                podd=p;
            }
            p=p->next;
            i++;
        }
        if(podd) podd->next=nullptr;
        if(peven) peven->next=nullptr; //此处不能忘记把当前的指针的下一个设为NULL，否则会一直循环
        if(i<=1) return head; //长度小于等于1时直接返回原指针
        //合并sort后的奇数子表和偶数子表
        return mergeNode(sortList(even),sortList(odd));
    }
    ListNode* mergeNode(ListNode* p,ListNode* q){
        ListNode* ans=nullptr;
        ListNode* cur=nullptr;
        while(p||q){ //比较两个头指针，每次将小的加入到答案链表中
            if(!q||(p&&(p->val<q->val))){
                if(!ans) ans=p;
                else cur->next=p;
                cur=p;
                p=p->next;
            } else {
                if(!ans) ans=q;
                else cur->next=q;
                cur=q;
                q=q->next;
            }
        } 
        cur->next=nullptr;
        return ans;
    }
};

数组中出现次数超过一半的数字·

分治：子问题为在子数组中出现次数超过一半的数，最后将左右两个子数组的结果合并

贪心：摩尔投票，利用抵消的方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
//my code
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int,int> num2cnt;
        int n=nums.size();
        for(int i=0;i<n;i++){
            num2cnt[nums[i]]++;
            if(num2cnt[nums[i]]>n/2){
                return nums[i];
            }
        }
        return 0;
    }
};

//贪心 摩尔投票法
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int n=nums[0];
        int cnt=1;
        int m=nums.size();
        for(int i=1;i<m;i++){
            if(nums[i]==n) cnt++;//相同，次数++
            else {
                if(cnt==0){ //不相同 若已经到了0，则更换答案，没到0就--
                    n=nums[i];
                    cnt=1;
                } else cnt--;
            }
        }
        return n;
    }
};

十一、常用排序算法·

冒泡排序，归并排序，快速排序，桶排序，堆排序

对角线遍历 II·

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    typedef struct node{
        int s;
        int y;
    }Node; //s=x+y 
    static bool cmp(Node x,Node y){
        return x.s<y.s?true:
               x.s>y.s?false:
               x.y<y.y?true:false;
    }
    vector<int> findDiagonalOrder(vector<vector<int>>& nums) {
        vector<Node> tmp;
        vector<int> ans;
        for(int i=0;i<nums.size();i++){
            for(int j=0;j<nums[i].size();j++){
                tmp.push_back({i+j,j});
            }
        }
        sort(tmp.begin(),tmp.end(),cmp);
        for(auto x:tmp){
            ans.push_back(nums[x.s-x.y][x.y]);
        }
        return ans;
    }
};

最大间距·

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
public:
    int maximumGap(vector<int>& nums) {
        return maximumGap_normal(nums);
    }
    int maximumGap_normal(vector<int>& nums){ //暴力解法
        sort(nums.begin(),nums.end());
        int ans=0,n=nums.size();
        if(n<2)return 0;
        for(int i=0;i<n-1;i++){
            ans=max(ans,nums[i+1]-nums[i]);
        }
        return ans;
    }
    int maximumGap_Bucketsort(vector<int>& nums){ //桶排序方式 这样实现比暴力还慢，不太行
        int n=nums.size();
        if(n<2)return 0;
        int minx=*min_element(nums.begin(), nums.end());
        int maxx=*max_element(nums.begin(), nums.end());
        if(n==2)return maxx-minx; //只有两个元素，返回两者最大值
        int d=ceil((double)(maxx-minx)/(n-1));
        if(maxx==minx)return 0; //考虑数组全相等的情况，防止之后d=0出现错误
        vector<int> minBuc(n-1,maxx+1);
        vector<int> maxBuc(n-1,minx-1);
        vector<bool> ap(n-1,false);
        for(int i=0;i<n;i++){
            int pos=(nums[i]-minx)/d;
            if(pos>=n-1)pos=n-2; //这里要注意最大值可能会等于minx+(n-1)d 如果不设成n-2会出错
            if(!ap[pos])ap[pos]=true;
            if(minBuc[pos]>nums[i])minBuc[pos]=nums[i];
            if(maxBuc[pos]<nums[i])maxBuc[pos]=nums[i];
        }
        int ans=d;
        for(int i=0;i<n-1;i++){
            if(!ap[i])continue;
            int j=i+1;
            while(j<n-1&&!ap[j])j++;
            if(j==n-1)break;
            ans=max(ans,minBuc[j]-maxBuc[i]);
            i=j-1;
        }
        return ans;
    }
};

有效的字母异位词·

判断两个单词的每个字母出现次数是否均一样

采用桶排序，也可以理解为使用标记数组或hash表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool isAnagram(string s, string t) {
        int cnts[26]={0};
        int cntt[26]={0};
        int n=s.size();
        for(int i=0;i<n;i++){
            cnts[s[i]-'a']++;
        }
        n=t.size();
        for(int i=0;i<n;i++){
            cntt[t[i]-'a']++;
        }
        for(int i=0;i<26;i++){
            if(cnts[i]!=cntt[i])return false;
        }
        return true;
    }
};

十二、Trie 树和KMP 算法·

《labuladong算法小抄》笔记·

一、语言基础·

C++·

传参用&表示引用

1
2
pair<int,int> p(1,2);
cout<<p.first<<p.second;

1.动态数组vector·

https://www.runoob.com/w3cnote/cpp-vector-container-analysis.html

https://www.cnblogs.com/maluning/p/8570717.html

初始化·
1
2
3
4
5
6
7
int n=7,m=8;
vector<int> nums;
vector<int> nums(n); //数组中全部为0
vector<int> nums{1,3,5}; //初始化为1,3,5
vector<int> nums(n,2); //初始化一个长度为n且全为2的数组
vector<vector<int>> dp; //初始一个二维数组
vector<vector<bool>> dp(m,vector<bool>(n,true)); //初始一个m*n的二维布尔数组 且值全为true
成员函数·
1
2
3
4
5
6
bool empty() //返回是否为空
size_type size(); //返回大小
reference back(); //返回最后一个值的引用
void push_back(const value_type& val); //尾部插入一个元素val
void pop_back(); //删除尾部元素
erase(vector<int>::iterator);

2.字符串string·

初始化·
1
2
string s; //s-->""
string s="abc";
成员函数·
1
2
3
4
5
6
size_t size();
bool empty();
void push_back(char c); //尾部插入一个字符c
void pop_back(); //删除尾部字符
string substr(size_t pos,size_t len); //获得pos开始的长度为len的子串
cout<<s1==s2; //看两字符串是否相等

3.哈希表unordered_map·

初始化·
1
2
unordered_map<int,int> mapping; //key and value both int
unordered_map<string,int> mapping; //key is string,value is int
成员函数·
1
2
3
4
size_type size(); //返回键值对个数
bool empty();//是否为空
size_type count (const key_type& key); //返回key在map中出现次数,由于哈希表，这个值只能是0/1，因此本函数用于判断key是否在哈希表中
size_type erase(const key_type& key); //清除一个键值对
常见操作·
1
2
3
4
5
6
7
8
9
10
vector<int> nums{1,2,3,4,5,6}
unordered_map<int,int> counter;
for(int num:nums){
    counter[num]++; //如果键值num本来不存在，则相当于是初始化为0后再+1:counter[num]=0;counter[num]++;
}
for(auto& it:counter){
    int key=it.first;
    int value=it.second;
    cout<<key<<":"<<value<<endl;
}

4.哈希集合unordered_set·

初始化·
1
2
unordered_set<int> visited;
unordered_set<string> visited;
成员函数·
1
2
3
4
5
size_type size(); //返回元素的个数
bool empty();//是否为空
size_type count (const key_type& key); //类似哈希表
pair<iterator,bool> insert(const key_type& key);//插入元素
size_type erase(const key_type& key);//删除元素

5.队列queue·

初始化·
1
2
queue<int> q;
queue<string> q;
成员函数·
1
2
3
4
5
6
size_type size(); //返回队列元素的个数
bool empty();//队列是否为空
void push(const value_type&val); //加入元素到队尾
value_type& front(); //获得队头元素引用
void pop(); //删除队头元素
int e=q.front();q.pop(); //获得队头元素并出队,注意,pop()是直接删除,不会返回队头元素

5.1双向队列deque·

1
2
3
4
5
void push_back(const value_type&val);
void pop_back();
void push_front(const value_type&val);
void pop_front();
value_type& front();back();

6.堆栈stack·

初始化·
1
2
stack<int> stk;
stack<string> stk;
成员函数·
1
2
3
4
5
size_type size(); //返回堆栈元素的个数
bool empty();//堆栈是否为空
void push(const value_type&val); //加入元素到栈顶
value_type& top(); //获得栈顶元素引用
void pop(); //删除栈顶元素

Java·

1.数组·

1
2
3
4
int m=5,n=10;
int[] nums=new int[n];
boolean[][] visited=new boolean[m][n];
nums.length -->获得数组长度

2.字符串String·

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
String s1="Hello,world";
char c=s1.charAt(2); //返回字符串中第2个字符
char[] chars=s1.toCharArray();  //字符串转字符数组
chars[1]='a';
String s2=new String(chars); //字符数组转字符串
System.out.println(s2);

if(s1.equals(s2)){
    //s1==s2
}else{
    //s1!=s2
}

String s3=s1+"!"; //+的效率比较低
StringBuilder sb=new StringBuilder(); //一般用StringBuilder append方法好一点
for(char c='a';c<'f';c++){  
    sb.append(c);
}
sb.append('a').append("avx").append(1234) //支持拼接字符串，字符，数字
    
String s=sb.toString();//转为字符串类型
//注:字符串比较尽量用s.equals(s1),否则可能出意想不到的问题

3.动态数组ArrayList·

类似C++的vector

E代表元素,下同

1
2
3
4
5
6
ArrayList<String> nums=new ArrayList<>();
ArrayList<Integer> strings=new ArrayList<>();
boolean isEmpty();
int size(); //获得数组大小
E get(int index); //获得index处元素
boolean add(E e); //尾部添加元素

4.双链表LinkedList·

1
2
3
4
5
6
7
8
LinkedList<String> strings=new LinkedList<>();
boolean isEmpty();
int size(); //获得数组大小
boolean contains(Object o); //时间复杂度为O(n),比较慢
boolean add(E e);
boolean addFirst(E e); //头部添加元素
E removeFirst();//delete first element
E removeLast();//delete last element

5.哈希表HashMap·

1
2
3
4
5
6
7
8
9
10
11
12
HashMap<Integer,String> map=new HashMap<>();
HashMap<String,int[]> map=new HashMap<>(); //字符串到数组

//常用方法
//K代表键值，V代表类型
boolean containsKey(Object key); //判断是否存在键key
V get(Object key);//获得key对应value值
V put(K key,V value); //存入哈希表
V remove(Object key); //删除key并返回对应值
V getOrDefault(Object key,defaultValue) //返回key对应value值，不存在则返回default值
Set<k> keySet() //获得Hash表中所有key
V putIfAbsent(K key,V value);//存在则不做事,不存在就插入

6.哈希集合HashSet·

1
2
3
4
Set<String> set=new HashSet<>(); //init
boolean add(E e); //add an element
boolean contains(Object o); //集合是否存在元素o
boolean remove(Object o); //若o存在则删除

7.队列Queue·

Queue是一个接口,初始化方式相对特别

1
2
3
4
5
6
7
Queue<String> q=new LinkedList<>();

boolean isEmpty();
int size();
E peek(); //返回队头元素
E poll(); //删除并返回队尾元素
boolean offer(E e); //将元素e插入队尾

8.堆栈Stack·

1
2
3
4
5
6
Stack<integer> s=new Stack<>();
boolean isEmpty();
int size();
E push(E e);
E peek(); //返回栈顶元素
E pop(); //删除并返回栈顶元素

Python·

1
2
3
4
list
tuple
set
dict

·

FEATURED TAGS
数据科学 算法
FRIENDS