Tips
1 Basic
1, 判断两个浮点数a和b是否相等时，不要用 a==b, 用 fabs(a-b) < 1e-9.
2, 判断一个整数是否为奇数， x % 2 != 0, 不要用 x % 2 == 1. ？？？？？
check the last digit to be 1 or not.
if (num & 0x1) = true, 奇数
else 偶数
3, 用 char 值作为数组下标 （如，统计字符串中每个字符出现的次数），要考虑到char可能是负数。 如果强制类型转换为unsigned int 再作下标，仍然是错的。
正确的做法，强制类型转换到unsigned char再用做下标。涉及到C++整型提升的规则。
4，std::size_t : nested type name
class C
{
public:
typedef int int_type; // as a nested typedef-name
using float_type = float; // C++11: typedef-name declared using 'using'
class inner_type { /*...*/ }; // as a nested class or struct
enum enum_type { one, two, three }; // nested enum (or 'enum class' in C++11)
};
int_type a1; // error, 'int_type' not known
C::int_type a2; // OK
C::enum_type a3 = C::one; // OK
c::float_ype f1; // OK
5, convert char to int
char a = '4';
int ia = a - '0';
6, median of size n array
It is middle element when n is odd andaverage of middle two elements when n is even.
7, skip repeat elements using while
while (vec[k] == vec[k+1] && j < k) --k;
while (vec[j] == vec[j-1] && j < k) ++j;
8, INT_MAX _and _
9, 判断闰年 两种情况是闰年1, 能被400整除，2, 能被4整除且不能被100整除，如1900
return (y%100 != 0 && y%4 == 0) || (y%400 == 0)
def isLeapYear(y):
# return (y%4 == 0 and y%100 != 0) or (y%400 == 0)
# and precedence is higher than or,
# and expression will execute first, then the result will calculate with or
return y%4 == 0 and y%100 != 0 or y%400 == 0
# 400 will return false
# return (y%100 != 0 and y%4 == 0)
if __name__ == '__main__':
print(isLeapYear(1900))
print(isLeapYear(1904))
print(isLeapYear(400))
2 Array Vector
2.1, Basic
vector.back() return the last element,vector.pop_back() pop the last element.
2.2, convert set<vector<int> > to vector<vector<int> >
// way1: range constructor
vector<vector<int> > resv(res.begin(), res.end());
// way2: copy
vector<vector<int> > resv(res.size());
copy(res.begin(), res.end(), resv.begin());
// way3: std::vector::assign
vector<vector<int> > resv;
resv.assign(res.begin(), res.end());
2.3, vector.reserver(n) then vector.push_back() and vector.size()
// Gray Code
// reflect-and-prefix method
// 时间复杂度O(2^n)，空间复杂度O(1)
class Solution {
public:
vector<int> grayCode(int n) {
const int size = 1 << n; // 2^n
vector<int> result;
result.reserve(size); // reserve 2^n spaces
// insert 0 to the first empty place of vector, not at the end of vector, size++, here size = 1;
// the vector total space not increased!!!!!! Keep push_back(7), will insert 7 at the index 1 of vector.
// then size++, here size = 2. vector is [0, 7, null, null, ... ] total 2^n spaces.
// vector.size() is the actual number of elements in the vector
result.push_back(0);
for (int i = 0; i < n; i++) {
const int highest_bit = 1 << i;
for (int j = result.size() - 1; j >= 0; j--) {// 要反着遍历，才能对称
result.push_back(highest_bit | result[j]);
}
}
return result;
}
};
2D Vector
std::vector< std::vector<int> > ragged(10) ;
for( std::size_t i = 0 ; i < ragged.size() ; ++i )
ragged[i] = std::vector<int>( i%10 + 1, i ) ;
// print 2d array
for ( const std::vector<int> &v : ragged)
{
for ( int x : v ) std::cout << x << ' ';
std::cout << std::endl;
}
0
1 1
2 2 2
3 3 3 3
4 4 4 4 4
5 5 5 5 5 5
6 6 6 6 6 6 6
7 7 7 7 7 7 7 7
8 8 8 8 8 8 8 8 8
9 9 9 9 9 9 9 9 9 9
3 Linked List
1, Linked List
Dummy pointer, pre, next
2, 头插入
ListNode *head = nullptr;
ListNoe *newNode = new ListNode(9);
newNode = head;
head= newNode;
insert 4 3 5 2
List: head -> 2 -> 5 -> 3 -> 4 -> nullptr;
4 string
1, string.find()
//1.1 Valid Parentheses (20)
std::size_t found = str.find(str2);
if (found != std::string::npos)
//1.2
str.replace(str.find(str2),str2.length(),"preposition");
2, stoi(str) convert string to integer, negative ok?
to_string(intX)
5 Tree
1, if node is leaf
int answer; // don't forget to initialize answer before call maximum_depth
void maximum_depth(TreeNode* root, int depth) {
if (!root) {
return;
}
// if node is leaf
if (!root->left && !root->right) {
answer = max(answer, depth);
}
maximum_depth(root->left, depth + 1);
maximum_depth(root->right, depth + 1);
}