题目列表
JZ3 数组中重复的数字
时间空间复杂度都为\(O(n)\)，直接建一个数组a，初始化全0，出现数i就a[i]++
int duplicate(vector<int>& numbers) {
const int N = 10005;
vector<int> count(N, 0);
for(int i = 0; i < numbers.size(); i ++){
count[numbers[i]] ++;
}
for(int i = 0; i < count.size(); i ++){
if(count[i] > 1){
return i;
}
}
return -1;
}
JZ4 二维数组中的查找
由题：二维数组从左到右从上到下递增，则a[i][j]是该元素到右下角的矩阵里最小的元素
为了控制不走回头路，从右上方或者左下方的元素开始。
从右上方开始：target < a[i][j]， target在该列左边
target > a[i][j]， target在该行下方
如果超出了矩阵范围还没找到，说明没有这个数。
bool Find(int target, vector<vector<int> > array) {
int row = array.size() - 1;
int col = array[0].size() - 1;
if(array.empty() || array[0].empty()) return false;
int i = 0, j = col;
while(i <= row && j >= 0){
if(target > array[i][j])
i ++;
else if(target < array[i][j])
j --;
else{
return true;
}
}
return false;
}
JZ5 替换空格
复习了一下string的用法
既可以用str[i]直接遍历，也可以用iterator遍历，改字符可以用string.insert
注意string.append用法
//s[i]写法
string replaceSpace(string s) {
// write code here
for(int i = 0; i < s.size(); i ++){
if(s[i] == ' '){
s[i] = '%';
s.insert(i + 1, "20");
}
}
return s;
}
//iterator写法
string replaceSpace(string s) {
// write code here
int length = s.length();
string ans = "";
string::iterator iter = s.begin();
for(; iter < s.end(); iter ++){
if(*iter == ' ')
ans.append("%20");
else {
ans.append(iter, iter + 1);
}
}
return ans;
}
JZ6 从尾到头打印链表
vector逆序写法
反向迭代器：rbegin()指向最后一个元素，rend()指向第一个元素前面的位置
vector<int> printListFromTailToHead(ListNode* head) {
vector<int> res;
ListNode* l;
l = head;
while(l != nullptr){
res.push_back(l -> val);
l = l -> next;
}
return vector<int>(res.rbegin(), res.rend());
}
JZ7 重建二叉树
用递归做，根据前序遍历序列的第一个数（当前根节点）把中序遍历分成左右子树，根据左右子树序列的长度，分出左右子树的前序遍历序列，对左右子树进行递归，返回值分别为当前root的left和right
TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
if(pre.empty() || vin.empty()) return NULL;
TreeNode *treenode = new TreeNode(pre[0]);
int l = distance(vin.begin(), find(vin.begin(), vin.end(), pre[0]));
vector<int> pre1(pre.begin() + 1, pre.begin() + l + 1);
vector<int> pre2(pre.begin() + l + 1, pre.end());
vector<int> vin1(vin.begin(), vin.begin() + l);
vector<int> vin2(vin.begin() + l + 1, vin.end());
treenode -> left = reConstructBinaryTree(pre1, vin1);
treenode -> right = reConstructBinaryTree(pre2, vin2);
return treenode;
}
JZ8 二叉树的下一个结点
分类讨论：1. 没有右子树，返回寻找父节点，如果当前节点是父节点的右儿子，就继续向上寻找父节点，直到当前节点是父节点的左儿子。如果无父节点返回null
2.有右子树，找右子树中最左边的节点。
段错误一发，原因是分类讨论1时，找父节点忘记判断父节点是否存在
TreeLinkNode* GetNext(TreeLinkNode* pNode) {
TreeLinkNode* node;
if(pNode == nullptr) return NULL;
if(pNode -> right == nullptr){
if(pNode -> next == nullptr) return NULL;
node = pNode->next;
while(node->right == pNode){
pNode = node;
if(node->next == nullptr) return NULL;
node = node->next;
}
return node;
}
else{
node = pNode->right;
while(node->left != nullptr){
node = node->left;
}
return node;
}
}