刷题总结

对刷过的题目加以总结和归纳。


目录

1.全排列
2.简单的数
3.加油站
4.背包问题
5.数据流中第一个唯一的数字
6.最小调整代价
7.Valid Word Square
8.统计数字
9.偷黄金
10.寻找旋转排序数组中的最小值 II
11.带重复元素的排列
12.验证二叉查找树
13.Word Pattern II
14.将整数A转换为B
15.二叉树的所有路径
16.二叉查找树中搜索区间
17.最长公共前缀 II
18.最近公共祖先
19.Keys Keyboard
20.最长公共子序列
21.硬币排成线
22.Construct Binary Tree from String
23.二维数组中的查找
24.替换空格
25.从尾到头打印链表
26.重建二叉树
27.用两个栈实现队列
28.旋转数组的最小数字
30.变态跳台阶
31.矩形覆盖
32.二进制中1的个数
33.数值的整数次方
34.调整数组顺序使奇数位于偶数前面
35.链表中倒数第k个结点
35.反转链表


全排列

题目描述:全排列

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
void helper(vector<int> &nums, vector<int> &permutation, set<int> &s, vector<vector<int>> &result) {
if (permutation.size() == nums.size()) {
vector<int> vi(permutation);
result.push_back(vi);
return;
}
for (int i=0; i<nums.size(); ++i) {
if (s.count(nums[i])) continue;
s.insert(nums[i]);
permutation.push_back(nums[i]);
helper(nums, permutation, s, result);
permutation.erase(permutation.end()-1);
s.erase(nums[i]);
}
}
vector<vector<int>> permute(vector<int> &nums) {
// write your code here
vector<vector<int>> result;
if (nums.empty()) {
result.push_back(vector<int>());
return result;
}
set<int> s;
vector<int> permutation;
helper(nums, permutation, s, result);
return result;
}


简单的数

题目描述:简单的数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int singleNumber(vector<int> &A) {
// write your code here
map<int, int> hash;
for (int i=0; i<A.size(); ++i) {
hash[A[i]] += 1;
}
int result;
for (map<int, int>::iterator mit = hash.begin(); mit != hash.end(); ++mit) {
if (mit->second == 1) {
result = mit->first;
}
}
return result;
}


加油站

题目描述:加油站

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
// write your code here
int index=-1;
int total = 0;
int sum = 0;
for (int i=0; i<gas.size(); ++i) {
sum += gas[i] - cost[i];
total += gas[i] - cost[i];
if (sum < 0) {
index = i;
sum = 0;
}
}
return total<0 ? -1: index + 1;
}


背包问题

题目描述:背包问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int backPack(int m, vector<int> &A) {
// write your code here
vector<vector<int>> d(A.size()+1, vector<int>(m+1));
for (int i=0; i<m+1; ++i) {
d[0][i] = 0;
}
for (int i=1; i<=A.size(); ++i) {
for (int j=1; j<=m; ++j) {
if (j-A[i-1] >= 0) {
d[i][j] = max(d[i-1][j-A[i-1]]+A[i-1], d[i-1][j]);
} else {
d[i][j] = d[i-1][j];
}
}
}
return d[A.size()][m];
}


数据流中第一个唯一的数字

题目描述:数据流中第一个唯一的数字

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
58
59
60
class DataStream {
public:
DataStream() {
head = new Node(0);
tail = head;
}
void add(int num) {
if (m_set.count(num) != 0) {
if (m_hashmap.find(num) != m_hashmap.end()) {
remove(num);
}
} else {
m_set.insert(num);
Node *node = new Node(num);
m_hashmap.insert(make_pair(num, tail));
tail->next = node;
tail = node;
}
}
void remove(int num) {
Node *pre = m_hashmap[num];
Node *tmp = pre->next;
pre->next = tmp->next;
m_hashmap.erase(num);
if (pre->next != NULL) {
m_hashmap[pre->next->val] = pre;
} else {
tail = pre;
}
delete(tmp);
}
int firstUnique() {
if (head->next != NULL) {
return head->next->val;
}
return -1;
}
private:
Node *head, *tail;
map<int, Node*> m_hashmap;
set<int> m_set;
};
int firstUniqueNumber(vector<int> &nums, int number) {
// Write your code here
DataStream ds;
for(int i=0; i<nums.size(); ++i) {
if (nums[i] == number) {
return ds.firstUnique();
}
ds.add(nums[i]);
}
return -1;
}


