领扣刷题笔记（C++ Difficulty：Easy）

注：C++兼容C的输入输出，会增大IO开销，可以添加以下代码提高IO效率

static const auto init = []() {
    /*
     *关掉c++中iostream和c中cstdio流的同步（cout和printf，cin和scanf）
     *关掉后不能同时使用c和c++的输入输出；
     */
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);//完成cin和cout的解耦，减少大量的缓冲区刷新操作
    return nullptr;
}();

1. Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:

Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

解题思路：

对数组进行遍历，将符合条件的数组元素返回；
另有高效率遍历哈希表法，待研究。

解答：

//暴力法：遍历整个数组，耗时较长（72ms）
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) 
    {
        vector<int> result;
        int size = nums.size();
        for (int i = 0; i < size; i++)
        {
            int complement = target - nums[i];
            for (int j = i + 1; j < size; j++)
            {
                if (nums[j] == complement)
                {
                    result.push_back(i);
                    result.push_back(j);
                    return result;
                }   
            }
        }
        return result;
    }
};

7. Reverse Integer

Given a 32-bit signed integer, reverse digits of an integer.
Example 1:
Input: 123
Output: 321
Example 2:
Input: -123
Output: -321
Example 3:
Input: 120
Output: 21
Note:
Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−2³¹, 2³¹ − 1]. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.

解题思路：

初始化一个long long类型的变量ans用于保存反转后的整数，每次执行以下操作：

1. ans = ans * 10 + x % 10;
2. x /= 10;

最后判断ans是否溢出，溢出则返回0，否则返回ans
在第一次尝试时，忽略了反转后的数字可能出现溢出的情况，定义int类型的ans会导致溢出，所以将ans定义为 long long类型

解答：

class Solution {
public:
    int reverse(int x) {
        //INT_MAX : 2147483647 
        //INT_MIN : -2147483648
        long long ans = 0;
        while (x != 0) {
            ans = ans * 10 + x % 10;
            x /= 10;
        }
        return (ans > INT_MAX || ans < INT_MIN) ? 0 : ans;
    }
};

118. Pascal's Triangle

Given a non-negative integer numRows, generate the first numRows of Pascal's triangle.

In Pascal's triangle, each number is the sum of the two numbers directly above it.
Example:
Input: 5
Output:

[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

解题思路：

根据杨辉三角的特点创建容器，并将每行开头和结尾赋值为1，当行数大于2时，根据杨辉三角的运算规则进行运算

解答：

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> res(numRows, vector<int>());
        for (int i = 0; i < numRows; ++i)
        {
            res[i].resize(i + 1);  //确定每行数字的个数
            //每行开头和结尾都为1
            res[i][0] = 1;
            res[i][i] = 1;
        }
        if (numRows > 2)
        {
            for (int i = 2; i < numRows; ++i) 
            {
                for (int j = 1; j < i; ++j) 
                    res[i][j] = res[i-1][j] + res[i-1][j-1];
            }
        }
        return res;
    }
};

136. Single Number

Given a non-empty array of integers, every element appears twice except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
Example 1:
Input: [2,2,1]
Output: 1
Example 2:
Input: [4,1,2,1,2]
Output: 4

解题思路：

题目要求算法的时间复杂度为O(n),空间复杂度为O(1)；
将容器的所有的数字进行异或运算，由于相同两个数字异或结果为0，所以所有元素异或的结果便为所寻单独的数字。

解答：

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int result = 0;
        for(auto ibeg = nums.begin(); ibeg != nums.end(); ++ibeg)
        {
            result ^= *ibeg;  //所有数字进行异或运算 
        }
        return result;
    }
};

182. Duplicate Emails

SQL架构

Create table If Not Exists Person (Id int, Email varchar(255))
Truncate table Person
insert into Person (Id, Email) values ('1', 'a@b.com')
insert into Person (Id, Email) values ('2', 'c@d.com')
insert into Person (Id, Email) values ('3', 'a@b.com')

Write a SQL query to find all duplicate emails in a table named Person.
Example:

+----+---------+
| Id | Email   |
+----+---------+
| 1  | a@b.com |
| 2  | c@d.com |
| 3  | a@b.com |
+----+---------+

For example, your query should return the following for the above table:

+---------+
| Email   |
+---------+
| a@b.com |
+---------+

Note: All emails are in lowercase.

解题思路：

使用 GROUP BY 和 HAVING 条件：向 GROUP BY 添加条件的一种更常用的方法是使用 HAVING 子句，该子句更为简单高效。
GROUP BY 语句用于结合合计函数，根据一个或多个列对结果集进行分组。

解答：

select Email from Person
group by Email having count(Email) > 1;

191. Number of 1 Bits

