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

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++ 的舒服。