剑指offer

《剑指offer》题解。

从左下角为起点开始 search,这样每次都能排除掉一列或者一行。(当然以右上角为起点也是可以的)。

class Solution {
public:
bool Find(int target, vector<vector<int> > array) {
if (array.size() == 0 || array[0].size() == 0) {
return false;
}
int n = array.size(), m = array[0].size();
int i = n - 1, j = 0;
while (i >= 0 && j < m) {
if (array[i][j] == target) return true;
else if (array[i][j] > target) i--;
else if (array[i][j] < target) j++;
}
return false;
}
};

时间复杂度:O(n+m)O(n+m)

正着来替换的话,需要开辟新的字符数组来保存一个中间结果。可以反着来,算出新数组长度后,倒着更新就好了。

如果是 %20 替换成空格话,直接正着来就好了。

class Solution {
public:
void replaceSpace(char *str,int length) {
int spaceCount = 0;
for (int i = 0; i < length; i++) {
if (str[i] == ' ') spaceCount++;
}
int newLength = length + 2 * spaceCount;
for (int i = length - 1, newi = newLength - 1; i >= 0; i--) {
if (str[i] == ' ') {
str[newi--] = '0';
str[newi--] = '2';
str[newi--] = '%';
} else {
str[newi--] = str[i];
}
}
}
};

时间复杂度:O(length+2spaceCount)O(length + 2 * spaceCount)

一边遍历一边保存结果。然后把结果倒一下。(感觉想考察栈?不过直接用数组完全可以实现)

/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) :
* val(x), next(NULL) {
* }
* };
*/
class Solution {
public:
vector<int> printListFromTailToHead(ListNode* head) {
vector<int> res;
ListNode* cur = head;
while (cur != NULL) {
res.push_back(cur->val);
cur = cur->next;
}
// reverse(res.begin(), res.end());
int n = res.size();
for (int i = 0; i < n / 2; i++) {
int tmp = res[i];
res[i] = res[n - 1 - i];
res[n - 1 - i] = tmp;
}
return res;
}
};

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

根据前序遍历和中序遍历重建二叉树。

/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
private:
TreeNode* buildBinaryTree(vector<int>& pre,vector<int>& vin, int ps, int vs, int size) {
if (size == 0) return NULL;
TreeNode* root = new TreeNode(pre[ps]);
int leftSize = 0;
while (vin[vs + leftSize] != pre[ps]) {
leftSize++;
}
root->left = buildBinaryTree(pre, vin, ps + 1, vs, leftSize);
root->right = buildBinaryTree(pre, vin, ps + 1 + leftSize, vs + leftSize + 1, size - leftSize - 1);
return root;
}
public:
TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
if (pre.size() == 0 || vin.size() == 0) return NULL;
return buildBinaryTree(pre, vin, 0, 0, pre.size());
}
};

时间复杂度:O(nlogn)O(nlogn),最坏应该是 O(n2)O(n^2)。时间复杂度是 T(n)=O(n)+2T(n/2)T(n)=O(n)+2T(n/2),是一个 O(n)O(n) 的复杂度,加上两个子问题的复杂度,算出来平均应该是 O(nlogn)O(nlogn)

  1. push() 放到 stack1 里

  2. pop() 的时候,看 stack2 是不是空的,如果是空的得把 stack1 里元素倒到 stack2 里,然后直接 pop stack2 中的元素就好了。

class Solution
{
public:
void push(int node) {
stack1.push(node);
}
int pop() {
if (stack2.empty()) {
while (!stack1.empty()) {
int t = stack1.top(); stack1.pop();
stack2.push(t);
}
}
int res = stack2.top(); stack2.pop();
return res;
}
private:
stack<int> stack1;
stack<int> stack2;
};

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

