רשומת נוכחות סטודנטים I פתרון Leetcode


רמת קושי קַל
נשאל לעתים קרובות Google
מחרוזת

הצהרת בעיה

בבעיה "רשומת נוכחות סטודנטים אני" ניתן לנו מחרוזת כאשר כל אות מייצגת את פרטי הנוכחות של סטודנט. פירוש האותיות במחרוזת הוא כדלקמן:

  1. פירושו 'A' נעדר.
  2. פירושו 'P' נוכח.
  3. 'L' פירושו מאוחר

התלמיד יקבל תגמול על בסיס נוכחותו אם הוא לא נעדר יותר מיום אחד או לא מאחר ברציפות במשך יותר מיומיים. המשימה שלנו היא לקבוע אם התלמיד יקבל תגמול או לא.

דוגמה

str="PPALLP"
true

הסבר:

רשומת נוכחות סטודנטים I פתרון Leetcode

מכיוון שהתלמיד אינו נעדר יותר מיום אחד ולא מאחר ברציפות במשך יותר מיומיים, כך עליו לקבל תגמול.

גישה לרשומת נוכחות סטודנטים I פתרון Leetcode

יישום

זוהי בעיית יישום בסיסית. עלינו לברר אם התלמיד יקבל תגמול או לא. אז כדי לתגמל את התלמיד עלינו לבדוק אם הוא לא נעדר יותר מיום אחד ולא מאחר ברציפות יותר מיומיים. אנו נבצע את הצעדים הבאים לביצוע בדיקה זו:

  1. אתחל את מספר ספירת 'A' וספירת 'L' באפס
  2. חצו את המיתר השלם.
    1. אם הדמות הנוכחית היא 'A', הגדל את ספירת 'A' אחת.
    2. אם הדמות הנוכחית היא 'L', הגדל את ספירת 'L' אחת.
    3. אחרת, ספירת 'L' הופכת לאפס.
    4. כעת בדוק אם ספירת 'A' גדולה או שווה ל -2 או שספירת 'L' גדולה מ- 2. אם התנאי נכון, השב שקר.
  3. בסופו של דבר, אם כל התנאים מתקיימים אז חזור נכון.

קוד C ++ לתיעוד נוכחות סטודנטים I

#include <bits/stdc++.h> 
using namespace std; 
bool checkRecord(string s) {
    int a=0, l=0;
    for(int i=0;i<s.size();i++) {
        if(s[i]=='A') a++;
        if(s[i]=='L') l++;
        else l=0;
        if(a>=2||l>2) return false;
    }
    return true;
}

int main() 
{ 
    string attendence ="PPALLP"; 
    bool ans=checkRecord(attendence); 
    cout<<boolalpha;
    cout<<ans<<endl;
    return 0;
}
true

קוד Java עבור רשומת נוכחות סטודנטים I

import java.util.Arrays;
import java.util.Set ;
import java.util.HashSet;
import java.util.*; 
public class Tutorialcup {
    public static boolean checkRecord(String s) {
    int a=0, l=0;
    for(int i=0;i<s.length();i++) {
        if(s.charAt(i)=='A') a++;
        if(s.charAt(i)=='L') l++;
        else l=0;
        if(a>=2||l>2) return false;
    }
    return true; 
    }
  public static void main(String[] args) {
        String attendence ="PPALLP"; 
        boolean ans=checkRecord(attendence); 
        System.out.println(ans);
  }
}
true

ניתוח המורכבות של רישום הנוכחות של סטודנטים I פתרון Leetcode

מורכבות זמן

מורכבות הזמן של הקוד הנ"ל היא O (n) כי אנחנו חוצים את המיתר רק פעם אחת. כאן n הוא אורך המחרוזת הנתונה.

מורכבות חלל

מורכבות החלל של הקוד הנ"ל היא O (1) מכיוון שאנחנו משתמשים רק במשתנה לאחסון התשובה.

הפניות