12.29_黑马数据结构与算法笔记Java

目录

305 旅行商问题 动态规划 实现2

306 旅行商问题 动态规划 实现3

307 分治 概述

308 快速选择算法 分治

309 快速选择算法 数组第k大数 Leetcode215

310 快速选择算法 数组中位数

311 快速幂 分治

312 快速幂 Leetcode50

313 平方根整数部分 Leetcode69-1

314 平方根整数部分 Leetcode69-2

315 至少k个重复字符的最长子串 Leetcode395 分析

316 至少k个重复字符的最长子串 Leetcode395 实现

317 回溯 概况

318 全排列 Leetcode46 分析

319 全排列 Leetcode46 实现

---

305 旅行商问题 动态规划 实现2

以后补

306 旅行商问题 动态规划 实现3

以后补

307 分治 概述

308 快速选择算法 分治

每次以最右边的一个数字为基准点，然后进行排序，逐渐缩小范围。?

309 快速选择算法 数组第k大数 Leetcode215

之前求的是由小到大，现在求的是由大到小

和之前方法的对应关系，就是5-?

310 快速选择算法 数组中位数

311 快速幂 分治

幂是偶数的情况：

?只需要乘4次，乘过的不用再乘

幂是奇数的情况：

要多乘一个2?

改动一下：

312 快速幂 Leetcode50

改动代码：

当n=0或者n=1的时候的情况没有考虑,考虑之后：

当n为负数的情况下，

负数最小值是 -2147483648 但是正数最大值是2147483647 所以负负得正后，会超过max，因此改int为long

另外一种判断奇数偶数的方法：?

与001做按位与的操作，这样子就可以拿到最后一位的数字了。最后一位是0就是偶数，最后一位是1就是奇数

?按位与的运算级较低，因此要用括号括起来

313 平方根整数部分 Leetcode69-1

?常规做法 以上，但如果按照下面这个来做的话，就会快很多

把乘法改为除法，可以避免若m很大的情况下，m*m超过最大值而出的bug这样的情况。??

?

315 至少k个重复字符的最长子串 Leetcode395 分析

316 至少k个重复字符的最长子串 Leetcode395 实现

317 回溯 概况

这种局部变量就不需要手动进行数据恢复

若是数组或者集合，就需要手动的进行数据恢复

318 全排列 Leetcode46 分析

319 全排列Leetcode46 实现

?