רוטר - אינדוקס של מחסנית (מילוי חורים)

יומן פעילות	לוח שנה	מבזקי חדשות	תקנון	RSS	כותרות	כותרות לפי תגובה	ניקוי קוקיז	IP	להורדת אפליקציה
eBay	AliExpress	GearBest	Amazon	Booking	Kiwi	SkyScanner	Trip Advisor

"אינדוקס של מחסנית (מילוי חורים)"

גירסת הדפסה

קבוצות דיון פיתוח, תיכנות ובניית אתרים נושא #21787	מנהל סגן המנהל מפקח Winner צל"ש מומחה

אשכול מספר 21787

Ice Cold

חבר מתאריך 3.8.02
28041 הודעות, 19 פידבק

00:25 29.08.16

אינדוקס של מחסנית (מילוי חורים)

יש לי בעיה מסויימת ואני מנסה לפשט אותה כמה שיותר...
יש לי מערך מסויים (אני ארשום אותו לגובה):
3
0
4
0
0
עכשיו תחשוב על טטריס, שה-0 הם "כלום". משמע, ה-3 וה-4 אמורים ליפול אחד על השני לתחתית המסך:
0
0
0
3
4
או מקרה קצת שונה:
3
0
4
0
1
צריך להיות:
0
0
3
4
1
למישהו יש רעיון איך אפשר לממש את זה בצורה הכי פשוטה?

תודה

שתף

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

האשכול	מחבר	תאריך כתיבה	מספר
אופציה אחת	VeNom	29.08.16 09:10	1
יהיה לך הוצאות מהמבנה נתונים הזה?	כמה עוד	29.08.16 09:51	2
בעיקרון -	-UC-	29.08.16 10:09	3
זה בדיוק מה שעשיתי היום בבוקר :) תודה!!	Ice Cold	29.08.16 20:06	5
למה מחסניות?	cfirzzz	07.09.16 00:31	7
לא הבנתי את כוונתך	-UC-	07.09.16 12:57	8
מכתב	cfirzzz	07.09.16 16:15	9
מכתב	cfirzzz	07.09.16 16:16	10
במערך זה נכון, אבל במחסנית אין לך את האופציה לגשת לאיבר באמצע/התחלה	-UC-	07.09.16 16:34	11
מכתב	cfirzzz	07.09.16 16:40	12
רק תיקון קטן, זה לא היה תרגיל חחח זה בשביל משחק שאני מפתח :)	Ice Cold	11.09.16 10:37	15
PriorityQueue ש-0 מחזיר מספר חיובי ולא 0 מחזיר מספר שלילי (בהנחה ששורה 0 זה הראש	ldan192	29.08.16 10:13	4
בסוף אני ו-UC חשבנו על אותו דבר :) תודה לכולם :)	Ice Cold	29.08.16 20:07	6
עוד פתרון עם o(1) זכרון	cfirzzz	09.09.16 09:51	13
זה ממש לא O)1(	-UC-	11.09.16 09:35	14
מכתב	cfirzzz	11.09.16 16:45	16
מכתב	cfirzzz	11.09.16 16:45	17

VeNom

חבר מתאריך 7.6.02
7922 הודעות, 1 פידבק

09:10 29.08.16

1. אופציה אחת
בתגובה להודעה מספר 0

זה להשתמש ב 2 תורים. תור של אפסים ותור רגיל. ברגע שהתור הרגיל מתמלא, תתחיל לרוקן מתור האפסים.
אופציה אחרת זה למצוא מימוש של PRIORITY QUEUE שיתאים לך:

https://en.wikipedia.org/wiki/Priority_queue

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

כמה עוד

חבר מתאריך 18.11.09
234 הודעות, 11 פידבק

09:51 29.08.16

2. יהיה לך הוצאות מהמבנה נתונים הזה?
בתגובה להודעה מספר 0

כלומר יש מצב שמ-
0
0
3
4
1
פתאום מוציאים את ה 1? וזה נהיה ככה?
0
0
3
4
0
או שמוציאים את 4?
0
0
3
0
1

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

-UC-

חבר מתאריך 1.8.02
21922 הודעות, 1 פידבק

10:09 29.08.16

3. בעיקרון -
בתגובה להודעה מספר 0

אתה מקבל מחסנית ומתחיל לרוקן אותה למחסנית אחרת כאשר רק מספרים ששונים מ-0 נכנסים אליה.
לבסוף, אתה צריך להפוך אותה, אז פשוט תרוקן אותה לתוך המחסנית הריקה שיש לך כבר. במקומות הריקים תדחוף את ה-0-ים שלך....

בעיקרון, מבחינת ביצועים זה סבבה לגמרי - O(n)

*מקווה שהבנתי אותך טוב....

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Ice Cold

חבר מתאריך 3.8.02
28041 הודעות, 19 פידבק

20:06 29.08.16

5. זה בדיוק מה שעשיתי היום בבוקר :) תודה!!
בתגובה להודעה מספר 3

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

cfirzzz

חבר מתאריך 1.8.02
5060 הודעות, 2 פידבק

00:31 07.09.16

7. למה מחסניות?
בתגובה להודעה מספר 3

אומנם אתה נשאר עם o(n) אבל מבזבז זכרון...
אפשר עם queue לעשות את זה ב פעם אחת

נשלח ע"י הסלולרי

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

-UC-

חבר מתאריך 1.8.02
21922 הודעות, 1 פידבק

