#30daychallenge (14) (15) | Perform String Shift & Product of Array Except Self

Hôm qua bận không thể đăng, dù biết không có ai xem nhưng vẫn cảm thấy có lỗi với bản thân. Dạo này tôi thấy hiệu suất không được cao lắm. (Social network nhiều:)))

Perform String Shifts

You are given a string s containing lowercase English letters, and a matrix shift, where shift[i] = [direction, amount]:

• direction can be 0 (for left shift) or 1 (for right shift). 
• amount is the amount by which string s is to be shifted.
• A left shift by 1 means remove the first character of s and append it to the end.
• Similarly, a right shift by 1 means remove the last character of s and add it to the beginning.

Return the final string after all operations.

Example 1:

Input: s = "abc", shift = [[0,1],[1,2]]
Output: "cab"
Explanation: 
[0,1] means shift to left by 1. "abc" -> "bca"
[1,2] means shift to right by 2. "bca" -> "cab"

Example 2:

Input: s = "abcdefg", shift = [[1,1],[1,1],[0,2],[1,3]]
Output: "efgabcd"
Explanation:  
[1,1] means shift to right by 1. "abcdefg" -> "gabcdef"
[1,1] means shift to right by 1. "gabcdef" -> "fgabcde"
[0,2] means shift to left by 2. "fgabcde" -> "abcdefg"
[1,3] means shift to right by 3. "abcdefg" -> "efgabcd"

Constraints:

• 1 <= s.length <= 100
• s only contains lower case English letters.
• 1 <= shift.length <= 100
• shift[i].length == 2
• 0 <= shift[i][0] <= 1
• 0 <= shift[i][1] <= 100

Leetcode là một trang rất hay để luyện giải thuật, nhưng không phải là một trang tuyệt vời để luyện lập trình thi đấu, hãy nhìn giới hạn của nó kìa, có nghĩa là nó quá coi thường thời gian chạy rồi. Có lẽ tôi sẽ phải sớm thôi chuyển sang trên codeforces.

Với đề bài này, nó giúp ta ôn lại một cấu trúc dữ liệu đặc biệt, vừa có thể dùng như Stack (LIFO), cũng có thể dùng như Queue(FIFO). Đa năng như thế nên tên nó là deque. Một cấu trúc dữ liệu tuyệt vời. Khá đơn giản, với interface là LinkedList thì càng hoàn hảo hơn.


Tôi làm đúng những gì Leetcode diễn giải như ở trên luôn nên chắc không giải thích thêm nữa.

  Product of Array Except Self

Given an array nums of n integers where n > 1,  return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Example:

Input:  [1,2,3,4]
Output: [24,12,8,6]

Constraint: It's guaranteed that the product of the elements of any prefix or suffix of the array (including the whole array) fits in a 32 bit integer.

Note: Please solve it without division and in O(n).

Follow up:
Could you solve it with constant space complexity? (The output array does not count as extra space for the purpose of space complexity analysis.)

Bỏ qua cái tối ưu không gian đi, giờ tôi không có nhiều thời gian cho bài toán này, cứ AC đã. (Biết là ngụy biện mà :(( )

Bài toán này bạn có nhận ra là mảng dưới là tích của các số không chứa chính nó, tôi khuyên bạn dẹp bỏ cái suy nghĩ tính tích của tất cả các số xong mảng bên dưới chia cho chính số nó đi nhé. Vì nó sẽ tạo nên rất nhiều trường hợp, bạn sẽ phải if else, submit nhiều lần không AC đâu. (Bởi tôi thử rồi).

Cách nghĩ đơn giản của bài toán này là khi bạn nhận ra, tích của tất cả mọi số trừ chính số đó chính bằng tích của phía bên phải * tích của phía bên trái, key của bài này ở chỗ đấy. Thế giờ code nhé:


Hết rồi, hẹn gặp Leetcode vào ngày mai. Cảm ơn bạn !