这周开始，有一个疯狂的想法，想要刷LeetCode的积分，兑换帽子。仔细想想还是挺好玩的，所以每天又多加了两道easy的题目，就不贴出来了。
算法方面，还是动态规划、贪心算法。对这两个算法还是不是很熟悉，需要多练习。
最近一直在研究IM业务，所以也订阅了一个专栏，但是发现其实看专栏如果只看一遍真的吸收的非常差，得像一个办法去加深自己的印象或者提高看专栏的效率。
1. although
1.1. 每日一题
1.1.1. 快乐数
/**
* 202. 快乐数
* 编写一个算法来判断一个数 n 是不是快乐数。
*
* 「快乐数」定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。如果 可以变为 1，那么这个数就是快乐数。
*
* 如果 n 是快乐数就返回 True ；不是，则返回 False 。
*
*
*
* 示例：
*
* 输入：19
* 输出：true
* 解释：
* 12 + 92 = 82
* 82 + 22 = 68
* 62 + 82 = 100
* 12 + 02 + 02 = 1
*/
将快乐数的每个结果，当做一个链表的形式来看，这道题目就转化为判断一个链表是否有环。
判断一个链表是否有环：快慢指针
public boolean isHappy(int n) {
//将所有的结果看成是一个 链表
//当这个 下次的结果在链表上
//这样问题就转化为 判断一个链表是否有环
//如果没有环那么必定最终结果是1
int slow =n,fast = getSum(n);
while (fast!=1&&slow!=fast){
slow = getSum(slow);
fast = getSum(getSum(fast));
}
return fast==1;
}
private int getSum(int n) {
int temp = n;
int sum = 0;
while (temp>0){
sum+=Math.pow(temp%10,2);
temp = temp/10;
}
return sum;
}
1.1.2. 山脉数组中查找目标值
/**
* Created with IntelliJ IDEA.
* Description:
* User: CDz
* Create: 2020-04-29 20:48
* 1095. 山脉数组中查找目标值
* （这是一个 交互式问题 ）
* <p>
* 给你一个 山脉数组 mountainArr，请你返回能够使得 mountainArr.get(index) 等于 target 最小 的下标 index 值。
* <p>
* 如果不存在这样的下标 index，就请返回 -1。
* <p>
* <p>
* <p>
* 何为山脉数组？如果数组 A 是一个山脉数组的话，那它满足如下条件：
* <p>
* 首先，A.length >= 3
* <p>
* 其次，在 0 < i < A.length - 1 条件下，存在 i 使得：
* <p>
* A[0] < A[1] < ... A[i-1] < A[i]
* A[i] > A[i+1] > ... > A[A.length - 1]
* <p>
* <p>
* 你将 不能直接访问该山脉数组，必须通过 MountainArray 接口来获取数据：
* <p>
* MountainArray.get(k) - 会返回数组中索引为k 的元素（下标从 0 开始）
* MountainArray.length() - 会返回该数组的长度
* <p>
* <p>
* 注意：
* <p>
* 对 MountainArray.get 发起超过 100 次调用的提交将被视为错误答案。此外，任何试图规避判题系统的解决方案都将会导致比赛资格被取消。
* <p>
* 为了帮助大家更好地理解交互式问题，我们准备了一个样例 “答案”：https://leetcode-cn.com/playground/RKhe3ave，请注意这 不是一个正确答案。
* <p>
* <p>
* <p>
* 示例 1：
* <p>
* 输入：array = [1,2,3,4,5,3,1], target = 3
* 输出：2
* 解释：3 在数组中出现了两次，下标分别为 2 和 5，我们返回最小的下标 2。
* 示例 2：
* <p>
* 输入：array = [0,1,2,4,2,1], target = 3
* 输出：-1
* 解释：3 在数组中没有出现，返回 -1。
* <p>
* <p>
* 提示：
* <p>
* 3 <= mountain_arr.length() <= 10000
* 0 <= target <= 10^9
* 0 <= mountain_arr.get(index) <= 10^9
**/
思路：二分查找。
先找到山峰的位置。二分查找的关键是，确定好边界，退出的条件。
public int findInMountainArray(int target, MountainArray mountainArr) {
int r = mountainArr.length() - 1;
int l = 0;
//思路：二分查找
//通过二分查找的方式先找到 山顶
int top = findTopByArray(l, r, mountainArr);
//[0...top] [top+1...len-1]
//从升序[0...top]中查找目标
int index = findTargetBySortArr(l, top, mountainArr, target);
//判断是否找到 若没有
if (index != -1) {
return index;
}
//从降序[top+1...len-1]中查找目标
return findTargetByInversedSortArr(top + 1, r, mountainArr, target);
}
private int findTopByArray(int l, int r, MountainArray mountainArr) {
while (l < r) {
int mid = l + (r - l) / 2;
//左边[l...mid] 右边[mid+1...r]
//判断右边最小的是否大于左边最大的
if (mountainArr.get(mid) < mountainArr.get(mid + 1)) {
//大于 说明还在左边有序列中
l = mid + 1;
} else {
r = mid;
}
}
return l;
}
/**
* 倒序数列中查找 target值
*
* @param l
* @param r
* @param mountainArr
* @param target
* @return
*/
private int findTargetByInversedSortArr(int l, int r, MountainArray mountainArr, int target) {
while (l <= r) {
int mid = l + (r - l) / 2;
int num = mountainArr.get(mid);
if (num == target) return mid;
if (num > target) {
l = mid + 1;
} else {
r = mid - 1;
}
}
// while (l < r) {
// int mid = l + (r - l) / 2;
// int num = mountainArr.get(mid);
// if (num > target) {
// l = mid + 1;
// } else {
// r = mid;
// }
// }
// if (mountainArr.get(l) == target) return l;
return -1;
}
private int findTargetBySortArr(int l, int r, MountainArray mountainArr, int target) {
// while (l < r) {
// int mid = l + (r - l) / 2;
// int num = mountainArr.get(mid);
// //这里如果不考虑相等的情况
// //变动的l必须在判断条件里面
// //因为 当相等时 判断肯定不能进入
// //这时再来加减 左右值就会出错
// if (num < target) {
// l = mid + 1;
// } else {
// r = mid;
// }
// }
// if (mountainArr.get(l) == target) return l;
while (l <= r) {
int mid = l + (r - l) / 2;
int num = mountainArr.get(mid);
if (num == target) return mid;
//这里加减时就需要把mid剔除掉
//即切分成了 [l...mid-1] [mid+1...r]
if (num < target) {
l = mid + 1;
} else {
r = mid - 1;
}
}
return -1;
}
interface MountainArray {
public int get(int index);
public int length();
}
static class MountainArrayImpl implements MountainArray {
private int len;
private int[] arr;
public MountainArrayImpl(int[] arr) {
this.arr = arr;
this.len = arr.length;
}
@Override
public int get(int index) {
return arr[index];
}
@Override
public int length() {
return len;
}
}
1.1.3. 搜索旋转排序数组
/**
* Created with IntelliJ IDEA.
* Description:
* User: CDz
* Create: 2020-04-27 21:53
* 33. 搜索旋转排序数组
* 假设按照升序排序的数组在预先未知的某个点上进行了旋转。
* <p>
* ( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
* <p>
* 搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
* <p>
* 你可以假设数组中不存在重复的元素。
* <p>
* 你的算法时间复杂度必须是 O(log n) 级别。
* <p>
* 示例 1:
* <p>
* 输入: nums = [4,5,6,7,0,1,2], target = 0
* 输出: 4
* 示例 2:
* <p>
* 输入: nums = [4,5,6,7,0,1,2], target = 3
* 输出: -1
**/
/**
* 思路，看到logn级别就需要先到 使用二分法
*
* 如何使用二分法？
*
* 已知条件中，是一个有序列的集合折叠
* 也就是说，通过二分后，可以划分为 一半有序 一半无序
*
* 如果在有序内部，再进行正常的二分
* 如果不在有序的内部，在无序内部进行二分如此循环最终就可以找到
*
* @param nums
* @param target
* @return
*/
public int search(int[] nums, int target) {
int l = 0;
int r = nums.length-1;
while (l<=r){
int mid = l+(r-l)/2;
//left [l...mid]
//right [mid+1...r]
if (nums[mid]==target)return mid;
//找到有序列
if (nums[l]<=nums[mid]){
//左边有序
//再判断是否在有序列的区间内
if (target<nums[mid]&&target>=nums[l]){
//说明在有序列内，且在左边数组中
r = mid;
}else {
l = mid+1;
}
}else {
//右边有序
if (target>=nums[mid+1]&&target<=nums[r]){
l=mid+1;
}else {
r = mid;
}
}
}
return -1;
}
1.1.4. 数组中数字出现的次数
/**
* Created with IntelliJ IDEA.
* Description:
* User: CDz
* Create: 2020-04-28 20:42
*
* 面试题56 - I. 数组中数字出现的次数
* 一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
*
*
*
* 示例 1：
*
* 输入：nums = [4,1,4,6]
* 输出：[1,6] 或 [6,1]
* 示例 2：
*
* 输入：nums = [1,2,10,4,1,4,3,3]
* 输出：[2,10] 或 [10,2]
*
*
* 限制：
*
* 2 <= nums <= 10000
**/
这题关键点，使用位运算来解答。
已知：
n^n=0n^0=n所以我们很容易能找出一个数组中，如果只有一个元素不是重复的，其他都是重复的，找出这个重复的元素。
那么问题就可以转化为：如何将这个数组分组，这两组的特性要满足：
- 相同的元素必须在同一组
- 不同的两个元素必须在不同组
例如：[1,1,2,2,3,4]分组后：
[1,1,3][2,2,4]
如何分组？
很容易能想到的是通过奇偶性质来分组，但是不同的两个数可能都是奇数或者偶数。
问题转化，如何区分两个不同的数？
借助^运算的特性，^的特性是，二进制中：
- 相同位为0
- 不同位为1
所以我们只需要找到，这两个不同的数字^运算后的低位的第一个1的位置就好了。
通过&1运算，&1一般我用来判断是否为奇偶数的，只判断的最后一位，如果我们想找到，其他位，只需要将1<<=1不停的讲1左移就可以试出来。
public int[] singleNumbers(int[] nums) {
//找到两个不同数字的^异或混合数
int sum = 0;
for (int num : nums) {
sum^=num;
}
//找到这两个不同数字的不同分组标记
int mask = 1;
while ((sum&mask)==0){
mask<<=1;
}
//根据mask分组找出两个不同的数字
int a = 0;
int b = 0;
for (int num : nums) {
if ((num&mask)==0){
a^=num;
}else {
b^=num;
}
}
return new int[]{a,b};
}
1.1.5. 最大子序和
/**
* Created with IntelliJ IDEA.
* Description:
* User: CDz
* Create: 2020-05-03 09:46
*
* 53. 最大子序和
* 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
*
* 示例:
*
* 输入: [-2,1,-3,4,-1,2,1,-5,4],
* 输出: 6
* 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
* 进阶:
*
* 如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。
**/
动态规划：
- 假设
f(i)为当前i位置的最优解， f(i)=max(f(i-1)+nums[i],num[i])- 这里的
f(i-1)是控制变量 因为nums[i]必须要加上
public int maxSubArray(int[] nums) {
//动态规划求解
//假设 f(i)为当前 i位置的最优解
//那么f(i) = max(f(i-1)+nums[i],nums[i])
//这里的 f(i-1)是控制变量 因为 nums[i]必须要加上
int res = nums[0];//这里不能初始化为0 因为可能只有一个元素，也有可能所有的元素都小于1
int pre = 0;
for (int i = 0; i < nums.length; i++) {
pre = Math.max(pre+nums[i],nums[i]);
res = Math.max(res,pre);
}
return res;
}
贪心算法，每一步的最优解
public int maxSubArray1(int[] nums) {
//贪心算法
//每一步都需要是最优解
int sum = 0;
int ans = Integer.MIN_VALUE;
for (int num : nums) {
sum+=num;
ans = Math.max(ans,sum);
//当sum小于零时 重新来过
if (sum<0){
sum = 0;
}
}
return ans;
}
1.1.6. 合并两个有序链表
/**
* Created with IntelliJ IDEA.
* Description:
* User: CDz
* Create: 2020-05-01 08:20
* <p>
* 21. 合并两个有序链表
* 将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
* <p>
* 示例：
* <p>
* 输入：1->2->4, 1->3->4
* 输出：1->1->2->3->4->4
**/
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
//使用优先队列求解
PriorityQueue<ListNode> queue = new PriorityQueue<>(Comparator.comparingInt(l -> l.val));
if (l1 != null) {
queue.add(l1);
}
if (l2 != null) {
queue.add(l2);
}
ListNode preHead = new ListNode(-1);
ListNode head = preHead;
while (!queue.isEmpty()) {
ListNode poll = queue.poll();
if (poll == null) continue;
head.next = poll;
if (poll.next != null) {
queue.offer(poll.next);
}
head = head.next;
}
return preHead.next;
}
1.1.7. 无重复字符的最长子串
/**
* Created with IntelliJ IDEA.
* Description:
* User: CDz
* Create: 2020-05-02 09:54
* 3. 无重复字符的最长子串
* 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
* <p>
* 示例 1:
* <p>
* 输入: "abcabcbb"
* 输出: 3
* 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
* 示例 2:
* <p>
* 输入: "bbbbb"
* 输出: 1
* 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
* 示例 3:
* <p>
* 输入: "pwwkew"
* 输出: 3
* 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
* 请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
**/
滑动窗口：关键是是要能确定，滑动窗口的start位置定位。
public int lengthOfLongestSubstring(String s) {
//求解子串 一般都是用滑动窗口的方式
//先使用滑动窗口试一下
int start = 0;
int end = 0;
int ans = 0;
//这一题的关键点在于，滑动窗口的 start位置定位
//当出现重复元素后，start并不一定是从end开始，
//start可能是在 其他位置，所以需要记录一下所有 char的位置
//重复的覆盖
HashMap<Character, Integer> map = new HashMap<>();
while (end < s.length()) {
char alph = s.charAt(end);
if (map.containsKey(alph)){
//有重复更新start
//这里的start也要是最大值才行
start = Math.max(map.get(alph),start);
// start = map.get(alph);
}
ans = Math.max(ans,end-start+1);
//end的原因是 如果重复要从下一个开始
map.put(alph,end+1);
end++;
}
return ans;
}
2. review
3. tip
3.1. LeetCode如何定义难度阶梯的？
写了也有一百多道LeetCode题目了，最近有一个小的疯狂想法，想要积分兑换一个LeetCode周边的帽子。
然后就开始每天刷三道题目，每日一题刷完后，又找来了另外的两道easy题目，发现了LeetCode题目的难度阶梯定义规则。
一般easy题目，是一个小的阶梯技巧，或者一种类型的解题方法。就像是我们做1+2=3这样的一样，或者说是二元一次方程这样的技巧。
一般medium题目，是一个解题技巧或者两个，加上一个数据结构。
而hard题目，可能是比较难的一中技巧，或者两三个技巧混合，加上一个数据结构。
4. share
4.1. Spring核心关系图
4.2. 学习专栏的困惑
4.2.1. 如何阅读专栏？
4.3. 一个让人秃头的计划
刷LeetCode攒积分，换取LeetCode周边帽子
仔细想想真实讽刺，这个帽子是不是刚好挡住了秃了的脑袋。
