时间戳

首页 > 解决方案 > 将 JavaScript 函数转换为 C++

javascript - 将 JavaScript 函数转换为 C++

问题描述

我正在研究一个动态编程问题，并且能够编写一个 Javascript 解决方案：

function howSum(targetSum,numbers,memo = {}){
    //if the targetSum key already in hashmap,return its value
    if(targetSum in memo) return memo[targetSum]; 

    if(targetSum == 0) return [];
    if(targetSum < 0) return null;

    for(let num of numbers){
        let aWay = howSum(targetSum-num,numbers,memo);
        if(aWay !== null){
            memo[targetSum] = [...aWay,num];
            return memo[targetSum];
        }
    }

    //no way to generate the targetSum using any elements of input array
    memo[targetSum] = null;
    return null;
}

现在我正在考虑如何将其转换为 CPP 代码。我将不得不使用unordered map对memo对象的引用。

但是我应该如何在基本条件中返回empty arrayand值？我应该在插入元素时返回 an and it 吗？这不是一种编程方式吗？另外，我应该如何将 传递给C++ 中的无序映射？目前我已经重载了创建备忘录无序映射并传递它的函数。nullarray pointerreallocCdefault parametermemoreference

任何指导将不胜感激，因为我可以解决未来的问题。

标签： javascriptc++dynamic-programming

解决方案

这是我的看法：

#include <optional>
#include <vector>
#include <unordered_map>

using Nums = std::vector<int>;
using OptNums = std::optional<Nums>;

namespace detail {

using Memo = std::unordered_map<int, OptNum>>;

OptNums const & howSum(int targetSum, Nums const & numbers, Memo & memo) {
    if (auto iter = memo.find(targetSum); iter != memo.end()) {
        return iter->second; // elements are std::pair<int, OptNums>
    }
    auto & cached = memo[targetSum]; // create an empty optional in the map

    if (targetSum == 0) {
        cached.emplace(); // create an empty Nums in the optional
    }
    else if (targetSum > 0) {
        for (int num : numbers) {
            if (auto const & aWay = howSum(targetSum-num, numbers, memo)) {
                cached = aWay;           // copy vector into optional
                cached->push_back(num); 
            }
        }
    }
    return cached;
}
} // detail

std::optional<Nums> howSum(int targetSum, Nums const & numbers) {
    detail::Memo memo;
    return detail::howSum(targetSum, numbers, memo);
}

一些评论：

  1. 使用两个函数，一个创建备忘录并将其传递给真正的实现函数是一种很好的模式。它使面向用户的界面变得干净。

  2. “detail”命名空间只是一个名字，没有什么神奇的含义，但经常用来表示实现细节。

  3. 在实现中，我返回对可选的引用。这是避免在算法从递归中展开的每次调用中复制返回向量的优化。然而，这确实需要一些小心，因为您必须小心返回对将超过本地范围的对象的引用（例如，不返回 std::nullopt，或者引用绑定到临时可选。）这也是为什么我总是在备忘录对象中创建元素——即使在否定的情况下——所以我可以安全地返回对它的引用。请注意，应用于 unordered_map 的 operator[] 将创建该元素，如果它不存在，则find不会。

  4. 由于detail函数返回的引用只有在调用者中声明的备忘录的生命周期，调用者本身必须返回它返回的可选的副本，以确保在函数清理过程中数据不被破坏称呼。请注意，它不返回引用。

  5. 此外，for 循环中的“if”也有一些变化。它声明一个本地引用，将其初始化为递归调用的结果。bool整个表达式是对 optional 的引用，如果 optional 持有一个值，它会隐式转换为 true。这是一个值得指出的有用习语，但更明确地说，这是等价的：

    if (auto const & aWay = howSum(targetSum-num, numbers, memo); aWay.has_value())

这是一个充实的示例，并带有一些测试用例来证明它是有效的。 https://godbolt.org/z/cWrdhvM1n

推荐阅读