W模型

v模型

需求分析 验收测试

概要设计 系统测试

​ 详细设计 集成测试

​ 编码 单元测试

​ V

NC55 最长公共前缀

描述

给你一个长度为 $n$ 的字符串数组 $strs$，编写一个函数来查找字符串数组中的最长公共前缀，返回这个公共前缀。

解法1：纵向扫描

先得到最短的字符串，然后用最短的字符串去一一比较

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution:
    def longestCommonPrefix(self , strs ):
        # write code here
        if len(strs) == 0:
            return ""
        strs.sort(key=lambda x:len(x))
        min_len = len(strs[0]) # 得到最短的长度
        temp = strs[0]
        res = ""
        for i in range(1,min_len+1):
            flag = True
            for cur_str in strs:
                if temp[:i] != cur_str[:i]:
                    flag = False
                    break
            if flag == True:
                res = temp[:i]
        return res

NC17 最长回文子串

描述

对于一个字符串，请设计一个高效算法，计算其中最长回文子串的长度。

给定字符串A以及它的长度n，请返回最长回文子串的长度。

解法一：动态规划

参考题解：题解 | #最长回文子串#_牛客博客 (nowcoder.net)

定义 dp[i][j] 表示 A[i:j] 是否为回文串。

外循环从后向前遍历，i ->[6 0]

内循环从 i 开始向后遍历，直接结束。

每轮内循环的第一次循环可以解决 单个字符的回文串。

每次循环由外向内检测字串是否为回文串。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution:
    def getLongestPalindrome(self, A, n):
        # write code here
        dp = [
            [0 for _ in range(n)]
            for _ in range(n)
        ] # dp[i][j] 表示 A[i:j] 是否为回文串
        max_len = 0
        # 从右到左
        for i in range(n-1,-1,-1):
            
            # 从左到右
            for j in range(i,n):
                cur_len = j- i +1 # 字串长度
                print(A[i:j+1],i,j,A[i],A[j],cur_len)
                if A[i] == A[j]:
                    # cur_len <= 2那么就为回文串，
                    # cur_len > 2： dp[i][j] = dp[i+1][j-1]
                    if cur_len <= 2:
                        dp[i][j] = 1
                    else:
                        dp[i][j] = dp[i+1][j-1]
                if dp[i][j]:
                    print(dp[i][j])
                    max_len = max(max_len,cur_len)
        return max_len

NC127 最长公共字串

描述

给定两个字符串str1和str2,输出两个字符串的最长公共子串

题目保证str1和str2的最长公共子串存在且唯一。

解法：暴力解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution:
    def LCS(self , str1 , str2 ):
        # write code here
        len1 = len(str1)
        len2 = len(str2)
        if len1 < len2:
            min_len = len1
            min_str = str1
            max_str = str2
        else:
            min_len = len2
            min_str = str2
            max_str = str1
        global_max_str = ""
        for i in range(min_len-1,-1,-1):
            for j in range(i,min_len):
                cur_str = min_str[i:j+1]
                if cur_str in max_str:
                    if len(global_max_str) < len(cur_str):
                        global_max_str = cur_str
                print(str2[i:j+1])
        return global_max_str

解法：动态规划

参考评论区：

【数据结构和算法】动态规划解最长公共子串_牛客博客 (nowcoder.net)

注意这题求的是最长公共子串，不是最长公共子序列，子序列可以是不连续的，但子串一定是连续的。

定义 dp[i][j] 表示字符串 str1中的第 i个字符和 str2中 第 j 个字符为最后一个元素所构成的最长公共字串。

如果要求 dp[i][j]，也就是 str1的第 i 个字符和str2的第j个字符为最后一个元素所构成的最长公共字串，我们首先需要判断这两个字符是否相等。

• 如果不相等，那么他们就不能构成公共字串，也就是

  dp[i][j]=0

• 如果相等，我们还需要计算前面相等字符的个数，其实就是 dp[i-1][j-1]，所有

  dp[i][j]=dp[i-1][j-1]+1

其重点是，以i，j分别是str1，str2的结束字符串，当前的结尾字符记录，会在前一个字符记录上进行迭代，同时在迭代过程中记录字串长度，并记住结束位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution:
    def LCS(self , str1 , str2 ):
        # write code here
        maxLength = 0
        maxLastIndex = 0 # 记录最长公共字串最后一个元素在字符串str1中的位置
        len1 = len(str1)
        len2 = len(str2)

        dp = [
            [0 for _ in range(len2+1)]
            for _ in range(len1+1)
        ]

        for i in range(len1):
            for j in range(len2):

                # 递推公式，两个字符相等的情况
                if str1[i] == str2[j]:
                    dp[i+1][j+1] = dp[i][j] + 1

                    # 如果遇到了更长的字串，要更新，记录最长字串的长度
                    if dp[i+1][j+1] > maxLength:
                        maxLength = dp[i+1][j+1]
                        maxLastIndex = i
                else:
                    dp[i+1][j+1] = 0 # 递推公式，两个字符不相等的情况
        
        # 对字符串进行截取
        res = str1[maxLastIndex-maxLength+1:maxLastIndex+1]
        return res

解法二：优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

maxLastIndex = 0  # 
maxLength = 0 # 记录最长公共字串的长度
len1 = len(str1)
len2 = len(str2)

dp = [0 for _ in range(len2+1)]

# print("--")
for i in range(0,len1):
    for j in range(len2-1,-1,-1):
      
        if str1[i] == str2[j]:
            # print(
            dp[j+1] = dp[j] + 1
            # print(i,j,dp[j],dp[j+1])
            
            if dp[j+1] > maxLength:
                maxLength = dp[j+1]
                maxLastIndex = i
        else:
            # 如果存在间隔会在这里置为0
            dp[j+1] = 0  # 递推公式，两个字符不相等的情
# print("---")
# print(dp)
res = str1[maxLastIndex-maxLength+1:maxLastIndex+1]
return res

226. 翻转二叉树

描述

翻转一棵二叉树。

示例：

输入：

1
2
3
4
5

     4
   /   \
  2     7
 / \   / \
1   3 6   9

输出：

1
2
3
4
5

     4
   /   \
  7     2
 / \   / \
9   6 3   1

解法

参考题解

除此之外还可以用bfs。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if root == None:
            return None
        left = self.invertTree(root.left)
        right = self.invertTree(root.right)
        root.right = left
        root.left = right
        return root

