当前位置:   article > 正文

C语言 | Leetcode C语言题解之第241题为运算表达式设计优先级

C语言 | Leetcode C语言题解之第241题为运算表达式设计优先级

题目:

题解:

  1. #define ADDITION -1
  2. #define SUBTRACTION -2
  3. #define MULTIPLICATION -3
  4. int* diffWaysToCompute(char * expression, int* returnSize) {
  5. int len = strlen(expression);
  6. int *ops = (int *)malloc(sizeof(int) * len);
  7. int opsSize = 0;
  8. for (int i = 0; i < len;) {
  9. if (!isdigit(expression[i])) {
  10. if (expression[i] == '+') {
  11. ops[opsSize++] = ADDITION;
  12. } else if (expression[i] == '-') {
  13. ops[opsSize++] = SUBTRACTION;
  14. } else {
  15. ops[opsSize++] = MULTIPLICATION;
  16. }
  17. i++;
  18. } else {
  19. int t = 0;
  20. while (i < len && isdigit(expression[i])) {
  21. t = t * 10 + expression[i] - '0';
  22. i++;
  23. }
  24. ops[opsSize++] = t;
  25. }
  26. }
  27. struct ListNode ***dp = NULL;
  28. dp = (struct ListNode ***)malloc(sizeof(struct ListNode **) * opsSize);
  29. for (int i = 0; i < opsSize; i++) {
  30. dp[i] = (struct ListNode **)malloc(sizeof(struct ListNode *) * opsSize);
  31. for (int j = 0; j < opsSize; j++) {
  32. dp[i][j] = NULL;
  33. }
  34. }
  35. for (int i = 0; i < opsSize; i += 2) {
  36. struct ListNode *node = (struct ListNode*)malloc(sizeof(struct ListNode));
  37. node->val = ops[i];
  38. node->next = NULL;
  39. dp[i][i] = node;
  40. }
  41. for (int i = 3; i <= opsSize; i++) {
  42. for (int j = 0; j + i <= opsSize; j += 2) {
  43. int l = j;
  44. int r = j + i - 1;
  45. for (int k = j + 1; k < r; k += 2) {
  46. struct ListNode *left = dp[l][k - 1];
  47. struct ListNode *right = dp[k + 1][r];
  48. for (struct ListNode *left = dp[l][k - 1]; left; left = left->next) {
  49. for (struct ListNode *right = dp[k + 1][r]; right; right = right->next) {
  50. struct ListNode *node = (struct ListNode *)malloc(sizeof(struct ListNode));
  51. if (ops[k] == ADDITION) {
  52. node->val = left->val + right->val;
  53. }
  54. else if (ops[k] == SUBTRACTION) {
  55. node->val = left->val - right->val;
  56. }
  57. else if (ops[k] == MULTIPLICATION) {
  58. node->val = left->val * right->val;
  59. }
  60. node->next = dp[l][r];
  61. dp[l][r] = node;
  62. }
  63. }
  64. }
  65. }
  66. }
  67. int *ans = (int *)malloc(sizeof(int) * (1 << opsSize));
  68. int pos = 0;
  69. for (struct ListNode *node = dp[0][opsSize - 1]; node; node = node->next) {
  70. ans[pos++] = node->val;
  71. }
  72. *returnSize = pos;
  73. for (int i = 0; i < opsSize; i++) {
  74. for (int j = 0; j < opsSize; j++) {
  75. struct ListNode *curr, *tmp;
  76. curr = dp[i][j];
  77. while (curr) {
  78. tmp = curr;
  79. curr = curr->next;
  80. free(tmp);
  81. }
  82. }
  83. free(dp[i]);
  84. }
  85. free(dp);
  86. free(ops);
  87. return ans;
  88. }
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/870638
推荐阅读
相关标签
  

闽ICP备14008679号