头像

Newton

神秘的东方




离线:4个月前


最近来访(10)
用户头像
Seeker.
用户头像
YanW
用户头像
4_3
用户头像
风之羁绊
用户头像
Tsuki_suki
用户头像
R_U_OK
用户头像
齐天大仙


Newton
2021-04-20 21:23

感觉智商受到了侮辱… 用hash来做,上来就是map。结果复杂不说,还四处报错。

根据题意,可以确定最大的数组范围。
然后可以直接遍历整个数组来找最大值,同时得到的结果也是从小到大的序号。

#include<iostream>
#include<algorithm>
using namespace std;

const int N=10010;
int s[N], n;

int main()
{
    cin >> n;
    int x;
    while(n--)
    {
        cin >> x;
        s[x]++;
    }

    int res=0;
    for(int i=1; i<N; i++)
    {
        if(s[res]<s[i])
            res=i;
    }
    cout << res << endl;
    return 0;
}



Newton
2021-04-19 22:19

DP

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int n = text1.size(), m = text2.size(); // text是从0开始
        vector<vector<int>> f(n+1, vector<int>(m+1));  // 状态我们从1开始
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=m; j++)
            {
                // 由于i不存在,j不存在,包含在f[i-1][j]和f[i][j-1]中,但我们求最大值,所以可以忽略,直接求max就行了
                f[i][j] = max(f[i-1][j], f[i][j-1]);  // i不存在,j存在 。  和 i存在, j不存在的情况
                if(text1[i-1] == text2[j-1]){ // 若当前i和j均存在,则在子序列里, 所以就看f[i-1][j-1] 加上本身 1
                    f[i][j] = max(f[i][j], f[i-1][j-1]+1);
                }
            }
        }
        return f[n][m];
    }
};


活动打卡代码 AcWing 90. 64位整数乘法

Newton
2021-04-16 18:50

快速幂运算的拓展。

#include<iostream>
using namespace std;
typedef long long ll;

ll calcuate(ll a, ll b, ll p)
{
    ll res=0;
    while(b)
    {
        if(b & 1)
            res =  (res + a) % p;
        a = (a*2) % p;
        b >>= 1;
    }
    return res % p;
}

int main()
{
    ll a, b, p;
    cin >> a >> b >> p;
    ll res = calcuate(a, b, p);
    cout << res << endl;
    return 0;
}



Newton
2021-04-14 23:06

1、取二进制n中的第k位: n >> k & 1
2、二进制转10进制。 原始值左移一位,并加上当前位数。

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {  // 最高位向左移,最后得到的就是十进制。 即 res << 1.   取n中第k位 即为 n>>k & 1
        uint32_t res = 0;
        for(int i = 0; i<32; i++) // 翻转后,高位从0开始
            res = (res << 1) + (n >> i & 1); 
        return res;
    }
};


活动打卡代码 AcWing 592. 雨

Newton
2021-04-12 21:35

CV, ORL

#include<queue>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int N = 55; //矩阵边长
int n, m;
int h[N][N]; // 高度
int dist[N][N]; // dijstra 需要一个全局的dist
bool st[N][N]; // 判常数组
struct Node{ // 矩阵中每个点的值
    int x, y, d; //坐标 和 值
    // 堆里面需要所有元素进行排序
    bool operator < (const Node& t) const{
        return d > t.d; // 堆默认是大根堆,这题最短路,变成小根堆。所以 > 
    }
};

int main()
{
    int T;
    cin >> T; // 测试数据数量 
    for(int C=1; C<=T; C++) // 每个测试数据
    {
        cin >> n >> m;
        for(int i=1; i<=n; i++)
            for(int j=1; j<=m; j++)
                cin >> h[i][j]; //每个元素的高度
        // 初始化
        memset(dist, 0x3f, sizeof dist); // 因为求最短路,所以先初始化为正无穷
        memset(st, 0, sizeof st);
        priority_queue<Node> heap;

        // 把周围一圈的点加入堆里
        for(int i=1; i<=n; i++) 
        {
            heap.push({i, 1, h[i][1]}); // 先最左侧,高度为h[i][1]
            dist[i][1] = h[i][1];
            heap.push({i, m, h[i][m]}); // 最右侧加进来
            dist[i][m] = h[i][m];
        }
        for(int i=2; i<m; i++) // 上下两行加进来
        {
            heap.push({1, i, h[1][i]});
            dist[1][i] = h[1][i];
            heap.push({n, i, h[n][i]});
            dist[n][i] = h[n][i];
        }

        int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

        int res = 0; //记录最终的储水量
        while(heap.size()) //堆不空
        {
            auto t = heap.top();
            heap.pop();

            if(st[t.x][t.y]) continue; // 若该点搜过了就继续
            st[t.x][t.y] = true; // 标记为它已经更新过其它点了
            res += t.d - h[t.x][t.y];  // 格子的最终高度 - 其初始身的高度 即为 该格子储水量

            // 枚举当前点的临边,去更新四条临边
            for(int i=0; i<4; i++)
            {
                int x = t.x + dx[i], y=t.y + dy[i];
                if(x >= 1 && x <=n && y>=1 && y<=m)
                {
                    if(dist[x][y] > max(t.d, h[x][y])) // 如果能更新这四条临边
                    {
                        dist[x][y] = max(t.d, h[x][y]);
                        heap.push({x, y, dist[x][y]});
                    }
                }
            }
        }
        printf("Case #%d: %d\n", C, res);
    }
    return 0;
}



