发表于 | 更新于 | 分类于

题目描述

在二维平面上，有一个机器人从原点 (0, 0) 开始。给出它的移动顺序，判断这个机器人在完成移动后是否在 (0, 0) 处结束。

移动顺序由字符串表示。字符 move[i] 表示其第 i 次移动。机器人的有效动作有 R（右），L（左），U（上）和 D（下）。如果机器人在完成所有动作后返回原点，则返回 true。否则，返回 false。

注意：机器人“面朝”的方向无关紧要。 “R” 将始终使机器人向右移动一次，“L” 将始终向左移动等。此外，假设每次移动机器人的移动幅度相同。

示例 1:

输入: "UD"
输出: true
解释：机器人向上移动一次，然后向下移动一次。所有动作都具有相同的幅度，因此它最终回到它开始的原点。因此，我们返回 true。

示例 2:

输入: "LL"
输出: false
解释：机器人向左移动两次。它最终位于原点的左侧，距原点有两次 “移动” 的距离。我们返回 false，因为它在移动结束时没有返回原点。

题目分析

通过哈希表存储每个动作的次数, L和R的次数相等并且U和D的次数相等则会返回原点.

源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    bool judgeCircle(string moves) {
        unordered_map<char, int> m;
        m['L'] = 0;
        m['R'] = 0;
        m['U'] = 0;
        m['D'] = 0;
        for(int i=0; i<moves.size(); ++i) {
            m[moves[i]] += 1;
        }
        return m['L'] == m['R'] && m['U'] == m['D'];
    }
};

发表于 | 更新于 | 分类于

题目描述

给定两个表示复数的字符串。

返回表示它们乘积的字符串。注意，根据定义 i2 = -1 。

示例 1:

输入: "1+1i", "1+1i"
输出: "0+2i"
解释: (1 + i) * (1 + i) = 1 + i2 + 2 * i = 2i ，你需要将它转换为 0+2i 的形式。

示例 2:

输入: "1+-1i", "1+-1i"
输出: "0+-2i"
解释: (1 - i) * (1 - i) = 1 + i2 - 2 * i = -2i ，你需要将它转换为 0+-2i 的形式。

题目分析

没啥可分析的…就找到四个数字乘下带公式就可以…

源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    string complexNumberMultiply(string a, string b) {
        int z, x, c, v;
        string s;
        z = atoi(a.substr(0, a.find('+')).c_str());
        s = a.substr(a.find('+')+1);
        s.pop_back();
        x = atoi(s.c_str());
        c = atoi(b.substr(0, b.find('+')).c_str());
        s = b.substr(b.find('+')+1);
        s.pop_back();
        v = atoi(s.c_str());
        string res = to_string(z*c-x*v) + "+" + to_string(z*v+x*c) + "i";
        return res;
    }
};

发表于 | 更新于 | 分类于

题目描述

给定两个字符串 s 和 t，它们只包含小写字母。

字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。

请找出在 t 中被添加的字母。

示例:

输入：
s = "abcd"
t = "abcde"

输出：
e

解释：
'e' 是那个被添加的字母。

题目分析

不用位运算的做法是遍历字符串t, 将t中每一个字符的出现次数存入哈希表, 而后遍历字符串s, 减去每个字符出现次数, 找到那个出现次数为1的字符.

使用位运算做法则是初始化结果res为0, 对s和t的每一位与res取异或, 最后res的值便是多出来的字符.

