判断一二叉棵树是否为BST。
结合BST的特征一直递归着找就行。
class Solution {
public:
bool result;
enum Flag {left,right,leftright};
void isValidBSTStep(TreeNode * root,int val1,int val2,Flag flag) {
switch(flag){
case left:
if(root->val &l……
无穷背包?
输入2 3 6 7
输出2 3 6 7所有能构成7的情况。
int cmp(int a,int b) {
return a < b;
}
struct ValNode {
ValNode():IsExist(false){set_v.clear();}
vector<vector<int>>set_v;
bool IsExist;
};
class Solution {
public:
bool CheckIsExist(vector<int>&ite……
输入n,获得1-n生成的所有BTS
class Solution {
public:
vector<TreeNode *> genTreeNodes(int left,int right) {
vector<TreeNode *> nodes;
nodes.clear();
if(left > right) {
nodes.push_back(NULL);
return nodes;
……
模拟pow,注意超时和n为负数的情况。
可以二分下去这样复杂度为log(n)
class Solution {
public:
double powstep(double x,int n) {
if(n == 0)return 1.0;
if(n == 1)return x;
if(n == 2)return x<em>x;
if(n % 2 == 0) {
return powstep(powstep(x,n/2),2);
……
单链表划分。选择一个val x然后单链表中比x值小的节点在前,大的在后,但是小与小,大与大之间保持原位置。
想法:
先找到第一个比x小的值,放到最前面。
再找到第一个比x大的值。
接下来就是从x大的值的节点后面开始枚举,大的继续,出现小的,交换到第一个比x大的值前面。
class Solution {
public:
ListNode <……
序列化二叉树,但是行输出时从左到右从右到左交替进行。
class Solution {
public:
enum Direciton {left,right};
vector<vector<int> > zigzagLevelOrder(TreeNode <em>root) {
vector<vector<int>> result;
result.clear();
……
将一个二叉树扁平化。
所有扁平化就是:
1
/ \
2 5
/ \ \
3 4 6
1
\
2
\
3
\
4
\
5
\
6
each node’s right child points to the next node of a pre-order traversal.
class Solution {
public:
……
八皇后问题,输出各解决方案。
class Solution {
public:
int count;
int <em>x;
int *y;
int index;
bool *rows,</em>cols,<em>ltrb,</em>rtlb;
vector<vector<string>> ans;
vector<string>item;
void SetFalse(b……
八皇后问题,输出解法数量即可。
class Solution {
public:
int count;
bool <em>rows,</em>cols,<em>ltrb,</em>rtlb;
void SetFalse(bool *arrayin,int n) {
for(int i = 0;i < n;i++)
arrayin[i] = false;
}
void Move(int row,int n) {
……
乱序的情况下,找最长连续子序列。
说实话,这个题我确实没在o(n)的复杂度下做出来。
看了别人的代码才恍然大悟。
不过之前有想到用hash不过我记得STL的map是o(logn)的查找复杂度,所以最终的复杂度是o(nlogn)当时就放弃了。
今天好好的了解了下
什么是散列表,map set hash_map hash_set有什么区别。感觉还是很有帮助的……