Write a function that takes an unsigned integer and return the number of '1' bits it has (also known as the Hamming weight).
Example 1:
Input: 00000000000000000000000000001011
Output: 3
Explanation: The input binary string 00000000000000000000000000001011 has a total of three '1' bits.
Example 2:
Input: 00000000000000000000000010000000
Output: 1
Explanation: The input binary string 00000000000000000000000010000000 has a total of one '1' bit.
Example 3:
Input: 11111111111111111111111111111101
Output: 31
Explanation: The input binary string 11111111111111111111111111111101 has a total of thirty one '1' bits.
Note:

• Note that in some languages such as Java, there is no unsigned integer type. In this case, the input will be given as signed integer type and should not affect your implementation, as the internal binary representation of the integer is the same whether it is signed or unsigned.
• In Java, the compiler represents the signed integers using 2's complement notation. Therefore, in Example 3 above the input represents the signed integer -3.
  Follow up:
  If this function is called many times, how would you optimize it?

解题思路：

• 思路1：除2取余法，末尾为1，除2取余后为1，末尾为0，除2取余后为0
• 思路2：与1相与，直接判定末位是否为1
• 思路3：直接去掉二进制中位置最靠后的1。假设n=1100，则n-1=1011，那么n&(n-1)=1000,位置最靠后的1被去掉。

解答：

//方法1
class Solution {
public:
    int hammingWeight(uint32_t n) {
        int cnt = 0;
        while(n != 0)
        {
            cnt += n % 2;
            n >>= 1;
        }
        return cnt;
    }
};
//方法2
class Solution {
public:
    int hammingWeight(uint32_t n) {
        int cnt = 0;
        while(n != 0)
        {
            cnt += n & 1;
            n >>= 1;
        }
        return cnt;
    }
};
//方法3
class Solution {
public:
    int hammingWeight(uint32_t n) {
        int cnt = 0;
        while(n != 0)
        {
            n = n & (n-1);
            cnt++;
        }
        return cnt;
    }
};

231. Power of Two

Example 1:
Input: 1
Output: true
Explanation: 2⁰ = 1
Example 2:
Input: 16
Output: true
Explanation: 2⁴ = 16
Example 3:
Input: 218
Output: false

解题思路：

通过观察可知，如果一个数字为2的幂，那么这个数字中的二进制数中的最高位必为1，其它都为0，那么灵气减1，最高位变为0，其它位变为1。例如2³=8,其二进制形式为1000，那么8 - 1 = 7，7的二进制形式为0111，1000 & 0111 = 0；我们可以通过这个性质来判断该数字是否为2的幂。

解答：

class Solution {
public:
    bool isPowerOfTwo(int n) {
        return (n > 0) && (! (n & (n - 1) ) );
    }
};

268. Missing Number

Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.
Example 1:
Input: [3,0,1]
Output: 2
Example 2:
Input: [9,6,4,2,3,5,7,0,1]
Output: 8
Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

解题思路：

要求时间复杂度为O(n)；

• 思路1： 采用和136. Single Number类似的思路，将容器中所有的数字和有序数列1,2,3……,n异或，如果容器中存在数字x，那么和有序数列中对应的x异或结果为零，最终得到的结果便为缺失的数字。
• 思路2：采用求和相减，若容器长度为n，利用求和公式计算s1 = n * (n+1) / 2，减去容器中数字的求和s2，则可得缺失的数字。

解答：

//方法1：
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int result = 0;
        int len = nums.size();
        for(int i = 0; i < len; ++i)
        {
            result ^= (i+1) ^ nums[i];
        }
        return result;
    }
};
//方法2：
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size();
        int s1 = n * (n + 1) / 2;
        int s2 = 0;
        for(int i : nums)
        {
            s2 += i;
        }
        return s1 - s2;
    }
};

344. Reverse String

Write a function that takes a string as input and returns the string reversed.
Example 1:
Input: "hello"
Output: "olleh"
Example 2:
Input: "A man, a plan, a canal: Panama"
Output: "amanaP :lanac a ,nalp a ,nam A"

解题思路：

• 思路1： 通过s.length()获取s的字符长度，然后通过下标访问s，将s中的字符从尾到头拼接到result上，得到返回结果。
• 思路2： 利用reverse函数，reverse(beg, end)会将区间(beg, end)之间的元素全部逆转。

解答：

// code 1: 
// 4ms
class Solution {
public:
    string reverseString(string s) {
        string result = "";
        auto len = s.length();
        while(len > 0)
        {
            result += s[len - 1];
            --len;
        }
        return result;
    }
};
// code 2:
// 4ms
class Solution {
public:
    string reverseString(string s) {
        reverse(s.begin(),s.end());
        return s;
    }
};

461. Hamming Distance

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.
Given two integers x and y, calculate the Hamming distance.
Note:
0 ≤ x, y < 2³¹.
Example:

Input: x = 1, y = 4
Output: 2
Explanation:
1   (0 0 0 1)
4   (0 1 0 0)
       ↑   ↑