一、安卓四大组件

其分别为Activity、Service、Content Provider、Broadcast receiver。

Activity

（1）一个Activity通常就是一个单独的屏幕（窗口）。

（2）Activity之间通过Intent进行通信。

（3）android应用中每一个Activity都必须要在AndroidManifest.xml配置文件中声明，否则系统将不识别也不执行该Activity。

Service

1. service用于在后台完成用户指定的操作。service分为两种：

   • started（启动）：当应用程序组件（如activity）调用startService()方法启动服务时，服务处于started状态。
   • bound（绑定）：当应用程序组件调用bindService()方法绑定到服务时，服务处于bound状态。

2. startService()与bindService()区别：

   • started service（启动服务）是由其他组件调用startService()方法启动的，这导致服务的onStartCommand()方法被调用。当服务是started状态时，其生命周期与启动它的组件无关，并且可以在后台无限期运行，即使启动服务的组件已经被销毁。因此，服务需要在完成任务后调用stopSelf()方法停止，或者由其他组件调用stopService()方法停止。
   • 使用bindService()方法启用服务，调用者与服务绑定在了一起，调用者一旦退出，服务也就终止，大有“不求同时生，必须同时死”的特点。

3. 开发人员需要在应用程序配置文件中声明全部的service，使用<service></service>标签。

4. Service通常位于后台运行，它一般不需要与用户交互，因此Service组件没有图形用户界面。Service组件需要继承Service基类。Service组件通常用于为其他组件提供后台服务或监控其他组件的运行状态。

content provider

1. android平台提供了Content Provider使一个应用程序的指定数据集提供给其他应用程序。其他应用可以通过ContentResolver类从该内容提供者中获取或存入数据。
2. 只有需要在多个应用程序间共享数据是才需要内容提供者。例如，通讯录数据被多个应用程序使用，且必须存储在一个内容提供者中。它的好处是统一数据访问方式。
3. ContentProvider实现数据共享。ContentProvider用于保存和获取数据，并使其对所有应用程序可见。这是不同应用程序间共享数据的唯一方式，因为android没有提供所有应用共同访问的公共存储区。
4. 开发人员不会直接使用ContentProvider类的对象，大多数是通过ContentResolver对象实现对ContentProvider的操作。
5. ContentProvider使用URI来唯一标识其数据集，这里的URI以content://作为前缀，表示该数据由ContentProvider来管理。

broadcast receiver

1. 你的应用可以使用它对外部事件进行过滤，只对感兴趣的外部事件(如当电话呼入时，或者数据网络可用时)进行接收并做出响应。广播接收器没有用户界面。然而，它们可以启动一个activity或serice来响应它们收到的信息，或者用NotificationManager来通知用户。通知可以用很多种方式来吸引用户的注意力，例如闪动背灯、震动、播放声音等。一般来说是在状态栏上放一个持久的图标，用户可以打开它并获取消息。
2. 广播接收者的注册有两种方法，分别是程序动态注册和AndroidManifest文件中进行静态注册。
3. 动态注册广播接收器特点是当用来注册的Activity关掉后，广播也就失效了。静态注册无需担忧广播接收器是否被关闭，只要设备是开启状态，广播接收器也是打开着的。也就是说哪怕app本身未启动，该app订阅的广播在触发时也会对它起作用。

四大组件总结

四大组件的注册

4大基本组件都需要注册才能使用，每个Activity、service、Content Provider都需要在AndroidManifest文件中进行配置。

AndroidManifest文件中未进行声明的activity、服务以及内容提供者将不为系统所见，从而也就不可用。

而broadcast receiver广播接收者的注册分静态注册（在AndroidManifest文件中进行配置）和通过代码动态创建并以调用Context.registerReceiver()的方式注册至系统。

需要注意的是在AndroidManifest文件中进行配置的广播接收者会随系统的启动而一直处于活跃状态，只要接收到感兴趣的广播就会触发（即使程序未运行）。

4大组件的激活

内容提供者的激活：当接收到ContentResolver发出的请求后，内容提供者被激活。

而其它三种组件activity、服务和广播接收器被一种叫做intent的异步消息所激活。

4大组件的关闭

内容提供者仅在响应ContentResolver提出请求的时候激活。

而一个广播接收器仅在响应广播信息的时候激活。所以，没有必要去显式的关闭这些组件。

Activity关闭：可以通过调用它的finish()方法来关闭一个activity。

服务关闭：对于通过startService()方法启动的服务要调用Context.stopService()方法关闭服务，使用bindService()方法启动的服务要调用Contex.unbindService()方法关闭服务。

android中的任务（Activity栈）

1. 任务其实就是activity的栈，它由一个或多个Activity组成，共同完成一个完整的用户体验。栈底的是启动整个任务的Activity，栈顶的是当前运行的用户可以交互的Activity，当一个activity启动另外一个的时候，新的activity就被压入栈，并成为当前运行的activity。而前一个activity仍保持在栈之中。当用户按下BACK键的时候，当前activity出栈，而前一个恢复为当前运行的activity。栈中保存的其实是对象，栈中的Activity永远不会重排，只会压入或弹出。
2. 任务中的所有activity是作为一个整体进行移动的。整个的任务（即activity栈）可以移到前台，或退至后台。
3. Android系统是一个多任务(Multi-Task)的操作系统，可以在用手机听音乐的同时，也执行其他多个程序。每多执行一个应用程序，就会多耗费一些系统内存，当同时执行的程序过多，或是关闭的程序没有正确释放掉内存，系统就会觉得越来越慢，甚至不稳定。为了解决这个问题，Android引入了一个新的机制，即生命周期(Life Cycle)。

二、安卓六大布局

声明Android程序布局有两种方式：

1. 使用xml描述布局
2. 在java代码中通过调用方法进行控制

可以使用任何一种声明界面布局的方式，也可以同时使用两种方式。

使用XML文件声明有以下3个特点：

• 将程序的表现层和控制层分离；
• 在后期修改用户界面时，无须更改程序的源程序；
• 在可视化工具直接看到所设计的用户界面，有利于加快界面设计的过程。

六大界面布局方式包括：

• 线性布局（LinearLayout）
• 框架布局（FrameLayout）
• 表格布局（TableLayout）
• 相对布局（RelativeLayout）
• 绝对布局（AbsoluteLayout）
• 网格布局（GridLayout）

2.1 线性布局

