1.二维数组查找
题目描述 ![二维数组查找,替换空格,从尾到头打印列表](https://www.ctvol.com/wp-content/themes/justnews/themer/assets/images/lazy.png)
解题思路
暴力解法:
遍历数组中的每一个元素,与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
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/598675.html