bigsai

bigsai 查看完整档案

无锡编辑南京理工大学  |  软件工程 编辑  |  填写所在公司/组织 github.com/javasmall 编辑
编辑

公众号:bigsai

专注于Java、数据结构与算法。
欢迎各位叨扰。目前组织力扣打卡群,欢迎加入一起学习!

个人动态

bigsai 发布了文章 · 1月12日

我和蓝桥杯的那两年

前言

有很多事情在最初的时候是令人最难忘的,无论是学习还是生活的点点滴滴,追忆起那些最初的场景,既美好又有点失落,美好是因为那种懵懂而摸索的进步和得知确实很难得,而些许失落是因为一晃都过去那么久啦,那时候的地点、人和事都已很难重温。

前几天翻空间说说发现母校的师弟师妹们都在报名第十二届蓝桥杯大赛,走在寒风飕飕的路上,勾起本科生涯那段寒天与蓝桥杯的故事。记得刚上大一时候不久,老师问班上同学们有什么目标,有几个同学回答了我记得很清楚,一个说想考研,还有说想进BAT,还有一个同学说想参加竞赛拿奖。那是我第一次知道算法竞赛的存在。而我自己本科开始学算法时候不是为了进大厂、为了考研,那时候啥也不懂就是因为要参加蓝桥杯比赛。

我们学校是双非,大部分人要么考研要么搞开发,专注算法的不是很多,更多的还是带着学。我本科学校对蓝桥杯还是挺看重的,并不是个人直接报名,而是参加校赛之后得奖后然后学校统一安排报名,所以第一道坎就是过校赛。

第一次止步校赛

第一次准备比赛的时候,那时候刚上大二,因为在大一基本都是玩过来的,到了大二距离校赛前一段时间。我的舍友W找我问我是要参加蓝桥杯的校赛嘛,我跟他说是的然后他说可以一起准备。因为咱两没有参加协会、也不认识啥这方面有啥天赋的人,所以只能黑灯瞎摸索。开始了第一次蓝桥杯的探寻之旅。

然后那个时候完全是小白从0开始,我们俩从协会群里找到几年历年试题以及一些资料,然后开始研究。我记得很清楚的那时候练习一些啥求素数、进制转换 等等之类的题。那个时候这种题对我们X小白来说已经很有挑战啦。然后后面的编程题更是读不懂不知道怎么做啊,也没测试样例只有题目的一两个样例。但是哪个时候,学会了一个新的东西:回溯算法 。回溯也称为暴力,我和w花了好几天研究回溯算法,刚开始也搞不懂递归,更何况带着逻辑的回溯算法,把回溯算法硬啃之后我两发现:咦,这题好像可以暴力破解哎!当然,虽然用暴力能够求解出一部分问题,但是实质上暴力只能过一部分样例。

当然感觉良好,到参加校赛那天和想象的不太一样,第一次和那么多人一起参加这样比赛,大部分是cpp我用的是Java学校的机器非常老旧,跑个Java程序就会非常卡,遇到那些题突然就慌了,记得很清楚的一道需要用long类型表示的数字我硬是在那边纠结为啥用int表示不出来,那时候编程素养其实还真的很欠火候,天气凉凉,结果校赛也是很遗憾的凉了。当然W舍友也凉了,我们决定寒假和来年要好好准备。

第二次终去北京

在第一次落败第二年的春天,我和W舍友就在杭电上刷题准备下一次的蓝桥杯,从基础到字符串,再到贪心、bfs、dfs以及其他。快到暑假的时候Y同学加入到我们,那时候我们三暑假就会一起刷题讨论题,共同进步。入秋之后我们专业几个报名的还开了一个蓝桥杯校选拔赛互助小队一起准备,那时候快校赛时候发现《将夜Ⅰ》超级好看哈哈在暖暖被窝里熬夜追了一晚,第二天上午还不是很清醒的就去参加比赛了。经过不少时间的准备当然也是容易通过校赛(毕竟我们双非强者有限)。而我们专业也有好多人通过校赛,可以一起省赛一日游,终于能满一个小心愿了,不管怎么样也去体验一波。

在寒假期间我们也做了一些准备,搜集了一些算法资料和视频以及蓝桥杯试题,有个小伙伴还买了历年试题讲解,假期有时我正在被窝里打王者Y同学就偶尔给我来一题强行拖我一下,想想那段无忧无虑的日子还是很美好的。在三月份很幸运的我们专业又是很多人晋级国赛,我们几个晋级的就很期待去北京。

在五月份天气变暖起来,我们一行在J老师的带领下出行去北京,这是我第一次坐高铁去那么远的地方,也是第一次去北京。途径南京、徐州、济南、天津这些大站都拿起手机拍一拍。到了北京在J老师的带领下我们就在北方工业大学考点附近一个酒店。老师允许我们小范围活动我们专业几个人便在附近商场一起吃了顿自助餐,可能是咱们乡下人居多很多人(我)没来过北京走两步拍两下、发个朋友圈,跟家里说我来北京啦!

而第二天比赛时候,也算是被国赛血虐了一把。我参与的那场国赛的难度和竞争力比省赛高了一大截。如果能拿个国一,我觉得还是很厉害的。当初还打算北京转转但由于时间紧,服从安排就老实呆着,不过踏过北京的土地也很满足了又多去过一个大城市!在这里插入图片描述

谈谈蓝桥杯

有些人可能很少参加比赛,所以对蓝桥杯不太了解。

我打蓝桥杯的时候,还有一些打ACM的同学没有参与蓝桥杯,但现在就不同了。这些年随着蓝桥杯大赛的水准和规模慢慢提高,有很多双一流学校的学生参加,也吸引了很多ACMer参与,看到前面拿奖的基本都是好学校,专业顶尖选手越来越多。大赛选手与ACM参赛选手重叠度逐年增加,多届蓝桥杯国赛一等奖、二等奖选手同时是ACM的金牌获得者,可以说蓝桥杯大赛俨然是一块大佬试金石。

讲了这么多,我应该帮你捋一捋介绍一下,搞清自身定位,当然可能有些偏颇仅供参考哈!

蓝桥杯 VS ACM:

属性蓝桥杯ACM
队伍形式个人赛三人团体
赛制OIACM
分组研究生组、A组、B组、C组各学校统一竞争
时长4小时5小时
题目类型填空+编程题编程题
官网dasai.lanqiao.cn

蓝桥杯:

蓝桥杯全国软件和信息技术专业人才大赛是由工业和信息化部人才交流中心举办的全国性IT学科赛事。全国1200余所高校参赛,累计参赛人数超过40万人。2020年,蓝桥杯大赛被列入中国高等教育学会发布的“全国普通高校学科竞赛排行榜”,是高校教育教学改革和创新人才培养的重要竞赛项目。
大赛共包括三个竞赛组别,个人赛-软件类,个人赛-电子类,以及视觉艺术大赛。其中个人赛-软件类的比赛科目包括C/C++程序设计、Java软件开发、Python程序设计。今年第十二届蓝桥杯报名时间是2020年12月-2021年3月,4月省赛,5月国赛。

ACM:

国际大学生程序设计竞赛(英文全称:International Collegiate Programming Contest(简称ICPC))是由国际计算机协会(ACM)主办的,一项旨在展示大学生创新能力、团队精神和在压力下编写程序、分析和解决问题能力的年度竞赛。经过近40年的发展,ACM国际大学生程序设计竞赛已经发展成为全球最具影响力的大学生程序设计竞赛。赛事目前由方正集团赞助。ACM一般区域赛在秋季,各个区域赛时间不同,每个队只能参加同一年两场区域赛。

蓝桥杯是个人赛,个人赛软件类分为:C/C++大学研究生组,C/C++大学A组,C/C++大学B组,C/C++大学C组,Java大学研究生组,Java大学A组,Java大学B组,Java大学C组,Python大学组共9个组别。研究生只能报研究生组。一本院校(985、211)本科生只能报大学A组以上组别。其它本科院校本科生可报大学B组及以上组别。其它高职、高专院校可自行选择报任意组别。每位选手只能申请参加其中一个组别的竞赛。各个组别单独评奖。蓝桥杯的分组竞赛方式,让平时被“学霸”打压的普通学生,也能有获得感,有进步感,给更多学生指引了努力的方向。

在比赛的时候蓝桥杯是OI赛制,也就是提交答案之后赛后评判,根据通过的样例数量给分。这样的赛制,放宽了对于编程速度的要求,对于大部分选手来说更友好一点,可以更从容地解决问题,但也可能有些错误被疏忽不知道已经错了。

而ACM是团体赛,需要三个人协力解答问题,想要拿到好的成绩队友当然也相当关键,各个学校强弱校都统一竞争,头部榜基本被名校和ACM强校霸榜。竞赛是ACM制,也就是当场评测,只能知道通过(通过会升起一个气球看周围气球数就知道其他队A了多少题),或者错误(WA、RE、TLE等),出错需要及时修改答案。只有完全通过才会给分,对算法要求是比较高的。

蓝桥杯适合各个层次的人,特别是给了很多普通本科和高职高专选手接触更多算法编程的机会,有一定的普及性,为广大双非和专科院校的学生提供了更广阔的舞台。现在很多程序比赛,都属于拔高性质。很多初级阶段的计算机相关专业的学生,无法参加这类拔高性质的比赛,但是从数量上看,他们才是未来程序界的主力军,他们应该接触更多的算法知识,提升自身水平。蓝桥杯的试题以算法和数据结构为主,和各种国际国内知名的程序设计比赛相比,其专业水平绝对不输。

ACM(ICPC)个人觉得是更适合一些算法高端玩家,老玩家(高中就打OI)、传统ACM强校(有氛围、能凑齐队友)、高付出的一个比赛,当然也适合对它热爱的同学,当然,这种比赛偏一小部分人,是算法精英级别的一个比赛。当然也有很多努力几年最后也打了个铁(甚至爆零)也没办法,ACM就是个无底洞,它的乐趣在于不停的探索和AC。

当然,我的建议就是有能力、有准备、有氛围、有热爱去冲ACM的,趁着年轻当然冲一冲,拿个牌牌很好(和参加蓝桥杯刚好也不冲突),当然这个期间也要付出非常多的努力。如果准备的比较晚了(大二无算法基础就很难了),就不一定非要去冲ACM,因为在这个高手集群和后浪层出的时代你真的有可能会打个铁,所以要慎重选择。而蓝桥杯感觉是全民皆宜的一个比赛,认可度在算法竞赛类也很高,通过比赛大部分人也能够进步、去证明自己。总的来说ACM是圈内难度较大,普及分布在强校,认可度最高的一个比赛,题型上来看范围也更广、更深。而蓝桥杯则是一个算法普及度很高的比赛,题型上更侧重于经典算法和常用算法(例如贪心、bfs、dfs、dp等,而数论、计算几何等知识考查相比ACM少很多)。蓝桥杯将算法普及和推广、让更多人参与进来,这点目前在国内做的是最好的。

蓝桥杯对我(你)的意义

其实生活和学习需要一定的竞争和认可,通过这样的竞争促进自己的进步,通过得奖或者其他成就增强自己的信心,为下一轮的学习循环做准备。当然这个过程可能并不一定一帆风顺,很可能你会遇到一些挫败和灰心,而蓝桥杯相比ACM就是给了更多人这样的机会(至少我和我身边同学这样)。在同一个舞台,不同人追向不同的目标,根据自己条件和身边氛围去向前迈进。至少我觉得在这方面蓝桥杯是其他赛事无法比拟的。

如果你有ACM的机会,那么和队友刷题的经历一定很难忘,如果没有ACM机会也没关系,可以一起备战蓝桥杯等算法比赛,找几个队友一起准备,讨论互助,让枯燥的东西因为竞争和帮助而变得更加有趣,也希望看到此篇的大佬都能有成,进步的路上一帆风顺!也愿看到此篇的后来人能有所收获。希望你们都能去北京,也希望你们都能拿证书!

最后,附上和本校小学弟部分聊天图,因为从我们这届过后本科学校搬到又大又豪华的新校区,每次遇到母校小学弟都会很温馨的给老学长拍几张新校区图片,实名羡慕啊!

看到这张图,突然就是想起自己那个时候,我曾向一个学长问的问题我跟他说我好好冲蓝桥杯,但事后我凉了就没消息了,第二年才过了校赛和那个学长一起参赛。虽然我不能和小学弟一起参赛了,在这里也希望他以及看到这篇的你们都能有个好的结果!