LinearLayout容器中的组件一个挨一个排列，通过控制android:orientation属性，可控制各组件是横向排列还是纵向排列。

2.2 表格布局

TableLayout继承自Linearout，本质上仍然是线性布局管理器。表格布局采用行、列的形式来管理UI组件，并不需要明确地声明包含多少行、多少列，而是通过添加TableRow、其他组件来控制表格的行数和列数。

每向TableLayout中添加一个TableRow就代表一行；

每向TableRow中添加一个一个子组件就表示一列；

如果直接向TableLayout添加组件，那么该组件将直接占用一行；

在表格布局中，可以为单元格设置如下三种行为方式：

• Shrinkable：该列的所有单元格的宽度可以被收缩，以保证该表格能适应父容器的宽度；
• Strentchable：该列所有单元格的宽度可以被拉伸，以保证组件能完全填满表格空余空间；
• Collapsed：如果该列被设置为Collapsed，那么该列的所有单元格会被隐藏；

2.3 帧布局

FrameLayout直接继承自ViewGroup组件。帧布局为每个加入其中的组件创建一个空白的区域(称为一帧)，每个子组件占据一帧，这些帧会根据gravity属性执行自动对齐。

2.4 相对布局

一个元素相对另一个元素

2.5 网格布局

它把整个容器划分为rows × columns个网格，每个网格可以放置一个组件。性能及功能都要比tablelayout好，比如GridLayout布局中的单元格可以跨越多行，而tablelayout则不行，此外，其渲染速度也比tablelayout要快。

2.6 绝对布局

即Android不提供任何布局控制，而是由开发人员自己通过X坐标、Y坐标来控制组件的位置。每个组件都可指定如下两个XML属性：

• layour_x;
• layout_y;

绝对布局已经过时，不应使用或少使用。

界面布局类型的选择和性能优化

首先得明确，界面布局类型的嵌套越多越深越复杂，会使布局实例化变慢，使Activity的展开时间延长。建议尽量减少布局嵌套，尽量减少创建View对象的数量。

1. 减少布局层次，可考虑用RelativeLayout来代替LinearLayout。通过Relative的相对其他元素的位置来布局，可减少块状嵌套；

2. 另一种减少布局层次的技巧是使用 <merge /> 标签来合并布局；

3. 重用布局。Android支持在XML中使用 <include /> 标签， <include /> 通过指定android:layout属性来指定要包含的另一个XML布局。

   如：

   1 2 3

   <include android:id="@+id/id1" android:layout="@layout/mylayout"> <include android:id="@+id/id2" android:layout="@layout/mylayout"> <include android:id="@+id/id3" android:layout="@layout/mylayout">

三、五大存储

在Android中，可供选择的存储方式有：

• SharedPreferences
• 文件存储
• SQLite数据库方式
• 内容提供器（Content provider）
• 网络

3.1 SharedPreferences

Android提供用来存储一些简单的配置信息的一种机制，例如，一些默认欢迎语、登录的用户名和密码等。其以键值对的方式存储，使得我们可以很方便的读取和存入。

SharedPreferences是以XML的格式以文件的方式自动保存的，在DDMS中的File Explorer中展开到/data/data/<package

name>/shared_prefs下，以上面这个为例，可以看到一个叫做SETTING_Infos.xml的文件

   注意：Preferences只能在同一个包内使用，不能在不同的包之间使用。

3.2 文件存储

在Android中，其提供了openFileInput 和 openFileOupu 方法读取设备上的文件，下面看个例子代码，具体如下所示：

1
2
3

String FILE_NAME = "tempfile.tmp";  //确定要操作文件的文件名
FileOutputStream fos = openFileOutput(FILE_NAME, Context.MODE_PRIVATE); //初始化
FileInputStream fis = openFileInput(FILE_NAME); //创建写入流

上述代码中两个方法只支持读取该应用目录下的文件，读取非其自身目录下的文件将会抛出异常。需要提醒的是，如果调用

FileOutputStream 时指定的文件不存在，Android 会自动创建它。另外，在默认情况下，写入的时候会覆盖原文件内容，如果想把

新写入的内容附加到原文件内容后，则可以指定其模式为Context.MODE_APPEND。

3.3 SQLite数据库方式

SQLite是Android所带的一个标准的数据库，它支持SQL语句，它是一个轻量级的嵌入式数据库。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

/* 
 * 什么是SQLiteDatabase？ 
 * 一个SQLiteDatabase的实例代表了一个SQLite的数据库，通过SQLiteDatabase实例的一些方法，我们可以执行SQL语句， 
 * 对数据库进行增、删、查、改的操作。需要注意的是，数据库对于一个应用来说是私有的，并且在一个应用当中，数据库的名字也是惟一的。  
 */  


/* 
 * 什么是SQLiteOpenHelper ？  
 * 这个类主要生成一个数据库，并对数据库的版本进行管理。 
 * 当在程序当中调用这个类的方法getWritableDatabase()或者getReadableDatabase()方法的时候，如果当时没有数据，那么Android系统就会自动生成一个数据库。 
 * SQLiteOpenHelper 是一个抽象类，我们通常需要继承它，并且实现里边的3个函数， 
 *     onCreate（SQLiteDatabase）：在数据库第一次生成的时候会调用这个方法，一般我们在这个方法里边生成数据库表。 
 *     onUpgrade（SQLiteDatabase, int, int）：当数据库需要升级的时候，Android系统会主动的调用这个方法。一般我们在这个方法里边删除数据表，并建立新的数据表，当然是否还需要做其他的操作，完全取决于应用的需求。 
 *     onOpen（SQLiteDatabase）：这是当打开数据库时的回调函数，一般也不会用到。  
 */  

3.4 内容提供器（Content provider）方式

1.什么是ContentProvider

数据在Android当中是私有的，当然这些数据包括文件数据和数据库数据以及一些其他类型的数据。难道两个程序之间就没有办法对于数据进行交换？解决这个问题主要靠ContentProvider。

一个Content Provider类实现了一组标准的方法接口，从而能够让其他的应用保存或读取此Content Provider的各种数据类型。也就是说，一个程序可以通过实现一个Content Provider的抽象接口将自己的数据暴露出去。外界根本看不到，也不用看到这个应用暴露的数据在应用当中是如何存储的，或者是用数据库存储还是用文件存储，还是通过网上获得，这些一切都不重要，重要的是外界可以通过这一套标准及统一的接口和程序里的数据打交道，可以读取程序的数据，也可以删除程序的数据，当然，中间也会涉及一些权限的问题。