12:57 07.09.16

8. לא הבנתי את כוונתך
בתגובה להודעה מספר 7

ב-2 המקרים אתה תלוי באופן המימוש של המבנה הנתונים ואת שניהם ניתן לממש ע"י רשימה מקושרת, השוני הוא באופן השליפה מהם...
אם כבר יש לו מחסנית, אז יש לו את המימוש...

אשמח אם תוכל להסביר לי מה השוני מבחינת זיכרון @cfirzzz@

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

cfirzzz

חבר מתאריך 1.8.02
5060 הודעות, 2 פידבק

16:15 07.09.16

9. מכתב
בתגובה להודעה מספר 8

תחשוב על המערך הבא
0 3 5 0 3 0
אנחנו רוצים להגיע ל
0 0 0 3 5 3
תחזיק 2 אינדקסים
a עובר על כל האיברים
b מצביע למקום הבא שאליו מעבירים
נתחיל
a על אינדקס 0, רואה 0, מקדם את a
a על אינדקס 1, רואה 3, שם 3 איפה ש b מצביע (אינדקס 0) מקדם את b ומאפס את התא שa מצביע עליו, עכשיו המערך נראה ככה :
0 3 5 0 0 3
בסוף הריצה המערך יהיה כמו שרצינו, ולא השתמשנו בזכרון נוסף

נשלח ע"י הסלולרי

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

cfirzzz

חבר מתאריך 1.8.02
5060 הודעות, 2 פידבק

16:16 07.09.16

10. מכתב
בתגובה להודעה מספר 8

@-UC-@

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

-UC-

חבר מתאריך 1.8.02
21922 הודעות, 1 פידבק

16:34 07.09.16

11. במערך זה נכון, אבל במחסנית אין לך את האופציה לגשת לאיבר באמצע/התחלה
בתגובה להודעה מספר 10

אלא רק לראש המחסנית בכל פעם.

הבחור דיבר על מחסנית ולא מערך - כנראה שהתרגיל עצמו הוא במחסנית...
@cfirzzz@

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

cfirzzz

חבר מתאריך 1.8.02
5060 הודעות, 2 פידבק

16:40 07.09.16

12. מכתב
בתגובה להודעה מספר 11

נכון, פספסתי את הכותרת :/

נשלח ע"י הסלולרי

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Ice Cold

חבר מתאריך 3.8.02
28041 הודעות, 19 פידבק

10:37 11.09.16

15. רק תיקון קטן, זה לא היה תרגיל חחח זה בשביל משחק שאני מפתח :)
בתגובה להודעה מספר 12

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

ldan192
חבר מתאריך 14.9.08
95119 הודעות

10:13 29.08.16

4. PriorityQueue ש-0 מחזיר מספר חיובי ולא 0 מחזיר מספר שלילי (בהנחה ששורה 0 זה הראש
בתגובה להודעה מספר 0

private class SpecialComp implements Comparator<SpecialComp> {
public int compareTo(SpecialComp other) {
if (this.val == 0) return 1;
return -1;
}
}

בברכה,
עידן

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Ice Cold

חבר מתאריך 3.8.02
28041 הודעות, 19 פידבק

20:07 29.08.16

6. בסוף אני ו-UC חשבנו על אותו דבר :) תודה לכולם :)
בתגובה להודעה מספר 0

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

cfirzzz

חבר מתאריך 1.8.02
5060 הודעות, 2 פידבק

09:51 09.09.16

13. עוד פתרון עם o(1) זכרון
בתגובה להודעה מספר 0

int size = stack.size();
int holes = 0;
for (int i = 0 ; i < size ; ++i)
{
int popped = stack.pop();
if (popped != 0)
{
stack.push(popped);
++holes;
}
}
for (int i = 0 ; i < holes ; ++i)
{
stack.push(0);
}

@-UC-@

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

-UC-

חבר מתאריך 1.8.02
21922 הודעות, 1 פידבק

09:35 11.09.16

14. זה ממש לא O)1(
בתגובה להודעה מספר 13

אלא O)n(
שים לב שאתה רץ על SIZE שזה N למעשה...

אגב, הפתרון שלך לא יעבוד
במחסנית יש לך גישה רק לראש המחסנית, אז בפתרון שלך -
אתה שולף איבר מראש המחסנית ובודק אם הוא שונה מ-0, אם כן - אז אתה דוחף אותו חזרה לראש המחסנית. סיבוב הבא אתה תשלוף אותו מחדש - אף פעם לא תגיע לאיבר הבא...
חובה להשתמש כאן במחסנית(או מבנה נתונים אחר) ולשלוף איבר איבר

@cfirzzz@

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

cfirzzz

חבר מתאריך 1.8.02
5060 הודעות, 2 פידבק

16:45 11.09.16

16. מכתב
בתגובה להודעה מספר 14

א. כתבתי שזה o(1) זכרון - לא זמן ריצה, ברור שאי אפשר לרוץ ב o(1) כשחובה לבדוק את כל האיברים
ב. צודק, משום מה היה לי בראש queue, יהיה טוב.

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

cfirzzz

חבר מתאריך 1.8.02
5060 הודעות, 2 פידבק

16:45 11.09.16

17. מכתב
בתגובה להודעה מספר 14

@-UC-@
מישהו חייב לעשות משהו עם זה שחייב לערוך הודעה חדשה כדי לתייג

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד