二维数组查找，替换空格，从尾到头打印列表

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

本文地址：https://blog.csdn.net/qq_43031201/article/details/107442755