2. 什么是ContentResolver

外界的程序通过ContentResolver接口可以访问ContentProvider提供的数据，在Activity当中通过getContentResolver()可以得到当前应用的ContentResolver实例。

3. ContentProvider和ContentResolver中用到的Uri

在ContentProvider和ContentResolver当中用到了Uri的形式通常有两种，一种是指定全部数据，另一种是指定某个ID的数据。

content://contacts/people/ 这个Uri指定的就是全部的联系人数据。

content://contacts/people/1 这个Uri指定的是ID为1的联系人的数据。

3.5 网络存储

pass

参考链接

https://blog.csdn.net/shenggaofei/article/details/52450668

Activity生命周期

各生命周期状态说明

阶段状态

一个Activity从本质上讲拥有4种状态：

• 运行：如果当前的activity在前台界面上时（堆栈顶端）。

• 暂停：如果activity被另一个非全屏活动强占焦点并覆盖时（如弹窗dialog），它将会暂停。一个暂停的活动也是完全活跃的（它的所有的状态和成员信息将会保留，但activity本身将不会再依附于WindowsManager了），在内存极度缺乏的状态会被系统杀死。

• 停止：如果activity完全被另一个全屏活动遮挡住时，它将会停止。该活动也仍保留全部的状态和成员信息，但将会被隐藏起来不再展示给用户，并且当内存在其他地方被需要时该活动就将会被系统杀死。

• 重启：如果activity处于暂停或者停止状态，系统将会在内存中终止该活动无论是结束活动或者杀死进程。当它再一次展示给用户时，它必须是完全重启并且恢复到之前的状态。

状态转换

参考链接

Activity生命周期 - 简书 (jianshu.com)

面试部分

参考1

虾皮安卓一面凉经_笔经面经_牛客网 (nowcoder.com)

垃圾回收

参考阅读

垃圾收集器1 - 资本可不会睡觉，同志请抓紧时间！ (li-rr.github.io)

首先回顾一下java内存区域：Java内存区域 - 资本可不会睡觉，同志请抓紧时间！ (li-rr.github.io)

程序计数器，本地方法栈，虚拟机栈 3个区域随线程而生，随线程而灭，这几个区域的内存分配和回收都具有确定性，不需要考虑如何回收。

在Java堆和方法区中具有不确定性，接口实现的多个类需要的内存可能会不一样，一个方法不同分支所需的内存也不一样，只有在运行的时候才能知道创建了哪些对象，创建了多少对象

垃圾的判断

• 引用计数法

  在对象中添加一个引用计数器，每当有一个地方引用它时，计数器就加一；任何时刻计数器为零的对象就是不可能再被使用的。

  弊端的例子：(54条消息) 关于引用计数法的循环引用问题_黑-白-色的博客-CSDN博客_引用计数法 循环引用

• 可达性分析法

  基本思路：通过称为“GC Roots”的根对象作为起始节点集，从这些节点开始，根据引用关系向下搜索，搜索过程走过的路径被称为“引用链”（Reference Chain），如果某个对象到GC Roots间没有任何引用链相连，则此对象是不可能再次被使用的。

  如下对象可认定为”GC Root”对象：

  1 2 3 4 5 6

  1. 虚拟机栈（栈帧中的本地变量表）中引用的对象，譬如各个线程被调用的方法堆栈中使用到的参数、局部变量、临时变量等 2. 在方法区中类静态属性引用的对象，譬如Java类的引用类型静态变量 3. 在方法区中常量引用的对象，譬如字符串常量池（String Table）里的引用 4. 在本地方法栈中JNI（既通常所说的Native方法）引用的对象 5. 活着的线程Thread

垃圾回收算法

标记清除算法

首先，会先标记所有需要回收的对象，接着将被标记的不可用的对象清除。

优点是算法简单，只需要清理被标记的地址空间。缺点也比较明显，因为标记位置零散，很碎片化，导致被清除完后，可用的地址空间也零零散散。如果连续的可用内存空间少，那么遇到大的内存对象需分配内存时，就很难分配到适宜的连续内存空间。

标记-复制算法

标记-复制算法被简称为复制算法，其是为了解决标记-清除算法面对大量可回收对象时执行效率低的问题。

将内存空间平分为A、B两块，将A中存活的对象移动到B内存块中，再对A块所有对象进行清除。但是这个算法也有明显的缺点，那就是不管A区域或B区域有多少个存活对象，都需要将整块内存分成两个区域，意味着能够真正使用的内存变成了一半，造成内存的利用率不高。

标记整理算法

其标记过程仍然与“标记-清除”算法一样，但后续步骤不是直接对可回收对象进行清理，而是让所有存活对象都向内存空间一端移动，然后直接清理到边界以外的内存。但是，缺点也有，就是多出了将存活内存平移的操作，会降低清除的效率。

分代回收算法

将对象进行代的划分，把不同生命周期的对象放在不同的代上使用不同的垃圾回收方式。主要代划分如下：

• 年轻代（例如：方法的局部变量等）

• 年老代（例如：缓存对象、单例对象等）

• 持久代（例如：加载过的类信息）

由上可知：堆大小=新生代+老年代

将朝生夕灭的对象集中放在一起，每次回收时只关注如何保留少量存活而不是去标记那些大量将要被回收的对象，就能以较低代价回收到大量的空间；

如果剩下的都是难以消亡的对象，那把它们集中放在一块，VM便可以用较低的频率来回收这个区域，这兼顾了垃圾收集的时间开销和内存的空间有效利用。

内存优化

1. 对象无需引用，则置空为null，方便检测被垃圾内存
2. 多用基本数据类型，少用它们的引用数据类型。例如Integer会比int所占大
3. 少用static修饰变量，被修饰的全局性的变量是不会被GC回收的
4. 字符串拼接要用StringBuffer(用append拼接)替代String，例如String str =str1+str2+str3+str4+str5，每多一个“+”，就会多创建一个对象。

参考资料

(54条消息) android垃圾回收机制_只管羊毛薅的博客-CSDN博客_android 垃圾回收机制

fragment和activity

首先看Activity的生命周期，有：
onCreate()、onStart()、onResume()、onPause()、onStop()、onDestroy()、onRestart()

其中：
onCreate()和onDestroy()是成对关系
onStart()和onStop()是成对关系
onResume()和onPause()是成对关系

