发表于 | 分类于

Reverse Bits

题目描述：

将一个无符号数的二进制进行逆序。

例子：

具体描述见LeetCode190

解题思路：

解题的思路类似于递归的想法。我们先将数左移位和右移位16位后进行或运算，这样就将左半侧和右半侧逆序完成；接下来在左右半侧中各自在不断的左移位和右移位进行位的逆序。

原始数据： 00 00 00 10 10 01 01 00 | 00 01 11 10 10 01 11 00

第一次操作：00 01 11 10 10 01 11 00 | 00 00 00 10 10 01 01 00

第二次操作：10 01 11 00 | 00 01 11 10 | 10 01 01 00 | 00 00 00 10

第三次操作: 11 00 10 01 11 10 00 01 01 00 10 01 00 10 00 00

第四次操作： 00 11 01 10 10 11 01 00 00 01 01 10 10 00 00 00

代码如下：

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        n = (n >> 16) | (n << 16);
        n = ((n & 0xFF00FF00) >> 8) | ((n & 0x00FF00FF) << 8);
        n = ((n & 0xF0F0F0F0) >> 4) | ((n & 0x0F0F0F0F) << 4);
        n = ((n & 0xcccccccc) >> 2) | ((n & 0x33333333) << 2);
        n = ((n & 0xaaaaaaaa) >> 1) | ((n & 0x55555555) << 1);
        return n;
    }
};

发表于 | 分类于

Factorial Trailing Zeroes

题目描述：

给定一个数要求计算其阶乘结果尾部0的个数。

例子：

具体描述见LeetCode172

解题思路：

阶乘的结果中0的结果来至于5的个数，因为2的因子的个数远远多于5，所以只要找到了5的个数就可以知道阶乘尾部0的个数。又因为25，125等存在多个5，所以我们需要不断的找到这些因子的数量。将所有因子的数量相加即可得到0的个数。

代码如下：

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int trailingZeroes(int n) {
        int result = 0;
        for (long long i = 5; n / i > 0; i *= 5){
            result += (n / i);
        }
        return result;
    }
};

发表于 | 分类于

Excel Sheet Column Number

题目描述：

给定一个代表Excel表格列数的字符串，要求返回这个字符串代表的列数。

例子：

具体描述见LeetCode171

解题思路：

首先是构建每个字符所对应的整数；其次根据规律：
AA = 1 26 ^ 1 + 1 26 ^ 0即可通过遍历字符串得到最终的整型结果。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int titleToNumber(string s) {
        int res = 0;
        map<char, int> hash;
        for (int i = 0; i < 26; i++){
            hash['A' + i] = i + 1;
        }
        for (int i = 0; i < s.size(); i++){
            res += hash[s[i]] * pow(26, s.size() - i - 1);
        }
        return res;
    }
};

发表于 | 分类于

K-diff Pairs in an Array

题目描述：

给定一个数组和一个整数k,要求找到数组中|num[i] - num[j]| = k的组合数量。

例子：

具体描述见LeetCode532

解题思路：

本题主要的想法是利用哈希表。我们用哈希表记录下每个数出现的次数；然后遍历哈希表，在遍历到当前数的时候，我们查看哈希表中是否存在key为当前数加上k的数。另外需要判断k为0的情况。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int findPairs(vector<int>& nums, int k) {
        if (k < 0) return 0;
        int res = 0;
        map<int, int> hash;
        for (int i = 0; i < nums.size(); i++){
            hash[nums[i]]++;
        }
        if (k != 0){
            for (auto it = hash.begin(); it != hash.end(); it++){
                if (hash.find(it->first + k) != hash.end())
                    res++;
            }
        }else{
            for (auto it = hash.begin(); it != hash.end(); it++){
                if (it->second > 1)
                    res++;
            }
        }
        return res;
    }
    
};

发表于 | 分类于

Find All Duplicates in an Array

题目描述：

给定一个数组要求找到数组中出现超过两次的数字。

例子：

具体描述见LeetCode442

解题思路：

本题有两种解题方式，一个是利用哈希表记录下已经出现的数字，而后如果在后序的遍历中又出现则将其保存到结果中；另外一种解法是，例如我们将2保存到数组中的第1个位置上，不断的判断位置上数组和index的关系，在将数字放在对应位置上后，剩下的出现多次的数肯定不在对应的位置上，将其保存到结果中即可。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        map<int, int> hash;
        vector<int> res;
        for (int i = 0; i < nums.size(); i++){
            if (hash.find(nums[i]) == hash.end()){
                hash.insert({nums[i], 1});
            }else{
                res.push_back(nums[i]);
            }
        }
        return res;
    }
};
class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        vector<int> res;
        int i = 0;
        while(i < nums.size()){
            if (nums[i] != nums[nums[i] - 1])
                swap(nums[i], nums[nums[i] - 1]);
            else
                i++;
        }
        for (int i = 0; i < nums.size(); i++){
            if (nums[i] - 1 != i){
                res.push_back(nums[i]);
            }
        }
        return res;
    }
};

发表于 | 分类于

Third Maximum Number

题目描述：

给定一个数组，要求找到数组中的第三大的数字。

例子：

具体描述见LeetCode414

解题思路：

