首页 > 代码库 > leetcode 几道题目
leetcode 几道题目
是周六晚上的几道题，晚上11点半，睡的早，起不来！
494. Target Sum
分析：看完这题，看到数据范围，长度20，枚举就是1<<20 = 1e6, 然后单次20，总共就是2e8，感觉应该是暴力枚举，然后我就按照二进制的方式写了代码，tle了，我感觉应该可以过啊，然后就用dfs写了一下，刚好能过，卡的时间，感觉应该有优化的地方。其实正确的思路是dp，我刚开始感觉也是dp，因为要计算所有的可能，感觉dp也是暴力，算所有可能出现的情况，感觉跟暴力差不多！今天看了下别人的分析，是自己分析错了，http://bookshadow.com/weblog/2017/01/22/leetcode-target-sum/ 我每次都看这个人写的题解，非常棒，更新速度快，思路清晰！然后这道题，因为题目说了，所有数之和不超过1000，那么所有可能出现数的范围就确定了-1000到1000，总共2000， 每次每个数只需要考虑加减这两种情况，所以复杂度是2000 * 20 = 4e4，这个复杂度很小，速度很快！还有注意：这道题因为有些和为负数，所以加上一个偏移来解决。
mycode：
1 class Solution { 2 private: 3 int dp[2][2020]; 4 public: 5 int findTargetSumWays(vector<int>& nums, int s) { 6 int pos = 1000; 7 memset(dp, 0, sizeof dp); 8 dp[0][0 + pos] = 1; 9 int cur = 1;10 for (int x : nums) {11 for (int i = 0; i <= 2000; i++)12 dp[cur][i] = 0;13 for (int i = 0; i <= 2000; i++) {14 if(i + x <= 2000)15 dp[cur][i + x] += dp[cur ^ 1][i];16 if(i - x >= 0)17 dp[cur][i - x] += dp[cur ^ 1][i];18 }19 cur ^= 1;20 }21 s += pos;22 if(s < 0 || s > 2000) return 0;23 return dp[cur ^ 1][s];24 }25 };
leetcode 几道题目
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。