零基础的我刷力扣一周后，总结了点东西

柔情只为你懂 2021-09-09 12:54 289阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_Q1NETiBA5biD5bCP56aF_size_37_color_FFFFFF_t_70_g_se_x_16_pic_center]

# 一、前言 #

之前一直想学习数据结构与算法，因为一直听说这个很重要嘛，还有力扣这个网站那也是神交已久啊~~

但是又不敢接触，因为恐惧嘛，害怕学不会，害怕被吊打~~~~~

后来遇到了一个大佬，算法大佬，超强的！

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzUyODgzODk4_size_16_color_FFFFFF_t_70]————[英雄哪里出来][Link 1]

我跟他聊了我的情况，他就推荐我开始刷力扣，刷简单的，通过率高的，先培养习惯，兴趣，信心。然后我就开始了！

## 小结计划 ##

> 这是我第一篇小结  
> 以后每周一会做一篇周结  
> 每月月结，同时删除周结

# 二、相关知识 #

## 1. 时间复杂度O() ##

算法的目的就是为了提高程序的效率，而在优化了程序后，表现最突出的就是程序的运行时间。

那么测试我们的程序是否跑的更快了，难道掐秒计算吗?

举个例子：

**程序优化完后，运行一结束。诶诶，快停，记录时间！！看看快了没!**

**而这个时间，为实际时间，也可以说是绝对时间，但是这个时间能被很多因素影响**

而这个因素就有很多了，硬件，软件，系统等…

所以进引入了相对时间的计时方法，也就是时间复杂度，来判断我们的程序是否得到了优化

规定，一段程序的时间由时间复杂度来表示。

而时间复杂度又分为三种，*最优情况*，*最劣情况*，*平均情况*。而这个情况是由问题来决定的

比如：我们将某个正在军训的班级拉出来一排，一排五个人，让他们从左到右依次报数(从1开始)  
用这个数来代表他们本来的名字，作为代号  
而我们需要找一个叫做张三的人  
  
不过我们不能大声问谁是张三，只能根据代号挨个去问  
如果张三的代号为1，那么我们只需要寻找一次就可以  
如果为3那么我们需要寻找3次  
如果为5或者张三不在这一排，我们就必须查找5次才能得到结果

而这个第一种情况就是最优情况，为O(1)，第三种情况为最劣情况，也就是O(n)

通常使用最劣情况来表示一个程序的最终情况，也就是O()

一个简单的赋值语句，判断语句的时间复杂度为O(1)，而不管你这个语句有多长，只要他是切实能写出来的次数，都是O(1)

循环语句根据循环的次数的变化而分为O(1)，O(N)，上面说过O(1)那么O(n)就是循环的次数随着题目或者问题的改变而改变的，就属于O(n)

而判断整个程序时间复杂度的方法为，以时间复杂度最高的为主：也就是说，就算你赋值了1000000个变量，而循环结果是随时间变化的，那么你的程序的时间复杂度为：O(n)

因为随着循环次数的增加，也就是n->无穷大，你的变量数目，也会相对于n来说越来越小。

所以可以忽略不计，为O(1)\*O(n)==O(n)

常见的时间复杂度：O(1)，O(logn)，O(n)，O(n*logn)，O(n*\**2)，O(2*\*\*n)O(n!)

按照从小到大的顺序排列

## 2. 空间复杂度O() ##

空间复杂度也具有相同的概念，只是有些地方变得不太一样了

如果说时间还能掐秒计算时间，那么占用空间就没那么好计算了，难不成，你去看看代码多少航，行多的占用内存就大吗？这也不是，有的代码很少，但是需要占用的内存多，有的代码看着很多，但是占用内存很小

空间复杂度是想对占用空间，比如说，你的程序创建100个变量接收了100个数字，字符串，在空间复杂度里面属于O(1)，而你创建一个数组，哈希表，栈等就是O(n)

# 三、刷题小结 #

自从开始刷力扣，也有些许日子了，从一开始的每日一题，到每日两题，再到学习学到无聊的时候就去刷题，也算是经历了一番蜕变。

从一开始的什么都不懂，做题全靠暴力破解，但现在掌握了几个方法。

也了解了一些关于数据结构与算法的小知识

学习新知识固然重要，但是也需要总结之前的知识，毕竟温故而知新嘛

## 1. 二分法 ##

