wy的leetcode刷题记录_Day36

wy的leetcode刷题记录_Day36

时间：

816. 模糊坐标

今天的每日一题是：816. 模糊坐标

题目介绍

我们有一些二维坐标，如 “(1, 3)” 或 “(2, 0.5)”，然后我们移除所有逗号，小数点和空格，得到一个字符串S。返回所有可能的原始字符串到一个列表中。

原始的坐标表示法不会存在多余的零，所以不会出现类似于"00", “0.0”, “0.00”, “1.0”, “001”, "00.01"或一些其他更小的数来表示坐标。此外，一个小数点前至少存在一个数，所以也不会出现“.1”形式的数字。

最后返回的列表可以是任意顺序的。而且注意返回的两个数字中间（逗号之后）都有一个空格。

示例 1:
输入: “(123)”
输出: [“(1, 23)”, “(12, 3)”, “(1.2, 3)”, “(1, 2.3)”]

示例 2:
输入: “(00011)”
输出: [“(0.001, 1)”, “(0, 0.011)”]
解释: 0.0, 00, 0001 或 00.01 是不被允许的。

思路

浏览题目之后，我认为这道题应该是一个切分字符串然后进行特殊值处理的问题。然后细读完之后我的思路是这样的：其实这道题给了你去除了“， ”（分割x和y）、“.“（分割了整数部分和小数部分）得到的一串数字，我们的任务就是加上”， "和“.”。于是我们第一层遍历是将字符串s分成俩部分x和y，第二层遍历是遍历x和y，将x和y都划分为整数形式和小数形式。其中特别需要注意的俩点：

• 如果整数部分不为0的话，那么整数部分的最高位不能为0
• 小数部分的末位不能位0

同时满足上述俩点才能切分整数和小数，否则不切分。最后我们将该层的切分后的小数部分和整数部分拼接，最后按层拼接答案即可。

代码

class Solution {
public:
    vector<string> ambiguousCoordinates(string s) {
        //if(s[n-1]==0)
        int n=s.size();
        s=s.substr(1,n-2);
        n=s.size();
        vector<string> ans;
        for(int i=1;i<n;i++)
        {
            string left=s.substr(0,i);
            string right=s.substr(i);
            vector<string> point_left=getSpiltStr(left);
            vector<string> point_right=getSpiltStr(right);
            if(point_right.empty()||point_left.empty())
                continue;
            for(auto l:point_left)
                for(auto r:point_right)
                    ans.push_back("("+l+", "+r+")");
        }
        return ans;
    }

    vector<string> getSpiltStr(string s)
    {
        int n=s.size();
        vector<string> SpiltStr;
        if(s[0]!='0'||s=="0")//将s作为一个整数 不加小数点的情况
            SpiltStr.push_back(s);
        for(int i=1;i<n;i++)//添加小数点
        {
            string point_left=s.substr(0,i);//小数点左
            string point_right=s.substr(i);//小数点右
            if(point_left[0]=='0'&&i!=1||point_right.back()=='0')
            //小数点左边的整数部分的第一位不能为0，除非整数部分就是0
            //小数点右边的小数部分的最后一位不能为0
                continue;
            SpiltStr.push_back(point_left+"."+point_right);
        }
        return SpiltStr;
    }

};
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

收获

暴力模拟法：还是需要点脑子的，不能直接暴力枚举，得先确定他需要的是什么，然后怎样实施这个暴力解法。

226. 翻转二叉树

226. 翻转二叉树

题目介绍

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

示例 1：

输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]

示例 2：
> 输入：root = [2,1,3]
输出：[2,3,1]

思路

方法一：DFS：前中后序都可以，本题使用的是前序。遍历到根节点交换左右节点然后继续向下搜索其交换后的左右节点，同理递归。
方法二：BFS：遍历每一层，该层是已经转换完成的节点，只需交换其左右节点即可，这里需要注意写代码时要考虑这个节点是空节点的情况（空节点没有左节点和右节点）。

代码

DFS:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        dfs(root);
        return root;
    }
    void dfs(TreeNode* node)
    {
        if(!node)
            return;

        swap(node->left,node->right);

        dfs(node->left);
        dfs(node->right);
    }
    void swap(TreeNode*& node1,TreeNode*& node2)
    {
        TreeNode* node;
        node=node1;
        node1=node2;
        node2=node;
    }
};
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

BFS

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(!root)
            return root;
        queue<TreeNode*> qu;
        qu.push(root);
        while(!qu.empty())
        {
            int n=qu.size();
            for(int i=0;i<n;i++)
            {
                TreeNode* node=qu.front();
                qu.pop();
                // if(node->left==nullptr&&node->right==nullptr)
                if(node==nullptr)
                    continue;
                swap(node->left,node->right);
                qu.push(node->left);
                qu.push(node->right);
            }
        }
        return root;
    }

    void swap(TreeNode*& node1,TreeNode*& node2)
    {
        TreeNode* node;
        node=node1;
        node1=node2;
        node2=node;
    }
};
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

收获

巩固了DFS和BFS