📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
回复: 8
跳转到指定楼层
上一主题 下一主题
收起左侧

Snapchat 电面面经

全局:

2016(1-3月) 码农类General 硕士 全职@snapchat - 内推 - 技术电面  | | Fail | 在职跳槽

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

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
Question 1:
Leetcode 128 Valid Palindrome 原题

您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
ke it a palindrome.

解法为DP

评分

参与人数 1大米 +10 收起 理由
love1point + 10

查看全部评分


上一篇:OA Interactive Broker
下一篇:关于店面
推荐
ykwwind 2016-4-11 14:15:04 | 只看该作者
全局:
  1. public static int help(char[] letters, int size) {
  2.         int[][] dp =  new int[size][size];
  3.         for(int k = 1; k < size; ++k) {
  4.             for(int i = 0; i+k < size; ++i) {
  5.                 int j = i+k;
  6.                 if(letters[i] == letters[j]) {
  7.                     dp[i][j] = k==1?0:dp[i+1][j-1];
  8.                 }
  9.                 else {
  10.                     dp[i][j] = Math.min(Math.min(dp[i+1][j], dp[i][j-1]), k==1?0:dp[i+1][j-1])+1;
  11.                 }
  12.             }
  13.         }
  14.         return dp[0][size-1];
  15.     }
复制代码
回复

使用道具 举报

全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
回复

使用道具 举报

推荐
 楼主| abrahamf 2016-4-11 16:04:41 | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
回复

使用道具 举报

🔗
lfy249 2016-4-11 13:52:31 | 只看该作者
全局:
目测第二题非常难,楼主解得怎么样呢
回复

使用道具 举报

🔗
mingzhou1987 2016-4-11 14:08:03 | 只看该作者
全局:
同问第二题,dp的状态方程怎么写。。完全没有头绪。。
回复

使用道具 举报

🔗
stephenshaw 2016-4-11 16:58:20 | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
回复

使用道具 举报

🔗
 楼主| abrahamf 2016-4-14 13:41:29 | 只看该作者
全局:
TsengJuiWang 发表于 2016-4-14 12:02
是不是应该是dp[j]哇? 另外s = "abcd"的话,结果应该是几?我觉得是3哇,可是程序输出的是2

补充内容 ( ...

是的,有增删改三种方法,很容易漏掉一个。我就是漏了个结果悲剧了。。。
回复

使用道具 举报

🔗
 楼主| abrahamf 2016-4-14 15:12:57 | 只看该作者
全局:
对不起,之前发的code不知为什么把"[i]"都吞掉了,再发一遍。。。


  1. int minStepToPal(string &str) {
  2.     if (str.empty())
  3.         return 0;
  4.    
  5.     vector<vector<int>> dp(str.length(), vector<int>(str.length()));
  6.     for (int i = str.length() - 1; i >= 0; --i) {
  7.         for (int j = i; j < str.length(); ++j) {
  8.             if (i == j)
  9.                 dp[i][j] = 0;
  10.             else if (i + 1 == j)
  11.                 dp[i][j] = (str[i] == str[j] ? 0 : 1);
  12.             else {
  13.                 if (str[i] == str[j])
  14.                     dp[i][j] = dp[i + 1][j - 1];
  15.                 else
  16.                     dp[i][j] = min(dp[i + 1][j - 1], min(dp[i][j - 1], dp[i + 1][j])) + 1;
  17.             }
  18.         }
  19.     }
  20.     return dp[0][str.length() - 1];
  21. }
复制代码
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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