The above arrows point to positions where the corresponding bits are different.

解题思路：

n = x ^ y，两数对应位置若不相同，则n的相应位置置1
利用n = n & (n - 1)获取n中1的个数

解答：

class Solution {
public:
    int hammingDistance(int x, int y) {
        int n = x^y, count = 0;
        while(n){
            count ++;
            n = n&(n-1);
        }
        return count;
    }
};

476. Number Complement

Given a positive integer, output its complement number. The complement strategy is to flip the bits of its binary representation.
Note:

1. The given integer is guaranteed to fit within the range of a 32-bit signed integer.
2. You could assume no leading zero bit in the integer’s binary representation.
   Example 1:
   Input: 5
   Output: 2
   Explanation: The binary representation of 5 is 101 (no leading zero bits), and its complement is 010. So you need to output 2.
   Example 2:
   Input: 1
   Output: 0
   Explanation: The binary representation of 1 is 1 (no leading zero bits), and its complement is 0. So you need to output 0.

解题思路：

题例中5的二进制为101，补数为010,补数可以通过101 ^ 111获得，所以首先获取与num相同二进制位数的111，通过判断num左移1位是否为空可以获得其位数，进而获取mask。

解答：

class Solution {
public:
    int findComplement(int num) {
        int mask = 2, tmp = num;
        while(tmp >>= 1)
        {
            mask <<= 1;  
        }
        return num ^ (mask-1);
    }
};

509. Fibonacci Number

The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,

F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), for N > 1.

Given N, calculate F(N).
Example 1:
Input: 2
Output: 1
Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.
Example 2:
Input: 3
Output: 2
Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.
Example 3:
Input: 4
Output: 3
Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3.
Note:
0 ≤ N ≤ 30.

解题思路：

• 思路1：采用递归的方法
• 思路2：采用数组，将斐波那契数存入到数组中。

解答：

//方法1：
//效率较低，运行时间20ms
int fibonacci(int n)
{
    if(n == 0)
        return 0;
    else if(n == 1)
        return 1;
    return fibonacci(n-1) + fibonacci(n-2); 
}
class Solution {
public:
    int fib(int N) {
        return fibonacci(N);     
    }
};
//方法2：
//运行时间0ms
class Solution {
public:
    int fib(int N) {
        int *p = new int[N+1];//开辟大小为N+1的数组
        p[0] = 0;
        p[1] = 1;
        for(int i = 2; i < N+1; ++i)
        {
            p[i] = p[i-1] + p[i-2];
        }
        return p[N];
    }
};

561. Array Partition I

Given an array of 2n integers, your task is to group these integers into n pairs of integer, say (a₁, b₁), (a₂, b₂), ..., (a_n, b_n) which makes sum of min(a_i, b_i) for all i from 1 to n as large as possible.
Example 1:
Input: [1,4,3,2]
Output: 4
Explanation: n is 2, and the maximum sum of pairs is 4 = min(1, 2) + min(3, 4).
Note:

1. n is a positive integer, which is in the range of [1, 10000].
2. All the integers in the array will be in the range of [-10000, 10000].

解题思路：

为得到最大的和，所以要保证第2大的数字和第1大的数字进行组合，第4大的数字和第3大的数字进行组合，以此类推。可以看出，我们将数组进行排序后，取2n+1项进行相加，即可得结果。

解答：

class Solution {
public:
    int arrayPairSum(vector<int>& nums) {
        int len = nums.size();
        sort(nums.begin(), nums.end());
        int result = 0;
        for(int i = 0; i < len; ++i)
        {
            result += nums[i];
            ++i;
        }
        return result;
    }
};

595. Big Countries

SQL架构

Create table If Not Exists World (name varchar(255), continent varchar(255), area int, population int, gdp int)
Truncate table World
insert into World (name, continent, area, population, gdp) values ('Afghanistan', 'Asia', '652230', '25500100', '20343000000')
insert into World (name, continent, area, population, gdp) values ('Albania', 'Europe', '28748', '2831741', '12960000000')
insert into World (name, continent, area, population, gdp) values ('Algeria', 'Africa', '2381741', '37100000', '188681000000')
insert into World (name, continent, area, population, gdp) values ('Andorra', 'Europe', '468', '78115', '3712000000')
insert into World (name, continent, area, population, gdp) values ('Angola', 'Africa', '1246700', '20609294', '100990000000')

There is a table World

+-----------------+------------+------------+--------------+---------------+
| name            | continent  | area       | population   | gdp           |
+-----------------+------------+------------+--------------+---------------+
| Afghanistan     | Asia       | 652230     | 25500100     | 20343000      |
| Albania         | Europe     | 28748      | 2831741      | 12960000      |
| Algeria         | Africa     | 2381741    | 37100000     | 188681000     |
| Andorra         | Europe     | 468        | 78115        | 3712000       |
| Angola          | Africa     | 1246700    | 20609294     | 100990000     |
+-----------------+------------+------------+--------------+---------------+