然后看Activity的几种状态：

运行状态、暂停状态、停止状态、销毁状态

Activity的几种生存期：
完整生存期、可见生存期、前台生存期

根据生命周期、状态、生存期对Activity做一个解释分析

运行状态：当一个活动位于返回栈的栈顶时该活动就是处于运行状态

暂停状态：当一个活动不处于栈顶位置但仍然可见时，活动处于暂停状态（比如在对话框后面的activity）

停止状态：当一个活动不再处于栈顶位置并且完全不可见时，活动处于停止状态

销毁状态：当一个活动从返回栈中移除后就变成了销毁状态

完整生存期：活动从onCreate()到onDestroy()之间经历的就是完整生存周期

可见生存期：活动在onStart()到onStop()之间经历的就是可见生存期。此时活动可见，即便可能不能与用户交互。

前台生存期：活动在onResume()到onPause之间经历的就是前台生存期。此时活动可见并且能与用户交互。

Fragment的生命周期

Fragment是用来描述一些行为或一部分用户界面在一个Activity中,你可以合并多个fragment在一个单独的activity中建立多个UI面板，同时重用fragment在多个activity中。

它相比Activity可以在一个界面上灵活的替换一部分页面

因为Fragment和Activity是可以通信的，Fragment是一种控制器对象，Activity可以委派它完成一个任务，这些任务通常就是管理用户界面（Activity通过findFragmetById获得Fragment的一个实例，Fragment通过getActivy获得Activity的实例和Context）。

Activity知道如何管理Fragment，因此Fragment的使用需要Activity的支持，使得Fragment的生命周期和Activity的生命周期非常像，很多方法名称都和Activity是一样的。

Fragment的运行状态：

运行状态：当fragment可见，并且它关联的activity处于运行状态，此fragment也处于运行状态。

暂停状态：当一个activity进入暂停状态（比如对话框等未占满屏幕的activity进入栈顶），fragment也进入到暂停状态

停止状态：当一个activity进入停止状态，与之关联的fragment也进入停止状态；或者通过fragment事务的remove和replace方法将fragment移除。如果在事务commit之前调用了addToBackStack()方法，这时的fragment也会停止

销毁状态：Fragment依附Activity存在，当activity被销毁，与之关联的fragment也被销毁。或者通过fragment事务的remove和replace方法将fragment移除。如果在事务commit之前没有调用addToBackStack()方法，这时的fragment也会销毁

fragment和Activity之间的通信：（控件间的相互操作）

• fragment控制fragment：得到一个Activity，然后通过这个Activity的getFragmentManager()获得该Fragment的实例。

• fragment控制Activity：这个很简单。每个Fragment都有getActivity()得到一个Activity的实例：

  1 2	View listView = getActivity().findViewById(R.id.list); //PS:在当前activity和fragment已经进行关联的情况下否则返回null。

• Activity控制fragment：activity也可以获得一个fragment的引用，从而调用fragment中的方法：

  1	xxxFragment xxx=getFragmentManager().findFragmentById();

• Activity控制Activity：这个显然是通过Intent活动之间的通信完成。别忘了在被打开的活动中创建Intent和得到Intent一起进行，写个静态的actionStart()。

Android进程间通信

1. 使用Intent
2. 使用文件共享
3. 使用Messenger
4. 使用AIDL
5. 使用ContentProvider
6. 使用Socket

1. 使用Intent

Activity，Service，Receiver 都支持在 Intent 中传递 Bundle 数据，而 Bundle 实现了 Parcelable 接口，可以在不同的进程间进行传输。

Parcelable 实现序列化

Bundle主要用于传递数据；它保存的数据，是以key-value(键值对)的形式存在的。

我们经常使用Bundle在Activity之间传递数据，传递的数据可以是boolean、byte、int、long、float、double、string等基本类型或它们对应的数组，也可以是对象或对象数组。当Bundle传递的是对象或对象数组时，必须实现Serializable 或Parcelable接口。下面分别介绍Activity之间如何传递基本类型、传递对象。

在一个进程中启动了另一个进程的 Activity，Service 和 Receiver ，可以在 Bundle 中附加要传递的数据通过 Intent 发送出去。

2. 使用文件共享

Windows 上，一个文件如果被加了排斥锁会导致其他线程无法对其进行访问，包括读和写；而 Android 系统基于 Linux ，使得其并发读取文件没有限制地进行，甚至允许两个线程同时对一个文件进行读写操作，尽管这样可能会出问题。

可以在一个进程中序列化一个对象到文件系统中，在另一个进程中反序列化恢复这个对象（注意：并不是同一个对象，只是内容相同。）。

SharedPreferences 是个特例，系统对它的读 / 写有一定的缓存策略，即内存中会有一份 ShardPreferences 文件的缓存，系统对他的读 / 写就变得不可靠，当面对高并发的读写访问，SharedPreferences 有很多大的几率丢失数据。因此，IPC 不建议采用 SharedPreferences。

3. 使用Messenger

暂时放弃

4. 使用AIDL

AIDL:Android Interface Definition Language

暂时放弃

5. 使用 ContentProvider

用于不同应用间数据共享，和 Messenger 底层实现同样是 Binder 和 AIDL，系统做了封装，使用简单。

系统预置了许多 ContentProvider ，如通讯录、日程表，需要跨进程访问。

使用方法：继承 ContentProvider 类实现 6 个抽象方法，这六个方法均运行在 ContentProvider 进程中，除 onCreate 运行在主线程里，其他五个方法均由外界回调运行在 Binder 线程池中。

ContentProvider 的底层数据，可以是 SQLite 数据库，可以是文件，也可以是内存中的数据。

6. 使用Socket

Socket起源于 Unix，而 Unix 基本哲学之一就是“一切皆文件”，都可以用“打开 open –读写 write/read –关闭 close ”模式来操作。Socket 就是该模式的一个实现，网络的 Socket 数据传输是一种特殊的 I/O，Socket 也是一种文件描述符。Socket 也具有一个类似于打开文件的函数调用： Socket()，该函数返回一个整型的Socket 描述符，随后的连接建立、数据传输等操作都是通过该 Socket 实现的。

常用的 Socket 类型有两种：流式 Socket（SOCK_STREAM）和数据报式 Socket（SOCK_DGRAM）。

参考链接

Android进程间通信方式 - 简书 (jianshu.com)

进程调度

