DS博客作业07 - HelloWorld开发者社区

#1.本周学习总结（0--2分） ##1.思维导图 DS博客作业07

##2.谈谈你对查找运算的认识及学习体会。

本章主要学习了多种的数据查找方法，以及各种查找方法的评价指标。
通过学习，知道了查找分为两种，一种是静态查找，一种是动态查找。静态查找，就是仅仅作查询和检索的功能，而动态查找则是在静态查找的基础上增添了增加数据和删除数据的功能。通过查找算法的评价指标（ASL），我们能比较各算法的优劣。ASL是指找到（找不到）查找表中记录平均需要的关键字比较次数。
在线性表的查找中，学习了三种查找方法：顺序查找、二分查找、分块查找。顺序查找就是我们最初的简单算法，将数组遍历一遍查找数据，二分查找则是顺序查找的改进，每一次取中间值进行比较，从效率上看，时间复杂度从顺序查找的O(n)变为了O(log2n)，效率大大提高。分块查找就是将数据分为一个一个的有序块，是一种介于顺序查找和二分查找查找方法。
除了线性表的查找外，查找的方法还有跟我们这学期所学的树有关——树表。树表的查找是利用每层可以存放2的n-1次个数（n为结点所在层数），使得数据的比较次数减少到树的高度。
总的来说，这章的内容并不算很难，算法思路很好理解，主要是树表的代码实现上会有一些难度。

#2.PTA实验作业（6分）本周要求挑3道题目写设计思路、调试过程。设计思路用伪代码描述。题目选做要求：

原则上题目选择越难，代码量越大分值越高。

##2.1 6-3 二叉搜索树中的最近公共祖先

在一棵树T中两个结点u和v的最近公共祖先(LCA)，是树中以u和v为其后代的深度最大的那个结点。现给定某二叉搜索树(BST)中任意两个结点，要求你找出它们的最近公共祖先。

###2.1.1设计思路（伪代码）

//设计思路
查找两个结点的结果只有两种情况：节点存在，找得到公共祖先；结点不存在，不存在公共祖先一说。
节点存在的情况有一下几种：两个结点分别在左右子树、全在左子树、全在右子树、有一个结点为对方的父亲结点。总的来说，代码实现上可以分成两块，一块是有一个结点为对方的父亲结点的情况，另一块是两结点分别在所遍历结点的左右子树的情况。无论两个数据是全在该遍历的结点的左子树，还是右子树，都不符合最近的要求，只有出现了上面那两种情况的时候，该遍历结点才是最近的公共祖先。


//伪代码（LCA函数）
if 树为空 then
    返回 ERROR
end if
if u或v不存在在树中 then
    返回 ERROR
end if
if u或v是该遍历是的结点时 then //表明其中一个为对方的父亲
    返回 该结点的Key值
end if
if u、v分别在该遍历结点的左右子树时 then
    返回 该结点的Key值
end if
if 该结点的Key值小于u的值 then
    调用递归，进入该结点的右孩子结点
else
    调用递归，进入该结点的左孩子结点
end if

###2.1.2代码截图（注意，截图，截图，截图。不要粘贴博客上。） DS博客作业07

###2.1.3本题PTA提交列表说明。 DS博客作业07

Q1:这道题老师上课的时候讲过，所以做起来挺简单的，然后
A1:然后PTA下面的编译器输出部分一堆的error，认认真真地看完后……所有的Key都写成了key，然后一个左括号变成了*……，不认真看题，不好好看打了什么内容的下场。 n条几乎一模一样的错误提示……
Q2:全部k改成K后，想着终于搞定了，结果答案错误，提示我空树的时候答案错误
A2:当时在想，空树的情况我不是考虑了吗？为什么还会错，后来检查了一遍代码，好吧，写顺手了……
写博客的时候，突然想到不用判断结点存在好像也是可以的，直接找不到结点就通过T==NULL这个条件判断不就好了，然后就改了代码去PTA上提交了一下，好像不行的样子。在一思索，好像是不行，网一树里就有那么一个点刚好符合最近祖先的条件，但是树还没有遍历到树的最后一层，没法证明它存不存在，还是要写一个函数来判断数据是否存在。 ##2.2 7-1 QQ帐户的申请与登陆

实现QQ新帐户申请和老帐户登陆的简化版功能。最大挑战是：据说现在的QQ号码已经有10位数了。

###2.2.1设计思路（伪代码）

//设计思路
利用map容器的 键+值且键不能重复的特点，保证账号不会重复，用法与哈希表相似，查找的时间复杂度为O(1)。


//伪代码
定义int型变量n，表示操作次数；User型数组user，存放账号密码；map型变量QQ，char型变量choice，用于表示操作类型
for i=0 to n do
    输入操作类型，QQ号、密码；
    if 操作类型为L then//登陆
        if 账号不存在 then
            输出“ERROR: Not Exist”
        else
            if 账号对应的密码不正确 then
                输出"ERROR: Wrong PW"
            else
                输出"Login: OK"
            end if
        end if
    else//注册
        if 账号不存在 then
            输出"New: OK"
            将这组账号密码存入map容器QQ中
        else
            输出"ERROR: Exist"
        end if
    end if
end for

###2.2.2代码截图（注意，截图，截图，截图。不要粘贴博客上。） DS博客作业07 ###2.2.3本题PTA提交列表说明。

Q1:一开始的时候，没想那么多，就想着调用个函数，然后利用顺序查找的方法来做，简单粗暴，结果如下图所示
A1:很好，乖乖想算法吧。然后老师上课的时候介绍了map容器，跟用哈希表差不多，还更简单，于是疯狂改代码
Q2:改完代码，VS上运行正确，到PTA上一提交，编译错误？？？
A2:好吧，继续我的编译器输出查看路程，我少了一个 } （黑人问号.jpg）检查了两边，主函数没少大括号啊……
算了，从头开始看吧，然后，然后，我的结构体的下半部分呢…… 然后，难过，发生了什么，我VS运行的好好的，复制黏贴一下，结构体给我弄没了。。。一半
改回去之后，皆大欢喜。

##2.3 7-2 航空公司VIP客户查询

不少航空公司都会提供优惠的会员服务，当某顾客飞行里程累积达到一定数量后，可以使用里程积分直接兑换奖励机票或奖励升舱等服务。现给定某航空公司全体会员的飞行记录，要求实现根据身份证号码快速查询会员里程积分的功能。

###2.3.1设计思路（伪代码）

//设计思路
利用map容器的特点，用法与哈希表类似


//伪代码
定义字符型数组id[20]；long long型变量distance；
for i=0 to n do
    输入身份证号和航行距离
    if 航行距离小于最小航行距离 then
        令distance等于最小航行距离
    end if
    if 没有乘坐记录 then
        将id、distance的值存入map容器中
    else
        修改map容器中身份证号对应的称作距离的值
    end if
end for
定义int型变量m，查找数目
输入m
for i=0 to m do
    输入id号
    if 该身份证号不在存档中 then
        输出"No Info"
    else
        输出该身份证号所对应的里程
    end if
end for

###2.3.2代码截图（注意，截图，截图，截图。不要粘贴博客上。） DS博客作业07

###2.3.3本题PTA提交列表说明。 DS博客作业07

Q1:这道题，看题目超简单，跟前面的QQ那道题是类似的，就多了一个map值的变化，然鹅，编译错误。
A1:一看编译器输出，好吧，忘记换成c++的了
Q2:改回c++编译器之后，部分正确，一看错误提示，还运行超时……思路没毛病，代码好像有点点问题，map容器那块的函数有点错，修修改改，感觉有无数次的多种错误，运行超时，运行超时，运行超时的……然后，找了同学要代码，跟她的思路一样，就比她多了个结构体而已，不知所措。
后面直接放弃，跟她一样，把结构体去掉，正确了？？？？！！！！！！总觉得很莫名其妙……

#3、阅读代码（-2--2分）找一份和查找运算相关代码，谈谈你对这个代码认识体会。

考研题种关于查找、二叉搜索树内容。 ACM、PTA天梯赛、leecode面试刷题网站,找查找相关题目阅读分析。请按照下面内容填写代码阅读内容。请未必认真完成，如果发现应付，没有介绍代码思路、体会等扣分。

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

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
你的算法时间复杂度必须是 O(log n) 级别。
如果数组中不存在目标值，返回 [-1, -1]。
 - 示例 1:
输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]
 - 示例 2:
输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]

作者：LeetCode
链接：https://leetcode-cn.com/problems/two-sum/solution/zai-pai-xu-shu-zu-zhong-cha-zhao-yuan-su-de-di-yi-/
来源：力扣（LeetCode）

##3.2 解题思路

方法一：线性扫描

首先，我们对 nums 数组从左到右做线性遍历，当遇到 target 时中止。如果我们没有中止过，那么 target 不存在，我们可以返回“错误代码” [-1, -1] 。如果我们找到了有效的左端点坐标，我们可以坐第二遍线性扫描，但这次从右往左进行。这一次，第一个遇到的 target 将是最右边的一个（因为最左边的一个存在，所以一定会有一个最右边的 target）。我们接下来只需要返回这两个坐标。时间复杂度：O(n)；空间复杂度：O(1)
方法二：二分查找

总体算法工作过程与线性扫描方法类似，除了找最左和最右下标的方法。这里我们仅仅做几个微小的调整，用这种修改过的二分查找方法去搜索这个排过序的数组。首先，为了找到最左边（或者最右边）包含 target 的下标（而不是找到的话就返回 true ），所以算法在我们找到一个 target 后不能马上停止。我们需要继续搜索，直到 lo == hi 且它们在某个 target 值处下标相同。另一个改变是 left 参数的引入，它是一个 boolean 类型的变量，指示我们在遇到 target == nums[mid] 时应该做什么。如果 left 为 true ，那么我们递归查询左区间，否则递归右区间。考虑如果我们在下标为 i 处遇到了 target ，最左边的 target 一定不会出现在下标大于 i 的位置，所以我们永远不需要考虑右子区间。当求最右下标时，道理同样适用。时间复杂度：O(log2n)；空间复杂度：O(1)

##3.3 代码截图

方法一
方法二

##3.4 学习体会

这道题呢，其实是挺简单的，但是力扣里面难度却显示中等。我一开始的时候，看到这道题，想到的就是方法一，直接用顺序查找的方式做。
后来，我看了力扣里面的题解，发现他有两种做法，另外一种是二分查找法。提升了算法的时间复杂度。
有去看了眼题，好吧，我又不认真看题了，他要求的是用时间复杂度为O(logn)的算法来做，顺序查找简单粗暴，但是时间复杂度达到了O(n)。而二分查找法正好符合条件。
虽然我觉得输入数据的时候，时间复杂度就达到了O(n)，查找的时间复杂度是O(n)还是O(logn)区别并不是很大。但是数据量多起来的时候，还是差挺多的。我们做题的时候也应该尽量去使用那些效率高的算法，而不是怎么简单怎么来。

Android自定义View - Paint画笔作业讲解(5)

Java AQS_共享模式_CountDownLatch源码深度分析

热门文章