发表于 | 分类于

Max Consecutive Ones

题目描述：

给定一个数组中只包含着0和1，要求找到最长的连续的1的长度。

例子：

具体描述见LeetCode485

解题思路：

我们直接遍历数组，用flag标签表示遍历的位置。如果碰上了1，则找到当前连续1的长度，然后与上一个连续的1长度进行比较即可。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int findMaxConsecutiveOnes(vector<int>& nums) {
        int length = 0;
        int i = 0;
        while(i < nums.size()){
            if (nums[i] == 1){
                int tmp = 0;
                while(nums[i] == 1){
                    tmp++;
                    i++;
                }
                length = max(length, tmp);
            }else{
                i++;
            }
        }
        return length;
    }
};

发表于 | 分类于

Find the Duplicate Number

题目描述：

给定一个包含n+1个数的数组，数组中的数的范围是1到n；其中有且只有存在一个数重复，且可能重复多次。要求找到这个重复的数。

例子：

具体描述见LeetCode289

解题思路：

我们这边利用二分查找的方式来解题。既然存在一个重复的数，那对于中位数而言，重复的数肯定在数量较多的那一侧。所以我们每次只要遍历所有的数找到比中位数小的数的数量。根据统计的数量进行对low和high的调整即可。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int low = 1;
        int high = nums.size() - 1;
        int mid = 0;
        int count = 0;
        while(low < high){
            mid = low + (high - low) / 2;
            count = 0;
            for (int i = 0; i < nums.size(); i++){
                if (nums[i] <= mid) count++;
            }
            if (count > mid) high = mid;
            if (count <= mid) low = mid + 1;
        }
        return low;
    }
};

发表于 | 分类于

Combination Sum III

题目描述：

给定数组[1…..9]和数字k，要求返回数组中k个数和为n的所有组合。

例子：

具体描述见LeetCode216

解题思路：

主要的解题思路是深度优先搜索。我们用res保存最后的结果，用record保存当前访问过程的结果，k表示还需要访问数的个数，n表示剩余的和。当k和n都等于0的时候，把当前的访问结果保存下来；不符合的情况我们直接返回；而后需要确定继续下一层遍历的起始位置，我们需要判断当前的record是否为空，为空置为1，不为空置为尾部数据的下一个数即可。而后继续遍历。需要注意的地方在于我们push到record中后，当前深度优先搜索结束后需要pop出当前层push的数。

代码如下：

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:
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<vector<int>> res;
        vector<int> record;
        dfs(res, k, n, record);
        return res;
        
    }
    void dfs(vector<vector<int>>& res, int k, int n, vector<int>& record){
        if (k == 0 && n == 0){
            res.push_back(record);
            return;
        }
        if (n <= 0 || k == 0)
            return;
        int start = record.size() == 0 ? 1 : record.back() + 1;
        for (int i = start; i <= 9; i++){
            record.push_back(i);
            dfs(res, k - 1, n - i, record);
            record.pop_back();
        }
    }
};

发表于 | 分类于

Gray Code

题目描述：

给定一个整数n，要求返回n位格雷码的对应的数字的结果。

例子：

具体描述见LeetCode89

解题思路：

对于n位的格雷码结果，我们从末尾开始对每个结果加上1左移n-1位的结果然后添加到旧的结果中即可得到n+1位的格雷码的结果。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int> res(1, 0);
        
        for (int i = 0; i < n; i++){
            int cur = res.size();
            while(cur){
                cur--;
                int temp = res[cur];
                temp += (1 << i);
                res.push_back(temp);
            }
        }
        return res;
    }
};

发表于 | 分类于

Number of Islands

题目描述：

给定一个矩阵，其中1表示陆地，0表示水；要求找到矩阵中岛的数量。

例子：

具体描述见LeetCode200

解题思路：

本题中主要用的方法是深度优先搜索；我们对矩阵中的每个位置进行遍历，如果是1的情况下，我们先将岛的数量加1，然后遍历整个岛的所有位置将其标记为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
25
class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int count = 0;
        for (int i = 0; i < grid.size(); i++){
            for (int j = 0; j < grid[0].size(); j++){
                if (grid[i][j] == '1') count++;
                helper(grid, i, j);
            }
        }
        return count;
        
    }
    void helper(vector<vector<char>>& grid, int i, int j){
        if (i < 0 || j < 0 || i >= grid.size() || j >= grid[0].size()) return;
        if (grid[i][j] == '0') return;
        else {
            grid[i][j] = '0';
            helper(grid, i + 1, j);
            helper(grid, i, j + 1);
            helper(grid, i - 1, j);
            helper(grid, i, j - 1);
        }
    }
};

发表于 | 分类于

hammingDistance

题目描述：

给定两个数字，要求返回这两个数的二进制数对应位上不同的位置的个数。

例子：

具体描述见LeetCode461

解题思路：

具体思路是我们对输入的两个数进行异或操作，然后计算结果中1的个数即可。至于计算数字中1的个数，我们利用flag开始不断地左移，然后和结果进行与操作就可以判断每个位置上的情况了。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int hammingDistance(int x, int y) {
        int num = x ^ y;
        int count = 0;
        int flag = 1;
        while(flag){
            if (num & flag)
                count++;
            flag = flag << 1;
        }
        return count;
    }
};

发表于 | 分类于

Add Strings

题目描述：

