发表于 | 分类于

Count Numbers with Unique Digits

题目描述：

给定一个表示位数的数字n,返回n位数中所有位数均不相同的数字的个数。

例子：

具体描述见LeetCode357

解题思路：

除了n在0和1的情况下特殊对待以外。我们找到每种位数下的数字的可能性进行相加即可得到最后的结果。其中在cal函数中我们定义了res和j初始值均为9，表示首位的可能为1~9，次位的可能在选取1~9之后加上0依旧有9种可能。而后根据排列组合的公式即可得到我们的结果。

代码如下：

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 countNumbersWithUniqueDigits(int n) {
        if (n == 0) return 1;
        if (n == 1) return 10;
        int pre = 10;
        int next = 0;
        for (int i = 1; i < n; i++){
            next = pre + cal(i);
            pre = next;
        }
        return next;
    }
    int cal(int count){
        int res = 9;
        int j = 9;
        while(count != 0){
            res = res * j;
            j = j - 1;
            count--;
        }
        return res;
    }
};

发表于 | 分类于

Add Digits

题目描述：

给定一个数，不断的将其所有位数相加的和作为新的数直到这个数的长度为1为止。

例子：

具体描述见LeetCode258

解题思路：

按照字面方式进行解题即可

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int addDigits(int num) {
        int res = 0;
        while(to_string(num).size() != 1){
            string tmp = to_string(num);
            for (int i = 0; i < tmp.size(); i++){
                res += tmp[i] - '0';
            }//对每一位数进行求和
            num = res;
            res = 0;//此处记得置0
        }
        return num;
    }
};

发表于 | 分类于

Convert a Number to Hexadecimal

题目描述：

给定一个数将其转化为16进制的形式。

例子：

具体描述见LeetCode405

解题思路：

主要的思路就是不断的求余和除法。其中需要注意的有两点；其一这样得到的16进制与我们想要的结果是逆序相反的；其二是负数的处理在利用unsigned int对原始数据进行处理即可。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    string toHex(int num) {
        unsigned int n = num;
        string res;
        while(n){
            int b = n % 16;
            res += (b < 10) ? ('0' + b):('a' + b - 10);
            n /= 16;
        }
        reverse(res.begin(), res.end());
        
        return res == "" ? "0" : res;
    }
};

发表于 | 分类于

First Unique Character in a String

题目描述：

给定一个字符串，找到字符串中第一个只出现一次的那个字符。

例子：

具体描述见LeetCode387

解题思路：

我们用一个数组记录数最后位置出现位置信息，用一个数组记录字符出现的次数信息。而后再遍历次数数组找到最早出现的那个字符位置即可。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int firstUniqChar(string s) {
        int res = -1;
        vector<int> vec(26, -1);
        vector<int> num(26, 0);
        for (int i = 0; i < s.size(); i++){
            if (vec[s[i] - 'a'] == -1) vec[s[i] - 'a'] = i;
            num[s[i] - 'a']++;
        }
        for (int i = 0; i < 26; i++){
            if (num[i] == 1 && res == - 1) res = vec[i];
            else if (num[i] == 1 && res != -1) res = min(res, vec[i]);
        }
        return res;
    }
};

发表于 | 分类于

Number of Boomerangs

题目描述：

给定一组表示二维坐标的数组，要求找到所有的三元组(i,j,k)；其中i到j和i到k的距离相同。

例子：

具体描述见LeetCode447

解题思路：

首先我们定义外循环找到第一个点i,在此基础之上我们循环剩下的所有节点,用哈希表记录下剩下节点到i节点的距离的长度和对应的次数；而后对应节点i的循环结束之后我们找到哈希表中出现超过1次的距离，并根据公式将对应的可能加入到结果中即可。

代码如下：

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
class Solution {
public:
    int numberOfBoomerangs(vector<pair<int, int>>& points) {
        int res = 0;
        
        for (int i = 0; i < points.size(); i++){
            unordered_map<int, int> hash;
            
            for (int j = 0; j < points.size(); j++){
                if (j == i) continue;
                int dy = points[j].second - points[i].second;
                int dx = points[j].first - points[i].first;
                
                int key = dx * dx;
                key += dy * dy;
                hash[key]++;
            }
            for (auto k : hash){
                if (k.second > 1){
                    res += k.second * (k.second - 1);
                }
            }
        }
        return res;
        
    }
};