二分查找法是一种算法

他经常用在：

> 给定一个升序的数组/列表和一个目标值，尽可能快的查找其中的目标值
> 
> 若存在，返回目标值得索引
> 
> 若不存在，返回-1
> 
> 这样的场景

相比于直接遍历整个数组，使用二分法无疑会让我们的程序效率更高！

因为是**升序**的，所以我们可以**以数组中间的元素为中线**，将数组分为**左右**两个数组

python代码展示：

target = 7  # 给一个目标值
    start = 0  # 用于计算中间值，和后面陆续的将数组划分为两个数组
    end = len(li)-1 # 用于计算中间值，记录列表最后值的索引
    li = [1, 2, 3, 4, 5, 6 ,7, 8, 9, 10]
    while start<end:
        # 记录一个循环
        mid = (start+n)//2  # 值为4
        """ 一个升序数组/列表 以中间mid（//是保持中间值为整数）为界限 看似分成两个数组 li_left = [1， 2， 3 ，4， 5] li_right = [6, 7, 8, 9, 10] """
    	if target>li[mid]:
            # 如果目标值比中间值大，就说名目标值（7）在右边的列表
            start = mid+1 # 让start变成右边列表的第一个元素的索引
            # 抛弃左边的列表不要，只看右边的列表li_right = [6, 7, 8, 9, 10]
        else:
            # 如果目标值小于等于中间值，就说明目标值在左边的列表
            end = mid # 让n变成左边列表的最大值的索引
            # 抛弃右边的列表不要，只看左边的列表
    print("mid的值就是目标值的索引：", mid)
    # 运行结果为6

Java代码：

public class Test{ 
        public static void main(String[] args){ 
            int[] aa = new int[]{ 1, 2, 3, 4, 5, 6 ,7, 8, 9, 10};
            int target = 7;  // 给一个目标值，查找目标值是否在数组中
            int start = 0;  // 用于计算中间值，和后面陆续的将数组划分为两个数组
            int mid = 0;    // 设置中间值遍历
            int end = aa.length; // 用于计算中间值，记录列表最后值的索引
            while(start<end){       // 设置循环条件，当头指针小于尾指针时终止循环
                mid = (start+end)/2;
                /* 一个升序数组/列表 以中间mid（//是保持中间值为整数）为界限 看似分成两个数组 左边是： [1， 2， 3 ，4， 5] 右边是： [6, 7, 8, 9, 10] */
                if (target>aa[mid]) start = mid+1;  // 如果目标值比中间值大，就说名目标值（7）在右边的列表,让start变成右边列表的第一个元素的索引
                else end = mid;   // 如果目标值小于等于中间值，就说明目标值在左边的列表，让end编程左边列表的尾部
            }
            System.out.println("mid的值就是目标值在数组中的索引："+mid);
        }
    }
    
    // 运行结果为6

随着循环的进行，列表会越来越小，最后只剩目标值，然后最小值的索引就是我们需要的值

二分法时间复杂度分析：O(logn) 每次循环使数组长度减半，因此又被称为折半查找法

直接遍历整个数组（暴力解法）时间复杂度分析：O(n)

## 2. 双指针法 ##

在我们的二分法中就是用了双指针的方法，起始时一个指针指向数组的头部，一个指针指向数组的尾部，使用这种方法会让我们对数组的操作更加流畅一些。

双指针法常常是用在：

> 查找某些元素时

力扣的第一道题就是一个经典的双指针优化程序的题目

> 给你一个目标值和一个有序数组
> 
> 找出数组中和为目标值的元素
> 
> 返回她们的下标
> 
> 元素不能与自己相加

正常的做法是进行嵌套循环，挨个查找，这样的时间复杂度为：O(n\*2)

而如果使用双指针的方法，结合二分法就能使时间复杂度降低到：O(logn)

遍历的方法就相当于一个人在找东西，双指针的方法就好像是两个人在找东西

打个例子：

> 我有一块种着10棵树的地
> 
> 有人告诉我，你有一棵树需要浇水了
> 
> 如果只有我自己（正常遍历）
> 
> 并且我不需要跑到树前面观察才能判断我的树是否需要浇水
> 
> 我只能一棵一棵的找，然后判断
> 
> 而如果我有一个助手（双指针）
> 
> 我就可以缩短排查的时间

java：

