头像

itdef

https://space.bilibili.com/18508846




在线 



itdef
3小时前

地址 https://www.acwing.com/problem/content/description/139/

有 N 片雪花,每片雪花由六个角组成,每个角都有长度。

第 i 片雪花六个角的长度从某个角开始顺时针依次记为 ai,1,ai,2,…,ai,6。

因为雪花的形状是封闭的环形,所以从任何一个角开始顺时针或逆时针往后记录长度,
得到的六元组都代表形状相同的雪花。

例如 ai,1,ai,2,…,ai,6 和 ai,2,ai,3,…,ai,6,ai,1 就是形状相同的雪花。

ai,1,ai,2,…,ai,6 和 ai,6,ai,5,…,ai,1 也是形状相同的雪花。

我们称两片雪花形状相同,当且仅当它们各自从某一角开始顺时针或逆时针记录长度,能得到两个相同的六元组。

求这 N 片雪花中是否存在两片形状相同的雪花。

输入格式
第一行输入一个整数 N,代表雪花的数量。

接下来 N 行,每行描述一片雪花。

每行包含 6 个整数,分别代表雪花的六个角的长度
(这六个数即为从雪花的随机一个角顺时针或逆时针记录长度得到)。

同行数值之间,用空格隔开。

输出格式
如果不存在两片形状相同的雪花,则输出:

No two snowflakes are alike.

如果存在两片形状相同的雪花,则输出:

Twin snowflakes found.

数据范围
1≤N≤100000,
0≤ai,j<10000000
输入样例:
2
1 2 3 4 5 6
4 3 2 1 6 5
输出样例:
Twin snowflakes found.

解答 使用哈希记录每个雪花的特征 便于比对相同雪花
关键在于选择合适的哈希函数
这里使用的是 将6片雪花的值的积与和相加 再%一个质数,这样相同6片雪花的值必然会得出同一个结果,然后我们再进行比对

优化了stl数据结构 改为数组
从cin 优化成scanf
poj原题也可以AC了
http://poj.org/problem?id=3349

// 21342343254.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <stdio.h>
#include <map>
#include <vector>
#include <memory.h>

using namespace std;

/*
输出格式
如果不存在两片形状相同的雪花,则输出:

No two snowflakes are alike.

如果存在两片形状相同的雪花,则输出:

Twin snowflakes found.

数据范围
1≤N≤100000,
0≤ai,j<10000000
输入样例:
2
1 2 3 4 5 6
4 3 2 1 6 5
输出样例:
Twin snowflakes found.
*/


int n;

//map<long long, vector<int> > mm;

int mm[100015][6];  int p = 1e5+13;

int  GetHash(const int arr[6]) {
    long long ret = 1;
    for (int i = 0; i < 6; i++) {
        ret *= arr[i];
        ret %=p;
    }

    for (int i = 0; i < 6; i++) {
        ret += arr[i];
        ret %=p;
    }

    return ret;
}

bool check(const int a[6], const int b[6])      
{
    for (int i = 0; i < 6; i++)
        for (int j = 0; j < 6; j++)
        {
        //正序 逆序 判断两次
            bool flag = 1;
            for (int k = 0; k < 6; k++)        
                if (a[(i + k) % 6] != b[(j + k) % 6]) flag = 0;
            if (flag) return 1;
            flag = 1;
            for (int k = 0; k < 6; k++)
                if (a[(i + k) % 6] != b[(j - k + 6) % 6]) flag = 0;
            if (flag) return 1;
        }
    return 0;
}



int main()
{
    scanf("%d",&n);  
    int arr[6];
    memset(mm,-1,sizeof mm);

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 6; j++) {
            scanf("%d",&arr[j]);
        }

        int  hashV = GetHash(arr);
        if (mm[hashV][0] != -1) {
            if (check(mm[hashV], arr) == 1) {
                cout << "Twin snowflakes found." << endl;
                return 0;
            }
        }

        memcpy(mm[hashV] , arr, sizeof(arr[0])*6);

    }

    cout << "No two snowflakes are alike." << endl;
    return 0;
}

我的视频题解空间




itdef
5天前
编写一个高效的算法来判断 m x n 矩阵中,是否存在一个目标值。该矩阵具有如下特性:
每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。

示例 1:

1111.jpg

输入:matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出:true


示例 2:

222.jpg

输入:matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出:false

提示:
m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-104 <= matrix[i][j], target <= 104

解答
二维的一个二分搜索的题目
注意条件
每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。

那么遍历每行的开头结尾元素 判断target是否可能存在该行,可能则进行二分查找

class Solution {
public:
    bool Check(vector<vector<int>>& matrix, int target,int line){
        int l = 0; int r = matrix[0].size()-1;
        while(l<r){
            int mid = (l+r )>> 1;
            if(matrix[line][mid] >= target ) r =mid;
            else l = mid+1;
        }

        return (matrix[line][l] == target );
    }

    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int x = matrix.size(); int y = matrix[0].size();
        for(int i = 0; i < x;i++){
            if(matrix[i][0] == target || matrix[i][y-1] == target) return true;
            if(matrix[i][0] < target && matrix[i][y-1]>target ){
                //二分搜索
                if(Check(matrix,target,i)) return true;
            }else if(matrix[i][0] > target){break;}
        }