发表于 | 分类于

Nth Digit

题目描述：

给定一个数字n，要求找到从1,2,3,4,….排列中的第n位数字。

例子：

具体描述见LeetCode400

解题思路：

首先我们用digit变量来寻找到这一位数字所在数的位数是多少。通过循环不断的进行n的减少直到n可能小于0；此时我们就知道了这位数的位数；根据剩下的n来找到对应的数字；最后找到对应位数上的数字即可。详细解法可以见discuss

代码如下：

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 findNthDigit(int n) {
        long base = 9;
        int digits = 1;
        while(n - digits * base > 0){
            n -= base * digits;
            base = base * 10;
            digits++;
        }//此时已经得到了位数
        int index = n % digits;
        if (index == 0)
            index = digits;
        long num = 1;
        for (int i = 1; i < digits; i++)
            num *= 10;
        num += (index == digits) ? n / digits - 1 : n / digits;
        //找到对应的数字
        for (int i = index; i < digits; i++)
            num /= 10;
        return num % 10;
        //找到对应位数的数字
    }
};

发表于 | 分类于

Subarray Sum Equals K

题目描述：

给定一个数组和一个目标值K，要求找到所有子数组的和为K的可能。

例子：

具体描述见LeetCode560

解题思路：

我们用哈希表记录下每次加上一个数组中的数的累加和以及出现的次数；然后每次加完之后我们可以通过key为累加值减去k判断当前是否能够构成一个字数粗和为k。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int cnt = 0;
        map<int, int> hash;
        hash[0]++;
        int cum = 0;
        for (int i = 0; i < nums.size(); i++){
            cum += nums[i];
            cnt += hash[cum - k];
            hash[cum]++;
        }
        return cnt;
    }
};

发表于 | 分类于

Island Perimeter

题目描述：

给定一个矩阵1表示陆地，0表示海洋，要求找到陆地的周长。

例子：

具体描述见LeetCode463

解题思路：

解题的思路是我们找到所有的1的格子的数量；并且在遍历过程中我们记录下当前格子上方以及左侧格子是否为1；为1即表示两个1之间相邻。根据记录下来的1的格子的数量和相邻的数量即可得到周长。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int islandPerimeter(vector<vector<int>>& grid) {
        int res = 0;
        int repeat = 0;
        for (int i = 0; i < grid.size(); i++){
            for (int j = 0; j < grid[0].size(); j++){
                if (grid[i][j] == 1){
                    res++;
                    if (i != 0 && grid[i - 1][j] == 1) repeat++;
                    if (j != 0 && grid[i][j - 1] == 1) repeat++;
                }
            }
        }
        return 4 * res - 2 * repeat;
        
    }
};

发表于 | 分类于

Find the Duplicate Number

题目描述：

给定一个数组长度为n+1;其中只包含着1~n的数且只有一个数出现了重复，要求找到这个数。

例子：

具体描述见LeetCode287

解题思路：

我们考虑用二分查找的方式来找到这个数。我们先找到中间数mid;然后找到数组中找到小于等于mid数的个数；如果个数大于mid说明重复的数在low~mid之间。

代码如下：

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;
    }
};

发表于 | 分类于

Merge Two Binary Trees

题目描述：

将两棵二叉树进行合并；如果都有对应位置节点就将节点上的数值相加；如果均为空则为空；如果只有一个不为空；将不为空的位置合并到结果中。

例子：

具体描述见LeetCode617

解题思路：

利用递归的思路来解题；如果只有一方为空的情况下，返回那个非空的一方节点；如果两个节点都不为空的情况下；将对应位置的值相加后合并左右子树即可。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if (!t1 || !t2) return !t1 ? t2 : t1;
        else if (t1 && t2){
            t1->val += t2->val;
            t1->left = mergeTrees(t1->left, t2->left);
            t1->right = mergeTrees(t1->right, t2->right);
            return t1;
        }
        
    }
};