# Sword finger offer special exercise

Continuously updating

## 1. Search in two-dimensional array

Problem: in a two-dimensional array (each one-dimensional array has the same length), each row is sorted in ascending order from left to right, and each column is sorted in ascending order from top to bottom. Please complete a function, input such a two-dimensional array and an integer, and judge whether the array contains the integer.
Idea 1: so easy.
Idea 2: considering that it is an increasing order array, just start from the bottom left or the top right. Take the bottom left as an example: if the integer is less than the current value, move it up one bit, if it is greater than the current value, move it right one bit.

```class Solution:
def search(self,array,target):
if(array==[]):
return False
len_row=len(array)
len_col=len(array)
i=len_row-1
j=0
while i>=0 and j<len_col:
if(target<array[i][j]):
i-=1
elif(target>array[i][j]):
j+=1
else:
return True
return False

'''test'''
if __name__ == '__main__':
a=Solution()
array=[[1,2,3],[4,5,6],[7,8,9]]
target=12
print(a.search(array,target))
```

## 2. Replace spaces

Question: please implement a function to replace each space in a string with "% 20". For example, when the string is We Are Happy Then the replaced string is We%20Are%20Happy.
Idea 1: python replace method.
Idea 2: create a new string ss, traverse the characters of the original string, and when a space is encountered, add a "% 20" to ss to output ss.

```class Solution:
def repalceSpace_1(self,s):
s=s.replace(" ","%20")
return s
def repalceSpace_2(self,s):
res=""
len_s=len(s)
for i in range(len_s):
if(s[i]==" "):
res+="%20"
else:
res+=s[i]
return res

if __name__ == '__main__':
a=Solution()
s='We Are  Happy'
print(a.repalceSpace_2(s))
```

## 3. Print the linked list from end to end

Question: enter a linked list and return an ArrayList in the order of linked list values from tail to head.
Idea 1: traverse the linked list, append to the list, and flip the list.
Idea 2: traverse the linked list and insert it into the head of the list every time.

```class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
res=[]
while listNode:
res.append(listNode.val)
listNode=listNode.next
res=res[::-1]
return res
res=[]
while listNode:
res.insert(0,listNode.val)
listNode=listNode.next
return res

if __name__ == '__main__':
A1 = ListNode(1)
A2 = ListNode(2)
A3 = ListNode(3)
A4 = ListNode(4)
A5 = ListNode(5)

A1.next=A2
A2.next=A3
A3.next=A4
A4.next=A5

a=Solution()