102 二叉树的层次遍历
因为题目要求遍历的结果是一个二维列表,每一层节点的遍历结果是一个列表,所以每次出了入队树节点,还有该节点的深度。
time: 4ms, memory: 15MB
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
struct DNode{
int depth;
TreeNode *t;
DNode(int d, TreeNode *n): depth(d), t(n){}
};
vector<vector<int>> levelOrder(TreeNode* root) {
queue<DNode> q;
vector<vector<int>> v;
if(!root) return v;
// initialize
q.push(DNode(0, root));
TreeNode *cur;
int cur_dep = 0;
vector<int> tmp_v;
while(!q.empty()){
cur = q.front().t;
if(q.front().depth > cur_dep){
cur_dep = q.front().depth;
v.push_back(tmp_v);
tmp_v.clear();
}
q.pop();
tmp_v.push_back(cur -> val);
if(cur -> left) q.push(DNode(cur_dep+1, cur -> left));
if(cur -> right) q.push(DNode(cur_dep+1, cur -> right));
}
v.push_back(tmp_v);
return v;
}
};
108 将有序数组转换为二叉搜索树
昨天做过一个二叉搜索树的题,给定的有序数组其实就是二叉树的中序遍历结果。恢复的结果有很多种,但由于限定了左右子树的高度差不能超过1,所以范围就小了很多。其实,还是有两种不同的做法,我选择的是左边高右边低;还可以左边低右边高,应该也不算错。
解这种二分问题最怕的就是边界,第一关键就是统一区间,要么两边都左闭右开,要么两边都左闭右闭;第二就是边界条件,如果左闭右开,边界条件就是右下标小于等于左下标;否则,边界条件就是右下标小于左下标。
最近不统计运行时间和内存了,每次跑都不一样,不太科学。
代码:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* helperBST(vector<int>& nums, int left, int right){
// [, )
if(right <= left) return NULL;
int mid = (right - left) / 2 + left;
TreeNode *root = new TreeNode(nums[mid]);
root -> left = helperBST(nums, left, mid);
root -> right = helperBST(nums, mid+1, right);
return root;
}
TreeNode* sortedArrayToBST(vector<int>& nums) {
if(nums.size() == 0) return NULL;
TreeNode *root = helperBST(nums, 0, nums.size());
return root;
}
};
88 合并两个有序数组
最直接的想法就是用归并排序的想法,引入额外的数组来存放两个数组合并后的结果,最后拷贝回数组1:
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int i=0, j = 0, k = 0;
vector<int> nums;
if(n==0) return;
while(i < m && j < n){
if(nums1[i] <= nums2[j]) nums.push_back(nums1[i++]);
else nums.push_back(nums2[j++]);
}
while(i < m) nums.push_back(nums1[i++]);
while(j < n) nums.push_back(nums2[j++]);
nums1.clear();
for(i = 0; i < m+n; i++)
nums1.push_back(nums[i]);
}
};
后来注意到,题干说,假设数组1有足够的空间,理解一下就是,m不是nums1的size。那就很简单了,从后向前扫描两个数组,将当前比较的更大的值拷贝到指定的位置。因为是从后向前扫描,所以不用担心覆盖问题。
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int i = m - 1, j = n - 1, k = m + n - 1;
while(k >= 0 && i >= 0 && j >= 0){
if(nums1[i] >= nums2[j]){
nums1[k--] = nums1[i--];
}
else nums1[k--] = nums2[j--];
}
while(k >= 0){
if(i >= 0) nums1[k--] = nums1[i--];
else nums1[k--] = nums2[j--];
}
}
};
278 第一个错误的版本
标签:二分查找
比较简单的二分查找题目,还是需要注意区间和边界。
1)经过几题我发现,比较好的卡区间的方法就是,确保正确答案一定在选择的区间里,已经验证过的错误的答案一定不在选择的区间里。
2)至于防止死循环的方法,就是确保每次区间一定是缩小的。这样也可以保证算法是正确的。
3)区间中点的算法:left + 1/2(right - left); 如果采用1/2(right + left),可能回导致溢出。
// Forward declaration of isBadVersion API.
bool isBadVersion(int version);
class Solution {
public:
int firstBadVersion(int n) {
int l = 1, r = n, mid;
while(l < r){
mid = l + (r - l) / 2;
if(isBadVersion(mid)) r = mid;
else l = mid + 1;
if(l == r) break;
}
return l;
}
};
网友评论