我是按照严格递增的话来写的。取中间元素和最后一个元素比较,然后每次都排除掉非“分割线”所在的那个区间(正常的递增区间)。(PS:之所以用最后一个元素,是因为如果只有两个元素的话,mid 每次都是 L 元素,而不是 R 元素,会有点问题。

如果是非递减的话,感觉只能 O(n)O(n) 的写法了。因为没办法区分 [1, 0, 1, 1, 1][1, 1, 1, 0, 1]

class Solution {
public:
int minNumberInRotateArray(vector<int> rotateArray) {
if (rotateArray.size() == 0) {
return 0;
}
int L = 0, R = rotateArray.size() - 1;
while (L < R) {
int mid = L + (R - L) / 2;
if (rotateArray[mid] > rotateArray[R]) {
L = mid + 1;
} else {
R = mid;
}
}
return rotateArray[L];
}
};

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

用一个数组记录一下结果。避免重复的计算。

class Solution {
private:
int fib[50];
public:
int Fibonacci(int n) {
if (n <= 1) {
return n;
}
return fib[n] ? fib[n] : fib[n] = Fibonacci(n - 1) + Fibonacci(n - 2);
}
};

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

跳台阶

和上一题一样。

class Solution {
private:
int jump[50];
public:
int jumpFloor(int number) {
if (number <= 1) {
return 1;
}
return jump[number] ? jump[number]: jump[number] = jumpFloor(number - 1) + jumpFloor(number - 2);
}
};

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

得到递推公式:

F(n)=F(n1)+F(n2)++F(1)+F(0)F(n) = F(n - 1) + F(n - 2) + \cdots + F(1) + F(0)

处理一下可得:

F(n)=2n1F(n) = 2^{n - 1}

然后快速幂一下。

class Solution {
public:
int jumpFloorII(int number) {
return quickPow(number - 1);
};
int quickPow(int n) {
int base = 2;
int r = 1;
while (n) {
if (n & 1 == 1) {
r *= base;
}
base *= base;
n >>= 1;
}
return r;
}
};

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

考虑横着放和竖着放两种情况。发现还是 fibonacci

class Solution {
public:
int rectCover(int number) {
if (number <= 1) {
return number;
}
int first = 1, second = 1, third = first + second;
for (int i = 2; i <= number; i++) {
third = first + second;
first = second;
second = third;
}
return third;
}
};

时间复杂度:O(n)O(n)。不过 fibonacci 写成矩阵快速幂复杂度可以变成 O(logn)O(logn)

的运算会吞掉最右边的 1。

class Solution {
public:
int NumberOf1(int n) {
int count = 0;
while (n) {
count++;
n = (n - 1) & n;
}
return count;
}
};

时间复杂度:O(n)O(n),取决于 n 中 1 的个数。

快速幂。注意一下 exponent 是负数的情况

class Solution {
public:
double Power(double base, int exponent) {
double res = 1.0;
bool reciprocal = exponent < 0;
exponent = abs(exponent);
while (exponent) {
if (exponent & 1 == 1) {
res *= base;
}
base *= base;
exponent >>= 1;
}
if (reciprocal) {
res = 1.0 / res;
}
return res;
}
};

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

因为得保证稳定性,所以想要时间复杂度是 O(n)O(n) 的话,只能开辟一块空间来存储。

class Solution {
public:
void reOrderArray(vector<int> &array) {
stack<int> even;
int cur = 0;
for (int i = 0; i < array.size(); i++) {
if (array[i] & 1 == 1) {
array[cur++] = array[i];
} else {
even.push(array[i]);
}
}
for (int i = array.size() - 1; i >= cur; i--) {
int t = even.top(); even.pop();
array[i] = t;
}
}
};

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

担心 k 会比总长度要大,所以算出总长度后,就可以直接得到对应的正数的位置。

如果题目保证了 k 会比总长度要小,可以用一个 fastslow 指针来做,常数的优化。

/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
class Solution {
public:
ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
int count = 0;
ListNode* now = pListHead;
while (now != NULL) {
count++;
now = now -> next;
}
if (k > count) {
return NULL;
}
int target = count - k;
ListNode* res = pListHead;
while (target--) {
res = res -> next;
}
return res;
}
};

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

反转链表,就改改指针就好了。

/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
class Solution {
public:
ListNode* ReverseList(ListNode* pHead) {
if (pHead == NULL || pHead -> next == NULL) {
return pHead;
}
ListNode* pre = NULL;
ListNode* now = pHead;
while (now) {
ListNode* next = now -> next;
now -> next = pre;
pre = now;
now = next;
}
return pre;
}
};

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

直接遍历就好了。