源码

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
class Solution { // 不用位运算
public:
    unordered_map<char, int> m;
    string::iterator it;
    char findTheDifference(string s, string t) {
        for(char c='a'; c<='z'; ++c) { // 初始化哈希表m
            m[c] = 0;
        }

        it = t.begin();

        while(it != t.end()) {
            m[*it] = m[*it]+1;
            it++;
        }

        it = s.begin();

        while(it != s.end()) {
            m[*it] = m[*it]-1;
            it++;
        }

        for(char c='a'; c<='z'; ++c) {
            if(m[c] != 0) return c;
        }
        return 0;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
class Solution { // 使用位运算
public:
    char findTheDifference(string s, string t) {
        char c = 0; // 初始化结果res为0
        s.push_back(0); // 统一s和t的字符数
        for(int i=0; i<t.size(); ++i) {
            c ^= s[i]; // 对res和s[i]取异或
            c ^= t[i]; // 对res和t[i]取异或
        }
        return c;
    }
};

发表于 | 更新于 | 分类于

题目描述

给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。

示例 1:

输入: 2
输出: [0,1,1]

示例 2:

输入: 5
输出: [0,1,1,2,1,2]

题目分析

假如某一个数的二进制1位数是n, 则它左移一位的数的1位数也是n, 这样我们便可以使用筛法来避免重复运算.

源码

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
int finded[100000] = {0};

class Solution {
public:
    int dp(int num, int max) {
        if(finded[num] == 0) {
            int t = num, sum = 0;
            while(t != 0) {
                sum += t & 1;
                t>>=1;
            }
            t = num;
            while(t <= max) {
                finded[t] = sum;
                t <<= 1;
            }
        }
        return finded[num];
    }

    vector<int> countBits(int num) {
        vector<int> res;
        res.push_back(0);
        for(int i=1; i<=num; ++i) {
            res.push_back(dp(i, num));
        }
        return res;
    }
};

发表于 | 更新于 | 分类于

题目描述

给定一个包含 0, 1, 2, …, n 中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。

示例 1:

输入: [3,0,1]
输出: 2

示例 2:

输入: [9,6,4,2,3,5,7,0,1]
输出: 8

题目分析

初始化结果为0, 对每一位和结果取异或, 最后所得的结果便是缺失的数字.

源码

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int res = 0;
        for(int i=0; i<nums.size(); ++i) {
            res ^= i+1;
            res ^= nums[i];
        }
        return res;
    }
};

发表于 | 更新于 | 分类于

题目描述

给定一个二叉树，检查它是否是镜像对称的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

   1
  / \
 2   2
/ \ / \
3  4 4  3

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

  1
 / \
 2   2
 \    \
  3    3

题目分析

题目可以用递归和递推两种方法解决, 递归方法思路如下:

对根节点下两棵子树进行判断, 两棵子树的根节点值相等并且子树的两颗子树也为对称则为对称树.

源码(递归)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    bool isTwoSym(TreeNode* l, TreeNode* r) {
        if(l == NULL || r == NULL) { // 两个节点中含有NULL节点
            return l == r;
        }else {
            return l->val == r->val && isTwoSym(l->left, r->right) && isTwoSym(l->right, r->left);
        }
    }
    bool isSymmetric(TreeNode* root) {
        if(root == NULL) return true;
        if(root->left == NULL && root->right == NULL) return true;
        // ↑ 单根节点情况
        if((root->left == NULL && root->right != NULL) || (root->right == NULL && root->left != NULL)) return false;
        // ↑ 根节点下只有一个节点情况
        return isTwoSym(root->left, root->right);
    }
};

源码(深度优先搜索)

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:
    bool isSymmetric(TreeNode* root) {
        if(root == NULL) return true; // 如果根节点是空节点则返回true
        stack<TreeNode*> st1, st2; // 将节点储存在栈中
        st1.push(root->left); // 将根节点左右的节点压入栈中
        st2.push(root->right);
        while(!st1.empty() && !st2.empty()) { // 在任意一个栈为空时停止循环
            TreeNode* cur1 = st1.top();
            TreeNode* cur2 = st2.top();
            st1.pop();
            st2.pop();
            if((cur1 == NULL && cur2 != NULL) || (cur1 != NULL && cur2 == NULL)) return false;
            if(cur1 != NULL) {
                if(cur1->val != cur2->val) return false;
                st1.push(cur1->left); // 左节点先压入左 后压入右
                st1.push(cur1->right);
                st2.push(cur2->right); // 右节点先压入右 后压入左
                st2.push(cur2->left);
            }
        }
        return true;
    }
};

发表于 | 更新于 | 分类于

题目描述

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

示例 1:

1
2
输入: [1,3,5,6], 5
输出: 2

示例 2:

1
2
输入: [1,3,5,6], 2
输出: 1

示例 3:

1
2
输入: [1,3,5,6], 7
输出: 4

示例 4:

1
2
输入: [1,3,5,6], 0
输出: 0

题目分析

由于是有序数组, 则先比较目标数字与两侧极值的, 确定目标数字是否在数组之中, 而后从第一个元素开始迭代, 如果target > nums[i] 并且 <= nums[i+1]则返回i+1;

