58 对称二叉树

题目描述

请实现一个函数，用来判断一棵二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。

示例1

输入：

1
{8,6,6,5,7,7,5}

返回值：

1
true

示例2

输入：

1
{8,6,9,5,7,7,5}

返回值：

1
false

思路：

判断左子树和右子树是否对称，相当对判断左子树的左孩子和右子树的右孩子是否相等，左子树的右孩子和右子树的左孩子是否相等。

采用队列存取每个结点

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
26
27
28
29
30
31
32
33
34
35
36
37
/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    bool isSymmetrical(TreeNode* pRoot) {
        queue<TreeNode*> l;
        queue<TreeNode*> r;
        if(!pRoot)return true;
        l.push(pRoot->left);
        r.push(pRoot->right);
        while(!l.empty()&&!r.empty()){
            TreeNode* tl=l.front();
            TreeNode* tr=r.front();
            if(!tl&&!tr);
            else if(tl&&tr){
                if(tl->val!=tr->val)return false;
                l.push(tl->left);
                l.push(tl->right);
                r.push(tr->right);
                r.push(tr->left);
            }
            else return false;
            l.pop();r.pop();
        }
        return true;
    }
    

};

59 按之字形顺序打印二叉树

题目描述

请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。

示例1

输入：

1
{8,6,10,5,7,9,11}

返回值：

1
[[8],[10,6],[5,7,9,11]]

思路：

维护两个栈，一个保存从前向后的结点，一个保存从后向前的结点。

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    vector<vector<int> > Print(TreeNode* pRoot) {
        stack<TreeNode*> st;
        stack<TreeNode*> st2;
        int flag=1;
        vector<vector<int>> res;
        if(!pRoot)return res;
        st.push(pRoot);
        while(!st.empty()||!st2.empty()){
            int len=st.empty()?st2.size():st.size();
            vector<int> rol;
            while(len>0){
                TreeNode* t;                     
                if(flag==1){         
                    t=st.top();
                    if(t->left)st2.push(t->left);
                    if(t->right)st2.push(t->right);  
                    st.pop();
                }
                else{
                    t=st2.top();
                    if(t->right)st.push(t->right);
                    if(t->left)st.push(t->left);
                    st2.pop();
                }                         
                rol.push_back(t->val);
                len--;               
            }
            flag*=-1;
            res.push_back(rol);
        }
        return res;
    }
    
};

60 把二叉树打印成多行

题目描述

从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。

示例1

输入：

1
{8,6,10,5,7,9,11}

返回值：

1
[[8],[6,10],[5,7,9,11]]

思路：

维护一个队列，广度遍历二叉树，遍历的时候要记住每层的结点数

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
26
27
28
29
30
31
32
33
34
/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
        vector<vector<int> > Print(TreeNode* pRoot) {
            queue<TreeNode*> qu;
            vector<vector<int>> res;
            if(!pRoot)return res;
            qu.push(pRoot);
            while(!qu.empty()){
                TreeNode* t;
                int len=qu.size();
                vector<int> rol;
                while(len>0){
                    t=qu.front();
                    qu.pop();
                    if(t->left)qu.push(t->left);
                    if(t->right)qu.push(t->right);
                    rol.push_back(t->val);
                    len--;
                }
                res.push_back(rol);
            }
            return res;
        }
};

61 序列化二叉树

题目描述

请实现两个函数，分别用来序列化和反序列化二叉树

二叉树的序列化是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过 某种符号表示空节点（#），以 ！ 表示一个结点值的结束（value!）。

二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。

例如，我们可以把一个只有根节点为1的二叉树序列化为”1,”，然后通过自己的函数来解析回这个二叉树

示例1

输入：

1
{8,6,10,5,7,9,11}

返回值：

1
{8,6,10,5,7,9,11}

思路：

先序遍历二叉树，将二叉树的结点转换成字符串，‘#’表示空结点，’!’分割每个结点。