这道题主要的注意的点或者说技巧在于，我们可以用一个set来保存数字。set本身使用的是红黑色作为底层实现，所以每次插入都是保持有序的状态。所以我们可以不断将数插入到set中，然后根据是否已经超过三个数来决定要不要删除set中的数。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int thirdMax(vector<int>& nums) {
        set<int> hash;
        for (auto num: nums){
            hash.insert(num);
            if (hash.size() > 3)
                hash.erase(hash.begin());
        }
        return hash.size() == 3 ? *hash.begin() : *hash.rbegin();
    }
};

发表于 | 分类于

Decode Ways

题目描述：

给定一个数字字符串和各个数字字符串对应的字母字符，要求找到这个数字字符可以被解码为字母串的可能数。

例子：

具体描述见LeetCode91

解题思路：

首先我们遍历字符串中的每个字符的时候，我们需要判断当前的字符是不是0，因为如果是0的情况下，可能出现不符合要求的字符串，比如123406；如果是合理的0字符，则当前字符的可能组合数和上一个字符是一致的；如果是不合理的字符0直接返回0；其次在当前字符不是0的情况下，我们判断两种情况；一种是能否和上一个字符组合，可以的情况下就是当前字符的可能和上一个字符可能数相加；如果无法组合就是当前字符的组合了(本题中主要用到的是DP的想法，需要注意的是0字符的处理)

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int numDecodings(string s) {
        if (s == "" || s[0] == '0') return 0;
        vector<int> res(2, 1);
        
        for (int i = 1; i < s.size(); i++){
            int temp = (s[i] - '0') + 10 * (s[i - 1] - '0');
            if (s[i] == '0'){
                if (temp > 20 || temp == 0) return 0;
                else res.push_back(res[i - 1]);
            }else{
                if (temp >= 27 || temp < 10){
                    res.push_back(res[i]);
                }else{
                    res.push_back(res[i] + res[i - 1]);
                }
            }
        }
        return res[res.size() - 1];
    }
};

发表于 | 分类于

Sort Characters By Frequency

题目描述：

给定一个字符串，要求返回一个新的字符串。新的字符串所有字符和旧字符数量一样，但是排列顺序要以字符出现的顺序来排列。

例子：

具体描述见LeetCode451

解题思路：

主要思路是我们构建一个字符和字符出现次数的哈希表。而后构建一个空的桶(用vector实现)；而后遍历哈希表，根据字符出现的次数放入桶的位置，相同次数的字符放入相同的桶。最后从桶的末尾开始将字符连接即是我们要求的返回字符串。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    string frequencySort(string s) {
        unordered_map<char, int> hash;
        string res = "";
        vector<string> bucket = {s.size() + 1, ""};
        for (auto c : s) hash[c]++;
        auto it = hash.begin();
        while(it != hash.end()){
            char c = it->first;
            int n = it->second;
            bucket[n].append(n, c);
            it++;
        }
        for (int i = bucket.size() - 1; i >= 0; i--){
            if (!bucket[i].empty()){
                res += bucket[i];
            }
        }
        return res;
    }
};

发表于 | 分类于

Pow(x, n)

题目描述：

给定一个数x,求得其n次方的结果。

例子：

具体描述见LeetCode50

解题思路：

这一题主要注意的地方有：我们的n可能是负数，所以需要判断是否对x取倒数；其次是p可能非常的大需要比较大的数来保存。另外因为用到了移位的位算法，所以我们需要将p定义为无符号的数。而后对于下面的移位操作简单进行说明。假设我们要计算3的11次方的结果；二进制表示为1011。第一次末尾为1，所以将结果乘以3，然后移位，然后乘数进行乘积变为9；二次移位也是1，所以继续乘以9，这时候结果是3次方；而后x继续乘积就是4次方，但是移位结果为0；所以不进行乘积；继续乘方为8次方，末尾为1.所以结果为11次方。程序结束。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    double myPow(double x, int n) {
        double ans = 1;
        unsigned long long p;
        if (n < 0){
            x = 1 / x;
            p = -n;
        }else{
            p = n;
        }
        while(p){
            if (p & 1){
                ans *= x;
            }
            x *= x;
            p >>= 1;
        }
        return ans;
        
    }
};

发表于 | 分类于

Find the Derangement of An Array

题目描述：

给定一个数字n，表示用[1..n]组成排列组合。要求找到所有满足对应位置与其数不对应的情况。

例子：

具体描述见LeetCode634

解题思路：

主要的思路是动态规划，其中找到的规律是D[N] = (N - 1)*(D[N - 1] + D[N - 2]);我们可以理解为如下的解法：在对N个数进行排列时，第一个位置可以是N-1中选择，假设选择了X,而对应的X的位置上的位置可能是1，这种情况下一共有D[N - 2]可能；如果不是1的情况下则有D[N - 2]可能。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int findDerangement(int n) {
        unsigned long long n1 = 0;
        unsigned long long n2 = 1;
        if (n == 1) return n1;
        if (n == 2) return n2;
        unsigned long long  res = 0;
        for (int i = 2; i < n; i++){
            res = (i)*(n1 + n2) % (1000000000 + 7);
            n1 = n2;
            n2 = res;
        }
        return res;       
    }
};