[Algorithm][综合训练][合并k个已排序的链表][dd爱旋转][小红取数]详细讲解

---

1.合并k个已排序的链表

1.题目链接

• 合并k个已排序的链表

---

2.算法原理讲解 && 代码实现

• 自己的解法：堆 -> 将全部节点丢入堆中

  class Solution 
  {typedef pair<int, ListNode*> PIL;
  public:ListNode* mergeKLists(vector<ListNode*>& lists) {priority_queue<PIL, vector<PIL>, greater<>> heap;for(const auto& list : lists){ListNode* cur = list;while(cur){heap.push({cur->val, cur});cur = cur->next;}}ListNode* newHead = new ListNode(0);ListNode* tail = newHead;while(heap.size()){ListNode* node = heap.top().second;heap.pop();tail->next = node;tail = tail->next;}tail->next = nullptr;tail = newHead->next;delete newHead;return tail;}
  };
  

• 优化解法：堆 -> 只存入每个链表的头结点，出堆时，再压入下一个节点
  • 对自己的版本进行了时间上和空间上的优化
  • 并且对堆排序时的比较方法进行了优化

  class Solution 
  {struct CMP{bool operator()(ListNode* l1, ListNode* l2){return l1->val > l2->val;}};
  public:ListNode* mergeKLists(vector<ListNode*>& lists) {priority_queue<ListNode*, vector<ListNode*>, CMP> heap;for(auto head : lists){if(head != nullptr){heap.push(head);}}ListNode* newHead = new ListNode(0);ListNode* tail = newHead;while(heap.size()){ListNode* tmp = heap.top();heap.pop();tail = tail->next = tmp;if(tmp->next != nullptr){heap.push(tmp->next);}}tail = newHead->next;delete newHead;return tail;}
  };
  

---

2.dd爱旋转

1.题目链接

• dd爱旋转

---

2.算法原理详解 && 代码详解

• 解法：模拟 + 优化
  • 180° --> 一次行对称 + 一次列对称
  • 行列的顺序无所谓
  • 如果为偶数次，则无需变换

  #include <iostream>
  #include <vector>
  using namespace std;int n = 0;
  vector<vector<int>> matrix;void SwapRol() // 行对称
  {for(int i = 0; i < n / 2; i++){for(int j = 0; j < n; j++){swap(matrix[i][j], matrix[n - 1 - i][j]);}}
  }void SwapCol() // 列对称
  {for(int j = 0; j < n / 2; j++){for(int i = 0; i < n; i++){swap(matrix[i][j], matrix[i][n - 1 - j]);}}
  }int main()
  {cin >> n;matrix.resize(n, vector<int>(n, 0));for(int i = 0; i < n; i++){for(int j = 0; j < n; j++){cin >> matrix[i][j];}}int q = 0, x = 0;cin >> q;int row = 0, col = 0;while(q--){cin >> x;if(x == 1){row++, col++;}else{row++;}}if(row %= 2){SwapRol();}if(col %= 2){SwapCol();}for(int i = 0; i < n; i++){for(int j = 0; j < n; j++){cout << matrix[i][j] << " ";}cout << endl;}return 0;
  }
  

---

3.小红取数

1.题目链接

• 小红取数

---

2.算法原理详解 && 代码实现

• 解法：01背包 + 同余(倍数问题可以转换为余数问题)

  • 同余定理：
    

  • 状态表示：dp[i][j]：从前i个数中挑选，总和%k等于j时，最大和是多少

  • 状态转移方程：
    

  • 初始化：
    

  • 返回值：dp[n][0] --> 因为k的倍数的余数为0

  #include <iostream>
  #include <vector>
  #include <climits>
  using namespace std;int main()
  {int n = 0, k = 0;cin >> n >> k;vector<long long> nums(n + 1, 0);for(int i = 1; i <= n ; i++){cin >> nums[i];}vector<vector<long long>> dp(n + 1, vector<long long>(k, LLONG_MIN));dp[0][0] = 0;for(int i = 1; i <= n; i++){for(int j = 0; j < k; j++){dp[i][j] = max(dp[i - 1][j], dp[i - 1][(j - nums[i] % k + k) % k] + nums[i]);}}cout << (dp[n][0] <= 0 ? -1 : dp[n][0]) << endl;return 0;
  }