力扣剑指Offer(每日打卡)

力扣门

剑指 Offer 03. 数组中重复的数字–哈希

哈希表

class Solution {
    public int findRepeatNumber(int[] nums) {        
        int l = nums.length;
        int[] hash = new int[l];
        for(int num : nums) {
            hash[num]++;
            if(hash[num] > 1) return num;
        }
        return 0;
    }
}
1
2
3
4
5
6
7
8
9
10
11

*原地交换

class Solution {
    public int findRepeatNumber(int[] nums) {                
        //原地交换
        int l = nums.length;
        for(int i = 0; i < l; i++)  {
            //位置不正确
            while(nums[i] != i) {            
                //交换的位置如果已经正确了，则说明出现重复
                if(nums[nums[i]] == nums[i]) {
                    return nums[i];
                } 
                //否则不断交换，直到位置正确。            
                int tmp = nums[nums[i]];
                nums[nums[i]] = nums[i];
                nums[i] = tmp;
            }     
            //位置正确则i++跳过       
        }        
        return 0;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

剑指 Offer 04. 二维数组中的查找
剑指 Offer 05. 替换空格

剑指 Offer 06. 从尾到头打印链表–链表

先计算长度+数组从后往前赋值

class Solution {
    public int[] reversePrint(ListNode head) {
    	//计算长度
        ListNode tmp = head;
        int l = 0;
        while(tmp != null) {
            l++;
            tmp = tmp.next;
        }
        //反向赋值
        int[] res = new int[l];
        tmp = head;
        while(tmp != null) {
            l--;
            res[l] = tmp.val;
            tmp = tmp.next;
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

递归：避免长度的显示计算

class Solution {

    public int[] reversePrint(ListNode head) {
        dfs(head, 0);
        return res;
    }

    private int[] res;

    private int l;

    public void dfs(ListNode head, int i) {
        if(head == null) {
            l = i;
            //此时l的长度就是链表的长度，初始化结果数组
            res = new int[l];
            return;
        }
        i++; //计数
        dfs(head.next, i); 
        res[l - i] = head.val; //赋值
    }

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

剑指 Offer 07. 重建二叉树
剑指 Offer 09. 用两个栈实现队列
剑指 Offer 10- I. 斐波那契数列

class Solution {
    public int fib(int n) {
        if(n <= 1) return n;
        int f1 = 0;
        int f2 = 1;
        int fn = f1 + f2;        
        for(int i = 3; i <= n; i++) {
            //这里取模是防止后面加法导致超出储存范围
            f1 = f2 % 1000000007;
            f2 = fn % 1000000007;            
            fn = f2 + f1;
        }
        return fn % 1000000007; //最后也需要取模
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

优化

class Solution {
    public int fib(int n) {
        if(n <= 1) return n;
        int f1 = 0;
        int f2 = 1;
        int fn = f1 + f2;        
        for(int i = 3; i <= n; i++) {
            f1 = f2;
            f2 = fn;            
            fn = (f2 + f1) % 1000000007;
        }
        return fn; 
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

剑指 Offer 10- II. 青蛙跳台阶问题
剑指 Offer 11. 旋转数组的最小数字
剑指 Offer 12. 矩阵中的路径
剑指 Offer 14- I. 剪绳子
*剑指 Offer 14- II. 剪绳子 II
数据大范围问题
剑指 Offer 15. 二进制中1的个数
剑指 Offer 16. 数值的整数次方

• 测试用例

  2.00000
  -2147483648
  1.00000
  2147483647
  1
  2
  3
  4

>快速幂：基于二分法的递归
```java
class Solution {
    public double myPow(double x, int n) { 
        if(n == 0) return 1.0;
        if (n < 0)  {
            x = 1.0/x;
            //负数最小值特判
            if(n == Integer.MIN_VALUE){
                x*=x;
                n++;
            }
            n=-n;
        }
        if((n & 1) == 1) {
            //奇数  x^9=x^8 * x
            return myPow(x,n-1) * x;
        } else {
            //偶数  x^8=x^4 * x^4
            double tmp = myPow(x, n >> 1);
            return  tmp * tmp;
        }        
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

快速幂：基于二分法的迭代

class Solution {
    //快速幂：基于二分法的迭代
    public double myPow(double x, int n) { 
        double sum = 1.0;
        //特殊情况
        if(n < 0) {
            x = 1.0 / x;
            if(n == Integer.MIN_VALUE) {
                sum*=x;
                n++;
            }
            n = - n;
        }        
        //8421法则，13对应二进制为1101，即2^13可拆分为2^8 2^4  2^1 
        //思路：我们只要从后往前判断二进制为1的，就进行累乘        
        while(n > 0) {
            if((n & 1) == 1) {
                sum *= x;
            }
            x = x * x; //2^1  2^2  2^4  2^8...
            n = n>>1;  //移位
        }
        return sum;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

剑指 Offer 17. 打印从1到最大的n位数
剑指 Offer 18. 删除链表的节点
**剑指 Offer 19. 正则表达式匹配
剑指 Offer 20. 表示数值的字符串—*题解有限状态机
剑指 Offer 21. 调整数组顺序使奇数位于偶数前面
双指针
O(N)空间复杂度，新建数组，遇到奇数放左边，即从左往右，偶数放右边即从右往左

class Solution {
    public int[] exchange(int[] nums) {
        int l = nums.length;
        int[] res = new int[l];
        int left = 0, right = l - 1;        
        for(int i = 0; i < l; i++) {
            if((nums[i] & 1) == 1) {
                res[left++] = nums[i];
            } else {
                res[right--] = nums[i];          
            }
        }
        return res;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

O(1)空间复杂度 原地修改

class Solution {
    public int[] exchange(int[] nums) {
    	int left = 0, right = nums.length - 1;
        while(left <= right) {
            if((nums[left] & 1) == 1) {
                //奇数则往后
                left++;
            } else {
                //偶数则换到最后面并往前
                int tmp = nums[right];
                nums[right] = nums[left];
                nums[left] = tmp;
                right--;                
            }
        }
        return nums;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

剑指 Offer 22. 链表中倒数第k个节点
剑指 Offer 24. 反转链表
剑指 Offer 25. 合并两个排序的链表
剑指 Offer 26. 树的子结构
思路一：暴力，对每个点进行一次dfs遍历，看了一下题解，就是暴力，没有所谓的优化😅
对每个点进行一次dfs遍历的遍历可以用BFS、也可以用DFS，比BFS快多了，但我不管了😅
剑指 Offer 27. 二叉树的镜像
剑指 Offer 28. 对称的二叉树
剑指 Offer 29. 顺时针打印矩阵（旋转矩阵）
剑指 Offer 30. 包含min函数的栈
剑指 Offer 31. 栈的压入、弹出序列

代码可简化

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        int len = pushed.length;
        if(len == 0) return true;
        //初始化
        Stack<Integer> sk = new Stack<>();        
        int i = 0, j = 0;        
        while(i < len) {            
            if(pushed[i] == popped[j]) {
                //相等则说明压入后直接弹出，所以不用入栈
                j++;
            } else {
                //但栈内元素可能与它相等，例如[2,1,0]和[1,2,0]
                while(!sk.isEmpty() && pushed[sk.peek()] == popped[j]) {
                    sk.pop();
                    j++;
                }
                sk.push(i);//下标或者值都行
            }
            i++;
        }
        //剩下的元素与栈内的元素一一对应
        while(j < len) {
            if(pushed[sk.pop()] != popped[j]) {
                return false;
            }
            j++;
        }  
        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

剑指 Offer 32 - I. 从上到下打印二叉树
剑指 Offer 32 - II. 从上到下打印二叉树 II
剑指 Offer 32 - III. 从上到下打印二叉树 III
剑指 Offer 33. 二叉搜索树的后序遍历序列
*法二待学：单调栈

class Solution {
    private boolean res = true;

    private int postIdx;

    public boolean verifyPostorder(int[] postorder) {
        int[] midorder = Arrays.copyOf(postorder, postorder.length);
        Arrays.sort(midorder);
        System.out.println(Arrays.toString(midorder));
        // //二叉搜索树中序遍历有序
        // 根据后序+中序的构建方式，进行遍历，正常遍历即序列正确，反之错误
        postIdx = postorder.length - 1;
        dfs(midorder, 0, midorder.length - 1, postorder);
        return res;
    }

    public void dfs(int[] midorder, int left, int right, int[]postorder) {
        if(res == false || left > right) return;
        int idx = search(midorder, left, right, postorder[postIdx]);
        if(idx == -1) {
            res = false;
            return;
        }
        postIdx--;
        dfs(midorder, idx + 1, right, postorder);
        dfs(midorder, left, idx - 1, postorder); 
    }

    int search(int[] midorder, int left, int right, int target) {
        while(left <= right) {
            int mid = (left+right) / 2;
            if(midorder[mid] == target) return mid;
            else if(midorder[mid] < target) left = mid + 1;
            else right = mid - 1;     
        }
        return -1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

剑指 Offer 34. 二叉树中和为某一值的路径
剑指 Offer 35. 复杂链表的复制
递归+hashmap

剑指 Offer 36. 二叉搜索树与双向链表

思路就是由于树的双链表的结构是中序遍历的结果，所以我们只要记录每个元素的上一个元素，就能进行拼接链表。以题目例子为例，记录1遍历2，记录2遍历3，纪录3遍历4，记录4遍历5，
可以以最简单的思路去思考，例如先中序遍历获取所有节点，放到List中，那么此时再进行双向链表转换，该怎么做？是不是每次连接都需要前一个元素。所以可以以此进行思考，从而扩展到二叉树。

class Solution {
    private Node prev = null;
    private Node first = null;

    public Node treeToDoublyList(Node root) {
        dfs(root);
        if(first != null && prev != null) {
            first.left = prev;
            prev.right = first;
        }
        return first;
    }

    public void dfs(Node node) {
        if(node == null) return;
        dfs(node.left);
        node.left = prev;
        if(prev != null) {
            prev.right = node;
        } else {
            //第一个
            first = node;
        }
        prev = node;
        dfs(node.right);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

剑指 Offer 39. 数组中出现次数超过一半的数字
*投票算法没想出来
剑指 Offer 40. 最小的k个数
剑指 Offer 41. 数据流中的中位数
剑指 Offer 42. 连续子数组的最大和
剑指 Offer 43. 1～n 整数中 1 出现的次数（不会）
剑指 Offer 44. 数字序列中某一位的数字(超时、内存)
剑指 Offer 45. 把数组排成最小的数（未通过）
问题
[8308,830]
[12121,12]
剑指 Offer 46. 把数字翻译成字符串–DFS
链接

class Solution {
    public int translateNum(int num) {
        String str = String.valueOf(num);
        dfs(str, 0);
        return count;
    }
    private int count = 0;
    public void dfs(String str, int i) {
        if(i == str.length()) {
            count++;
            return;
        } else if(i > str.length()) {
            return;
        }
        dfs(str, i + 1);       
        if(i+1 < str.length()){
            char a = str.charAt(i);
            char b = str.charAt(i+1);
            boolean tf = (a == '2' && b <= '5') || (a == '1');
            if(a != '0' && tf) {
                dfs(str, i+2);
            }            
        }
    }
}

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

*动态规划不会
剑指 Offer 47. 礼物的最大价值
剑指 Offer 48. 最长不含重复字符的子字符串
双指针+哈希

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int len = s.length();
        // 用于判断字符是否存在
        Map<Character, Boolean> map = new HashMap<>();
        int i = 0, j = 0;
        int max = 0;
        while(j < len) {
            char a = s.charAt(j);
            Boolean tf = map.get(a);
            if(tf == null) {
                //加入
                map.put(a, true);
            } else {
                //出现重复，获取和比较字段长度
                int count = j - i;
                if(max < count) {
                    max = count;
                }
                //移除元素，直到map中不存在重复
                while(s.charAt(i) != a) {
                    map.remove(s.charAt(i));
                    i++;
                }
                i++;
            } 
            j++;
        }
        //最后的串没有重复时
        int tmp  = j - i;
        return max < tmp ? tmp : max;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

#剑指 Offer 50. 第一个只出现一次的字符

剑指 Offer 51. 数组中的逆序对
可以学一下归并排序和做一下小和问题，逆序对跟小和问题基本是一样的，只不过是反过来。学习链接
区别就在于merge函数里面的累加

   while(i <= mid && j <= right) {
       if(nums[i] <= nums[j]) {
           tmp[t++] = nums[i++];
       } else {
           //mid - i + 1的元素都大于arr[j]
           sum+= (mid - i + 1);
           tmp[t++] = nums[j++];
       }
   }
1
2
3
4
5
6
7
8
9