3（287） 数组中重复的数字
给定一个包含 $n + 1$ 个整数的数组 $nums$ ，其数字都在 $[1, n]$ 范围内（包括 $1$ 和 $n$），可知至少存在一个重复的整数。
假设 $nums$ 只有 一个重复的整数 ，返回 这个重复的数 。
你设计的解决方案必须 不修改 数组 $nums$ 且只用常量级 $O(1)$ 的额外空间。
示例 1：
输入：nums = [1,3,4,2,2]
输出：2示例 2：
输入：nums = [3,1,3,4,2]
输出：3提示：
- $1 <= n <= 10^5$
- $nums.length == n + 1$
- $1 <= nums[i] <= n$
- $nums$ 中 只有一个整数 出现 两次或多次 ，其余整数均只出现 一次
题解
/* O3*/
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int r=nums[0];
while(nums[r]!=r)
{
swap(nums[0],nums[r]);
r=nums[0];
}
return r;
}
};
/* 287*/
class Solution {
public:
int findDuplicate(vector<int>& nums) {
unordered_map<int, bool> map;
for(int i=0;i<nums.size();i++)
{
if(map[nums[i]])
return nums[i];
map[nums[i]]=true;
}
return 0;
}
};4（240） 二维数组中的查找
在一个 n * m 的二维数组中，每一行都按照从左到右 非递减 的顺序排序，每一列都按照从上到下 非递减 的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
示例:
现有矩阵 matrix 如下：
[
[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 = $5$，返回 $true$。
给定 target = $20$，返回 $false$。
限制：
0 <= n <= 1000
0 <= m <= 1000题解
/*004*/
/*240*/
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int i= matrix.size()-1,j=0;//以左下角为flag
while(i>=0&&j<matrix[0].size())//注意使用matrix[0].size()作为判断
{
if(matrix[i][j]>target)i--;
else if(matrix[i][j]<target)j++;
else return true;
}
return false;
}
};5 替换空格
请实现一个函数，把字符串 $s$ 中的每个空格替换成"%20"。
示例 1：
输入：s = "We are happy."
输出："We%20are%20happy."限制：
0 <= s 的长度 <= 10000题解
class Solution {
public:
string replaceSpace(string s) {
string result;
for(auto &c: s)
{
if(c==' ')
{
result.push_back('%');
result.push_back('2');
result.push_back('0');
}
else
result.push_back(c);
}
return result;
}
};29（54） 顺时针打印矩阵
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。
示例 1：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]示例 2：
输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]限制：
0 <= matrix.length <= 1000 <= matrix[i].length <= 100
题解
/*
* @lc app=leetcode.cn id=54 lang=cpp
*
* [54] 螺旋矩阵
*/
// @lc code=start
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
if(matrix.empty())return {};
vector<int> res;
int left=0;//左边界
int right=matrix[0].size()-1;//右边界
int top=0;//上边界
int bottom=matrix.size()-1;//下边界
while (true)
{
//left->right
for(int i=left;i<=right;i++)
{
res.push_back(matrix[top][i]);
}
if(++top>bottom)break;
//top->botton
for(int i=top;i<=bottom;i++)
{
res.push_back(matrix[i][right]);
}
if(--right<left)break;
//right->left
for(int i=right;i>=left;i--)
{
res.push_back(matrix[bottom][i]);
}
if(--bottom<top)break;
for(int i=bottom;i>=top;i--)
{
res.push_back(matrix[i][left]);
}
if(++left>right)break;
}
return res;
}
};
// @lc code=end
50 字符流中第一个不重复的字符
在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。
示例 1:
输入：s = "abaccdeff"
输出：'b'示例 2:
输入：s = ""
输出：' '限制：
0 <= s 的长度 <= 50000题解
class Solution {
public:
char firstUniqChar(string s) {
if(s=="")return ' ';
unordered_map<char, bool> map;
for(int i=0;i<s.size();i++)
{
map[s[i]]=(map.find(s[i])==map.end());
}
for(int i=0;i<s.size();i++)
{
if(map[s[i]])
return s[i];
}
return ' ';
}
};
