liuyubobobo / play-leetcode Goto Github PK

why 0082 C++ solution no free up memory？

波波老师，第377题，当测试用例是[3,33,333] 10000时，用递归的方法可以通过，但是当用动态规划的方法main2.cpp时，会出现signed integer overflow的错误，将vector memo改成vector memo也仍然会出现这个错误

比如测试改成：[0, 4, 3, 5]，此时target=10，返回的结果是[3,3]。题目中要求是：不能重复利用这个数组中同样的元素，所以需要把外层循环的判断调整为：nums.length-1。

当然，根据题目中给出的假设：假设每种输入只会对应一个答案，所以不会有我们这样的case，所以处不处理都可以通过测试。

public int minSubArrayLen2(int s, int[] nums) {

	int res = nums.length+1;

	for (int i = 0 ; i<nums.length ; i++){
	    int sum = 0;
	    for (int j = i ; j<nums.length; j++){
		sum+=nums[j];
		if (sum>=s){
		    res = Math.min(res,j-i+1);
		    break;
		}
	    }
	}
	if (res!=nums.length+1){
	    return res;
	}else {
	    return 0;
	}
    }

这样就不需要额外的空间了！

对于main.cpp中的代码，当测试用例是-2147483648仍然会报溢出错误。
Line 8: Char 28: runtime error: negation of -2147483648 cannot be represented in type 'int'; cast to an unsigned type to negate this value to itself (solution.cpp)
改成下面的代码就OK了
long long num = abs((long long)x);

bobo老师有时间提交一下leetcode5号题求最长回文子串的解法吧!!!

老师您好，
当我对
[]
[null]
这两个测试用例进行测试时，我的代码输出
0
0
但是Expected
0
1
好诡异，不过我的代码提交是可以AC的，哈哈哈。

bobo老师好。leetcode 第 289 题。

        R = board.size(), C = board[0].size();
        vector<vector<int>> res(R, vector<int>(C, 0));

        for(int i = 0; i < R; i ++)
            for(int j = 0; j < C; j ++){

                int num = 0;
                for(int ii = max(0, i - 1); ii <= min(i + 1, R + 1); ii ++)
                    for(int jj = max(0, j - 1); jj <= min(j + 1, C + 1); jj ++){
                        if(ii == i && jj == j) continue;
                        num += board[ii][jj];
                    }

                if(board[i][j]){
                    if(num < 2 || num > 3) res[i][j] = 0;
                    else res[i][j] = 1;
                }
                else{
                    if(num == 3) res[i][j] = 1;
                }
            }

        board = res;

假设是一个 4 x 3 的数组，min(j + 1, C + 1) 会导致 jj 的取值可以为 3，而，数组的列数取值只能小于等于2，这样就会导致数组越界。
应该将 R + 1 改为 R - 1，C + 1 改为 C -1。

整形溢出

老师你这道题思路很好，但是对于[1,3,2,-3,-2,5,5,-5,1]这个测试用例，算前缀和，算到2的时候，出现了一次6，然后到5的时候又出现了一次6，但是实际上我们已经把从3- -2这部分删除掉了，所以每次删除中间部分元素的时候，也需要把计算中间部分的map中保存的对应内容也给删掉才可以~

res[1][0] = grid[0][0] + res[0][0];
这条代码是不是有问题呀？应该是res[1][0] = grid[1][0] + res[0][0]
当然直接改的话会出错，因为grid[1][0]可能会发生越界
在下面的for循环中，res[i%2][0] = grid[i][0] + res[(i-1)%2][0];这条代码已经计算了res[1][0]
综上所述， res[1][0] = grid[0][0] + res[0][0]; 这条代码时错误而且多余的

Hi, 刘老师.
在github上看到你的各种算法代码, 激动地流下了口水, 哈哈.
今天在用 java 刷LeetCode 的 222. Count Complete Tree Nodes 遇上了一个疑问, 想请教你一下.

1. 这道求完全二叉树的节点个数问题, 最常规的方式就是递归, 方法一如下:

class Solution {
  public int countNodes(TreeNode root) {
    if(root != null) {
      return 1 + countNodes(root.left) + countNodes(root.right);
    } else {
      return 0;
    }
  }
}

但这个方法在大数据量的情况下会超时, 时间应该超过了 1s.

2. 根据完全二叉树的规律, 寻找最后一个叶子节点的方法二:

class Solution {
  public int countNodes(TreeNode root) {
    int nodes = 0, h = height(root);
    while(root != null) {
      if(height(root.right) + 1 == h) {
        // 右子树高度 = 左子树高度, 最后个叶节点在右子树
        // 加上左子树的所有节点, 往右子树走
        nodes += 1 << h;
        root = root.right;
      } else { // height(root.right) + 2 == h
        // 右子树高度 = 左子树高度 - 1, 最后个叶节点在左子树
        // 加上右子树的所有节点, 往左子树走
        nodes += 1 << (h - 1);
        root = root.left;
      }
      h--;
    }
    return nodes;
  }

  // 完全二叉树, 高度只看左子树
  // 返回的高度比实际高度小1, 为了方便计算满二叉树的节点个数
  public int height(TreeNode root) {
    return root == null ? -1 : 1 + height(root.left);
  }
}

这个方法效率高了许多, 耗时 81ms, Discuss 中基本都是讨论的这种方法.

3. 但是! 当我提交方法二后, 发现排名并不靠前, 下面的类似方法三的却是都类似如下代码:

class Solution {
  public int countNodes(TreeNode root) {
    if(root == null) return 0;
    if (root.val != Integer.MIN_VALUE) {
      root.val = Integer.MIN_VALUE;
      return 1 + countNodes(root.left) + countNodes(root.right);
    } else {
      return 0;
    }
  }
}

这就是在常规方法一的基础上, inplace的改变了每个节点的值, 增加判断条件. 我思考了下, 认为函数递归调用栈与方法一没有区别, 为什么时间却缩短到了 12ms ?

我的问题是: 方式三中增加了原地赋值和判断, 性能为什么提高了如此之多?

感谢刘老师!

将435号题目，main2.cpp代码粘贴到leetcode上运行，会报错error: redefinition of 'struct Interval'

https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof/

输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。
序列内的数字由小到大排列，不同序列按照首个数字从小到大排列
没有找到这个问题的代码，
我的解决方案是：

class Solution {
public:
    vector<vector<int>> findContinuousSequence(int target) {
        int i,j = 0;
        vector<int> vec;
        vec.push_back(1);
        int sum = 0;
        vector<vector<int>> res;

        while(vec[j] <= target){
            if(sum < target){
                sum += vec[j];
                j++;
                vec.push_back(j+1);
            }
            else if(sum > target){
                sum -= vec[i];
                i++;
            }
            else{
                res.push_back(vector<int>(vec.begin()+i, vec.begin()+j));
                sum -= vec[i];
                i++;
            }
        }
        return res;

    }
};

有时会提示 terminate called after throwing an instance of 'std::bad_alloc'
what(): std::bad_alloc
有时是AddressSanitizer:DEADLYSIGNAL
有时使用测试用例又能出现正确解答，
所以我一时找不出无法通过的原因，希望您予以指点改进方法，感激不尽。

rt

209子数组的问题，
while循环中第一个条件 if(r + 1 < nums.size() && sum < s)中的r + 1 < nums.size()
1.要是换成 r < nums.size() -1 答案就不对了，为什么呢？ 想不明白，请老师帮忙
2.还有为啥r从-1开始
谢谢老师～

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {

        assert(s > 0);

        int l = 0 , r = -1; // sliding window: nums[l...r]
        int sum = 0;
        int res = nums.size() + 1;

        while(l < nums.size()){

            if(r + 1 < nums.size() && sum < s)//问题在这里
                sum += nums[++r];
            else
                sum -= nums[l++];

            if(sum >= s)
                res = min(res, r - l + 1);
        }

        return res == nums.size() + 1 ? 0 : res;
    }
};

波波老师您好，请问Play-Leetcode/0021-Merge-Two-Sorted-Lists/cpp-0021/main.cpp里面为什么要写第46行呢？
dummyHead->next = NULL;
谢谢！

在回溯法中如果使用交换2个元素的思路,以下方法是对的:

class Solution {
    List<List<Integer>> ret = new ArrayList<List<Integer>>();
    public List<List<Integer>> permute(int[] nums) {
        if(nums==null || nums.length==0) return ret;

        search(nums, 0);
        return ret;
    }
    private void search(int[] nums, int index) {
        if(index == nums.length) {
            List<Integer> list = new ArrayList<Integer>();
            for(int i : nums){
                list.add(i);
            }
            ret.add(list);
        }
        for(int i=index;i<nums.length;i++) {
            swap(nums, i, index);
            search(nums, index+1);
            swap(nums, i, index);
        }
    }
    private void swap(int[] nums, int i, int j) {
        if(i == j) return;

        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
}

`//K-th-Symbol-in-Grammar-C++ -solution
//Author : Amish Bharti
//NIT Durgapur

#include<bits/stdc++.h>

class Solution {
public:
int kthGrammar(int N, int K) {

    int count = __builtin_popcount(K-1);
      return count & 1;
}

};
`

您好，正如标题中所示，该题第二种利用lambda表达式的解法无法AC。
测试样例如下：

["l5sh 6 3869 08 1295", "16o 94884717383724 9", "43 490972281212 3 51", "9 ehyjki ngcoobi mi", "2epy 85881033085988", "7z fqkbxxqfks f y dg", "9h4p 5 791738 954209", "p i hz uubk id s m l", "wd lfqgmu pvklkdp u", "m4jl 225084707500464", "6np2 bqrrqt q vtap h", "e mpgfn bfkylg zewmg", "ttzoz 035658365825 9", "k5pkn 88312912782538", "ry9 8231674347096 00", "w 831 74626 07 353 9", "bxao armngjllmvqwn q", "0uoj 9 8896814034171", "0 81650258784962331", "t3df gjjn nxbrryos b"]

我根据您的代码修正后AC的代码，请您指正：

class Solution {
public:
    vector<string> reorderLogFiles(vector<string>& logs) {
        sort(logs.begin(), logs.end(), [logs](const string &log1, const string &log2) -> bool {
             int space1 = log1.find(' ');
             string id1 = log1.substr(0, space1);
             string after1 = log1.substr(space1+1);

             int space2 = log2.find(' ');
             string id2 = log2.substr(0, space2);
             string after2 = log2.substr(space2+1);

             if (isalpha(after1[0]) != isalpha(after2[0])) {
                return isalpha(after1[0]);
             }

             if (isalpha(after1[0]))
                return after1 == after2 ? id1 < id2 : after1 < after2;
             return find(logs.begin(), logs.end(), log1) < find(logs.begin(), logs.end(), log2); 
        });
        return logs;
    }
};