01 二维数组中的查找
题目描述
在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
示例1
输入：
1
| 7,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]
|
返回值：
思路：
由于数组从左到右递增，从上到下递增，那么从右上角开始看，设有x行y列
若target比a[0,y]大，则target在a[0,y]下方
若target比a[0,y]小，则target在a[0,y]左方
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public:
bool Find(int target, vector<vector<int> > array) {
if(array.size()==0||array[0].size()==0)return false;
int x=0;
int y=array[0].size()-1;
bool ans=false;
while(x<array.size()&&y>=0){
if(array[x][y]==target){
ans=true;
break;
}
if(array[x][y]>target){
y--;
}
else{
x++;
}
}
return ans;
}
};
|
02 替换空格
题目描述
请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
思路：
创建一个新的字符串，遍历给出的字符串，遇到空格时新字符串加“%20”，若不是空格则加上对应的字符
ps：题目给出的函数返回值为void，所以要利用strcpy函数将新字符复制到老字符串的地址空间下
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public:
void replaceSpace(char *str,int length) {
string s=str;
string ans;
for(char c:s){
if(c==' ')ans+="%20";
else ans+=c;
}
strcpy(str, ans.c_str());
}
};
|
03 从尾到头打印链表
题目描述
输入一个链表，按链表从尾到头的顺序返回一个ArrayList。
示例1
输入：
返回值：
思路：
利用递归，遍历链表，自底向上保存在容器中
1
2
3
4
5
6
7
8
9
10
| class Solution {
public:
vector<int> printListFromTailToHead(ListNode* head) {
vector<int> ans;
if(!head)return ans;
ans=printListFromTailToHead(head->next);
ans.push_back(head->val);
return ans;
}
};
|
04 重建二叉树
题目描述
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
示例1
输入：
1
| [1,2,3,4,5,6,7],[3,2,4,1,6,5,7]
|
返回值：
思路：
前序遍历二叉树的顺序是根左右，中序遍历二叉树的顺序是左根右
前序遍历数组中第一个节点为根节点，找出中序遍历数组中根节点的位置n
两个数组n+1往后都是右子树的节点
利用递归的思想，先建好左右子树，最后合成二叉树
递归出口为最后剩下一个元素则返回
遇到的问题
c++中copy函数返回值是迭代器，不是容器，需要自己写一个函数完成数组的复制
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
| class Solution {
public:
TreeNode* reConstructBinaryTree(vector<int> pre, vector<int> vin) {
if (pre.size() == 0)return nullptr;
if (pre.size() == 1) {
return new TreeNode(pre[0]);
}
TreeNode* root = new TreeNode(pre[0]);
int rootindex = 0;
for (int i = 0; i < vin.size(); i++) {
if (pre[0] == vin[i]) {
rootindex = i;
break;
}
}
root->left = reConstructBinaryTree(mycopy(1, rootindex+1, pre),
mycopy(0, rootindex , vin));
root->right = reConstructBinaryTree(mycopy(rootindex + 1, pre.size(), pre),
mycopy(rootindex + 1, vin.size(), vin));
return root;
}
vector<int> mycopy(int l, int r, vector<int> v) {
return vector<int>(v.begin() + l, v.begin() + r);
}
};
|
