leetcode学习

leetcode

  • 27 移除元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
数组删除->覆盖元素

# 暴力解法
// 时间复杂度：O(n^2)
// 空间复杂度：O(1)
class Solution {
public:
 int removeElement(vector<int>& nums, int val) {
     int size = nums.size();
     for (int i = 0; i < size; i++) {
         if (nums[i] == val) { // 发现需要移除的元素，就将数组集体向前移动一位
             for (int j = i + 1; j < size; j++) {
                 nums[j - 1] = nums[j];
             }
             i--; // 因为下标i以后的数值都向前移动了一位，所以i也向前移动一位
             size--; // 此时数组的大小-1
         }
     }
     return size;

 }
};
  • 快慢指针

//通过一个快指针和慢指针在一个for循环下完成两个for循环的工作
1.快指针：指向 新数组 的元素，新数组就是不含有目标元素的数组
2.慢指针：指向更新 新数组 下标的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 时间复杂度：O(n)
// 空间复杂度：O(1)
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int slowIndex = 0;
        for (int fastIndex = 0; fastIndex < nums.size(); fastIndex++) {
            if (val != nums[fastIndex]) {
                nums[slowIndex++] = nums[fastIndex];
            }
        }
        return slowIndex;
    }
};

二分查找

  • 条件
    • 有序数组
    • 元素不重复
  • 边界处理
    • 每一次边界处理坚持定义

写法一

第一种写法，我们定义 target 是在一个在左闭右闭的区间里，也就是[left, right] （这个很重要非常重要）。

区间的定义这就决定了二分法的代码应该如何写，因为定义target在[left, right]区间，所以有如下两点：

  • while (left <= right) 要使用 <= ，因为left == right是有意义的，所以使用 <=
  • if (nums[middle] > target) right 要赋值为 middle - 1，因为当前这个nums[middle]一定不是target，那么接下来要查找的左区间结束下标位置就是 middle - 1

在排序数组中查找元素的第一个和最后一个位置

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

进阶：你可以设计并实现时间复杂度为 $O(\log n)$ 的算法解决此问题吗？

示例 1：

  • 输入：nums = [5,7,7,8,8,10], target = 8
  • 输出：[3,4]

示例 2：

  • 输入：nums = [5,7,7,8,8,10], target = 6
  • 输出：[-1,-1]

示例 3：

  • 输入：nums = [], target = 0
  • 输出：[-1,-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/*
与二分查找的区别在于nums[middle]==target时
寻找左边界时，先记录下来，再让right=middle-1继续向左寻找，右边界反之
*/

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int leftboarder=getLeftBoarder(nums,target);
        int rightboarder=getRightBoarder(nums,target);
        return vector<int>{leftboarder,rightboarder};
    }

private:
    int getRightBoarder(vector<int>& nums,int target){
        int left=0,right=nums.size()-1,middle=0,rightboarder=-1;
        while(left<=right){
            middle=left+(right-left)/2;
            if(nums[middle]<target){
                left=middle+1;
            }else if(nums[middle]>target){
                right=middle-1;
            }else{
                rightboarder=middle;
                left=middle+1;
            }
        }
        return rightboarder;
    }

    int getLeftBoarder(vector<int>& nums,int target)
    {
        int left=0,right=nums.size()-1,middle=0,leftboarder=-1;
        while(left<=right){
            middle=left+(right-left)/2;
            if(nums[middle]<target){
                left=middle+1;
            }else if(nums[middle]>target){
                right=middle-1;
            }else{
                leftboarder=middle;
                right=middle-1;
            }
        }
        return leftboarder;
    }
};

哈希表

  • 查找操作需要完成什么任务？
    • 待查值k->确定k在存储结构中的位置
  • 查找技术及其共性
    • 顺序查找、二分查找、二叉排序查找等。都是通过一系列给定值与关键码的比较，查找效依赖于比较次数
  • 不通过比较进行查找？
    • 建立关键码与存储地址的对应关系
  • 散列技术既是一种查找技术，也是存储技术