为了确定首先执行哪个进程以及最后执行哪个进程以实现最大 CPU 利用率，计算机科学家已经定义了一些算法，它们是：

• 先到先服务(FCFS)调度算法 : 从就绪队列中选择一个最先进入该队列的进程为之分配资源，使它立即执行并一直执行到完成或发生某事件而被阻塞放弃占用 CPU 时再重新调度。
• 短作业优先(SJF)的调度算法 : 从就绪队列中选出一个估计运行时间最短的进程为之分配资源，使它立即执行并一直执行到完成或发生某事件而被阻塞放弃占用 CPU 时再重新调度。
• 时间片轮转调度算法 : 时间片轮转调度是一种最古老，最简单，最公平且使用最广的算法，又称 RR(Round robin)调度。每个进程被分配一个时间段，称作它的时间片，即该进程允许运行的时间。
• 多级反馈队列调度算法：前面介绍的几种进程调度的算法都有一定的局限性。如短进程优先的调度算法，仅照顾了短进程而忽略了长进程 。多级反馈队列调度算法既能使高优先级的作业得到响应又能使短作业（进程）迅速完成。，因而它是目前被公认的一种较好的进程调度算法，UNIX 操作系统采取的便是这种调度算法。
• 优先级调度 ： 为每个流程分配优先级，首先执行具有最高优先级的进程，依此类推。具有相同优先级的进程以 FCFS 方式执行。可以根据内存要求，时间要求或任何其他资源要求来确定优先级。

MVC，MVP和MVVM

MVC：视图，控制器，模型

MVC模式的意思是，软件可以分成三个部分。

1
2
3

视图（View）：用户界面。
控制器（Controller）：业务逻辑
模型（Model）：数据保存

各部分之间的通信方式如下。

1
2
3

View 传送指令到 Controller
Controller 完成业务逻辑后，要求 Model 改变状态
Model 将新的数据发送到 View，用户得到反馈

所有通信都是单向的。

主要处理逻辑为：View触发事件，controller响应并处理逻辑，调用Model，Model处理完成后将数据发送给View，View更新。

MVP：

MVP 模式将 Controller 改名为 Presenter，同时改变了通信方向。

1. 各部分之间的通信，都是双向的。

2. View 与 Model 不发生联系，都通过 Presenter 传递。

3. View 非常薄，不部署任何业务逻辑，称为”被动视图”（Passive View），即没有任何主动性，而 Presenter非常厚，所有逻辑都部署在那里。

MVP模型中，P为Presenter，并以Presenter为核心，负责从model获取数据，并填充到View中。该模型使得Model和View不再有联系，且View被称为“被动视图”，暴露出setter接口。

MVVVM

MVVM 模式将 Presenter 改名为 ViewModel，基本上与 MVP 模式完全一致。

唯一的区别是，它采用双向绑定（data-binding）：View的变动，自动反映在 ViewModel，反之亦然。Angular 和 Ember 都采用这种模式。

MVVM模型中，VM为ViewModel，同样是以VM为核心，但是不同于MVP，MVVM采用了数据双向绑定的方案，替代了繁琐复杂的DOM操作。该模型中，View与VM保持同步，View绑定到VM的属性上，如果VM数据发生变化，通过数据绑定的方式，View会自动更新视图；VM同样也暴露出Model中的数据。

参考2

四种引用

强引用

Java中默认声明的就是强引用，比如：

1
2

Object obj = new Object(); //只要obj还指向Object对象，Object对象就不会被回收
obj = null;  //手动置null

只要强引用存在，垃圾回收器将永远不会回收被引用的对象，哪怕内存不足时，JVM也会直接抛出OutOfMemoryError，不会去回收。如果想中断强引用与对象之间的联系，可以显示的将强引用赋值为null，这样一来，JVM就可以适时的回收对象了

软引用

软引用是用来描述一些非必需但仍有用的对象。在内存足够的时候，软引用对象不会被回收，只有在内存不足时，系统则会回收软引用对象，如果回收了软引用对象之后仍然没有足够的内存，才会抛出内存溢出异常。这种特性常常被用来实现缓存技术，比如网页缓存，图片缓存等。

用java.lang.ref.SoftReference类来表示软引用。

1

SoftReference<byte[]> sr = new SoftReference<>(buff);

弱引用

弱引用的引用强度比软引用要更弱一些，无论内存是否足够，只要 JVM 开始进行垃圾回收，那些被弱引用关联的对象都会被回收。

用 java.lang.ref.WeakReference 来表示弱引用。

1

WeakReference<byte[]> sr = new WeakReference<>(buff);

虚引用

虚引用是最弱的一种引用关系，如果一个对象仅持有虚引用，那么它就和没有任何引用一样，它随时可能会被回收

214. 最短回文串 - 力扣（LeetCode） (leetcode-cn.com)

描述

给定一个字符串 s，你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。

示例 1：

1
2

输入：s = "aacecaaa"
输出："aaacecaaa"

示例 2：

1
2

输入：s = "abcd"
输出："dcbabcd"

解法

先逆序，然后截取逆序后的前i个字符拼接到原串上，取满足回文条件最小的i。

1
2
3
4
5
6
7
8
9
10
11
12

class Solution:
    def shortestPalindrome(self, s: str) -> str:
        length=len(s)
        if length==0:
            return ""
        rs = s[::-1] # 先逆序
        i = 0
        while True:
            if rs[i:]==s[:length-i]:
                break
            i+=1
        return rs[:i]+s

基本框架

以dfs求深度为例：

1 2 3 4 5 6 7 8 9 10 11 12 13

class Solution: def maxDepth(self , root ): # write code here def depth(node): if node == None: return 0 a = depth(node.left) + 1 b = depth(node.right) + 1 return max(a,b) depth = depth(root) return depth

B树

定义

B树也称B-树,它是一颗多路平衡查找树。我们描述一颗B树时需要指定它的阶数，阶数表示了一个结点最多有多少个孩子结点，一般用字母m表示阶数。当m取2时，就是我们常见的二叉搜索树。

定义如下：

• 每个节点最多有m-1个关键字

• 根节点最少可以有1个关键字

• 非根节点至少有 math.ceil(m/2)-1个关键字

  ceil上取整，floor下取整

• 每个节点中的关键字按从小到大的顺序排列，每个关键字中的左子树都小于它，而右子树中的所有关键字都大于它。

• 所有叶子节点都位于同一层，或者说根节点到每个叶子节点的长度都相同。

