头像

itdef

https://space.bilibili.com/18508846 && http://www.cnblogs.com/itdef




离线:1分钟前


最近来访(317)
用户头像
ssuunn
用户头像
辉小歌
用户头像
emmmmm_4
用户头像
anji
用户头像
simonhan
用户头像
WUT_CS2004_SJQ
用户头像
Uncle
用户头像
Anoxia_3
用户头像
skydegree
用户头像
wei_good
用户头像
星逐月丶
用户头像
逸兴遄飞
用户头像
david.song
用户头像
直行格子
用户头像
acw_milo
用户头像
香香小马
用户头像
虹林清溪
用户头像
白墙
用户头像
snkz5qing
用户头像
猪啊猪


itdef
2天前

地址 https://leetcode-cn.com/problems/missing-number/

给定一个包含 [0, n] 中 n 个数的数组 nums ,找出 [0, n] 这个范围内没有出现在数组中的那个数。

进阶:
你能否实现线性时间复杂度、仅使用额外常数空间的算法解决此问题?

示例 1:
输入:nums = [3,0,1]
输出:2
解释:n = 3,因为有 3 个数字,所以所有的数字都在范围 [0,3] 内。
2 是丢失的数字,因为它没有出现在 nums 中。

示例 2:
输入:nums = [0,1]
输出:2
解释:n = 2,因为有 2 个数字,所以所有的数字都在范围 [0,2] 内。
2 是丢失的数字,因为它没有出现在 nums 中。

示例 3:
输入:nums = [9,6,4,2,3,5,7,0,1]
输出:8
解释:n = 9,因为有 9 个数字,所以所有的数字都在范围 [0,9] 内。
8 是丢失的数字,因为它没有出现在 nums 中。

示例 4:
输入:nums = [0]
输出:1
解释:n = 1,因为有 1 个数字,所以所有的数字都在范围 [0,1] 内。
1 是丢失的数字,因为它没有出现在 nums 中。


提示:
n == nums.length
1 <= n <= 104
0 <= nums[i] <= n
nums 中的所有数字都 独一无二

解答
使用异或的属性
0和某一个数异或等于他自己, 再次异或后就会重新置零
那么我们将0 和从1到n的所有数异或
然后再和nums中所有的数字异或 最后有一个数没有异或两次。就是我们需要的答案

0^a^b^c^d^a^b^d = c
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int k = 0;
        for(int i = 0; i <= nums.size() ;i++){
            k ^= i;
        }
        for(int i = 0; i < nums.size();i++){
            k ^= nums[i];
        }
        return k;
    }
};

我的视频题解空间




itdef
2天前

地址 https://leetcode-cn.com/problems/first-bad-version/

你是产品经理,目前正在带领一个团队开发新的产品。不幸的是,你的产品的最新版本没有通过质量检测。
由于每个版本都是基于之前的版本开发的,所以错误的版本之后的所有版本都是错的。
假设你有 n 个版本 [1, 2, ..., n],你想找出导致之后所有版本出错的第一个错误的版本。
你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。
实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

示例 1:
输入:n = 5, bad = 4
输出:4
解释:
调用 isBadVersion(3) -> false 
调用 isBadVersion(5) -> true 
调用 isBadVersion(4) -> true
所以,4 是第一个错误的版本。

示例 2:
输入:n = 1, bad = 1
输出:1


提示:
1 <= bad <= n <= 231 - 1

解答
二分模板
erfen.png
每次尝试版本区间的中间索引, 得到是否为错误版本,逐步缩小区间,得到正确答案。

// The API isBadVersion is defined for you.
// bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
        int l = 1; int r = n;
        while(l<r){
            int mid = ((long long )l+r) >> 1;
            if(isBadVersion(mid)) r = mid;
            else l = mid+1;
        }      

        return l;
    }
};

我的视频题解空间




itdef
3天前

地址 https://vjudge.net/problem/HDU-1166

