首页 > 代码库 > 根据上排给出十个数,在其下排填出对应的十个数
根据上排给出十个数,在其下排填出对应的十个数
根据上排给出十个数,在其下排填出对应的十个数
要求下排每个数都是先前上排那十个数在下排出现的次数。
上排的十个数如下:
【0,1,2,3,4,5,6,7,8,9】
举一个例子,
数值: 0,1,2,3,4,5,6,7,8,9
分配: 6,2,1,0,0,0,1,0,0,0
0在下排出现了6次,1在下排出现了2次,
2在下排出现了1次,3在下排出现了0次....
以此类推..
1 #include <iostream> 2 #include <map> 3 4 using namespace std; 5 6 class Solution { 7 public: 8 void solve(int pre[], int next[]) { 9 for (int i = 0; i < 10; ++i) {10 preCount[pre[i]]++;11 }12 13 recurse(pre, next, 10, 0);14 }15 16 void recurse(int pre[], int next[], int n, int sum) {17 if (n <= 0) {18 if (check(pre, next, 10)) {19 print(next, 10);20 }21 return;22 }23 24 if (sum > 10) return;25 26 if (pre[n - 1] > 10 || pre[n - 1] < 0) {27 next[n - 1] = 0;28 recurse(pre, next, n - 1, sum);29 } else {30 for (int i = 0; i <= 10 / (pre[n - 1] + 1) + 1; ++i) {31 if (i == pre[n - 1] && preCount[pre[n - 1]] == pre[n - 1]) continue;32 next[n - 1] = i;33 recurse(pre, next, n - 1, sum + i * pre[n - 1]);34 }35 if (preCount[pre[n - 1]] == pre[n - 1]) {36 next[n - 1] = pre[n - 1];37 recurse(pre, next, n - 1, sum);38 }39 }40 }41 42 private:43 map<int, int> preCount;44 45 bool check(int pre[], int next[], int n) {46 map<int, int> count;47 for (int i = 0; i < n; ++i) {48 count[next[i]]++;49 }50 51 for (int i = 0; i < n; ++i) {52 if (count[pre[i]] != next[i]) return false;53 }54 return true;55 }56 57 void print(int arr[], int n) {58 for (int i = 0; i < n; ++i) {59 cout << arr[i] << " ";60 } 61 cout << endl;62 }63 };64 65 int main()66 {67 int pre[] = {10, 10, 10, 10, 10, 10, 10, 10, 10, 10};// {1, 2, 2, 3, 3, 3, 4, 4, 4, 4}; //{0, 1, 2, 2, 3, 3, 3, 4, 5, 6}; //{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};68 int next[10];69 Solution s;70 s.solve(pre, next);71 return 0;72 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。