【优选算法题练习】day9

摘星

发布于 2023-10-15 15:55:09

1040

发布于 2023-10-15 15:55:09

文章被收录于专栏：C/C++学习

一、DP35 【模板】二维前缀和

1.题目简介

DP35 【模板】二维前缀和

题目来源于牛客网，可通过链接进行练习。

2.解题思路

3.代码

#include <iostream>
using namespace std;
#include<vector>
int main() {
    int n, m, q;
    while (cin >> n >> m >> q) {
        vector<vector<long long>> nums(n + 1, vector<long long> (m + 1));
        for(int i = 1;i <= n; ++i)
        {
            for(int j = 1;j <= m; ++j)
            {
                cin>>nums[i][j];
            }
        }
        vector<vector<long long>> dp(n + 1, vector<long long> (m + 1));
        for(int i = 1;i <= n; ++i)
        {
            for(int j = 1;j <= m; ++j)
            {
                dp[i][j] = nums[i][j] + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];
            }
        }
        while(q--)
        {
            int x1 = 0, y1 = 0, x2 = 0, y2 = 0;
            cin >> x1 >> y1 >> x2 >> y2;
            cout<<dp[x2][y2] - (dp[x1 - 1][y2] + dp[x2][y1 - 1] - dp[x1 - 1][y1 - 1])<<endl;
        }
    }
    return 0;
}

4.运行结果

二、面试题 01.01. 判定字符是否唯一

1.题目简介

面试题 01.01. 判定字符是否唯一

题目来源于Leetcode，可通过链接练习。

2.解题思路

3.代码

class Solution {
public:
    bool isUnique(string astr) {
        //用一个整数来充当哈希表
        int n = 0;
        for(auto& e : astr)
        {
            int t = e - 'a';
            if((n & (1 << t)) == 0)
            {
                n ^= (1 << t);
            }
            else
            {
                return false;
            }
        }
        return true;
    }
};

4.运行结果

三、724. 寻找数组的中心下标

1.题目简介

724. 寻找数组的中心下标

题目来源于Leetcode，可通过链接练习。

2.解题思路

3.代码

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        vector<int> lsum(nums.size());//左边的前缀和
        vector<int> rsum(nums.size());//右边的前缀和
        for(int i = 1;i < nums.size(); ++i)
        {
            lsum[i] = lsum[i - 1] + nums[i - 1];
        }
        for(int i = nums.size() - 2;i >= 0; --i)
        {
            rsum[i] = rsum[i + 1] + nums[i + 1];
        }
        for(int i = 0;i < nums.size(); ++i)
        {
            if(lsum[i] == rsum[i]) return i;
        }
        return -1;
    }
};