/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
class Solution {
public:
ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
{
ListNode* dummy = new ListNode(0);
ListNode* now = dummy;
while (pHead1 != NULL && pHead2 != NULL) {
if (pHead1 -> val < pHead2 -> val) {
now -> next = pHead1;
pHead1 = pHead1 -> next;
} else {
now -> next = pHead2;
pHead2 = pHead2 -> next;
}
now = now -> next;
}
now -> next = pHead1 != NULL ? pHead1 : pHead2;
return dummy -> next;
}
};

时间复杂度:O(length(pHead1)+length(pHead2))O(length(pHead1) + length(pHead2))

  1. 看根节点是否一致

  2. 然后比对 Tree2 中各个节点在 Tree1 中都有。

/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class Solution {
public:
bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
{
if (pRoot1 == NULL || pRoot2 == NULL) {
return false;
}
return pRoot1 -> val == pRoot2 -> val && Tree1HasTree2(pRoot1, pRoot2)
|| HasSubtree(pRoot1->left, pRoot2)
|| HasSubtree(pRoot1->right, pRoot2);
}
bool Tree1HasTree2(TreeNode* pRoot1, TreeNode* pRoot2) {
if (pRoot2 == NULL) return true;
if (pRoot1 == NULL) return false;
return pRoot1 -> val == pRoot2 -> val
&& Tree1HasTree2(pRoot1 -> left, pRoot2 -> left)
&& Tree1HasTree2(pRoot1 -> right, pRoot2 -> right);
}
};

时间复杂度:O(mn)O(m*n)

递归一下。

/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class Solution {
public:
void Mirror(TreeNode *pRoot) {
if (pRoot == NULL) return;
Mirror(pRoot -> left);
Mirror(pRoot -> right);
swap(pRoot -> left, pRoot -> right);
}
};

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

顺时针打印矩阵。注意拐弯。

class Solution {
public:
vector<int> printMatrix(vector<vector<int> > matrix) {
int n = matrix.size();
int m = matrix[0].size();
int left = 0, right = m - 1, down = n - 1, up = 0;
vector<int> res;
int i, j;
while (true) {
for(int j = left; j <= right; j++) res.push_back(matrix[up][j]);
if (++up > down) break;
for (int i= up; i <= down; i++) res.push_back(matrix[i][right]);
if (--right < left) break;
for(int j = right; j >= left; j--) res.push_back(matrix[down][j]);
if (--down < up) break;
for (int i = down; i >= up; i--) res.push_back(matrix[i][left]);
if (++left > right) break;
}
return res;
}
};

时间复杂度:O(nm)O(n*m)

多用一个栈用来保存前缀字符里最小的元素。

class Solution {
private:
stack<int> st;
stack<int> minst;
public:
void push(int value) {
st.push(value);
minst.push(minst.empty() || value < minst.top() ? value : minst.top());
}
void pop() {
st.pop();
minst.pop();
}
int top() {
return st.top();
}
int min() {
return minst.top();
}
};

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

模拟栈操作。