源码

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        if(target <= nums[0]) return 0;
        if(target > nums[nums.size()-1]) return nums.size();
        if(target == nums[nums.size()-1]) return nums.size()-1;
        for(int i=0; i<nums.size(); ++i) {
            if(nums[i] < target && nums[i+1] >= target) return i+1;
        }
        return -1;
    }
};

发表于 | 更新于 | 分类于

题目描述

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串，判断字符串是否有效。

有效字符串需满足：

1
2
3
1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 注意空字符串可被认为是有效字符串。

示例 1:

1
2
输入: "()"
输出: true

示例 2:

1
2
输入: "()[]{}"
输出: true

示例 3:

1
2
输入: "(]"
输出: false

示例 4:

1
2
输入: "([)]"
输出: false

示例 5:

1
2
输入: "{[]}"
输出: true

题目分析

使用栈来读取每个括号, 如果栈顶的括号与将压入的括号相对, 则弹出栈顶元素, 否则入栈.

最后检查是否栈为空, 如非空则为非法字符串.

源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool isValid(string s) {
        if(s.size()%2 != 0) return false;
        // 如果字符串字符数目为奇数则一定有单个的括号
        stack<char>* st = new stack<char>(); // 新建指针以便结束时删除
        st->push('1');
        for(int i=0; i<s.size(); ++i) {
            if(st->top() == s[i]-1 || st->top() == s[i]-2) {
                st->pop();
            }else {
                st->push(s[i]);
            }
        }
        bool a = st->top() == '1';
        delete st;
        return a;
    }
};

发表于 | 更新于 | 分类于

题目描述

罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。

1
2
3
4
5
6
7
8
字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。

数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

1
2
3
I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。

给定一个罗马数字，将其转换成整数。输入确保在 1 到 3999 的范围内。

示例 1:

1
2
输入: "III"
输出: 3

示例 2:

1
2
输入: "IV"
输出: 4

示例 3:

1
2
输入: "IX"
输出: 9

示例 4:

1
2
3
输入: "LVIII"
输出: 58
解释: L = 50, V= 5, III = 3.

示例 5:

1
2
3
输入: "MCMXCIV"
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.

题目分析

题中可知如果某一位字母的下一位比其本身大, 则是一个合成数, 例如CM, XC, IV等.

源码

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
class Solution {
public:
    unordered_map<char, int> m; // 用哈希表储存每个字母所对应的数字
    // 因为不需要遍历表, 所以使用哈希表提高读取速度.
    int romanToInt(string s) {
        m['I'] = 1;
        m['V'] = 5;
        m['X'] = 10;
        m['L'] = 50;
        m['C'] = 100;
        m['D'] = 500;
        m['M'] = 1000;
        int result = 0; // 数字总和
        for(int i=0; i<s.length(); ++i) { // 遍历输入的字符串
            if(m[s[i]] < m[s[i+1]]) { // 如果某个字母的下一个字母数字要比其大则为合成数
                result += (m[s[i+1]] - m[s[i]]);
                // cout<<(m[s[i+1]] - m[s[i]])<<" ! "<<i<<endl;
                ++i; // 避免重复遍历
                continue;
            }
            result += m[s[i]];
            // cout<<m[s[i]]<<" "<<i<<endl;
        }
        return result;
    }
};

发表于 | 更新于 | 分类于

题目描述

判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

示例 1:

1
2
输入: 121
输出: true

示例 2:

1
2
3
输入: -121
输出: false
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

示例 3:

1
2
3
输入: 10
输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数。

题目分析

首先负数一定不是回文数, 其次一位数一定是回文数. 两位数以上则可以取每一位数字后对比.

源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool isPalindrome(int x) {
        if(x<0) return false; //负数不是回文数.
        if(x<10) return true; //一位数是回文数.
        if(double(x)/10 == x/10) return false; //最后一位为0的不是回文数.
        int n = log10(x)+1; //取位数
        // cout<<n<<endl;
        unsigned int num = 0;
        for(int i=1; i<=n; ++i) {
            int temp = x%int(pow(10, i))/int(pow(10, i-1));
            num += temp*pow(10, n-i);
        }
        return num == x;
    }
};
0%