Arrays: Left Rotation

Array (Easy)

A left rotation operation on an array shifts each of the array’s elements 1 unit to the left. For example, if 2 left rotations are performed on array [1,2,3,4,5], then the array would become [3,4,5,1,2].

Given an array a of n integers and a number, d, perform d left rotations on the array. Return the updated array to be printed as a single line of space-separated integers.

• Function Description
  • Complete the function rotLeft in the editor below. It should return the resulting array of integers.
  • rotLeft has the following parameter(s):
    • An array of integers a
    • An integer d, the number of rotations.
• Input Format
  • The first line contains two space-separated integers n and d, the size of a and the number of left rotations you must perform.
  • The second line contains n space-separated integers a[i].
• Constraints
  • 1 <= n <= 10^5
  • 1 <= d <= n
  • 1 <= a[i] < 10^6
• Output Format
  • Print a single line of n space-separated integers denoting the final state of the array after performing d left rotations.

Sample Input

5 4
1 2 3 4 5

Sample Output

5 1 2 3 4

Explanation

When we perform d=4 left rotations, the array undergoes the following sequence of changes:

[1,2,3,4,5] -> [2,3,4,5,1] -> [3,4,5,1,2] -> [4,5,1,2,3] -> [5,1,2,3,4]

Code:

#!/bin/python3

import math
import os
import random
import re
import sys

# Complete the rotLeft function below.
def rotLeft(a, d):
    # print(a, d)  # [1, 2, 3, 4, 5] 4
    ### APPROACH1: Did not execute within the time limits
    # n = len(a)
    # r = d % n
    # for i in range(r):
    #     a[:] = a[1:n]+a[:1]
    # return a
    
    ### APPROACH2
    a[:] = a[d:] + a[:d]
    return a

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    nd = input().split()

    n = int(nd[0])

    d = int(nd[1])

    a = list(map(int, input().rstrip().split()))

    result = rotLeft(a, d)

    fptr.write(' '.join(map(str, result)))
    fptr.write('\n')

    fptr.close()

2D Array - DS

Array (Easy)

Given a 6x 2D Array, arr:

1 1 1 0 0 0
0 1 0 0 0 0
1 1 1 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0

We define an hourglass(⌛️) in A to be a subset of values with indices falling in this pattern in arr’s graphical representation:

a b c
  d
e f g

There are 16 hourglasses in arr(arr里面有16个沙漏), and an hourglass sum is the sum of an hourglass’ values. Calculate the hourglass sum for every hourglass in arr, then print the maximum hourglass sum.(计算每个沙漏的总和, 找出16个中最大的那一个)

For example, given the 2D array:

-9 -9 -9  1 1 1 
 0 -9  0  4 3 2
-9 -9 -9  1 2 3
 0  0  8  6 6 0
 0  0  0 -2 0 0
 0  0  1  2 4 0

We calculate the following 16 hourglass values:

-63, -34, -9, 12, 
-10, 0, 28, 23, 
-27, -11, -2, 10, 
9, 17, 25, 18

Our highest hourglass value is 28 from the hourglass:

0 4 3
  1
8 6 6

Note: If you have already solved the Java domain’s Java 2D Array challenge, you may wish to skip this challenge.

Function Description:

• Complete the function hourglassSum in the editor below. It should return an integer, the maximum hourglass sum in the array.
• hourglassSum has the following parameter(s):
  • arr: an array of integers
• Input Format
  • Each of the 6 lines of inputs arr[i] contains 6 space-separated integers arr[i][j].
• Constraints
  • -9 <= arr[i][j] <= 9
  • 0 <= i, j <= 5
• Output Format
  • Print the largest (maximum) hourglass sum found in arr.

Sample Input

1 1 1 0 0 0
0 1 0 0 0 0
1 1 1 0 0 0
0 0 2 4 4 0
0 0 0 2 0 0
0 0 1 2 4 0

Sample Output

19

The hourglass with the maximum sum (19) is:

2 4 4
  2
1 2 4

解题思路:

arr[i][j]    arr[i][j+1]     arr[i][j+2]
             arr[i+1][j+1] 
arr[i+2][j]  arr[i+2][j+1]   arr[i+2][j+2]

另外, 一个沙漏最多只有7个值, 每个值介于-9 ~ 9 之间, 所以最小的hourglass会是7*-9=63

Code:

#!/bin/python3

import math
import os
import random
import re
import sys