A country is big if it has an area of bigger than 3 million square km or a population of more than 25 million.
Write a SQL solution to output big countries' name, population and area.
For example, according to the above table, we should output:

+--------------+-------------+--------------+
| name         | population  | area         |
+--------------+-------------+--------------+
| Afghanistan  | 25500100    | 652230       |
| Algeria      | 37100000    | 2381741      |
+--------------+-------------+--------------+

解题思路：

利用人口和面积进行筛选

解答：

select name, population, area from World where area > 3000000 or population > 25000000;

620. Not Boring Movies

SQL架构

Create table If Not Exists cinema (id int, movie varchar(255), description varchar(255), rating float(2, 1))
Truncate table cinema
insert into cinema (id, movie, description, rating) values ('1', 'War', 'great 3D', '8.9')
insert into cinema (id, movie, description, rating) values ('2', 'Science', 'fiction', '8.5')
insert into cinema (id, movie, description, rating) values ('3', 'irish', 'boring', '6.2')
insert into cinema (id, movie, description, rating) values ('4', 'Ice song', 'Fantacy', '8.6')
insert into cinema (id, movie, description, rating) values ('5', 'House card', 'Interesting', '9.1')

X city opened a new cinema, many people would like to go to this cinema. The cinema also gives out a poster indicating the movies’ ratings and descriptions.
Please write a SQL query to output movies with an odd numbered ID and a description that is not 'boring'. Order the result by rating.
For example, table cinema:

+---------+-----------+--------------+-----------+
|   id    | movie     |  description |  rating   |
+---------+-----------+--------------+-----------+
|   1     | War       |   great 3D   |   8.9     |
|   2     | Science   |   fiction    |   8.5     |
|   3     | irish     |   boring     |   6.2     |
|   4     | Ice song  |   Fantacy    |   8.6     |
|   5     | House card|   Interesting|   9.1     |
+---------+-----------+--------------+-----------+

For the example above, the output should be:

+---------+-----------+--------------+-----------+
|   id    | movie     |  description |  rating   |
+---------+-----------+--------------+-----------+
|   5     | House card|   Interesting|   9.1     |
|   1     | War       |   great 3D   |   8.9     |
+---------+-----------+--------------+-----------+

解题思路：

通过description和id进行筛选，然后通过rating进行倒序排序（DESC）

解答：

SELECT id, movie, description, rating
FROM cinema
WHERE id % 2 != 0 and description != 'boring'
ORDER BY rating DESC

627. Swap Salary

SQL架构

create table if not exists salary(id int, name varchar(100), sex char(1), salary int)
Truncate table salary
insert into salary (id, name, sex, salary) values ('1', 'A', 'm', '2500')
insert into salary (id, name, sex, salary) values ('2', 'B', 'f', '1500')
insert into salary (id, name, sex, salary) values ('3', 'C', 'm', '5500')
insert into salary (id, name, sex, salary) values ('4', 'D', 'f', '500')

Given a table salary, such as the one below, that has m=male and f=female values. Swap all f and m values (i.e., change all f values to m and vice versa) with a single update query and no intermediate temp table.For example:

| id | name | sex | salary |
|----|------|-----|--------|
| 1  | A    | m   | 2500   |
| 2  | B    | f   | 1500   |
| 3  | C    | m   | 5500   |
| 4  | D    | f   | 500    |

After running your query, the above salary table should have the following rows:

| id | name | sex | salary |
|----|------|-----|--------|
| 1  | A    | f   | 2500   |
| 2  | B    | m   | 1500   |
| 3  | C    | f   | 5500   |
| 4  | D    | m   | 500    |

解题思路：

利用SQL中的case-when多条件判断语句，类似C++中的switch-case语句

解答：

UPDATE salary
SET sex = (CASE sex WHEN 'm' THEN 'f'
                    WHEN 'f' THEN 'm'
           END)

657. Robot Return to Origin

There is a robot starting at position (0, 0), the origin, on a 2D plane. Given a sequence of its moves, judge if this robot ends up at (0, 0) after it completes its moves.
The move sequence is represented by a string, and the character moves[i] represents its ith move. Valid moves are R (right), L (left), U (up), and D (down). If the robot returns to the origin after it finishes all of its moves, return true. Otherwise, return false.
Note: The way that the robot is "facing" is irrelevant. "R" will always make the robot move to the right once, "L" will always make it move left, etc. Also, assume that the magnitude of the robot's movement is the same for each move.
Example 1:
Input: "UD"
Output: true
Explanation: The robot moves up once, and then down once. All moves have the same magnitude, so it ended up at the origin where it started. Therefore, we return true.
Example 2:
Input: "LL"
Output: false
Explanation: The robot moves left twice. It ends up two "moves" to the left of the origin. We return false because it is not at the origin at the end of its moves.

