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

Cryptic Studio 家OA,题目不多质量不错,可看可学

🔗
 楼主| chenyy0527 2015-9-9 11:15:59 | 只看该作者
全局:
Linzertorte 发表于 2015-9-9 07:17
这个中缀求值用divide-conquer比较简单。 扫描一遍,找到第一个+,然后左右分成两个子问题。找不到+,就找 ...

对哦,好办法,我还是用的stack,弱弱的=。=
回复

使用道具 举报

🔗
 楼主| chenyy0527 2015-9-10 11:37:19 | 只看该作者
全局:
Linzertorte 发表于 2015-9-9 11:35
楼主会不会python...

并不会,但是看代码无所谓,都能看得懂
回复

使用道具 举报

🔗
Linzertorte 2015-9-12 13:26:46 | 只看该作者
全局:
http://www.1point3acres.com/bbs/thread-141458-1-1.html  过来凑凑热闹,把楼主批判一番
回复

使用道具 举报

🔗
 楼主| chenyy0527 2015-9-13 03:26:33 | 只看该作者
全局:
Linzertorte 发表于 2015-9-12 13:26
http://www.1point3acres.com/bbs/thread-141458-1-1.html  过来凑凑热闹,把楼主批判一番

哈哈哈好的 :D
回复

使用道具 举报

🔗
kelvinzhong 2015-9-16 07:54:42 | 只看该作者
全局:
发个我写的代码,个人感觉还是比较清晰易懂的,没有任何trick的DFS。

  1. bool cal(string &e, int &target, int pos, int pre_val, int cur_val, string tmp_e, string &ret) {
  2.         // Base Case 1
  3.         if (pos == e.length()) {
  4.                 if (pre_val + cur_val == target) {
  5.                         ret = tmp_e;
  6.                         return true;
  7.                 }
  8.                 return false;
  9.         }

  10.         int tmp_val = 0;
  11.         string tmp = "";
  12.         int pre_val2, cur_val2;
  13.         string tmp_e2;
  14.         for (int i = pos; i < e.length(); i ++) {
  15.                 tmp_val = tmp_val * 10 + e[i] - '0';
  16.                 tmp += e[i];
  17.                
  18.                 // Case 1: '+'
  19.                 pre_val2 = pre_val + cur_val;
  20.                 if (tmp_e.length() == 0) {
  21.                         tmp_e2 = tmp;
  22.                 } else {
  23.                         tmp_e2 = tmp_e + '+' + tmp;
  24.                 }
  25.                 if (cal(e, target, i + 1, pre_val2, tmp_val, tmp_e2, ret)) {
  26.                         return true;
  27.                 }

  28.                 if (tmp_e.length() == 0)
  29.                         continue;

  30.                 // Case 2: '*'
  31.                 cur_val2 = cur_val * tmp_val;
  32.                 tmp_e2 = tmp_e + '*' + tmp;
  33.                 if (cal(e, target, i + 1, pre_val, cur_val2, tmp_e2, ret)) {
  34.                         return true;
  35.                 }
  36.         }
  37.         return false;
  38. }

  39. string cal(string e, int target) {
  40.         string ret;
  41.         cal(e, target, 0, 0, 0, "", ret);
  42.         return ret.length() == 0 ? "No Solution" : ret;
  43. }

  44. void test() {
  45.         string e = "123";
  46.         cout << cal(e, 6) << endl;
  47.         cout << cal(e, 9) << endl;
  48.         e = "1231231234";
  49.         cout << cal(e, 11353) << endl;
  50.         e = "3456237490";
  51.         cout << cal(e, 1185) << endl;
  52.         cout << cal(e, 9191) << endl;
  53. }
复制代码
回复

使用道具 举报

🔗
hbsophia 2015-9-16 13:05:35 | 只看该作者
全局:
kelvinzhong 发表于 2015-9-16 07:54
发个我写的代码,个人感觉还是比较清晰易懂的,没有任何trick的DFS。

大牛,请问tmp_e2是神马意思?多谢
回复

使用道具 举报

🔗
kelvinzhong 2015-9-16 13:09:41 | 只看该作者
全局:
hbsophia 发表于 2015-9-16 13:05
大牛,请问tmp_e2是神马意思?多谢

tmp_e2就是要传入下一个recursion的expression. sorry for the confusion of variable name.
回复

使用道具 举报

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

使用道具 举报

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

使用道具 举报

🔗
pyemma 2015-9-16 13:54:15 | 只看该作者
全局:
  1. public class Solution {
  2.     public List<String> addOperators(String num, int target) {
  3.         List<String> result = new ArrayList<String>();
  4.                 List<Long> list = new ArrayList<Long>();
  5.                 dfs(num, target, "", 0, list, result);
  6.                 return result;
  7.     }
  8.    
  9.     private void dfs(String num, int target, String current, int index,
  10.                 List<Long> list, List<String> result) {
  11.                 if (index == num.length()) {
  12.                         long sum = 0;
  13.                         for (int i = 0; i < list.size(); ++i)
  14.                                 sum += list.get(i);
  15.                         if (sum == target)
  16.                                 result.add(current);
  17.                 } else {
  18.                         int end = index;
  19.                         long number = 0;
  20.                         while (end < num.length()) {
  21.                                 // overflow
  22.                                 int digit = num.charAt(end) - '0';
  23.                                 if ((Integer.MAX_VALUE - digit) / 10 < number)
  24.                                         break;
  25.                                 // continues zero
  26.                                 if (end > index && number == 0)
  27.                                         break;
  28.                                 number = number * 10 + digit;
  29.                                 if (current.length() == 0) {
  30.                                         list.add(number);
  31.                                         dfs(num, target, num.substring(index, end+1), end+1, list, result);
  32.                                         list.remove(list.size()-1);
  33.                                 } else {
  34.                                         list.add(number);
  35.                                         dfs(num, target, current+'+'+num.substring(index, end+1), end+1, list, result);
  36.                                         list.remove(list.size()-1);
  37.                                         list.add(-number);
  38.                                         dfs(num, target, current+'-'+num.substring(index, end+1), end+1, list, result);
  39.                                         list.remove(list.size()-1);
  40.                                         long temp = list.get(list.size()-1);
  41.                                         list.set(list.size()-1, temp*number);
  42.                                         dfs(num, target, current+'*'+num.substring(index, end+1), end+1, list, result);
  43.                                         list.set(list.size()-1, temp);
  44.                                 }
  45.                                 ++end;
  46.                         }
  47.                 }
  48.         }
  49. }
复制代码
紧紧跟随种神代码,贴个我写的DFS
用了个list来保存当前的所有算式中的数字,但是全部转换成加法了
注意连续0和leading 0的情况要及时排除
回复

使用道具 举报

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

本版积分规则

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