Python3 ծրագիր՝ պտտման հարցումների և տվյալ տողի K-րդ նիշի համար մշտական ժամանակում

Այս խնդրի դեպքում մենք պետք է կատարենք հարցումները ըստ տրված կանոնների և տպենք նիշերը թարմացված տողից։ Մենք խնդիրը կլուծենք՝ օգտագործելով երկու տարբեր մոտեցումներ. Առաջին մոտեցման դեպքում մենք կօգտագործենք լարերի ռոտացիայի հայեցակարգը, իսկ երկրորդ մոտեցման դեպքում մենք կօգտագործենք ինդեքսների հարմարեցման մոտեցումը:

Խնդրի հայտարարություն – Մեզ տրված խնդիրն է՝ կատարել տրված հարցումներ տողի վրա: Մենք տվել ենք հարցումների զանգված, և յուրաքանչյուր հարցում պարունակում է երկու ամբողջ թիվ։

Հետևեք ստորև բերված հայտարարություններին՝ տողի վրա տրված հարցումները կատարելու համար:

• (1, l) – Մենք պետք է ձախ պտտենք լարը l անգամ:

• (2, l) – Մենք պետք է մուտք գործենք նիշը l-րդ դիրքից: Այստեղ, 1 <= l <= n.

Նմուշի օրինակներ

Մուտք

queries = [[1, 3], [2, 3], [2, 4], [2, 2]], s = "vdflkmng"

Ելք

m, n, k

Բացատրություն – Եկեք կատարենք զանգվածում տրված բոլոր չորս հարցումները:

• Առաջին հարցումում կատարել տողի 3 ձախ պտույտ։ Վերջնական տողը կլինի «lkmngvdf»:

• Տպեք երրորդ նիշը, որը «m» է:

• Տպեք չորրորդ նիշը, որը «n» է:

• Տպեք երկրորդ նիշը, որը «k» է:

Մուտք

queries = [[1, 3], [1, 2], [1, 3], [2, 2]], s = "welcome"

Ելք

l

Բացատրություն

• Առաջին հարցումից հետո տողը կլինի «comewel»:

• Երկրորդ հարցումից հետո տողը կլինի «mewelco»:

• Երրորդ հարցումից հետո տողը կլինի «elcomew»:

• Վերջին հարցումում այն տպում է 2-րդ նիշը, որը «l» է:

Մոտեցում 1

Այս մոտեցմամբ մենք տրված տողը բաժանում ենք երկու մասի և նորից միանում՝ N ձախ պտույտներ կատարելու համար։ Դրանից հետո մենք մուտք ենք գործում նիշը տվյալ ինդեքսից երկրորդ հարցման մեջ։

Ալգորիթմ

Քայլ 1 – Առաջին քայլում մենք պահանջում ենք կրկնել բոլոր հարցումների զանգվածը:

Քայլ 2 – Եթե que[m][0] == 1, կատարեք s տողի que[m][1] ընդհանուր պտույտները և պահեք այն s-ում:

Քայլ 2.1 – Qu[m][1] ձախ պտույտներ կատարելու համար մենք կարող ենք m ցուցանիշից տողը բաժանել երկու մասի և միացնել աջ և ձախ մասը:

Քայլ 3 – Եթե que[m][0] == 2, մենք պետք է տպենք նիշը if que[m][1] ինդեքսից:

Քայլ 4 – Մուտք գործեք նիշը տվյալ ինդեքսից և ցուցադրեք այն ելքում:

Օրինակ

def executeQueries(s, str_len, que, que_len):
    # Traverse query
    for m in range(que_len):
        # String rotation
        if que[m][0] == 1:
            # Rotate the string by que[m][1] to the left
            s = s[que[m][1]:] + s[:que[m][1]]
        else:
            index = que[m][1] - 1
            # Show character
            print(s[index])
# Driver code
if __name__ == "__main__":
    s = "vdflkmng"
    length = len(s)
    queries = [[1, 3], [2, 3], [2, 4], [2, 2]]
    queries_length = len(queries)
    executeQueries(s, length, queries, queries_length)

Արդյունք

m
n
k

Ժամանակի բարդություն – O(M*N), երբ մենք տողը բաժանում ենք երկու մասի և անցնում ենք ցուցակը:

Տիեզերական բարդություն – O(N), քանի որ մենք պահում ենք պտտվող տողը:

Մոտեցում 2

Այս մոտեցումը վերը նշված մոտեցման օպտիմալացված տարբերակն է: Այստեղ մենք ցույց ենք տալիս վերջին ցուցանիշը: Երբ մենք կատարում ենք հարցումը, մենք թարմացնում ենք ցուցիչի արժեքը, որն օգնում է մեզ խնայել ժամանակ և տարածություն:

Ալգորիթմ

Քայլ 1 – Սահմանեք «ind_ptr» փոփոխականը և սկզբնավորեք զրոյով՝ ներկայացնելով ցուցիչի ցուցիչը:

Քայլ 2 – Օգտագործեք օղակը՝ ցանկը անցնելու համար:

Քայլ 3 – Եթե que[m][0]-ը հավասար է 1-ի, մենք պետք է շահարկենք ցուցիչի արժեքը:

Քայլ 3.1 – Ավելացրե՛ք que[m][1] ind_ptr-ին, վերցրե՛ք մոդուլը ստացված արժեքի 26-ով և կրկին վերագրեք այն ind_ptr փոփոխականին:

Քայլ 4 – Եթե que[m][0]-ը հավասար է 2-ի, մենք պետք է տպենք նիշը, որը գտնվում է que[m][1] ինդեքսում:

Քայլ 5 – Ավելացրեք que[m][1] – 1 ind_ptr փոփոխականին և վերցրեք դրա մոդուլը 26-ով: Դրանից հետո ստացված արժեքը վերագրեք ինդեքսային փոփոխականին:

Քայլ 6 – Մուտք գործեք նիշը ինդեքսից և տպեք այն ելքում ցուցադրելու համար:

Օրինակ

def executeQueries(s, str_len, que, que_len):
    # Starting pointer
    ind_ptr = 0
    # Traverse query
    for m in range(que_len):
        # String rotation
        if que[m][0] == 1:
            # Change index pointer value
            ind_ptr = (ind_ptr + que[m][1]) % str_len
        else:
            index = que[m][1]
            # Get the rotational index of the character
            index = (ind_ptr + index - 1) % str_len
            # Show character
            print(s[index])
if __name__ == "__main__":
    s = "vdflkmng"
    length = len(s)
    queries = [[1, 3], [2, 3], [2, 4], [2, 2]]
    queries_length = len(queries)
    executeQueries(s, length, queries, queries_length)

Արդյունք

m
n
k

Ժամանակի բարդություն – O(M), երբ մենք կրկնում ենք հարցումների տվյալ ցանկը:

Տիեզերական բարդություն – O(1), քանի որ մենք օգտագործում ենք մշտական տարածություն:

Լարի ձախ պտույտները կատարում ենք ըստ տրված պայմանների։ Ծրագրավորողները կարող են նաև փորձել կատարել հարցումներ, որոնք պարունակում են լարերի ճիշտ ռոտացիա: