LeetCode 探索：发散你的思维 [389] 找不同 给定两个字符串 s 和 t，它们只包含小写字母。
字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。
请找出在 t 中被添加的字母。
解题思路：使用异或操作，两个字符串中成对的字符进行异或得到0，0再和多出来的一个字符c异或，则得到c
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 : char findTheDifference (string s, string t) { char res = 0 ; for (char c : s) res ^= c; for (char c : t) res ^= c; return res; } };
[392] 判断子序列 给定字符串 s 和 t ，判断 s 是否为 t 的子序列。你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长（长度 ~= 500, 000），而 s 是个短字符串（长度 <=100）。字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，”ace”是”abcde”的一个子序列，而”aec”不是）。
解题思路：以-1为起始点，每次从index + 1中找出t是否存在字符s[i]，若不存在，则返回false；循环退出的时候返回true。
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 : bool isSubsequence (string s, string t) { int index = -1 ; for (int i = 0 ; i < s.length(); i++) { index = t.find_first_of(s[i], index + 1 ); if (index == string ::npos) return false ; } return true ; } };
[401] 二进制手表 二进制手表顶部有 4 个 LED 代表小时（0-11），底部的 6 个 LED 代表分钟（0-59）。每个 LED 代表一个 0 或 1，最低位在右侧。给定一个非负整数 n 代表当前 LED 亮着的数量，返回所有可能的时间。
解题思路：暴力穷举，计算每一个情况出现的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 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 class Solution { public : int count (int n) { int res = 0 ; while (n != 0 ) { n = n & (n - 1 ); res++; } return res; } vector <string > readBinaryWatch (int num) { vector <string > res; for (int i = 0 ; i < 12 ; i++) { if (count(i) == num) res.push_back(to_string(i) + ":00" ); else { for (int j = 0 ; j < 60 ; j++) { if (count(i) + count(j) == num) res.push_back(to_string(i) + ":" + ((j < 10 ) ? "0" + to_string(j) : to_string(j))); } } } return 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 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 class Solution {public : vector <int > enumerate (int digit, int n, int limit) vector <int > ret; if (n == 0 ) { ret.push_back(0 ); return ret; } if (digit <= n) { int shift = (1 << digit) - 1 ; if (shift < limit) { ret.push_back(shift); } return ret; } vector <int > off = enumerate(digit - 1 , n, limit); for (int high: off) { int shift = high << 1 ; if (shift < limit) { ret.push_back(shift); } } vector <int > on = enumerate(digit - 1 , n - 1 , limit); for (int high: on) { int shift = (high << 1 ) + 1 ; if (shift < limit) { ret.push_back(shift); } } return ret; } vector <string > readBinaryWatch (int num) int min = num<4 ? num: 4 ; vector <string > ret; for (int i=0 ; i<=min; i++) { vector <int > hour = enumerate(4 , i, 12 ); vector <int > minute = enumerate(6 , num - i, 60 ); for (int h: hour) { for (int m: minute) { if (m >= 10 ) { string s = to_string(h) + ":" + to_string(m); ret.push_back(s); } else { string s = to_string(h) + ":0" + to_string(m); ret.push_back(s); } } } } return ret; } };
[404] 左叶子之和 计算给定二叉树的所有左叶子之和。
解题思路：迭代，使用队列对树进行遍历，当队列不为空时，执行循环
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 isLeaf (TreeNode *node) { return node->left == NULL && node->right == NULL ; } int sumOfLeftLeaves (TreeNode *root) { if (root == NULL ) return 0 ; int sum = 0 ; queue <TreeNode *> q; q.push(root); while (!q.empty()) { TreeNode *node = q.front(); q.pop(); if (node->left != NULL ) { if (isLeaf(node->left)) sum += node->left->val; else q.push(node->left); } if (node->right != NULL ) q.push(node->right); } return sum; } };
[405] 数字转换为十六进制数 给定一个整数，编写一个算法将这个数转换为十六进制数。对于负整数，我们通常使用 补码运算 方法。
注意:
十六进制中所有字母(a-f)都必须是小写。 十六进制字符串中不能包含多余的前导零。如果要转化的数为0，那么以单个字符’0’来表示；对于其他情况，十六进制字符串中的第一个字符将不会是0字符。 给定的数确保在32位有符号整数范围内。 不能使用任何由库提供的将数字直接转换或格式化为十六进制的方法。
解题思路：将int类型转换为unsigned int类型计算，会自动对负数进行补码表示
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 : string toHex (int num) { if (num == 0 ) return "0" ; string map [16 ] = {"0" , "1" , "2" , "3" , "4" , "5" , "6" , "7" , "8" , "9" , "a" , "b" , "c" , "d" , "e" , "f" }; string res = "" ; unsigned int n = num; while (n != 0 ) { int temp = n % 16 ; n /= 16 ; res = map [temp] + res; } return res; } };
[409] 最长回文串 给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。
在构造过程中，请注意区分大小写。比如 “Aa” 不能当做一个回文字符串。
解题思路：使用哈希表
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 class Solution { public : int longestPalindrome (string s) { int sum = 0 ; int table[128 ] = {0 }; for (char c : s) table[c]++; int add = 0 ; for (int i = 65 ; i <= 122 ; i++) { if (table[i] > 0 ) { if (table[i] % 2 == 0 ) sum += table[i]; else { sum += (table[i] - 1 ); add = 1 ; } } } return sum + add; } };
[412] Fizz Buzz 写一个程序，输出从 1 到 n 数字的字符串表示。
如果 n 是3的倍数，输出“Fizz”；
如果 n 是5的倍数，输出“Buzz”；
如果 n 同时是3和5的倍数，输出 “FizzBuzz”。
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 class Solution { public : vector <string > fizzBuzz (int n) { vector <string > res; for (int i = 1 ; i <= n; i++) { if (i % 3 == 0 && i % 5 == 0 ) res.push_back("FizzBuzz" ); else if (i % 3 == 0 ) res.push_back("Fizz" ); else if (i % 5 == 0 ) res.push_back("Buzz" ); else res.push_back(to_string(i)); } return res; } };
[414] 第三大的数 给定一个非空数组，返回此数组中第三大的数。如果不存在，则返回数组中最大的数。要求算法时间复杂度必须是O(n)。
解题思路：利用set集合的元素的唯一性和有序性
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 thirdMax (vector <int > &nums) { set <int > table (nums.begin(), nums.end()) auto it = table.end(); if (table.size() >= 3 ) { it--; it--; } return *(--it); } };
解题思路：用三个变量来储存第一第二第三大的数，并同时替换
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 class Solution { public : int thirdMax (vector <int > &nums) { long first = -2147483653 ; long second = -2147483654 ; long third = -2147483655 ; for (int i = 0 ; i < nums.size(); i++) { if (nums[i] > first) { third = second; second = first; first = nums[i]; } else if (nums[i] < first && nums[i] > second) { third = second; second = nums[i]; } else if (nums[i] < second && nums[i] > third) { third = nums[i]; } } return (third < -2147483648 ) ? (int )first : (int )third; } };
[415] 字符串相加 给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和。
注意：
num1 和num2 的长度都小于 5100. num1 和num2 都只包含数字 0-9. num1 和num2 都不包含任何前导零。 你不能使用任何內建 BigInteger 库， 也不能直接将输入的字符串转换为整数形式。
解题思路：
算法流程： 设定 i，j 两指针分别指向 num1，num2 尾部，模拟人工加法；
计算进位： 计算 carry = tmp // 10，代表当前位相加是否产生进位；
添加当前位： 计算 tmp = n1 + n2 + carry，并将当前位 tmp % 10 添加至 res 头部；
索引溢出处理： 当指针 i或j 走过数字首部后，给 n1，n2 赋值为 00，相当于给 num1，num2 中长度较短的数字前面填 00，以便后续计算。
当遍历完 num1，num2 后跳出循环，并根据 carry 值决定是否在头部添加进位 11，最终返回 res 即可。
时间复杂度 O(max(M, N))O(max(M, N))：其中 MM，NN 为 22 数字长度，按位遍历一遍数字（以较长的数字为准）；空间复杂度 O(1)O(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 28 29 30 31 32 33 class Solution { public : string addStrings (string num1, string num2) { string res = "" ; int i = num1.length() - 1 , j = num2.length() - 1 ; int carry = 0 ; while (i >= 0 || j >= 0 ) { int n1 = (i >= 0 ) ? num1[i] - '0' : 0 ; int n2 = (j >= 0 ) ? num2[j] - '0' : 0 ; int temp = n1 + n2 + carry; carry = temp / 10 ; res = to_string(temp % 10 ) + res; i--; j--; } if (carry == 1 ) res = "1" + res; return res; } };
[434] 字符串中的单词数 统计字符串中的单词个数，这里的单词指的是连续的不是空格的字符。
请注意，你可以假定字符串里不包括任何不可打印的字符。
解题思路：即使用空格分隔字符串，但需要注意头尾的处理
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 : int countSegments (string s) { int count = 0 ; int pos = s.find_first_not_of(' ' , 0 ); int last = s.find_first_of(' ' , pos); while (pos != string ::npos && last != string ::npos) { pos = s.find_first_not_of(' ' , last + 1 ); last = s.find_first_of(' ' , pos); count++; } if (pos != string ::npos && last == string ::npos) count++; return count; } };
