头像

itdef

www.cnblogs.com/itdef




在线 



itdef
2小时前

题目描述

给定一个 n × n 的二维矩阵表示一个图像。

将图像顺时针旋转 90 度。

说明:

你必须在原地旋转图像,这意味着你需要直接修改输入的二维矩阵。
请不要使用另一个矩阵来旋转图像。

示例 1:

给定 matrix = 
[
  [1,2,3],
  [4,5,6],
  [7,8,9]
],

原地旋转输入矩阵,使其变为:
[
  [7,4,1],
  [8,5,2],
  [9,6,3]
]
示例 2:

给定 matrix =
[
  [ 5, 1, 9,11],
  [ 2, 4, 8,10],
  [13, 3, 6, 7],
  [15,14,12,16]
], 

原地旋转输入矩阵,使其变为:
[
  [15,13, 2, 5],
  [14, 3, 4, 1],
  [12, 6, 8, 9],
  [16, 7,10,11]
]


算法1

根据矩阵的转置定义
先将元素 i j 互相交换后
然后以中心为轴 左右交换 即可实现90度旋转

C++ 代码

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        //ele[i][j] 交换
        for (int i = 0; i <matrix.size() ; i++) {
            for (int j = i; j < matrix[i].size(); j++) {
                swap(matrix[i][j], matrix[j][i]);
            }
        }

        //PrintMatrix(matrix);

        //以对称线为中心 左右交换
        for (int i = 0; i < matrix.size(); i++) {
            int l = 0; int r = matrix[i].size() - 1;
            while (l < r) {
                swap(matrix[i][l], matrix[i][r]);
                l++; r--;
            }
        }

        //PrintMatrix(matrix);

        return;
    }
};





itdef
6小时前

题目描述

给定一个数组 candidates 和一个目标数 target ,
找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

说明:

所有数字(包括目标数)都是正整数。
解集不能包含重复的组合。 
示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]
示例 2:

输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
  [1,2,2],
  [5]
]

算法1

预排序
然后同样的使用DFS 尝试每个数字是否要放入答案
注意 类似测试例子中 有多个1 的时候
注意避免出现多个1 ,2 ,5 的答案
这里规避的方案是 在DFS时候,如果不选择当前数字 则直接选择下一个不相同的数字

C++ 代码


class Solution {
public:
    vector<vector<int>> ans;

    void Dfs(vector<int> v, int curridx, const vector<int>& candidates, int target) 
    {
        if (curridx >= candidates.size())  return;
        if (candidates[curridx] > target) return;

        //当前数字不放进
        {
            //如果不选择 则选择与当前数字不同的数组
            int val = candidates[curridx];
            int idx = curridx;
            while (idx < candidates.size() && candidates[idx] == val) {
                idx++;
            }
            Dfs(v, idx, candidates, target);
        }

        //当前数字放进去
        {
            target = target - candidates[curridx];
            v.push_back(candidates[curridx]);
            if (target == 0) {
                ans.push_back(v);
                return;
            }
            Dfs(v, curridx + 1, candidates, target);
        }

    }

    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        if (candidates.empty())  return ans;
        sort(candidates.begin(), candidates.end());
        int idx = 0;
        vector<int> v;
        Dfs(v, idx, candidates, target);

        return ans;
    }
};




itdef
1天前

题目描述

给定一个字符串数组,将字母异位词组合在一起。
字母异位词指字母相同,但排列不同的字符串。

示例:

输入: ["eat", "tea", "tan", "ate", "nat", "bat"]
输出:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]
说明:

所有输入均为小写字母。
不考虑答案输出的顺序。


算法1

单词字母相同但是位置不同 那么就考虑使用字母的哈希来表示这个单词
这里构造一个26位长的字符串 若有字母a 则索引0做一次标记 若有字母z 则索引25做一次标记
最后在使用一个26位长的字符串为关键字的哈希表吧相同的字母记录在一起即可

C++ 代码

class Solution {
public:
    unordered_map<string ,vector<string>> mm;
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        for (const auto& e : strs) {
            string v(26, '0');
            for (const auto&ee : e) {
                int idx = ee - 'a';
                v[idx]++;
            }
            mm[v].push_back(e);
        }
        vector<vector<string>> ans;
        //归类完毕
        for (auto& e: mm) {
            ans.push_back(e.second);
        }

        return ans;
    }
};




itdef
1天前

题目描述

给定两个字符串形式的非负整数 num1 和num2 ,计算它们的和。

 

提示:

num1 和num2 的长度都小于 5100
num1 和num2 都只包含数字 0-9
num1 和num2 都不包含任何前导零
你不能使用任何內建 BigInteger 库, 也不能直接将输入的字符串转换为整数形式
。

算法1

题目思想和链表数相加类似
两个数翻转后计算 注意进位 最后答案再翻转即可

时间复杂度

参考文献

C++ 代码