最小调整代价

题目描述:最小调整代价

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int MinAdjustmentCost(vector<int> &A, int target) {
// write your code here
int n = A.size();
int f[n + 1][101];
for (int i = 0; i <= n ; ++i)
for (int j = 0; j <=100; ++j)
f[i][j] = INT8_MAX;
for (int i = 0; i <= 100; ++i)
f[0][i] = 0;
for (int i = 1; i <=n; ++i)
for (int j = 0; j <= 100;++j)
if (f[i-1][j] != INT8_MAX)
for (int k = 0; k <= 100; ++k)
if (abs(j-k) <= target)
if (f[i][k] > f[i-1][j] + abs(A[i-1]-k))
f[i][k] = f[i-1][j] + abs(A[i-1]-k);
int ans = INT8_MAX;
for (int i = 0; i <= 100; ++i)
if (f[n][i] < ans)
ans = f[n][i];
return ans;
}


Valid Word Square

题目描述:最小调整代价

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
bool validWordSquare(vector<string> &words) {
// Write your code here
int n = words.size();
string row;
string col;
bool flag = true;
for (int i=0; i<n; ++i) {
for (int j=0; j<n; ++j) {
row.push_back(words[i][j]);
col.push_back(words[j][i]);
}
if (row != col) {
flag = false;
return flag;
}
row.clear();
col.clear();
}
return flag;
}


统计数字

题目描述:统计数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int digitCounts(int k, int n) {
// write your code here
int count = 0;
for (int i=0; i<=n; ++i) {
int j = i;
while (j!=0) {
if (j%10 == k) {
++count;
}
j /= 10;
}
}
if (k==0) ++count;
return count;
}


偷黄金

题目描述:偷黄金

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int findResult(vector<int> &nums, int pos, int count, int n) {
if (pos == n) return 0;
if (cache.count(3*pos+count) != 0) return cache[3*pos+count];
int butou = findResult(nums, pos+1, 0, n);
int tou = 0;
if(count < 2) {
tou = nums[pos] + findResult(nums, pos+1, count+1, n);
}
cache.insert(make_pair(3*pos+count, max(butou, tou)));
return cache[3*pos+count];
}


寻找旋转排序数组中的最小值 II

题目描述:寻找旋转排序数组中的最小值 II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int findMin(vector<int> &nums) {
// write your code here
int lo = 0;
int hi = nums.size()-1;
while(lo<hi){
int mid = lo + (hi - lo)/2;
if(nums[mid]>nums[hi]){
lo = mid+1;
}else if(nums[mid]<nums[hi]){
hi = mid;
}else{
hi--;
}
}
return nums[lo];
}


带重复元素的排列

题目描述:带重复元素的排列

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
vector<vector<int>> permuteUnique(vector<int> &nums) {
// write your code here
vector<vector<int>> res;
if (nums.empty()) {
res.push_back(vector<int>());
return res;
}
vector<int> permu;
set<int> s;
set<string> set_str;
permute(nums, permu, res, s, set_str);
return res;
}
void permute(vector<int> &nums, vector<int> &permu, vector<vector<int>> &res, set<int> &s, set<string> &set_str) {
int n = nums.size();
if (permu.size() == n) {
stringstream ss;
for (int i=0; i<permu.size(); ++i) {
ss << permu[i];
}
if (set_str.count(ss.str())) {
return;
}
set_str.insert(ss.str());
vector<int> tmp(permu);
res.push_back(tmp);
return;
}
for (int i=0; i<n; ++i) {
if (s.count(i)) continue;
permu.push_back(nums[i]);
s.insert(i);
permute(nums, permu, res, s, set_str);
permu.pop_back();
s.erase(i);
}
}


