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[0])
        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:
    def printListFromTailToHead_1(self,listNode):
        res=[]
        while listNode:
            res.append(listNode.val)
            listNode=listNode.next
        res=res[::-1]
        return res
    def printListFromTailToHead_2(self,listNode):
        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()

    print(a.printListFromTailToHead_1(A1))

Tags: Python

Posted by doreg28 on Sat, 21 May 2022 13:16:46 +0300