将一个二叉树扁平化。
所有扁平化就是:
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有什么区别。感觉还是很有帮助的……
这个题是http://blog.sina.com.cn/s/blog_672f71fc0101os5r.html
该题目的变形,只是把数组换成了单链表,在单链表查找的时候注意优化,每次二分之后head节点对于left来说依然是head,但是对right来说head节点要更新为mid的那个节点。不然会超时。
class Solution {
public:
ListNode * GetListNthNode(ListNode * h……
模拟题,迭代直到n即可。
class Solution {
public:
string SayStep(string str) {
string strstep = "";
int index = 0;
while(index < str.length()) {
char c = str[index];
int count_c = 1;
int i;
for(i =……
从前往后一个一个标记会超时,后来想了下 某些情况下复杂度是o(n^2)
但是从后往前标记,不一样,近似于o(n)
class Solution {
public:
void FindMin(int A[],int n,bool flag[]) {
if(n <= 0)return;
int min = 0xffff;
for(int i = n-1;i >= 0;i--) {
if(A[i] + i >=……
二分查找的变形,有序数组,允许重复数字,要求查找目标的区间,如果不存在目标,输出[-1,-1]。
class Solution {
public:
void bSearch(int A[],int left,int right,int target,int flag,int &val) {
if(left > right)return ;
int mid = (left + right) / 2;
if(A[mid] == target)……
http://blog.sina.com.cn/s/blog_672f71fc0101phtr.html 该题的变形。
允许重复数字,但是求得的子集中要去除重复子集。
开始超时,后来稍微优化了下,需要检验目前找到的子集中是否有当前需要插入的子集,从后往前,发现size不一样就可以停下了。
当然想的如果还超时就用map
int cmp(int a,int b) {
return a < ……
Unique Paths
http://blog.sina.com.cn/s/blog_672f71fc0101pf1c.html 的变形。加入障碍物,判断一下即可。
struct PPoint
{
int x;
int y;
};
class Solution {
public:
bool CheckIn(int x,int y,PPoint *p,int top)
{
for(int i = 0;i < top;i++)
{
if(x == p[i]……