给定两个代表数字的字符串，要求返回这两个数字和的结果。

例子：

具体描述见LeetCode415

解题思路：

主要的思路是想将字符串逆序，从低位开始加起；用carry来记录进位；然后找到较长的字符串的长度用于遍历的停止条件；其中一个小技巧是如果另外一个字符串已到末尾我们就用0来代替。需要注意的地方还有我们跳出遍历后需要判断当前的进位是否存在，以及我们需要对结果逆序再返回。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    string addStrings(string num1, string num2) {
        reverse(num1.begin(), num1.end());
        reverse(num2.begin(), num2.end());
        int carry = 0;
        string res;
        int length = num1.size() > num2.size() ? num1.size(): num2.size();
        int index = 0;
        while(index < length){
            int n1 = index >= num1.size() ? 0 : num1[index] - '0';
            int n2 = index >= num2.size() ? 0 : num2[index] - '0';
            int sum = n1 + n2 + carry;
            char tmp = '0' + sum % 10;
            res += + tmp;
            carry = sum / 10;
            index++;
        }
        if (carry == 1) res += '1';
        reverse(res.begin(), res.end());
        return res;
    }
};

发表于 | 分类于

Is Power of Num

题目描述：

给定一个数字，要求判断这个数字是否是2的幂次所得到的。同理，我们判断这个数是不是3和4的幂次所得到。

例子：

具体描述见LeetCode231、LeetCode326和LeetCode342

解题思路：

解题的思路都是类似的，我们将数字转化为对应的n进制的数；在这个数是对应的幂次的情况下，首位是1，且其他位数全是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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Solution {
public:
    bool isPowerOfTwo(int n) {
        if (n <= 0) return false;
        string res;
        while(n){
            char tmp = '0' + n % 2;
            res = tmp + res;
            n = n / 2;
        }
        for (int i = 1; i < res.size(); i++){
            if (res[i] == '1') return false;
        }
        return true;
    }
};
class Solution {
public:
    bool isPowerOfThree(int n) {
        if (n == 1) return true;
        if (n < 3) return false;
        string res;
        while(n){
            char tmp = '0' + n % 3;
            res = tmp + res;
            n = n / 3;
        }
        if (res[0] != '1') return false;
        for(int i = 1; i < res.size(); i++){
            if (res[i] != '0') return false;
        }
        return true;
    }
};
class Solution {
public:
    bool isPowerOfFour(int num) {
        if (num == 1) return true;
        if (num < 4) return false;
        string res;
        while(num){
            char tmp = '0' + num % 4;
            res = tmp + res;
            num /= 4;
        }
        if (res[0] != '1') return false;
        for (int i = 1; i < res.size(); i++){
            if (res[i] != '0') return false;
        }
        return true;
    }
};

发表于 | 分类于

Course Schedule III

题目描述：

给定一个数组，数组中包含的数据[a, b]; a代表着课程的所需时间，b代表这个课程必须在这个时间前完成。要求找到能完成最多课程的选课方法和数量。

例子：

具体描述见LeetCode630

解题思路：

这题主要用的想法是贪心；首先我们对数据进行排序，排序的规则是课程结束时间。然后我们利用一个multiset来保存当前选择的每个课程的时间长度和consume来记录我们当前使用的时间长度。然后遍历数组，如果加上当前课程不会超过结束时间就将其加入到multiset和consume中，如果已经超过的情况下，我们将保存课程时间的最后一个数据和当前的课程时间比较，如果较大的情况下，说明我们可以放弃上一个选择的课程然后选择当前课程。因为我们总是需要尽可能的在一个时间段内选择更多的花费时间长度小的课程这样我们就能选择更多的课程。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int scheduleCourse(vector<vector<int>>& courses) {
        sort(courses.begin(), courses.end(), [](vector<int> a, vector<int>b){ return a.back() < b.back();});
        multiset<int> cls;
        int consume = 0;
        
        for (int i = 0; i < courses.size(); i++){
            if (consume + courses[i].front() <= courses[i].back()){
                consume += courses[i].front();
                cls.insert(courses[i].front());
            }else if (*cls.rbegin() > courses[i].front()){
                consume += courses[i].front() - *cls.rbegin();
                cls.erase(--cls.end());
                cls.insert(courses[i].front());
            }
        }
        return cls.size();
    }
};

发表于 | 分类于

Intersection of Two Arrays II

题目描述：

给定两个数组，要求返回这两个数组之间的交集(重复元素也包括)。

例子：

具体描述见LeetCode350

解题思路：

对第一个数组构建哈希表，key为字符，value为出现的次数；然后遍历第二个字符串，如果遍历过程中该字符出现在哈希表中且出现的次数不为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:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        map<int, int>hash;
        vector<int> res;
        for (int i = 0; i < nums1.size(); i++){
            if (hash.find(nums1[i]) == hash.end()){
                hash.insert({nums1[i], 1});
            }else{
                hash[nums1[i]]++;
            }
        }//构建第一个数组的哈希表
        for (int j = 0; j < nums2.size(); j++){
            if (hash.find(nums2[j]) != hash.end() && hash[nums2[j]] != 0){
                res.push_back(nums2[j]);
                hash[nums2[j]]--;
                //如果出现在哈希表中，我们保存其到结果中并且将出现的次数减一
            }
        }
        return res;
    }
};