2017/11/21 Leetcode 日记
2017/11/21 Leetcode 日记
496. Next Greater Element I
You are given two arrays (without duplicates) nums1 and nums2 where nums1’s elements are subset of nums2. Find all the next greater numbers for nums1's elements in the corresponding places of nums2.
The Next Greater Number of a number x in nums1 is the first greater number to its right in nums2. If it does not exist, output -1 for this number.
class Solution {
public:
vector<int> nextGreaterElement(vector<int>& findNums, vector<int>& nums) {
vector<int> tNums;
for(int i = , sz = findNums.size(); i < sz; i++){
bool finded = false;
int index = ;
for(int j = findN(findNums[i], nums), nsz = nums.size(); j < nsz; j++){
if(nums[j] > findNums[i]){
index = j;
break;
}
}
if(index == ) tNums.push_back(-);
else tNums.push_back(nums[index]);
}
return tNums;
}
// return index of nums[k] == num
int findN(int num, vector<int>& nums){
for(int i = , sz = nums.size(); i < sz; i++){
if(nums[i] == num){
return i;
}
}
return -;
}
};
c++
513. Find Bottom Left Tree Value
Given a binary tree, find the leftmost value in the last row of the tree.
(BFS)
/**
* 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:
int findBottomLeftValue(TreeNode* root) {
queue<TreeNode*> leaves;
leaves.push(root);
while(!leaves.empty()){
TreeNode *temp = leaves.front();leaves.pop();
if(!temp->right && !temp->left && leaves.empty()) return temp->val;
if(temp->right)
leaves.push(temp->right);
if(temp->left)
leaves.push(temp->left);
}
}
};
c++
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None class Solution:
def findBottomLeftValue(self, root):
"""
:type root: TreeNode
:rtype: int
"""
list = []
list.append(root)
while(len(list)):
temp = list.pop()
if(temp.right == None and temp.left == None and len(list) == ):
return temp.val
if(temp.right):
list.append(temp.right)
if(temp.left):
list.append(temp.left)
python3
540. Single Element in a Sorted Array
Given a sorted array consisting of only integers where every element appears twice except for one element which appears once. Find this single element that appears only once.
(二分搜索)
class Solution {
public:
int singleNonDuplicate(vector<int>& nums) {
int left = , right = nums.size()-;
int mid = (left + right) / ;
if(mid == left) return nums[mid];
while(left < right){
if(mid % == ){
if(Left(mid, nums)) {
right = mid-;
mid = (right + left)/;
}
else if(Right(mid, nums)){
left = mid+;
mid = (left + right)/;
}
else return nums[mid];
}else{
if(Left(mid, nums)){
left = mid+;
mid = (left + right)/;
}else{
right = mid-;
mid = (right + left)/;
}
}
}
return nums[mid];
}
bool Left(int i, vector<int>& nums){
int left = ;
if(i == ) return false;
else if (nums[i] != nums[i-]) return false;
else return true;
}
bool Right(int i, vector<int>& nums){
int right = nums.size()-;
if (i == right) return false;
else if (nums[i] != nums[i+]) return false;
else return true;
}
};
c++
647. Palindromic Substrings
Given a string, your task is to count how many palindromic substrings in this string.
The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.
class Solution {
public:
int countSubstrings(string s) {
int left = , right = s.size();
// cout<<right<<endl;
// return traceBack(s, left, right);
int count = ;
for(int i = left; i < right; i++){
for(int j = i; j < right; j++){
bool palindromic = true;
for(int ind = i, end = j; ind <= end; ind++, end--){
if(s[ind] != s[end]) palindromic = false;
}
if(palindromic) count++;
}
}
return count;
}
};
c++
637. Average of Levels in Binary Tree
Given a non-empty binary tree, return the average value of the nodes on each level in the form of an array.
/**
* 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:
vector<double> averageOfLevels(TreeNode* root) {
queue<TreeNode*> q;
queue<long long> level;
vector<double> ave; q.push(root);
level.push();
long long last = , sum = , num = ;
while(!q.empty()){
TreeNode * temp = q.front();q.pop();
long long tp = level.front(); level.pop(); if(temp->right) {q.push(temp->right);level.push(tp+);}
if(temp->left) {q.push(temp->left);level.push(tp+);} if(tp == last){
sum += temp->val;
num ++;
}else{
ave.push_back((double)sum/(double)num);
sum = ;
num = ;
last = tp;
sum += temp->val;
}
if(q.empty()) ave.push_back((double)sum/(double)num);
}
return ave;
}
};
c++
515. Find Largest Value in Each Tree Row
You need to find the largest value in each row of a binary tree.
/**
* 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:
vector<int> largestValues(TreeNode* root) {
queue<TreeNode*> q;
queue<int> level;
vector<int> ave; if(root == NULL) return ave; q.push(root);
level.push();
int last = , max = -(<<);
while(!q.empty()){
TreeNode * temp = q.front();q.pop();
int tp = level.front(); level.pop(); if(temp->right) {q.push(temp->right);level.push(tp+);}
if(temp->left) {q.push(temp->left);level.push(tp+);} if(tp == last){
if(max < temp->val)
max = temp->val;
}else{
ave.push_back(max);
max = -(<<);
last = tp;
if(max < temp->val)
max = temp->val;
}
if(q.empty()) ave.push_back(max);
}
return ave;
}
};
c++
最新文章
- Android四大组件及activity的四大启动模式
- zookeeper学习（一）安装、配置、运行
- WinForms 2015V2版本Reports支持更多种条形码！
- DIV+CSS滑动门效果
- ORACLE创建、修改、删除序列
- Semaphore 和 Mutex
- python多进程中的队列数据共享问题
- 同步or异步
- angular细节整理
- 除了修改WEBCONFIG会导致WEB服务重启外，还有其他的什么操作会导致重启？
- C#第十二天
- 淘淘商城_day09_课堂笔记
- java宠物练习
- 【转】Entity Framework 5.0系列之自动生成Code First代码
- Codeforces 977E：Cyclic Components（并查集）
- (后端)项目中的错误之java中判断字符里面含有某些字符
- SQL Server 阻塞原因分析
- 冒泡排序——Bubble Sort
- springMVC入门-09
- 更新Android Studio 3.1.1碰到的问题