反序列化时以’!’为界将字符串中的数字转化成int类型，并为其创建新结点，以先序遍历的顺序创建树

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    char* Serialize(TreeNode *root) {    
        string s=ser(root);
        char* ch=new char[s.size()];
        strcpy(ch, s.c_str());
        return ch;
    }
    
    string ser(TreeNode* root){
        if(!root)return "#";
        string s=to_string(root->val)+"!";
        s+=ser(root->left);
        s+=ser(root->right);
        return s;
    }
    TreeNode* Deserialize(char *str) {
        int i=0;
        return des(i,str);
    }
    
    TreeNode* des(int& i,char* s){
        if(s[i]=='#'){
            i++;
            return nullptr;
        }
        int num=0;
        while(s[i]!='!'){
            num=num*10+(s[i]-'0');
            i++;
        }
        i++;
        TreeNode* root=new TreeNode(num);
        root->left=des(i,s);
        root->right=des(i,s);
        return root;
    }
};

62 二叉搜索树的第k个结点

题目描述

给定一棵二叉搜索树，请找出其中的第k小的TreeNode结点

输入：

1
{5,3,7,2,4,6,8},3

返回值：

1
{4}

思路：

中序遍历二叉搜索树，返回遇到的第k个结点

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
26
27
/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
TreeNode* KthNode(TreeNode* pRoot, int k) {
    if (!pRoot)return nullptr;
    int i = k;
    TreeNode* res=nullptr;
    dfs(pRoot, i, res);
    return res;
}
void dfs(TreeNode* root, int& i, TreeNode*& res) {
    if (root->left)dfs(root->left, i, res);
    if (i <= 0)return;   
    if (i == 1)res = root;
	i--;
    if (root->right)dfs(root->right, i, res);
}
};

63 数据流中的中位数

题目描述

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。

思路：

创建一个大顶堆一个小顶堆，

第单数个数放入大顶堆，第偶数个数放入小顶堆

放入大顶堆前先放入小顶堆排序，再将小顶堆的堆顶放入大顶堆，确保大顶堆的数全都小于小顶堆

放入小顶堆前先放入大顶堆排序，再将大顶堆的堆顶放入小顶堆，确保小顶堆的数全都大于大顶堆

数据流有单数个时大顶堆的堆顶就是中位数，偶数时取两个堆顶的和*0.5

c++中priority_queue意为优先队列，有三个参数，第一个是数据类型，第二个是存储容器，第三个是排序方法，默认用vector存储，大顶堆。设置greater参数就是小顶堆

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    priority_queue<int> maxHeap;
    priority_queue<int,vector<int>,greater<int>> minHeap;
    void Insert(int num) {
        if(maxHeap.size()==minHeap.size()){
            minHeap.push(num);
            maxHeap.push(minHeap.top());
            minHeap.pop();
        }
        else{
            maxHeap.push(num);
            minHeap.push(maxHeap.top());
            maxHeap.pop();
        }
    }

    double GetMedian() { 
        int lenMax=maxHeap.size(),lenMin=minHeap.size();
        return (lenMax==lenMin)?(maxHeap.top()+minHeap.top())*0.5:maxHeap.top();
    }

};

64 滑动窗口的最大值

题目描述

给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。

窗口大于数组长度的时候，返回空

示例1

输入：

1
[2,3,4,2,6,2,5,1],3

返回值：

1
[4,4,6,6,6,5]

思路：

创建一个双端队列，保存数组的下标，当队首不在窗口内出队，每加入一个新元素就和队尾比较，确保队列是一个降序队列，队首元素是当前滑动窗口最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    vector<int> maxInWindows(const vector<int>& num, unsigned int size) {
        deque<int> dqu;
        vector<int> res;
        if(num.size()==0||size>num.size()||size==0)return res;
        for(int i=0;i<num.size();i++){            
            while(!dqu.empty()&&i-dqu.front()+1>size)dqu.pop_front();
            while(!dqu.empty()&&num[dqu.back()]<num[i])dqu.pop_back();
            dqu.push_back(i);
            if(i+1>=size)res.push_back(num[dqu.front()]);
        }
        return res;
    }
};

65 矩阵中的路径

题目描述

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。 例如
$$
\begin{matrix}
a&b&c&e\
s&f&c&s\
a&d&e&e\
\end{matrix}
$$
矩阵中包含一条字符串”bcced”的路径，但是矩阵中不包含”abcb”路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。

示例1

输入：

1
"ABCESFCSADEE",3,4,"ABCCED"

