小编Zha*_*nan的帖子

组合
给定两个整数n和k,返回1 ... n中k个数的所有可能组合.
例如,如果n = 4且k = 2,则解决方案是:

[
   [2, 4],
   [3, 4],
   [2, 3],
   [1, 2],
   [1, 3],
   [1, 4],
]

Run Code Online (Sandbox Code Playgroud)

---

我个人认为,
时间复杂度= O(n ^ k),n和k是输入.

---

谢谢你的帮助.
最后,时间复杂度= O(C(n,k)*k)= O((n!/(k!*(n - k)!))*k),n和k是输入,
因为,每次当我们得到一个组合时,我们需要将子列表列表复制到one_rest,即O(k),有C(n,k)*k.

---

C++

#include <vector>
using namespace std;

class Solution {
public:
    vector<vector<int> > combine(int n, int k) {
        vector<vector<int>> list;

        // Input validation.
        if (n < k) return list;

        int start = 1;
        vector<int> subList;
        helper(n, k, start, list, subList);

        return list;
    } …

在我以前的知识中:当我们想要检查double或float是否等于0.0时,
我们不应该这样写:

double x = 0.0;
if (x == 0.0) System.out.println("yes");
else System.out.println("no");

但几分钟前,我再次尝试过,在Java(1.7)和C++(Apple LLVM 6.0版)下,编写这样的问题没有问题!我分别在Java和C++下尝试过"double"类型和"float"类型.

我的问题:

• 我错过了什么,或者我们真的可以在当前的Java和C++下检查double或float.
• 如果可以的话,我们是否可以在Java和C++的早期版本下完成它？

float x = 0.0f;
if (x == 0) System.out.println("yes");
else System.out.println("no");

float y = 100.0f - 50.0f*2.0f + 45.0f*3 - 135.0f;
if (y == 0.0f) System.out.println("yes");
else System.out.println("no");

if …

回文分区

给定一个字符串 s，分区 s 使得分区的每个子串都是一个回文。
返回 s 的所有可能的回文分区。

我个人认为，时间复杂度是 O(n^n)，n 是给定字符串的长度。

谢谢Dan Roche，时间复杂度 = O(n* (2^n))，请查看下面的详细信息。

#include <vector>
using namespace std;

class Solution {
public:
vector<vector<string>> partition(string s) {
    vector<vector<string>> list;
    vector<string> subList;

    // Input validation.
    if (s.length() <= 1) {
        subList.push_back(s);
        list.push_back(subList);
        return list;
    }

    int len = s.length();
    vector<vector<bool>> memo(len, vector<bool>(len));
    for (int i = 0; i < len; i ++) {
        for (int j = 0; j < len; j ++) {
            if (i >= …

通配符匹配
实现通配符模式匹配，并支持' ？'和' * '。

• '？' 匹配任何单个字符。
• '*'匹配任何字符序列（包括空序列）。

匹配项应覆盖整个输入字符串（而非部分）。

函数原型应为：
bool isMatch（const char * s，const char * p）

一些例子：

• isMatch（“ aa”，“ a”）吗？假
• isMatch（“ aa”，“ aa”）吗？真正
• isMatch（“ aaa”，“ aa”）吗？假
• isMatch（“ aa”，“ *”）吗？真正
• isMatch（“ aa”，“ a *”）吗？真正
• isMatch（“ ab”，“？*”）吗？真正
• isMatch（“ aab”，“ c * a * b”）吗？假

---

题：

• 什么时间复杂？
• 什么是空间复杂度？

我个人认为

• 时间复杂度高度依赖于“输入”，不能像T = O（？）那样写出来。
• 空间复杂度= O（min（sLen，pLen）），因为最大递归深度= O（min（sLen，pLen））。

尝试过：
写出时间复杂度表达式，然后画出递归树：

TC Expression => T(n) = T(n - 1) + O(1),            when pChar == '?' or pChar == sChar,
                      = T(n - 1) + …

路径总和
给定一个二叉树和一个总和，找出所有根到叶的路径，其中每个路径的总和等于给定的总和。
例如：总和 = 11。

    5 
   / \ 
  4   8
 /   / \ 
2  -2   1 

Run Code Online (Sandbox Code Playgroud)

答案是 ：

[
  [5, 4, 2], 
  [5, 8, -2]
]

Run Code Online (Sandbox Code Playgroud)

我个人认为，时间复杂度 = O(2^n)，n 是给定二叉树的节点数。

---

谢谢Vikram Bhat和David Grayson，紧时间复杂度 = O(nlogn)，n 是给定二叉树中的节点数。

• 算法检查每个节点一次，这导致 O(n)
• “矢量one_result（subList）；” 每次都会将整个路径从 subList 复制到 one_result，这会导致 O(logn)，因为高度是 O(logn)。
  

所以最后，时间复杂度 = O(n * logn) =O(nlogn)。

---

这个解决方案 的想法是DFS [C++]。

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode …

Run Code Online (Sandbox Code Playgroud)

描述:
给定两个排序的数组(非下降),在T = O(lg(m + n))中找到Kth min元素,m和n分别是两个数组的长度.

问题:
不了解下面的算法大约有三点:

• 当A [aPartitionIndex] <B [bPartitionIndex]时,为什么我们可以直接丢弃A的左边部分？
• 为什么不能同时丢弃A的左侧部分和B的右侧部分？
• 一些"资源"说这个算法可以应用于在N个排序数组中找到Kth min,怎么样？将k分成N个部分？

代码: Java.解决方案:二进制搜索.

    // k is based on 1, not 0.
    public int findKthMin(int[] A, int as, int ae, 
                           int[] B, int bs, int be, int k) {

        int aLen = ae - as + 1;
        int bLen = be - bs + 1;

        // Guarantee the first array's size is smaller than the second one,
        // which is convenient to remaining part …