解题思路：

设置四个标志位，利用switch-case判断moves的值，相应标志位+1。
当‘上’=‘下’并且‘左’=‘右’的时候，机器人回到原点。

解答：

// code 1：
// 8ms
class Solution {
public:
    bool judgeCircle(string moves) {
        vector<int> sign(4,0);
        for(auto c : moves)
        {
            switch(c)
            {
                case 'U':
                    sign[0]++;
                    break;
                case 'D':
                    sign[1]++;
                    break;
                case 'L':
                    sign[2]++;
                    break;
                case 'R':
                    sign[3]++;
                    break;
            }
        }
        return sign[0] == sign[1] && sign[2] == sign[3];
    }
};
// code 2：
// 4ms
class Solution {
public:
    bool judgeCircle(string moves) {
        int a = 0, b = 0, c = 0, d = 0;
        for(int i=0;i<moves.size();i++){
            a+=moves[i]=='R';
            b+=moves[i]=='L';
            c+=moves[i]=='U';
            d+=moves[i]=='D';
        }
        return a == b && c == d;
    }
};

709. To Lower Case

Implement function ToLowerCase() that has a string parameter str, and returns the same string in lowercase.
Example 1:

Input: "Hello"
Output: "hello"

Example 2:

Input: "here"
Output: "here"

Example 3:

Input: "LOVELY"
Output: "lovely"

解题思路：

利用C++ tolower()函数；

解答：

class Solution {
public:
    string toLowerCase(string str) {
        for(auto &letter : str)
        {
            letter = tolower(letter);
        }
        return str;
    }
};

771. Jewels and Stones

You're given strings Jrepresenting the types of stones that are jewels, and S representing the stones you have. Each character in S is a type of stone you have. You want to know how many of the stones you have are also jewels.
The letters in J are guaranteed distinct, and all characters in J and S are letters. Letters are case sensitive, so "a" is considered a different type of stone from "A".
Example 1:

Input:J = "aA", S = "aAAbbbb"
Output: 3

Example 2:

Input: J = "z", S = "ZZ"
Output: 0

Note:

• S and J will consist of letters and have length at most 50.
• The characters in J are distinct.

解题思路：

• 思路1： 遍历J和S，两者相等，计数+1；
• 思路2： 创建临时数组a[256]，先以J中元素的ASCII值作为a的索引并作标记。后以S中元素的ASCII值作为a的索引，判断该位置是否为零，如果不为零，则计数+1；
• 思路3： 和2类似，不过将大小写字母分开，减少了数组的长度。

解答：

//code 1：
//运行时间大于4ms；
class Solution {
public:
    int numJewelsInStones(string J, string S) {
        int num = 0;
        for (int i = 0; i < J.length(); i++)
        {
            for (int j = 0; j< S.length(); j++)
                if (J[i] == S[j])
                    num += 1;
        }
        return num;
    }
};
//code 2:
//运行时间4ms；
class Solution {
public:
    int numJewelsInStones(string J, string S) {
        char a[256]={0}; 
        for(int i=0;i<J.length();++i)
            a[J[i]]++; //相应字母的ASCII值作为索引；
        int ans=0; 
        for(int i=0;i<S.length();++i)
            if(a[S[i]]) 
                ans++;
        return ans;     
    }
};
// code  3:
//运行时间0ms；
class Solution {
public:
    int numJewelsInStones(string J, string S) {
        int a_upper[26] = {0} , a_lower[26] = {0};      
        for(auto ch : J)
        {
            int x;            
            if(isupper(ch))
            {
                x = ch - 'A';
                a_upper[x] = 1;
            }
            else
            {
                x = ch - 'a';
                a_lower[x] = 1;
            }
        } 
        int num = 0;
        for(auto ch : S)
        {
            int x;
            if(isupper(ch))
            {
                x = ch - 'A';
                if(a_upper[x])  ++num;
            }
            else
            {
                x = ch - 'a';
                if(a_lower[x])  ++num;
            } 
        } 
        return num;
    }
};

804. Unique Morse Code Words

International Morse Code defines a standard encoding where each letter is mapped to a series of dots and dashes, as follows: "a" maps to ".-", "b"maps to "-...", "c" maps to "-.-.", and so on.
For convenience, the full table for the 26 letters of the English alphabet is given below:

[".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."]

Now, given a list of words, each word can be written as a concatenation of the Morse code of each letter. For example, "cab" can be written as "-.-..--...", (which is the concatenation "-.-." + "-..." + ".-"). We'll call such a concatenation, the transformation of a word.
Return the number of different transformations among all words we have.
Example:
Input: words = ["gin", "zen", "gig", "msg"]
Output: 2
Explanation:
The transformation of each word is:
"gin" -> "--...-."
"zen" -> "--...-."
"gig" -> "--...--."
"msg" -> "--...--."
There are 2 different transformations, "--...-." and "--...--.".
Note:

• The length of words will be at most 100.
• Each words[i] will have length in range [1, 12].
• words[i] will only consist of lowercase letters.

解题思路：

将words中word的字母逐个转换为morsecode，并存入临时string，之后将其插入到无序容器unordered_set<string> result;中，然后获取不同元素的数量。

解答：

class Solution {
public:
    int uniqueMorseRepresentations(vector<string>& words) {
        unordered_set<string> result;
        //vector<string>morseWords;
        vector<string> morseCode{".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."};
        for(auto word = words.begin(); word != words.end(); ++word)
        {
            string tmp = "";
            for(auto letter : *word)
            {
                tmp += morseCode[letter - 'a'];
            }
            result.insert(tmp);
        }
        return result.size();
    }
};

832. Flipping an Image

Given a binary matrix A, we want to flip the image horizontally, then invert it, and return the resulting image.
To flip an image horizontally means that each row of the image is reversed. For example, flipping [1, 1, 0] horizontally results in [0, 1, 1].
To invert an image means that each 0 is replaced by 1, and each 1 is replaced by 0. For example, inverting [0, 1, 1] results in [1, 0, 0].
Example 1:

Input: [[1,1,0],[1,0,1],[0,0,0]]
Output: [[1,0,0],[0,1,0],[1,1,1]]
Explanation: First reverse each row: [[0,1,1],[1,0,1],[0,0,0]].
Then, invert the image: [[1,0,0],[0,1,0],[1,1,1]]

Example 2:

Input: [[1,1,0,0],[1,0,0,1],[0,1,1,1],[1,0,1,0]]
Output: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]
Explanation: First reverse each row: [[0,0,1,1],[1,0,0,1],[1,1,1,0],[0,1,0,1]].
Then invert the image: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]

Notes:

• 1 <= A.length = A[0].length <= 20
• 0 <= A[i][j] <= 1

解题思路：

• 翻转：利用临时数组反转
• 反转：与1异或获得反转效果或者利用if-else判断，不可按位取反

解答：

class Solution {
public:
    vector<vector<int>> flipAndInvertImage(vector<vector<int>>& A) {
        for(auto vint = A.begin(); vint != A.end(); ++vint)
        {
            int len = (*vint).size();
            vector<int> tmp(len, 0);
            for(int i = 0; i < len; i++)
                tmp[i] = (*vint)[len - 1 - i];
            for(auto &i : tmp)
            {
                i ^= 1;
            }
            *vint = tmp;
        }
        return A;
    }
};

852. Peak Index in a Mountain Array

Let's call an array A a mountain if the following properties hold:

• A.length >= 3
• There exists some 0 < i < A.length - 1 such that A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1]
  Given an array that is definitely a mountain, return any i such that A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1].
  Example 1:
  Input: [0,1,0]
  Output: 1
  Example 2:
  Input: [0,2,1,0]
  Output: 1
  Note:

1. 3 <= A.length <= 10000
2. 0 <= A[i] <= 10^6
3. A is a mountain, as defined above.

解题思路：

指定临时变量peak和peak_index，peak与A[i]进行比较，若peak小于A[i]，则令peak = A[i]; peak_index = i;，遍历数组，直到peak取到最大值，peak_index为peak取最大时的i值

解答：

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& A) {
        int peak = 0, peak_index = 0;
        auto len = A.size() - 1;
        for(int i = 0; i < len; ++i)
        {
            if(peak < A[i])
            {
                peak = A[i];
                peak_index = i;
            }
        }
        return peak_index;
    }
};

867. Transpose Matrix

Given a matrix A, return the transpose of A.
The transpose of a matrix is the matrix flipped over it's main diagonal, switching the row and column indices of the matrix.
Example 1:
Input: [[1,2,3],[4,5,6],[7,8,9]]
Output: [[1,4,7],[2,5,8],[3,6,9]]
Example 2:
Input: [[1,2,3],[4,5,6]]
Output: [[1,4],[2,5],[3,6]]
Note:

1. 1 <= A.length <= 1000
2. 1 <= A[0].length <= 1000

解题思路：

A为m * n的矩阵，所以A的转置为n * m的矩阵，故先创建n * m的矩阵result，通过遍历令result[j][i] = A[i][j],最后返回result

解答：

class Solution {
public:
    vector<vector<int>> transpose(vector<vector<int>>& A) {
        int m = A.size();
        int n = A[0].size();
        /*
         * A为m * n的矩阵，则A的转置为n * m的矩阵
         * 所以定义result为n * m的矩阵
         */
        vector<vector<int>> result(n);
        for(int i = 0; i < n; ++i)
            result[i].resize(m);
        for(int i = 0; i < m; ++i)
        {  
            for(int j = 0; j < n; ++j)
            {
                result[j][i] = A[i][j];
            }
        }
        return result;
    }
};

