算法题目复习（0909-0917）

1. 连续子序列和

pdd的算法题，根本不记得怎么做

给一个数组，有正数和负数，算出连续子序列的和最大为多少

int maxSubArraySum(vector<int>& nums) {
    int maxSoFar = nums[0];
    int maxEndingHere = nums[0];

    for (size_t i = 1; i < nums.size(); ++i) {
        maxEndingHere = max(nums[i], maxEndingHere + nums[i]);
        maxSoFar = max(maxSoFar, maxEndingHere);
    }

    return maxSoFar;
}

int main() {
    std::vector<int> nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    int maxSum = maxSubArraySum(nums);
    std::cout << "Maximum subarray sum is " << maxSum << std::endl;
    return 0;
}

Kadane's算法

太神了。。主要灵魂是：要么继续当前子数组，要么从当前位置开始一个新的数组（就是说如果过去的数加上i<i,就没必要用过去的数了）

2. 给一个字符串，只包含A和B两种字符，判断这个数组包含AB数量相等的连续子序列最长是多少，应该怎么做用c++

用一个哈希表记录前缀和

主要我做的时候想到了前缀和，但是不知道怎么找一个数组两个相等的数之差最大是多少

它的算法就是用哈希表存下来（idx，val），如果下一个val在哈希表中存在，就更新idx之差最大。这样On就能算了。

3 最长上升子序列

没想到这题用动态规划都得n平方，好难

思路就是dp[i] 是以i结尾的，前面任意选的子序列，dp[j]是以j结尾的子序列,要从j转移到i，就意味着nums[i]肯定大于nums[j], 那就找比i小的所有j里，dp[j]最大的进行转移，+1

    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n+1);
        dp[0] = 1;
        for(int i =1;i<n;i++){
            int maxj = 0;
            for(int j =0;j<i;j++){
                if(nums[j] < nums[i])
                    maxj = max(maxj, dp[j]);
            }
            dp[i] = maxj+1;
        }
        int res = 0;
        for(int i =0;i<n;i++){
            res = max(res, dp[i]);
        }
        return res;

4. 求质数

主要是求最小公约数，这个循环的话循环到sqrt(x)就行

或者先弄一个质数列表，这个列表得到的方式是:埃拉托斯特尼筛法

跟我想的差不多，用一个列表保存

还有！整除不要用/，用//

5. 搜索二维矩阵二

    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size(), n = matrix[0].size();
        int x = 0, y = n-1;
        while(x<m && y >= 0){
            if(matrix[x][y] == target){
                return true;
            }else if(matrix[x][y] > target){
                y --;
            }else{
                x++;
            }
        }
        return false;
    }

这题是z字形查找，就是从右上角的点开始查找，每次能排除一行或者一列

6. 图论的题

一直没搞清什么最短路那几个问题：

给一堆点，找到联通所有点的最短路

prim算法：找到n-1条边。每次选距离生成树最近的节点，将该点加入生成树，更新非生成树节点到生成树的距离。（初始化一个minDist数组，用来记录每个节点到生成树的最小距离）

初始化为每个点到第一个点的最小距离，然后迭代，它的重点在于选点，比较适合稠密图，复杂度是on平方

Krustral算法：是我自己想的那种并查集思路。对所有边按权值从大到小排列，判断选中的边的两个端点是否在一个并查集内，如果不在，就加入到一个。

djistra算法 

7. 随机链表的复制

就是给一个链表深拷贝为另一个链表，其中每个节点都有一个随机指针，指向任意一个节点

做法就是：定义两个old->new，new->old节点的映射map，第一次遍历创建新节点，并维护映射。第二次遍历根据老节点的random找到对应的新节点来设置新节点的random。

 Node* copyRandomList(Node* head) {
        unordered_map<Node*,Node*> mp;
        Node * head2 = new Node(0);
        Node * cur2 = head2;
        Node * cur = head;
        while(cur!=nullptr){
            cur2->next = new Node (cur->val);
            cur2 =cur2->next;
            mp[cur] = cur2;
            cur = cur->next;
        } 
        cur = head, cur2 = head2->next;
        while(cur!=nullptr){
            cur2->random = mp[cur->random];
            cur = cur->next;
            cur2 = cur2->next;
        }
        return head2->next;
    }