验证二叉查找树

题目描述:验证二叉查找树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
bool isValidBST(TreeNode * root) {
// write your code here
return helper(root, INT32_MIN, INT32_MAX);
}
bool helper(TreeNode *root, int minValue, int maxValue) {
if (root == NULL) return true;
bool leftFlag = helper(root->left, minValue, root->val);
bool rightFlag = helper(root->right, root->val, maxValue);
if (!leftFlag || !rightFlag) return false;
if (root->val > minValue && root->val < maxValue) {
return true;
}
if (root->val == INT32_MIN || root->val == INT32_MAX) {
return true;
}
return false;
}


Word Pattern II

题目描述:Word Pattern II

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
bool wordPatternMatch(string &pattern, string &str) {
// write your code here
map<char, string> hashmap;
set<string> s;
return match(pattern, 0, str, 0, hashmap, s);
}
bool match(string &pattern, int p, string &str, int r, map<char, string> &hashmap, set<string> &s) {
if (p == pattern.size() && r == str.size()) return true;
if (p == pattern.size() || r == str.size()) return false;
char c = pattern[p];
for (int i=r; i<str.size(); ++i) {
string word = str.substr(r, i-r+1);
if (hashmap.count(c) && hashmap[c] == word) {
if (match(pattern, p+1, str, i+1, hashmap, s)) return true;
} else if (!hashmap.count(c)) {
if (s.count(word)) continue;
hashmap[c] = word;
s.insert(word);
if (match(pattern, p+1, str, i+1, hashmap, s)) return true;
hashmap.erase(c);
s.erase(word);
}
}
return false;
}


将整数A转换为B

题目描述:将整数A转换为B

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int bitSwapRequired(int a, int b) {
// write your code here
unsigned int n = a, m = b;
int count = 0;
while (n!=0 || m != 0) {
if ((n&1)^(m&1)) ++count;
n >>= 1;
m >>= 1;
}
return count;
}


二叉树的所有路径

题目描述:将整数A转换为B

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
vector<string> binaryTreePaths(TreeNode * root) {
// write your code here
stack<TreeNode *> s;
TreeNode *next = root;
vector<TreeNode *> vi;
vector<string> result;
while (true) {
while(next != NULL) {
s.push(next);
vi.push_back(next);
next = next->left;
}
if (s.empty()) break;
TreeNode *top = s.top();
s.pop();
if (top->left == NULL && top->right == NULL) {
stringstream os;
for (int i=0; i<vi.size()-1; ++i) {
os << vi[i]->val;
os << "->";
}
os << vi[vi.size()-1]->val;
result.push_back(os.str());
TreeNode *node = vi[vi.size()-1];
vi.pop_back();
while (!vi.empty() && (vi[vi.size()-1]->right == NULL || vi[vi.size()-1]->right == node)) {
node = vi[vi.size()-1];
vi.pop_back();
}
}
next = top->right;
}
return result;
}


二叉查找树中搜索区间

题目描述:二叉查找树中搜索区间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
vector<int> searchRange(TreeNode * root, int k1, int k2) {
// write your code here
vector<int> result;
helper(root, k1, k2, result);
sort(result.begin(), result.end());
return result;
}
void helper(TreeNode *root, int k1, int k2, vector<int> &result) {
if (root == NULL) return;
if (root->val >= k1 && root->val <= k2) {
result.push_back(root->val);
}
helper(root->left, k1, k2, result);
helper(root->right, k1, k2, result);
}


最长公共前缀 II