        return false;
    }
};

我的视频题解空间



活动打卡代码 AcWing 435. 传球游戏

itdef
7天前
#include <iostream>

using namespace std;

const int N = 35;

int n, m;
int f[N][N];

int main()
{
    cin >> n >> m;

    f[0][0] = 1;
    for (int i = 1; i <= m; i ++ )
        for (int j = 0; j < n; j ++ )
            f[i][j] = f[i - 1][(j + n - 1) % n] + f[i - 1][(j + 1) % n];

    cout << f[m][0] << endl;

    return 0;
}




活动打卡代码 LeetCode 1473. 粉刷房子 III

itdef
7天前
class Solution {
public:
    int minCost(vector<int>& houses, vector<vector<int>>& cost, int m, int n, int target) {
        const int INF = 0x3f3f3f3f;
        const int M = 110;
        const int N = 30;

        int f[M][N], g[M][N];

        memset(f, 0x3f, sizeof(f));
        memset(g, 0x3f, sizeof(g));

        for (int k = 1; k <= n; k++)
            f[0][k] = g[0][k] = 0;

        for (int i = 1; i <= m; i++)
            for (int j = min(i, target); j >= 1; j--) {
                if (houses[i - 1] > 0) {
                    int c = houses[i - 1];
                    f[j][c] = min(f[j][c], g[j - 1][c]);

                    for (int k = 1; k <= n; k++)
                        if (k != c)
                            f[j][k] = INF;

                } else {
                    for (int k = 1; k <= n; k++)
                        f[j][k] = min(f[j][k], g[j - 1][k]) + cost[i - 1][k - 1];
                }

                int m1 = INF, m2 = INF;
                for (int k = 1; k <= n; k++)
                    if (m1 > f[j][k]) {
                        m2 = m1;
                        m1 = f[j][k];
                    } else if (m2 > f[j][k])
                        m2 = f[j][k];

                if (m1 == m2) {
                    for (int k = 1; k <= n; k++)
                        g[j][k] = m1;
                } else {
                    for (int k = 1; k <= n; k++)
                        if (f[j][k] == m1) g[j][k] = m2;
                        else g[j][k] = m1;
                }

                for (int k = 1; k <= n; k++)
                    f[0][k] = g[0][k] = INF;
            }

        int ans = INF;
        for (int k = 1; k <= n; k++)
            ans = min(ans, f[target][k]);

        if (ans == INF)
            ans = -1;

        return ans;
    }
};




活动打卡代码 AcWing 78. 左旋转字符串

itdef
7天前
class Solution {
public:
    string leftRotateString(string str, int n) {
        reverse(str.begin(), str.end());
        reverse(str.begin(), str.end() - n);
        reverse(str.end() - n, str.end());
        return str;
    }
};


活动打卡代码 LeetCode 7. 整数反转

itdef
7天前
class Solution {
public:
    int reverse(int x) {
        int res = 0;
        while (x) {
            if (x > 0 && res > (INT_MAX - x % 10) / 10) return 0;
            if (x < 0 && res < (INT_MIN - x % 10) / 10) return 0;
            res = res * 10 + x % 10;
            x /= 10;
        }
        return res;
    }
};




活动打卡代码 AcWing 1540. 主导颜色

itdef
8天前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>

using namespace std;

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    unordered_map<int, int> hash;

    for (int i = 0; i < n * m; i ++ )
    {
        int x;
        scanf("%d", &x);
        if ( ++ hash[x] * 2 > n * m)
        {
            printf("%d\n", x);
            break;
        }
    }
    return 0;
}




活动打卡代码 LeetCode 554. 砖墙

itdef
8天前
class Solution {
public:
    int leastBricks(vector<vector<int>>& wall) {
        unordered_map<int, int> cnt;
        for (auto& line: wall) {
            for (int i = 0, s = 0; i + 1 < line.size(); i ++ ) {
                s += line[i];
                cnt[s] ++ ;
            }
        }
        int res = 0;
        for (auto [k, v]: cnt) res = max(res, v);
        return wall.size() - res;
    }
};



活动打卡代码 AcWing 53. 最小的k个数

itdef
8天前
class Solution {
public:
    vector<int> getLeastNumbers_Solution(vector<int> input, int k) {
        priority_queue<int> heap;
        for (auto x: input) {
            heap.push(x);
            if (heap.size() > k) heap.pop();
        }
        vector<int> res;
        while (heap.size()) res.push_back(heap.top()), heap.pop();
        reverse(res.begin(), res.end());
        return res;
    }
};



活动打卡代码 AcWing 53. 最小的k个数

itdef
8天前
class Solution {
public:
    vector<int> getLeastNumbers_Solution(vector<int> input, int k) {
        priority_queue<int> heap;
        for (auto x: input) {
            heap.push(x);
            if (heap.size() > k) heap.pop();
        }
        vector<int> res;
        while (heap.size()) res.push_back(heap.top()), heap.pop();
        reverse(res.begin(), res.end());
        return res;
    }
};