要回国了,写个简单的总结吧。

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
把贵司招聘信息放这里
查看: 521|回复: 1
收起左侧

[Leetcode] Palindrome Partitioning II discuss中的一段代码求解释

[复制链接] |试试Instant~ |关注本帖
我的人缘0
caffery24 发表于 2015-8-20 21:17:16 | 显示全部楼层 |阅读模式
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?Sign Up 注册获取更多干货

x
首先吐槽下。。。刷到110+,hard的题大部分都没思路了。。。有时还会发生做过的题再打开还是得想好久的情况。。。有没有人能帮忙给点建议。

这个题目,自己是用一个二维数组纪录是否为pal同时,从后往前不断更新每一个字母到末尾的字符串的需要的最小cut数。。。然后看了discuss,有一个方法只用o(n) space, 看了好久没看懂原理,能不能请大家帮忙分析下,谢谢了。
题目要求如下:

Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

For example, given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.


代码如下:不知道它是怎么来更新cut[]的。。。
  1. class Solution {
  2. public:
  3.     int minCut(string s) {
  4.         int n = s.size();
  5.         vector<int> cut(n+1, 0);  // number of cuts for the first k characters
  6.         for (int i = 0; i <= n; i++) cut[i] = i-1;
  7.         for (int i = 0; i < n; i++) {
  8.             for (int j = 0; i-j >= 0 && i+j < n && s[i-j]==s[i+j] ; j++) // odd length palindrome
  9.                 cut[i+j+1] = min(cut[i+j+1],1+cut[i-j]);

  10.             for (int j = 1; i-j+1 >= 0 && i+j < n && s[i-j+1] == s[i+j]; j++) // even length palindrome
  11.                 cut[i+j+1] = min(cut[i+j+1],1+cut[i-j+1]);
  12.         }
  13.         return cut[n];
  14.     }
  15. };
复制代码
不知道正不正常啊,第一次刷题,感觉很难啊,自己又贪玩。。。经常一天只能做三道题。。。主要是很多hard的题没思路。。。不知道是不是因为自己转专业,没系统学习的原因,还有些虽然做出来,总感觉是碰巧,没有说能达到,碰到题目,能分类题目,选择不同方法(如dfs,bfs,dp..)的阶段,特别是recursive的题目,对递归的理解和运用还是不清晰,请大家给点建议

上一篇:leetcode 谁有这些按照公司分类的题目列表?
下一篇:求问一个关于time complexity的概念问题
我的人缘0
vivyao 发表于 2015-8-22 03:36:34 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
不太理解中间那两个循环。。
回复 支持 反对

使用道具 举报

全球28万学生4.7分推荐
游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-5-27 20:26

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表