上图是一颗阶数为4的B树。在实际应用中的B树的阶数m都非常大（通常大于100），所以即使存储大量的数据，B树的高度仍然比较小。

每个结点中存储了关键字（key）和关键字对应的数据（data），以及孩子结点的指针。

我们将一个key和其对应的data称为一个记录。但为了方便描述，除非特别说明，后续文中就用key来代替（key, value）键值对这个整体。

在数据库中我们将B树（和B+树）作为索引结构，可以加快查询速速，此时B树中的key就表示键，而data表示了这个键对应的条目在硬盘上的逻辑地址。

插入操作

插入操作是指插入一条记录，即（key, value）的键值对。

果B树中已存在需要插入的键值对，则用需要插入的value替换旧的value。若B树不存在这个key,则一定是在叶子结点中进行插入操作。

1. 根据要插入的key的值，找到叶子结点并插入。

2. 判断当前结点key的个数是否小于等于m-1，若满足则结束，否则进行第3步。

   节点有没有满

3. 以结点中间的key为中心分裂成左右两部分，然后将这个中间的key插入到父结点中，这个key的左子树指向分裂后的左半部分，这个key的右子支指向分裂后的右半部分，然后将当前结点指向父结点，继续进行第3步。

下面以5阶B树为例，介绍B树的插入操作，在5阶B树中，结点最多有4个key,最少有2个key

在实现B树的代码中，为了使代码编写更加容易，我们可以将结点中存储记录的数组长度定义为m而非m-1，这样方便底层的结点由于分裂向上层插入一个记录时，上层有多余的位置存储这个记录。同时，每个结点还可以存储它的父结点的引用，这样就不必编写递归程序。

一般来说，对于确定的m和确定类型的记录，结点大小是固定的，无论它实际存储了多少个记录。

但是分配固定结点大小的方法会存在浪费的情况，比如key为28,29所在的结点，还有2个key的位置没有使用，但是已经不可能继续在插入任何值了，因为这个结点的前序key是27,后继key是30,所有整数值都用完了。

所以如果记录先按key的大小排好序，再插入到B树中，结点的使用率就会很低，最差情况下使用率仅为50%。

13,17,21,22,23,24,26,27,28,29,30,31,32,33,34,35,36,39,40,41,53,97

删除操作

删除操作是指，根据key删除记录，如果B树中的记录中不存对应key的记录，则删除失败。

1. 如果当前需要删除的key位于非叶子结点上，则用后继key（这里的后继key均指后继记录的意思）覆盖要删除的key，然后在后继key所在的子支中删除该后继key。此时后继key一定位于叶子结点上，这个过程和二叉搜索树删除结点的方式类似。删除这个记录后执行第2步。

2. 该结点key（移出后继节点的节点）个数大于等于Math.ceil(m/2)-1，结束删除操作，否则执行第3步。

3. 如果兄弟结点key个数大于Math.ceil(m/2)-1，则父结点中的key（移上去的后继节点）下移到该结点，兄弟结点中的一个key上移，删除操作结束。

   否则，将父结点中的key下移与当前结点及它的兄弟结点中的key合并，形成一个新的结点。父结点中的key的两个孩子指针就变成了一个孩子指针，指向这个新结点。然后当前结点的指针指向父结点，重复上第2步。

   有些结点它可能即有左兄弟，又有右兄弟，那么我们任意选择一个兄弟结点进行操作即可。

   合并操作会将当前指针，指向被合并节点的父节点

B+树

定义

维基百科上所定义的方式，即关键字个数比孩子结点个数小1，这种方式是和B树基本等价的。上图就是一颗阶数为4的B+树。

除此之外B+树还有以下的要求：

1. B+树包含2种类型的结点：内部结点（也称索引结点）和叶子结点。根结点本身即可以是内部结点，也可以是叶子结点。根结点的关键字个数最少可以只有1个。
2. B+树与B树最大的不同是内部结点不保存数据，只用于索引，所有数据（或者说记录）都保存在叶子结点中。
3. m阶B+树表示了内部结点最多有m-1个关键字（或者说内部结点最多有m个子树），阶数m同时限制了叶子结点最多存储m-1个记录。
4. 内部结点中的key都按照从小到大的顺序排列，对于内部结点中的一个key，左树中的所有key都小于它，右子树中的key都大于等于它。叶子结点中的记录也按照key的大小排列。
5. 每个叶子结点都存有相邻叶子结点的指针，叶子结点本身依关键字的大小自小而大顺序链接。

插入操作

1. 若为空树，创建一个叶子结点，然后将记录插入其中，此时这个叶子结点也是根结点，插入操作结束。
2. 针对叶子类型结点：根据key值找到叶子结点，向这个叶子结点插入记录。
   • 插入后，若当前结点key的个数小于等于m-1，则插入结束。
   • 否则将这个叶子结点分裂成左右两个叶子结点，左叶子结点包含前m/2个记录，右结点包含剩下的记录，将第m/2+1个记录的key进位到父结点中（父结点一定是索引类型结点），进位到父结点的key左孩子指针向左结点,右孩子指针向右结点。将当前结点的指针指向父结点，然后执行第3步。
     • 针对索引类型结点：若当前结点key的个数小于等于m-1，则插入结束。
     • 否则，将这个索引类型结点分裂成两个索引结点，左索引结点包含前(m-1)/2个key，右结点包含m-(m-1)/2个key，将第m/2个key进位到父结点中，进位到父结点的key左孩子指向左结点, 进位到父结点的key右孩子指向右结点。将当前结点的指针指向父结点，然后重复第3步。

5,6,7,8,9,10,15,16,17,18,19,20,21,22

删除操作

如果叶子结点中没有相应的key，则删除失败。否则执行下面的步骤

1）删除叶子结点中对应的key。删除后若结点的key的个数大于等于Math.ceil(m-1)/2 – 1，删除操作结束,否则执行第2步。

2）若兄弟结点key有富余（大于Math.ceil(m-1)/2 – 1），向兄弟结点借一个记录，同时用借到的key替换父结（指当前结点和兄弟结点共同的父结点）点中的key，删除结束。否则执行第3步。

3）若兄弟结点中没有富余的key,则当前结点和兄弟结点合并成一个新的叶子结点，并删除父结点中的key（父结点中的这个key两边的孩子指针就变成了一个指针，正好指向这个新的叶子结点），将当前结点指向父结点（必为索引结点），执行第4步（第4步以后的操作和B树就完全一样了，主要是为了更新索引结点）。

