算法题解-912. 排序数组
1.题目描述912. 排序数组
给定一个整数数组 nums，将该数组升序排列。
示例 1：
12输入：[5,2,3,1]输出：[1,2,3,5]
示例 2：
12输入：[5,1,1,2,0,0]输出：[0,0,1,1,2,5]
提示：
1 <= A.length <= 10000
-50000 <= A[i] <= 50000
2.代码实现12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152class Solution { public static List<Integer> sortArray(int[] nums) { int[] temp = new int[nums.length]; sort(nums, 0, nums.length-1, temp); List<Integer> list = new ...
算法题解-509. 斐波那契数
1.题目描述509. 斐波那契数
斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
12F(0) = 0, F(1) = 1F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
给定 N，计算 F(N)。
示例 1：
123输入：2输出：1解释：F(2) = F(1) + F(0) = 1 + 0 = 1.
示例 2：
123输入：3输出：2解释：F(3) = F(2) + F(1) = 1 + 1 = 2.
示例 3：
123输入：4输出：3解释：F(4) = F(3) + F(2) = 2 + 1 = 3.
提示：
0 ≤ N ≤ 30
2.代码实现123456789101112131415161718192021222324class Solution { public int fib(int N) { ...
算法分析设计-递归与分治策略
一. 分治法（Divide and conquer）分治：
将一个规模较大问题分解为规模较小的子问题，先求解这些子问题， 然后将各子问题的解合并得到原问题的解的算法思路。
递归：
直接或者间接的调用自身的算法（程序）叫递归算法（程序）。
为什么要用递归？
递归是一种自然的思考方式
思路清晰
易于实现
慎用递归？
程序具体执行步骤难理解
坏的递归大幅度提高算法复杂度
二.汉诺塔（Hanoi Tower）问题1.问题描述有 A,B,C 三根柱子，A 上面有 n 个盘子，我们想把 A 上面的盘子移动到 C 上，但是要满足以下三个条件：
每次只能移动一个盘子;
盘子只能从柱子顶端滑出移到下一根柱子;
盘子只能叠在比它大的盘子上。
2.解题思路
假设 n = 1，只有一个盘子，很简单，直接把它从 A 中拿出来，移到 C 上
假设 n = 2，需要借助B柱子，先将最上面的盘子移动到B柱子，再将最下面的盘子移动到C柱子上，再将B柱子上的盘子移动到C柱子上即可完成。
如果 n > 2，我们可以将除开最后一个盘子之外的所有盘子暂时充当一个整体，之后就可以采用 n = 2 的方法移动。
...
算法分析设计-算法思维
一. 算法设计模式
枚举 或者说 暴力求解 （Brute force）
分治法（Divide and conquer）
贪婪算法（Greedy approach）
动态规划（Dynamic programming）
回溯法（Backtracking）
分支定界法（Branch and bound）
概率算法（Randomized algorithm）
二. 算法思维1.什么是算法思维？现实问题——》形式化描述——》设计算法——》方案实施——》现实问题
2.算法思维解决实际问题的步骤
Understand the problem（理解）
Formulate it（制定）
Design algorithm（设计）
Implment it（实现）
Run the code and solve the original problem（运行）
三.实例-交通信号设计
1.表示输入（冲突网络）
1234567891011121314151617181920/** * String 表示通行方向 “AB”，“AC” ...... * LinkedList<String> ...
算法分析设计-十大排序算法
一.算法分类分类：
非线性时间比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破 O(nlogn)，因此成为非线性时间比较类程序。
线性时间非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此称为线性时间非比较类排序。
复杂度：
时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。
稳定性：
稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面
不稳定：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面
排序方式：
内排序：所有排序操作都在内存中完成。
外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行。
1.排序算法类型
2.排序算法时间复杂度
排序方法
时间复杂度(平均)
时间复杂度(最坏)
时间复杂度(最好)
空间复杂度
稳定性
冒泡排序
O(n2)
O(n2)
O(n)
O(1)
稳定
快速排序
O(nlogn)
O(n2)
...
算法分析设计-复杂度分析
一. 时间复杂度评价标准：▶ 运行时间 ▶ 运算步骤 ▶ 增长量级
1.运行时间运行时间随机器而异，它是由机器本身软硬件环境决定的，与算法无关。我们更多的讨论影响运行时间的另一个因素—运算步骤。
2.运算步骤① 什么是运算步骤？
基本运算（加，减，乘，除，余，判断，数组的读取，写入，函数调用等）发生的次数。
②优点
机器无关，具有解释力
③缺点
计数繁琐，求解有难度，函数复杂
④注意
算法复杂度主要考虑输入规模较大的情形，此时具体的增长函数不是那么重要，关键是其增长量级。
3.增长量级（Order of growth）假设某算法的执行步骤 f(n) 跟输入的规模的关系为 f(n) = 3n2+150n+10000，影响最大的项为3n2。能否用n2表示？为什么？
基本可以，但是不完全可以。
为什么基本可以？
当n很大时，后面的项（增长速度慢）不重要。
为什么不完全可以？
只用n2表示不了后面的项，也表示不了系数。
① 增长量级的近似表示
增长量级的近似表示 1增长量级的近似表示 2增长量级的近似表示 3下界（Big-Ω）：Ω(n2) 表示存在常数 c 使得当 n >= n0 ...
算法分析设计-关于算法
1. 什么是算法？算法是解决某个问题的确定性指令序列，满足性质：
输入：有外部提供的量作为算法的输入。
输出：算法产生至少一个量作为输出。
确定性：组成算法的每条指令是清晰，无歧义的。
有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。
算法的本质：是解决问题的方法。
算法的优势：（1）把麻烦的事交给计算机做（2）可以解决一类问题
算法的核心任务：设计合理的算法。
2. 如何表示算法？
自然语言
流程图（清晰直观）
伪代码
计算机语言
3. 如何评价算法？
4. 求解斐波那锲数列123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990//Fibonacci/** * 求解斐波那契数 */public class Fibonacci ...
开发工具-AndroidStudio的使用
一.快捷键（Mac平台）1. 注释的快捷键
快速注释单行，也可以区域注释：Command+/
快速多行注释，也可以区域注释：Command+option+/
文档注释，常用于方法函数的注释：Command+Ctrl+M
文档注释的快捷键系统没有设置，Keymap中搜索 Fix doc comment 自己设置就好了。我设置的是Command+Ctrl+M。
2. 快速运行的快捷键
运行最近一次的main函数：Ctrl+R
3. 关于代码的快捷键
查看当前函数的参数，常用于重载：Command+P
跳进对应代码内部：Command+鼠标左键
generate(产生) setter/getter方法：Command +N
调出代码错误解决方法：Option+Enter
快速调出if，for，try等代码环绕：Option+Command+T
清除无效包引用：Option + Ctrl + O
自动缩进对齐：Ctrl + Option + I
4.搜索的快捷键
搜索当前文件的内容：Command+F
替换当前某些文件的内容：Command+R
全局搜索类：Command+O
方法被调用 ...
