ตรวจสอบว่าสามารถเยี่ยมชมเซลล์ได้มากกว่าหนึ่งครั้งในสตริงใน C++ . หรือไม่

สมมติว่าเรามีสตริงที่มีจุด (.) และตัวเลข จุดบ่งชี้ว่าเซลล์นั้นว่างเปล่า และหากมีตัวเลข x ในเซลล์ใดๆ แสดงว่าเราสามารถย้าย x ขั้นไปทางขวาหรือซ้ายภายในสตริงได้ งานของเราคือตรวจสอบว่าเราสามารถเยี่ยมชมเซลล์ได้มากกว่าหนึ่งครั้งหรือไม่ ตัวอย่างเช่น ถ้าสตริงเป็นเหมือน “. 2 . . . 2 . ” จากนั้นเราสามารถเยี่ยมชมเซลล์ที่ 4 ได้สองวิธี จากเซลล์ที่สองเป็นสองขั้นตอนไปทางขวา หรือจากสองขั้นตอนทางซ้ายจากเซลล์ 6

เราจะใช้อาร์เรย์ที่เรียกว่า visit[] เพื่อติดตามจำนวนครั้งที่เซลล์ของสตริงสามารถเยี่ยมชมได้ ตอนนี้ให้สำรวจสตริง และตรวจสอบว่าอักขระปัจจุบันคือจุดหรือตัวเลข สำหรับ dot ไม่ทำอะไรเลย สำหรับ x เพิ่มจำนวนและเพิ่มจำนวนครั้งในอาร์เรย์ที่เข้าชมภายในช่วง [i – x, i + x] ทีละ 1 โดยการสำรวจอาร์เรย์ที่เข้าชมแล้วหากเราได้ห้องบางส่วนมา มากกว่าหนึ่งครั้งหรือไม่

ตัวอย่าง

#include <iostream>
#include <queue>
using namespace std;
class Node {
   public:
   int key;
   Node *left, *right;
};
Node* getNode(int key) {
   Node* newNode = new Node;
   newNode->key = key;
   newNode->left = newNode->right = NULL;
   return newNode;
}
bool isLevelWiseSorted(Node* root) {
   int prevMax = INT_MIN;
   int min_val, max_val;
   int levelSize;
   queue<Node*> q;
   q.push(root);
   while (!q.empty()) {
      levelSize = q.size();
      min_val = INT_MAX;
      max_val = INT_MIN;
      while (levelSize > 0) {
         root = q.front();
         q.pop();
         levelSize--;
         min_val = min(min_val, root->key);
         max_val = max(max_val, root->key);
         if (root->left)
            q.push(root->left);
         if (root->right)
            q.push(root->right);
      }
      if (min_val <= prevMax)
         return false;
         prevMax = max_val;
   }
   return true;
}
int main() {
   Node* root = getNode(1);
   root->left = getNode(2);
   root->right = getNode(3);
   root->left->left = getNode(4);
   root->left->right = getNode(5);
   root->right->left = getNode(6);
   root->right->right = getNode(7);
   if (isLevelWiseSorted(root))
      cout << "Tree is levelwise Sorted";
   else
      cout << "Tree is Not levelwise sorted";
}

ผลลัพธ์

Tree is level wise Sorted