class Solution {
public:
bool IsPopOrder(vector<int> pushV,vector<int> popV) {
stack<int> st;
int now = 0;
for (int i = 0; i < popV.size(); i++) {
while (st.empty() || st.top() != popV[i]) {
if (now >= pushV.size()) return false;
st.push(pushV[now++]);
}
st.pop();
}
return true;
}
};
``
时间复杂度:$$O(n)$$
## [从上往下打印二叉树](https://www.nowcoder.com/practice/7fe2212963db4790b57431d9ed259701?tpId=13&tqId=11175&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking)
利用队列层次遍历树。
```cpp
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class Solution {
public:
vector<int> PrintFromTopToBottom(TreeNode* root) {
vector<int> res;
queue<TreeNode*> q;
if (root != NULL) q.push(root);
while (!q.empty()) {
TreeNode* t = q.front(); q.pop();
res.push_back(t -> val);
if (t -> left) q.push(t -> left);
if (t -> right) q.push(t -> right);
}
return res;
}
};

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

后序遍历。最右边的是根节点,然后根据 BST 的性质判断一波。

class Solution {
public:
bool VerifySquenceOfBST(vector<int> sequence) {
if (sequence.size() == 0) return false;
return isLegalPost(sequence, 0, sequence.size() - 1);
}
bool isLegalPost(vector<int>& s, int L, int R) {
if (L >= R) return true;
int seg = L;
while (seg < R && s[seg] < s[R]) {
seg++;
}
for (int i = seg; i < R; i++) {
if (s[i] < s[R]) return false;
}
return isLegalPost(s, L, seg - 1) && isLegalPost(s, seg, R - 1);
}
};

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

DFS。

/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class Solution {
private:
vector<int> cur;
vector<vector<int>> res;
void DFS(TreeNode* root, int number) {
if (number == 0 && root -> left == NULL && root -> right == NULL) {
res.push_back(cur);
}
if (root -> left) {
cur.push_back(root -> left -> val);
DFS(root -> left, number - root -> left -> val);
cur.pop_back();
}
if (root -> right) {
cur.push_back(root -> right -> val);
DFS(root -> right, number - root -> right -> val);
cur.pop_back();
}
}
public:
vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
if (!root) return res;
cur.push_back(root -> val);
DFS(root, expectNumber - root -> val);
cur.pop_back();
sort(res.begin(), res.end(), [](const vector<int>& a, const vector<int>& b) -> bool {
return a.size() > b.size();
});
return res;
}
};

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

一种不用辅助空间的时间复杂度为 O(n)O(n) 的算法。

  1. 遍历一遍,把生成的节点放在各自节点后面

  2. 在遍历一遍,赋值 random 指针。(这里相当于搞了 map 来映射)

  3. 然后分离目标链表和原链表

/*
struct RandomListNode {
int label;
struct RandomListNode *next, *random;
RandomListNode(int x) :
label(x), next(NULL), random(NULL) {
}
};
*/
class Solution {
public:
RandomListNode* Clone(RandomListNode* pHead) {
RandomListNode* dummy = new RandomListNode(0);
RandomListNode* res = dummy;
RandomListNode* now = pHead;
while (now) {
RandomListNode* next = now -> next;
RandomListNode* node = new RandomListNode(now -> label);
now -> next = node;
node -> next = next;
now = next;
}
now = pHead;
while (now) {
RandomListNode* node = now -> next;
RandomListNode* random = now -> random;
if (random) {
node -> random = random -> next;
}
now = node -> next;
}
now = pHead;
while (now) {
RandomListNode* node = now -> next;
now -> next = node -> next;
res -> next = node;
res = res -> next;
now = now -> next;
}
return dummy -> next;
}
};

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

中序遍历搞一下。

/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class Solution {
public:
TreeNode* Convert(TreeNode* pRootOfTree)
{
stack<TreeNode*> st;
TreeNode* now = pRootOfTree;
TreeNode* pre;
TreeNode* res;
while (!st.empty() || now) {
while (now) {
st.push(now);
now = now -> left;
}
if (!st.empty()) {
TreeNode* t = st.top(); st.pop();
if (pre) {
pre -> right = t;
t -> left = pre;
} else {
res = t;
}
pre = t;
now = t -> right;
}
}
return res;
}
};

全排列。

class Solution {
private:
int visit[10];
set<string> s;
string cur;
public:
void dfs(string& str) {
if (cur.length() == str.length()) {
s.insert(cur);
return;
}
for (int i = 0; i < str.length(); i++) {
if (visit[i]) continue;
visit[i] = 1;
cur += str[i];
dfs(str);
cur.pop_back();
visit[i] = 0;
}
}
vector<string> Permutation(string str) {
if (str.length() == 0) return vector<string>();
cur = "";
dfs(str);
vector<string> res(s.begin(), s.end());
return res;
}
};

STL 里的 next_permutation() 也可以做。

class Solution {
public:
vector<string> Permutation(string str) {
vector<string> result;
if(str == "") return result;
do {
result.push_back(str);
} while (next_permutation(str.begin(), str.end()));
return result;
}

时间复杂度:O(n!)O(n!)

多数投票算法 Boyer–Moore majority vote algorithm

class Solution {
public:
int MoreThanHalfNum_Solution(vector<int> numbers) {
int count = 0;
int lastNumber = 0;
for (int i = 0; i < numbers.size(); i++) {
if (count == 0) {
count = 1;
lastNumber = numbers[i];
} else {
count = lastNumber == numbers[i] ? count + 1: count - 1;
}
}
count = 0;
for (int i = 0; i< numbers.size(); i++) {
if (numbers[i] == lastNumber) count++;
}
if (count <= numbers.size() / 2) lastNumber = 0;
return lastNumber;
}
};

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

用堆来实现。

class Solution {
public:
vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
priority_queue<int> q;
for (int i = 0; i < input.size(); i++) {
if (q.size() < k) {
q.push(input[i]);
} else {
if (!q.empty() && q.top() > input[i]) {
q.pop();
q.push(input[i]);
}
}
}
vector<int> res;
if (q.size() == k) {
while (!q.empty()) {
res.push_back(q.top()); q.pop();
}
}
return res;
}
};

时间复杂度:O(nlogk)O(nlogk)

另外可以用快排的思路做。时间复杂度可以是 O(n)O(n)

写出 dp 方程就好了。可以写成以 i 为结尾的数组,最大的连续子数组的和就是当前前缀和减去最小的前缀和。

class Solution {
public:
int FindGreatestSumOfSubArray(vector<int> array) {
int minPrefixSum = 0;
int prefixSum = 0;
int res;
for (int i = 0; i < array.size(); i++) {
prefixSum += array[i];
res = i == 0 ? prefixSum - minPrefixSum : max(res, prefixSum - minPrefixSum);
minPrefixSum = min(minPrefixSum, prefixSum);
}
return res;
}
};

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

找规律。一个位数一个位数做。

举例 1234512345,看百分位 3333left1212right4545

让百分位取 11

  1. left0110-11 是完全没问题的,随便取。这块有 12100=120012*100=1200 种取法。

  2. left1212,发现当前位 x33,所以对 right 是没有限制的,right100100 种取法。

而步骤 2 里取法,是对当前位数有要求的,必须是当前位 x 大于 11 才行。如果当前位等于 11,比如数字是 1214512145 算百分位,对 right 就有限制了,right 只能取到 0450-45,有 4646 种取法。如果当前位等于 00,那 right 没办法取,自然只有 00 种取法。

class Solution {
public:
int NumberOf1Between1AndN_Solution(int n)
{
int res = 0;
for (int i = 1; i <= n; i *= 10) {
res += n / (i * 10) * i;
int x = (n / i) % 10;
res += x > 1 ? i : (n % i + 1) * x;
}
return res;
}
};

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

PS:看别人写法还有用数位 DP 来做的

搞成字符串排序。其实就相当于字段序排序。

class Solution {
public:
string PrintMinNumber(vector<int> numbers) {
vector<string> sn;
for (int i = 0; i < numbers.size(); i++) {
sn.push_back(to_string(numbers[i]));
}
sort(sn.begin(), sn.end(), [](const string& a, const string& b) -> bool {
return a + b < b + a;
});
string res;
for (const auto &piece : sn) res += piece;
return res;
}
};

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

丑数

可以直到下一个丑数一定是当前丑数集合中,乘上 223355 得到的。

维护一个 t2, t3, t5t2 当前丑数中乘上 22 就比当前最大丑数要大的丑数位置。

class Solution {
public:
int GetUglyNumber_Solution(int index) {
vector<int> uglyNumber;
uglyNumber.push_back(1);
int t2 = 0, t3 = 0, t5 = 0;
for (int i = 1; i < index; i++) {
uglyNumber.push_back(min(uglyNumber[t2] *2, min(uglyNumber[t3] * 3, uglyNumber[t5] * 5)));
while (uglyNumber[i] >= uglyNumber[t2] * 2) t2++;
while (uglyNumber[i] >= uglyNumber[t3] * 3) t3++;
while (uglyNumber[i] >= uglyNumber[t5] * 5) t5++;
}
return uglyNumber[index - 1];
}
};

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

开个 map 记一下。

class Solution {
public:
int FirstNotRepeatingChar(string str) {
unordered_map<char, int> m;
for (const auto &c : str) m[c]++;
for (int i = 0; i < str.length(); i++) {
if (m[str[i]] == 1) return i;
}
return -1;
}
};

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