Task01 01.01 数据结构与算法+Leetcode入门¶
Chapter 1¶
数据结构是程序的骨架，算法是程序的灵魂———— Niklaus Emil Wirth
为此我们需要了解两个概念：
-
什么是算法：
-
什么是数据结构：
所谓 算法 ：就是解决问题的方法/步骤： 这里举个特别经典的例子：把大象放入冰箱需要几步？ 很显然需要三步：打开冰箱、放入大象、关闭冰箱。那么由此联想到上述的算法的定义，我们很显然可以看出，把大象放入冰箱这一个问题的算法就是上述的三步。 换句话说，解决问题的方法，就是算法。
所谓 数据结构 则是数据在计算机中的表示与相关的操作的集合，我们都知道常见的数据结构有：表、树、图、链式存储、线性存储这些概念，从这方面考虑即可
当你学会掌握 算法 与 数据结构 后，能够将两者有机结合起来，那么我们就可以写出一个很好的程序。当然，仅仅写出一个可以成功解决问题的程序还不够，我们所要追求的是效率更高，更简单，占用空间更少的高效的程序。而这也就要求我们进一步去不断的优化算法与数据结构，从而才能不断提升程序的效率（这也是当前算法研究的主要方向，设计/发现更高效的算法）。
数据结构¶
数据结构（Data Structure） ：是带有结构特性的数据元素的集合
简单来讲：数据结构 就是：数据的组织结构、用来组织和存储数据。 其又分为： 逻辑结构 、和 物理结构
数据结构的逻辑结构¶
逻辑结构（Logical Structure） ：数据元素之间的相互关系
逻辑结构根据元素之间的关系可以分为以下四种:
1.集合结构¶
集合结构（Set） ：数据元素同属于一个集合，除此以外无其他关系。
集合结构当中的元素时无序且唯一存在的（这个可以参考数学当中集合的定义，一集合具有确定性、无序性，和互异性）
1. 确定性：集合当中的元素必须是具有相同特征的确定事物
2. 无序性：集合当中各个元素之间并没有顺序，调换顺序并不影响集合本身
3. 互异性：集合当中的元素保证彼此互不相同
2.线性结构¶
线性结构 ：数据元素之间属于一对一关系
各个元素之间具有相关联性：比如位置上的相邻（数组这种元素位置相邻的）、亦或者逻辑上的相邻（链式存储）还有由此衍生出来的栈、队列、哈希表
3.树形结构¶
树形结构 ：数据结构之间是一对多的关系
以最简单的为例：二叉树，自根节点往下，每一个节点有两个子树（左子树和右子树）具体的图如下：
当然除此之外，还有多叉树、森林等一些复杂的树。
4. 图形结构：¶
图形结构 ：数据元素是 多对多 的关系
图这种数据结构，由边和节点组成，按照边是有向还是无向可以分为 有向图 和 无向图 等。
1.2物理结构¶
物理结构（Physical Structure）：数据在计算机当中实际的存储方式
数据在计算机当中存储方式一般是这两种：顺序存储结构 、链式存储结构 ，其中顺序存储结构类似数组（数据存储在内存当中是相邻的），链式存储结构是指数据在计算机存储当中是可以不安相邻顺序存储的，但是通过指针的方式使得在计算机当中物理存储位置不同的数据相关联到了一起。
1.顺序存储结构¶
顺序存储结构（Sequential Storage Structure）：数据在计算机内存当中以相邻的方式进行存储。
顺序存储当中，由于数据都是相邻存储，所以具有 随机访问（例如访问数组第五个数据）方便的优点。但是同时，由于这种相邻的数据存储方式，导致数据在顺序结构当中修改很困难（譬如在数组中删除中间的一个数，则需要将该数清楚，且将其之后的数依次前移）需要很长的时间。 顺序结构如下：
这种结构的优点是：简单、易理解，且实际占用最少的存储空间。缺点是：需要占用一片地址连续的存储单元；并且存储分配要事先进行；另外对于一些操作的时间效率较低（移动、删除元素等操作）。（具体解释如上）
2.链式存储结构¶
链式存储结构（Linked Storage Structure）：数据可以不存在于相邻的单元之中，但是在使用逻辑，调用上，其保证处于逻辑相邻
具体的链式结构示意图如下：
在链式存储结构当中，由于相邻结点之间并无强制的相邻关系，所以对该组数据当中的节点数据进行增删改的时候很方便，只需要修改节点间的逻辑关系即可，但是同时由于节点数据并不处于相邻的存储空间当中，随机访问 数据的时候会使得必须从该段数据的一端开始遍历，直到找到所求数据为止。
链式存储结构中，逻辑上相邻的数据元素在物理地址上可能相邻，可也能不相邻。其在物理地址上的表现是随机的。链式存储结构中，一般将每个数据元素占用的若干单元的组合称为一个链结点。每个链结点不仅要存放一个数据元素的数据信息，还要存放一个指出这个数据元素在逻辑关系的直接后继元素所在链结点的地址，该地址被称为指针。换句话说，数据元素之间的逻辑关系是通过指针来间接反映的。
这种结构的优点是：存储空间不必事先分配，在需要存储空间的时候可以临时申请，不会造成空间的浪费；一些操作的时间效率远比顺序存储结构高（插入、移动、删除元素）。缺点是：不仅数据元素本身的数据信息要占用存储空间，指针也需要占用存储空间，链式存储结构比顺序存储结构的空间开销大。
Chapter 2 01.01.04 练习题¶
1.1 1.2235. 两整数相加¶
题目大意
描述：给定两个整数 num1 和 num2。
要求：返回这两个整数的和。
说明：
\(100\leq num1,num2\leq 100\)
示例 1： 输入：num1 = 12, num2 = 5 输出：17 解释：num1 是 12，num2 是 5，它们的和是 12 + 5 = 17，因此返回 17。
示例 2： 输入：num1 = -10, num2 = 4 输出：-6 解释：num1 + num2 = -6，因此返回 -6。
解题代码如下：
class Solution:
def sum(self, num1: int, num2: int) -> int:
return num1+num2
2.1 2.1929. 数组串联¶
题目大意
描述：给定一个长度为 n 的整数数组 nums。
要求：构建一个长度为 2 * n 的答案数组 ans，答案数组下标从 0 开始计数 ，对于所有 0 <= i < n 的 i ，满足下述所有要求：
ans[i] == nums[i]。 ans[i + n] == nums[i]。 具体而言，ans 由两个 nums 数组「串联」形成。
说明： \(n==nums.length\) \(1\leq n\leq 1000\) \(1\leq nums[i]\leq 1000\)
示例：
输入：nums = [1,2,1] 输出：[1,2,1,1,2,1] 解释：数组 ans 按下述方式形成： - ans = [nums[0],nums[1],nums[2],nums[0],nums[1],nums[2]] - ans = [1,2,1,1,2,1]
输入：nums = [1,3,2,1] 输出：[1,3,2,1,1,3,2,1] 解释：数组 ans 按下述方式形成： - ans = [nums[0],nums[1],nums[2],nums[3],nums[0],nums[1],nums[2],nums[3]] - ans = [1,3,2,1,1,3,2,1]
解题代码：
class Solution:
def getConcatenation(self, nums: List[int]) -> List[int]:
length=len(nums)
for i in range(length):
nums.append(nums[i])
return nums
append函数添加即可
3.0771. 宝石与石头¶
3.1 题目大意 描述：给定一个字符串 jewels 代表石头中宝石的类型，再给定一个字符串 stones 代表你拥有的石头。stones 中每个字符代表了一种你拥有的石头的类型。
要求：计算出拥有的石头中有多少是宝石。
说明：
- 字母区分大小写，因此 a 和 A 是不同类型的石头。
- \(1\leq jewels.length,stones.length \leq 50\)
jewels和stones仅由英文字母组成。jewels中的所有字符都是唯一的。
示例：
输入：jewels = "aA", stones = "aAAbbbb"
输出：3
输入：jewels = "z", stones = "ZZ"
输出：0
解题代码：
class Solution:
def numJewelsInStones(self, jewels: str, stones: str) -> int:
res=0
for i in range(len(jewels)):
for j in range(len(stones)):
if stones[j]==jewels[i]:
res+=1
return res