class Solution {
public:
    string addStrings(string num1, string num2) {
        string ans;
        reverse(num1.begin(), num1.end());
        reverse(num2.begin(), num2.end());

        int p1 = 0; int p2 = 0;
        int extraAdd = 0;
        while (p1 < num1.size() && p2 < num2.size()) {
            int sum = (num1[p1]-'0') + (num2[p2] -'0') + extraAdd;
            extraAdd = sum / 10;
            sum = sum % 10;
            ans += to_string(sum);
            p1++; p2++;
        }

        while (p1 < num1.size()) {
            int sum = (num1[p1] - '0') + extraAdd;
            extraAdd = sum / 10;
            sum = sum % 10;
            ans += to_string(sum);
            p1++;
        }
        while (p2 < num2.size()) {
            int sum = (num2[p2] - '0') + extraAdd;
            extraAdd = sum / 10;
            sum = sum % 10;
            ans += to_string(sum);
            p2++;
        }

        if (extraAdd != 0) {
            ans += to_string(extraAdd);
        }

        reverse(ans.begin(),ans.end());
        return ans;
    }
};




itdef
1天前

题目描述

给定一个按照升序排列的整数数组 nums,和一个目标值 target。
找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target,返回 [-1, -1]。

进阶:

你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗?
 

示例 1:

输入:nums = [5,7,7,8,8,10], target = 8
输出:[3,4]
示例 2:

输入:nums = [5,7,7,8,8,10], target = 6
输出:[-1,-1]
示例 3:

输入:nums = [], target = 0
输出:[-1,-1]
 

提示:

0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums 是一个非递减数组
-109 <= target <= 109


算法1

二分模板 请看Y总的分享
注意边界和特殊情况判断即可

C++ 代码

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        if(nums.empty()) return vector<int>{-1, -1};
        int l = 0; int r = nums.size() - 1;
        while (l < r) {
            int mid = (l + r )>> 1;
            if (nums[mid] >= target) r = mid;
            else l = mid+1;
        }
        int retl = l;
        if (nums[l] != target) return vector<int>{-1, -1};
        l = 0; r = nums.size() - 1;

        while (l < r) {
            int mid = (l + r + 1) >> 1;
            if (nums[mid] <= target) l = mid;
            else r = mid - 1;
        }


        return vector<int>{retl,l};
    }
};






itdef
1天前

题目描述

有一个众所周知的事实,每个彗星的背后都藏着一个UFO。

这些UFO经常到地球来带走一些它们的忠实支持者。

不幸的是,UFO的空间有限,每次星际之旅都只能带走一组支持者。

为了让所有的支持者团队能够提前知道究竟哪组支持者会被带走,UFO们设计了如下方案:

它们给彗星制定一个名称,通过将该名称和某一组支持团队的名称进行比较,
从而判断这一组支持团队是否会被带走。

具体的比较方式如下:

首先,我们将彗星和支持者团队的名称通过以下方式转化为数字:

每个大写字母对应一个整数,A对应1,B对应2,…,Z对应26。
将名称中的每个字母转化为对应数字,再将这些数字相乘,
例如,USACO对应的数字相乘为21 * 19 * 1 * 3 * 15 = 17955。
将得到的乘积 mod 47 就可得到最终数字。
我们将彗星和支持者团队的名称都通过上述方式转化为最终数字后,
如果两个名称对应的数字相同,那么这组支持者就将被带走。

现在,请你编写一个程序,读取彗星和支持者团队的名称,
并根据上述方案判断两个名称是否匹配。

输入格式
第一行,一个由大写字母构成,长度不超过6的字符串,表示彗星的名称。

第二行,一个由大写字母构成,长度不超过6的字符串,表示支持者团队的名称。

输出格式
如果两个名称可以匹配,则输出”GO”,否则输出”STAY”。


样例

输入样例1:
COMETQ
HVNGAT
输出样例1:
GO
输入样例2:
ABSTAR
USACO
输出样例2:
STAY

算法1

模拟 取输入字符串的每个字母与最小字母的差值加1 就是该字母的值
然后乘法的时候注意取模 避免爆长度

时间复杂度

参考文献

C++ 代码

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

#include <iostream>
#include <string>



using namespace std;

int Check(string s)
{
    int sum = 1;
    for (auto& e : s) {
        sum *= (e - 'A'+1);
        sum = sum % 47;
    }

    return sum ;
}


int main()
{
    string A, B;
    cin >> A >> B;

    int a = Check(A);
    int b = Check(B);

    if (a == b) {
        cout << "GO" << endl;
    }
    else {
        cout << "STAY" << endl;
    }

    return 0;
}





新鲜事 原文

itdef
2天前
第一枚勋章,嗨.
图片


新鲜事 原文

itdef
5天前
感谢各位点赞的朋友,考虑我是不是也开个B站解题视频专栏,班门弄斧下,hh



itdef
13天前

之前已经将部分内容写到动态里了,不过想想还是发在分享更加合适

书籍
图论算法理论、实现及应用
acwing基础课群和 算法交流群 我都有上传该文件PDF

1.png
2.png

//====================================================================

然后是一个学习傅里叶的网站 有互动演示 对于理解概念很有帮助
http://www.jezzamon.com/fourier/zh-cn.html
3.png
4.png



新鲜事 原文

itdef
15天前
再次安利下这本以题讲图论的书籍
图片 图片 图片 图片