Missing Number
[Problem]
Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array. For example, Given nums = [0, 1, 3] return 2. Note: Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?
[Solution2] sum: Time~O(n) Space~O(1) //overflow risk
missing = expected_sum - actual_sum = (0+n)(n+1)/2 - sum
class Solution {
public:
int missingNumber(vector<int>& nums) {
//sol1: actual_sum = 0+...+n = (0+n)*(n+1)/2
//missing = actual_sum - sum
int n = nums.size(), sum = 0;
for(auto num : nums) sum += num;
return 0.5*n*(n+1) - sum;
}
};
[Solution1] xor: Time~O(n) Space~O(1) //no overflow risk
xor all [i] and 0 to n: i^i=0, 0^missing=missing => final result = missing
[Tip]
- do not use for(auto...) since need to use counter "i"
- 0~n: n+1 numbers, nums[0~n-1]: n items => "for(i=0~n-1) res^=i^nums[i]" will not xor "n" => must init res=n
class Solution {
public:
int missingNumber(vector<int>& nums) {
//sol2: xor all items and 0~n => (i^i)=0 so 0^missing=missing
int n = nums.size(), res = n;
for(int i=0; i<n; ++i) res ^= i ^ nums[i];
return res;
}
};
Number of 1 Bits
[Problem]
Write a function that takes an unsigned integer and returns the number of ’1' bits it has (also known as the Hamming weight). For example, the 32-bit integer ’11' has binary representation 00000000000000000000000000001011, so the function should return 3.
[Solution] Time~O(n) Space~O(1)
count last digit&1, right shift
for(i=0~31) { count+=n&1; n=n>>1;}
[Tip]
n&1=last digit of n = 0 or 1 => if(n&1==1) ++count;
n=n>>1 //do not forget to "n=" n>>1
class Solution {
public:
int hammingWeight(uint32_t n) {
// count += last_bit==1 then right_shift
int count= 0;
for(int i=0; i<32; ++i) {
count+= n & 1;
n = n >> 1; //do not forget "n="
}
return count;
}
};
Integer to Roman
[Problem]
Given an integer, convert it to a roman numeral. Input is guaranteed to be within the range from 1 to 3999.
[Reference]
如今我们最常见的罗马数字就是钟表的表盘符号：Ⅰ，Ⅱ，Ⅲ，Ⅳ（IIII），Ⅴ，Ⅵ，Ⅶ，Ⅷ，Ⅸ，Ⅹ，Ⅺ，Ⅻ…… 对应阿拉伯数字（就是现在国际通用的数字），就是1，2，3，4，5，6，7，8，9，10，11，12. (注：阿拉伯数字其实是古代印度人发明的，后来由阿拉伯人传入欧洲，被欧洲人误称为阿拉伯数字.) 基本字符:I=1 V=5 X=10 L=50 C=100 D=500 M=1000 1、相同的数字连写，所表示的数等于这些数字相加得到的数，如：Ⅲ = 3； 2、小的数字在大的数字的右边，所表示的数等于这些数字相加得到的数， 如：Ⅷ = 8；Ⅻ = 12； 3、小的数字，（限于Ⅰ、X 和C）在大的数字的左边，所表示的数等于大数减小数得到的数，如：Ⅳ= 4；Ⅸ= 9； 4、正常使用时，连写的数字重复不得超过三次。（表盘上的四点钟“IIII”例外） 5、在一个数的上面画一条横线，表示这个数扩大1000倍。 6. No 0, no 5000 7. max is 3999 = "MMMCMXCIX" 有几条须注意掌握： 1、基本数字Ⅰ、X 、C 中的任何一个，自身连用构成数目，或者放在大数的右边连用构成数目，都不能超过三个；放在大数的左边只能用一个。 2、不能把基本数字V 、L 、D 中的任何一个作为小数放在大数的左边采用相减的方法构成数目；放在大数的右边采用相加的方式构成数目，只能使用一个。 3、V 和X 左边的小数字只能用Ⅰ。 4、L 和C 左边的小数字只能用X。 5、D 和M 左边的小数字只能用C。
[Solution1] define 1000,900,500,400,100,90,50,40,10,9,5,4,1
- diction from unit_val=>unit_str: vector<pair<int,string>> units =
{{1000,"M"},{900,"CM"},{500,"D"},{400,"CD"},{100,"C"},{90,"XC"},{50,"L"},{40,"XL"},{10,"X"},{9,"IX"},{5,"V"},{4,"IV"},{1,"I"}}
- res=""
for(unit_i=0~units.size()-1 //for each possible unit(from large to small)
&& if num>0) //stop if num=0
for(k=0~num/(units[unit_i].first)-1) //repeat the same unit if applicable(should <=3 times)
s+= units[unit_i].second;
num %= units[unit_i].first;
return ress;
[Tip]
- use vector<pair<int,string>> instead of map<int,string> so can for-loop every possible unit
- vector<pair<int,string>> shouls store units from large to small -> divid large unit first
- not 900=>"CM"(instead of "DM"), 90=>"XC"(instead of "LC"), 9=>"IX"(instead of "VX")
- outer-loop through each possible unit, inner-loop repeat current unit if required(should <=3 times)
- outer-loop should stop if num<=0 //skip checking any smaller units
class Solution {
public:
string intToRoman(int num) {
//vector<pair<unit,string>> dic={1000->"M", 900->"DM",...1->"I"} //must be decending order!!!
//for(i=0~n-1) while(n>=v[i].first) { s+= v[i].second; n-=v[i].first}
vector<pair<int,string>> units = {{1000,"M"},{900,"CM"},{500,"D"},{400,"CD"},{100,"C"},{90,"XC"},
{50,"L"},{40,"XL"},{10,"X"},{9,"IX"},{5,"V"},{4,"IV"},{1,"I"}};
string res="";
for(int unit_i=0; num>0 && unit_i<units.size(); ++unit_i) { //for each unit(large to small)
for(int k=0; k<num / units[unit_i].first; ++k) { //repeat as many as possible (should <=3)
res += units[unit_i].second;
}
num %= units[unit_i].first;
}
return res;
}
};
[Solution2] define 1~9 for each digit(1000th,100th,10th,1th)
vector<string> thousandth{"", "M", "MM", "MMM"};
vector<string> hundredth{"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
vector<string> tenth{"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
vector<string> oneth{"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};
return thousandth[num / 1000] + hundredth[(num % 1000) / 100] + tenth[(num % 100) / 10] + oneth[num % 10];
class Solution {
public:
string intToRoman(int num) {
//sol2: define 1~9 for 1000th, 100th, 10th and 1th digit
vector<string> thousandth{"", "M", "MM", "MMM"};
vector<string> hundredth{"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
vector<string> tenth{"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
vector<string> oneth{"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};
return thousandth[num / 1000] + hundredth[(num % 1000) / 100] + tenth[(num % 100) / 10] + oneth[num % 10];
}
};
Roman to Integer
[Problem]
Given a roman numeral, convert it to an integer. Input is guaranteed to be within the range from 1 to 3999.
[Solution1] pre&cur Time~O(n) Space~O(1)
- map<char,int> m = {{'I',1},{'V',5},{'X',10},{'L',50},{'C',100},{'D',500},{'M',1000}}
- for(i=0~i) if(pre<cur) val+=cur-2*pre; else val-=cur
class Solution {
public:
int romanToInt(string s) {
// sol2: val+= pre<cur ? cur:(cur-2pre)//pre has been added as last cur
unordered_map<char, int> m = { {'I',1},{'V',5},{'X',10},{'L',50},{'C',100},{'D',500},{'M',1000}};
int n = s.length(), val=0, pre = 0, cur = 0;
for(int i=0; i<n; ++i) {
cur = m[s[i]];
val += cur>pre ? (cur-2*pre) : cur;
pre = cur; //DO NOT FORGET!!
}
return val;
}
};
[Solution2] cur&next Time~O(n) Space~O(1)
- map<char,int> m = {{'I',1},{'V',5},{'X',10},{'L',50},{'C',100},{'D',500},{'M',1000}}
- for(i=0~n-1) if(cur==last||cur>=next) val+=cur; else val-=cur
[Tip]
- no need to validate Roman
- smaller|larger: -smaller+larger
same|same: +same+same
larger|smaller: +smaller+larger
=> if(i==last_digit or [i]==smaller or same) +smaller/same/last_digit; else -smaller
class Solution {
public:
int romanToInt(string s) {
//map={I=>1 V=>5 X=>10 L=>50 C=>100 D=>500 M=>1000}
//- smaller(I/X/C) larger=> larger-smaller
//- larger smaller=> larger+smaller
//- same same=> same+same
//if(i==n-1 || [i]>=[i+1]) val+[i]; else val-[i];
unordered_map<char, int> m = { {'I',1},{'V',5},{'X',10},{'L',50},{'C',100},{'D',500},{'M',1000}};
int n = s.length(), val=0, res = 0;
for(int i=0; i<n; ++i) {
val = m[s[i]];
if(i==n-1 || val>=m[s[i+1]]) res += val;
else res -= val;
}
return res;
}
};
Gray Code
[Problem]
The gray code is a binary numeral system where two successive values differ in only one bit. Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0. For example, given n = 2, return [0,1,3,2]. Its gray code sequence is: 00 - 0 01 - 1 11 - 3 10 - 2 Note: For a given n, a gray code sequence is not uniquely defined. For example, [0,2,3,1] is also a valid gray code sequence according to the above definition. For now, the judge is able to judge based on one instance of gray code sequence.
[Solution1] binary->gray_code: Time~O(n) Space~O(n)//res.size=n
binary(i)=>gray_code((i>>1)^i) //right shift 1 bit, then "exclusive or" 1 (0^0=1^1=0, 0^1=1^0=1) 1
class Solution {
public:
vector<int> grayCode(int n) {
// sol1: binary->gray_code:(i>>1)^i
vector<int> res;
int last = pow(2, n);
for(int i = 0; i < last; ++i) {
res.push_back((i>>1)^i);
}
return res;
}
};
[Solution2] mirror arrangement: Time~O(n^2) Space~O(n)//res.size=n
mirror arrangement: reversely each item in g(n-1) + additional_leftmost_bit_1
- init: 1 element 0 //res={0}
- for (i=0~n-1)
size=res.size; add_bit = 1<<1;
for(j=size-1~0) res.push(res[i] | add_bit)
- time = 1+1+2+4...+2*(n-1) =O((1+n)n) = O(n^2)
class Solution {
public:
vector<int> grayCode(int n) {
vector<int> res{0}; //init has 1 item 0
for(int i = 0; i < n; ++i) {
int size = res.size();
int add_bit = 1 << i;
for (int j = size-1; j >=0; --j) { //reverse order
res.push_back(res[j] | add_bit);
}
}
return res;
}
};
Decode Ways
[Problem]
A message containing letters from A-Z is being encoded to numbers using the following mapping: 'A' -> 1 'B' -> 2 ... 'Z' -> 26 Given an encoded message containing digits, determine the total number of ways to decode it. For example, Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12). The number of ways decoding "12" is 2.
[Solution] 1d-DP: Time~O(n) Space~(n)
- dp[i]=decode ways for substring s[0:i-1]
- vector<int> dp(n+1,0) //all init to 0, actual value start from dp[1]=ways of s[0], dp[0] used to calculate dp[1] only
- dp[0] = n==0 ? 0 : 1
for(i=1~n) //dp[n]=ways of s[0:n-1] //NOT "n-1" but "n"!!!
if(s[i-1]!='0') dp[i]+=dp[i-1]; //for each way of s[0:i-2] or '', append s[i-1]=>way of s[0:i-1]
if(i>=2 && (s[i-1]=='1' || (s[i-2]=='2' && s[i-1]<='6'))) dp[i]+=dp[i-2]; //for each way of s[i-3] or '', append s[i-1]s[i-2]=>way of s[0:i-1]
[Tip]
- dp size = n+1, dp[0] only used to calculate dp[1]
what should dp[0] be? if n==0, dp[0]=0; if n>0, dp[1]=1 so to use formular dp[i]+=dp[i-1] => dp(0)=dp[1]=1
- dp[i]= ways to code s[0:i-1] not s[0:i], so "for(i=1~n)" not "for(i=1~n-1", and "return dp[n]"
- if(i>=2 && (s[i-1]=='1' || (s[i-2]=='2' && s[i-1]<='6'))) // not s[i-1]='2' || (s[i-1]=='1'&&s[i-1]<='6') //1X, 21~26
class Solution {
public:
int numDecodings(string s) {
// 1d-DP, int dp[s.length+1]
// dp[i]=ways to code s[0:i-1] //rules 1~26, so '0' can only be in 'x0', i.e. '10' or '20'
// dp[0] = n==0 ? 0 : 1; //if s[0] exist, must have 1 valid way to code
// for(i=1~n-1)
// s[i-1]=1~9) dp[i]+=dp[i-1] //if(s[i-1]!='0')
// s[i-1:i-2]=10~26 dp[i]+=dp[i-2] //if(i>=2 && (s[i-2]=='1'||(s[i-2]=='2' && s[i-1]<='6')))
int n = s.length();
vector<int> dp(n+1, 0); //dp[i]=decode ways for s[0:i-1], init to 0
dp[0] = n==0 ? 0 : 1;
for(int i=1; i<=n; ++i) { //i<=n since s[i-1] and dp[n]
if(s[i-1]!='0') dp[i] += dp[i-1]; //for each s[0:i-2] decode way: append the code for s[i-1] (x)
if(i>=2 && (s[i-2]=='1'|| (s[i-2]=='2' && s[i-1]<='6'))) dp[i] += dp[i-2]; //for each s[0:i-2] decode way: append the code for s[i-1:i-2] (xy)
}
return dp[n];
}
};
Reverse Integer
[Problem]
Reverse digits of an integer. Example1: x = 123, return 321 Example2: x = -123, return -321 Have you thought about this? Here are some good questions to ask before coding. Bonus points for you if you have already thought through this! If the integer's last digit is 0, what should the output be? ie, cases such as 10, 100. Did you notice that the reversed integer might overflow? Assume the input is a 32-bit integer, then the reverse of 1000000003 overflows. How should you handle such cases? For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.
[Solution] Time~O(n) Space~O(1) //n=digit_cnt
res=0, while(x!=0){
if(abs(res)>INT_MAX/10) return 0;
res=res*10+x/10; //add-up rightmost digit;
x/=10; }//right shift 1 digit
return res
[Tip]
- add up rightmost digit, right shift 1 digit, repeat
- check overflow during add-up (since non-overflow origin may have overflow reverse)
class Solution {
public:
int reverse(int x) {
int res = 0;
while(x != 0) {
if(abs(res) > INT_MAX / 10) return 0; //do not forget abs()
res = res * 10 + x % 10; //add up last digit
x /= 10; //right shift 1 digit
}
return res;
}
};