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:
- The length range of nums # is [1, 50]
- 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 -1add 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]+digitsSearch 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 resIntroduction 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] = 0Diagonal 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