面试经典150题
合并两个有序数组
两个按非递减顺序排列的整数数组nums1和nums,另有两个整数m和n,分别表示nums1和nums2中的元素数组。
请合并nums2到nums1中,使合并后的数组同样按非递减顺序排列。
直接合并后排序
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
for(int i = 0; i < n; i++){
nums1[m + i] = nums2[i];
}
sort(nums1.begin(), nums1.end());
}
};
双指针
合并后排序没有利用数组nums1与nums已经被排序的性质。
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int sorted[m+n];
int index = 0, i = 0, j = 0;
while(i < m && j < n){
if(nums1[i] <= nums2[j]){
sorted[index++] = nums1[i++];
}else{
sorted[index++] = nums2[j++];
}
}
while(i < m){
sorted[index++] = nums1[i++];
}
while(j < n){
sorted[index++] = nums2[j++];
}
for(i=0; i<m+n; i++){
nums1[i] = sorted[i];
}
}
};
逆向双指针
之所以要使用临时变量,是因为如果直接合并到nums1中,nums1中的元素可能在取出之前被覆盖。
如何直接避免覆盖nums1中的元素呢?
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int index = m + n -1, i = m-1, j = n-1;
while(i >= 0 && j >= 0){
if(nums1[i] >= nums2[j]){
nums1[index--] = nums1[i--];
}else{
nums1[index--] = nums2[j--];
}
}
while(i >= 0){
nums1[index--] = nums1[i--];
}
while(j >= 0){
nums1[index--] = nums2[j--];
}
}
};
移除元素
给一个数组nums和一个值val,需要移除所有数值等于val的元素,并返回不同于val的元素的数量。
双指针
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int left = 0;
int right = 0;
int n = nums.size();
while(right < n){
if(nums[right] != val){
nums[left++] = nums[right];
}
right++;
}
return left;
}
};
双指针优化
如果要移除的元素在数组的开头,例如序列[1,2,3,4,5],当val为1时,我们需要把每一个元素都左移一位。
注意元素顺序可以改变,那么直接将5移动到序列开头。
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int left = 0;
int right = nums.size()-1;
while(left <= right){
if(nums[left] == val){
nums[left] = nums[right];
right--;
}else{
left++;
}
}
return left;
}
};
删除有序数组中的重复项
原地删除重复出现的元素,使每个元素只出现一次。
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int left = 0;
int right = 1;
int n = nums.size();
while(right < n){
if(nums[left] != nums[right]){
left++;
nums[left] = nums[right];
}
right++;
}
return left+1;
}
};
三角形最小路径和
给定一个三角形,找出自顶向下的最小路径和。
class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
int m = triangle.size();
int n = triangle[0].size();
vector<vector<int>> dp(m);
for(int i=0; i<m ;i++){
dp[i] = vector<int>(i+1,0);
}
dp[0][0] = triangle[0][0];
for(int i=1; i<m; i++){
for(int j=0; j<=i; j++){
if(j == 0){
dp[i][j] = dp[i-1][j] + triangle[i][j];
}else if(j == i){
dp[i][j] = dp[i-1][j-1] + triangle[i][j];
}else{
dp[i][j] = min(dp[i-1][j-1], dp[i-1][j])+triangle[i][j];
}
}
}
return *std::min_element(dp[m-1].begin(), dp[m-1].end());
}
};
最大正方形
暴力法
使用dp[i][j]表示以(i,j)为右下角,且只包含1的正方形的边长最大值。如果我们能计算出所有dp[i][j]的值,那么其中的最大值即为矩阵中只包含1的正方形的边长的最大值,其平方就是最大正方形的面积。
对于每个位置(i,j),检查在矩阵中该位置的值:
- 如果该位置的值是0,则dp[i][j]=0,因为当前位置不可能在由1组成的正方形中;
- 如果该位置的值是1,则dp[i][j]的值由其上方,左方和左上方决定。
此外,还需要考虑边界条件,如果i和j中至少有一个为0,则以此位置为右下角的最大正方形的边长只能是1,因此dp[i][j] = 1。
class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
int maxSide = 0;
int rows = matrix.size(), columns = matrix[0].size();
vector<vector<int>> dp(rows, vector<int>(columns));
for(int i=0; i<rows; i++){
for(int j=0; j<columns; j++){
if(matrix[i][j] == '1'){
if(i == 0 || j == 0){
dp[i][j] = 1;
}else{
dp[i][j] = min(min(dp[i-1][j], dp[i-1][j-1]), dp[i][j-1]) + 1;
}
maxSide = max(maxSide, dp[i][j]);
}
}
}
return maxSide * maxSide;
}
};
课程表
这学期必须学numCourses门课程,选修某些课程之前需要一些先修课程。
本题是一道经典的拓扑排序问题。
给定一个包含n个节点的有向图G,我们给出它的节点编号的一种排列,如果满足:
对于图G中的任意一条有向边(u,v),u在排列中都出现在v的签名。那么称该排列是图G的拓扑排序。
深度优先搜索
我们可以将深度优先搜索的流程与拓扑排序的求解联系起来,用一个栈存储所有已经搜索完成的节点。
对于一个节点u,如果它的所有相邻节点都已经搜索完成,那么回溯到u的时候,u本身也会变成一个已经搜索完成的节点。
多数元素
给定一个大小为n的数组nums,返回其中的多数元素。多数元素是指在数组中出现次数大于n/2的元素。
哈希表
使用哈希映射(HashMap)来存储每个元素以及出现的次数。对于哈希映射中的每个键值对,键表示一个元素,值表示该元素出现的次数。
我们用一个循环遍历数组nums,并将数组中的每个元素加入哈希映射中。
同样在遍历数组nums时候使用打擂台的方式,维护最大值,这样就省去了最后对哈希映射的遍历。
相同的树
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
if(p == nullptr && q == nullptr){
return true;
}
if((p == nullptr && q != nullptr) || (p != nullptr && q == nullptr)){
return false;
}
bool leftCheck = isSameTree(p->left, q->left);
bool rightCheck = isSameTree(p->right, q->right);
return leftCheck && rightCheck && (p->val == q->val);
}
};
原文地址:https://blog.csdn.net/Caramel_biscuit/article/details/140199806
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!