4）若索引结点的key的个数大于等于Math.ceil(m-1)/2 – 1，则删除操作结束。否则执行第5步

5）若兄弟结点有富余，父结点key下移，兄弟结点key上移，删除结束。否则执行第6步

6）当前结点和兄弟结点及父结点下移key合并成一个新的结点。将当前结点指向父结点，重复第4步。

注意，通过B+树的删除操作后，索引结点中存在的key，不一定在叶子结点中存在对应的记录。

下面是一颗5阶B树的删除过程，5阶B数的结点最少2个key，最多4个key。

参考链接

B树和B+树的插入、删除图文详解 - nullzx - 博客园 (cnblogs.com)

2021拼多多

1、数位之和

定义为：每个数字的十进制表示中(0~9)，每个数位各不相同且各个数位之和等于N。
满足条件的数字可能很多，找到其中的最小值即可。

输入描述：

1 2	共一行，一个正整数N，如题意所示，表示组合中数字不同数位之和。 （1 <= N <= 1,000）

输出描述：

1 2	共一行，一个整数，表示该组合中的最小值。 如果组合中没有任何符合条件的数字，那么输出-1即可。

题目分析：

数：123456789 是最小的数位之和，因为题目中限定了每个数位各不相同，

则只需求1-45之间的就行

解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

def myCompute(num):
    if num > 45:
        return -1
    if num < 10:
        return num

    nums = 0
    digits = 0 # 记录第几位数，用于进位

    for i in range(9,0,-1):
        if num != 0 and i <= num:
            print(nums,i,"-")
            num -= i
            nums += i * (10**digits)
            
            digits += 1
    return nums

解法二：

1
2
3
4
5
6
7
8
9
10
11

def compute(x,num):
    '''
    num代表每一位上的数字
    x 代表总和
    '''
    # 如果发现，剩余的总和比安排的数字还小就不需要递归了
    if x<= num:
        return x
    else:
        # 在剩余的总和中，安排剩余的数字
        return num + 10 * compute(x-num,num-1)

2、字符串变换

多多君最近在研究字符串之间的变换，可以对字符串进行若干次变换操作:

1. 交换任意两个相邻的字符，代价为0。
2. 将任意一个字符a修改成字符b，代价为 |a - b|（绝对值）。

现在有两个长度相同的字符串X和Y，多多君想知道，如果要将X和Y变成两个一样的字符串，需要的最少的代价之和是多少。

输入描述：

1 2 3 4

共三行，第一行，一个整数N，表示字符串的长度。 （1 <= N <= 2,000） 接下来两行，每行分别是一个字符串，表示字符串X和Y。 （字符串中仅包含小写字母）

输出描述：

1	共一行，一个整数，表示将X和Y变换成一样的字符串需要的最小的总代价。

示例：

输入：

1 2 3

4 abca abcd

输出：

1

3

解法：

1
2
3
4
5
6
7
8
9
10
11

def myCompute2(str1,str2):
    str1 = ''.join(sorted(str1))
    str2 = ''.join(sorted(str2))

    n = len(str1)
    res = 0
    for i in range(n):
        ch1 = str1[i]
        ch2 = str2[i]
        res += abs(ord(ch1)-ord(ch2))
    return res

3、和谐值的计算

多多路上从左到右有N棵树（编号1～N），其中第i个颗树有和谐值Ai。

多多鸡认为，如果一段连续的树，它们的和谐值之和可以被M整除，那么这个区间整体看起来就是和谐的。

现在多多鸡想请你帮忙计算一下，满足和谐条件的区间的数量。

输入描述：

第一行，有2个整数N和M，表示树的数量以及计算和谐值的参数。
（ 1 <= N <= 100,000, 1 <= M <= 100 ）
第二行，有N个整数Ai, 分别表示第i个颗树的和谐值。
（ 0 <= Ai <= 1,000,000,000 ）

输出描述：

1	共1行，每行1个整数，表示满足整体是和谐的区间的数量。

解法：

来自牛客评论区

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

def myCompute3(M,A):
    n = len(A)
    count = 0
    note = dict()
    note[0] =1
    # # # # 先从区间数量开始遍历
    # for idx in range(1,n+1):
    #     # print(idx,end=", ")
    #     # 从起点开始遍历
    #     for start in range(0,n):
    #         end_idx = start+idx
    #         if end_idx>n : continue

    #         if sum(A[start:end_idx]) % M == 0:
              
    #             # print(A[start:end_idx])
    #             # print(start,end_idx,end="; ")
    #             count+=1
        # print(n)
    # map的作用  map 里面是sum 跟m取余之后的余数相同值的次数 ，  
    # 如果sum在累加过程中两次取余相等，那么第一次取余的sum
    # 和第二次取余的sum中间加的数列  一定是m的倍数
    sum = 0
    for i in range(n):
        sum += A[i]
        index = sum % M
        if index not in note:
            note[index] = 0
        # print(index)
        count += note[index]
        note[index] += 1
    print(count)

4、骰子分类

多多君拼团购买了N个骰子，为了方便后面进行活动，多多君需要将这些骰子进行分类。

两个骰子为同类的定义是：

将其中一个骰子通过若干次上下、左右或前后翻转后，其与另一个骰子对应的6面数字均相等。

现在多多君想知道不同种类的骰子的数量分别有多少。

放弃了

【自顶向下】从一个规模较大的问题 f(20)，向下逐渐分解规模，直到 f(1)、f(2)触底，再逐层返回答案，这就是【自顶向下】

【自顶向上】直接从最低下，最简单，问题规模最小的f(1)和f(2)开始往上推，直到推到想要的答案f(20)，这就是动态规划的思路。

---

求解动态规划的核⼼问题是穷举。

• 但是这类存在重叠子问题，直接暴力搜索效率较低。故需要一个备忘录或者DP Table，避免不必要的计算。

• 其一定具备最优子结构，才能通过子问题的最值得到原问题的最值。

• 由于问题千变万化，穷举所有可行解不不容易，故需要列出正确的状态转移方法。

重叠子问题，最优子结构，状态转移方程是动态规划的三要素。

写出状态转移方程一般是最难的，一个辅助框架：

明确 状态 -> 定义 dp数组/函数的含义 -> 明确 选择 -> 明确 base case。

摘自算法小抄

涛拍岸，卷起千堆雪。斜阳独立，西风柔，鬓挽霞云。