905. Sort Array By Parity

Given an array A of non-negative integers, return an array consisting of all the even elements of A, followed by all the odd elements of A.
You may return any answer array that satisfies this condition.
Example 1:

Input: [3,1,2,4]
Output: [2,4,3,1]
The outputs [4,2,3,1], [2,4,1,3], and [4,2,1,3] would also be accepted.

Note:

1. 1 <= A.length <= 5000
2. 0 <= A[i] <= 5000

解题思路：

创建临时容器存放偶数和奇数，最后存入到结果容器并返回。

解答：

class Solution {
public:
    vector<int> sortArrayByParity(vector<int>& A) {
        vector<int> odd, even, result;
        for(auto vint = A.begin(); vint != A.end(); ++vint)
        {
            if((*vint) % 2 == 0)
                even.push_back(*vint);
            else
                odd.push_back(*vint);
        }
        result.insert(result.end(), even.begin(), even.end());//将even插入result；
        result.insert(result.end(), odd.begin(), odd.end());//将odd插入result；
        return result;
    }
};

922. Sort Array By Parity II

Given an array A of non-negative integers, half of the integers in A are odd, and half of the integers are even.
Sort the array so that whenever A[i] is odd, i is odd; and whenever A[i] is even, i is even.
You may return any answer array that satisfies this condition.
Example 1:
Input: [4,2,5,7]
Output: [4,5,2,7]
Explanation: [4,7,2,5], [2,5,4,7], [2,7,4,5] would also have been accepted.
Note:

1. 2 <= A.length <= 20000
2. A.length % 2 == 0
3. 0 <= A[i] <= 1000

解题思路：

1. 先将数组A按照奇偶分为两个数组odd和even，然后按照偶数、奇数的顺序依次插入到结果数组；
2. 思路和1类似，利用vector的top()取出栈顶元素和pop()删除栈顶元素；

解答：

// code 1:
// 80ms
class Solution {
public:
    vector<int> sortArrayByParityII(vector<int>& A) {
        vector<int> odd, even, result;
        for(auto vint = A.begin(); vint != A.end(); ++vint)
        {
            if((*vint) % 2 == 0)
                even.push_back(*vint);
            else
                odd.push_back(*vint);
        }
        size_t len = A.size();
        auto e = even.begin();
        auto o = odd.begin();
        for(auto i = 0; i < len; ++i)
        {
            if(i % 2 == 0)
            {
                result.push_back(*e);
                e++;
            }                
            else
            {
                result.push_back(*o);
                o++;
            }

        }
        return result;
    }
};
// code 2：
// 64ms
class Solution {
public:
    vector<int> sortArrayByParityII(vector<int>& A) 
    {
        stack<int> odd;
        stack<int> even;
        vector<int>::iterator iter;
        int a=0;//奇偶标志位
        for(iter=A.begin();iter!=A.end();iter++)
        {
            if(*iter%2==0)
                even.push(*iter);
            else
                odd.push(*iter);
        }
        for(iter=A.begin();iter!=A.end();iter++)
        {
              //top()取出栈顶元素，pop()删除栈顶元素；
              if(a==0)
              {
                *iter=even.top();
                 even.pop();
              }
            else
            {
                *iter=odd.top();
                 odd.pop();
            }
            a=1-a;//奇偶变换
        }
        return A;
    }
};

929. Unique Email Addresses

Every email consists of a local name and a domain name, separated by the @ sign.
For example, in alice@leetcode.com, aliceis the local name, and leetcode.com is the domain name.
Besides lowercase letters, these emails may contain '.'s or '+'s.
If you add periods ('.') between some characters in the local name part of an email address, mail sent there will be forwarded to the same address without dots in the local name. For example, "alice.z@leetcode.com"and "alicez@leetcode.com"forward to the same email address. (Note that this rule does not apply for domain names.)
If you add a plus ('+') in the local name, everything after the first plus sign will be ignored. This allows certain emails to be filtered, for example m.y+name@email.com will be forwarded to my@email.com. (Again, this rule does not apply for domain names.)
It is possible to use both of these rules at the same time.
Given a list of emails, we send one email to each address in the list. How many different addresses actually receive mails?
Example 1:

Input:["test.email+alex@leetcode.com","test.e.mail+bob.cathy@leetcode.com","testemail+david@lee.tcode.com"]
Output: 2
Explanation: "testemail@leetcode.com" and "testemail@lee.tcode.com" actually receive mails

Note:

• 1 <= emails[i].length <= 100
• 1 <= emails.length <= 100
• Each emails[i]contains exactly one '@'character.

解题思路：

1. 若邮箱中含有‘+’，先将‘+’和‘@’之间的字符删掉
2. 将新的邮箱中‘@’之前的‘.’删掉
3. 将最后的邮箱插入到无序容器unordered_set<string> result;

