给定一个正整数n ，你可以做如下操作：
1.如果n是偶数，则用n / 2替换n 。
2.如果n是奇数，则可以用n + 1或n - 1替换n 。
3.返回 n变为 1 所需的 最小替换次数 。
public class Solution4_03 {
public int integerReplacement(int n) {
var i = 0;
while (n != 1) {
if ((n & 1) == 0) n >>>= 1;//n为偶数则右移一位
else {
if (n == 3) n -= 1;//特殊情况，（3-1）/2只需两步，（3+1）/2/2则需三步
//n为奇数时，看n的二进制，举个例子，0x0111-1=0x0110，还剩两个一，0x0111+1=0x1000，剩 //下一个1，0x0011-1=0x0001，0x0011+1=0x0100,也剩下一个1；
//当n的二进制从第一位开始有连续三位以及三位以上的1时，+1用的步数少，
//当n的二进制从第一位开始有连续两个1时，无论加1还是减1，都是剩下一个1，但是减1使n更快变成 //奇数，之后使用的步数更多，不划算，所以要加一，所以0x...11的情况，加1，3是特殊情况，其余 //情况减1
else if ((n & 3) != 3) n -= 1;
else n += 1;
}
i++;
}
return i;
}
}
给你链表的头节点 head 和一个整数 k 。
交换 链表正数第 k 个节点和倒数第 k 个节点的值后，返回链表的头节点（链表 从 1 开始索引）。
public class Solution4_05 {
public ListNode swapNodes(ListNode head, int k) {
var p1 = head;public class Solution4_05 {
public ListNode swapNodes(ListNode head, int k) {
var p1 = head;//p1负责遍历整个链表
var p2 = head;//p2遍历k节点之前
var p3 = head;//p3遍历倒数k节点之后
var count = 1;
/*
p1与p2一开始同时遍历链表，遍历到k，p2停下，之后，
p1从k开始遍历，p3从第一个节点开始遍历
当p1走到表尾，p3就走到了倒数第k个节点
*/
while (p1.next != null) {
if (count < k) p2 = p2.next;
else p3 = p3.next;
count++;
p1 = p1.next;
}
//交换节点的值
count = p2.val;
p2.val = p3.val;
p3.val = count;
return head;
}
}
给你一个下标从 0 开始的字符串 s ，以及一个下标从 0 开始的整数数组 spaces 。
数组 spaces 描述原字符串中需要添加空格的下标。每个空格都应该插入到给定索引处的字符值 之前 。
例如，s = "EnjoyYourCoffee" 且 spaces = [5, 9] ，那么我们需要在 'Y' 和 'C' 之前添加空格，这两个字符分别于下标 5和下标 9 。因此，最终得到 "Enjoy Your Coffee" 。
请你添加空格，并返回修改后的字符串。
public class Solution4_08 {
public String addSpaces(String s, int[] spaces) {
var builder = new StringBuilder(s);//用StringBuilder操作更简便
int i = 0, j = 1;
for (; i + 1 < spaces.length; i++, j++) {
builder.insert(spaces[i], " ");//循环遍历直接添加空格
//每次添加空格后，都会使后面的字符的索引加一，所以spaces数组的数也要加一
spaces[i + 1] += j;
}
/*
上面那个for只添加了spaces数组索引一以及之后位置的空格，这里补上第一个空格，
如果在for里加上这一步，会使 spaces[i + 1] += j 这个操作的索引范围超出
*/
builder.insert(spaces[i] , " ");
return builder.toString();
}
}
记忆法递归求斐波那契
public class FeiBoNaQie {
public static int feibonaqie(int n) {
/*用一个集合来记录斐波那契数对应的值，在递归中会重复使用到
记录对应的值防止重复计算，需要可以直接在集合中找到，省去了很多计算的时间*/
ArrayList<Integer> list = new ArrayList<>();
list.add(0);
list.add(1);
return f(n, list);
}
public static int f(int n, ArrayList<Integer> list) {
if (list.size() > n) return list.get(n);//集合中有f(n,list),直接用
var x = f(n - 2, list);
var y = f(n - 1, list);
list.add(x + y);//集合没有f(n,list),先存起来，待会就会用得到
return list.get(n);
}
}
我们将整数 x的 权重 定义为按照下述规则将 x变成 1所需要的步数：
如果x是偶数，那么x = x / 2
如果x是奇数，那么x = 3 * x + 1
比方说，x=3 的权重为 7 。因为 3 需要 7 步变成 1 （3 --> 10 --> 5 --> 16 --> 8 --> 4 --> 2 --> 1）。
给你三个整数lo，hi 和k。你的任务是将区间[lo, hi]之间的整数按照它们的权重升序排序，如果大于等于 2 个整数有 相同的权重，那么按照数字自身的数值升序排序。
请你返回区间[lo, hi]之间的整数按权重排序后的第k个数。
注意，题目保证对于任意整数x（lo <= x <= hi），它变成1 所需要的步数是一个 32 位有符号整数。
public class Solution4_09 {
//map用来记录整数x的权重，键为x，值为权重
Map<Integer, Integer> map = new HashMap<>();
//获取对应整数的权重
public int getquan(int n) {
if (n == 1) return 0;//1的权重是0
if (map.containsKey(n)) return map.get(n);//集合里有，直接拿
int t = 0;
if ((n & 1) == 0) t = getquan(n >>> 1) + 1;//n是偶数的情况
else t = getquan(3 * n + 1) + 1;//n是奇数的情况
map.put(n, t);//记录权重
return map.get(n);
}
public int getKth(int lo, int hi, int k) {
int[][] arr = new int[hi - lo + 1][2];//二维数组记录lo到hi之间的整数的权重
for (int i = lo; i <= hi; i++) {
arr[i - lo][0] = i;
arr[i - lo][1] = getquan(i);
}
/*对arr排序, 本来是用lambda表达式的，即Arrays.sort(arr, (a,b)->a[1]-b[1])，
但编译器叫我用Comparator接口，现在还没搞懂*/
Arrays.sort(arr, Comparator.comparingInt(a -> a[1]));
return arr[k - 1][0];
}
}