首页 > 编程语言 >【C++】速通涉及 “vector” 的经典OJ编程题

【C++】速通涉及 “vector” 的经典OJ编程题

时间:2024-10-08 09:48:50浏览次数:12  
标签:ch OJ nums int sum C++ 异或 vector

【C++】速通涉及 “vector” 的经典OJ编程题

一. 杨辉三角

本题LeetCode链接:
在这里插入图片描述

解题思路:

利用vector的特性创建一个二维数组,通过观察得知杨辉三角的0行0列全为1,其他位置元素的值都等于其上一行同列元素与上一行前一列元素的和。

代码实现:

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> arr(numRows);
         for(int i = 0; i < numRows; i++)
        {
            //arr[i].resize(i + 1, 1);//将开辟的空间全初始化为1
            arr[i].resize(i + 1);
            arr[i][0] = arr[i][i] = 1;
        }

        //第一、二行的元素都是1,从第3行,第2列开始循环
        for(int i = 2; i < numRows; i++)
        {
            for(int j = 1; j < i; j++)
            {
                arr[i][j] = arr[i - 1][j] + arr[i - 1][j - 1];
            }
        }
        return arr;
    }
};

二. 删除有序数组中的重复项

本题LeetCode链接:
在这里插入图片描述

解题思路:

比较相邻的两个元素是否相等,若不相等则依次从原数组第二个位置(即变量index,下标为1)插入到原数组中

代码实现:

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int index = 1;
        for(int i = 0; i < nums.size() - 1; i++)//注意下面的i + 1越界情况
        {
            if(nums[i] != nums[i + 1])
            {
                nums[index] = nums[i + 1];
                index++;
            }
        }
        //由于一旦发生交换后index就会++;所以此时index的大小就为最终长度
        return index;
    }
};

【C/C++】按位运算符使用规制

1. 按位与(&):两个相应的二进制位都为1时,结果为1,否则为0。
2. 按位或(|):两个相应的二进制位只要有一个为1,结果为1。
3. 按位异或(^):两个相应的二进制位相异时,结果为1,相同时,结果为0。
4. 按位取反(~):对一个二进制数按位取反,即0变为1,1变为0。
5. 左移(<<):将一个二进制数的各位全部左移若干位,高位丢弃,低位补0。
6. 右移(>>):将一个二进制数的各位全部右移若干位,低位丢弃,高位补符号位

三. 只出现一次的数字

本题LeetCode链接:
在这里插入图片描述

解题思路:

0异或任何一个数的结果为该数本身,两个相同的整数异或结果为0;

代码实现:

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int num = 0;
        for(auto ch : nums)
        {
            num ^= ch;
        }
        return num;
    }
};

四. 只出现一次的数字 III

本题LeetCode链接:
在这里插入图片描述

解题思路:

由于给定的整数序列中恰好有两个元素只出现一次,其余所有元素均出现两次;
将全部元素异或到sum(值为0)中就是这两个元素的异或结果(1.两个相等的元素异或结果为0;2.任何一整数异或0的结果为它本身);由于这两个数不相等,那么异或的结果sum中至少有一个二进制比特位的值为1,我们这里就找到结果sum中的最低的且值为1的比特位,并且把sum中的其他比特位都改变为0得到 lowbit(通过sum ^ -sum得到lowbit,lowbit其他比特位数值均为0);这就是这两个不同的元素的区别,再利用按位与(&)的特征来找到这两个不同的元素;此时用lowbit的唯一的数值为1的比特位来作为判断条件,分别用两个0异或原数组中的所以元素,由于其他元素均出现且只出现了两次,不管异或到哪个0这两个相同整数异或结果都是0,不会影响到最终要找的这两个不同元素。

关键声明:

     s = 101100
    ~s = 010011
(~s)+1 = 010100 // 根据补码的定义,这就是 -s   效果:s 的最低 1 左侧取反,右侧不变
s & -s = 000100 // lowbit

作者:灵茶山艾府
链接:https://leetcode.cn/problems/single-number-iii/solutions/2484352/tu-jie-yi-zhang-tu-miao-dong-zhuan-huan-np9d2/
来源:力扣(LeetCode)

代码实现:

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        size_t sum = 0;
        for(auto ch : nums)
        {
            sum ^= ch;
        }

        //只保留一个二进制数最低位的1,其他位均为0;
        size_t lowbit = sum & -sum;//此处要用size_t,解决溢出情况

        int type1 = 0,type2 = 0;//此处不可以用size_t,与vector<int>不匹配
        for(auto ch : nums)
        {
            if(lowbit & ch)
            {
                type1 ^= ch;
            }
            else
            {
                type2 ^= ch;
            }
        }

      return  {type1, type2};
      
        //vector<int> ans(2,0);
        //for(auto ch : nums)
        //{
            //ans[(ch & lowbit) == 0] ^= ch; 
        //}
        //return ans;
    }
};