Newton
2021-04-12 20:22

对于每个位置i,去判断它左边的最大值是多少,然后再判断它右边的最大值是多少。 然后取两者最小的一个,即为最终高度。最后该位置i的储水量,即为最终高度 减去 它本身的高度

所以做法:

1、从左向右遍历,求出每个位置的左边最高高度left[i]. 即left为最高高度, 所以求left[i-1]与当前位置高度height[i]比较即可。
2、同理,从右向左求得每个位置的最高高度right[i]。
3、答案即为 res+= min(left[i], right[i]) - height[i]
class Solution {
public:
    int trap(vector<int>& height) {
        if (height.empty())
            return 0;
        int n = height.size();
        vector<int> left(n), right(n);
        left[0] = height[0];
        right[n-1] = height[n-1];
        for(int i=1; i<n; i++)
            left[i] = max(left[i-1], height[i]);
        for(int i=n-2; i>=0; i--)
            right[i] = max(right[i+1], height[i]);
        int res = 0;
        for(int i=0; i<n; i++)
        {
            res += min(left[i], right[i]) - height[i];
        }
        return res;
    }
};


活动打卡代码 AcWing 1381. 阶乘

Newton
2021-04-11 23:40

寒假做过的呀 QAQ ,还是不会,而且忘了做过。。

找非0,首先把0给找完,即对每个因子分解为 2^a、 5^b、 其他部分_1。

对其他部分_1计算非0的数字。

最后k=min(a, b); 再让其他部分将剩下的2或者5进行累乘,继续算非0数字,即得到正确结果

#include<iostream>
#include<algorithm>
using namespace std;
int n;
int main()
{
    cin >> n;
    int a=0, b=0, res=1; // res从1开始即阶乘从1开始乘
    for(int i=1; i<=n; i++) // 阶乘是从1开始乘的
    {
        int x = i; // 将每个因子都分解为2^a * 5^b * 其他部分
        while(x%2==0) // 因子分解为对应2的个数
        {
            x/=2;
            a++;
        }
        while(x%5==0) // 2分解完后剩余式子分解为5的个数
        {
            x/=5;
            b++;
        }
        // 其他部分即为非0部分,需要一直累乘即为阶乘。 且我们需要记录最右侧的非0数字,则%10即可得到非0。
        res = (res * x) % 10;
    }
    // 由于a, b不一定相等,所以最后一定会存在一个多出来的,需要进一步乘,并得到最后一位的数字
    int k = min(a, b);
    for(int i=0; i<a-k; i++)
        res = (res * 2) % 10;
    for(int i=0; i<b-k; i++)
        res = (res * 5) % 10;
    cout << res << endl;
    return 0;
}



Newton
2021-04-11 23:04
class Solution {
public:
    bool searchArray(vector<vector<int>> array, int target) {
        // 由题意可知,右上角的值x为突破口
        // 若 x > target,则x所在列均不满足要求,即往前面一列找。
        // 若 x < target,则x所在行均不满足要求,即往下面一行找。
        // 若 x = target,则返回 true
        if(array.empty() || array[0].empty()) return false;
        int i = 0, j = array[0].size() - 1;
        while(i<array.size() && j>=0)
        {
            int x = array[i][j];
            if(x == target) return true;
            else if(x > target) j--;
            else i++;
        }
        return false;
    }
};



Newton
2021-04-11 22:55

直接遍历。

class Solution {
public:
    bool searchArray(vector<vector<int>> array, int target) {
        for(int i=0; i<array.size(); i++)
        {
            for(int j=0; j<array[i].size(); j++)
            {
                if(array[i][j] == target)
                {
                    return true;
                }
            }
        }
        return false;
    }
};


活动打卡代码 AcWing 77. 翻转单词顺序

Newton
2021-04-11 22:28

分成两步,先翻转整个的字符串,再单独翻转每个单词。

class Solution {
public:
    string reverseWords(string s) {
        reverse(s.begin(), s.end()); // 先翻转整个字符串
        for(int i=0; i<s.size(); i++)
        {
            int j = i+1;
            while(j<s.size() && s[j] != ' ') j++; // j为从单词头到单位尾的空格位置
            reverse(s.begin() + i, s.begin() + j); // 翻转单个单词。  注意是s.begin() + j
            i = j; // 每翻转完后, 换下个单词
        }
        return s;
    }
};