对于Set，我个人的理解是这样的，Set是叫关联容器，当然了，这个名称太专业（其实我记不住），所以我们只要记住它是集合的意思就行了，既然是集合的话，以前数学我们学到的集合的性质有互异性，也就是不能有重复的元素，还有无序性，这里无序性在这里不是适用的啊，它是默认按照升序（就是从小到大的意思）的排列方式排好的
————————————————
版权声明：本文为CSDN博主「菜到极致就是渣」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/gaoqiandr/article/details/125394052

两数之和

力扣题目链接(opens new window)

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9

所以返回 [0, 1]

  • 当查询一个元素是否出现过或元素是否在集合里时，使用哈希表
  • 需要明确
    • map用来做什么
      • map用来存放访问过的元素，在遍历数组时需要记录遍历过哪些元素及下标，才能找到与当前元素相匹配的
    • map中的key和value分别表示什么
      • 题中需要判断元素是否出现过，所以元素值应该为key，返回的下表为value
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        std::unordered_map<int,int>map;
        for(int i=0;i<nums.size();i++)
        {
            auto iter=map.find(target-nums[i]);
            if(iter!=map.end())
            {
                return{iter->second,i};
            }
            map.insert(pair<int,int>(nums[i],i));
        }
        return {};
    }
};

水果成篮

你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果 种类 。

你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：

  • 你只有 两个 篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
  • 你可以选择任意一棵树开始采摘，你必须从 每棵 树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
  • 一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。

给你一个整数数组 fruits ，返回你可以收集的水果的 最大 数目。

最长和谐字串

和谐数组是指一个数组里元素的最大值和最小值之间的差别 正好是 1 。

现在，给你一个整数数组 nums ，请你在所有可能的子序列中找到最长的和谐子序列的长度。

数组的子序列是一个由数组派生出来的序列，它可以通过删除一些元素或不删除元素、且不改变其余元素的顺序而得到。

示例 1：

1
2
3
输入：nums = [1,3,2,2,5,2,3,7]
输出：5
解释：最长的和谐子序列是 [3,2,2,2,3]
  • count 的使用，map的使用
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int findLHS(vector<int>& nums) {
        unordered_map<int,int>ans;
        int result=0;
        for(int i=0;i<nums.size();i++)
        {
            ans[nums[i]]++;
        }
        for(auto[key,val]:ans)
        {
            if(ans.count(key+1))
            {
                result=max(result,val+ans[key+1]);
            }
        }
        return result;
    }
};

滑动窗口

  • 最长、最短。子串，子序列

–>寻找最长

  • 核心：左右双指针在起始点，R逐位向右滑动循环
    • 如果，窗内元素满足要求，R向右扩大，并更新最优结果
    • 如果，窗内元素不满足条件，L向右缩小窗口
  • R到达结尾

–>寻找最长

  • 核心：左右双指针在起始点，R逐位向右滑动循环
    • 如果，窗内元素满足要求，L向右缩小窗口，并更新最优结果
    • 如果，窗内元素不满足条件，R向右扩大窗口
  • R到达结尾
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
//最长模板
初始化left,right,result,bestresult
while(右指针没有到结尾){
    窗口扩大，加入right对应元素，更新当前result
    while(result不满足要求)
    {
        窗口缩小，移除left对应元素，left右移
    }
	更新最优结果bestresult
    right++；
}
返回bestresult
    
//最短
初始化left,right,result,bestresult
while(右指针没有到结尾){
    窗口扩大，加入right对应元素，更新当前result
    while(result满足要求)
    {
		更新最优结果bestresult
        窗口缩小，移除left对应元素，left右移
    }
    right++；
}
返回bestresult

二叉树

图片

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/*中序遍历*/
void InOrder(BiTree T)
{
	if (T != NULL)
	{
		InOrder(T->lchild);    // 遍历结点左子树
		visit(T);              // 访问结点
		InOrder(T->rchild);    // 遍历结点右子树
	}
}
 
/*输出树结点*/
void visit(BiTree T)
{
	printf("树结点的值：%c\n", T->data);
}

扫一扫，分享到微信

微信分享二维码

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

很惭愧<br><br>只做了一点微小的工作<br>谢谢大家