Arrays and strings

target

1. Understand the difference between array and dynamic array.

2. Be familiar with the basic operations in array and dynamic array.

3. Be able to understand and use multidimensional arrays.

4. Understand the concept of string and the different characteristics of string.

5. Be able to use double pointer skills to solve practical problems.

Array introduction

An array is a basic data structure used to store a collection of elements in order. However, elements can be accessed randomly because each element in the array can be identified by the array index.

Arrays can have one or more dimensions. Here we start with a one-dimensional array, which is also called a linear array.

Introduction to dynamic array

The array has a fixed capacity. We need to specify the size of the array during initialization. Sometimes it is very inconvenient and may cause waste.

Therefore, most programming languages provide built-in dynamic array. It is still a random access list data structure, but the size is variable.

Find the middle index of the array

Given an array of integer type {nums, please write a method that can return the "central index" of the array.

We define the array center index in this way: the sum of all elements on the left of the array center index is equal to the sum of all elements on the right.

If there is no central index in the array, we should return - 1. If the array has multiple central indexes, we should return the one closest to the left.

Example 1:

input: 
nums = [1, 7, 3, 6, 5, 6]
output: 3
 explain: 
Index 3 (nums[3] = 6) The sum of the numbers on the left side of(1 + 7 + 3 = 11),Sum of and right(5 + 6 = 11)equal.
meanwhile, 3 It is also the first central index that meets the requirements.

Example 2:

input: 
nums = [1, 2, 3]
output: -1
 explain: 
There is no central index in the array that meets this condition.

explain:

  • The length range of num is [0, 10000].
  • Any {num [i] will be an integer in the range [- 1000, 1000].
class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        if len(nums) < 3:
            return -1
        for i in range(len(nums)):
            if sum(nums[:i]) == sum(nums[i+1:]):
                return i
        return -1
        

At least twice the maximum number of other data

In a given array num, there is always a maximum element.

Finds whether the largest element in the array is at least twice as large as every other number in the array.

If yes, the index of the largest element is returned, otherwise - 1 is returned.

Example 1:

input: nums = [3, 6, 1, 0]
output: 1
 explain: 6 The largest integer is, For other integers in the array,
6 Greater than twice the number of other elements in the array. The index of 6 is 1, So we return to 1.

 

Example 2:

input: nums = [1, 2, 3, 4]
output: -1
 explain: 4 Not more than twice as big as three, So we go back -1.

 

Tips:

  1. The length range of nums # is [1, 50]
  2. The integer range of each {num [i] is [0, 100]
class Solution:
    def dominantIndex(self, nums: List[int]) -> int:
        nums_max = max(nums)
        ind = nums.index(nums_max)
        tmp = []
        for item in nums:
            if nums_max >= 2 * item or item == nums_max:
                tmp.append(item)
        if len(tmp) == len(nums) :
            return ind
        else:
            return -1

add one-tenth

Given a non negative integer represented by a non empty array of integers, add one to the number.

The highest digit is stored in the first place of the array, and each element in the array only stores a single digit.

You can assume that this integer does not start with zero except for the integer 0.

Example 1:

input: [1,2,3]
output: [1,2,4]
explain: The input array represents the number 123.

Example 2:

input: [4,3,2,1]
output: [4,3,2,2]
explain: The input array represents the number 4321.
class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        n=len(digits)
        for i in range(n-1,-1,-1):
            if digits[i]<9:
                digits[i]+=1
                return digits
            else:
                digits[i]=0
        return [1]+digits

Search insertion location

Given a sort array and a target value, find the target value in the array and return its index. If the target value does not exist in the array, return the position where it will be inserted in order. You can assume that there are no duplicate elements in the array.

Example 1:

input: [1,3,5,6], 5
 output: 2
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        for i in range(0, len(nums)):
            if nums[i] >= target:
                return i
            elif i == len(nums) - 1:
                return len(nums)

Merge interval

Given a set of intervals, please merge all overlapping intervals.

Example 1:

input: [[1,3],[2,6],[8,10],[15,18]]
output: [[1,6],[8,10],[15,18]]
explain: section [1,3] and [2,6] overlap, Merge them into [1,6].
class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        res = []
        intervals.sort()
        for i in intervals:
            if not res or res[-1][1]<i[0]:
                res.append(i)
            else:
                res[-1][1] = max(res[-1][1],i[1])
        return res

Introduction to 2D data

Multidimensional arrays are more suitable for complex structures such as tables or matrices.

Learning objectives:

1. How are two-dimensional arrays stored in memory

2. How to use two-dimensional array to solve problems

Rotation matrix

Here's a picture by # n × An image represented by an N-matrix, where the size of each pixel is 4 bytes. Please design an algorithm to rotate the image 90 degrees.

Can you do it without taking up additional memory space?

Example 1:

given matrix = 
[
  [1,2,3],
  [4,5,6],
  [7,8,9]
],

Rotate the input matrix in place so that it becomes:
[
  [7,4,1],
  [8,5,2],
  [9,6,3]
]
class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        n = len(matrix)
        # Flip the mirror up and down first
        for i in range(n // 2):
            for j in range(n):
                matrix[i][j], matrix[n - 1 - i][j] = matrix[n - 1 - i][j], matrix[i][j]
        
        # Then flip the main diagonal
        for i in range(n):
            for j in range(i):
                matrix[j][i], matrix[i][j] = matrix[i][j], matrix[j][i]

Zero matrix

Write an algorithm if M × If an element in N matrix is 0, its row and column are cleared.

Example 1:

Input:
[
  [1,1,1],
  [1,0,1],
  [1,1,1]
]
Output:
[
  [1,0,1],
  [0,0,0],
  [1,0,1]
]

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        rownum = len(matrix)
        colnum = len(matrix[0])
        row = [False for i in range(rownum)]
        col = [False for i in range(colnum)]
        for i in range(rownum):
            for j in range(colnum):
                if matrix[i][j] == 0:
                    row[i] = True
                    col[j] = True
        for i in range(rownum):
            for j in range(colnum):
                if row[i] or col[j]:
                    matrix[i][j] = 0

Diagonal traversal

Given a matrix containing M x N elements (M rows, N columns), please return all elements in the matrix in the order of diagonal traversal, as shown in the figure below.

 

Example:

Input:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]

Output: [1,2,4,7,5,3,6,8,9]

Explanation:


Author: leetcode
Link: https://leetcode-cn.com/leetbook/read/array-and-string/cuxq3/
Source: LeetCode
The copyright belongs to the author. For commercial reprint, please contact the author for authorization. For non-commercial reprint, please indicate the source.

class Solution:
    def findDiagonalOrder(self, matrix: List[List[int]]) -> List[int]:
        m = len(matrix)
        if not m:
            return []
        n = len(matrix[0])
        if not n:
            return []
        matrix_num = m*n
 
        count = 0
        x = y = 0
        li = []
        direction = "up"
        while count < matrix_num:
            count += 1
            li.append(matrix[x][y])
            # Upper right
            if direction == "up":
                # Conditions without changing direction (1. X > 0 in front of the upper wall, 2. Y < n-1 in front of the right wall)
                if x > 0 and y < n-1:
                     x -= 1
                     y += 1
                     continue
                else:
                    direction = "down"
                    # Hit the upper wall x=0
                    if x == 0 and y < n-1:
                        y += 1
                    # Hit the right wall
                    elif y == n-1:
                        x += 1
            # Lower left direction
            else:
                # Conditions without changing direction (1. X < m in front of the lower wall, 2. Y > 0 in front of the right wall)
                if x < m-1 and y > 0:
                    x += 1
                    y -= 1
                    continue
                else:
                    direction = "up"
                    if x == m-1:
                        y += 1
                    elif y == 0 and x < m-1:
                        x += 1
        return li

String introduction

A string is an array of characters.

Learning objectives:

1. Be familiar with the basic operations in the string, especially the unique operations not in the array;
2. Understand the differences between different comparison functions;
3. Understand whether the string is changeable and the problems in the connection process;
4. Be able to solve basic problems related to strings, such as sorting, substring, string matching, etc.

Longest Common Prefix

Write a function to find the longest common prefix in the string array.

If there is no public prefix, the empty string '' is returned.

Example 1:

Input: ["flower","flow","flight"]
Output: "fl"
Example 2:

Input: ["dog","racecar","car"]
Output: ''
Explanation: the input does not have a public prefix.
explain:

All inputs contain only lowercase letters a-z.

Author: leetcode
Link: https://leetcode-cn.com/leetbook/read/array-and-string/ceda1/
Source: LeetCode
The copyright belongs to the author. For commercial reprint, please contact the author for authorization. For non-commercial reprint, please indicate the source.

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        import os
        return os.path.commonprefix(strs)

Longest Palindromic Substring

Given a string s, find the longest palindrome substring in S. You can assume that the maximum length of S is 1000.

Example 1:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example 2:

Input: "cbbd"
Output: "bb"

Author: leetcode
Link: https://leetcode-cn.com/leetbook/read/array-and-string/conm7/
Source: LeetCode
The copyright belongs to the author. For commercial reprint, please contact the author for authorization. For non-commercial reprint, please indicate the source.

class Solution:
    def longestPalindrome(self, s: str) -> str:
        max_length = 0
        start = 0
        for i in range(len(s)):
            if i - max_length >= 1 and s[i-max_length-1: i+1] == s[i-max_length-1: i+1][::-1]:
                start = i - max_length - 1
                max_length +=2
                continue
            if i - max_length >= 0 and s[i-max_length: i+1] == s[i-max_length: i+1][::-1]:
                start = i - max_length
                max_length += 1
        return s[start: start+max_length]

Flip the words in the string

Given a string, flip each word in the string one by one.

 

Example 1:

input: "the sky is blue"
output: "blue is sky the"
class Solution:
    def reverseWords(self, s: str) -> str:
        li = s.split(" ")
        str = ""
        for i in range(len(li)-1, -1, -1):
            if li[i]:
                str = str + li[i] + " "
        # Because there is an extra space character "" in the last word          
        return str[:-1] 

String matching algorithm: KMP

Knuth – Morris – Pratt (KMP) algorithm is an improved string matching algorithm. Its core is to use the information after matching failure to minimize the matching times between pattern string and main string, so as to achieve the purpose of fast matching. Its time complexity is O(m+n)O(m + n)O(m+n).

int match (char* P, char* S){ // KMP algorithm
    int* next = buildNext(P); // Construct next table
    int m = (int) strlen (S), i = 0; // Text string pointer
    int n = (int) strlen(P), j = 0; //Mode string pointer
    while (j < n && i < m) // Match characters one by one from left to right
        if (0 > j || S[i] == P[j]) // If it matches, or P has removed the leftmost
            {i++; j++} // Then go to the next character
        else
            j = next[j]; // Shift the mode string to the right (Note: the text string does not need to be fallback)
    delete [] next; // Release next table
    return i - j;
}

Implement str ()

Implement the strStr() function.

Given a haystack string and a need string, find the first position of the need string in the haystack string (starting from 0). If it does not exist, - 1 is returned.

Example 1:

Input: haystack = "hello", need = "ll"
Output: 2
Example 2:

Input: haystack = "AAAAA", need = "BBA"
Output: - 1
explain:

When , need , is an empty string, what value should we return? This is a good question in the interview.

For this question, when , need , is an empty string, we should return 0. This is consistent with the definitions of {str() in C language and} indexOf() in Java.

Author: leetcode
Link: https://leetcode-cn.com/leetbook/read/array-and-string/cm5e2/
Source: LeetCode
The copyright belongs to the author. For commercial reprint, please contact the author for authorization. For non-commercial reprint, please indicate the source.

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        for i in range(0, len(haystack) - len(needle) + 1):
            if haystack[i: i + len(needle)] == needle:
                return i
        return -1

 

Tags: Python data structure

Posted by bigwatercar on Mon, 23 May 2022 21:35:07 +0300