# Complete the hourglassSum function below.
def hourglassSum(arr):
    r = len(arr)
    c = len(arr[0])
    # temp_max = -float('Inf')
    temp_max = -63

    for i in range(r-2):
        for j in range(c-2):
            temp = arr[i][j]+arr[i][j+1]+arr[i][j+2]+arr[i+1][j+1]+arr[i+2][j]+arr[i+2][j+1]+arr[i+2][j+2]
            temp_max = max(temp,temp_max)
    return temp_max

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    arr = []

    for _ in range(6):
        arr.append(list(map(int, input().rstrip().split())))

    result = hourglassSum(arr)

    fptr.write(str(result) + '\n')

    fptr.close()

New Year Chaos

Array, Sorting (Medium)

It’s New Year’s Day and everyone’s in line for the Wonderland rollercoaster ride! There are a number of people queued up, and each person wears a sticker indicating their initial position in the queue. Initial positions increment by 1 from 1 at the front of the line to n at the back.

Any person in the queue can bribe the person directly in front of them to swap positions. If two people swap positions, they still wear the same sticker denoting their original places in line. One person can bribe at most two others. For example, if n = 8 and Person5 bribes Person4, the queue will look like this: 1,2,3,5,4,6,7,8.

Fascinated by this chaotic queue, you decide you must know the minimum number of bribes that took place to get the queue into its current state!

Function Description:

• Complete the function minimumBribes in the editor below. It must print an integer representing the minimum number of bribes necessary, or Too chaotic if the line configuration is not possible.
• minimumBribes has the following parameter(s):
  • q: an array of integers
• Input Format
  • The first line contains an integer , the number of test cases.
  • Each of the next pairs of lines are as follows:
    • The first line contains an integer , the number of people in the queue
    • The second line has space-separated integers describing the final state of the queue.
• Constraints
• Output Format
  • Print an integer denoting the minimum number of bribes needed to get the queue into its final state. Print Too chaotic if the state is invalid, i.e. it requires a person to have bribed more than people.

• Sample Input

  2
  5
  2 1 5 3 4
  5
  2 5 1 3 4

  Sample Output

  3
  Too chaotic

Explanation:

解题思路:

• 就是一个数组，每个数字只能移动两个位置，如果大于两个位置就不合理了. 反向思维就是数组排序，如果是合理的，需要几次能排序成功
• 把input数组变成顺序的数组即可

Code:

#!/bin/python3

import math
import os
import random
import re
import sys
from collections import defaultdict

# Complete the minimumBribes function below.
def minimumBribes(q):
    res = defaultdict(int)
    cnt = 0
    cont = True

    while cont:
        cont = False
        for i in range(len(q)-1):
            if q[i] > q[i+1]:
                res[q[i]] += 1
                if res[q[i]] > 2:
                    cont = False
                    cnt = 'Too chaotic'
                    break
                q[i],q[i+1] = q[i+1],q[i]
                cnt += 1
                cont = True
    print(cnt)


if __name__ == '__main__':
    t = int(input())

    for t_itr in range(t):
        n = int(input())

        q = list(map(int, input().rstrip().split()))

        minimumBribes(q)

Minimum Swaps 2

Array (Medium)

You are given an unordered array consisting of consecutive integers in [1, 2, 3, …, n] without any duplicates. You are allowed to swap any two elements. You need to find the minimum number of swaps required to sort the array in ascending order.

For example, given the array arr=[7,1,3,2,4,5,6] we perform the following steps:

i arr swap (indices)
0 [7, 1, 3, 2, 4, 5, 6] swap (0,3)   # 1,3 是ascending, 2 不是, 所以与7交换
1 [2, 1, 3, 7, 4, 5, 6] swap (0,1)
2 [1, 2, 3, 7, 4, 5, 6] swap (3,4)
3 [1, 2, 3, 4, 7, 5, 6] swap (4,5)
4 [1, 2, 3, 4, 5, 7, 6] swap (5,6)
5 [1, 2, 3, 4, 5, 6, 7]

It took 5 swaps to sort the array.

Function Description:

• Complete the function minimumSwaps in the editor below. It must return an integer representing the minimum number of swaps to sort the array.
• minimumSwaps has the following parameter(s):
  • arr: an unordered array of integers
• Input Format
  • The first line contains an integer, n, the size of arr.
  • The second line contains n space-separated integers arr[i].
• Constraints
  • 1 <= n <= 10^5
  • 1 <= arr[i] <= n
• Output Format
  • Return the minimum number of swaps to sort the given array.

Sample Input 0

4
4 3 1 2

Sample Output 0

3

Sample Input 1

5
2 3 4 1 5

Sample Output 1

3

Sample Input 2

7
1 3 5 2 4 6 7

Sample Output 2

3

解题思路:

1. 找到正确顺序的元素位置并交换
2. 将数组先排序,以的形式保存到Map中,遍历未排序的数组,将元素逐个和已排序数组对应位置元素比较,若相等则跳过,不等则从Map中取出已排序元素的index更新未排序元素的value上(交换操作),同时swap list中的元素.这样遍历完成之后,就得到整个交换过程

