Computer >> Máy Tính >  >> Lập trình >> C ++

Crossonal Traverse II trong C ++

Giả sử chúng ta có một danh sách các danh sách được gọi là nums, chúng ta phải hiển thị tất cả các phần tử của nums theo thứ tự đường chéo.

Vì vậy, nếu đầu vào giống như

Crossonal Traverse II trong C ++

thì đầu ra sẽ là [1,6,2,8,7,3,9,4,12,10,5,13,11,14,15,16]

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

  • Xác định ret mảng

  • Xác định một mảng 2D v

  • để khởi tạo i:=0, khi tôi

    • để khởi tạo j:=0, khi j

      • chèn {nums [i, j], i, j} vào cuối v

  • sắp xếp mảng v

  • cho mỗi nó trong v, do,

    • chèn nó [0] vào cuối ret

  • trả lại ret

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<int> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class Solution {
public:
   static bool cmp(vector <int>& a, vector <int>& b ){
      int sum1 = a[1] + a[2];
      int sum2 = b[1] + b[2];
      return sum1 == sum2 ? a[1] > b[1] : sum1 < sum2;
   }
   vector<int> findDiagonalOrder(vector& nums) {
      vector<int> ret;
      vector<vector<int> > v;
      for (int i = 0; i < nums.size(); i++) {
         for (int j = 0; j < nums[i].size(); j++) {
            v.push_back({ nums[i][j], i, j });
         }
      }
      sort(v.begin(), v.end(), cmp);
      for (auto& it : v)
      ret.push_back(it[0]);
      return ret;
   }
};
main(){
   Solution ob;
   vector<vector<int>> v = {{1,2,3,4,5},{6,7},{8},{9,10,11},{12,13,14,15,16}};
   print_vector(ob.findDiagonalOrder(v));
}

Đầu vào

{{1,2,3,4,5},{6,7},{8},{9,10,11},{12,13,14,15,16}}

Đầu ra

[1, 6, 2, 8, 7, 3, 9, 4, 12, 10, 5, 13, 11, 14, 15, 16, ]