题目描述:最长公共前缀 II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int the_longest_common_prefix(vector<string> &dic, string &target) {
// write your code here
int longest = INT32_MIN;
for (int i=0; i<dic.size(); ++i) {
int count = 0;
for (int j=0; j<dic[i].length() && j<target.length(); ++j) {
if (dic[i][j] == target[j]) count++;
else break;
}
if (count > longest) longest = count;
}
return longest;
}


最近公共祖先

题目描述:最近公共祖先

1
2
3
4
5
6
7
8
9
10
11
12
13
14
TreeNode * lowestCommonAncestor(TreeNode * root, TreeNode * A, TreeNode * B) {
// write your code here
if (root == NULL) return NULL;
if (root == A) return A;
if (root == B) return B;
TreeNode *l = lowestCommonAncestor(root->left, A, B);
TreeNode *r = lowestCommonAncestor(root->right, A, B);
if (l!=NULL && r!=NULL) return root;
return l?l:r;
}


Keys Keyboard

题目描述:Keys Keyboard

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
int maxA(int N) {
// write your code here
vector<int> count(N+1);
for (int i=1; i<=N; ++i) {
int num1 = count[i-1]+1;
int num2 = 0;
if (i>3) {
num2 = helper(count, i);
}
count[i] = max(num1, num2);
}
return count[N];
}
int helper(vector<int> &count, int i) {
int index = i-3;
int MaxCount = 0;
while (index >= 0) {
int cnt = count[index] * (2 + i - index - 3);
MaxCount = max(MaxCount, cnt);
index--;
}
return MaxCount;
}


最长公共子序列

题目描述:最长公共子序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int longestCommonSubsequence(string &A, string &B) {
// write your code here
vector<vector<int>> d(A.size()+1, vector<int>(B.size()+1));
for (int i=1; i<=A.size(); ++i) {
for (int j=1; j<=B.size(); ++j) {
if (A[i-1] == B[j-1]) {
d[i][j] = d[i-1][j-1]+1;
} else {
d[i][j] = max(d[i][j-1], d[i-1][j]);
}
}
}
return d[A.size()][B.size()];
}


硬币排成线

题目描述:硬币排成线

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool firstWillWin(int n) {
// write your code here
if (n == 0) return false;
else if (n == 1) return true;
else if (n == 2) return true;
bool dp[n+1];
dp[0] = false;
dp[1] = true;
dp[2] = true;
for (int i=3; i<=n; ++i) {
dp[i] = !dp[i-1] || !dp[i-2];
}
return dp[n];
}


Construct Binary Tree from String

题目描述:Construct Binary Tree from String

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
TreeNode * str2tree(string &s) {
// write your code here
if (s.empty()) return NULL;
int first = s.find('(');
int val;
if (first != -1) {
sscanf(s.substr(0, first).c_str(), "%d", &val);
} else {
if (s[0] == ')') {
return NULL;
}
sscanf(s.c_str(), "%d", &val);
}
TreeNode *cur = new TreeNode(val);
if (first == -1) {
return cur;
}
int start = first, leftCount = 0;
for (int i=start; i<s.length(); ++i) {
if (s[i] == '(') leftCount++;
else if(s[i] == ')') leftCount--;
if (leftCount == 0 && start == first) {
string sstr = s.substr(start+1, i-start);
cur->left = str2tree(sstr);
start = i+1;
} else if (leftCount == 0) {
string sstr = s.substr(start+1, i-start);
cur->right = str2tree(sstr);
}
}
return cur;
}


二维数组中的查找

题目描述:二维数组中的查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool Find(int target, vector<vector<int> > array) {
if (array.size() == 0 || array[0].size() == 0) return false;
int row = 0;
int col = array[0].size()-1;
while (row < array.size() && col >= 0) {
if (target < array[row][col]) {
col--;
} else if(target > array[row][col]) {
row++;
} else {
return true;
}
}
return false;
}


替换空格