public class Shuzu { 
        public static void main(String[] args) { 
            int target = 7;
            int[] arr = new int[]{ 1, 2, 3, 4, 5, 6, 7, 8, 9};
            System.out.println(ArrD(7,arr)+"\n"+ArrS(target,arr));
        }
        static int ArrD(int target, int[] arr) { 
            // 单指针
            for (int i = 0; i < arr.length; i++) { 
                if (arr[i] == target) return i;
            }
            return -1;
        }
        static int ArrS(int target, int[] arr){ 
            // 双指针
            int end = arr.length-1;
            int start = 0;
            while (start<end){ 
                if (arr[start]==target) return start;
                if (arr[end]==target) return end;
                start++;
                end--;
            }
            return -1;
        }
    }

py：

def ArrD(target, arr):
        # 单指针
        for i in range(len(arr)):
            if arr[i]target: return i
        return -1;
    def ArrS(target, arr):
        # 双指针
        start = 0
        end = len(arr)-1
        while start<end:
            if arr[start]==target: return start
            if arr[end]==target: return end
            start+=1
            end-=1
        return end
    
    target = 7
    arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    print(ArrD(target, arr), "\n", ArrS(target, arr))

## 3. 递归 ##

递归与其说是一种算法，不如说是一种思想。

它更类似于我们高中数学学过的数列的递推推导式：A(n) = A(n-1)+5 首项为1

让你通过这个式子计算第n项的值的话

你高中会使用它推导出一个通项公式，再将n代入求解

但是再计算机眼里就不用这么麻烦

你只需要每次调用这个公式，然后计算出值就好

在编程语言里就是 ：定义一个函数，调用自身，返回结果就是递归

就相当于计算机帮你从1开始执行了很多遍的A(n) = A(n-1)+5

无限套娃？不不不，他还是有个限度的，没法无限，哈哈哈

比如需要求A(5)，那么就是：

> A(5) = A(4)+5
> 
> A(4) = A(3)+5
> 
> A(3) = A(2)+5
> 
> A(2) = A(1)+5
> 
> A(1) = 3
> 
> A(5) = 3+5+5+5+5=23

代码实现：

java代码：

public class Digui { 
        public static void main(String[] args) { 
            int sum = Shu(5);
            System.out.println(sum);
        }
        static int Shu(int n){ 
            if (n<=1) return 3;
            else return Shu(n-1)+5;
        }
    }

py代码：

def Shu(n:int)->int:
        if n<=1: return 3
        else: return Shu(n-1)+5
    
    print(Shu(5))

最后的计算结果是23

## 4. 数组 ##

什么是数组？数组就是存储多个相同数据的集合，他们的内存地址是相邻的，所以可以通过数组取值。

这么说，是不是有点不好理解，那么这样呢？

我有一颗白菜，手拿着就能回家，那如果是十几颗呢？

我就可以用麻袋！麻袋！装进去，带回家！是的你要存的数据就是白菜，而这个数组就是你要用的麻袋~~~~~

麻袋中的白菜怎么拿出来我需要用的呢？

下标，数组中的下标是以0开始的，什么是下标，就是你从0开始查，查到某个你要的数据，查到几，下标就是几，就相当于，我在装白菜的时候，说“这是第0个白菜，这是第1个白菜…”，而他们也能听懂（别管他们能不能听懂，我说能就能，哈哈~~），等我需要哪一颗白菜的时候，喊一声，他就自己跳出来了

当然我们的数组一般存储的数据比较多，而计算机又不和人一样能够直接看到数组的全部元素，他只记得里面第一颗白菜的样子，所以我们在查找某个元素，但是又不知道他在哪里的时候，只能通过遍历的手段来获取了

遍历每一棵白菜，将他与我们需要找的白菜对比没如果是就不找了，如果不是就继续找。

具体的代码形式我就不多说了，这个都是知道的。

## 5. 字符串 ##

字符串是我们在编程语言里面见到的第一个数据结构 **hello world**

当然，字符串不仅是我们滴各一人士的数据结构，也是我们在生活中用到最多的，比如我们网上聊天，就是字符串，看的小说，是字符串…

而有的字符擦混存储在文件中供计算机读取，然后输出到屏幕上给我们看。

字符串可以看成是一个字符型数组，但是又不尽相同

字符串可以**遍历，查询，拼接**，但是不能**修改**

