leetcode解题思路分析（七十）605

种花问题
给你一个整数数组 flowerbed 表示花坛，由若干 0 和 1 组成，其中 0 表示没种植花，1 表示种植了花。另有一个数 n ，能否在不打破种植规则的情况下种入 n 朵花？能则返回 true ，不能则返回 false。

贪心算法遍历一遍即可。

class Solution { 
public:
    bool canPlaceFlowers(vector<int>& flowerbed, int n) { 
        int count = 0;
        int m = flowerbed.size();
        int prev = -1;
        for (int i = 0; i < m; i++) { 
            if (flowerbed[i] == 1) { 
                if (prev < 0) { 
                    count += i / 2;
                } else { 
                    count += (i - prev - 2) / 2;
                }
                if (count >= n) { 
                    return true;
                }
                prev = i;
            }
        }
        if (prev < 0) { 
            count += (m + 1) / 2;
        } else { 
            count += (m - prev - 1) / 2;
        }
        return count >= n;
    }
};

根据二叉树创建字符串
你需要采用前序遍历的方式，将一个二叉树转换成一个由括号和整数组成的字符串。

分别考虑是否有子节点、有左儿子还是右儿子等情况即可

/** * 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:
    string tree2str(TreeNode* t) { 
        if (t == nullptr)
        { 
            return "";
        }
        else if (t->left == nullptr && t->right == nullptr)
        { 
            return to_string(t->val);
        }
        else if (t->right == nullptr)
        { 
            return to_string(t->val) + "(" + tree2str(t->left) + ")";
        }
        else
        { 
            return to_string(t->val) + "(" + tree2str(t->left) + ")" + "(" + tree2str(t->right) + ")" ;
        }
    }
};

在系统中查找重复文件
给定一个目录信息列表，包括目录路径，以及该目录中的所有包含内容的文件，您需要找到文件系统中的所有重复文件组的路径。一组重复的文件至少包括二个具有完全相同内容的文件。

哈希表的简单使用

class Solution { 
public:
  vector<vector<string>> findDuplicate(vector<string> &paths) { 
    //key为文件内容，value为目录+文件名
    unordered_map<string, vector<string>> m;
    for (string &s : paths) { 
      //' '前的字符串即为目录，为其追加一个'/'
      int start = s.find(' ');
      string path = s.substr(0, start).append(1, '/');
      //寻找`(`
      int leftBracket = s.find('(', start);
      while (leftBracket != -1) { 
        //根据'('和' '的位置确定文件名
        string fileName = s.substr(start + 1, leftBracket - start - 1);
        //寻找`)`
        int rightBracket = s.find(')', leftBracket);
        //根据'('和')'的位置确定文件内容，将其作为key，目录和文件名作为value
        m[s.substr(leftBracket + 1, rightBracket - leftBracket - 1)].emplace_back(path + fileName);
        //继续寻找该目录的下一个文件
        start = rightBracket + 1;
        leftBracket = s.find('(', start);
      }
    }
    //找出具有重复内容的文件路径
    vector<vector<string>> result;
    for (auto &p : m) { 
      if (p.second.size() >= 2) { 
        result.emplace_back(p.second);
      }
    }
    return result;
  }
};

有效三角形的个数
给定一个包含非负整数的数组，你的任务是统计其中可以组成三角形三条边的三元组个数。

本题主要有几个重点：1.想到先排序从而方便解决问题 2.排序之后暴力搜索可以剪枝 3.剪枝之后每次其实第三条边从上次开始计算即可 4.考虑到数据量很大，第三条边从数组尾部开始向前，第二条边向后。所以这也可以看作是双指针滑动了

class Solution { 
public:
    int triangleNumber(vector<int>& nums) { 
        if (nums.size() < 3) return 0;
        sort(nums.begin(), nums.end(), greater<int>());
        int res = 0;
        int N = nums.size();
        for (int i = 0; i < N - 2; ++i) { 
            int l = i + 1;
            int r = N - 1;
            while (l < r) { 
                if (nums[l] + nums[r] <= nums[i]) { 
                    --r;
                } else { 
                    res += r - l;
                    ++l;
                }
            }
        }
        return res;
    }
};

合并二叉树
给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。

深度搜索或者广度优先皆可

class Solution { 
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) { 
        if (t1 == nullptr) { 
            return t2;
        }
        if (t2 == nullptr) { 
            return t1;
        }
        auto merged = new TreeNode(t1->val + t2->val);
        merged->left = mergeTrees(t1->left, t2->left);
        merged->right = mergeTrees(t1->right, t2->right);
        return merged;
    }
};

有趣的电影
某城市开了一家新的电影院，吸引了很多人过来看电影。该电影院特别注意用户体验，专门有个 LED显示板做电影推荐，上面公布着影评和相关电影描述。作为该电影院的信息部主管，您需要编写一个 SQL查询，找出所有影片描述为非 boring (不无聊) 的并且 id 为奇数的影片，结果请按等级 rating 排列。

Write your MySQL query statement below
select *
from cinema
where mod(id, 2) = 1 and description != ‘boring’
order by rating DESC
;
任务调度器
给你一个用字符数组 tasks 表示的 CPU 需要执行的任务列表。其中每个字母表示一种不同种类的任务。任务可以以任意顺序执行，并且每个任务都可以在 1 个单位时间内执行完。在任何一个单位时间，CPU 可以完成一个任务，或者处于待命状态。然而，两个相同种类的任务之间必须有长度为整数 n 的冷却时间，因此至少有连续 n 个单位时间内 CPU 在执行不同的任务，或者在待命状态。你需要计算完成所有任务所需要的最短时间。

挨个排列即可

class Solution { 
public:
    int leastInterval(vector<char>& tasks, int n) { 
        unordered_map<char, int> freq;
        for (char ch: tasks) { 
            ++freq[ch];
        }
        // 最多的执行次数
        int maxExec = max_element(freq.begin(), freq.end(), [](const auto& u, const auto& v) { 
            return u.second < v.second;
        })->second;
        // 具有最多执行次数的任务数量
        int maxCount = accumulate(freq.begin(), freq.end(), 0, [=](int acc, const auto& u) { 
            return acc + (u.second == maxExec);
        });
        return max((maxExec - 1) * (n + 1) + maxCount, static_cast<int>(tasks.size()));
    }
};