只出现一次的数字

只出现一次的数字

多数元素

求众数

二分查找

二分查找是计算机科学中最基本、最有用的算法之一。它描述了在有序集合中搜索特定值的过程。

二分查找中使用的术语：

• 目标Target–你要查找的值
• 索引Index–你要查找的当前位置
• 左、右指示符Left、Right–用来维持查找空间的指标
• 中间指示符Mid–我们用来应用条件来确定我们应该向左查找还是向右查找的索引

如何工作

二分查找对具有指定左索引和右索引的连续序列进行操作。这就是所谓的查找空间。二分查找维护查找空间的左、右和中间指示符，并比较查找目标或将查找条件应用于集合的中间值；如果条件不满足或值不相等，则清除目标不可能存在的那一半，并在剩下的一半上继续查找，直到成功为止。如果查以空的一半结束，则无法满足条件，并且无法找到目标。

二分查找

寻找左侧边界的二分搜索

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

int left_bound(int[] nums, int target) {
    if (nums.length == ) return -1;
    int left = 0;
    int right = nums.length;
    while(left < right) {//因为搜索区间是左闭右开
        int mid = (left + right) / 2;
        if (nums[mid] == target) {
            right = mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid;
        }
    }
    return left;

猜测数字大小

搜索旋转排序数组

• 找到选择的下标rotation_index，也就是数组中最小的元素。二分查找在这里可以派上用上。
• 在选中的数组区域中再次使用二分查找

哈希表

哈希表是一种使用哈希函数组织数据，以及支持快速插入和搜索的数据结构。

有两种不同类型的哈希表：哈希集合和哈希映射。

• 哈希集合是集合数据结构的实现之一，用于存储非重复值
• 哈希映射时映射数据结构的实现之一，用于存储key, value键值对。

哈希表的原理

使用哈希函数将键映射到存储桶

1. 当我们想插入一个新的键时，哈希函数将决定该键应该分配到哪个桶中，并将该键存储在相应的桶中
2. 当我们想搜索一个键时，哈希表将使用相同的哈希函数来查找对应的桶，并只在特定的桶中进行搜索

设计哈希表的关键

哈希函数

哈希函数是哈希表的最重要的组件，该哈希表用于将映射到特定的桶

冲突解决

冲突解决算法应该解决以下几个问题：

1. 如何组织在同一个桶中的值？
2. 如果为同一个桶分配了太多的值，该怎么办？
3. 如何在特定的桶中搜索目标值？

设计哈希集合

不使用任何内建哈希表库设计一个哈希集合

应该包含：

• add(value)：向哈希集合中插入一个值。
• contains(value)：返回哈希集合中是否存在这个值。
• remove(value)：将给定值从哈希集合中删除。如果哈希集合中没有这个值，什么都不做

设计哈希映射

不使用任何内建的哈希表设计一个哈希映射

• put(key, value)：向哈希映射中插入（键、值）的数值对。如果键对应的值已经存在，更新这个值
• get(key)：返回给定的键所对应的值，如果映射中不包含这个键，返回-1
• remove(key：如果隐射中存在这个键，删除这个数值对

实际应用-哈希集合

使用哈希集查重

插入新值并检查值是否在哈希集中是简单有效的。

存在重复元素

只出现一次的数字

列表操作

1. 遍历nums中的每一个元素
2. 如果某个nums中的数字是新出现的，则将它添加到列表中
3. 如果某个数字已经在列表中，删除它

两个数组的交集

快乐数

递归

递归原理

递归是一种解决问题的有效方法，在递归过程中，函数将自身作为子例程调用

每当递归函数调用自身时，它都会将给定的问题拆解为子问题。递归调用继续进行，直到子问题无需进一步递归就可以解决的地步。

为了确保递归函数不会导致无限循环，它应具有以下属性：

1. 一个简单的基本案例（base case）–能够不使用递归来产生答案的终止方案。
2. 一组规则，也称作递推关系（recurrentce relation），可将所有其他情况拆分到基本案例。

两两交换链表中的节点

递归写法要观察本级递归的解决过程，形成抽象模型，因为递归本质就是不断重复相同的事情。而不是思考完整的调用栈，一级又一级，无从下手。我们应该关注一级调用小单元的情况，也就是单f(x)。

关心三点：

1. 返回值
2. 调用单元做了什么
3. 终止条件

本题中：

1. 返回值：交换完成的子链表
2. 调用单元：设需要完成的两个点为head和next，head连接后面交换完成的子链表，next连接head，完成交换
3. 终止条件：head为空指针或者next未空指针，也就是当前无节点或者只有一个节点，无法进行交换

递推关系

在实现递归函数之前，两件重要的事情要弄清楚：

• 递推关系：一个问题的结果与其子问题的结果之间的关系。
• 基本情况：不需要进一步的递归调用就可以计算答案的情况。有时，基本案例也被称为bottom cases，因为它们往往是问题被减少到最小规模的情况，也就是如果我们认为将问题划分为子问题是一种自上而下的方式的最下层。

杨辉三角

二次项展开式

反转链表

• 递归

• 迭代
  遍历列表时，将当前节点的next指针改为指向前一个元素。由于节点没有引用上一个节点，因此必须事先存储其前一个元素。在更改引用之前，还需要另一个指针来存储下一个节点

  1 2 3 4 5 6 7 8 9 10 11

  public ListNode reverseList(ListNode head) { ListNode prev = null; ListNode curr = head; while(curr != null) { ListNode nextTemp = curr.next; curr.next = prev; prev = curr; curr = nextTemp; } return prev; }

递归中的重复问题

记忆化

记忆化是一种优化技术，主要用于加快计算机程序的速度，方法是存储昂贵的函数调用的结果，并在相同的输入再次出现时返回缓存的结果

斐波那契数

耗时的原因是重复计算，可以造一个备忘录，每次算出某个字问题的答案后别急着返回，先记到备忘录里再返回；每次遇到一个子问题先去备忘录里查一查，如果发现之前已经解决过这个问题了，直接把答案拿出来用，不要在耗时计算了。

爬楼梯

暴力

把所有的可能爬的阶数进行组合，也就是1和2.而在每一步中会继续调用函数，并返回函数的和。

记忆化递归

动态规划

分解为包含最优子结构的子问题，即它对的最优解可以从其子问题的最优解来有效地构建

递归–时间复杂度

给出一个递归算法，其时间复杂度通常是递归调用的数量和计算时间复杂度的乘积

总结

合并两个有序链表

两个链表头部较小的一个域剩下的元素merge操作结果合并。

第K个语法符号

Paging

介绍

1

The Paging Library helps you load and display small chunks of data at a time.Loading partial data on demand reduces usage of network bandwidth and system

处理大量数据的处理方法：

1. 借助刷新控件实现用户手动请求数据。
2. 数据到达边界自动请求加载。

优点

• RxJava 2以及Android Jetpack的支持，如LiveData、Room。
• 自定义分页策略。
• 异步处理数据。
• 结合RecyclerView等

实战

创建数据源

1.非Room数据库

2.Room数据库

如果是使用Room与Paging结合的方式呢

1
2
3
4
5

@Dao
interface  CheeseDao {
    @Query("SELECT * FROM Cheese ORDER BY name COLLATE NOCASE ASC")
    fun allCheesedByName() : DataSource.Factory<Int, Cheese>
}

构建LiveData<PagedList>

1
2
3

val allCheeses = dao.allCheesesByName().toLiveData(Config) (pageSize = 30, 
            enablePlaceholders = true,
                maxSize = 200)

创建PagedListAdapter

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

class CheeseAdapter : PagedListAdapter<Cheese, CheeseViewHolder>(diffCallback) {
    override fun onBindViewHolder(holder: CheeseViewHolder, position: Int) {
        holder.bindTo(getItem(position))
    }

    override fun onCreateViewHolder(parent: ViewGroup, viewType: Int): CheeseViewHolder = CheeseViewHolder(parent)

    companion object {
        private val diffCallback = object : DiffUtil.ItemCallback<Cheese>() {
            override fun areItemsTheSame(oldItem: Cheese, newItem: Cheese): Boolean =
                    oldItem.id == newItem.id

            /**
             * Note that in kotlin, == checking on data classes compares all contents, but in Java,
             * typically you'll implement Object#equals, and use it to compare object contents.
             */
            override fun areContentsTheSame(oldItem: Cheese, newItem: Cheese): Boolean =
                    oldItem == newItem
        }
    }
}