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))