题目描述:二维数组中的查找

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
class Solution {
public:
void replaceSpace(char *str,int length) {
if (str == NULL) return;
int spaceCount = 0;
for (int i=0; i<strlen(str); ++i) {
if (str[i] == ' ') {
spaceCount++;
}
}
int strLen = strlen(str);
int spaceLen = 2 * spaceCount + strLen;
// 当前长度不够直接返回
if (spaceLen >= length) {
return;
}
// 处理'\0'
strLen++;
spaceLen++;
while (strLen >= 0 && spaceLen >= 0) {
if (str[strLen] == ' ') {
str[spaceLen--] = '0';
str[spaceLen--] = '2';
str[spaceLen--] = '%';
strLen--;
} else {
str[spaceLen--] = str[strLen--];
}
}
}
};


从尾到头打印链表

题目描述:二维数组中的查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vector<int> printListFromTailToHead(ListNode* head) {
stack<ListNode *> s;
vector<int> result;
while (head != NULL) {
s.push(head);
head = head->next;
}
while (!s.empty()) {
ListNode *node = s.top();
s.pop();
result.push_back(node->val);
}
return result;
}


重建二叉树

题目描述:重建二叉树

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
TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
if (pre.size() < 1 || vin.size() < 1 || pre.size() != vin.size()) return NULL;
return constructBinaryTree(pre, 0, pre.size()-1, vin, 0, vin.size()-1);
}
TreeNode* constructBinaryTree(vector<int> &pre, int pstart, int pend, vector<int> &vin, int vstart, int vend) {
if (pstart > pend) return NULL;
int value = pre[pstart];
int index = vstart;
while (index <= vend && vin[index] != value) {
++index;
}
if (index > vend) {
return NULL;
}
TreeNode *node = new TreeNode(value);
node->left = constructBinaryTree(pre, pstart+1, pstart+index-vstart, vin, vstart, index-1);
node->right = constructBinaryTree(pre, pstart+index-vstart+1, pend, vin, index+1, vend);
return node;
}

时间复杂度:O(nlogn)
空间复杂度:O(n)


用两个栈实现队列

题目描述:用两个栈实现队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution
{
public:
void push(int node) {
stack1.push(node);
}
int pop() {
if (stack2.empty()) {
while (!stack1.empty()) {
int top = stack1.top();
stack1.pop();
stack2.push(top);
}
}
int node = stack2.top();
stack2.pop();
return node;
}
private:
stack<int> stack1;
stack<int> stack2;
};


旋转数组的最小数字

题目描述:旋转数组的最小数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int minNumberInRotateArray(vector<int> rotateArray) {
if (rotateArray.size() == 0) return 0;
return findMinNumberInRotateArray(rotateArray, 0, rotateArray.size()-1);
}
int findMinNumberInRotateArray(vector<int> &rotateArray, int start, int end) {
if (start >= end) return rotateArray[start];
int mid = start + (end - start) / 2;
if (rotateArray[start] > rotateArray[mid]) {
return findMinNumberInRotateArray(rotateArray, start, mid);
} else if (rotateArray[end] <= rotateArray[mid]) {
return findMinNumberInRotateArray(rotateArray, mid+1, end);
} else {
return rotateArray[start];
}
}

时间复杂度:O(logn)
空间复杂度:O(1)


跳台阶

题目描述:跳台阶

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int jumpFloor(int number) {
if (number == 0) return 0;
map<int, int> cache;
return helper(0, number, cache);
}
int helper(int curNumber, int number, map<int, int> &cache) {
if (curNumber == number) return 1;
if (curNumber > number) return 0;
if(cache.count(curNumber) != 0) return cache[curNumber];
int oneJump = helper(curNumber+1, number, cache);
int twoJump = helper(curNumber+2, number, cache);
cache[curNumber] = oneJump + twoJump;
return cache[curNumber];
}

时间复杂度:O(n)
空间复杂度:O(n)
更简单的做法:

