P3 数组中的重复数字
-
题目描述：在一个长度为n的数组nums里的所有数字都在0~n-1范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
-
示例：输入：[2,3,4,1,2,3]
? 输出：2 或 3
-
题解一：计数法 ， 空间复杂度O（N），时间复杂度O（N）
class Solution { public: int findRepeatNumber(vector<int>& nums) { int n = nums.size(); vector<int> ret(n); for(int x:nums){ if(ret[x] >= 1){ return x; } ret[x]++; } return -1; } }; -
题解二：计数法，空间复杂度O（N），时间复杂度O（N*logN)
class Solution { public: int findRepeatNumber(vector<int>& nums) { unordered_map<int,int> hashmap; for(auto num:nums){ hashmap[num]++; } for(auto it = hashmap.begin();it!=hashmap.end();it++){ if(it->second != 1){ return it->first; } } return 0; } }; -
题解三：排序法，空间复杂度O（1），时间复杂度O（N*logN）
class Solution { public: int findRepeatNumber(vector<int>& nums) { sort(nums.begin(),nums.end()); for(int i = 1;i < nums.size();i++){ if(nums[i] == nums[i-1]){ return nums[i]; } } return -1; } }; -
题解四：交换法，空间复杂度O（1），时间复杂度O（N）
?
有点问题 class Solution { public: int findRepeatNumber(vector<int>& a) { int n = a.size(); for(int i = 0;i < n;i++){ if(a[i] == i){ continue; } if(a[a[i]] == a[i]){ return a[i]; } swap(a[a[i]],a[i]); } return -1; } };
P4 二维数组中的查找
-
题目描述：在一个n*m的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。输入一个二维数组和一个整数，判断数组中是否含有该整数。
-
示例：
[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]给定target = 3，返回true。
-
题解一：
class Solution { public: bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) { if(!matrix.size()){ return false; } int r = 0; int rMax = matrix.size(); int c = matrix[0].size()-1; while(r < rMax && c >= 0){ if(target == matrix[r][c]){ return true; }else if(target < matrix[r][c]){ c--; }else{ r++; } } return false; } };
P5 替换空格
-
解释
请实现一个函数，把字符串s中的每个空格替换成”%20“。
-
示例
输入：s = "We are happy."
输出："We%20are%20happy."
-
题解一（c++字符串不可变）
class Solution { public: string replaceSpace(string s) { int n = s.length(); int count = 0; for(char ch:s){ if(ch == ‘ ‘){ count++; } } s.resize(n+count*2); int tail = s.length()-1; int head = n - 1; while(head >= 0){ if(s[head] != ‘ ‘){ s[tail--] = s[head]; }else{ s[tail--] = ‘0‘; s[tail--] = ‘2‘; s[tail--] = ‘%‘; } head--; } return s; } };
P6 从尾到头打印链表
-
解释
输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
-
示例
输入：head = [1,2,3]
输出：[3,2,1]
-
题解一
class Solution { public: vector<int> reversePrint(ListNode* head) { ListNode* p = head; vector<int> ret; while(p != nullptr){ ret.push_back(p->val); p = p->next; } reverse(ret.begin(),ret.end()); return ret; } }; -
题解二
class Solution { public: vector<int> reversePrint(ListNode* head) { ListNode* p = head; stack<int> ret; vector<int> result; while(p != nullptr){ ret.push(p->val); p = p->next; } while(!ret.empty()){ result.push_back(ret.top()); ret.pop(); } return result; } }; -
题解三
class Solution { public: void dfs(ListNode* head,vector<int>& ret){ if(!head){ return; } dfs(head->next,ret); ret.push_back(head->val); } vector<int> reversePrint(ListNode* head) { vector<int> ret; dfs(head,ret); return ret; } };
P7 重构二叉树
P9 用两个栈实现队列
-
解释
用两个栈实现一个队列。队列的声明如下，请实现它的两个函数appendTail和deleteHead，分别完成在队列尾部插入整数和在队列头部删除整数的功能。（若队列中没有元素，deleteHead操作返回-1）
-
示例
输入：
["CQueue","appendTail","deleteHead","deleteHead"]
[[],[3],[],[]]
输出：[null,null,3,-1] -
题解一
class CQueue { public: stack<int> a,b; CQueue() { while(!a.empty()){ a.pop(); } while(!b.empty()){ b.pop(); } } //1,3 void appendTail(int value) { a.push(value); } int deleteHead() { if(b.empty()){ while(!a.empty()){ b.push(a.top()); a.pop(); } } if(b.empty()){ return -1; } int val = b.top(); b.pop(); return val; } };
P11 旋转数组的最小数字
-
解释
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的一个旋转，输出旋转数组的最小元素。例如，数组[3,4,5,1,2]为[1,2,3,4,5]的一个旋转，该数组的最小值为1。
-
示例
输入：[3,4,5,1,2]
输出：1
-
题解一：空间复杂度为O（1），时间复杂度为O（N）
class Solution { public: int minArray(vector<int>& numbers) { int ret = numbers[0]; for(int num:numbers){ ret = min(ret,num); } return ret; } }; -
题解二：空间复杂度为O（1），时间复杂度为O（logN）
e class Solution { public: int minArray(vector<int>& numbers) { int low = 0; int high = numbers.size()-1; while(low <= high){ int temp = (low+high)/2; if(numbers[temp] < numbers[high]){ high = temp; }else if(numbers[temp] > numbers[high]){ low = temp + 1; }else{ high--; } } return numbers[low]; } };