标签:ch,OJ,nums,int,sum,C++,异或,vector
From: https://blog.csdn.net/2303_80737493/article/details/142714267

相关文章

  • NZOJ 模拟赛5
    T1逃离遗迹根据外星人的回信,在遗迹中有分布着三样道具。当三样道具都拿走后,遗迹就很快自动毁灭,所以必须要在最短时间内离开。遗迹可以看作是由N个房间(编号1..N)和N-1条长度不等通道所组成,并且任意两个房间之间有且只有一条路可以相互到达。现在我们的队员已经在编号为A,B,C的......
  • c++条件变量
    条件变量是用于线程间同步的一种机制,它允许一个或多个线程在某个条件满足之前等待,并在条件满足时通知等待的线程继续执行。以下是条件变量的基本使用方法,包括notify_one和notify_all的作用。使用条件变量的基本步骤创建条件变量和互斥量:首先需要创建一个std::condition_v......
  • 题解 QOJ1869【Power Station of Art】/ SS241006B【结论题】
    题解QOJ1869【PowerStationofArt】/SS241006B【结论题】PetrozavodskSummer2021.Day6.XJTUContest,GPofXJTUXXIIOpenCupnamedafterE.V.Pankratiev,GrandPrixofXi'an题目描述给出一个无向图,每个点有点权\(a\)和颜色\(c\),其中颜色只会有红蓝两种。......
  • 题解 QOJ2559【Endless Road】/ SS241006D【套路题】
    PetrozavodskWinter2022.Day2.KAISTContest+KOITST2021XXIIOpenCupnamedafterE.V.Pankratiev,GrandPrixofDaejeon题目描述现在有\(10^9\)个花盆,依次编号为\(1,2,\dots,10^{9}\)。给定\(n\)个二元组\(L_i,R_i(L_i<R_i)\),我们将进行\(n\)次以下操......
  • XB家的OJ - XBOJ
    基于Hydro,我们开始试运行一个新的OJ系统XBOJ注册方法及概述使用邮箱在XBOJ注册在上面的链接网站注册完成后,使用该网站加入OJ邀请码(使用base64解码一次)ZGlzdGluZ3Vpc2hlZA==该OJ中收录了部分ewen的v系列题目,以及部分原创题,最后是一点有趣洛谷题的搬运......
  • QOJ #9438. Two Box
    题面传送门首先考虑给定一个状态怎么计算答案。考虑建立一棵\(m\)层的树,在第\(d\)层的时候,考虑每个极长连续段\([l,r]\)满足\(\max\limits_{i=l}^{r}a_i\geqd\),则将\([l,r+1]\)看作这棵树上的一个点,向\(d+1\)层中所有被这个区间包含的点连边。对于第\(i\)层的第......
  • c++指针传递与引用传递
    c不支持引用传递的!在C++中,指针传递和引用传递是两种常用的参数传递方式,它们各自有不同的特点和适用场景。下面是两者之间的主要区别:1.语法和使用指针传递定义和调用:函数参数是一个指针类型,调用时需要传递变量的地址。解引用:在函数内部需要使用解引用操作符*来访问指针......
  • c++可变模板参数
    在C++中的可变模板参数使用省略号...来表示一个参数包(ParameterPack),其具体位置决定了这个包是模板参数包还是函数参数包,以及如何进行参数展开。1.模板参数包:c...Args省略号放在类型名称的右边,用来表示模板参数包,即可以接受任意数量的模板类型参数。template<typename...A......
  • P5416 = UOJ 198 时空旅行 题解
    Statement一棵树,每个节点上有一个集合,每个儿子集合由父亲集合增加一个点\((x_i,c_i)\)或删除一个点得到。根节点集合为\(\{(0,0,0,c_0)\}\)多次询问,每次问\(u\)点的集合内,\(\min\{(x_i-x)^2+c_i\}\)Solution首先你认真读完题发现原题中\(y,z\)都是没用的然后离线DFS......
  • LOJ 6041 事情的相似度 题解
    Statement先把串reverse,多次给\(l,r\),求\[\max_{l\lei<j\ler}\{\text{LCP}(i,j)\}\]Solution\(\text{sqrtlog}\sim\text{sqrt}\):莫队+线段树/树状数组/set,用SA做\(nm/\omega\):bitset乱搞\(\log^2\):SAM+LCT+BIT在parent树上,LCP等于LCA的......