只出现一次的数字＜难度系数⭐＞&& 杨辉三角＜难度系数⭐＞

1、只出现一次的数字＜难度系数⭐＞

📝 题述：给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

⚠ 说明：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗 ？

💨示例1：

输入: [2,2,1]
输出: 1

💨示例2：

输入: [4,1,2,1,2]
输出: 4

🧷 平台：Visual studio 2017 && windows

🔑 核心思想：使用异或操作符 ^ —— 相同为 0，相异为 1

leetcode原题

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ret = 0;
        //1、operator[]
        /*for(size_t i = 0; i < nums.size(); ++i)
        {
            ret ^= nums[i];
        }*/
        //2、迭代器
        /*vector<int>::iterator it = nums.begin();
        while(it != nums.end())
        {
            ret ^= *it;
            ++it;
        }*/
        //3、范围for
        for(auto e : nums)
        {
            ret ^= e;
        }
        return ret;
    }
};

2、杨辉三角＜难度系数⭐＞

📝 题述：给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。在「杨辉三角」中，每个数是它左上方和右上方的数的和。

💨示例1：

输入：numRows = 5
输出：[ [1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1] ]

💨示例2：

输入：numRows = 1
输出：[ [1] ]

⚠提示：1 <= numRows <= 30

🧷 平台：Visual studio 2017 && windows

🔑 核心思想：需要先生成一个杨辉三角，每行的第一个和最后一个是 1，其余设置为 0，如果是 0，则需要计算。这里可以发现规律：1 = 1 + (1 - 1)，这里以第一个要计算的值为例，且这里的数字代表的下标 —— 第 3 行以 1 为下标位置的值是等于第 2 行以 1 为下标的值加上第 2 行以 1 - 1 为下标的值。

leetcode原题

class Solution {
public:
    //vector<vector<int>>就是一个二维数组,这里在vector模拟实现的时候也会细讲
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> vv;
        vv.resize(numRows);
        //生成
        for(size_t i = 0; i < vv.size(); ++i)
        {
        	//每行有多少个,并初始化为0
            vv[i].resize(i + 1, 0);
            //每一行的第一个和最后一个赋值为1
            /*vv[i].front() = 1;
            vv[i].back() = 1;*/
            vv[i][0] = 1;
            vv[i][vv[i].size() - 1] = 1; 
        }
        //遍历
        for(size_t i = 0; i < vv.size(); ++i)
        {
            for(size_t j = 0; j < vv[i].size(); ++j)
            {
                if(vv[i][j] == 0)//需要处理
                {
                    vv[i][j] = vv[i - 1][j] + vv[i - 1][j - 1];
                }
            }
        }
        return vv;
    }
};

📝补充

这道题如果是用 C语言去写的话，就要动态开辟一个二维数组，写起来相对没有 C++ 的舒服。