请解释一下这句话什么意思vector<vector<int>> memo(n,vector<int>(m,INT_MIN));
时间: 2023-10-22 12:32:32 浏览: 36
这句话是使用C++语言中的vector和二维数组的方式来创建一个名为memo的变量。其中,memo包含n个元素,每个元素是一个大小为m的vector<int>,每个vector<int>中的元素初始化为INT_MIN。这样定义的memo变量可以用于存储动态规划中的中间结果,以便后续的计算能够更高效地进行。
相关问题
leedcode1376题class Solution {public: int numOfMinutes(int n, int headID, vector<int>& manager, vector<int>& informTime) { int res = 0; // 遍历下属,找到下属中需要花费时间最长的那一个 for (int i = 0; i < n; i++) { if (manager[i] == headID) { res = max(res, numOfMinutes(n, i, manager, informTime)); } } // 加上当前领导向下属传递信息所需要的时间 return res + informTime[headID]; }};代码超出时间限制,如何优化
这个问题的核心在于遍历下属的过程,因为遍历下属是一个递归过程,所以在遍历过程中会有很多重复计算,导致算法时间复杂度较高。可以使用记忆化搜索来优化算法,缓存已经计算过的结果,避免重复计算。
具体来说,可以使用一个数组来记录每个员工的最长传递时间,如果已经计算过该员工的最长传递时间,直接返回该值,否则就递归计算该员工的最长传递时间。
优化后的代码如下:
```
class Solution {
public:
int numOfMinutes(int n, int headID, vector<int>& manager, vector<int>& informTime) {
vector<int> memo(n, -1); // 缓存每个员工的最长传递时间
return dfs(headID, manager, informTime, memo);
}
int dfs(int cur, vector<int>& manager, vector<int>& informTime, vector<int>& memo) {
if (memo[cur] != -1) { // 如果已经计算过该员工的最长传递时间,直接返回该值
return memo[cur];
}
int res = 0;
for (int i = 0; i < manager.size(); i++) {
if (manager[i] == cur) { // 遍历当前员工的下属
res = max(res, dfs(i, manager, informTime, memo)); // 递归计算下属的最长传递时间
}
}
memo[cur] = res + informTime[cur]; // 更新缓存
return memo[cur];
}
};
```
这样,时间复杂度就从指数级别降到了线性级别,可以通过本题。
<html> <head> <title> New Document </title> </head> <body> <form method="POST" action="../0001/success.asp" name=form > <textarea cols="45" name="memo" rows="8" wrap="on" class="editbox2" onKeyDown="textCounter(this.form.memo,this.form.remLen,160);" onKeyUp="textCounter(this.form.memo,this.form.remLen,160);"></textarea> <br> 共可输入160字,还剩 <input readonly type=text name=remLen size=3 maxlength=3 value="160" class=editbox1> 字。 <br> </form> </body> </html> <script language="JavaScript"> function textCounter(field, countfield, maxlimit) { if (field.value.length > maxlimit) field.value = field.value.substring(0,maxlimit); else countfield.value = maxlimit - field.value.length; } </script>解析思路
这是一个基本的 HTML 页面,里面包含一个表单(form)元素和一个文本框(textarea)元素。当用户在文本框中输入文字时,通过 JavaScript 脚本实现了一个字数限制功能,文本框旁边会显示还可以输入多少个字。当用户输入的文字超过了限制时,脚本会自动截取多余的部分。当用户提交表单时,数据将被发送到 "../0001/success.asp" 页面进行处理。