code:

#!/bin/python3

import math
import os
import random
import re
import sys
from collections import defaultdict

# Complete the minimumSwaps function below.
def minimumSwaps(arr):
    ### APPROACH1: Did not execute within the time limits
    # n = len(arr)
    # count = 0
    # for i in range(1,n+1):
    #     if i == arr[i-1]:  # i即是顺序数组的索引也是元素
    #         continue
    #     else:
    #         index = arr.index(i)  # 找到正确顺序的元素位置
    #         arr[i-1],arr[index] = arr[index],arr[i-1] # 并交换
    #         count += 1
    # return count

    ### APPROACH2: use dict
    ref_arr = sorted(arr)
    index_dict = {v: i for i,v in enumerate(arr)}
    swaps = 0
    
    for i,v in enumerate(arr):
        correct_value = ref_arr[i]
        if v != correct_value:
            to_swap_ix = index_dict[correct_value]
            arr[to_swap_ix],arr[i] = arr[i], arr[to_swap_ix]
            index_dict[v] = to_swap_ix
            index_dict[correct_value] = i
            swaps += 1
    return swaps  


if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    n = int(input())

    arr = list(map(int, input().rstrip().split()))

    res = minimumSwaps(arr)

    fptr.write(str(res) + '\n')

    fptr.close()

Array Manipulation

Array, Prefix Sum Algorithm (Hard)

给你一个长度为N的列表，列表的初始值全是0。对此列表，你要进行M次查询，输出列表种最终N个值的最大值。对每次查询，给你的是3个整数——a,b和k，你要对列表中从位置a到位置b范围内的（包含a和b)的全部元素加上k.

• 输入格式
  • 第一行包含两个整数 N和 M
  • 接下来 M行，每行包含3个整数 a, b 和 k
  • 列表中的数位置编号为从1到 N
• 输出格式
  • 单独的一行包含 最终列表里的最大值
• 约束条件
  • 3 <= N <= 10^7
  • 1 <= M <= 2*10^5
  • 1 <= a <= b <= N
  • 0 <= k <= 10^9

输入样例 0:

5 3
1 2 100
2 5 100
3 4 100

输出样例 0:

200

解释:

第一次更新后，列表变为 100 100 0 0 0，
第二次更新后，列表变为 100 200 100 100 100。
第三次更新后，列表变为 100 200 200 200 100。
因此要求的答案是200

解题思路:

1. 暴力解法就是, 将每次更新的列表都算出来, 选取最后一个列表的最大值, 时间复杂度 O(n^2).
2. 使用前缀和, 避免把区间内的所有元素都操作一遍. (每次区间内的元素都是加上同样的值, 不妨只操作一次)
   1. 找到区间的开始点𝑙和结束点𝑟以后
   2. 只在开始位置𝑙加上对应值，在区间结束点的下一位（如果存在的话）减去这个对应值
   3. 最后得到的数组通过区间求和操作得到最大值

跟上面同样的例子:

第一次更新后，列表变为 [100, 0, -100, 0, 0]
第二次更新后，列表变为 [100, 100, -100, 0, 0]
第三次更新后，列表变为 [100, 100, 0, 0, -100]
因此答案为求和得到的最大值是200

Code:

#!/bin/python3

import math
import os
import random
import re
import sys

# Complete the arrayManipulation function below.
def arrayManipulation(n, queries):
    ### APPROACH 1: Did not execute within the time limits
    ### Brute Force Method
    # arr= [0]*n
    # max_val = 0
    # # print(queries,n,'-===-') # [[1, 2, 100], [2, 5, 100], [3, 4, 100]] 5 -===-
    # for q in queries:
    #     l,r = q[0]-1, q[1]-1  # 范围左右两边的索引
    #     for i in range(l,r+1): # 
    #         arr[i] += q[2]
    #         max_val = max(arr[i],max_val)
    # return max_val

    ### APPROACH 2: use prefix Sum Algorithm 前缀和
    arr = [0] * n
    max_val = 0
    for q in queries:
        l,r = q[0]-1, q[1]-1
        arr[l] += q[2]
        if r+1 < n:
            arr[r+1] -= q[2]
    # print(arr,'=======')
    tmp = 0
    for i in range(n):
        tmp += arr[i]
        max_val = max(max_val,tmp)
    return max_val


if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    nm = input().split()

    n = int(nm[0])

    m = int(nm[1])

    queries = []

    for _ in range(m):
        queries.append(list(map(int, input().rstrip().split())))

    result = arrayManipulation(n, queries)

    fptr.write(str(result) + '\n')

    fptr.close()