C国的死对头A国这段时间正在进行军事演习,所以C国间谍头子Derek和他手下Tidy又开始忙乎了。
A国在海岸线沿直线布置了N个工兵营地,Derek和Tidy的任务就是要监视这些工兵营地的活动情况。
由于采取了某种先进的监测手段,所以每个工兵营地的人数C国都掌握的一清二楚,
每个工兵营地的人数都有可能发生变动,可能增加或减少若干人手,但这些都逃不过C国的监视。
中央情报局要研究敌人究竟演习什么战术,所以Tidy要随时向Derek汇报某一段连续的工兵营地一共有多少人,
例如Derek问:“Tidy,马上汇报第3个营地到第10个营地共有多少人!”Tidy就要马上开始计算这一段的总人数并汇报。
但敌兵营地的人数经常变动,而Derek每次询问的段都不一样,所以Tidy不得不每次都一个一个营地的去数,
很快就精疲力尽了,
Derek对Tidy的计算速度越来越不满:"你个死肥仔,算得这么慢,我炒你鱿鱼!”
Tidy想:“你自己来算算看,这可真是一项累人的工作!我恨不得你炒我鱿鱼呢!”
无奈之下,Tidy只好打电话向计算机专家Windbreaker求救,
Windbreaker说:“死肥仔,叫你平时做多点acm题和看多点算法书,现在尝到苦果了吧!”
Tidy说:"我知错了。。。"但Windbreaker已经挂掉电话了。Tidy很苦恼,这么算他真的会崩溃的,
聪明的读者,你能写个程序帮他完成这项工作吗?不过如果你的程序效率不够高的话,
Tidy还是会受到Derek的责骂的.
Input
第一行一个整数T,表示有T组数据。
每组数据第一行一个正整数N(N<=50000),表示敌人有N个工兵营地,
接下来有N个正整数,第i个正整数ai代表第i个工兵营地里开始时有ai个人(1<=ai<=50)。
接下来每行有一条命令,命令有4种形式:
(1) Add i j,i和j为正整数,表示第i个营地增加j个人(j不超过30)
(2)Sub i j ,i和j为正整数,表示第i个营地减少j个人(j不超过30);
(3)Query i j ,i和j为正整数,i<=j,表示询问第i到第j个营地的总人数;
(4)End 表示结束,这条命令在每组数据最后出现;
每组数据最多有40000条命令
Output
对第i组数据,首先输出“Case i:”和回车,
对于每个Query询问,输出一个整数并回车,表示询问的段中的总人数,这个数保持在int以内。
Sample Input
1
10
1 2 3 4 5 6 7 8 9 10
Query 1 3
Add 3 6
Query 2 7
Sub 10 2
Add 6 3
Query 3 10
End 
Sample Output
Case 1:
6
33
59

解法
线段树模板
segmentTree.png


#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>

using namespace std;

const int N = 50010;
struct Node {
    int l; int r;
    int sum;
}t[4*N];
int a[N];

void build(int p, int l, int r) {
    t[p].l = l; t[p].r = r;
    if (l == r) { t[p].sum = a[l]; return; }

    int mid = (l + r) >> 1;
    build(p * 2, l, mid);
    build(p * 2 + 1, mid + 1, r);
    t[p].sum += t[p * 2].sum + t[p * 2 + 1].sum;
}

int query(int p, int l, int r) {
    if (l <= t[p].l && r >= t[p].r) { return t[p].sum; }
    int mid = (t[p].l + t[p].r) >> 1;
    int ret = 0;
    if (l <= mid) { ret += query(p * 2, l, r); }
    if (r > mid) { ret += query(p*2+1,l,r); }
    return ret;
}

void update(int p, int x, int v) {
    if (t[p].l == t[p].r) { t[p].sum += v; return; }
    int mid = (t[p].l + t[p].r) >> 1;
    if (x <= mid) { update(p * 2, x, v); }
    else { update(p*2+1,x,v); }
    t[p].sum = t[p*2].sum + t[p * 2 + 1].sum;
}


int loop;
int n;

int main()
{
    scanf("%d",&loop);
    int idx = 0;
    while (loop--) {
        cin >> n;
        memset(a,0,sizeof a);
        memset(t,0,sizeof t);
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
        }
        build(1,1,n);
        string s;int a; int b;
        idx++;
        printf("Case %d:\n",idx);
        while(1){
            char s[50];
            scanf("%s",s);
            if (s[0] == 'Q') {
                scanf("%d%d",&a,&b);
                printf("%d\n", query(1, a, b));
            }
            else if (s[0] == 'A') {
                scanf("%d%d", &a, &b);
                update(1, a, b);
            }
            else if (s[0] == 'S') {
                scanf("%d%d", &a, &b);
                update(1, a, -b);
            }
            else if (s[0] == 'E') {
                //本轮结束 跳出
                break;
            }
        }
    }

    return 0;
}

我的视频题解空间




itdef
4天前

这里分享下我学习KMP的心得

KMP算法是三位计算机科学家发明的字符串匹配算法。
从暴力逐个比对到最大公共前后缀优化
kmp1.png

next数组
kmp2.png
假设已经得到next数组,使用数组进行字符串匹配的流程如上,代码如下

const int N = 100010, M = 1000010;
int n, m;
int ne[N];
char s[M], p[N];
{

    for (int i = 1, j = 0; i <= m; i ++ )
    {
        while (j && s[i] != p[j + 1]) j = ne[j];
        if (s[i] == p[j + 1]) j ++ ;
        if (j == n)
        {
            //ok  得到答案
            return 0;
        }
    }
}

//==================================================================
下面我们来进行next数组的计算
Next数组就是计算某个坐标之前的字符串的能匹配的前缀与后缀的长度
本质上就是自己和自己的匹配
kmp3.png

int n, m;
int ne[N];
char s[M], p[N];
for (int i = 2, j = 0; i <= n; i ++ )
{
   while (j && p[i] != p[j + 1]) j = ne[j];
   if (p[i] == p[j + 1]) j ++ ;
   ne[i] = j;
}

本题的解答代码则呼之欲出

#include <iostream>

using namespace std;

const int N = 100010, M = 1000010;

int n, m;
int ne[N];
char s[M], p[N];

int main()
{
    cin >> n >> p + 1 >> m >> s + 1;

    for (int i = 2, j = 0; i <= n; i ++ )
    {
        while (j && p[i] != p[j + 1]) j = ne[j];
        if (p[i] == p[j + 1]) j ++ ;
        ne[i] = j;
    }

    for (int i = 1, j = 0; i <= m; i ++ )
    {
        while (j && s[i] != p[j + 1]) j = ne[j];
        if (s[i] == p[j + 1]) j ++ ;
        if (j == n)
        {
            printf("%d ", i - n);
            j = ne[j];
        }
    }

    return 0;
}

我的视频题解空间




itdef
8天前

这里分享下我学习KMP的心得
1.png

2.png
假设已经得到next数组,使用数组进行字符串匹配的流程如上代码如下

const int N = 100010, M = 1000010;
int n, m;
int ne[N];
char s[M], p[N];
{

    for (int i = 1, j = 0; i <= m; i ++ )
    {
        while (j && s[i] != p[j + 1]) j = ne[j];
        if (s[i] == p[j + 1]) j ++ ;
        if (j == n)
        {
            //ok  得到答案
            return 0;
        }
    }
}

//==================================================================
下面我们来进行next数组的计算
Next数组就是计算某个坐标之前的字符串的能匹配的前缀与后缀的长度
本质上就是自己和自己的匹配
3.png

int n, m;
int ne[N];
char s[M], p[N];
for (int i = 2, j = 0; i <= n; i ++ )
{
   while (j && p[i] != p[j + 1]) j = ne[j];
   if (p[i] == p[j + 1]) j ++ ;
   ne[i] = j;
}

我的视频题解空间




itdef
15天前

地址 https://leetcode-cn.com/problems/search-a-2d-matrix-ii/

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性:
每行的元素从左到右升序排列。
每列的元素从上到下升序排列。

示例 1:

111.jpg

输入:matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], 
target = 5
输出:true

示例 2:

222.jpg

输入:matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], 
target = 20
输出:false


提示:
m == matrix.length
n == matrix[i].length
1 <= n, m <= 300
-109 <= matrix[i][j] <= 109
每行的所有元素从左到右升序排列
每列的所有元素从上到下升序排列
-109 <= target <= 109

解答
第一印象是暴力遍历,然后做了一些剪枝,避免重复无效的比较查找
能AC 但是效率较低

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        for(int i = 0; i < matrix.size();i++){
            if(matrix[i][0] > target){break;}
            if( matrix[i].back() < target) {continue;}
            for(int j = 0; j < matrix[0].size();j++){
                if(matrix[i][j]> target) {break;}
                if(matrix[i][j] == target) return true;    
            }
        }
        return false;
    }
};

优化方案。 由于矩阵是有序排列,每行的查找可以使用二分。

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

    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        for(int i = 0; i < matrix.size();i++){
            if(matrix[i][0] > target){break;}
            if( matrix[i].back() < target) {continue;}
            if(bsearch(matrix,target,i) == true) return true;
        }
        return false;
    }
};

我的视频题解空间




itdef
16天前

地址 https://leetcode-cn.com/problems/summary-ranges/

给定一个无重复元素的有序整数数组 nums 。
返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表。
也就是说,nums 的每个元素都恰好被某个区间范围所覆盖,并且不存在属于某个范围但不属于 nums 的数字 x 。
列表中的每个区间范围 [a,b] 应该按如下格式输出:
"a->b" ,如果 a != b
"a" ,如果 a == b

示例 1:
输入:nums = [0,1,2,4,5,7]
输出:["0->2","4->5","7"]
解释:区间范围是:
[0,2] --> "0->2"
[4,5] --> "4->5"
[7,7] --> "7"

示例 2:
输入:nums = [0,2,3,4,6,8,9]
输出:["0","2->4","6","8->9"]
解释:区间范围是:
[0,0] --> "0"
[2,4] --> "2->4"
[6,6] --> "6"
[8,9] --> "8->9"

示例 3:
输入:nums = []
输出:[]

示例 4:
输入:nums = [-1]
输出:["-1"]

示例 5:
输入:nums = [0]
输出:["0"]


提示:
0 <= nums.length <= 20
-231 <= nums[i] <= 231 - 1
nums 中的所有值都 互不相同
nums 按升序排列

解答
本意就是数组排序(本题数组已经排过序)
然后找出连续的数字的起始和结束数字 加入答案. 这里采取双指针方案
主要是注意各种边界条件。
11.png

class Solution {
public:
    vector<string>  ans;
    vector<string> summaryRanges(vector<int>& nums) {
        int l =0; int r = 0;

        while(l<nums.size() && r < nums.size()){
            while( r < nums.size()-1 && nums[r+1] == nums[r]+1){
                r++;
            }
            if(r >= nums.size()){
                r = nums.size()-1;
            }
            string tmp = to_string(nums[l])+"->"+to_string(nums[r]);
            if(l== r){tmp = to_string(nums[l]);}
            ans.push_back(tmp);
            l=r+1; r=l;
        }

        return ans;
    }
};

我的视频题解空间




itdef
17天前

地址 https://leetcode-cn.com/problems/combination-sum-iii/

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数,并且每种组合中不存在重复的数字。

说明:
所有数字都是正整数。
解集不能包含重复的组合。 

示例 1:
输入: k = 3, n = 7
输出: [[1,2,4]]

示例 2:
输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]

解答
题目的数据范围不大 就是9个数字的从小到大的组合。
使用dfs深度搜索 将所有数字的组合排列出来,检出符合条件的答案。
注意,不能包含重复组合。那么我们在搜索尝试的时候 需要选择比上一个数字大的数字进行尝试。
11.png

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> numsHash;
    bool Check(const vector<int>& v,int n){
        int sum = 0;
        for(auto& e:v){
            sum += e;
        }
        return sum == n;
    }

    void dfs(int k ,int n , vector<int>& v){
        if(v.size() == k){
            if(Check(v,n)){
                ans.push_back(v);
            }
            return ;
        }
        int startval = 1;
        if(!v.empty()){
            startval = v.back()+1;
        }
        for(int i =startval;i<=9;i++){
            if(numsHash[i] ==0){
                v.push_back(i);
                dfs(k,n,v);
                v.pop_back();
            }
        }

        return;
    }

    vector<vector<int>> combinationSum3(int k, int n) {
        vector<int> v;
        numsHash.resize(10);
        dfs(k,n,v);
        return ans;
    }
};

我的视频题解空间



新鲜事 原文

itdef
17天前
攒力扣金币换奖品中
图片



itdef
23天前

地址 https://leetcode-cn.com/problems/house-robber-ii/

你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。
这个地方所有的房屋都 围成一圈 ,这意味着第一个房屋和最后一个房屋是紧挨着的。
同时,相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组,计算你 在不触动警报装置的情况下 ,今晚能够偷窃到的最高金额。


示例 1:
输入:nums = [2,3,2]
输出:3
解释:你不能先偷窃 1 号房屋(金额 = 2),然后偷窃 3 号房屋(金额 = 2), 因为他们是相邻的。

示例 2:
输入:nums = [1,2,3,1]
输出:4
解释:你可以先偷窃 1 号房屋(金额 = 1),然后偷窃 3 号房屋(金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。
     
示例 3:
输入:nums = [0]
输出:0
 

提示:
1 <= nums.length <= 100
0 <= nums[i] <= 1000

同打家劫舍I 一样使用动态规划dp来解决该题
如果我们选择某一个房间进行盗窃
我们的选择有两种 盗窃该房间和不盗窃该房间
1 盗窃该房间 那么就说明他之前的相邻房间是没有被盗窃的,
我们此时的受益应该当前房间的财富和当前房间不相邻的房间能获得的最大财富之和。
如果以dp[i]表示在当前房间i能获得的最大受益 那么dp[i]= dp[i-2]+当前房间财富;
2 不盗窃当前房间 那么能获取的财富就是上一个房间时能获取的最大财富
如果以dp[i]表示在当前房间i能获得的最大受益 那么dp[i]= dp[i-1];

但是不同点在于 他是一个圆圈
所以从某一点开始那么开始的一个点和最后一个点是不能同时选择的 因为他们也是相邻的。
那么我们将第一个房间排除 和 最后一个房间排除 来进行两次运算,取能获取的最大财富即可.
34.png

class Solution {
public:
    int dp[150];
    int rob(vector<int>& nums) {
        if(nums.size() == 1) return nums[0];
        memset(dp, 0, sizeof dp);

        //两次比较 第一次不选第一个  第二次不选择最后一个
        vector<int> cp = nums;
        //第0位插入一个数字方便动态规划 不考虑边界情况
        nums[0] = 0;
        dp[1] = nums[1];
        int ans = dp[1];
        for (int i = 2; i < nums.size(); i++) {
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
            ans = max(dp[i], ans);
        }


        memset(dp, 0, sizeof dp);
        cp.insert(cp.begin(), 0);
        dp[1] = cp[1];
        cp.back() = 0;
        ans = max(ans,dp[1]);
        for (int i = 2; i < nums.size(); i++) {
            dp[i] = max(dp[i - 1], dp[i - 2] + cp[i]);
            ans = max(dp[i], ans);
        }

        return ans;
    }
};

我的题解空间