返回值：

1
true

思路：

用回溯法解决。在搜索中，遇到这条路不可能和目标字符串匹配成功的情况（例如：此矩阵元素和目标字符不同、此元素已被访问，超出矩阵范围），则应立即返回，称之为可行性剪枝 。

每一个元素都可能是起点，所以要遍历矩阵找出符合条件的字符。

深度搜索当前字符的前后左右，搜索过的元素标为空，防止重复搜索，若不匹配返回false

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    bool res=false;
    bool hasPath(string matrix, int rows, int cols, string str) {
        for(int i=0;i<rows;i++){
            for(int j=0;j<cols;j++){
                if(dfs(matrix,str,rows,cols,0,i,j))return true;;
            }
        }
        return false;
    }
    
    bool dfs(string matrix,string str,int rows, int cols,int pre,int i,int j){
        if(i>=rows||i<0||j>=cols||j<0||matrix[j+i*cols]!=str[pre])return false;
        if(pre==(str.size()-1))return true;
        matrix[j+i*cols]='\0';
        bool res=dfs(matrix,str,rows,cols,pre+1,i+1,j)||dfs(matrix,str,rows,cols,pre+1,i-1,j)
            ||dfs(matrix,str,rows,cols,pre+1,i,j+1)||dfs(matrix,str,rows,cols,pre+1,i,j-1);
        return res;
    }
};

66 机器人的运动范围

题目描述

地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？

示例1

输入：

1
5,10,10

返回值：

1
21

思路：

从第一个位置开始，深度搜索上下左右四个位置，判断当前格子是否符合条件，不符合返回0，且不往这个格子后搜索，相当于路被堵住了。符合则返回值+1

设置flag数组记录走过的格子，避免重复

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:
    int row,col;
    int movingCount(int threshold, int rows, int cols) {
        int res=0;
        row=rows;col=cols;
        vector<vector<bool>> flag(rows,vector<bool>(cols,true));
        res=Compare(threshold, 0, 0, flag);
        return res;
    }
    
    int Compare(int k,int i,int j,vector<vector<bool>>& flag){
        if(i>=row||i<0||j>col||j<0||!flag[i][j])return 0;
        string s1=to_string(i);
        string s2=to_string(j);
        int num=0;
        for(auto c:s1)num+=(c-'0');
        for(auto c:s2)num+=(c-'0');
        flag[i][j]=false;
        if(num>k)return 0;
        int res=Compare(k, i+1, j, flag)+Compare(k, i-1, j, flag)
            +Compare(k, i, j+1, flag)+Compare(k, i+1, j-1, flag)+1;
        return res;
    }
};

67 剪绳子

题目描述

给你一根长度为n的绳子，请把绳子剪成整数长的m段（m、n都是整数，n>1并且m>1，m<=n），每段绳子的长度记为k[1],…,k[m]。请问k[1]x…xk[m]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

输入：

1
8

返回值：

1
18

思路：

利用动态规划的思想

我们想要求长度为n的绳子剪掉后的最大乘积，可以从前面比n小的绳子转移而来
用一个dp数组记录从0到n长度的绳子剪掉后的最大乘积，也就是dp[i]表示长度为i的绳子剪成m段后的最大乘积，初始化dp[2] = 1
我们先把绳子剪掉第一段（长度为j），如果只剪掉长度为1，对最后的乘积无任何增益，所以从长度为2开始剪
剪了第一段后，剩下(i - j)长度可以剪也可以不剪。如果不剪的话长度乘积即为j * (i - j)；如果剪的话长度乘积即为j * dp[i - j]。取两者最大值max(j * (i - j), j * dp[i - j])
第一段长度j可以取的区间为[2,i/2+1]，大于i/2+1会剪重复，对所有j不同的情况取最大值，因此最终dp[i]的转移方程为
dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]))
最后返回dp[n]即可

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int cutRope(int number) {
        vector<int> dp(number+1);
        dp[2]=1;
        for(int i=3;i<=number;i++){
            for(int j=2;j<=(i/2)+1;j++){
                dp[i]=max(dp[i],max(j*(i-j),j*dp[i-j]));
            }
        }
        return dp[number];
    }
};