有的时候拼接用得好也能很大程度上降低我们解决问题的难度

我们可以通过运算符号对字符串进行

<table> 
 <thead> 
  <tr> 
   <th align="center">运算符</th> 
   <th align="center">作用</th> 
   <th align="center">实例</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="center">+</td> 
   <td align="center">拼接字符串</td> 
   <td align="center">“a”+“a”=&gt;“aa”</td> 
  </tr> 
  <tr> 
   <td align="center">=</td> 
   <td align="center">赋值字符串</td> 
   <td align="center">“a”=“b”=&gt;“b”</td> 
  </tr> 
  <tr> 
   <td align="center">==</td> 
   <td align="center">判断字符串是否相等</td> 
   <td align="center">“a”==“b”=&gt;false</td> 
  </tr> 
  <tr> 
   <td align="center">[]</td> 
   <td align="center">通过下标获取字符串中的字符</td> 
   <td align="center">“asd”[0]=&gt;“a”</td> 
  </tr> 
 </tbody> 
</table>

说起字符串，能说的也可以很多，也可以很少

说多了有AI的NLP自然语言处理，K近邻算法，正则表达式…

这里就不多说了，先学会基本操作

## 6. 链表 ##

链表是一种抽象的数据结构，他实际上是一个链表对象，头结点就是这个链表对象，而链表的没一个节点都是一个对象。

链表是一个不定长的线性表数据结构，链表没有内置方法来获取其长度，只能通过遍历来获得里面的内容。

链表实现：

java：

class ListNode{ 
        public int val;     // 存储的值
        public ListNode next;    // 指向下一节点
        public ListNode(int val){    // 构造函数/方法
            this.val = val;
            next = null;
        }
    }

py：

class ListNode:
        def __init__(self,val):  # 构造函数
            self.val = val   # 存储的值
            next = None      # 指向下一节点

是的，链表就是这样实现的。我们一般只能拿到头结点，然后通过判断下一节点是否为空位约束条件来终止循环。

实例：

> 给你个链表\[1, 2, 3, 4, 5\]
> 
> 求链表的长度

java代码：

package com.example.demo;
    
    public class ListNodeStudy { 
        public static void main(String[] args) { 
            ListNode h1 = new ListNode(1);    // 1
            ListNode h2 = new ListNode(2);    // 2
            ListNode h3 = new ListNode(3);    // 3
            ListNode h4 = new ListNode(4);    // 4
            ListNode h5 = new ListNode(5);    // 5
            h1.next = h2;    // 下一节点
            h2.next = h3;    // 下一节点
            h3.next = h4;    // 下一节点
            h4.next = h5;    // 下一节点
            // 题目的链表是这样是实现的，不过不会让你去实现，而是给你h1让你来找长度
            System.out.println(len(h1));
        }
        static int len(ListNode head){ 
            int len = 0;   // 为链表长度定义变量
            while (head!=null){    // 遍历链表获取长度
                len++;
                head = head.next;
            }
            return len;
        }
    }
    class ListNode{ 
        public int val;     // 存储的值
        public ListNode next;    // 指向下一节点
        public ListNode(int val){    // 构造函数/方法
            this.val = val;
            next = null;
        }
    }

py：

class ListNode:
        def __init__(self, val):  # 构造函数
            self.val = val  # 存储的值
            self.next = None  # 指向下一节点
    
    
    h1 = ListNode(1)
    h2 = ListNode(2)
    h3 = ListNode(3)
    h4 = ListNode(4)
    h5 = ListNode(5)
    h1.next = h2
    h2.next = h3
    h3.next = h4
    h4.next = h5
    
    
    def ListNodeLen(head: ListNode) -> int:
        len = 0
        while head != None:
            len += 1
            head = head.next
        return len
    
    
    print(ListNodeLen(h1))

# 三、结语 #

也许我学的慢，但是我始终都在进步！那我总有一天会成功。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_Q1NETiBA5biD5bCP56aF_size_37_color_FFFFFF_t_70_g_se_x_16_pic_center]: /images/20210907/08f3c39dd19c4960bafe478df4c98672.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzUyODgzODk4_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/4e9555ad88dd4d2187c07221cde80fd7.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzUyODgzODk4,size_16,color_FFFFFF,t_70
[Link 1]: /images/20210907/856082dd65c342f5bc0aae9d9c9229ee.png