一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1663|回复: 8
收起左侧

Snapchat 电面面经

[复制链接] |试试Instant~ |关注本帖
abrahamf 发表于 2016-4-11 12:54:22 | 显示全部楼层 |阅读模式

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

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

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

x
Question 1:
Leetcode 128 Valid Palindrome 原题

Question 2:
Given a string, every step you can add/delete/change one character at any position. Minimize the step number to make it a palindrome.

解法为DP

评分

1

查看全部评分

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.                 }. 鍥磋鎴戜滑@1point 3 acres
  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.             }. from: 1point3acres.com/bbs
  13.         }
  14.         return dp[0][size-1];
  15.     }
复制代码
回复 支持 3 反对 0

使用道具 举报

TsengJuiWang 发表于 2016-4-14 12:02:03 | 显示全部楼层
abrahamf 发表于 2016-4-11 16:04
int minStepToPal(string &str) {
    if (str.empty())
        return 0;
. visit 1point3acres.com for more.
是不是应该是dp[j]哇? 另外s = "abcd"的话,结果应该是几?我觉得是3哇,可是程序输出的是2

补充内容 (2016-4-14 12:06):
抱歉,楼主,我理解了,可以通过将c改成a然后删除最后的d实现,你的代码是对的。谢谢!
回复 支持 1 反对 0

使用道具 举报

 楼主| abrahamf 发表于 2016-4-11 16:04:41 | 显示全部楼层
lfy249 发表于 2016-4-11 13:52
目测第二题非常难,楼主解得怎么样呢

int minStepToPal(string &str) {
    if (str.empty())
        return 0;
   
    vector<vector<int>> dp(str.length(), vector<int>(str.length()));
    for (int i = str.length() - 1; i >= 0; --i) {
        for (int j = i; j < str.length(); ++j) {
            if (i == j)
                dp[j] = 0;
            else if (i + 1 == j)
                dp[j] = (str == str[j] ? 0 : 1);
            else {. Waral 鍗氬鏈夋洿澶氭枃绔,
                if (str == str[j])
                    dp[j] = dp[i + 1][j - 1];
                else
                    dp[j] = min(dp[i + 1][j - 1], min(dp[j - 1], dp[i + 1][j])) + 1;
            }
        }. 1point 3acres 璁哄潧
    }
    return dp[0][str.length() - 1];
}


dp[j]代表从下标i到下标j的sub string需要多少步才能成为palindrome。那个三项求min的为主要状态表达式,楼主思路都对的,但写完后漏了其中一项,后来时间不够,所以跪了,可惜。
回复 支持 1 反对 0

使用道具 举报

lfy249 发表于 2016-4-11 13:52:31 | 显示全部楼层
目测第二题非常难,楼主解得怎么样呢
回复 支持 反对

使用道具 举报

mingzhou1987 发表于 2016-4-11 14:08:03 | 显示全部楼层
同问第二题,dp的状态方程怎么写。。完全没有头绪。。
回复 支持 反对

使用道具 举报

stephenshaw 发表于 2016-4-11 16:58:20 | 显示全部楼层
mingzhou1987 发表于 2016-4-11 14:08
.鐣欏璁哄潧-涓浜-涓夊垎鍦同问第二题,dp的状态方程怎么写。。完全没有头绪。。

我感觉是这样:
. 鍥磋鎴戜滑@1point 3 acres
m,,n 表示string 的index范围:-google 1point3acres
if m <= n:. 1point 3acres 璁哄潧
    dp[m][n] = 0; //如果只是单个字符,则不用变

if string[m] == string[n]:
    dp[m][n] = dp[m-1][n-1]; //若头尾相等,则去头去尾看中间
else:.1point3acres缃
    dp[m][n] = 1 + dp[m-1][n-1]; //若头尾不等,则把尾变成头相同的字符,再弄中间

补充内容 (2016-4-11 16:59):
错了。。。第一个应该是 . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
if m>=n:
    dp[m][n] = 0;

补充内容 (2016-4-11 17:03):
原来还可以添加/删除啊。。。。无视我吧
回复 支持 反对

使用道具 举报

 楼主| 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不知为什么把""都吞掉了,再发一遍。。。. 1point 3acres 璁哄潧


  1. int minStepToPal(string &str) {
  2.     if (str.empty()). 鍥磋鎴戜滑@1point 3 acres
  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);. Waral 鍗氬鏈夋洿澶氭枃绔,
  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. }
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

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

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-3 23:58

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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