零基础的我刷力扣一周后，总结了点东西 |
您所在的位置：网站首页 › 华为刷步数只能一次刷完吗 › 零基础的我刷力扣一周后，总结了点东西 |
零基础的我刷力扣一周后，总结了点东西
|
之前一直想学习数据结构与算法，因为一直听说这个很重要嘛，还有力扣这个网站那也是神交已久啊~~ 但是又不敢接触，因为恐惧嘛，害怕学不会，害怕被吊打~~~~~ 后来遇到了一个大佬，算法大佬，超强的！
我跟他聊了我的情况，他就推荐我开始刷力扣，刷简单的，通过率高的，先培养习惯，兴趣，信心。然后我就开始了！ 小结计划这是我第一篇小结以后每周一会做一篇周结 每月月结，同时删除周结 二、相关知识 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(nlogn)，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 startli[mid]: # 如果目标值比中间值大，就说名目标值（7）在右边的列表 start = mid+1 # 让start变成右边列表的第一个元素的索引 # 抛弃左边的列表不要，只看右边的列表li_right = [6, 7, 8, 9, 10] else: # 如果目标值小于等于中间值，就说明目标值在左边的列表 end = mid # 让n变成左边列表的最大值的索引 # 抛弃右边的列表不要，只看左边的列表 print("mid的值就是目标值的索引：", mid) # 运行结果为6Java代码： 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 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 // 双指针 int end = arr.length-1; int start = 0; while (start public static void main(String[] args) { int sum = Shu(5); System.out.println(sum); } static int Shu(int n){ if (nint: if n“aa”=赋值字符串“a”=“b”=>“b”==判断字符串是否相等“a”==“b”=>false[]通过下标获取字符串中的字符“asd”[0]=>“a”说起字符串，能说的也可以很多，也可以很少 说多了有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)) 三、结语也许我学的慢，但是我始终都在进步！那我总有一天会成功。 |
————英雄哪里出来【本文地址】