CPP
728. Self Dividing Numbers
Easy
A self-dividing number is a number that is divisible by every digit it contains.
For example, 128 is a self-dividing number because 128 % 1 == 0, 128 % 2 == 0, and 128 % 8 == 0.
Also, a self-dividing number is not allowed to contain the digit zero.
Given a lower and upper number bound, output a list of every possible self dividing number, including the bounds if possible.
Example 1:
Input:
left = 1, right = 22
Output: [1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 15, 22]
Note: The boundaries of each input argument are 1 <= left <= right <= 10000.
[3]:
// 很慢因為 selfDividing 檢查了所有 digit。其實只要有一個不整除就可以踢掉這個數了
// getDigits 裡用 to_string 和 stoi 在整數和字串間切換
#include <iostream>
#include <vector>
#include <unordered_set>
{
auto getDigits = [](int num)
{
std::unordered_set<int> digits;
for(char& c : std::to_string(num))
digits.insert(std::stoi(std::string(1, c)));
return digits;
};
auto f = [=](int left, int right)
{
std::vector<int> res;
for (int n=left ; n<=right ; n++)
{
std::unordered_set<int> digits = getDigits(n);
bool selfDividing = true;
if (digits.find(0) != digits.end())
selfDividing = false;
else
for (const int& digit : digits)
selfDividing = (selfDividing && n%digit==0);
if (selfDividing)
res.push_back(n);
}
return res;
};
for (const int& n : f(1, 22))
std::cout << n << ", ";
}
1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 15, 22,
1281. Subtract the Product and Sum of Digits of an Integer
Easy
Given an integer number n, return the difference between the product of its digits and the sum of its digits.
Example 1:
Input: n = 234
Output: 15
Explanation:
Product of digits = 2 * 3 * 4 = 24
Sum of digits = 2 + 3 + 4 = 9
Result = 24 - 9 = 15
Constraints:
1 <= n <= 10^5
[19]:
#include <iostream>
#include <vector>
{
auto f = [](int n)
{
int sum = 0;
int prod = 1;
while (n>0)
{
int digit = n%10;
sum = sum + digit;
prod = prod*digit;
n = n/10;
}
return prod-sum;
};
std::cout << f(114) << std::endl;
}
-2
1512. Number of Good Pairs
Easy
Given an array of integers nums. A pair (i,j) is called good if nums[i] == nums[j] and i < j. Return the number of good pairs.
Example 1:
Input: nums = [1,2,3,1,1,3]
Output: 4
Explanation: There are 4 good pairs (0,3), (0,4), (3,4), (2,5) 0-indexed.
Constraints:
1 <= nums.length <= 100
1 <= nums[i] <= 100
[5]:
#include <iostream>
#include <vector>
{
auto f = [](std::vector<int>& nums)
{
int res = 0;
for(size_t j=0 ; j<nums.size() ; j++)
for(size_t i=0 ; i<j ; i++)
if (nums[i]==nums[j])
res++;
return res;
};
std::vector<int> nums = {1, 2, 3, 1, 1, 3};
std::cout << f(nums) << std::endl;
}
4
1470. Shuffle the Array
Easy
Given the array nums consisting of 2n elements in the form [x1,x2,…,xn,y1,y2,…,yn], return the array in the form [x1,y1,x2,y2,…,xn,yn].
Example 1:
Input: nums = [2,5,1,3,4,7], n = 3
Output: [2,3,5,4,1,7]
Explanation: Since x1=2, x2=5, x3=1, y1=3, y2=4, y3=7 then the answer is [2,3,5,4,1,7].
Constraints:
1 <= n <= 500
nums.length == 2n
1 <= nums[i] <= 10^3
[4]:
#include <iostream>
#include <vector>
{
auto f = [](std::vector<int>& nums, int n)
{
std::vector<int> res;
for (size_t i=0 ; i<n ; i++)
{
res.push_back(nums[i]);
res.push_back(nums[i+n]);
}
return res;
};
std::vector<int> nums = {2, 5, 1, 3, 4, 7};
for(const int& n : f(nums, 3))
std::cout << n << ", ";
}
2, 3, 5, 4, 1, 7,
1480. Running Sum of 1d Array
Easy
Given an array nums. We define a running sum of an array as runningSum[i] = sum(nums[0]…nums[i]). Return the running sum of nums.
Example 1:
Input: nums = [1,2,3,4]
Output: [1,3,6,10]
Explanation: Running sum is obtained as follows: [1, 1+2, 1+2+3, 1+2+3+4].
Constraints:
1 <= nums.length <= 1000
-10^6 <= nums[i] <= 10^6
[3]:
// std::partial_sum 比 native 寫法慢一點
#include <iostream>
#include <vector>
#include <numeric>
{
auto f = [](std::vector<int>& nums)
{
std::partial_sum(nums.begin(), nums.end(), nums.begin());
return nums;
};
std::vector<int> nums = {1, 2, 3, 4};
for (int n : f(nums))
std::cout << n << ", ";
}
1, 3, 6, 10,
[3]:
#include <iostream>
#include <vector>
{
auto f = [](std::vector<int>& nums)
{
int sum = 0;
for (int& n : nums)
{
int m = n;
n += sum;
sum += m;
}
return nums;
};
std::vector<int> nums = {1, 2, 3, 4};
for (int n : f(nums))
std::cout << n << ", ";
}
1, 3, 6, 10,
344. Reverse String
Easy
Write a function that reverses a string. The input string is given as an array of characters char[].
Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
You may assume all the characters consist of printable ascii characters.
Example 1:
Input: ["h","e","l","l","o"]
Output: ["o","l","l","e","h"]
[8]:
// std::reverse
#include <iostream>
#include <algorithm>
#include <vector>
{
auto f = [](std::vector<char>& s)
{
std::reverse(s.begin(), s.end());
};
std::vector<char> s = {'h', 'e', 'l', 'l', 'o'};
f(s);
for (char c : s)
std::cout << c;
}
olleh
[5]:
// for & std::swap
#include <iostream>
#include <algorithm>
#include <vector>
{
auto f = [](std::vector<char>& s)
{
for(int i=0, j=s.size()-1 ; i<j ; std::swap(s[i++],s[j--]));
};
std::vector<char> s = {'h', 'e', 'l', 'l', 'o'};
f(s);
for (char c : s)
std::cout << c;
}
olleh
557. Reverse Words in a String III
Easy
Given a string, you need to reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order.
Example 1:
Input: "Let's take LeetCode contest"
Output: "s'teL ekat edoCteeL tsetnoc"
Note: In the string, each word is separated by single space and there will not be any extra space in the string.
把被空白格開的字一個一個倒過來
[3]:
#include <iostream>
#include <algorithm>
#include <memory>
#include <string>
{
auto f = [](std::string s)
{
if (s.size()==0)
return s;
else
{
s += " ";
size_t i = 0, j = 0;
for (size_t k=0 ; k<s.size() ; k++)
{
if (s[k]==' ')
{
for (j=k-1 ; i<j ; std::swap(s[i++], s[j--]));
i = j = k+1;
}
}
s.pop_back();
return s;
}
};
std::cout << f("Let's take LeetCode contest") << std::endl;
}
s'teL ekat edoCteeL tsetnoc
657. Robot Return to Origin
Easy
There is a robot starting at position (0, 0), the origin, on a 2D plane. Given a sequence of its moves, judge if this robot ends up at (0, 0) after it completes its moves.
The move sequence is represented by a string, and the character moves[i] represents its ith move. Valid moves are R (right), L (left), U (up), and D (down). If the robot returns to the origin after it finishes all of its moves, return true. Otherwise, return false.
Note: The way that the robot is “facing” is irrelevant. “R” will always make the robot move to the right once, “L” will always make it move left, etc. Also, assume that the magnitude of the robot’s movement is the same for each move.
Example 1:
Input: moves = "UD"
Output: true
Explanation: The robot moves up once, and then down once. All moves have the same magnitude, so it ended up at the origin where it started. Therefore, we return true.
Constraints:
1 <= moves.length <= 2 * 10^4
moves only contains the characters 'U', 'D', 'L' and 'R'.
[1]:
#include <iostream>
#include <string>
{
auto f = [](std::string moves)
{
int ud = 0, lr = 0;
for (char c : moves)
{
switch(c){
case 'U': ud += 1; break;
case 'D': ud -= 1; break;
case 'L': lr -= 1; break;
case 'R': lr += 1; break;
}
}
return (ud==0 && lr==0);
};
std::cout << f("UD") << std::endl;
}
1
1309. Decrypt String from Alphabet to Integer Mapping
Easy
Given a string s formed by digits (‘0’ - ‘9’) and ‘#’ . We want to map s to English lowercase characters as follows:
Characters ('a' to 'i') are represented by ('1' to '9') respectively.
Characters ('j' to 'z') are represented by ('10#' to '26#') respectively.
Return the string formed after mapping.
It’s guaranteed that a unique mapping will always exist.
Example 1:
Input: s = "10#11#12"
Output: "jkab"
Explanation: "j" -> "10#" , "k" -> "11#" , "a" -> "1" , "b" -> "2".
Constraints:
1 <= s.length <= 1000
s[i] only contains digits letters ('0'-'9') and '#' letter.
s will be valid string such that mapping is always possible.
[16]:
#include <iostream>
#include <string>
#include <unordered_map>
{
auto f = [](std::string s)
{
std::unordered_map<std::string, std::string> map = {{"1", "a"}, {"2", "b"}, {"3", "c"}, {"4", "d"}, {"5", "e"}, {"6", "f"}, {"7", "g"}, {"8", "h"}, {"9", "i"}, {"10#", "j"}, {"11#", "k"}, {"12#", "l"}, {"13#", "m"}, {"14#", "n"}, {"15#", "o"}, {"16#", "p"}, {"17#", "q"}, {"18#", "r"}, {"19#", "s"}, {"20#", "t"}, {"21#", "u"}, {"22#", "v"}, {"23#", "w"}, {"24#", "x"}, {"25#", "y"}, {"26#", "z"}};
std::string res;
std::string::reverse_iterator it=s.rbegin();
while(it!=s.rend())
{
if (*it=='#'){
res = map[std::string({*(it+2), *(it+1), *it})] + res;
it+=3;
}else{
res = map[std::string({*it})] + res;
it+=1;
}
}
return res;
};
std::cout << f("10#11#12") << std::endl;
}
jkab
1436. Destination City
Easy
You are given the array paths, where paths[i] = [cityAi, cityBi] means there exists a direct path going from cityAi to cityBi. Return the destination city, that is, the city without any path outgoing to another city.
It is guaranteed that the graph of paths forms a line without any loop, therefore, there will be exactly one destination city.
Example 1:
Input: paths = [["London","New York"],["New York","Lima"],["Lima","Sao Paulo"]]
Output: "Sao Paulo"
Explanation: Starting at "London" city you will reach "Sao Paulo" city which is the destination city. Your trip consist of: "London" -> "New York" -> "Lima" -> "Sao Paulo".
Constraints:
1 <= paths.length <= 100
paths[i].length == 2
1 <= cityAi.length, cityBi.length <= 10
cityAi != cityBi
All strings consist of lowercase and uppercase English letters and the space character.
[1]:
// 把 iput 看成一個 2-column table，找出現在右邊但不在左邊 column 的城市
// std::set_difference 需要 sorted input 所以不能用。只能用 std::copy_if
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <unordered_set>
{
auto f = [](std::vector<std::vector<std::string>>& paths)
{
std::unordered_set<std::string> a, b;
std::vector<std::string> diff;
for (std::vector<std::string> path : paths)
{
a.insert(path[0]);
b.insert(path[1]);
}
std::copy_if(b.begin(), b.end(), std::back_inserter(diff), [&a] (std::string city) { return a.find(city) == a.end(); });
return diff[0];
};
std::vector<std::vector<std::string>> paths = {{"London","New York"}, {"New York","Lima"}, {"Lima","Sao Paulo"}};
std::cout << f(paths) << std::endl;
}
Sao Paulo
804. Unique Morse Code Words
Easy
International Morse Code defines a standard encoding where each letter is mapped to a series of dots and dashes, as follows: “a” maps to “.-“, “b” maps to “-…”, “c” maps to “-.-.”, and so on.
For convenience, the full table for the 26 letters of the English alphabet is given below:
[“.-“,”-…”,”-.-.”,”-..”,”.”,”..-.”,”–.”,”….”,”..”,”.—”,”-.-“,”.-..”,”–”,”-.”,”—”,”.–.”,”–.-“,”.-.”,”…”,”-“,”..-“,”…-“,”.–”,”-..-“,”-.–”,”–..”]
Now, given a list of words, each word can be written as a concatenation of the Morse code of each letter. For example, “cab” can be written as “-.-..–…”, (which is the concatenation “-.-.” + “.-” + “-…”). We’ll call such a concatenation, the transformation of a word.
Return the number of different transformations among all words we have.
Example:
Input: words = ["gin", "zen", "gig", "msg"]
Output: 2
Explanation:
The transformation of each word is:
"gin" -> "--...-."
"zen" -> "--...-."
"gig" -> "--...--."
"msg" -> "--...--."
There are 2 different transformations, "--...-." and "--...--.".
Note:
The length of words will be at most 100.
Each words[i] will have length in range [1, 12].
words[i] will only consist of lowercase letters.
[5]:
#include <iostream>
#include <string>
#include <vector>
#include <unordered_set>
#include <unordered_map>
{
auto f = [](std::vector<std::string>& words)
{
std::unordered_map<char, std::string> morse = {{'a', ".-"}, {'b', "-..."}, {'c', "-.-."}, {'d', "-.."}, {'e', "."}, {'f', "..-."}, {'g', "--."}, {'h', "...."}, {'i', ".."}, {'j', ".---"}, {'k', "-.-"}, {'l', ".-.."}, {'m', "--"}, {'n', "-."}, {'o', "---"}, {'p', ".--."}, {'q', "--.-"}, {'r', ".-."}, {'s', "..."}, {'t', "-"}, {'u', "..-"}, {'v', "...-"}, {'w', ".--"}, {'x', "-..-"}, {'y', "-.--"}, {'z', "--.."}};
std::unordered_set<std::string> transformed;
for (const std::string& word : words)
{
std::string code = "";
for (const char& c : word)
code += morse[c];
transformed.insert(code);
}
return transformed.size();
};
std::vector<std::string> words = {"uirqyr","ffqkc","joq","joq","joq"};
std::cout << f(words) << std::endl;
}
2
709. To Lower Case
Easy
Implement function ToLowerCase() that has a string parameter str, and returns the same string in lowercase.
Example 1:
Input: "Hello"
Output: "hello"
[2]:
// std::for_each 和 std::tolower 寫法
// 如果用 transform 就要寫 std::transform(str.begin(), str.end(), str.begin(), [](char c){ return std::tolower(c); });
// for_each 和 transform 的差別就是 for_each 的 unary fnc 是 void，transform 的一定要 output 然後被填進第三個 argument 所指向的位址
#include <algorithm>
#include <cctype>
#include <iostream>
#include <string>
{
auto f = [](std::string str)
{
// std::transform(str.begin(), str.end(), str.begin(), std::tolower); // 不能這樣寫；為什麼一定要寫一個 lambda？
// std::transform(str.begin(), str.end(), str.begin(), [](const char& c){ return std::tolower(c); }); // ok
std::for_each(str.begin(), str.end(), [](char& c){ c = std::tolower(c); });
return str;
};
std::cout << f("Hellow") << std::endl;
}
hellow
[6]:
// unordered_map 寫法
#include <iostream>
#include <string>
#include <unordered_map>
{
auto f = [](std::string str)
{
std::unordered_map<char, char> u = {{'A','a'}, {'B','b'}, {'C','c'}, {'D','d'}, {'E','e'},
{'F','f'}, {'G','g'}, {'H','h'}, {'I','i'}, {'J','j'}, {'K','k'}, {'L','l'}, {'M','m'},
{'N','n'}, {'O','o'}, {'P','p'}, {'Q','q'}, {'R','r'}, {'S','s'}, {'T','t'}, {'U','u'},
{'V','v'}, {'W','w'}, {'X','x'}, {'Y','y'}, {'Z','z'}};
for (std::string::iterator it=str.begin() ; it!=str.end() ; it++)
if (u.find(*it) != u.end()) // 在 c++20 可以直接寫 u.contains(*it)
*it = u[*it];
return str;
};
std::cout << f("Hellow") << std::endl;
}
hellow
[4]:
// transform + unordered_map 寫法
#include <iostream>
#include <string>
#include <algorithm>
#include <unordered_map>
{
auto f = [](std::string str)
{
std::unordered_map<char, char> lower = {{'A','a'}, {'B','b'}, {'C','c'}, {'D','d'},
{'E','e'}, {'F','f'}, {'G','g'}, {'H','h'}, {'I','i'}, {'J','j'}, {'K','k'},
{'L','l'}, {'M','m'}, {'N','n'}, {'O','o'}, {'P','p'}, {'Q','q'}, {'R','r'},
{'S','s'}, {'T','t'}, {'U','u'}, {'V','v'}, {'W','w'}, {'X','x'}, {'Y','y'},
{'Z','z'}, {'a','a'}, {'b','b'}, {'c','c'}, {'d','d'}, {'e','e'}, {'f','f'},
{'g','g'}, {'h','h'}, {'i','i'}, {'j','j'}, {'k','k'}, {'l','l'}, {'m','m'},
{'n','n'}, {'o','o'}, {'p','p'}, {'q','q'}, {'r','r'}, {'s','s'}, {'t','t'},
{'u','u'}, {'v','v'}, {'w','w'}, {'x','x'}, {'y','y'}, {'z','z'}};
std::transform(str.begin(), str.end(), str.begin(), [&](char c){ return lower[c]; });
return str;
};
std::cout << f("Hellow") << std::endl;
}
hellow
[3]:
// 直接改 ACSII 寫法
#include <iostream>
#include <string>
#include <algorithm>
{
auto f = [](std::string str)
{
for (std::string::iterator it=str.begin() ; it!=str.end() ; it++)
if ( 64 < *it && *it < 91 )
*it += 32;
return str;
};
std::cout << f("Hellow") << std::endl;
}
hellow
[4]:
// 用 transform 改 ACSII 寫法
#include <iostream>
#include <string>
#include <algorithm>
{
auto f = [](std::string str)
{
std::transform(str.begin(), str.end(), str.begin(),
[](char& c){ return (64 < (int)c && (int)c < 91) ? (char)((int)c + 32) : c;});
return str;
};
std::cout << f("Hellow") << std::endl;
}
hellow
1108. Defanging an IP Address
Easy
Given a valid (IPv4) IP address, return a defanged version of that IP address.
A defanged IP address replaces every period “.” with “[.]”.
Example 1:
Input: address = "1.1.1.1"
Output: "1[.]1[.]1[.]1"
Constraints:
The given address is a valid IPv4 address.
把一串 IP 位址的 “.” 全部取代成 “[.]”
[5]:
// 用 algorithm 裡的方法沒辦法把 char 取代成 std::string
// 如果想先把 std::string 拆成 std::string 的 vector 都需要用到 istream，搜 c++ sentense to list of words
#include <iostream>
#include <string>
{
auto f = [](std::string address)
{
std::string res = "";
for (const char& c : address)
if (c=='.')
res += "[.]";
else
res += c;
return res;
};
std::cout << f("1.1.1.1") << std::endl;
}
1[.]1[.]1[.]1
[7]:
// std::string 有 replace 可以用但要先自己把 "." 的 index 找出來
// 除了 ranges 之外沒看到現成的 filter/find all 可以用
#include <iostream>
#include <string>
#include <vector>
{
auto f = [](std::string address)
{
std::vector<int> idx;
for (size_t i=0 ; i<address.size() ; i++)
if (address[i]=='.')
idx.push_back(i);
for (std::vector<int>::reverse_iterator it=idx.rbegin() ; it!=idx.rend(); it++)
address.replace(*it, 1, "[.]");
return address;
};
std::cout << f("140.112.90.3") << std::endl;
}
140[.]112[.]90[.]3