从室友到队友到专业伙伴,圈子越来越大,从校选拔赛到省赛到国赛,走的越来越远,虽然我花了很久才体验到这段旅程,但依然很满足那段天真的岁月。第十二届蓝桥杯大赛正在报名(报名官网:https://dasai.lanqiao.cn/),也希望你们都能有属于自己的这段岁月,望加油共勉!

原创公众号:bigsai
文章已收录在 全网都在关注的数据结构与算法学习仓库 欢迎star

原创不易,bigsai请思否的朋友们帮两件事帮忙一下:

  1. 一键三连支持一下, 您的肯定是我创作的源源动力。
  2. 微信搜索「bigsai」,关注我,2021一起加油!

咱们下次再见!

查看原文

赞 1 收藏 0 评论 0

bigsai 发布了文章 · 1月6日

【五大常用算法】一文搞懂分治算法

前言

分治算法(divide and conquer)是五大常用算法(分治算法、动态规划算法、贪心算法、回溯法、分治界限法)之一,很多人在平时学习中可能只是知道分治算法,但是可能并没有系统的学习分治算法,本篇就带你较为全面的去认识和了解分治算法。

在学习分治算法之前,问你一个问题,相信大家小时候都有存钱罐的经历,父母亲人如果给钱都会往自己的宝藏中存钱,我们每隔一段时间都会清点清点钱。但是一堆钱让你处理起来你可能觉得很复杂,因为数据相对于大脑有点庞大了,并且很容易算错,你可能会将它先分成几个小份算,然后再叠加起来计算总和就获得这堆钱的总数了

image-20201130124009617

当然如果你觉得各个部分钱数量还是太大,你依然可以进行划分然后合并,我们之所以这么多是因为:

  • 计算每个小堆钱的方式和计算最大堆钱的方式是相同的(区别在于体量上)
  • 然后大堆钱总和其实就是小堆钱结果之和。这样其实就有一种分治的思想。

当然这些钱都是想出来的……

BACDB95DF648E67CF0576A009697EBD2

分治算法介绍

分治算法是用了分治思想的一种算法,什么是分治

分治,字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。在计算机科学中,分治法就是运用分治思想的一种很重要的算法。分治法是很多高效算法的基础,如排序算法(快速排序,归并排序),傅立叶变换(快速傅立叶变换)等等。

将父问题分解为子问题同等方式求解,这和递归的概念很吻合,所以在分治算法通常以递归的方式实现(当然也有非递归的实现方式)。分治算法的描述从字面上也很容易理解,分、治其实还有个合并的过程:

  • 分(Divide):递归解决较小的问题(到终止层或者可以解决的时候停下)
  • 治(Conquer):递归求解,如果问题够小直接求解。
  • 合并(Combine):将子问题的解构建父类问题

一般分治算法在正文中分解为两个即以上的递归调用,并且子类问题一般是不想交的(互不影响)。当求解一个问题规模很大很难直接求解,但是规模较小的时候问题很容易求解并且这个问题并且问题满足分治算法的适用条件,那么就可以使用分治算法。

image-20201130165303362

那么采用分治算法解决的问题需要 满足那些条件(特征) 呢?

1 . 原问题规模通常比较大,不易直接解决,但问题缩小到一定程度就能较容易的解决。

2 . 问题可以分解为若干规模较小、求解方式相同(似)的子问题。且子问题之间求解是独立的互不影响。

3 . 合并问题分解的子问题可以得到问题的解。

你可能会疑惑分治算法和递归有什么关系?其实分治重要的是一种思想,注重的是问题分、治、合并的过程。而递归是一种方式(工具),这种方式通过方法自己调用自己形成一个来回的过程,而分治可能就是利用了多次这样的来回过程。

分治算法经典问题

对于分治算法的经典问题,重要的是其思想,因为我们大部分借助递归去实现,所以在代码实现上大部分都是很简单,而本篇也重在讲述思想。

分治算法的经典问题,个人将它分成两大类:子问题完全独立和子问题不完全独立。

1 . 子问题完全独立就是原问题的答案可完全由子问题的结果推出。

2 . 子问题不完全独立,有些区间类的问题或者跨区间问题使用分治可能结果跨区间,在考虑问题的时候需要仔细借鉴下。

二分搜索

二分搜索是分治的一个实例,只不过二分搜索有着自己的特殊性

  • 序列有序
  • 结果为一个值

正常二分将一个完整的区间分成两个区间,两个区间本应单独找值然后确认结果,但是通过有序的区间可以直接确定结果在那个区间,所以分的两个区间只需要计算其中一个区间,然后继续进行一直到结束。实现方式有递归和非递归,但是非递归用的更多一些:

public int searchInsert(int[] nums, int target) {
  if(nums[0]>=target)return 0;//剪枝
  if(nums[nums.length-1]==target)return nums.length-1;//剪枝
  if(nums[nums.length-1]<target)return nums.length;
  int left=0,right=nums.length-1;
  while (left<right) {
    int mid=(left+right)/2;
    if(nums[mid]==target)
      return mid;
    else if (nums[mid]>target) {
      right=mid;
    }
    else {
      left=mid+1;
    }
  }
  return left;
}

快速排序

快排也是分治的一个实例,快排每一趟会选定一个数,将比这个数小的放左面,比这个数大的放右面,然后递归分治求解两个子区间,当然快排因为在分的时候就做了很多工作,当全部分到最底层的时候这个序列的值就是排序完的值。这是一种分而治之的体现。

image-20201120133851275

public void quicksort(int [] a,int left,int right)
{
  int low=left;
  int high=right;
  //下面两句的顺序一定不能混,否则会产生数组越界!!!very important!!!
  if(low>high)//作为判断是否截止条件
    return;
  int k=a[low];//额外空间k,取最左侧的一个作为衡量,最后要求左侧都比它小,右侧都比它大。
  while(low<high)//这一轮要求把左侧小于a[low],右侧大于a[low]。
  {
    while(low<high&&a[high]>=k)//右侧找到第一个小于k的停止
    {
      high--;
    }
    //这样就找到第一个比它小的了
    a[low]=a[high];//放到low位置
    while(low<high&&a[low]<=k)//在low往右找到第一个大于k的,放到右侧a[high]位置
    {
      low++;
    }
    a[high]=a[low];            
  }
  a[low]=k;//赋值然后左右递归分治求之
  quicksort(a, left, low-1);
  quicksort(a, low+1, right);        
}

归并排序(逆序数)

快排在分的时候做了很多工作,而归并就是相反,归并在分的时候按照数量均匀分,而合并时候已经是两两有序的进行合并的,因为两个有序序列O(n)级别的复杂度即可得到需要的结果。而逆序数在归并排序基础上变形同样也是分治思想求解。

image-20201120173153449

private static void mergesort(int[] array, int left, int right) {
  int mid=(left+right)/2;
  if(left<right)
  {
    mergesort(array, left, mid);
    mergesort(array, mid+1, right);
    merge(array, left,mid, right);
  }
}

private static void merge(int[] array, int l, int mid, int r) {
  int lindex=l;int rindex=mid+1;
  int team[]=new int[r-l+1];
  int teamindex=0;
  while (lindex<=mid&&rindex<=r) {//先左右比较合并
    if(array[lindex]<=array[rindex])
    {
      team[teamindex++]=array[lindex++];
    }
    else {                
      team[teamindex++]=array[rindex++];
    }
  }
  while(lindex<=mid)//当一个越界后剩余按序列添加即可
  {
    team[teamindex++]=array[lindex++];

  }
  while(rindex<=r)
  {
    team[teamindex++]=array[rindex++];
  }    
  for(int i=0;i<teamindex;i++)
  {
    array[l+i]=team[i];
  }
}

最大子序列和

最大子序列和的问题我们可以使用动态规划的解法,但是也可以使用分治算法来解决问题,但是最大子序列和在合并的时候并不是简单的合并,因为子序列和涉及到一个长度的问题,所以正确结果不一定全在最左侧或者最右侧,而可能出现结果的区域为:

  • 完全在中间的左侧
  • 完全在中间的右侧
  • 包含中间左右两个节点的一个序列

用一张图可以表示为:

在这里插入图片描述

所以在具体考虑的时候需要将无法递归得到结果的中间那个最大值串的结果也算出来参与左侧、右侧值得比较。

力扣53. 最大子序和在实现的代码为:

public int maxSubArray(int[] nums) {
    int max=maxsub(nums,0,nums.length-1);
    return max;
}
int maxsub(int nums[],int left,int right)
{
    if(left==right)
        return  nums[left];
    int mid=(left+right)/2;
    int leftmax=maxsub(nums,left,mid);//左侧最大
    int rightmax=maxsub(nums,mid+1,right);//右侧最大

    int midleft=nums[mid];//中间往左
    int midright=nums[mid+1];//中间往右
    int team=0;
    for(int i=mid;i>=left;i--)
    {
        team+=nums[i];
        if(team>midleft)
            midleft=team;
    }
    team=0;
    for(int i=mid+1;i<=right;i++)
    {
        team+=nums[i];
        if(team>midright)
            midright=team;
    }
    int max=midleft+midright;//中间的最大值
    if(max<leftmax)
        max=leftmax;
    if(max<rightmax)
        max=rightmax;
    return  max;
}

最近点对

最近点对是一个分治非常成功的运用之一。在二维坐标轴上有若干个点坐标,让你求出最近的两个点的距离,如果让你直接求那么枚举暴力是个非常非常大的计算量,我们通常采用分治的方法来优化这种问题。

image-20201130204401673

如果直接分成两部分分治计算你肯定会发现如果最短的如果一个在左一个在右会出现问题。我们可以优化一下。

在具体的优化方案上,按照x或者y的维度进行考虑,将数据分成两个区域,先分别计算(按照同方法)左右区域内最短的点对。然后根据这个两个中较短的距离向左和向右覆盖,计算被覆盖的左右点之间的距离,找到最小那个距离与当前最短距离比较即可。

image-20201130205950625

这样你就可以发现就这个一次的操作(不考虑子情况),左侧红点就避免和右侧大部分红点进行距离计算(O(n2)的时间复杂度)。事实上,在进行左右区间内部计算的时候,它其实也这样递归的进行很多次分治计算。如图所示:

image-20201130210925059

这样下去就可以节省很多次的计算量。

但是这种分治会存在一种问题就是二维坐标可能点都聚集某个方法某条轴那么可能效果并不明显(点都在x=2附近对x分割作用就不大),需要注意一下。

杭电1007推荐给大家,ac的代码为:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
public class Main {
    static int n;
    public static void main(String[] args) throws IOException {
        StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        //List<node>list=new ArrayList();
         while(in.nextToken()!=StreamTokenizer.TT_EOF)
         {
             n=(int)in.nval;if(n==0) {break;}
            node no[]=new node[n];
            
             for(int i=0;i<n;i++)
             {
                 in.nextToken();double x=in.nval;
                 in.nextToken();double y=in.nval;
                // list.add(new node(x,y));
                 no[i]=new node(x,y);
             }
             Arrays.sort(no, com);
            double min= search(no,0,n-1);
            out.println(String.format("%.2f", Math.sqrt(min)/2));out.flush();
         }         
    }
    private static double search(node[] no, int left,int right) {
        int mid=(right+left)/2;
        double minleng=0;
        if(left==right) {return Double.MAX_VALUE;}
        else if(left+1==right) {minleng= (no[left].x-no[right].x)*(no[left].x-no[right].x)+(no[left].y-no[right].y)*(no[left].y-no[right].y);}
        else minleng= min(search(no,left,mid),search(no,mid,right));
        int ll=mid;int rr=mid+1;
        while(no[mid].y-no[ll].y<=Math.sqrt(minleng)/2&&ll-1>=left) {ll--;}
        while(no[rr].y-no[mid].y<=Math.sqrt(minleng)/2&&rr+1<=right) {rr++;}
        for(int i=ll;i<rr;i++)
        {
            for(int j=i+1;j<rr+1;j++)
            {
                double team=0;
                if(Math.abs((no[i].x-no[j].x)*(no[i].x-no[j].x))>minleng) {continue;}
                else
                { 
                    team=(no[i].x-no[j].x)*(no[i].x-no[j].x)+(no[i].y-no[j].y)*(no[i].y-no[j].y);
                    if(team<minleng)minleng=team;
                }
            }
        }
        return minleng;
    
    }
    private static double min(double a, double b) {
        // TODO 自动生成的方法存根
        return a<b?a:b;
    }
    static Comparator<node>com=new Comparator<node>() {

        @Override
        public int compare(node a1, node a2) {
            // TODO 自动生成的方法存根
            return a1.y-a2.y>0?1:-1;
        }};
    static class node
    {
        double x;
        double y;
        public node(double x,double y)
        {
            this.x=x;
            this.y=y;
        }
    }
}

结语

到这里,分治算法就讲这么多了,因为分治算法重要在于理解其思想,还有一些典型的分治算法解决的问题,例如大整数乘法、Strassen矩阵乘法、棋盘覆盖、线性时间选择、循环赛日程表、汉诺塔等问题你可以自己研究其分治的思想和原理。

原创公众号:bigsai
文章收录在 bigsai-algorithm

原创不易,bigsai请你帮两件事帮忙一下:

  1. 点赞在看, 您的肯定是我在思否创作的源源动力。
  2. 微信搜索「bigsai」,新人求关注~
查看原文

赞 5 收藏 3 评论 0

bigsai 发布了文章 · 2020-12-29

IVX开发—0代码实现一个九宫格抽奖

原创公众号:bigsai

前言

上次说过在看一些关于0代码开发平台ivx,前一段时间忙完考试最近跟着教程0代码实现一个九宫格抽奖,哈哈哈感觉还是蛮强大的,懂点的人都知道可视化这个东西我们正常都是用一些包或者库来实现数据可视化。而可视化编程我们可能还停留在Dreamweaver和安卓xml编程上。如果写过GUI或者之类就知道任何一个可视化操作的任务量是非常巨大的,所以内心还是很钦佩出这么一个东西。并且这个可视化不错的(上手需要一点时间)。

对于九宫格抽奖问题,要清楚并不是真正的前端界面去抽奖,而是后端生成一个数据前端九宫格根据这个数据去跑成一个这么结果的效果。下面就把个人实现的一个抽奖小程序实现过程记录一下,大家也可以尝试一下,因为不涉及代码可能截图更多。当然,由于这部分如果完整实现设计的内容太多可能使读者失去兴趣,我将一些简单的步骤先截图描述大家可以跟着做,后面更完善的功能可以看这个教学视频

试了一下可能刚开始了解稍微复杂一点各个按钮不熟悉,跟着教程一步步来慢慢会熟悉一点。后续也可能会使用ivx平台实现一些后台管理或者一些简单的小程序。当然,这只是一次破冰试验,到底怎么样还要等以后在看!

九宫格背景制作

首先登录ivx平台,进入控制台,新建一个WebApp、小程序。
image-20201227193413150

创建完毕之后在前台创建一个页面(点击一下页面图标即可),然后在右侧可以双击改名为抽奖页。
image-20201227202126328

由于九宫格抽奖效果在画布上的效果更好,可以点击抽奖页,然后在左侧拓展组件中(下滑)找到画布,点击然后在中间画一个差不多大小的矩形。
image-20201227202608750

然后点击画布,设置一个背景颜色更醒目一点。当然,为了美观你也可以将画布的宽高x,y设置一下。
image-20201227202758787

接着可以在画布中添加一个九宫格的背景图(需要提前制作)。点击画布然后在组件列表选择图片,画一个框加入之前准备好的图片,调整大小坐标使其大概覆盖画布。
image-20201227210257955

这样背景就搞好啦,下面需要添加一些动作能让他跑起来!

九宫格跑马灯效果制作

如何实现一个 的效果呢?

跑的效果其实是一个九宫格其中之一大小格子旋转移动的效果,所以事先思路也是先添加对应矩形,然后对矩形添加移动事件即可。

我们首先在画布下添加一个矩形,后将矩形坐标大小可以调(这里为了演示就不搞那么精准啦)。
image-20201227234354811

然后点击矩形,将背景颜色清空,然后适当修改矩形边框的大小。这样,初始位置的矩形就设置好了,下面就需要添加一些轨迹动作。

接下来在画布下添加一个时间轴,然后将我们刚刚跳动的矩形放到时间轴内(右侧对象树可直接拖动)。
image-20201228181625658
然后点击右侧对象树的矩形,在左侧的事件中添加轨迹 。然后点击右侧对象树的时间轴将事件设置成8的整数倍数(因为这里要跳动8下),方便设置每个跳动时间。点击右侧对象树的轨迹,将轨迹类别设为逐帧 (因为九宫格抽奖都是跳的而不是连续的),然后在时间轴上添加帧点。
image-20201228192800380
关键帧设置完毕之后,我们需要在每个关键帧确定方块移动到达的位置。按照顺时针的顺序在每个关键帧将矩形移动到应该展示的位置。可设置对应时刻具体的x和y。
image-20201228193658014
这样设置完毕之后,点击启动,是可以启动的,但是跑起来的速度太慢了,我们需要加大倍速,点击时间轴设置循环播放然后将播放倍数扩大到20倍,点击开始这个动画就能跑起来了!
image-20201228201511355

确定停止时间

在上面我们详细讲解了如何让马灯跑起来,现在就需要再优化一下界面,并且使它能够停下来。我们首先优化一下抽奖页面,在画布上添加一些文本到各个方格中,点击画布,然后在左侧拓展组件选择文本,赋值谢谢惠顾、各种奖项可以自己设置。当然字体颜色也可自己随意改动啊。
image-20201228205917047
页面做好之后可以准备考虑启动事件,我们可以通过按钮这个启动项让页面动起来,触发一系列抽奖逻辑,点击右侧对象树的抽奖页,在左侧拓展组件选择按钮,大小差不多覆盖网格最中间的部分,然后在对象树点击这个按钮,再点击右侧最上的事件,将按钮触发一个点击事件,点击与事件轴关联播放、暂停。
image-20201228211231312
这样预览的时候点击按钮就可以跑起来了,但是我们怎么让它在某个时刻停下来呢?这里就需要时间轴的好帮手—时间标记。我们可以在时间轴下添加一个时间标记,可以在任意一个时刻停下来。在这里我就让它停在三等奖的时间范围内,并且将这个时间标记改名为三等奖。同时将左侧默认的暂停点取消。
image-20201228213249027
然后我们需要在按钮上继续添加关联,点击按钮的关联事件,然后新添时间轴关联,事件选择播放某段时间段,结束时间就选择对象树种咱们刚刚选择的记录点(三等奖),播放方向为正向。
image-20201228212824437
这样完成之后编译点击抽奖会发现跑马灯能跑起来了!但是这个跑马灯只能跑一圈到三等奖就停下来了,我们怎样才能让它多跑几圈,实现一个真正跑马灯抽奖的效果呢?答案也很简单,我们依旧借助时间标记,我们在时间轴下再添加一个时间标记,并且将其暂停点也关掉、出发方向也改为正向,同时将它命名为记录点 (将它时间挪到1-2s之间)。后面的事情就让这个记录点来帮我们完成。
image-20201228214131461
然后我们准备给这个记录点添加一个事件之前,在画布下添加一个数值变量圈数。然后点击记录点再点击事件,可以选择事件播放到标记 。关联的对象就是圈数让每经过这个点圈数+1。
image-20201228220446396
同时还要将播放按钮的事件播放到某时间段先注释掉,让它可以跑下去。我们将注释的这个部分复制下来,添加到记录点的条件中,这个条件就是停止的条件,我们让圈数为6的时候执行前面停下来的动作
image-20201228221334415
这样编译运行就能在我们想要的三等奖下停下来啦! 今天先分享到这里,大家也可以一起研究一下!

查看原文

赞 1 收藏 1 评论 0

bigsai 发布了文章 · 2020-12-28

跳表 | 会跳的链表真的非常diao

原创公众号「bigsai
文章已收录在 我的Github bigsai-algorithm

前言

跳表是面试常问的一种数据结构,它在很多中间件和语言中得到应用,我们熟知的就有Redis跳表。并且在面试的很多场景可能会问到,偶尔还会让你手写试一试(跳表可能会让手写,红黑树是不可能的),这不,给大伙复原一个场景:

image-20201225113330615

但你别慌,遇到蘑菇头这种面试官也别怕,因为你看到这篇文章了(得意😏),不用像熊猫那样窘迫。

对于一个数据结构或算法,人群数量从听过名称、了解基本原理、清楚执行流程、能够手写 呈抖降的趋势。因为很多数据结构与算法其核心原理可能简单,但清楚其执行流程就需要动脑子去思考想明白,但是如果能够把它写出来,那就要自己一步步去设计和实现。可能要花很久才能真正写出来,并且还可能要查阅大量的资料。

而本文在前面进行介绍跳表,后面部分详细介绍跳表的设计和实现,搞懂跳表,这一篇真的就够了。

快速了解跳表

跳跃表(简称跳表)由美国计算机科学家William Pugh发明于1989年。他在论文《Skip lists: a probabilistic alternative to balanced trees》中详细介绍了跳表的数据结构和插入删除等操作。

跳表(SkipList,全称跳跃表)是用于有序元素序列快速搜索查找的一个数据结构,跳表是一个随机化的数据结构,实质就是一种可以进行二分查找的有序链表。跳表在原有的有序链表上面增加了多级索引,通过索引来实现快速查找。跳表不仅能提高搜索性能,同时也可以提高插入和删除操作的性能。它在性能上和红黑树,AVL树不相上下,但是跳表的原理非常简单,实现也比红黑树简单很多。

在这里你可以看到一些关键词:链表(有序链表)、索引、二分查找。想必你的脑海中已经有了一个初略的印象,不过你可能还是不清楚这个"会跳的链表"有多diao,甚至还可能会产生一点疑虑:跟随机化有什么关系?你在下文中很快就能得到答案!

回顾链表,我们知道链表和顺序表(数组)通常都是相爱相杀,成对出现,各有优劣。而链表的优势就是更高效的插入、删除。痛点就是查询很慢很慢!每次查询都是一种O(n)复杂度的操作,链表估计自己都气的想哭了😢。

image-20201224155243423

这是一个带头结点的链表(头结点相当于一个固定的入口,不存储有意义的值),每次查找都需要一个个枚举,相当的慢,我们能不能稍微优化一下,让它稍微跳一跳呢?答案是可以的,我们知道很多算法和数据结构以空间换时间,我们在上面加一层索引,让部分节点在上层能够直接定位到,这样链表的查询时间近乎减少一半,链表自己虽然没有开心起来,但收起了它想哭的脸。

image-20201224160740034

这样,在查询某个节点的时候,首先会从上一层快速定位节点所在的一个范围,如果找到具体范围向下然后查找代价很小,当然在表的结构设计上会增加一个向下的索引(指针)用来查找确定底层节点。平均查找速度平均为O(n/2)。但是当节点数量很大的时候,它依旧很慢很慢。我们都知道二分查找是每次都能折半的去压缩查找范围,要是有序链表也能这么跳起来那就太完美了。没错跳表就能让链表拥有近乎的接近二分查找的效率的一种数据结构,其原理依然是给上面加若干层索引,优化查找速度。

image-20201224175922421

通过上图你可以看到,通过这样的一个数据结构对有序链表进行查找都能近乎二分的性能。就是在上面维护那么多层的索引,首先在最高级索引上查找最后一个小于当前查找元素的位置,然后再跳到次高级索引继续查找,直到跳到最底层为止,这时候以及十分接近要查找的元素的位置了(如果查找元素存在的话)。由于根据索引可以一次跳过多个元素,所以跳查找的查找速度也就变快了。

对于理想的跳表,每向上一层索引节点数量都是下一层的1/2.那么如果n个节点增加的节点数量(1/2+1/4+…)<n。并且层数较低,对查找效果影响不大。但是对于这么一个结构,你可能会疑惑,这样完美的结构真的存在吗?大概率不存在的,因为作为一个链表,少不了增删该查的一些操作。而删除和插入可能会改变整个结构,所以上面的这些都是理想的结构,在插入的时候是否添加上层索引是个概率问题(1/2的概率),在后面会具体讲解。

跳表的增删改查

上面稍微了解了跳表是个啥,那么在这里就给大家谈谈跳表的增删改查过程。在实现本跳表的过程为了便于操作,我们将跳表的头结点(head)的key设为int的最小值(一定满足左小右大方便比较)。

对于每个节点的设置,设置成SkipNode类,为了防止初学者将next向下还是向右搞混,直接设置right,down两个指针。

class SkipNode<T>
{
    int key;
    T value;
    SkipNode right,down;//右下个方向的指针
    public SkipNode (int key,T value) {
        this.key=key;
        this.value=value;
    }
}

跳表的结构和初始化也很重要,其主要参数和初始化方法为:

public class SkipList <T> {
    
    SkipNode headNode;//头节点,入口
    int highLevel;//当前跳表索引层数
    Random random;// 用于投掷硬币
    final int MAX_LEVEL = 32;//最大的层

    SkipList(){
        random=new Random();
        headNode=new SkipNode(Integer.MIN_VALUE,null);
        highLevel=0;
    }
    //其他方法
}

查询操作

很多时候链表也可能这样相连仅仅是某个元素或者key作为有序的标准。所以有可能链表内部存在一些value。不过修改和查询其实都是一个操作,找到关键数字(key)。并且查找的流程也很简单,设置一个临时节点team=head。当team不为null其流程大致如下:

(1) 从team节点出发,如果当前节点的key与查询的key相等,那么返回当前节点(如果是修改操作那么一直向下进行修改值即可)。

(2) 如果key不相等,且右侧为null,那么证明只能向下(结果可能出现在下右方向),此时team=team.down

(3) 如果key不相等,且右侧不为null,且右侧节点key小于待查询的key。那么说明同级还可向右,此时team=team.right

(4)(否则的情况)如果key不相等,且右侧不为null,且右侧节点key大于待查询的key 。那么说明如果有结果的话就在这个索引和下个索引之间,此时team=team.down。

最终将按照这个步骤返回正确的节点或者null(说明没查到)。

image-20201224210130178

例如上图查询12节点,首先第一步从head出发发现右侧不为空,且7<12,向右;第二步右侧为null向下;第三步节点7的右侧10<12继续向右;第四步10右侧为null向下;第五步右侧12小于等于向右。第六步起始发现相等返回节点结束。

而这块的代码也非常容易:

public SkipNode search(int key) {
    SkipNode team=headNode;
    while (team!=null) {
        if(team.key==key)
        {
            return  team;
        }
        else if(team.right==null)//右侧没有了,只能下降
        {
            team=team.down;
        }
        else if(team.right.key>key)//需要下降去寻找
        {
            team=team.down;
        }
        else //右侧比较小向右
        {
            team=team.right;
        }
    }
    return null;
}

删除操作

删除操作比起查询稍微复杂一丢丢,但是比插入简单。删除需要改变链表结构所以需要处理好节点之间的联系。对于删除操作你需要谨记以下几点:

(1)删除当前节点和这个节点的前后节点都有关系

(2)删除当前层节点之后,下一层该key的节点也要删除,一直删除到最底层

根据这两点分析一下:如果找到当前节点了,它的前面一个节点怎么查找呢?这个总不能在遍历一遍吧!有的使用四个方向的指针(上下左右)用来找到左侧节点。是可以的,但是这里可以特殊处理一下 ,不直接判断和操作节点,先找到待删除节点的左侧节点。通过这个节点即可完成删除,然后这个节点直接向下去找下一层待删除的左侧节点。设置一个临时节点team=head,当team不为null具体循环流程为:

(1)如果team右侧为null,那么team=team.down(之所以敢直接这么判断是因为左侧有头结点在左侧,不用担心特殊情况)

(2)如果team右侧不 为null,并且右侧的key等于待删除的key,那么先删除节点,再team向下team=team.down为了删除下层节点。

(3)如果team右侧不 为null,并且右侧key小于待删除的key,那么team向右team=team.right。

(4)如果team右侧不 为null,并且右侧key大于待删除的key,那么team向下team=team.down,在下层继续查找删除节点。

image-20201225002518856

例如上图删除10节点,首先team=head从team出发,7<10向右(team=team.right后面省略);第二步右侧为null只能向下;第三部右侧为10在当前层删除10节点然后向下继续查找下一层10节点;第四步8<10向右;第五步右侧为10删除该节点并且team向下。team为null说明删除完毕退出循环。

删除操作实现的代码如下:

public void delete(int key)//删除不需要考虑层数
{
    SkipNode team=headNode;
    while (team!=null) {
        if (team.right == null) {//右侧没有了,说明这一层找到,没有只能下降
            team=team.down;
        }
        else if(team.right.key==key)//找到节点,右侧即为待删除节点
        {
            team.right=team.right.right;//删除右侧节点
            team=team.down;//向下继续查找删除
        }
        else if(team.right.key>key)//右侧已经不可能了,向下
        {
            team=team.down;
        }
        else { //节点还在右侧
            team=team.right;
        }
    }
}

插入操作

插入操作在实现起来是最麻烦的,需要的考虑的东西最多。回顾查询,不需要动索引;回顾删除,每层索引如果有删除就是了。但是插入不一样了,插入需要考虑是否插入索引,插入几层等问题。由于需要插入删除所以我们肯定无法维护一个完全理想的索引结构,因为它耗费的代价太高。但我们使用随机化的方法去判断是否向上层插入索引。即产生一个[0-1]的随机数如果小于0.5就向上插入索引,插入完毕后再次使用随机数判断是否向上插入索引。运气好这个值可能是多层索引,运气不好只插入最底层(这是100%插入的)。但是索引也不能不限制高度,我们一般会设置索引最高值如果大于这个值就不往上继续添加索引了。

我们一步步剖析该怎么做,其流程为

(1)首先通过上面查找的方式,找到待插入的左节点。插入的话最底层肯定是需要插入的,所以通过链表插入节点(需要考虑是否为末尾节点)

(2)插入完这一层,需要考虑上一层是否插入,首先判断当前索引层级,如果大于最大值那么就停止(比如已经到最高索引层了)。否则设置一个随机数1/2的概率向上插入一层索引(因为理想状态下的就是每2个向上建一个索引节点)。

(3)继续(2)的操作,直到概率退出或者索引层数大于最大索引层。

具体向上插入的时候,实质上还有非常重要的细节需要考虑。首先如何找到上层的待插入节点

这个各个实现方法可能不同,如果有左、上指向的指针那么可以向左向上找到上层需要插入的节点,但是如果只有右指向和下指向的我们也可以巧妙的借助查询过程中记录下降的节点。因为曾经下降的节点倒序就是需要插入的节点,最底层也不例外(因为没有匹配值会下降为null结束循环)。在这里我使用这个数据结构进行存储,当然使用List也可以。下图就是给了一个插入示意图。

image-20201225100031207

其次如果该层是目前的最高层索引,需要继续向上建立索引应该怎么办?

首先跳表最初肯定是没索引的,然后慢慢添加节点才有一层、二层索引,但是如果这个节点添加的索引突破当前最高层,该怎么办呢?

这时候需要注意了,跳表的head需要改变了,新建一个ListNode节点作为新的head,将它的down指向老head,将这个head节点加入栈中(也就是这个节点作为下次后面要插入的节点),就比如上面的9节点如果运气够好在往上建立一层节点,会是这样的。

image-20201225100432978

插入上层的时候注意所有节点要新建(拷贝),除了right的指向down的指向也不能忘记,down指向上一个节点可以用一个临时节点作为前驱节点。如果层数突破当前最高层,头head节点(入口)需要改变。

这部分更多的细节在代码中注释解释了,详细代码为:

public void add(SkipNode node)
{

    int key=node.key;
    SkipNode findNode=search(key);
    if(findNode!=null)//如果存在这个key的节点
    {
        findNode.value=node.value;
        return;
    }
    Stack<SkipNode>stack=new Stack<SkipNode>();//存储向下的节点,这些节点可能在右侧插入节点
    SkipNode team=headNode;//查找待插入的节点   找到最底层的哪个节点。
    while (team!=null) {//进行查找操作 
        if(team.right==null)//右侧没有了,只能下降
        {
            stack.add(team);//将曾经向下的节点记录一下
            team=team.down;
        }
        else if(team.right.key>key)//需要下降去寻找
        {
            stack.add(team);//将曾经向下的节点记录一下
            team=team.down;
        }
        else //向右
        {
            team=team.right;
        }
    }
    int level=1;//当前层数,从第一层添加(第一层必须添加,先添加再判断)
    SkipNode downNode=null;//保持前驱节点(即down的指向,初始为null)
    while (!stack.isEmpty()) {
        //在该层插入node
        team=stack.pop();//抛出待插入的左侧节点
        SkipNode nodeTeam=new SkipNode(node.key, node.value);//节点需要重新创建
        nodeTeam.down=downNode;//处理竖方向
        downNode=nodeTeam;//标记新的节点下次使用
        if(team.right==null) {//右侧为null 说明插入在末尾
            team.right=nodeTeam;
        }
        //水平方向处理
        else {//右侧还有节点,插入在两者之间
            nodeTeam.right=team.right;
            team.right=nodeTeam;
        }
        //考虑是否需要向上
        if(level>MAX_LEVEL)//已经到达最高级的节点啦
            break;
        double num=random.nextDouble();//[0-1]随机数
        if(num>0.5)//运气不好结束
            break;
        level++;
        if(level>highLevel)//比当前最大高度要高但是依然在允许范围内 需要改变head节点
        {
            highLevel=level;
            //需要创建一个新的节点
            SkipNode highHeadNode=new SkipNode(Integer.MIN_VALUE, null);
            highHeadNode.down=headNode;
            headNode=highHeadNode;//改变head
            stack.add(headNode);//下次抛出head
        }
    }
}

总结

对于上面,跳表完整分析就结束啦,当然,你可能看到不同品种跳表的实现,还有的用数组方式表示上下层的关系这样也可以,但本文只定义right和down两个方向的链表更纯正化的讲解跳表。

对于跳表以及跳表的同类竞争产品:红黑树,为啥Redis的有序集合(zset) 使用跳表呢?因为跳表除了查找插入维护和红黑树有着差不多的效率,它是个链表,能确定范围区间,而区间问题在树上可能就没那么方便查询啦。而JDK中跳跃表ConcurrentSkipListSet和ConcurrentSkipListMap。 有兴趣的也可以查阅一下源码。

对于学习,完整的代码是非常重要的,这里我把完整代码贴出来,需要的自取。

import java.util.Random;
import java.util.Stack;
class SkipNode<T>
{
    int key;
    T value;
    SkipNode right,down;//左右上下四个方向的指针
    public SkipNode (int key,T value) {
        this.key=key;
        this.value=value;
    }

}
public class SkipList <T> {

    SkipNode headNode;//头节点,入口
    int highLevel;//层数
    Random random;// 用于投掷硬币
    final int MAX_LEVEL = 32;//最大的层
    SkipList(){
        random=new Random();
        headNode=new SkipNode(Integer.MIN_VALUE,null);
        highLevel=0;
    }
    public SkipNode search(int key) {
        SkipNode team=headNode;
        while (team!=null) {
            if(team.key==key)
            {
                return  team;
            }
            else if(team.right==null)//右侧没有了,只能下降
            {
                team=team.down;
            }
            else if(team.right.key>key)//需要下降去寻找
            {
                team=team.down;
            }
            else //右侧比较小向右
            {
                team=team.right;
            }
        }
        return null;
    }

    public void delete(int key)//删除不需要考虑层数
    {
        SkipNode team=headNode;
        while (team!=null) {
            if (team.right == null) {//右侧没有了,说明这一层找到,没有只能下降
                team=team.down;
            }
            else if(team.right.key==key)//找到节点,右侧即为待删除节点
            {
                team.right=team.right.right;//删除右侧节点
                team=team.down;//向下继续查找删除
            }
            else if(team.right.key>key)//右侧已经不可能了,向下
            {
                team=team.down;
            }
            else { //节点还在右侧
                team=team.right;
            }
        }
    }
    public void add(SkipNode node)
    {
    
        int key=node.key;
        SkipNode findNode=search(key);
        if(findNode!=null)//如果存在这个key的节点
        {
            findNode.value=node.value;
            return;
        }

        Stack<SkipNode>stack=new Stack<SkipNode>();//存储向下的节点,这些节点可能在右侧插入节点
        SkipNode team=headNode;//查找待插入的节点   找到最底层的哪个节点。
        while (team!=null) {//进行查找操作
            if(team.right==null)//右侧没有了,只能下降
            {
                stack.add(team);//将曾经向下的节点记录一下
                team=team.down;
            }
            else if(team.right.key>key)//需要下降去寻找
            {
                stack.add(team);//将曾经向下的节点记录一下
                team=team.down;
            }
            else //向右
            {
                team=team.right;
            }
        }

        int level=1;//当前层数,从第一层添加(第一层必须添加,先添加再判断)
        SkipNode downNode=null;//保持前驱节点(即down的指向,初始为null)
        while (!stack.isEmpty()) {
            //在该层插入node
            team=stack.pop();//抛出待插入的左侧节点
            SkipNode nodeTeam=new SkipNode(node.key, node.value);//节点需要重新创建
            nodeTeam.down=downNode;//处理竖方向
            downNode=nodeTeam;//标记新的节点下次使用
            if(team.right==null) {//右侧为null 说明插入在末尾
                team.right=nodeTeam;
            }
            //水平方向处理
            else {//右侧还有节点,插入在两者之间
                nodeTeam.right=team.right;
                team.right=nodeTeam;
            }
            //考虑是否需要向上
            if(level>MAX_LEVEL)//已经到达最高级的节点啦
                break;
            double num=random.nextDouble();//[0-1]随机数
            if(num>0.5)//运气不好结束
                break;
            level++;
            if(level>highLevel)//比当前最大高度要高但是依然在允许范围内 需要改变head节点
            {
                highLevel=level;
                //需要创建一个新的节点
                SkipNode highHeadNode=new SkipNode(Integer.MIN_VALUE, null);
                highHeadNode.down=headNode;
                headNode=highHeadNode;//改变head
                stack.add(headNode);//下次抛出head
            }
        }

    }
    public void printList() {
        SkipNode teamNode=headNode;
        int index=1;
        SkipNode last=teamNode;
        while (last.down!=null){
            last=last.down;
        }
        while (teamNode!=null) {
            SkipNode enumNode=teamNode.right;
            SkipNode enumLast=last.right;
            System.out.printf("%-8s","head->");
            while (enumLast!=null&&enumNode!=null) {
                if(enumLast.key==enumNode.key)
                {
                    System.out.printf("%-5s",enumLast.key+"->");
                    enumLast=enumLast.right;
                    enumNode=enumNode.right;
                }
                else{
                    enumLast=enumLast.right;
                    System.out.printf("%-5s","");
                }

            }
            teamNode=teamNode.down;
            index++;
            System.out.println();
        }
    }
    public static void main(String[] args) {
        SkipList<Integer>list=new SkipList<Integer>();
        for(int i=1;i<20;i++)
        {
            list.add(new SkipNode(i,666));
        }
        list.printList();
        list.delete(4);
        list.delete(8);
        list.printList();
    }
}

进行测试一下可以发现跳表还是挺完美的(自夸一下)。
image-20201225105810595

原创不易,bigsai请思否的朋友们帮两件事帮忙一下:

  1. 点赞、收藏、关注支持一下, 您的肯定是我创作的源源动力。
  2. 微信搜索「bigsai」,关注我的原创技术公众号,前进道路上不迷路!

咱们下次再见!

查看原文

赞 14 收藏 8 评论 0

bigsai 发布了文章 · 2020-12-18

5张图搞懂Java引用拷贝、深拷贝、浅拷贝

原创公众号 「bigsai」 专注于Java和数据结构与算法的分享
文章收录在github/bigsai-algorithm 可收藏

在开发、刷题、面试中,我们可能会遇到将一个对象的属性赋值到另一个对象的情况,这种情况就叫做拷贝。拷贝与Java内存结构息息相关,搞懂Java深浅拷贝是很必要的!

在对象的拷贝中,很多初学者可能搞不清到底是拷贝了引用还是拷贝了对象。在拷贝中这里就分为引用拷贝、浅拷贝、深拷贝进行讲述。

引用拷贝

引用拷贝会生成一个新的对象引用地址,但是两个最终指向依然是同一个对象。如何更好的理解引用拷贝呢?很简单,就拿我们人来说,通常有个姓名,但是不同场合、人物对我们的叫法可能不同,但我们很清楚哪些名称都是属于"我"的!

image-20201216222353944

当然,通过一个代码示例让大家领略一下(为了简便就不写get、set等方法):

class Son {
    String name;
    int age;

    public Son(String name, int age) {
        this.name = name;
        this.age = age;
    }
}
public class test {
    public static void main(String[] args) {
        Son s1 = new Son("son1", 12);
        Son s2 = s1;
        s1.age = 22;
        System.out.println(s1);
        System.out.println(s2);
        System.out.println("s1的age:" + s1.age);
        System.out.println("s2的age:" + s2.age);
        System.out.println("s1==s2" + (s1 == s2));//相等
    }
}

输出的结果为:

Son@135fbaa4
Son@135fbaa4
s1的age:22
s2的age:22
true

浅拷贝

如何创建一个对象,将目标对象的内容复制过来而不是直接拷贝引用呢?

这里先讲一下浅拷贝,浅拷贝会创建一个新对象,新对象和原对象本身没有任何关系,新对象和原对象不等,但是新对象的属性和老对象相同。具体可以看如下区别:

  • 如果属性是基本类型(int,double,long,boolean等),拷贝的就是基本类型的值;
  • 如果属性是引用类型,拷贝的就是内存地址(即复制引用但不复制引用的对象) ,因此如果其中一个对象改变了这个地址,就会影响到另一个对象。

如果用一张图来描述一下浅拷贝,它应该是这样的:

image-20201217002917565

如何实现浅拷贝呢?也很简单,就是在需要拷贝的类上实现Cloneable接口并重写其clone()方法

@Override
protected Object clone() throws CloneNotSupportedException {
  return super.clone();
}

在使用的时候直接调用类的clone()方法即可。具体案例如下:

class Father{
    String name;
    public Father(String name) {
        this.name=name;
    }
    @Override
    public String toString() {
        return "Father{" +
                "name='" + name + '\'' +
                '}';
    }
}
class Son implements Cloneable {
    int age;
    String name;
    Father father;
    public Son(String name,int age) {
        this.age=age;
        this.name = name;
    }
    public Son(String name,int age, Father father) {
        this.age=age;
        this.name = name;
        this.father = father;
    }
    @Override
    public String toString() {
        return "Son{" +
                "age=" + age +
                ", name='" + name + '\'' +
                ", father=" + father +
                '}';
    }
    @Override
    protected Son clone() throws CloneNotSupportedException {
        return (Son) super.clone();
    }
}
public class test {
    public static void main(String[] args) throws CloneNotSupportedException {
        Father f=new Father("bigFather");
        Son s1 = new Son("son1",13);
        s1.father=f;
        Son s2 = s1.clone();
        
        System.out.println(s1);
        System.out.println(s2);
        System.out.println("s1==s2:"+(s1 == s2));//不相等
        System.out.println("s1.name==s2.name:"+(s1.name == s2.name));//相等
        System.out.println();

        //但是他们的Father father 和String name的引用一样
        s1.age=12;
        s1.father.name="smallFather";//s1.father引用未变
        s1.name="son222";//类似 s1.name=new String("son222") 引用发生变化
        System.out.println("s1.Father==s2.Father:"+(s1.father == s2.father));//相等
        System.out.println("s1.name==s2.name:"+(s1.name == s2.name));//不相等
        System.out.println(s1);
        System.out.println(s2);
    }
}

运行结果为:

Son{age=13, name='son1', father=Father{name='bigFather'}}
Son{age=13, name='son1', father=Father{name='bigFather'}}
s1==s2:false
s1.name==s2.name:true//此时相等

s1.Father==s2.Father:true
s1.name==s2.name:false//修改引用后不等
Son{age=12, name='son222', father=Father{name='smallFather'}}
Son{age=13, name='son1', father=Father{name='smallFather'}}

不出意外,这种浅拷贝除了对象本身不同以外,各个零部件和关系和拷贝对象都是相同的,就好像双胞胎一样,是两个人,但是其开始的样貌、各种关系(父母亲人)都是相同的。需要注意的是其中name初始==是相等的,是因为初始浅拷贝它们指向一个相同的String,而后 s1.name="son222" 则改变引用指向。

image-20201217103648400

深拷贝

对于上述的问题虽然拷贝的两个对象不同,但其内部的一些引用还是相同的,怎么样绝对的拷贝这个对象,使这个对象完全独立于原对象呢?就使用我们的深拷贝了。深拷贝:在对引用数据类型进行拷贝的时候,创建了一个新的对象,并且复制其内的成员变量。

image-20201217111300466

在具体实现深拷贝上,这里提供两个方式,重写clone()方法和序列法。

重写clone()方法

如果使用重写clone()方法实现深拷贝,那么要将类中所有自定义引用变量的类也去实现Cloneable接口实现clone()方法。对于字符类可以创建一个新的字符串实现拷贝。

对于上述代码,Father类实现Cloneable接口并重写clone()方法。son的clone()方法需要对各个引用都拷贝一遍

//Father clone()方法
@Override
protected Father clone() throws CloneNotSupportedException {
    return (Father) super.clone();
}
//Son clone()方法
@Override
protected Son clone() throws CloneNotSupportedException {
    Son son= (Son) super.clone();//待返回克隆的对象
    son.name=new String(name);
    son.father=father.clone();
    return son;
}

其他代码不变,执行结果如下:

Son{age=13, name='son1', father=Father{name='bigFather'}}
Son{age=13, name='son1', father=Father{name='bigFather'}}
s1==s2:false
s1.name==s2.name:false

s1.Father==s2.Father:false
s1.name==s2.name:false
Son{age=12, name='son222', father=Father{name='smallFather'}}
Son{age=13, name='son1', father=Father{name='bigFather'}}

序列化

可以发现这种方式实现了深拷贝。但是这种情况有个问题,如果引用数量或者层数太多了怎么办呢?

image-20201217105458651

不可能去每个对象挨个写clone()吧?那怎么办呢?借助序列化啊。

因为序列化后:将二进制字节流内容写到一个媒介(文本或字节数组),然后是从这个媒介读取数据,原对象写入这个媒介后拷贝给clone对象,原对象的修改不会影响clone对象,因为clone对象是从这个媒介读取。

熟悉对象缓存的知道我们经常将Java对象缓存到Redis中,然后还可能从Redis中读取生成Java对象,这就用到序列化和反序列化。一般可以将Java对象存储为字节流或者json串然后反序列化成Java对象。因为序列化会储存对象的属性但是不会也无法存储对象在内存中地址相关信息。所以在反序列化成Java对象时候会重新创建所有的引用对象。

在具体实现上,自定义的类需要实现Serializable接口。在需要深拷贝的类(Son)中定义一个函数返回该类对象:

protected Son deepClone() throws IOException, ClassNotFoundException {
      Son son=null;
      //在内存中创建一个字节数组缓冲区,所有发送到输出流的数据保存在该字节数组中
      //默认创建一个大小为32的缓冲区
      ByteArrayOutputStream byOut=new ByteArrayOutputStream();
      //对象的序列化输出
      ObjectOutputStream outputStream=new ObjectOutputStream(byOut);//通过字节数组的方式进行传输
      outputStream.writeObject(this);  //将当前student对象写入字节数组中

      //在内存中创建一个字节数组缓冲区,从输入流读取的数据保存在该字节数组缓冲区
      ByteArrayInputStream byIn=new ByteArrayInputStream(byOut.toByteArray()); //接收字节数组作为参数进行创建
      ObjectInputStream inputStream=new ObjectInputStream(byIn);
      son=(Son) inputStream.readObject(); //从字节数组中读取
      return  son;
}

使用时候调用我们写的方法即可,其他不变,实现的效果为:

Son{age=13, name='son1', father=Father{name='bigFather'}}
Son{age=13, name='son1', father=Father{name='bigFather'}}
s1==s2:false
s1.name==s2.name:false

s1.Father==s2.Father:false
s1.name==s2.name:false
Son{age=12, name='son222', father=Father{name='smallFather'}}
Son{age=13, name='son1', father=Father{name='bigFather'}}

写在最后

原创不易,bigsai我请思否两件事帮忙一下:

  1. 点赞支持一下, 您的肯定是我在思否创作的源源动力。
  2. 微信搜索「bigsai」,关注我的公众号(新人求支持),不仅免费送你电子书,我还会第一时间在公众号分享知识技术。加我还可拉你进力扣打卡群一起打卡LeetCode。

如果本篇对你有帮助,还请点个赞,如果您有更好的见解,可以在评论区交流!

查看原文

赞 9 收藏 6 评论 0

bigsai 发布了文章 · 2020-12-11

面试官本拿求素数搞我,但被我优雅的“回击“了(素数筛)

原创公众号(希望能支持一下):bigsai 转载请联系bigsai
文章收录在github

前言

现在的面试官,是无数开发者的梦魇,能够吊打面试官的属实不多,因为大部分面试官真的有那么那几下子。但在面试中,我们这些小生存者不能全盘否定只能单点突破—从某个问题上让面试官眼前一亮。这不,今天就来分享来了。

这年头,算法岗内卷不说,开发岗也有点内卷,对开发者要求越来越高了,而面试官也是处心积虑的 "刁难" 面试者,凡是都喜欢由浅入深,凡是都喜欢问个:你知道为什么?你知道原理吗?之类。并且,以前只是大厂面试官喜欢问算法,大厂员工底子好,很多甚至有ACM经验或者系统刷题经验,这很容易理解,但现在一些小公司面试官也是张口闭口 xx算法、xx数据结构你说说看,这不,真的被问到了。

求一个质数

在这么一次的过程,面试官问我算法题我不吃惊,我实现早把十大排序原理、复杂度分析、代码手写实现出来了,也把链表、树的各种操作温习的滚瓜烂熟,不过突然就是很诧异的面试官来了一道求素数问题,我把场景还原一下:

面试官:你知道怎么求素数吗?

我:求素数?

面试官:是的,就是求素数。

我:这很简单啊,判断一个数为素数,那么肯定就没有两个数(除了自身和1)相乘等于它,只需要枚举看看有没有能够被它整除的数就可以了,如果有那么就不是素数,如果没有,那么就是素数。

面试官露出一种失望的表情,说我说的对,但没答到点子上,让我具体说一下。

下面开始开始我的表演:

首先,最笨的方法,判断n是否为素数,就是枚举[2,n-1]之间有没有直接能够被n整除的,如果有,那么返回false这个就不是素数,否则就是素数,代码如下:

boolean isprime(int value){
  for(int i=2;i<value;i++)
  {
       if(value%i==0)
       {return false;}
  }
    return true;
}

这种判断一个素数的时间复杂度为O(n).

但是其实这种太浪费时间了,完全没必要这样,可以优化一下 。如果一个数不是质数,那么必定是两个数的乘积,而这两个数通常一个大一个小,并且小的小于等于根号n,大的大于等于根号n,我们只需要枚举小的可能范围,看看是否能够被整除,就可以判断这个数是否为素数啦。例如100=2*50=4*25=5*20=10*10 只需要找2—10这个区间即可。右侧的一定有个对应的不需要管它。

boolean isprime(int value)
{
  for(int i=2;i*i<value+1;i++)
    {
       if(value%i==0)
       {return false;}
    }
    return true;
}

这里之所以要小于value+1,就是要包含根号的情况,例如 3*3=9.要包含3.这种时间复杂度求单个数是O(sqrt(n))。面试官我给你画张图让你看看其中区别:

image-20201208105627132

说到这里面试官露出欣慰的笑容。

面试官:不错不错,基本点掌握了
我:老哥,其实求素数精髓不在这,这个太低效在很多时候,比如求小于n的所有素数,你看看怎么搞?

面试官:用个数组用第二种方法求O(n*sqrt(n))还行啊。

求多个素数

求多个素数的时候(小于n的素数),上面的方法就很繁琐了,因为有大量重复计算,因为 计算某个数的倍数 是否为素数的时候出现大量的重复计算,如果这个数比较大那么对空间浪费比较多。

这样,素数筛的概念就被发明和使用。筛的原理是从前往后进行一种递推、过滤排序以来统计素数。

埃拉托斯特尼(Eratosthenes)筛法

我们看一个数如果不是为素数,那么这个数没有数的乘积能为它,那么这样我们可以根据这个思想进行操作啊:

直接从前往后枚举,这个数位置没被标记的肯定就是素数,如果这个数是素数那么将这个数的倍数标记一下(下次遍历到就不需要在计算)。如果不是素数那么就进行下一步。这样数值越大后面计算次数越少,在进行具体操作时候可借助数组进行判断。所以埃氏筛的核心思想就是将素数的倍数确定为合数

假设刚开始全是素数,2为素数,那么2的倍数均不是素数;然后遍历到3,3的倍数标记一下;下个是5(因为4已经被标记过);一直到n-1为止。具体流程可以看图:

image-20201208112829007

具体代码为:

boolean isprime[];
long prime[];
void getprime()
{
        prime=new long[100001];//记录第几个prime
      int index=0;//标记prime当前下标
        isprime=new boolean [1000001];//判断是否被标记过
        for(int i=2;i<1000001;i++)
        {
            if(!isprime[i])
            {
                prime[index++]=i;
            }
            for(int j=i+i;j<1000000;j=j+i)//他的所有倍数都over
            {
                isprime[j]=true;                    
            }
        }
}

这种筛的算法复杂度为O(nloglogn);别小瞧多的这个logn,数据量大一个log可能少不少个0,那时间也是十倍百倍甚至更多的差距。

欧拉筛

面试官已经开始点头赞同了,哦哦的叫了起来,可其实还没完。还有个线性筛—欧拉筛。观察上述的埃氏筛,有很多重复的计算,尤其是前面的素数,比如2和3的最小公倍数为6,每3次2的计算就也会遇到是3的倍数,而欧拉筛在埃氏筛的基础上改进,有效的避免了这个重复计算。

具体是何种思路呢?就是埃氏筛是遇到一个质数将它的倍数计算到底,而欧拉筛则是只用它乘以已知晓的素数的乘积进行标记,如果素数能够被整除那就停止往后标记。

在实现上同样也是用两个数组,一个存储真实有效的素数,一个用来作为标记使用。

  • 在遍历到一个数的时候,如果这个数没被标记,那么这个数存在素数的数组中,对应下标加1.
  • 不管这个数是不是素数,遍历已知素数将它和该素数的乘积值标记,如果这个素数能够被当前值i整除,那么停止操作进行下一轮。

具体实现的代码为:

boolean isprime[];
int prime[];
void getprimeoula()// 欧拉筛
{
        prime = new int[100001];// 记录第几个prime
        int index = 0;
        isprime = new boolean[1000001];
        for (int i = 2; i < 1000001; i++) {
            if (!isprime[i]) {
                prime[index++] = i;
            }
            for (int j = 0; j < index && i * prime[j] <= 100000; j++){//已知素数范围内枚举
                isprime[i * prime[j]] = true;// 标记乘积
                if (i % prime[j] == 0)
                    break;
            }
        }
}

你可能会问为啥if (i % prime[j] == 0)就要break。

如果i%prime[j]==0,那么就说明i=prime[j]*k. k为一个整数。
那么如果进行下一轮的话
i*prime[j+1]=(prime[j]*k)*prime[j+1]=prime[j]*(k*prime[j+1]) i=k*prime[j+1]两个位置就产生冲突重复计算啦,所以一旦遇到能够被整除的就停止。

image-20201208121324157

你可以看到这个过程,6只标记12而不标记18,18被9*2标记。详细理解还需要多看看代码想想。过程图就不画啦!欧拉的思路就是离我较近的我给它标记。欧拉筛的时间复杂度为O(n),因为每个数只标记一次。

面试官露出一脸欣赏的表情,说了句不错,下面就是聊聊家常,让我等待下一次面试!

image-20201208121913781
原创不易,bigsai我请你帮两件事帮忙一下:

  1. 点赞支持一下, 您的肯定是我在思否创作的源源动力。
  2. 微信搜索「bigsai」,关注我的公众号(新人求支持),不仅免费送你电子书,我还会第一时间在公众号分享知识技术。加我还可拉你进力扣打卡群一起打卡LeetCode。

记得关注、咱们下次再见!

查看原文

赞 14 收藏 7 评论 4

bigsai 发布了文章 · 2020-12-08

花五分钟看这篇之前,你才发现你不懂RESTful

原创公众号:bigsai 转载请联系bigsai
文章收藏在回车课堂github

前言

在学习RESTful 风格接口之前,即使你不知道它是什么,但你肯定会好奇它能解决什么问题?有什么应用场景?听完下面描述我想你就会明白:

在互联网并没有完全流行的初期,移动端也没有那么盛行,页面请求和并发量也不高,那时候人们对接口的要求没那么高,一些动态页面(jsp)就能满足绝大多数的使用需求。

image-20201204001441126

但是随着互联网和移动设备的发展,人们对Web应用的使用需求也增加,传统的动态页面由于低效率而渐渐被HTML+JavaScript(Ajax)的前后端分离所取代,并且安卓、IOS、小程序等形式客户端层出不穷,客户端的种类出现多元化,而客户端和服务端就需要接口进行通信,但接口的规范性就又成了一个问题:

image-20201204001702612

所以一套结构清晰、符合标准、易于理解、扩展方便让大部分人都能够理解接受的接口风格就显得越来越重要,而RESTful风格的接口(RESTful API)刚好有以上特点,就逐渐被实践应用而变得流行起来。

image-20201204001618944

现在,RESTful是目前最流行的接口设计规范,在很多公司有着广泛的应用,其中Github 的API设计就是很标准的RESTful API,你可以参考学习。

在开发实践中我们很多人可能还是使用传统API进行请求交互,很多人其实并不特别了解RESTful API,对RESTful API的认知可能会停留在:

  • 面向资源类型的
  • 是一种风格
  • (误区)接口传递参数使用斜杠(/)分割而不用问号(?)传参。

而其实一个很大的误区不要认为没有查询字符串就是RESTful API,也不要认为用了查询字符串就不是RESTful API,更不要认为用了JSON传输的API就是RESTful API。

本教程将带你了解RESTful并用SpringBoot实战RESTful API,在实现本案例前,你需要保证你的电脑上

  • 拥有IDEA用来编写项目代码
  • 拥有Postman模拟请求进行测试
  • 拥有关系数据库MySQL 5.7
  • 拥有navicat对MySQL进行管理

一、REST介绍

REST涉及一些概念性的东西可能比较多,在实战RESTful API之前,要对REST相关的知识有个系统的认知。

REST的诞生

REST(英文:Representational State Transfer,简称REST,直译过来表现层状态转换)是一种软件架构风格、设计风格,而不是标准,只是提供了一组设计原则和约束条件。它主要用于客户端和服务器交互类的软件。基于这个风格设计的软件可以更简洁,更有层次,更易于实现缓存等机制。

它首次出现在 2000 年 Roy Thomas Fielding 的博士论文中,这篇论文定义并详细介绍了表述性状态转移(Representational State Transfer,REST)的架构风格,并且描述了 如何使用 REST 来指导现代 Web 架构的设计和开发。用他自己的原话说:

我写这篇文章的目的是:在符合架构原理前提下,理解和评估基于网络的应用软件的架构设计,得到一个功能强、性能好、适宜通信的架构。

需要注意的是REST并没有一个明确的标准,而更像是一种设计的风格,满足这种设计风格的程序或接口我们称之为RESTful(从单词字面来看就是一个形容词)。所以RESTful API 就是满足REST架构风格的接口。

在这里插入图片描述

Fielding博士当时提出的是REST架构在很久的时间内并没有被关注太多,而近些年REST在国内才变得越来越流行。下面开始详细学习REST架构特征。

REST架构特征

既然知道REST和RESTful的联系和区别,现在就要开始好好了解RESTful的一些约束条件和规则,RESTful是一种风格而不是标准,而这个风格大致有以下几个主要特征

以资源为基础 :资源可以是一个图片、音乐、一个XML格式、HTML格式或者JSON格式等网络上的一个实体,除了一些二进制的资源外普通的文本资源更多以JSON为载体、面向用户的一组数据(通常从数据库中查询而得到)。
统一接口: 对资源的操作包括获取、创建、修改和删除,这些操作正好对应HTTP协议提供的GET、POST、PUT和DELETE方法。换言而知,使用RESTful风格的接口但从接口上你可能只能定位其资源,但是无法知晓它具体进行了什么操作,需要具体了解其发生了什么操作动作要从其HTTP请求方法类型上进行判断。具体的HTTP方法和方法含义如下:

  • GET(SELECT):从服务器取出资源(一项或多项)。
  • POST(CREATE):在服务器新建一个资源。
  • PUT(UPDATE):在服务器更新资源(客户端提供完整资源数据)。
  • PATCH(UPDATE):在服务器更新资源(客户端提供需要修改的资源数据)。
  • DELETE(DELETE):从服务器删除资源。

当然也有很多在具体使用的时候使用PUT表示更新。从请求的流程来看,RESTful API和传统API大致架构如下:
image-20201204001311359

URI指向资源:URI = Universal Resource Identifier 统一资源标志符,用来标识抽象或物理资源的一个紧凑字符串。URI包括URL和URN,在这里更多时候可能代指URL(统一资源定位符)。RESTful是面向资源的,每种资源可能由一个或多个URI对应,但一个URI只指向一种资源。

无状态:服务器不能保存客户端的信息, 每一次从客户端发送的请求中,要包含所有必须的状态信息,会话信息由客户端保存, 服务器端根据这些状态信息来处理请求。 当客户端可以切换到一个新状态的时候发送请求信息, 当一个或者多个请求被发送之后, 客户端就处于一个状态变迁过程中。 每一个应用的状态描述可以被客户端用来初始化下一次的状态变迁。

REST架构限制条件

Fielding在论文中提出REST架构的6个限制条件,也可称为RESTful 6大原则, 标准的REST约束应满足以下6个原则:

客户端-服务端(Client-Server): 这个更专注客户端和服务端的分离,服务端独立可更好服务于前端、安卓、IOS等客户端设备。

无状态(Stateless):服务端不保存客户端状态,客户端保存状态信息每次请求携带状态信息。

可缓存性(Cacheability) :服务端需回复是否可以缓存以让客户端甄别是否缓存提高效率。

统一接口(Uniform Interface):通过一定原则设计接口降低耦合,简化系统架构,这是RESTful设计的基本出发点。当然这个内容除了上述特点提到部分具体内容比较多详细了解可以参考这篇REST论文内容

分层系统(Layered System):客户端无法直接知道连接的到终端还是中间设备,分层允许你灵活的部署服务端项目。

按需代码(Code-On-Demand,可选):按需代码允许我们灵活的发送一些看似特殊的代码给客户端例如JavaScript代码。

REST架构的一些风格和限制条件就先介绍到这里,后面就对RESTful风格API具体介绍。

二、RESTful API设计规范

既然了解了RESTful的一些规则和特性,那么具体该怎么去设计一个RESTful API呢?要从URL路径、HTTP请求动词、状态码和返回结果等方面详细考虑。至于其他的方面例如错误处理、过滤信息等规范这里就不详细介绍了。

URL设计规范

URL为统一资源定位器 ,接口属于服务端资源,首先要通过URL这个定位到资源才能去访问,而通常一个完整的URL组成由以下几个部分构成:

URI = scheme "://" host  ":"  port "/" path [ "?" query ][ "#" fragment ]

scheme: 指底层用的协议,如http、https、ftp
host: 服务器的IP地址或者域名
port: 端口,http默认为80端口
path: 访问资源的路径,就是各种web 框架中定义的route路由
query: 查询字符串,为发送给服务器的参数,在这里更多发送数据分页、排序等参数。
fragment: 锚点,定位到页面的资源

我们在设计API时URL的path是需要认真考虑的,而RESTful对path的设计做了一些规范,通常一个RESTful API的path组成如下:

/{version}/{resources}/{resource_id}

version:API版本号,有些版本号放置在头信息中也可以,通过控制版本号有利于应用迭代。
resources:资源,RESTful API推荐用小写英文单词的复数形式。
resource_id:资源的id,访问或操作该资源。

当然,有时候可能资源级别较大,其下还可细分很多子资源也可以灵活设计URL的path,例如:

/{version}/{resources}/{resource_id}/{subresources}/{subresource_id}

此外,有时可能增删改查无法满足业务要求,可以在URL末尾加上action,例如

/{version}/{resources}/{resource_id}/action

其中action就是对资源的操作。

从大体样式了解URL路径组成之后,对于RESTful API的URL具体设计的规范如下:

  1. 不用大写字母,所有单词使用英文且小写。
  2. 连字符用中杠"-"而不用下杠"_"
  3. 正确使用 "/" 表示层级关系,URL的层级不要过深,并且越靠前的层级应该相对越稳定
  4. 结尾不要包含正斜杠分隔符"/"
  5. URL中不出现动词,用请求方式表示动作
  6. 资源表示用复数不要用单数
  7. 不要使用文件扩展名

HTTP动词

在RESTful API中,不同的HTTP请求方法有各自的含义,这里就展示GET,POST,PUT,DELETE几种请求API的设计与含义分析。针对不同操作,具体的含义如下:

GET /collection:从服务器查询资源的列表(数组)
GET /collection/resource:从服务器查询单个资源
POST /collection:在服务器创建新的资源
PUT /collection/resource:更新服务器资源
DELETE /collection/resource:从服务器删除资源

在非RESTful风格的API中,我们通常使用GET请求和POST请求完成增删改查以及其他操作,查询和删除一般使用GET方式请求,更新和插入一般使用POST请求。从请求方式上无法知道API具体是干嘛的,所有在URL上都会有操作的动词来表示API进行的动作,例如:query,add,update,delete等等。

而RESTful风格的API则要求在URL上都以名词的方式出现,从几种请求方式上就可以看出想要进行的操作,这点与非RESTful风格的API形成鲜明对比。

在谈及GET,POST,PUT,DELETE的时候,就必须提一下接口的安全性和幂等性,其中安全性是指方法不会修改资源状态,即读的为安全的,写的操作为非安全的。而幂等性的意思是操作一次和操作多次的最终效果相同,客户端重复调用也只返回同一个结果。

上述四个HTTP请求方法的安全性和幂等性如下:

HTTP Method安全性幂等性解释
GET安全幂等读操作安全,查询一次多次结果一致
POST非安全非幂等写操作非安全,每多插入一次都会出现新结果
PUT非安全幂等写操作非安全,一次和多次更新结果一致
DELETE非安全幂等写操作非安全,一次和多次删除结果一致

状态码和返回数据

服务端处理完成后客户端也可能不知道具体成功了还是失败了,服务器响应时,包含状态码返回数据两个部分。

状态码

我们首先要正确使用各类状态码来表示该请求的处理执行结果。状态码主要分为五大类:

1xx:相关信息
2xx:操作成功
3xx:重定向
4xx:客户端错误
5xx:服务器错误

每一大类有若干小类,状态码的种类比较多,而主要常用状态码罗列在下面:

200 OK - [GET]:服务器成功返回用户请求的数据,该操作是幂等的(Idempotent)。
201 CREATED - [POST/PUT/PATCH]:用户新建或修改数据成功。
202 Accepted - [*]:表示一个请求已经进入后台排队(异步任务)
204 NO CONTENT - [DELETE]:用户删除数据成功。
400 INVALID REQUEST - [POST/PUT/PATCH]:用户发出的请求有错误,服务器没有进行新建或修改数据的操作,该操作是幂等的。
401 Unauthorized - [*]:表示用户没有权限(令牌、用户名、密码错误)。
403 Forbidden - [*] 表示用户得到授权(与401错误相对),但是访问是被禁止的。
404 NOT FOUND - [*]:用户发出的请求针对的是不存在的记录,服务器没有进行操作,该操作是幂等的。
406 Not Acceptable - [GET]:用户请求的格式不可得(比如用户请求JSON格式,但是只有XML格式)。
410 Gone -[GET]:用户请求的资源被永久删除,且不会再得到的。
422 Unprocesable entity - [POST/PUT/PATCH] 当创建一个对象时,发生一个验证错误。
500 INTERNAL SERVER ERROR - [*]:服务器发生错误,用户将无法判断发出的请求是否成功。

返回结果

针对不同操作,服务器向用户返回数据,而各个团队或公司封装的返回实体类也不同,但都返回JSON格式数据给客户端。

第三关 一个RESTful API案例

上面讲了RESTful理论知识,下面动手实现一个小案例吧!

预备

在本案例的实战中,我们访问的RESTful接口都是对数据库真实的操作,新建数据库,创建一个数据库和表(根据自己喜好)。

选择Maven依赖的时候,只需要勾选其中Spring的Web模块、MySQL驱动以及MyBatis框架。

本案例的POJO创建Dog.java实体对象,其具体构造为:

package com.restfuldemo.pojo;

public class Dog {
    private int id;//唯一id标识
    private String name;//名称
    private  int age;//年龄
    //省略get set
}

上面创建好了项目,我们就开始构建RESTful风格的API。在具体构建RESTful API的时候,需要对各种请求有更细致的认知,当然,本案例在实现各种请求的时候为了演示的便捷并没有完全遵循RESTful API规范,例如版本号等信息这里就不添加了,案例更侧重于使用SpringBoot实现这个接口。

本案例实现对dog资源的增删改查,如下是非RESTful 和RESTful接口对比:

API name非 RESTfulRESTful
获取dog/dogs/query/{dogid}GET: /dogs/{dogid}
插入dog/dogs/addPOST: /dogs
更新dog/dogs/update/{dogid}PUT:/dogs/{dogid}
删除dog/dods/delete/{dogid} DELETE:/dogs/{dogid}

另外在使用postman进行发送请求的时候,有三种常用的文件类型传递到后端:

在这里插入图片描述
form-data : 就是form表单中的multipart/form-data,会将表单数据处理为一条信息,用特定标签符将一条条信息分割开,而这个文件类型通常用来上传二进制文件。

x-www-form-urlencoded:就是application/x-www-form-urlencoded,是form表单默认的encType,form表单会将表单内的数据转换为键值对,这种格式不能上传文件。

raw:可以上传任意格式的文本,可以上传Text,JSON,XML等,但目前大部分还是上传JSON格式数据。当后端需要接收JSON格式数据处理的时候,可以采用这种格式来测试。

因为GET请求查询参数在URL上,其他类型请求使用x-www-form-urlencoded方式向后端传值。

GET POST PUT DELETE请求

GET请求用来获取资源:GET请求会向数据库发索取数据的请求,从而来获取资源,该请求就像数据库的select操作一样,只是用来查询数据,不会影响资源的内容。无论进行多少次操作,结果都是一样的。

并且GET请求会把请求的参数附加在URL后面,但是不同的浏览器对其有不同的大小长度限制。

在本案例中,我们设计两个GET请求的API。
GET /dogs :用来返回dog资源的列表。
GET /dogs/{dogid} :用来查询此id的单个dog资源。

POST请求用来新增一个资源 : POST请求向服务器发送数据,但是该请求会改变数据的内容(新添),就像数据库的insert操作一样,会创建新的内容。且POST请求的请求参数都是请求体中,其大小是没有限制的。

在本案例中,我们设计以下POST请求的API。
POST /dogs :服务端新增一个dog资源。

PUT请求用来更新资源,PUT请求是向服务器端发送数据的, 与POST请求不同的是,PUT请求侧重于数据的修改 ,就像数据库中update一样,而POST请求侧重于数据的增加。

在本案例中,我们设计以下POST请求的API。
PUT /dogs/{dogid} :用来更新此id的单个dog资源。

DELETE 请求用来删除资源,DELETE请求用途和它字面意思一致,用来删除资源。和数据库中delete相对应。

在本案例中,我们设计以下DELETE请求的API。
DELETE /dogs/{dogid} :用来删除此id的单个dog资源。

对应的Mapper文件为:

package com.restfuldemo.mapper;

import com.restfuldemo.pojo.Dog;
import org.apache.ibatis.annotations.*;
import java.util.List;

@Mapper
public interface DogMapper {

    @Select("select * from dog")
    List<Dog> getAllDog();

    @Select("select * from dog where id=#{id}")
    Dog getDogById(@Param("id") int id);

    @Insert("insert into dog (name,age) values (#{name},#{age})")
    boolean addDog(Dog dog);

    @Update("update dog set name=#{name},age=#{age} where id=#{id}")
    boolean updateDog(Dog dog);

    @Delete("delete  from dog where id=#{id}")
    boolean deleteDogById(int id);
}

对应controller文件为:

package com.restfuldemo.controller;

import com.restfuldemo.mapper.DogMapper;
import com.restfuldemo.pojo.Dog;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.web.bind.annotation.*;

import java.util.Arrays;
import java.util.List;

@RestController
public class TestController {

    @Autowired(required = false)
    DogMapper dogMapper;

    @GetMapping("dogs")
    public List<Dog> getDogs()
    {
        return  dogMapper.getAllDog();
    }

    @GetMapping("dogs/{id}")
    public Dog getDogById(@PathVariable("id") int id)
    {
        Dog dog=dogMapper.getDogById(id);
        return  dog;
    }
    @PostMapping("dogs")
    public boolean addDog(Dog dog)
    {
        return dogMapper.addDog(dog);
    }
    @PutMapping("dogs/{id}")
    public boolean updateDog(@PathVariable("id")int id,@RequestParam("name")String name,@RequestParam("age")int age)
    {

        Dog dog=dogMapper.getDogById(id);
        dog.setName(name);
        dog.setAge(age);
        return  dogMapper.updateDog(dog);
    }

    @DeleteMapping("dogs/{id}")
    public boolean deleteDog(@PathVariable("id") int id)
    {
        return  dogMapper.deleteDogById(id);
    }
}

经过笔者测试一切都是ok的,如果要项目源文件请联系笔者发你哈!

总结

RESTful风格的API 固然很好很规范,但大多数互联网公司并没有按照或者完全按照其规则来设计,因为REST是一种风格,而不是一种约束或规则,过于理想的RESTful API 会付出太多的成本。

比如RESTful API也有一些缺点

  • 比如操作方式繁琐,RESTful API通常根据GET、POST、PUT、DELETE 来区分操作资源的动作,而HTTP Method 本身不可直接见,是隐藏的,而如果将动作放到URL的path上反而清晰可见,更利于团队的理解和交流。
  • 并且有些浏览器对GET,POST之外的请求支持不太友好,还需要特殊额外的处理。
  • 过分强调资源,而实际业务API可能有各种需求比较复杂,单单使用资源的增删改查可能并不能有效满足使用需求,强行使用RESTful风格API只会增加开发难度和成本。

所以,当你或你们的技术团队在设计API的时候,如果使用场景和REST风格很匹配,那么你们可以采用RESTful 风格API。但是如果业务需求和RESTful风格API不太匹配或者很麻烦,那也可以不用RESTful风格API或者可以借鉴一下,毕竟无论那种风格的API都是为了方便团队开发、协商以及管理,不能墨守成规。
在这里插入图片描述
到这里RESTful API的介绍和实战就结束啦,本篇首先从RESTful的一些特点进行介绍,再到SpringBoot实战RESTful API,最后也说了一些RESTful API并不完美的地方,相信睿智的你对RESTful 一定有了很深刻的理解。在以后项目的API设计上定能有所优化。

不同的人对RESTful API可能有着不同的理解,但存在即合理,RESTful API有着其鲜明的优势和特点,目前也是一种API设计的主要选型之一,所以掌握和理解RESTful API还是相当重要的!
在这里插入图片描述

原创不易,bigsai我请你帮两件事帮忙一下:

  1. 点赞支持一下, 您的肯定是我在思否创作的源源动力。
  2. 微信搜索「bigsai」,关注我的公众号(新人求支持),会第一时间在公众号分享知识技术。还可一起打卡LeetCode。
查看原文

赞 35 收藏 19 评论 0

bigsai 赞了文章 · 2020-12-05

学生物的女朋友都能看懂的哈希表总结!

散列(哈希)表总结

之前给大家介绍了链表栈和队列今天我们来说一种新的数据结构散列(哈希)表,散列是应用非常广泛的数据结构,在我们的刷题过程中,散列表的出场率特别高。所以我们快来一起把散列表的内些事给整明白吧。文章框架如下

脑图

脑图

说散列表之前,我们先设想以下场景。

袁厨穿越回了古代,凭借从现代学习的做饭手艺,开了一个袁记菜馆,正值开业初期,店里生意十分火爆,但是顾客结账时就犯难了,每当结账的时候,老板娘总是按照菜单一个一个找价格(遍历查找),每次都要找半天,所以结账的地方总是排起长队,顾客们表示用户体验不咋滴。袁厨一想这不是办法啊,让顾客老是等着,太影响客户体验啦。所以袁厨就先把菜单按照首字母排序(二分查找),然后查找的时候根据首字母查找,这样结账的时候就能大大提高检索效率啦!但是呢?工作日顾客不多,老板娘完全应付的过来,但是每逢节假日,还是会排起长队。那么有没有什么更好的办法呢?对呀!我们把所有的价格都背下来不就可以了吗?每个菜的价格我们都了如指掌,结账的时候我们只需简单相加即可。所以袁厨和老板娘加班加点的进行背诵。下次再结账的时候一说吃了什么菜,我们立马就知道价格啦。自此以后收银台再也没有出现过长队啦,袁记菜馆开着开着一不小心就成了天下第一饭店了。

下面我们来看一下袁记菜馆老板娘进化史。

image-20201117132633797

image-20201117132633797

上面的后期结账的过程则模拟了我们的散列表查找,那么在计算机中是如何使用进行查找的呢?

散列表查找步骤

散列表-------最有用的基本数据结构之一。是根据关键码的值儿直接进行访问的数据结构,散列表的实现常常叫做散列(hasing)。散列是一种用于以常数平均时间执行插入、删除和查找的技术,下面我们来看一下散列过程。

我们的整个散列过程主要分为两步

(1)通过散列函数计算记录的散列地址,并按此散列地址存储该记录。就好比麻辣鱼我们就让它在川菜区,糖醋鱼,我们就让它在鲁菜区。但是我们需要注意的是,无论什么记录我们都需要用同一个散列函数计算地址,再存储。

(2)当我们查找时,我们通过同样的散列函数计算记录的散列地址,按此散列地址访问该记录。因为我们存和取得时候用的都是一个散列函数,因此结果肯定相同。

刚才我们在散列过程中提到了散列函数,那么散列函数是什么呢?

我们假设某个函数为 f,使得

存储位置 = f (关键字)

输入:关键字输出:存储位置(散列地址)

那样我们就能通过查找关键字不需要比较就可获得需要的记录的存储位置。这种存储技术被称为散列技术。散列技术是在通过记录的存储位置和它的关键字之间建立一个确定的对应关系 f ,使得每个关键字 key 都对应一个存储位置 f(key)。见下图

这里的 f 就是我们所说的散列函数(哈希)函数。我们利用散列技术将记录存储在一块连续的存储空间中,这块连续存储空间就是我们本文的主人公------散列(哈希)表

上图为我们描述了用散列函数将关键字映射到散列表,但是大家有没有考虑到这种情况,那就是将关键字映射到同一个槽中的情况,即 f(k4) = f(k3) 时。这种情况我们将其称之为冲突k3k4则被称之为散列函数 f同义词,如果产生这种情况,则会让我们查找错误。幸运的是我们能找到有效的方法解决冲突。

首先我们可以对哈希函数下手,我们可以精心设计哈希函数,让其尽可能少的产生冲突,所以我们创建哈希函数时应遵循以下规则

(1)必须是一致的,假设你输入辣子鸡丁时得到的是在看,那么每次输入辣子鸡丁时,得到的也必须为在看。如果不是这样,散列表将毫无用处。

(2)计算简单,假设我们设计了一个算法,可以保证所有关键字都不会冲突,但是这个算法计算复杂,会耗费很多时间,这样的话就大大降低了查找效率,反而得不偿失。所以咱们散列函数的计算时间不应该超过其他查找技术与关键字的比较时间,不然的话我们干嘛不使用其他查找技术呢?

(3)散列地址分布均匀我们刚才说了冲突的带来的问题,所以我们最好的办法就是让散列地址尽量均匀分布在存储空间中,这样即保证空间的有效利用,又减少了处理冲突而消耗的时间。

现在我们已经对散列表,散列函数等知识有所了解啦,那么我们来看几种常用的散列函数构造规则。这些方法的共同点为都是将原来的数字按某种规律变成了另一个数字。

散列函数构造方法

直接定址法

如果我们对盈利为0-9的菜品设计哈希表,我们则直接可以根据作为地址,则 f(key) = key;

即下面这种情况。

有没有感觉上面的图很熟悉,没错我们经常用的数组其实就是一张哈希表,关键码就是数组的索引下标,然后我们通过下标直接访问数组中的元素。

另外我们假设每道菜的成本为50块,那我们还可以根据盈利+成本来作为地址,那么则 f(key) = key + 50。也就是说我们可以根据线性函数值作为散列地址。

f(key) = a * key + ba,b均为常数

优点:简单、均匀、无冲突。

应用场景:需要事先知道关键字的分布情况,适合查找表较小且连续的情况

数字分析法

该方法也是十分简单的方法,就是分析我们的关键字,取其中一段,或对其位移,叠加,用作地址。比如我们的学号,前 6 位都是一样的,但是后面 3 位都不相同,我们则可以用学号作为键,后面的 3 位做为我们的散列地址。如果我们这样还是容易产生冲突,则可以对抽取数字再进行处理。我们的目的只有一个,提供一个散列函数将关键字合理的分配到散列表的各位置。这里我们提到了一种新的方式,抽取,这也是在散列函数中经常用到的手段。

image-20201117161754010

image-20201117161754010

优点:简单、均匀、适用于关键字位数较大的情况

应用场景:关键字位数较大,知道关键字分布情况且关键字的若干位较均匀

折叠法

其实这个方法也很简单,也是处理我们的关键字然后用作我们的散列地址,主要思路是将关键字从左到右分割成位数相等的几部分,然后叠加求和,并按散列表表长,取后几位作为散列地址。

比如我们的关键字是123456789,则我们分为三部分 123 ,456 ,789 然后将其相加得 1368 然后我们再取其后三位 368 作为我们的散列地址。

优点:事先不需要知道关键字情况

应用场景:适合关键字位数较多的情况

除法散列法

在用来设计散列函数的除法散列法中,通过取 key 除以 p 的余数,将关键字映射到 p 个槽中的某一个上,对于散列表长度为 m 的散列函数公式为

f(k) = k mod p (p <= m)

例如,如果散列表长度为 12,即 m = 12 ,我们的参数 p 也设为12,那 k = 100时 f(k) = 100 % 12 = 4

由于只需要做一次除法操作,所以除法散列法是非常快的。

由上面的公式可以看出,该方法的重点在于 p 的取值,如果 p 值选的不好,就可能会容易产生同义词。见下面这种情况。我们哈希表长度为6,我们选择6为p值,则有可能产生这种情况,所有关键字都得到了0这个地址数。 image-20201117191635083

那我们在选用除法散列法时选取 p 值时应该遵循怎样的规则呢?

  • m 不应为 2 的幂,因为如果 m = 2^p ,则 f(k) 就是 k 的 p 个最低位数字。例 12 % 8 = 4 ,12的二进制表示位1100,后三位为100。
  • 若散列表长为 m ,通常 p 为 小于或等于表长(最好接近m)的最小质数或不包含小于 20 质因子的合数。
合数:合数是指在大于1的整数中除了能被1和本身整除外,还能被其他数(0除外)整除的数。

质因子:质因子(或质因数)在数论里是指能整除给定正整数的质数。

这里的2,3,5为质因子

还是上面的例子,我们根据规则选择 5 为 p 值,我们再来看。这时我们发现只有 6 和 36 冲突,相对来说就好了很多。

优点:计算效率高,灵活

应用场景:不知道关键字分布情况

乘法散列法

构造散列函数的乘法散列法主要包含两个步骤

  • 用关键字 k 乘上常数 A(0 < A < 1),并提取 k A 的小数部分
  • 用 m 乘以这个值,再向下取整

散列函数为

f (k) = ⌊ m(kA mod 1) ⌋

这里的 kA mod 1 的含义是取 keyA 的小数部分,即 kA - ⌊kA⌋

优点:对 m 的选择不是特别关键,一般选择它为 2 的某个幂次(m = 2 ^ p ,p为某个整数)

应用场景:不知道关键字情况

平方取中法

这个方法就比较简单了,假设关键字是 321,那么他的平方就是 103041,再抽取中间的 3 位就是 030 或 304 用作散列地址。再比如关键字是 1234 那么它的平方就是 1522756 ,抽取中间 3 位就是 227 用作散列地址.

优点:灵活,适用范围广泛

适用场景:不知道关键字分布,而位数又不是很大的情况。

随机数法

故名思意,取关键字的随机函数值为它的散列地址。也就是 f(key) = random(key)。这里的random是 随机函数。

优点:易实现

适用场景:关键字的长度不等时

上面我们的例子都是通过数字进行举例,那么如果是字符串可不可以作为键呢?当然也是可以的,各种各样的符号我们都可以转换成某种数字来对待,比如我们经常接触的ASCII 码,所以是同样适用的。

以上就是常用的散列函数构造方法,其实他们的中心思想是一致的,将关键字经过加工处理之后变成另外一个数字,而这个数字就是我们的存储位置,是不是有一种间谍传递情报的感觉。

一个好的哈希函数可以帮助我们尽可能少的产生冲突,但是也不能完全避免产生冲突,那么遇到冲突时应该怎么做呢?下面给大家带来几种常用的处理散列冲突的方法。

处理散列冲突的方法

我们在使用 hash 函数之后发现关键字 key1 不等于 key2 ,但是 f(key1) = f(key2),即有冲突,那么该怎么办呢?不急我们慢慢往下看。

开放地址法

了解开放地址法之前我们先设想以下场景。

袁记菜馆内,铃铃铃,铃铃铃 电话铃响了

大鹏:老袁,给我订个包间,我今天要去带几个客户去你那谈生意。

袁厨:大鹏啊,你常用的那个包间被人订走啦。

大鹏:老袁你这不仗义呀,咋没给我留住呀,那你给我找个空房间吧。

袁厨:好滴老哥

哦,穿越回古代就没有电话啦,那看来穿越的时候得带着几个手机了。

上面的场景其实就是一种处理冲突的方法-----开放地址法

开放地址法就是一旦发生冲突,就去寻找下一个空的散列地址,只要列表足够大,空的散列地址总能找到,并将记录存入,为了使用开放寻址法插入一个元素,需要连续地检查散列表,或称为探查,我们常用的有线性探测,二次探测,随机探测

线性探测法

下面我们先来看一下线性探测,公式:

f,(key) = ( f(key) + di ) MOD m(di = 1,2,3,4,5,6....m-1)

我们来看一个例子,我们的关键字集合为{12,67,56,16,25,37,22,29,15,47,48,21},表长为12,我们再用散列函数 f(key) = key mod 12。

我们求出每个 key 的 f(key)见下表

我们查看上表发现,前五位的 f(key) 都不相同,即没有冲突,可以直接存入,但是到了第六位 f(37) = f(25) = 1,那我们就需要利用上面的公式 f(37) = f (f(37) + 1 ) mod 12 = 2,这其实就是我们的订包间的做法。下面我们看一下将上面的所有数存入哈希表是什么情况吧。

我们把这种解决冲突的开放地址法称为线性探测法。下面我们通过视频来模拟一下线性探测法的存储过程。

另外我们在解决冲突的时候,会遇到 48 和 37 虽然不是同义词,却争夺一个地址的情况,我们称其为堆积。因为堆积使得我们需要不断的处理冲突,插入和查找效率都会大大降低。

通过上面的视频我们应该了解了线性探测的执行过程了,那么我们考虑一下这种情况,若是我们的最后一位不为21,为 34 时会有什么事情发生呢?

此时他第一次会落在下标为 10 的位置,那么如果继续使用线性探测的话,则需要通过不断取余后得到结果,数据量小还好,要是很大的话那也太慢了吧,但是明明他的前面就有一个空房间呀,如果向前移动只需移动一次即可。不要着急,前辈们已经帮我们想好了解决方法

二次探测法

其实理解了我们的上个例子之后,这个一下就能整明白了,根本不用费脑子,这个方法就是更改了一下di的取值

线性探测: f,(key) = ( f(key) + di ) MOD m(di = 1,2,3,4,5,6....m-1)

二次探测:f,(key) = ( f(key) + di ) MOD m(di =1^2 , -1^2 , 2^2 , -2^2 .... q^2, -q^2, q<=m/2)

注:这里的是 -1^2 为负值 而不是 (-1)^2

所以对于我们的34来说,当di = -1时,就可以找到空位置了。

二次探测法的目的就是为了不让关键字聚集在某一块区域。另外还有一种有趣的方法,位移量采用随机函数计算得到,接着往下看吧.

随机探测法

大家看到这是不又有新问题了,刚才我们在散列函数构造规则的第一条中说

(1)必须是一致的,假设你输入辣子鸡丁时得到的是在看,那么每次输入辣子鸡丁时,得到的也必须为在看。如果不是这样,散列表将毫无用处。

咦?怎么又是在看哈哈,那么问题来了,我们使用随机数作为他的偏移量,那么我们查找的时候岂不是查不到了?因为我们 di 是随机生成的呀,这里的随机其实是伪随机数,伪随机数含义为,我们设置随机种子相同,则不断调用随机函数可以生成不会重复的数列,我们在查找时,用同样的随机种子它每次得到的数列是相同的,那么相同的 di 就能得到相同的散列地址

随机种子(Random Seed)是计算机专业术语,一种以随机数作为对象的以真随机数(种子)为初始条件的随机数。一般计算机的随机数都是伪随机数,以一个真随机数(种子)作为初始条件,然后用一定的算法不停迭代产生随机数

通过上面的测试是不是一下就秒懂啦,为什么我们可以使用随机数作为它的偏移量,理解那句,相同的随机种子,他每次得到的数列是相同的。

下面我们再来看一下其他的函数处理散列冲突的方法

再哈希法

这个方法其实也特别简单,利用不同的哈希函数再求得一个哈希地址,直到不出现冲突为止。

f,(key) = RH,( key ) (i = 1,2,3,4.....k)

这里的RH,就是不同的散列函数,你可以把我们之前说过的那些散列函数都用上,每当发生冲突时就换一个散列函数,相信总有一个能够解决冲突的。这种方法能使关键字不产生聚集,但是代价就是增加了计算时间。是不是很简单啊。

链地址法

下面我们再设想以下情景。

袁记菜馆内,铃铃铃,铃铃铃电话铃又响了,那个大鹏又来订房间了。

大鹏:老袁啊,我一会去你那吃个饭,还是上回那个包间

袁厨:大鹏你下回能不能早点说啊,又没人订走了,这回是老王订的

大鹏:老王这个老东西啊,反正也是熟人,你再给我整个桌子,我拼在他后面吧

不好意思啊各位同学,信鸽最近太贵了还没来得及买。上面的情景就是模拟我们的新的处理冲突的方法链地址法。

上面我们都是遇到冲突之后,就换地方。那么我们有没有不换地方的办法呢?那就是我们现在说的链地址法。

还记得我们说过得同义词吗?就是 key 不同 f(key) 相同的情况,我们将这些同义词存储在一个单链表中,这种表叫做同义词子表,散列表中只存储同义词子表的头指针。我们还是用刚才的例子,关键字集合为{12,67,56,16,25,37,22,29,15,47,48,21},表长为12,我们再用散列函数 f(key) = key mod 12。我们用了链地址法之后就再也不存在冲突了,无论有多少冲突,我们只需在同义词子表中添加结点即可。下面我们看下链地址法的存储情况。

链地址法虽然能够不产生冲突,但是也带来了查找时需要遍历单链表的性能消耗,有得必有失嘛。

公共溢出区法

下面我们再来看一种新的方法,这回大鹏又要来吃饭了。

袁记菜馆内.....

袁厨:呦,这是什么风把你给刮来了,咋没开你的大奔啊。

大鹏:哎呀妈呀,别那么多废话了,我快饿死了,你快给我找个位置,我要吃点饭。

袁厨:你来的,太不巧了,咱们的店已经满了,你先去旁边的小屋看会电视,等有空了我再叫你。小屋里面还有几个和你一样来晚的,你们一起看吧。

大鹏:电视?看电视?

上面得情景就是模拟我们的公共溢出区法,这也是很好理解的,你不是冲突吗?那冲突的各位我先给你安排个地方呆着,这样你就有地方住了。我们为所有冲突的关键字建立了一个公共的溢出区来存放。 溢出区法

那么我们怎么进行查找呢?我们首先通过散列函数计算出散列地址后,先于基本表对比,如果不相等再到溢出表去顺序查找。这种解决冲突的方法,对于冲突很少的情况性能还是非常高的。

散列表查找算法(线性探测法)

下面我们来看一下散列表查找算法的实现

首先需要定义散列列表的结构以及一些相关常数,其中elem代表散列表数据存储数组,count代表的是当前插入元素个数,size代表哈希表容量,NULLKEY散列表初始值,然后我们如果查找成功就返回索引,如果不存在该元素就返回元素不存在。

我们将哈希表初始化,为数组元素赋初值。

插入操作的具体步骤:

(1)通过哈希函数(除法散列法),将 key 转化为数组下标

(2)如果该下标中没有元素,则插入,否则说明有冲突,则利用线性探测法处理冲突。详细步骤见注释

查找操作的具体步骤:

(1)通过哈希函数(同插入时一样),将 key 转成数组下标

(2)通过数组下标找到 key值,如果 key 一致,则查找成功,否则利用线性探测法继续查找。

下面我们来看一下完整代码

散列表性能分析

如果没有冲突的话,散列查找是我们查找中效率最高的,时间复杂度为O(1),但是没有冲突的情况是一种理想情况,那么散列查找的平均查找长度取决于哪些方面呢?

1.散列函数是否均匀

我们在上文说到,可以通过设计散列函数减少冲突,但是由于不同的散列函数对一组关键字产生冲突可能性是相同的,因此我们可以不考虑它对平均查找长度的影响。

2.处理冲突的方法

相同关键字,相同散列函数,不同处理冲突方式,会使平均查找长度不同,比如我们线性探测有时会堆积,则不如二次探测法好,因为链地址法处理冲突时不会产生任何堆积,因而具有最佳的平均查找性能

3.散列表的装填因子

本来想在上文中提到装填因子的,但是后来发现即使没有说明也不影响我们对哈希表的理解,下面我们来看一下装填因子的总结

装填因子 α = 填入表中的记录数 / 散列表长度

散列因子则代表着散列表的装满程度,表中记录越多,α就越大,产生冲突的概率就越大。我们上面提到的例子中 表的长度为12,填入记录数为6,那么此时的 α = 6 / 12 = 0.5 所以说当我们的 α 比较大时再填入元素那么产生冲突的可能性就非常大了。所以说散列表的平均查找长度取决于装填因子,而不是取决于记录数。所以说我们需要做的就是选择一个合适的装填因子以便将平均查找长度限定在一个范围之内。


各位如果能感觉到这个文章写的很用心的话,能给您带来一丢丢帮助的话,能麻烦您给这个文章点个赞吗?这样我就巨有动力写下去啦。

另外大家如果需要其他精选算法题的动图解析,大家可以微信关注下 【袁厨的算法小屋】,我是袁厨一个酷爱做饭所以自己考取了厨师证的菜鸡程序员,会一直用心写下去的,感谢支持!
image

查看原文

赞 2 收藏 0 评论 7

bigsai 赞了文章 · 2020-12-04

坚持并活下去!cxuan 在思否的 2020 年终总结。

前段时间被 why 神开车带飞的时候,我才想起来,一年前的我和他有一段对话

image.png

没想到今年,却开启了 爆肝模式

写了 100 + 篇文章

在公众号的历程中,我喜欢使用大图 + 公众号原创篇数来记录一下自己究竟写了多少篇原创文章。详情可以翻阅一下这篇文章

cxuan 都能写 100 篇文章,你还有啥不能的

从刚开始写文章的磕磕绊绊,到现在能完整的撸出来一篇万字长文,也算是有了十足的进步。现在回过头来看一下当年的文章,有点想把他们都删了的冲动 ...

image.png

这就是文章刚开始的样子了,是的你没看错,我一篇文章到现在已经有一年半的时间了。刚开始的文章,没有排版,没有条理逻辑,仿佛不是给人看的,完全是在记笔记。

到现在,每篇文章都会认认真真画图。

但是这种方式并没有什么错,如果你选择了这种方式,就不要想着自己的文章为什么没人看,这就和上学时你的笔记是一样的,同学是不会看的,而且为什么要看你的笔记?有这个时间看一些官方的文章不是更值吗?

但是当时不懂,我第一开始的想法是通过记笔记的方式能让我的技术有一些进步,不甘于日常循环反复的 CRUD。事实上我也确实是这样做的,所以才有了后来的 100+ 篇原创技术文章。

这个目标一定要找好,如果你做公众号纯碎是想挣钱的话,那么建议不要走原创博主这条路线,否则你挣的都是辛苦钱

为什么我说的是辛苦钱?可能大家看到了自媒体接广告多么多么挣钱,但是这背后熬了多少次夜,起了多少次早,只有自己知道。

比如现在是早上 4.27 ,我又坐在电脑前淦文章了。

image.png

一些圈内的小伙伴给我起了很多昵称,比如刘肝?肝帝?我都笑纳了,不过我从来没这么认为,我只是想着能通过技术分享让大家学到点东西,同时实现自己的价值,否则,人生过得太无趣了。

你问我想实现的价值是什么?

我之前看到过有一个大佬写了一本从 Java 基础到主流框架的思想、源码、面试题分享,涵盖面比较全,我就想着有朝一日,我也要写出来这种 PDF,从计算机四大课程作为入手点,延伸到 Java 和其主流框架,中间夹杂着一些 C 语言知识、汇编知识等,这些都搞完了可能就是 bestJavaer 了。

这就是我的 Github,https://github.com/crisxuan/b... 目前还没有什么名气。

100 篇很少很少,但是每年 100 篇很多很多,我希望这份信心和坚持不是三分钟热度和一腔热血。

一些我觉得自己画的比较好的图片

image.png

image.png

image.png

要坚持下去。

技术的提升

写技术分享带来最大的一个好处就是技术的提升,有的时候确实是 倒逼 自己输出。如果一周没有写出来一篇文章,整个人会非常难受,所以有的时候为了这个目标,不得不熬夜或者早起。倒逼自己输出的好处就是,你能够系统的学习一些知识,让自己更快的成长。在做技术博主之前,我从来没有想过还能学习到操作系统这个层次,更不要说系统性的学习,但是今年这半年以来,真的是快要把 《现代操作系统》学完了。

但是学完了和学会了不一样,学完了只能你的视野更加开阔,和其他人有的聊,能够定位问题所出现的原因、涉及的相关知识点,从而有效的查资料从而解决排查和解决问题。

学会了就是另一个纬度 的事情了,学完了和学会了之前差着时间呢!我能在半年内学完一本硬核书,但是肯定做不到在半年时间内学会一本硬核书。

一个技术点,你能否站在现在的角度把它写深或者写全或者写的通俗易懂?一篇文章,你能否把它的相关知识写满写全?这些每个原创博主需要考虑的事情。你想给读者带来什么,这就是你的 IP

认识了非常多的小伙伴

自从做起来技术博主之后,真的太多小伙伴加我微信联系了,真的非常欣慰和感谢,感谢你们的认可和支持,这将会是我继续淦文的十足动力。

加我微信联系的有很多小伙伴,我可能无法一一回复(因为真的很忙),这里给大家说一声抱歉。再者,如果你可以像下面一样自我介绍一下就更好啦。

image.png

这可能是我看过最好的自我介绍了。

所以我非常希望能和每位小伙伴成为朋友,哎又要说但是了,真的是时间不允许。但是像是上面这样 用心 的自我介绍,我肯定会记得你的,因为上面这个聊天记录,也是我翻了好久的。

我一直认为我这个人挺 low 的,但是自从认识了这么多优秀的小伙伴们,我发现我简直 low 到爆了。有太多优秀的人才了。

有高一就开始学 C 的、有北大研究生、有 985 大学教授、有北美博士生,还有虽然学历不高,但是对技术拥有无限热枕的大专生,很幸运能够认识你们。

除了读者之外,还有很多优秀的同行。

获得一些小成就

思否 Top Writer ,年度最佳写作者,这个含金量很重。思否还给我寄了很多卫衣奖励,我至今还在穿。

image.png

博客园 2 年我收获了 450 + 个粉丝,我知道博客园的粉丝都比较优质,一般都是工作几年的大佬,所以这个数字,让我充满了成就感。希望有朝一日能够获得博客园的 推荐博客 荣誉,也希望博客园可以多给我的文章进行推荐啦。

image.png

掘金一年我就升到了 LV5 的等级,倔力值为

image.png

感觉明年升到 LV6 ,成为 掘金贡献者 指日可待呀。

这个是头条青云计划的奖励,赏金 1000 元,也是我见过奖励最大的平台。果然宇宙条舍得让创作者们恰饭。

image.png

我的一篇文章 《Java核心基础知识总结》 获得了 Infoq 的官方推荐还有池老板的推荐,让我倍感荣幸,同时 infoq 也给我寄了很多非常棒的奖励

image.png

image.png

CSDN 无疑是对我帮助最大的社区了,自从认真写博客以来,红月和刘成还有各位 CSDN 小编们都对我帮助很大,给予我写作的信心,也让我收获了 博客专家原力计划王者 的荣誉称号。

image.png

也有幸收到了 CSDN 定制的月饼,这个月饼非常赞

image.png

同时也感谢异步社区的认可,我荣获了 2020 年度最佳合作伙伴的称号

继续加油。

写了六本 PDF

这是我最值得炫耀的事情了,是的,我一年的时间把公众号的文章汇总成了六本 PDF,它们分别是

  • 《Java 核心技术总结》
  • 《HTTP 核心总结》
  • 《程序员必知的基础知识》
  • 《操作系统核心总结》
  • 《Java V2.0》
  • 《面试题总结》

这些 PDF 你可以在我的公众号 Java建设者 回复 cxuan 获取。

image.png

这些 PDF 并不是完整版,而且也会产生笔误,希望小伙伴们可以提出来,下一版进行更新

image.png

我会慢慢更新,欢迎读者朋友们多多关注我的公众号获取最新的更新信息。

当然,我的 Github 也收录了这些文章

我的 github

其中我的操作系统 PDF 也被国内某大学作为学习的参考资料了。

image.png

每日一题群

这同样是 2020 年我觉得做的非常有意义的一件事情,每天都会抛出来一个问题让大家探讨,目前还在更新,每日一题会包括 Java 方向、计算机基础方向、MySQL 方向、框架方向的一些面试题,目前已坚持四个月了(中间断隔了一段时间)。刚开始大家的热枕非常高,但是渐渐的回答的人慢慢少了下去。这也难怪,毕竟不是每个人都有时间每天回答问题,不过我希望这些面试题能够给你方向,因为很多小伙伴们都反映面试官出的题就是我群里发出来的题了

image.png

当然我欢迎你的加入,你可以在 Java建设者 公众号回复 交流 备注 每日一题 我拉你进群。

囤书

我个人有很强烈的囤书癖好,目前已经囤了各大出版社的经典书籍了。

原谅我还在租房,所以没弄书架,我估计搬家的时候能让我痛不欲生

你问我看没看完,当然没看完了,如果有生之年能够刷完这些书,那么这一辈子是不是就满足了呢?

好了,以上就是我这一年来主要做的事情了。其实每天都过的很有意义,也比较喜欢现在自己的这种状态,其实身居二线离家近做点自己的事情,也很香的不是吗?

展望 2021

《钢铁是怎样练成的》中有一句经典的话语

一个人的生命是应该这样度过的,当他回首往事的时候,不因虚度年华而悔恨,也不因碌碌无为而羞耻,这样他才能够说过好了这一生

2020 虽然经历了全球疫情、自然灾害、经济危机、战火纷争,内卷。。。。。。但却依然没有打到我们,在各种外部因素的摧残中,活下去,你就成功了。

所以 2021 年没有特别宏大的蓝图和愿景,只有六个字送给自己

坚持并活下去

勤勉、真诚、见贤思齐、不断学习才是自媒体或者说原创博主带给读者最大的财富。

查看原文

赞 3 收藏 0 评论 2

bigsai 发布了文章 · 2020-12-03

数据结构与算法—一文搞懂线性表(顺序表、链表)

原创公众号:bigsai 文章收藏在GitHub

前言

通过前面数据结构与算法前导我么知道了数据结构的一些概念和重要性,那么我们今天总结下线性表相关的内容。当然,我用自己的理解解分享给大家。

其实说实话,可能很多人依然分不清线性表,顺序表,和链表之间的区别和联系!

  • 线性表:逻辑结构, 就是对外暴露数据之间的关系,不关心底层如何实现。
  • 顺序表、链表:物理结构,他是实现一个结构实际物理地址上的结构。比如顺序表就是用数组实现。而链表用指针完成主要工作。不同的结构在不同的场景有不同的区别。

对于java来说,大家都知道List接口类型,这就是逻辑结构,因为他就是封装了一个线性关系的一系列方法和数据。而具体的实现其实就是跟物理结构相关的内容。比如顺序表的内容存储使用数组的,然后一个get,set,add方法都要基于数组来完成,而链表是基于指针的。当我们考虑对象中的数据关系就要考虑指针的属性。指针的指向和value。

下面用一个图来浅析线性表的关系。可能有些不太确切,但是其中可以参考,并且后面也会根据这个图举例。
在这里插入图片描述

线性表基本架构

对于一个线性表来说。不管它的具体实现方法如何,我们应该有的函数名称实现效果应该一致。你也可以感觉的到在一些结构的设计。比如List的ArraylistLinkedList。Map的HashMap和currentHashMap他们的接口api都是相同的,但是底层设计实现肯定是有区别的。

所以,基于面向对象的编程思维,我们可以将线性表写成一个接口,而具体实现的顺序表和链表可以继承这个接口的方法,提高程序的可读性。

还有一点比较重要的,记得初学数据结构与算法时候实现的线性表都是固定类型(int),随着知识的进步,我们应当采用泛型来实现更合理。至于接口的具体设计如下:

package LinerList;
public interface ListInterface<T> {    
    void Init(int initsize);//初始化表
    int length();
    boolean isEmpty();//是否为空
    int ElemIndex(T t);//找到编号
    T getElem(int index) throws Exception;//根据index获取数据
    void add(int index,T t) throws Exception;//根据index插入数据
    void delete(int index) throws Exception;
    void add(T t) throws Exception;//尾部插入
    void set(int index,T t) throws Exception;
    String toString();//转成String输出    
}

顺序表

顺序表是基于数组实现的,所以一些方法要基于数组的特性。对于顺序表应该有的基础属性为一个数组data和一个length.

还有需要注意的是初始化数组的大小,你可以固定大小,但是笔者为了可用性如果内存不够将扩大二倍。当然这样很可能因为空间使用问题造成很大的浪费

一些基本的额方法就不说了,下面着重讲解一些初学者容易混淆的概念和方法实现。这里把顺序表比作一队坐在板凳上的人。

插入

add(int index,T t)
其中index为插入的编号位置,t为插入的数据
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
-根据图片你就很好理解插入操作。当插入一个index时候,他的后面所有元素都要后移一位。你可以看的出插入时候整个操作的臃肿性。所以这也是顺序表性能表现最差的地方,频繁的插入,删除。

删除

同理,删除也是非常占用资源的。原理和插入类似,不过人走了,空一个小板凳后面的人需要往前挪
在这里插入图片描述

其他操作

其他操作就很简单了。比如如果按照编号获取数据getElem(int index),你可以直接根据数据坐标返回。a[index],而其他操作,可以通过遍历直接操作数组即可。

链表

我想,表应该是很多人感觉很绕的东西,这个很大原因可能因为指针。很多人说java没指针,其实java他也有隐形指针。只不过不能直接用罢了。

指针建立的数据关系往往比数组这些要抽象的多。对于指针域,你把他当成一个对象就好了,不过这个对象指向的是另一个同等级对象。对于这个关系,你可以比作每个person类。每个person类都有老公(老婆),而这个老公老婆也是一个实际对象,可以理解这更像一种逻辑约定关系,而不是硬生生的关系吧。在这里插入图片描述
指针你可以考虑成脑子记忆。上面的顺序表我们说它有序因为每个小板凳(数组)编号,我们可以根据这个来确定位置。而对于链表来说,你可以看作成一个站在操场上的一队人。而他的操作也略有不同,下面针对一些比较特殊和重要的进行归纳。

基本结构

对于线性表,我们只需要一个data数组和length就能表示基本信息。而对于链表,我们需要一个node(head头节点),和length,当然,这个node也是一个结构体。

class node<T>{
    T data;//节点的结果
    node next;//下一个连接的节点
    public node(){}
    public node(T data)
    {
        this.data=data;
    }
    public node(T data, node next) {
        this.data = data;
        this.next = next;
    } 
}

当然,这个节点有数据域指针域。数据域就是存放真实的数据,而指针域就是存放下一个node的指针。所以相比顺序表,如果用满数组情况下,链表占用更多的资源,因为它要存放指针占用资源。
在这里插入图片描述

插入

add(int index,T t)
其中index为插入的编号位置,t为插入的数据
加入插入一个节点node,根据index找到插入的前一个节点叫pre。那么操作流程为

  1. node.next=pre.next如下1的操作,将插入节点后面联系起来。此时node.next和pre.next一致。
  2. pre.next=node因为我们要插入node,而node链可以替代pre自身的next。那么直接将pre指向node。那么就相当于原始链表插入了一个node。

在这里插入图片描述
在这里插入图片描述

带头节点与不带头节点

在这里插入图片描述
很多人搞不清什么是带头节点不带头节点。带头节点就是head节点不放数据,第0项从head后面那个开始数。而不带头节点的链表head放数据,head节点就是第0位
主要区别

  • 带头节点和不带头节点的主要区别就在插入删除首位,尤其是首位插入。带头节点找元素需要多遍历一次因为它的第一个head节点是头节点,不存数据(可看作一列火车的火车头)。而方便的就是带头节点在首位插入更简单。因为插入第0位也是在head的后面
  • 而不带头节点的链表就需要特殊考虑首位。因为插入第0位其实是插入head的前面。假设有head,插入node。具体操作为:

在这里插入图片描述

  1. node.next=head;(node指向head,node这条链成我们想要的链)
  2. head=node;(很多人想不明白,其实这个时候node才是插入后最长链的首位节点,head在他的后面,而在链表中head通常表示首位节点,所以head不表示第二个节点,直接"="node节点。这样head和node都表示操作完成的链表。但是对外暴露的只有head。所以head只能指向第一个节点!)

插入尾

  • 而在插入尾部的时候,需要注意尾部的nextnull。不能和插入普通位置相比!

删除

在这里插入图片描述
按照index移除:delete(int index)

  • 找到该index的节点node。node.next=node.next.nex

按照尾部移除(拓展):deleteEnd()
这个方法我没有写,但是我给大家讲一下,按照尾部删除的思想就是:

  1. 声明一个node为head。
  2. node.next!=nullnode=node.next 指向下一个
  3. node.next==null时候。说明这个节点时最后一个。你可以node=null。这个这个node的前驱pre的next就是null。这个节点就被删除了。

头部删除(带头节点)

  • 带头节点的删除和普通删除一直。直接head.next(第1个元素)=head.next.next(第二个元素)
  • 这样head.next就直接指向第二个元素了。第一个就被删除了

头部删除(不带头节点)

  • 我们知道不带头节点的第一个就是存货真价实的元素的。不带头节点删除也很简单。直接将head移到第二位就行了。即:head=head.next

在这里插入图片描述

其他

  • 对于其他操作,主要时结合查找。而单链表的查找时从head开始。然后另一个节点team=headhead.next。然后用这个节点不停的等于它指向的next去查找我们需要的内容即while(循环条件){team=team.next}类似。
  • 不同教程和人写的线性表也不一致,这里只给出一个样例学习使用而并不是标准,希望大家审视。
  • 在实现上用了带头节点的链表实现,因为比较方便管理,不需要很多if else.

代码实现

顺序表

package LinerList;

public class seqlist<T> implements ListInterface<T> {
    private Object[] date;//数组存放数据
    private int lenth;
    public seqlist() {//初始大小默认为10
        Init(10);
    }

    public void Init(int initsize) {//初始化
        this.date=new Object[initsize];
        lenth=0;        
    }
    public int length() {        
        return this.lenth;
    }

    public boolean isEmpty() {//是否为空
        if(this.lenth==0)
            return true;
        return false;
    }

    /*
     * * @param t    
     * 返回相等结果,为-1为false
     */
    public int ElemIndex(T t) {
        // TODO Auto-generated method stub
        for(int i=0;i<date.length;i++)
        {
            if(date[i].equals(t))
            {
                return i;
            }
        }
        return -1;
    }

    /*
     *获得第几个元素
     */
    public T getElem(int index) throws Exception {
        // TODO Auto-generated method stub
        if(index<0||index>lenth-1)
            throw new Exception("数值越界");
        return (T) date[index];
    }
    
    public void add(T t) throws Exception {//尾部插入
         add(lenth,t);
    }

    /*
     *根据编号插入
     */
    public void add(int index, T t) throws Exception {
        if(index<0||index>lenth)
            throw new Exception("数值越界");
        if (lenth==date.length)//扩容
        {
            Object newdate[]= new Object[lenth*2];
            for(int i=0;i<lenth;i++)
            {
                newdate[i]=date[i];
            }
            date=newdate;
        }
        for(int i=lenth-1;i>=index;i--)//后面元素后移动
        {
            date[i+1]=date[i];
        }
        date[index]=t;//插入元素
        lenth++;//顺序表长度+1
        
    }

    public void delete(int index) throws Exception {
        if(index<0||index>lenth-1)
            throw new Exception("数值越界");
        for(int i=index;i<lenth;i++)//index之后元素前移动
        {
            date[i]=date[i+1];
        }
        lenth--;//长度-1    
    }

    @Override
    public void set(int index, T t) throws Exception {
        if(index<0||index>lenth-1)
            throw new Exception("数值越界");
        date[index]=t;
    }
    public String  toString() {
        String vaString="";
        for(int i=0;i<lenth;i++)
        {
            vaString+=date[i].toString()+" ";
        }
        return vaString;
        
    }
}

链表

package LinerList;

class node<T>{
    T data;//节点的结果
    node next;//下一个连接的节点
    public node(){}
    public node(T data)
    {
        this.data=data;
    }
    public node(T data, node next) {
        this.data = data;
        this.next = next;
    }
   
}
public class Linkedlist<T> implements ListInterface<T>{

    node head;
    private int length;
    public Linkedlist() {
        head=new node();
        length=0;
    }
    public void Init(int initsize) {
        head.next=null;
        
    }

    public int length() {
        return this.length;
    }

    
    public boolean isEmpty() {
        if(length==0)return true;
        else return false;
    }

    /*
     * 获取元素编号
     */
    public int ElemIndex(T t) {
        node team=head.next;
        int index=0;
        while(team.next!=null)
        {
            if(team.data.equals(t))
            {
                return index;
            }
            index++;
            team=team.next;
        }
        return -1;//如果找不到
    }

    @Override
    public T getElem(int index) throws Exception {
        node team=head.next;
        if(index<0||index>length-1)
        {
            throw new Exception("数值越界");
        }
        for(int i=0;i<index;i++)
        {
            team=team.next;
        }
        return (T) team.data;
    }


    public void add(T t) throws Exception {
        add(length,t);
        
    }
    //带头节点的插入,第一个和最后一个一样操作
    public void add(int index, T value) throws Exception {
        if(index<0||index>length)
        {
            throw new Exception("数值越界");
        }
        node<T> team=head;//team 找到当前位置node
        for(int i=0;i<index;i++)
        {
             team=team.next;
        }
        node<T>node =new node(value);//新建一个node
        node.next=team.next;//指向index前位置的下一个指针
        team.next=node;//自己变成index位置    
        length++;
    }
    

    @Override
    public void delete(int index) throws Exception {
        if(index<0||index>length-1)
        {
            throw new Exception("数值越界");
        }
        node<T> team=head;//team 找到当前位置node
        for(int i=0;i<index;i++)//标记team 前一个节点
        {
             team=team.next;
        }
        //team.next节点就是我们要删除的节点
        team.next=team.next.next;
        length--;
    }

    @Override
    public void set(int index, T t) throws Exception {
        // TODO Auto-generated method stub
        if(index<0||index>length-1)
        {
            throw new Exception("数值越界");
        }
        node<T> team=head;//team 找到当前位置node
        for(int i=0;i<index;i++)
        {
             team=team.next;
        }
        team.data=t;//将数值赋值,其他不变
        
    }

    public String toString() {
        String va="";
        node team=head.next;
        while(team!=null)
        {
            va+=team.data+" ";
            team=team.next;
        }
        return va;
    }

}

测试与结果

package LinerList;
public class test {
    public static void main(String[] args) throws Exception {
        // TODO Auto-generated method stub
        System.out.println("线性表测试:");
        ListInterface<Integer>list=new seqlist<Integer>();
        list.add(5);
        list.add(6);
        list.add(1,8);
        list.add(3,996);
        list.add(7);
        System.out.println(list.ElemIndex(8));
        System.out.println(list.toString());
        list.set(2, 222);
        System.out.println(list.toString());
        list.delete(4);
        System.out.println(list.toString());
        System.out.println(list.length());    
        
        System.out.println("链表测试:");
        list=new Linkedlist<Integer>();
        list.add(5);
        list.add(6);
        list.add(1,8);
        list.add(3,996);
        list.add(7);
        System.out.println(list.ElemIndex(8));
        System.out.println(list.toString());
        list.set(2, 222);
        System.out.println(list.toString());
        list.delete(4);
        System.out.println(list.toString());
        System.out.println(list.length());    
    }
}

输出:

线性表测试:
1
5 8 6 996 7
5 8 222 996 7
5 8 222 996
4
链表测试:
1
5 8 6 996 7
5 222 6 996 7
5 222 6 996
4

总结

这里的只是简单实现,实现基本方法。链表也只是单链表。完善程度还可以优化。如果有错误还请大佬指正

单链表查询速度较慢,因为他需要从头遍历。如果频繁操作尾部,可以考虑链表中不仅有head在加尾tail节点。而顺序表查询速度虽然快但是插入很费时费力。实际应用根据需求选择

java中的Arraylist和LinkedList就是两种方式的代表,不过LinkedList使用双向链表优化,并且jdk的api做了大量优化。所以大家不用造轮子,可以直接用,但是还是很有学习价值的。

如果有不理解或者不懂的可以联系交流讨论。

原创不易,bigsai请朋友们帮两件事帮忙一下:

  1. 点赞、关注支持一下, 您的肯定是我在思否创作的源源动力。
  2. 微信搜索「bigsai」,关注我的公众号,分享更多内容!

咱们下次再见!

查看原文

赞 3 收藏 1 评论 0

认证与成就

  • 获得 96 次点赞
  • 获得 2 枚徽章 获得 0 枚金徽章, 获得 0 枚银徽章, 获得 2 枚铜徽章

擅长技能
编辑

开源项目 & 著作
编辑

(゚∀゚ )
暂时没有

注册于 2019-08-11
个人主页被 3.9k 人浏览