1.二维数组查找

题目描述

解题思路

暴力解法：

遍历数组中的每一个元素，与target值相比较 时间复杂度：O（mn） 空间复杂度：O（1） 

线性查找

考虑到给出的数组排序具有一定的规律，当访问到一个元素时，排除数组中的部分元素 从数组的右上角，即matrix[0][cols - 1]开始查找，当前元素等于target，则返回true； 当前元素小于target，则向下移动一行，若当前元素大于target，则向左移动一列。 

C++

class Solution{ public:     bool findNumberIn2DArray(vector<vector<int>> & matrix, int target)     {     	// 首先判断数组是否为空，若数组为空或是一维数组，返回false     	if(matrix.empty() || matrix[0].empty()) return false;    	// 获取二维数组的行数和列数     	int rows = matrix.size();     	int cols = matrix[0].size();     	int row = 0;     	int col = cols-1;     	while(row<rows && col >= 0) 	// 注意判断循环条件时，col可以等于0     	{     	    if(target == matrix[row][col]) return true;     	    if(target > matrix[row][col]) row++;     	    else col--;     	}      	return false;     } }; 

Python

class Solution(object):     def findNumberIn2DArray(self, matrix, target):     	"""     	:type matrix: List[List[int]]     	:type target: int     	:rtype: bool     	"""     	if not matrix or not matrix[0]:     	    return False     	rows = len(matrix)     	cols = len(matrix[0])     	row = 0     	col = cols - 1     	while row<rows and col>=0:     	    if target == matrix[row][col]:     	    	return True     	    elif target > matrix[row][col]:     	    	row += 1     	    else:     	    	col -= 1     	return False 

2.替换空格

题目描述

解题思路

C++

没有开辟额外空间,先根据空格数量在字符串末尾扩容两个字符的空间 (因为一个空格变为%20需要多出两个空间), 然后倒序遍历将原来位置的字符放到后面, 最后返回s就可以了 

class Solution { public:     string replaceSpace(string s) {         int l1 = s.length() - 1;         for (int i = 0; i <= l1; i++) {             if (s[i] == ' ') {                 s += "00";             }         }         int l2 = s.length() - 1;         if (l2 <= l1) {             return s;         }         for (int i = l1; i >= 0; i--) {             char c = s[i];             if (c == ' ') {                 s[l2--] = '0';                 s[l2--] = '2';                 s[l2--] = '%';             } else {                 s[l2--] = c;             }         }         return s;     } };  

Python

初始化一个 list ，记为 res ； 遍历列表 s 中的每个字符 c ： 当 c 为空格时：向 res 后添加字符串 "%20"； 当 c 不为空格时：向 res 后添加字符 c ； 将列表 res 转化为字符串并返回。 

class Solution:     def replaceSpace(self, s: str) -> str:         res = []         for c in s:             if c == ' ': res.append("%20")             else: res.append(c)         return "".join(res) 

3.从尾到头打印链表

题目描述

解题思路与实现

1）反转

从头到尾将链表打印到数组中，返回反转后的结果即可 时间复杂度：O(n) 空间复杂度：O(n) 

C++

class Solution { public:     vector<int> reversePrint(ListNode* head) {         vector<int> res;         while (head){             res.push_back(head->val);             head = head->next;         }         reverse(res.begin(), res.end());         return res;     } }; 

Python

class Solution:     def reversePrint(self, head: ListNode) -> List[int]:         res = []         while head:             res.append(head.val)             head = head.next         return reverse(res) 

2）递归

假设head->next已经排号序，将head添加到末尾即可 head->next排序通过递归来实现，递归终止条件为head为空 时间复杂度：O（n） 空间复杂度：O（n） 

C++

class Solution{ public: 	vector<int> res; 	vector<int> reversePrint(ListNode* head){ 		if(!head) return res; 		reversePrint(head->next); 		res.push_back(head->val); 		return res; 		} }; 

Python

class Solution(object): 	def reversePrint(self, head): 		""" 		:type head: ListNode 		:rtype: List[int] 		""" 		if not head: return [] 		return self.reversePrint(head.next) + [head.val]  

3）堆栈

利用堆栈先进后出的特点，先将元素压入栈中，再将元素弹出并保存到列表中，即可实现反转 时间复杂度：O（n） 空间复杂度：O（n） 

C++

class Solution{ public: 	vector<int> reversePrint(ListNode* head){ 	vector<int> res; 	stack<int> st; 	while(head){ // push 		st.push(head->val); 		head = head->next; 		} 	while(!st.empty()){ // pop 		res.push_back(st.top()); 		st.pop(); 		} 	return res; 	} }; 

Python

class Solution(object): 	def reversePrint(self, head): 		stack = [] 		res = [] 		while head: # push 			stack.append(head.val) 			head = head.next 		while stack: # pop 			res.append(stack.pop()) 		return res 

c/c++开发分享二维数组查找，替换空格，从尾到头打印列表地址：https://blog.csdn.net/qq_43031201/article/details/107442755