两数之和
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
解法
用线性的时间复杂度来解决问题，那么就是说只能遍历一个数字，那么另一个数字呢，我们可以事先将其存储起来，使用一个 HashMap，来建立数字和其坐标位置之间的映射，我们都知道 HashMap 是常数级的查找效率，这样，我们在遍历数组的时候，用 target 减去遍历到的数字，就是另一个需要的数字了，直接在 HashMap 中查找其是否存在即可。
AC代码
public class Solution {public int[] twoSum(int[] nums, int target) {HashMap<Integer, Integer> m = new HashMap<Integer, Integer>();int[] res = new int[2];for (int i = 0; i < nums.length; ++i) {m.put(nums[i], i);}for (int i = 0; i < nums.length; ++i) {int t = target - nums[i];if (m.containsKey(t) && m.get(t) != i) {res[0] = i;res[1] = m.get(t);break;}}return res;}}
三数之和
给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，满足要求的三元组集合为：[[-1, 0, 1],[-1, -1, 2]]
解法
先将数组排序，使用 i，j，k 三个指针。i指向最小的数可能的位置，k 指向最大的数的位置，j 指向中间的数可能的位置。遍历原理核心为每次遍历会遇到得三种情况：
1.nums[i]+nums[j]==-nums[k]，此时说明刚好三数加一起等于 0，于是此时要把j向右拨一位，但此时nums[i]+nums[j] 变大了(nums[j] 变大的情况下)，所以同时也要把k向左拨。也即此时i++，k—;
2.nums[i]+nums[j]>-nums[k]，此时说明 nums[i]+nums[j]+nums[k]>0，所以k要向左拨，k—;
3.nums[i]+nums[j]<-nums[k]，此时说明 nums[i]+nums[j]+nums[k]<0，所以j要向右拨，j++;
当然，遍历的时候肯定会考虑重复等一些的情况，所以要加上邻位判断。比如在遍历第一种情况时，如果nums[j]==nums[j-1]，说明此时 j 已经考虑过了，直接 j++ 即可。
AC代码
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> res;
sort(nums.begin(), nums.end());
if (nums.empty() || nums.back() < 0 || nums.front() > 0) return {};
for (int k = 0; k < nums.size(); ++k) {
if (nums[k] > 0) break;
if (k > 0 && nums[k] == nums[k - 1]) continue;
int target = 0 - nums[k];
int i = k + 1, j = nums.size() - 1;
while (i < j) {
if (nums[i] + nums[j] == target) {
res.push_back({nums[k], nums[i], nums[j]});
while (i < j && nums[i] == nums[i + 1]) ++i;
while (i < j && nums[j] == nums[j - 1]) --j;
++i; --j;
} else if (nums[i] + nums[j] < target) ++i;
else --j;
}
}
return res;
}
};
最近三数之和
Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
Example:
Given array nums = [-1, 2, 1, -4], and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
解法
求最接近给定值的三数之和即我们要保证当前三数和跟给定值之间的差的绝对值最小，所以我们需要定义一个变量 diff 用来记录差的绝对值，然后我们还是要先将数组排个序，然后开始遍历数组，思路跟那道三数之和很相似，都是先确定一个数，然后用两个指针 left 和 right 来滑动寻找另外两个数，每确定两个数，我们求出此三数之和，然后算和给定值的差的绝对值存在 newDiff 中，然后和 diff 比较并更新 diff 和结果 closest 即可，代码如下：
AC代码
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
int closest = nums[0] + nums[1] + nums[2];
int diff = abs(closest - target);
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size() - 2; ++i) {
int left = i + 1, right = nums.size() - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
int newDiff = abs(sum - target);
if (diff > newDiff) {
diff = newDiff;
closest = sum;
}
if (sum < target) ++left;
else --right;
}
}
return closest;
}
};
三数之和较小值
Given an array of n integers nums and a target, find the number of index triplets i, j, k with 0 <= i < j < k < n that satisfy the condition nums[i] + nums[j] + nums[k] < target.
For example, given nums = [-2, 0, 1, 3], and target = 2.
Return 2. Because there are two triplets which sums are less than 2:
[-2, 0, 1]
[-2, 0, 3]
Follow up:
Could you solve it in O(n2) runtime?
解法
让我们求三数之和小于一个目标值，那么最简单的方法就是穷举法，将所有的可能的三个数字的组合都遍历一遍，比较三数之和跟目标值之间的大小，小于的话则结果自增 1。
AC代码
// O(n^2)
class Solution {
public:
int threeSumSmaller(vector<int>& nums, int target) {
if (nums.size() < 3) return 0;
int res = 0, n = nums.size();
sort(nums.begin(), nums.end());
for (int i = 0; i < n - 2; ++i) {
int left = i + 1, right = n - 1;
while (left < right) {
if (nums[i] + nums[left] + nums[right] < target) {
res += right - left;
++left;
} else {
--right;
}
}
}
return res;
}
};
岛屿的最大面积
给定一个包含了一些 0 和 1的非空二维数组 grid , 一个 岛屿 是由四个方向 (水平或垂直) 的 1 (代表土地) 构成的组合。你可以假设二维矩阵的四个边缘都被水包围着。
找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为0。)
示例 1:
[[0,0,1,0,0,0,0,1,0,0,0,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,1,1,0,1,0,0,0,0,0,0,0,0],
[0,1,0,0,1,1,0,0,1,0,1,0,0],
[0,1,0,0,1,1,0,0,1,1,1,0,0],
[0,0,0,0,0,0,0,0,0,0,1,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,0,0,0,0,0,0,1,1,0,0,0,0]]
对于上面这个给定矩阵应返回 6。注意答案不应该是11，因为岛屿只能包含水平或垂直的四个方向的‘1’。
示例 2:
[[0,0,0,0,0,0,0,0]]
对于上面这个给定的矩阵, 返回 0。
注意: 给定的矩阵grid 的长度和宽度都不超过 50。
解法
bfs 或者 dfs 均可，这种就是那种油田问题，但是这个只写函数感觉很难受写的。但是要注意 n==0 的情况，这样算法题一定要注意判断边界。
AC代码
class Solution {
public:
int dfs(vector<vector<int>>& grid,int ii,int j)
{
int n=grid.size();int m=grid[0].size();
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
grid[ii][j]=0;
int sum=1;
for(int i=0;i<4;i++)
{
int x=ii+dx[i];
int y=j+dy[i];
if(x>=0&&x<n&&y>=0&&y<m&&grid[x][y]==1)
sum+=dfs(grid,x,y);
}
return sum;
}
int maxAreaOfIsland(vector<vector<int>>& grid) {
int n=grid.size();int m=grid[0].size();
if(n==0)
return 0;
int ans=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(grid[i][j]==1)
{
ans=max(dfs(grid,i,j),ans);
}
}
}
return ans;
}
};
搜索旋转排序数组
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
你可以假设数组中不存在重复的元素。
你的算法时间复杂度必须是 O(log n) 级别。
示例 1:
输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4
示例 2:
输入: nums = [4,5,6,7,0,1,2], target = 3
输出: -1
解法
二分搜索法的关键在于获得了中间数后，判断下面要搜索左半段还是右半段，多画几个示意图可以发现如果中间的数小于最右边的数，则右半段是有序的，若中间数大于最右边数，则左半段是有序的，我们只要在有序的半段里用首尾两个数组来判断目标值是否在这一区域内，这样就可以确定保留哪半边了。
AC代码
class Solution {
public:
int search(int A[], int n, int target) {
if (n == 0) return -1;
int left = 0, right = n - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (A[mid] == target) return mid;
else if (A[mid] < A[right]) {
if (A[mid] < target && A[right] >= target) left = mid + 1;
else right = mid - 1;
} else {
if (A[left] <= target && A[mid] > target) right = mid - 1;
else left = mid + 1;
}
}
return -1;
}
};
最长连续递增序列
给定一个未经排序的整数数组，找到最长且连续的的递增序列。
示例 1:
输入: [1,3,5,4,7]
输出: 3
解释: 最长连续递增序列是 [1,3,5], 长度为3。
尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为5和7在原数组里被4隔开。
示例 2:
输入: [2,2,2,2,2]
输出: 1
解释: 最长连续递增序列是 [2], 长度为1。
注意：数组长度不会超过10000。
解法
最长连续递增序列是 [1,3,5], 长度为 3。 尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为 5 和 7 在原数组里被 4 隔开。
最长连续递增子序列，解法就直接模拟，从 1-n，要是 a[i]
AC代码
class Solution {
public:
int findLengthOfLCIS(vector<int>& nums) {
int n=nums.size();
if(n==0)
return 0;
int ans=0;
int tempans=1;
for(int i=0;i<n-1;i++)
{
if(nums[i]<nums[i+1])
tempans++;
else
{
if(tempans>ans)
ans=tempans;
tempans=1;
}
}
return max(ans,tempans);
}
};
数组中的第K个最大元素
在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
示例 1:
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4
说明:
你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。
解法
AC代码
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
priority_queue<int,vector<int>,greater<int>>q;
int si=nums.size();
for(int i=0;i<si;i++)
{
q.push(nums[i]);
if(q.size()>k)
q.pop();
}
return q.top();
}
};
最长连续序列
给定一个未排序的整数数组，找出最长连续序列的长度。
要求算法的时间复杂度为 O(n)。
示例:
输入: [100, 4, 200, 1, 3, 2]
输出: 4
解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4
解法
AC代码
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
int si=nums.size();
if(si==0)
return 0;
if(si==1)
return 1;
sort(nums.begin(),nums.end());
nums.erase(unique(nums.begin(),nums.end()),nums.end());
int ans=1,temp=1;
for(int i=1;i<si;i++)
{
while(i<si&&nums[i]==nums[i-1]+1)
{
temp++;
i++;
}
ans=ans<temp?temp:ans;
temp=1;
}
return ans;
}
};
第k个排列
给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。
按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：
- “123”
- “132”
- “213”
- “231”
- “312”
- “321”
给定 n 和 k，返回第 k 个排列。
说明：
给定 n 的范围是 [1, 9]。
给定 k 的范围是[1, n!]。
示例 1:
输入: n = 3, k = 3
输出: "213"
示例 2:
输入: n = 4, k = 9
输出: "2314"
解法
AC代码
class Solution {
public:
string getPermutation(int n, int k) {
string ans;
string num="123456789";
vector<int>f(n, 1);
for (int i = 1; i<n;++i)
f[i]=f[i-1] * i;
--k;
for (int i = n; i >= 1; --i)
{
int j = k / f[i - 1];
k %= f[i - 1];
ans.push_back(num[j]);
num.erase(j, 1);
}
return ans;
}
};
朋友圈
班上有 N 名学生。其中有些人是朋友，有些则不是。他们的友谊具有是传递性。如果已知 A 是 B 的朋友，B 是 C 的朋友，那么我们可以认为 A 也是 C 的朋友。所谓的朋友圈，是指所有朋友的集合。
给定一个 N * N 的矩阵 M，表示班级中学生之间的朋友关系。如果M[i][j] = 1，表示已知第 i 个和 j 个学生互为朋友关系，否则为不知道。你必须输出所有学生中的已知的朋友圈总数。
示例 1:
输入:
[[1,1,0],
[1,1,0],
[0,0,1]]
输出: 2
说明：已知学生0和学生1互为朋友，他们在一个朋友圈。
第2个学生自己在一个朋友圈。所以返回2。
示例 2:
输入:
[[1,1,0],
[1,1,1],
[0,1,1]]
输出: 1
说明：已知学生0和学生1互为朋友，学生1和学生2互为朋友，所以学生0和学生2也是朋友，所以他们三个在一个朋友圈，返回1。
注意：
N 在[1,200]的范围内。
对于所有学生，有M[i][i]= 1。
如果有M[i][j] = 1，则有M[j][i]= 1。
解法
第一反应并查集，但是也可以直接 dfs，维持一个 vis 数组，对于走过的不再遍历，对于未走过的按照给定的 ma[][]进行深度搜索。
AC代码
class Solution {
public:
void dfs(vector<vector<int>>& M,vector<bool>& vis,int i)
{
int n=M.size();
for(int j=0;j<n;j++)
{
if(M[i][j]==1&&!vis[j])
{
vis[j]=true;
dfs(M,vis,j);
}
}
}
int findCircleNum(vector<vector<int>>& M) {
int ans=0;
int n=M.size();
if(n==0)
return 0;
vector<bool>vis(n,false);
for(int i=0;i<n;i++)
{
if(!vis[i])
{
dfs(M,vis,i);
ans++;
}
}
return ans;
}
};
合并区间
给出一个区间的集合，请合并所有重叠的区间。
示例 1:
输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2:
输入: [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。
解法
我们首先想到的做法是先将输入的区间按照第一个元素排序。然后我们建立一个 result 用来存储最后的结果。我们现将第一个区间放入 result 中，然后对于后面输入的区间的 item.start 和 result[-1].end 比，如果 result[-1].end < item.start，我们就将 item 加入到 result，否则话说明要放入的区间和 result[-1] 有重叠，那么我们取result[-1].end = max(result[-1].end, item.end)。
AC代码
/**
* Definition for an interval.
* struct Interval {
* int start;
* int end;
* Interval() : start(0), end(0) {}
* Interval(int s, int e) : start(s), end(e) {}
* };
*/
class Solution {
public:
vector<Interval> merge(vector<Interval>& intervals) {
sort(intervals.begin(),intervals.end(),cmp);
int si=intervals.size();
if(si==1)
return intervals;
vector<Interval>ans;
int i=0;
Interval temp;
while(i<si)
{
int s=intervals[i].start,e=intervals[i].end;
int j=i+1;
while(j<si && intervals[j].start<=e)
{
if(e<intervals[j].end)
e=intervals[j].end;
j++;
}
temp.start=s;temp.end=e;
ans.push_back(temp);
i=j;
}
return ans;
}
static bool cmp(Interval a,Interval b)
{
if(a.start==b.start)
return a.end<b.end;
else
return a.start<b.start;
}
};
接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 感谢 Marcos 贡献此图。
示例:
输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6
解法
找到最高的那个柱子，把数组分成两部分，对于两部分都已经确定了一个边界高度了，所以对剩余的每个柱子至于确定一边的边界高度值，就可以直接计算出能接的雨水了
AC代码
class Solution {
public:
int trap(vector<int>& height) {
int n=height.size();
if(n<=2)
return 0;
int maxx=-1;int id;
for(int i=0;i<n;i++)
{
if(height[i]>maxx)
{
maxx=height[i];
id=i;
}
}
int ans=0;int t=height[0];
for(int i=0;i<id;i++)
{
if(t<height[i])
t=height[i];
else
ans+=(t-height[i]);
}
t=height[n-1];
for(int i=n-1;i>id;i--)
{
if(t<height[i])
t=height[i];
else
ans+=(t-height[i]);
}
return ans;
}
};
若有收获，就点个赞吧
0 人点赞
