题目描述：在一个长度为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;
}
};
题目描述：在一个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;
}
};
解释
请实现一个函数，把字符串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;
}
};
解释
输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
示例
输入：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;
}
};
解释
用两个栈实现一个队列。队列的声明如下，请实现它的两个函数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;
}
};
解释
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的一个旋转，输出旋转数组的最小元素。例如，数组[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];
}
};
原文：https://www.cnblogs.com/zhailipu/p/15156019.html