1. 位運(yùn)算
2. 10進(jìn)制進(jìn)位，取余
3. 找規(guī)律題目
Given an array of integers, every element appears twice except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
利用取余操作的特性相同為0，不同為1。可以得出，只出現(xiàn)一次的數(shù)字。
int singleNumber(vector<int>& nums) {
int start = 0;
for (auto n:nums) {
start ^= n;
}
return start;
}
Given an array of integers, every element appears three times except for one, which appears exactly once. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
136的升級(jí)版，可以使用32bit保存對(duì)應(yīng)每個(gè)bit之和取余進(jìn)行操作。對(duì)重復(fù)出現(xiàn)的那個(gè)的值進(jìn)行取余，如本題中的3，上題中的2。
int singleNumber(vector<int>& nums) {
vector<int> table(32, 0);
int res = 0;
for (int i = 0; i < 32; ++i) {
for (auto j = 0; j < nums.size(); ++j) {
table[i] += ((nums[j] >> i)&1);
table[i] %= 3;
}
res |= (table[i] << i);
}
return res;
}
Divide two integers without using multiplication, division and mod operator.
If it is overflow, return MAX_INT.
- 使用位運(yùn)算實(shí)現(xiàn)除法
- 主要思想是倍數(shù)可以用2的指數(shù)和求出
int divide(int dividend, int divisor) {
if (!divisor || (dividend == INT_MIN && divisor == -1)) {
return INT_MAX;
}
int sign = ((dividend < 0 && divisor > 0) || (dividend > 0 && divisor < 0) ) ? -1 : 1;
long long dvd = labs(dividend);
long long dvs = labs(divisor);
int res = 0;
while (dvs <= dvd) {
long long count = 1, dv = dvs;
while ((dv << 1) <= dvd) {
dv <<= 1;
count <<= 1;
}
dvd -= dv;
res += count;
}
return res*sign;
}
50. Pow(x, n)
Implement pow(x, n).
不適用位運(yùn)算時(shí)間復(fù)雜度為O(n)，使用位運(yùn)算時(shí)間復(fù)雜度為O(logn)
使用位運(yùn)算的關(guān)鍵是理解將某個(gè)數(shù)值拆分成二進(jìn)制表示的形式，如 9的二進(jìn)制表示為 1001 即是 2^3 + 2^0
double myPow(double x, int n) {
long long p = labs(n);
double res = 1;
while (p > 0) {
if (p & 1) res *= x;
x *= x;
p >>= 1;
}
return n < 0 ? 1/res : res;
}
9. Palindrome Number
Determine whether an integer is a palindrome. Do this without extra space.
巧妙地利用sum記錄一般數(shù)目，只能在原地進(jìn)行運(yùn)算。其實(shí)也是移位，不過(guò)是10進(jìn)制的。遍歷次數(shù)降低一半且空間復(fù)雜度為O(1)
bool isPalindrome(int x) {
if (x < 0 || (x != 0 && x % 10 == 0)) return false;
int sum = 0;
while (x > sum) {
sum = sum*10 + x%10;
x /= 10;
}
return (x == sum) || (x == sum/10);
}
8. String to Integer (atoi)
Implement atoi to convert a string to an integer.
Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.
Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.
Update (2015-02-10):
The signature of the C++ function had been updated. If you still see your function signature accepts a const char * argument, please click the reload button to reset your code definition.
實(shí)現(xiàn)atoi函數(shù)，需要注意的是 1. 去掉前面和后面的空白字符 2. 有效字符必須在'0'和'9'之間 3. 大于INT_MAX的輸出INT_MAX，小于INT_MIN的 INT_MIN
int myAtoi(string str) {
int cur = str.find_first_not_of(' ');
int pos = 1;
if (str[cur] == '-' || str[cur] == '+') {
pos = (str[cur] == '-') ? -1 : 1;
cur++;
}
long result = 0;
while (cur < str.size() && str[cur] >= '0' && str[cur] <= '9') {
result = result*10 + str[cur++] - '0';
if (result*pos >= INT_MAX) return INT_MAX;
if (result*pos <= INT_MIN) return INT_MIN;
}
return result*pos;
}
31. Next Permutation
Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).
The replacement must be in-place, do not allocate extra memory.
Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1
解析: 數(shù)組的下一個(gè)字典順序
邊界：數(shù)組大小小于2
思路：找規(guī)律的題目，1. 從后往前找第一個(gè)相鄰的構(gòu)成升序的p[n] < p[n+1]，n點(diǎn)為違法點(diǎn)。2. 對(duì)p[n]之后的元素進(jìn)行逆序 3. 在排序后的p[n+1]至最后的第一個(gè)大于p[n]的元素與p[n]交換
C++ STL中下一個(gè)字典順序的函數(shù)，next_permutation(beg, end)
時(shí)間復(fù)雜度：O(n)
void nextPermutation(vector<int>& nums) {
if(nums.size() < 2) return;
int i = nums.size() - 2;
for (;i >= 0; --i) {
if (nums[i] < nums[i+1]) break;
}
reverse(nums.begin() + i + 1, nums.end());
if (i == -1) return;
int j = i+1;
for (; j < nums.size(); ++j) {
if (nums[i] < nums[j]) {
swap(nums[i], nums[j]);
break;
}
}
}
60. Permutation Sequence
The set [1,2,3,…,n] contains a total of n! unique permutations.
By listing and labeling all of the permutations in order,
We get the following sequence (ie, for n = 3):
"123"
"132"
"213"
"231"
"312"
"321"
Given n and k, return the kth permutation sequence.
Note: Given n will be between 1 and 9 inclusive.
求[1,n]構(gòu)成的第k個(gè)數(shù)列，可以使用31題中的方法一步一步來(lái)，也可以根據(jù)規(guī)律去做。規(guī)律如下：第一位為每(n-1)!為1組，則res[0]為nums[k/(n-1)!]。剩下的n-1個(gè)數(shù)組也是這個(gè)規(guī)律。每次需要更新k和count，k %= count(含義為該組中第k個(gè))。
string getPermutation(int n, int k) {
vector<int> nums(n);
int count = 1;
for (int i = 0; i < n; ++i) {
nums[i] = i + 1;
count *= (i+1);
}
k--;
string res;
for (int i = 0; i < n; ++i) {
count /= (n - i);
int cur = k/count;
res += ('0' + nums[cur]);
k %= count;
for(int j = cur; j < n - i - 1; ++j) {
nums[j] = nums[j + 1];
}
}
return res;
}
13. Roman to Integer
Given a roman numeral, convert it to an integer.
Input is guaranteed to be within the range from 1 to 3999.
羅馬數(shù)字轉(zhuǎn)換成阿拉伯?dāng)?shù)字，主要是找出每個(gè)羅馬數(shù)字對(duì)應(yīng)的大小
int romanToInt(string s) {
unordered_map<char,int> hash_table = {{'I',1}, {'V',5}, {'X', 10}, {'L', 50}, {'C', 100}, {'D', 500}, {'M', 1000}};
int sum = hash_table[s.back()];
for (int i = s.size() - 2; i >= 0; --i) {
if (hash_table[s[i]] < hash_table[s[i+1]]) {
sum -= hash_table[s[i]];
} else {
sum += hash_table[s[i]];
}
}
return sum;
}
59. Spiral Matrix II
Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.
For example,
Given n = 3,
You should return the following matrix:
[
[ 1, 2, 3 ],
[ 8, 9, 4 ],
[ 7, 6, 5 ]
]
找出規(guī)律?。?！實(shí)現(xiàn)要細(xì)心
vector<vector<int>> generateMatrix(int n) {
vector<vector<int>> vv(n,vector<int>(n,0));
int rowStart = 0, rowEnd = n - 1;
int colStart = 0, colEnd = n - 1;
int cnt = 1;
while (rowStart <= rowEnd && colStart <= colEnd) {
for(int i = colStart; i<= colEnd; i++)
vv[rowStart][i] = cnt++;
rowStart++;
for(int i = rowStart; i<= rowEnd; i++)
vv[i][colEnd] = cnt++;
colEnd--;
for (int i = colEnd; i >= colStart; --i) {
vv[rowEnd][i] = cnt++;
}
rowEnd--;
for (int i = rowEnd; i >= rowStart; --i) {
vv[i][colStart] = cnt++;
}
colStart++;
}
return vv;
}
48. Rotate Image
You are given an n x n 2D matrix representing an image.
Rotate the image by 90 degrees (clockwise).
Follow up:
Could you do this in-place?
將數(shù)組旋轉(zhuǎn)2次，一次是水平或垂直，一次是斜著沿著軸。順序無(wú)關(guān)
/*
* clockwise rotate
* first reverse up to down, then swap the symmetry
* 1 2 3 7 8 9 7 4 1
* 4 5 6 => 4 5 6 => 8 5 2
* 7 8 9 1 2 3 9 6 3
*/
void rotate(vector<vector<int> > &matrix) {
reverse(matrix.begin(), matrix.end());
for (int i = 0; i < matrix.size(); ++i) {
for (int j = i + 1; j < matrix[i].size(); ++j)
swap(matrix[i][j], matrix[j][i]);
}
}
149. Max Points on a Line
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
找出一條直線(xiàn)上最多的點(diǎn)
這種題最怕的就是直接被嚇到，沒(méi)思路。其實(shí)一步步挨個(gè)遍歷，下層循環(huán)遍歷剩余點(diǎn)即可。頂層循環(huán)下，當(dāng)前點(diǎn)做起點(diǎn)，建立最大公約數(shù)的map，記錄重復(fù)點(diǎn)、x相同的點(diǎn)；每次頂層循環(huán)，求出以當(dāng)前為起點(diǎn)哪個(gè)直線(xiàn)上的點(diǎn)最多（斜率為0的為1條線(xiàn)）
其中用到數(shù)學(xué)知識(shí)，求最大公約數(shù)，使用輾轉(zhuǎn)相除法。余數(shù)為0時(shí)，小的那個(gè)為最大公約數(shù)。不為0時(shí)，小的為余數(shù)，大的為小的。
/**
* Definition for a point.
* struct Point {
* int x;
* int y;
* Point() : x(0), y(0) {}
* Point(int a, int b) : x(a), y(b) {}
* };
*/
class Solution {
public:
int maxPoints(vector<Point> &points) {
if(points.size()<2) return points.size();
int result=0;
for(int i=0; i<points.size(); i++) {
map<pair<int, int>, int> lines;
int localmax=0, overlap=0, vertical=0;
for(int j=i+1; j<points.size(); j++) {
if(points[j].x==points[i].x && points[j].y==points[i].y) {
overlap++;
continue;
}
else if(points[j].x==points[i].x) vertical++;
else {
int a=points[j].x-points[i].x, b=points[j].y-points[i].y;
int gcd=GCD(a, b);
a/=gcd;
b/=gcd;
lines[make_pair(a, b)]++;
localmax=max(lines[make_pair(a, b)], localmax);
}
localmax=max(vertical, localmax);
}
result=max(result, localmax+overlap+1);
}
return result;
}
private:
int GCD(int a, int b) {
while (b) {
int tmp = a%b;
a = b;
b = tmp;
}
return a;
}
};
