🤣膜拜大佬来了

虽然递归慢，但是写起来爽啊😁 虽然循环快，但是写起来磨啊😭 递归实现 class Solution { public: /** * * @param p TreeNode类 * @param q TreeNode类 * @return bool布尔型 */ bool isSameTree(TreeNode *p, TreeNode *q) { // write code here if (p == nullptr || q == nullptr) return p == q; if (p->val != q->val) return false; bool left = isS...

突破点：如果到某个加油站剩余油量不足0，就从下一个加油站重新开始。 class Solution { public: /** * * @param gas int整型vector * @param cost int整型vector * @return int整型 */ int canCompleteCircuit(vector<int> &gas, vector<int> &cost) { // write code here int size = gas.size(); int sum = 0, current = 0, idx = -1; for (...

符合动态规划的条件：  每个状态与前一个状态有关——设到i的最少步数为f(i)，则f(i) = f(i的上一个点) + 1 初始状态是已知的——刚开始几个点的f与第一个点有关  然后就是实现问题了，两个循环，外循环是遍历每个点，内循环是遍历当前点的“势力范围”。 class Solution { public: /** * * @param A int整型一维数组 * @param n int A数组长度 * @return int整型 */ int jump(int *A, int n) { // write code here // 动态规划：设到i的最少步数为f(i)，则f(i) = f...

二分法，注意考虑溢出 class Solution { public: /** * * @param x int整型 * @return int整型 */ int sqrt(int x) { // write code here // 需要考虑溢出 if (x <= 0) return 0; int left = 1, right = x; while (left < right) { long middle = (left + right) / 2; if (middle * middle <= x && (middle + 1) * (middle + 1...

开心，第一次☝️一遍通过，哇哈哈 其实我也不知道这个为啥叫贪心，是不是因为需要记录前面最大的那个值，所以显得比较贪心？ class Solution { public: /** * * @param A int整型一维数组 * @param n int A数组长度 * @return bool布尔型 */ bool canJump(int* A, int n) { // write code here if (n < 1) return false; int maxStep = A[0]; for (int i = 1; i < n; ++i) { if (maxStep <...

暴力法比较直接，贪心法比较美丽。 为啥可以用贪心呢？因为买必须在卖之前，因此每到一步都可以获取到这一步为止的最佳状态，不断这个最佳状态即可。 class Solution { public: /** * * @param prices int整型vector * @return int整型 */ int maxProfit(vector &prices) { // write code here int minVal = prices[0], profit = 0; for (int i = 1; i < prices.size(); ++i) { if (prices[i] &...

多么痛的领悟 返回条件写错，调了半小时；初始值写错，调了半小时；递归函数名写错，调了半小时。。。🥱 class Solution { public: /** * * @param root TreeNode类 * @return int整型 */ int maxPathSum(TreeNode *root) { // write code here // 后序遍历，记录左右子树最大的路径节点和 // 因为需要分别记录左子树和右子树的最大路径和，用循环实现起来比较麻烦 postOrder(root); return maxSum; } int postOrder(TreeNode *root)...

最直接的想法是双“指针”法，从两端向中间扫描。但题目说的递归法，想了老半天也没想到，看了大佬的解答，原来递归法还需要借助辅助空间。 有两个trick，轻轻松松三分钟，工具函数都不用写：  tolower函数 isalnum函数  class Solution { public: /** * * @param s string字符串 * @return bool布尔型 */ bool isPalindrome(string s) { // write code here int size = s.size(); if (size < 2) return true; // 仅考虑字母和数字，...

没做过这种图论的题目，一脸懵逼😳，看了大佬的解析，自己再总结（fushu）一遍： 将所有路径表示出来——  ->lot->log hit->hot ->cog ->dot->dog这个其实就是求图论中的单源最短路径，图中边是没有权重的，用BFS求解最合适（时间复杂度O(n)）。 class Solution { public: int ladderLength(string start, string end, unordered_set &dict) { queue> record; record.push(make_pair(start,...

大佬30行写出来的东西，硬是给我写了100行，欲哭无泪🥱 大佬写法  这里有一个很奇怪的问题，如果把row和col设置为私有变量，牛客会提示堆栈溢出，但是本地编译器没啥问题。本人才疏学浅，百思不得其姐，求大佬解答  class Solution { public: void solve(vector> &board) { int row = board.size(), col = board[0].size(); if (row < 3 || col < 3) return; // 行 for (int i = 0; i < col; ++i) { dfs(b...

因为一个小朋友分得最少的情况与他旁边两个小朋友👬都有关🐶，因此需要从两边扫描。 细节有点折磨人，改了4次才pass，呵呵哒。 注意三个问题：  扫描的循环开始值，与终止条件，一般来说正着敦不容易出错，反着敦(如第二个循环)就容易把边界条件搞搞搞...错了 需要变更dp元素的情况是，ratings1 = dp2(注意此处等于号) 变更不能++dp[i]，而需要在另一个元素的基础上+1  // // Created by jt on 2020/8/9. // class Solution { public: /** * * @param ratings int整型vector * @retur...

哇哈哈，位运算大法好。。。 两个异或=开心^^ // // Created by jt on 2020/8/8. // #include using namespace std; class Solution { public: /** * * @param A int整型一维数组 * @param n int A数组长度 * @return int整型 */ int singleNumber(int* A, int n) { // write code here int result = 0; for (int i = 0; i < n; ++i) { result ^= A[i]; ...

用两种方法来做（还有第三种方法，以后再看吧0.0）：  动态规划（简单，适合本题） 递归（有人把这叫DFS，我还纳闷了老半天，严格来说本题还有第三种方法BFS）  动态规划的话，理解比较清晰，写起来也比较简单。 递归的话，如果没有优化，会完全通过不了；优化过后，可以和DP媲美。 下面放出DP、DFS（有优化），DFS（无优化）的代码，供大佬们参考。 动态规划 // // Created by jt on 2020/8/8. // #include using namespace std; class Solution { public: bool wordBreak(string s, uno...