1
2
3
4
5
6
7
8
9
10
11
12
int jumpFloor(int number) {
if (number <= 2) return number;
int pre = 1;
int cur = 2;
for (int i=3; i<=number; ++i) {
cur = pre+cur;
pre = cur-pre;
}
return cur;
}

时间复杂度:O(n)
空间复杂度:O(1)


变态跳台阶

题目描述:变态跳台阶

1
2
3
4
5
6
7
8
9
10
11
12
13
int jumpFloorII(int number) {
vector<int> memo(number+1, 1);
memo[0] = 0;
memo[1] = 1;
for (int i=2; i<=number; ++i) {
for (int j=0; j<i; ++j) {
memo[i] += memo[j];
}
}
return memo[number];
}

时间复杂度:O(n^2)
空间复杂度:O(n)


矩形覆盖

题目描述:矩形覆盖

1
2
3
4
5
6
7
8
9
10
11
12
int rectCover(int number) {
if (number <= 1) return number;
int pre = 1;
int cur = 1;
for (int i=2; i<=number; ++i) {
cur = pre + cur;
pre = cur - pre;
}
return cur;
}

时间复杂度:O(n)
空间复杂度:O(1)


二进制中1的个数

题目描述:二进制中1的个数
最简单的解法:

1
2
3
4
5
6
7
8
9
int NumberOf1(int n) {
int numberCount = 0;
for (numberCount=0; n; n >>= 1) {
numberCount += n & 0x1;
}
return numberCount;
}

负数无法解决,正确解法:

1
2
3
4
5
6
7
8
9
10
int NumberOf1(int n) {
int numberCount = 0;
while (n) {
numberCount++;
n &= n-1;
}
return numberCount;
}

时间复杂度:O(2^n)
空间复杂度:O(1)


改进的方法:

1
2
3
4
5
6
7
8
9
int NumberOf1(int n) {
static unsigned int BitSetTable[256] = {0};
for (int i=1; i<= 255; ++i) {
BitSetTable[i] = (i & 1) + BitSetTable[i >> 1];
}
return BitSetTable[n&0xff] + BitSetTable[n>>8&0xff] + BitSetTable[n>>16&0xff] + BitSetTable[n>>24&0xff];
}

时间复杂度:O(1)
空间复杂度:O(2^n)


数值的整数次方

题目描述:数值的整数次方

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 快递幂
double Power(double base, int exponent) {
if (exponent == 0) return 1;
int n = abs(exponent);
double res = 1.0, cur = base;
while (n) {
if ((n & 1) == 1) {
res *= cur;
}
cur *= cur;
n >>= 1;
}
return (exponent > 0) ? res : 1/res;
}

时间复杂度:O(logn)
空间复杂度:O(1)


调整数组顺序使奇数位于偶数前面

题目描述:调整数组顺序使奇数位于偶数前面

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void reOrderArray(vector<int> &array) {
if(array.size() <= 1) return;
int n = array.size();
int index = 0;
for (int i=0; i<n; ++i) {
if (array[i] & 1) {
for (int j=i; j>index; j--) {
swap(array[j], array[j-1]);
}
index++;
}
}
}


链表中倒数第k个结点

题目描述:链表中倒数第k个结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
if (pListHead == NULL) return;
ListNode *pre = pListHead;
ListNode *cur = pListHead;
for (int i=0; i<k; ++i) {
if (cur == NULL) return NULL;
cur = cur->next;
}
while (cur) {
pre = pre->next;
cur = cur->next;
}
return pre;
}

时间复杂度:O(n)
空间复杂度:O(1)


反转链表

题目描述:反转链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
ListNode* ReverseList(ListNode* pHead) {
if (pHead == NULL || pHead->next == NULL) return pHead;
ListNode *pre = NULL;
ListNode *cur = pHead;
ListNode *next = NULL;
while (cur != NULL) {
next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
}
return pre;
}

时间复杂度:O(n)
空间复杂度:O(1)