亚马逊的在线笔试也是OJ题目,跟谷歌差不多。当然比较诧异的是,其实难度也跟谷歌差不多!
第一题:
巨麻烦的一道题目,大意是比较扑克牌序列,每个序列四张牌
规则一:
四张牌相同。自然数字大的胜出,比如3,3,3,3 < 6,6,6,6
规则二:
四张牌连续。当然序列最大的那个胜出。但是有个小trick,A在这里默认表最大牌,但是如果后接2,3,4,则A表最小牌,为了获得连续序列
比如A,2,3,4 < J,Q,K,A
规则三:
有三张相同。以每个序列相同牌较大的胜出。
比如3,3,3,2>2,2,2,A
规则四:
两个对子。当然以对子较大的胜出,最大的对子相同,则以次大的对子较大者胜出。
比如4,4,3,3 > 4,2,4,2
规则五:
一个对子。对子较大者胜出,如果对子相同,则比较剩下较大牌,如果还相同,比较次大牌
3,3,7,4 < 3,3,7,5
规则六:
如果以上皆不满足,则按照大牌>小牌比较(即从最大牌开始比较,分出高下为止)
如果两个序列不属于同一规则,则规则小者胜出。
如果序列一大于序列二,输出1,反之输出-1;如果序列相同,输出0。
如果发现作弊,即两副牌中某张牌数量超过5张,则输出-2。
OK,以上是题目描述。这个题目,个人感觉主要是读懂题意,实现起来确实也非常麻烦,但是没啥难点,但是也会搞很久。
主要是几点:
1、解析输入字符串(如果你用C、C++,会比较蛋疼)
2、适配规则逻辑(更像状态机)
3,比较逻辑
好像也没啥是吧,但是本屌丝做了N久才把Case全过。而且代码巨长,200+行,准备吃饭去了,代码稍后奉上。
昨晚有事。现在奉上我水的不忍直视的代码。
#include <iostream> #include <sstream> #include <string> #include <cstring> #include <algorithm> using namespace std; int change(char a) { switch (a) { case 'A': return 14; break; case 'J': return 11; break; case 'Q': return 12; break; case 'K': return 13; break; default: return 0; break; } } int istype(int *a) { int x = a[0]; int ans = 1; int hash[15]; memset(hash, 0, sizeof(hash)); for (int i = 0; i < 4; i++) { hash[a[i]]++; } int eq = 1; int deq = 0; for (int i = 1; i < 15; i++) { if (hash[i] == 4) return 1; if (hash[i] == 3) return 3; if (i>1) { if (hash[i] == hash[i - 1]&&hash[i]==1) { eq++; } } if (eq == 4) return 2; if (hash[i] == 2) deq++; if (deq == 2) return 4; } if (deq == 1) return 5; if (eq == 3 && hash[2] == hash[3] && hash[3] == hash[4] &&hash[2]==1 ){ if (a[3] == 14){ a[3] = 1; sort(a, a + 4); return 2; } } return 6; } int cmp(int *a, int *b, int kind) { if (kind == 3) { int h1[15], h2[15]; memset(h1, 0, sizeof(h1)); memset(h2, 0, sizeof(h2)); int c1, c2; for (int i = 0; i<4; i++) { h1[a[i]]++; if (h1[a[i]] == 3) c1 = a[i]; } for (int i = 0; i<4; i++) { h2[b[i]]++; if (h2[a[i]] == 3) c2 = a[i]; } if (c1>c2) return 1; if (c1<c2) return -1; } if (kind == 4) { int h1[15], h2[15]; memset(h1, 0, sizeof(h1)); memset(h2, 0, sizeof(h2)); int c1, c2; for (int i = 0; i<4; i++) { h1[a[i]]++; if (h1[a[i]] == 2) c1 = a[i]; } for (int i = 0; i<4; i++) { h2[b[i]]++; if (h2[a[i]] == 2) c2 = a[i]; } if (c1>c2) return 1; if (c1<c2) return -1; } for (int i = 3; i >=0; i--) { if (a[i] > b[i]) return 1; else if (a[i] < b[i]) return -1; } return 0; } int main() { /* Enter your code here. Read input from STDIN. Print output to STDOUT */ string a, b; int aa[4], bb[4]; int hash[15]; while (cin >> a >> b) { int ans = 0; int idx = 0; for (int i = 0; i < a.size(); i++) { int sum = 0; if (a[i] >= '2'&&a[i] <= '9') { sum = a[i] - '0'; aa[idx++] = sum; } else if (a[i] == '1') { sum = 10; aa[idx++] = sum; i++; } else if (a[i] == ',') { continue; } else{ sum = change(a[i]); aa[idx++] = sum; } } idx = 0; for (int i = 0; i < b.size(); i++) { int sum = 0; if (b[i] >= '2'&&b[i] <= '9') { sum = b[i] - '0'; bb[idx++] = sum; } else if (b[i] == '1') { sum = 10; bb[idx++] = sum; i++; } else if (b[i] == ',') { continue; } else{ sum = change(b[i]); bb[idx++] = sum; } } memset(hash, 0, sizeof(hash)); for (int i = 0; i < 4; i++) { hash[aa[i]]++; hash[bb[i]]++; if (hash[aa[i]] > 4 || hash[bb[i]] > 4) { ans = -2; break; } } if (ans == -2) { cout << ans << endl; continue; } std::sort(aa, aa + 4); std::sort(bb, bb + 4); int ka = istype(aa); int kb = istype(bb); //for (int i = 0; i < 4; i++) // cout << aa[i] << " "; //cout << endl; //for (int i = 0; i < 4; i++) // cout << bb[i] << " "; //cout << endl; //cout << ka << " " << kb << endl; if (ka == kb) { ans = cmp(aa, bb,ka); } else{ if (ka < kb) ans = 1; else ans = -1; } cout << ans << endl; } return 0; }
(二三题待续)--
题目二:
题意很简单,找出所给数字的下一个回文数。所给数字不一定是回文数,要找的是恰好大于这个数字的最小的回文数。
代码如下:
/* * Complete the function below. */ #include<iostream> #include<fstream> #include<string> using namespace std; string getNextSymmetricNumber(string n) { int len = n.length(); int i = 0; int dm = len / 2; dm += len % 2; int * num = new int[len + 1]; for (int i = 1; i <= len; i++){ num[i] = n[i - 1] - '0'; } int dntkn = 0; int dntkn1 = 1; for (int i = dm; i >= 1; i--){ int l = i; int r = len - i + 1; if (num[l]<num[r]) { dntkn1 = 0; num[dm]++; num[len - dm + 1] = num[dm]; for (int i = dm; i >= 1; i--){ if (num[i] == 0){ if (i >= 2){ num[i - 1]++; num[len - i + 2] = num[i - 1]; } else{ dntkn = 1; break; } } else break; } if (dntkn == 1) break; i = dm + 1; for (int k = dm + 1; k <= len; k++){ num[k] = 0; } } else if (num[l]>num[r]){ dntkn1 = 0; num[r] = num[l]; for (int i = l; i >= 1; i--){ num[len - i + 1] = num[i]; } break; } } if (dntkn1 == 1){ num[dm] = (num[dm] + 1) % 10; num[len - dm + 1] = num[dm]; for (int i = dm; i >= 1; i--){ if (num[i] == 0){ if (i >= 2){ num[i - 1] = (num[i - 1] + 1) % 10; num[len - i + 2] = num[i - 1]; } else{ dntkn = 1; break; } } else break; } } string out = ""; if (dntkn == 1) out += "1"; for (int i = 1; i <= len; i++){ if (dntkn == 1 && i == len) break; out += ('0' + num[i]); } if (dntkn == 1) out += "1"; return out; } int main() { ofstream fout(getenv("OUTPUT_PATH")); string res; string _n; getline(cin, _n); res = getNextSymmetricNumber(_n); fout << res << endl; fout.close(); return 0; }
题目三:
题意也很简单,给定两个节点,在一个无尽的完全三叉树中,找到其最小公共父节点号。
这个题目没有来得及做。找公共父节点倒不是什么新鲜事,但是这里有个小trick,给定的只是节点编号,返回的也是节点编号。而节点编号的规律是按层次,蛇形编号。
根节点是0,第一层从左到右是1~3,第二层从左到右就变成了12~4(因为整体是蛇形排列),第三层从左到右13~40 。。。
欢迎探讨