解答：

class Solution {
public:
    int numUniqueEmails(vector<string>& emails) {
        unordered_set<string> result; //无序容器-C++ Primer P394；
        for(auto email = emails.begin(); email != emails.end(); ++email)
        {
            auto plus_pos = (*email).find('+');//获取‘+’的位置
            auto at_pos = (*email).find('@');
            if(plus_pos < at_pos)
            {
                auto len = at_pos - plus_pos;
                (*email).erase(plus_pos, len);//移除‘+’和‘@’中间的内容
            }
            auto dot_pos = (*email).find('.');
            at_pos = (*email).find('@');
            while(dot_pos < at_pos)
            {
                //删除所有‘@’前的‘.’
                (*email).erase(dot_pos, 1);
                dot_pos = (*email).find('.');
                at_pos--;
            }
            result.insert(*email);
        }
        return result.size();
    }
};

942. DI String Match

Given a string S that only contains "I" (increase) or "D" (decrease), let N = S.length.
Return any permutation A of [0, 1, ..., N] such that for all i = 0, ..., N-1:

• If S[i] == "I", then A[i] < A[i+1]
• If S[i] == "D", then A[i] > A[i+1]
  Example 1:
  Input: "IDID"
  Output: [0,4,1,3,2]
  Example 2:
  Input: "III"
  Output: [0,1,2,3]
  Example 3:
  Input: "DDI"
  Output: [3,2,0,1]
  Note:

1. 1 <= S.length <= 10000
2. S only contains characters "I" or "D".

解题思路：

如果字符为I，则数字从0开始递增，如果字符为D，则数字从N开始递减；

解答：

class Solution {
public:
    vector<int> diStringMatch(string S) {
        int len = S.length();
        vector<int> A;
        int incNum = 0;
        int decNum = len;
        for(int i = 0; i < len; ++i)
        {
            if(S[i] == 'I')
                A.push_back(incNum++);
            else
                A.push_back(decNum--);
        }
        A.push_back(incNum);
        return A;
    }
};

944. Delete Columns to Make Sorted

We are given an array A of N lowercase letter strings, all of the same length.
Now, we may choose any set of deletion indices, and for each string, we delete all the characters in those indices.
For example, if we have an array A = ["``abcdef``","uvwxyz"] and deletion indices {0, 2, 3}, then the final array after deletions is ["bef", "vyz"], and the remaining columns of A are ["b"``,"``v"], ["e","y"], and ["f","z"]. (Formally, the c-th column is [A[0][c], A[1][c], ..., A[A.length-1][c]].)
Suppose we chose a set of deletion indices D such that after deletions, each remaining column in A is in non-decreasing sorted order.
Return the minimum possible value of D.length.
Example 1:
Input:["cba","daf","ghi"]
Output: 1
Explanation:
After choosing D = {1}, each column ["c","d","g"] and ["a","f","i"] are in non-decreasing sorted order. If we chose D = {}, then a column ["b","a","h"] would not be in non-decreasing sorted order.
Example 2:
Input: ["a","b"]
Output: 0
Explanation: D = {}
Example 3:
Input: ["zyx","wvu","tsr"]
Output: 3
Explanation: D = {0, 1, 2}
Note:

1. 1 <= A.length <= 100
2. 1 <= A[i].length <= 1000

解题思路：

题意解析，非降序意味着列中不存在降序
故进行两次for循环，外层循环为列，内层循环为行，如果前一行某列字母大于后一行（ASCII），则返回值+1；

解答：

class Solution {
public:
    int minDeletionSize(vector<string>& A) {
        int strLen = A[0].length();
        int vLen = A.size();
        int result = 0;
        //列序号
        for(int i = 0; i < strLen; ++i)
        {
            //行序号
            for(int j = 0; j < vLen - 1; ++j)
            {
                if(A[j][i] > A[j+1][i])
                {
                    result++;
                    break;//跳出循环
                }
            }
        }
        return result;
    }
};

961. N-Repeated Element in Size 2N Array

In a array A of size 2N, there are N+1 unique elements, and exactly one of these elements is repeated N times.
Return the element repeated N times.
Example 1:
Input: [1,2,3,3]
Output: 3
Example 2:
Input: [2,1,2,5,3,2]
Output: 2
Example 3:
Input: [5,1,5,2,5,3,5,4]
Output: 5
Note:

1. 4 <= A.length <= 10000
2. 0 <= A[i] < 10000
3. A.length is even

解题思路：

根据题意，其余数字都是不同的，仅有目标值重复，故寻找出现次数大于1的数

解答：

class Solution {
public:
    int repeatedNTimes(vector<int>& A) {
        int len = A.size();
        for(int i  = 0; i < len; ++i)
            for(int j = i + 1; j < len; ++j)
                if(A[i] == A[j])
                    return A[i];
    }
};

待更新