力扣记录：剑指offer（2）——JZ13-22

JZ13 机器人的运动范围

• 动态规划DP
  • 时间复杂度O(mn)，空间复杂度O(mn)

class Solution {
    
    public int movingCount(int m, int n, int k) {
    
        //判断特殊情况
        if(k == 0) return 1;
        //定义dp数组dp[i][j]表示i，j位置是否可达
        //可达为1，不可达为0
        int[][] dp = new int[m][n];
        //初始化
        dp[0][0] = 1;
        //计算结果
        int result = 1;
        //开始遍历
        for(int i = 0; i < m; i++){
    
            for(int j = 0; j < n; j++){
    
                //0，0已经计算过
                if(i == 0 && j == 0) continue;
                //不符合条件跳过
                if(digitSum(i) + digitSum(j) > k) continue;
                //上边或左边有一个可达则本位置可达
                if((i - 1 >= 0 && dp[i - 1][j] == 1) || (j - 1 >= 0 && dp[i][j - 1] == 1)) dp[i][j] = 1;
                //计算结果
                result += dp[i][j];
            }
        }
        //返回结果
        return result;
    }
    //计算位数和
    private int digitSum(int num){
    
        int res = 0;
        while(num != 0){
    
            res += (num % 10);
            num /= 10;
        }
        return res;
    }
}

JZ14-I 剪绳子

• 动态规划
  • 时间复杂度O(n^2)，空间复杂度O(n)

class Solution {
    
    public int cuttingRope(int n) {
    
        //定义dp数组dp[i]表示长度为i的绳子剪完最大值为dp[i]
        int[] dp = new int[n + 1];
        //初始化
        dp[2] = 1;
        //遍历
        for(int i = 3; i <= n; i++){
    
            for(int j = 1; j <= i / 2; j++){
    
                //剪两段（一段为1），剪多段，剪两段（一段为j）求最大
                dp[i] = Math.max(dp[i], Math.max(dp[i - j] * j, (i - j) * j));
            }
        }
        //返回结果
        return dp[n];
    }
}

• 数学推导 + 贪心：把绳子尽可能分为长度为3的小段，然后是2，最后是1（1+3替换为2+2）
  • 时间复杂度O(n)，空间复杂度O(1)

class Solution {
    
    public int cuttingRope(int n) {
    
        //判断特殊情况
        if(n == 2) return 1;
        if(n == 3) return 2;
        //计算分成3的个数和余数
        int num = n / 3;
        int rem = n % 3;
        //优先3
        if(rem == 0) return (int)Math.pow(3, num);
        //2不动
        if(rem == 2) return (int)Math.pow(3, num) * 2;
        //将1 + 3替换为2 + 2
        return (int)Math.pow(3, num - 1) * 4;
    }
}

JZ14-II 剪绳子II

• 需要取模，不能使用动态规划，直接数学推导 + 贪心，循环取余
  • 时间复杂度O(n)，空间复杂度O(1)
  • 定义结果为long类型

class Solution {
    
    public int cuttingRope(int n) {
    
        //判断特殊情况
        if(n == 2) return 1;
        if(n == 3) return 2;
        //取模
        int m = 1000000007;
        //定义结果为long类型
        long res = 1L;
        //循环取余
        while(n > 4){
    
            res *= 3;
            res = Math.floorMod(res, m);
            n -= 3;
        }
        //n最后可能为2，3，4
        return Math.floorMod(res * n, m);
    }
}

JZ15 二进制中1的个数

• 暴力法，遍历二进制的每一位
  • 时间复杂度O(logn)，空间复杂度O(1)

public class Solution {
    
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
    
        int res = 0;
        for(int i = 0; i < 32; i++){
    
            //判断当前位是否为1
            if((n & 1) == 1) res++;
            n = n >>> 1;
        }
        return res;
    }
}

• n & (n - 1)：二进制数字 n 最右边的 1 变成 0 ，其余不变（还可以判断n是否为2的幂）*
  • 时间复杂度O(M)，空间复杂度O(1)，M为二进制中1的个数

public class Solution {
    
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
    
        int res = 0;
        while(n != 0){
    
            res++;
            //找到n最右边的1并将其改为0
            n &= (n - 1);
        }
        return res;
    }
}

JZ16 数值的整数次方

• 快速幂，迭代实现
  • 时间复杂度O(logn)，空间复杂度O(1)

class Solution {
    
    public double myPow(double x, int n) {
    
        //判断特殊情况
        if(x == 0.0) return 0.0;
        if(x == 1.0) return 1.0;
        //将负数幂转为正数幂计算
        long N = n;
        if(N < 0){
    
            x = 1 / x;
            N = -N;
        }
        //定义结果
        double res = 1.0;
        //定义每轮乘数
        double mul = x;
        //奇数幂多乘一个，第一N=奇数和最后一次N=1
        //偶数幂只有最后一次N=1
        while(N > 0){
    
            //求余实现
            // if(N % 2 == 1) res *= mul;
            // mul *= mul;
            // N /= 2;
            //二进制实现
            if((N & 1) == 1) res *= mul;
            mul *= mul;
            N >>= 1;
        }
        return res;
    }
}

JZ17 打印从1到最大的n位数

• 暴力法，先求出上限，然后定义数组遍历赋值
  • 时间复杂度O(10^n)，空间复杂度O(1)

class Solution {
    
    public int[] printNumbers(int n) {
    
        //定义结果
        int res = (int)Math.pow(10, n) - 1;
        //打印结果
        int[] result = new int[res];
        for(int i = 0; i < res; i++){
    
            result[i] = i + 1;
        }
        return result;
    }
}

• 大数情况，使用字符串保存数组，全排列
  • 时间复杂度O(10^n)，空间复杂度O(n)

class Solution {
    
    //定义结果
    private int[] result;
    //计数
    private int count = 0;
    public int[] printNumbers(int n) {
    
        //初始化
        result = new int[(int) Math.pow(10, n) - 1];
        //i位的数
        for(int i = 1; i <= n; i++){
    
            //固定第一位，防止第一位为0
            for(char first = '1'; first <= '9'; first++){
    
                char[] num = new char[i];
                //第一位存在数组下标0
                num[0] = first;
                //递归其他位
                traverseNum(num, i, 2);
            }
        }
        return result;
    }
    //递归函数，输入总共有几位，当前第几位
    private void traverseNum(char[] num, int i, int n){
    
// //直接打印
// if(i < n){
    
// System.out.println(String.valueOf(num));
// return;
// }
        //当前位等于总共位时字符串转int存储到结果中
        if(i < n){
    
            result[count++] = Integer.parseInt(String.valueOf(num));
            return;
        }
        //递归下一位，第n位存在下标n-1
        for(char now = '0'; now <= '9'; now++){
    
            num[n - 1] = now;
            //递归
            traverseNum(num, i, n + 1);
        }
    }
}

JZ18 删除链表的节点

• 虚拟头节点，遍历删除
  • 时间复杂度O(n)，空间复杂度O(1)

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */
class Solution {
    
    public ListNode deleteNode(ListNode head, int val) {
    
        //判断特殊情况
        if(head == null) return null;
        //虚拟头结点
        ListNode virtualHead = new ListNode(0);
        virtualHead.next = head;
        //当前节点和上一个节点
        ListNode front = virtualHead;
        ListNode now = head;
        //遍历
        while(now != null){
    
            if(now.val == val){
    //找到要删除的节点
                front.next = now.next;
                break;
            }
            //下一轮
            front = now;
            now = now.next;
        }
        //返回头结点
        return virtualHead.next;
    }
}

JZ19 正则表达式匹配

• 动态规划DP
  • 时间复杂度O(mn)，空间复杂度O(mn)

class Solution {
    
    public boolean isMatch(String s, String p) {
    
        int m = s.length();
        int n = p.length();
        //定义dp数组dp[i][j]表示下标i-1（包括i-1）前的s子串和下标j-1（包括j-1）前的p子串是否匹配
        boolean[][] f = new boolean[m + 1][n + 1];
        //初始化
        //dp[i][0] = false但是dp[0][j]可能为true
        f[0][0] = true;
        //遍历顺序正序
        for (int i = 0; i <= m; ++i) {
    
            for (int j = 1; j <= n; ++j) {
    	//j从1开始
                if (p.charAt(j - 1) == '*') {
    	//如果j-1为*
                    f[i][j] = f[i][j - 2];	//s[i]和p[j - 1]不匹配
                    if (matches(s, p, i, j - 1)) {
    	//s[i]和p[j - 1]匹配
                        f[i][j] = f[i][j] || f[i - 1][j];
                    }
                } else {
    	//如果j-1不为*
                    if (matches(s, p, i, j)) {
    	//s[i]和p[j]匹配
                        f[i][j] = f[i - 1][j - 1];
                    }
                }
            }
        }
        return f[m][n];	//返回结果
    }
    //匹配函数，输入两个字符串及其对应下标
    public boolean matches(String s, String p, int i, int j) {
    
        if (i == 0) {
    
            return false;
        }
        if (p.charAt(j - 1) == '.') {
    
            return true;
        }
        return s.charAt(i - 1) == p.charAt(j - 1);
    }
}

JZ20 表示数值的字符串

• 遍历所有的情况
  • 时间复杂度O(n)，空间复杂度O(1)

class Solution {
    
    public boolean isNumber(String s) {
    
        //遍历所有情况
        //去掉字符串前后的空格
        s = s.trim();
        //判断是否出现e或E
        boolean eNum = false;
        //判断是否出现.
        boolean pNum = false;
        //判断是否出现整数
        boolean nNum = false;
        //遍历字符串
        for(int i = 0; i < s.length(); i++){
    
            if(s.charAt(i) >= '0' && s.charAt(i) <= '9'){
    //该位为数字
                nNum = true;
            }else if(s.charAt(i) == 'e' || s.charAt(i) == 'E'){
    //该位为e或E
                //e只能出现一次
                if(eNum) return false;
                //e前要有数
                if(!nNum) return false;
                eNum = true;
                //e后要有整数
                nNum = false;
            }else if(s.charAt(i) == '.'){
    //该位为点
                //e后不能有点
                if(eNum) return false;
                //最多只能有一个点
                if(pNum) return false;
                pNum = true;
            }else if(s.charAt(i) == '+' || s.charAt(i) == '-'){
    //该位为符号字符
                //只能出现在开头或e后
                if(i != 0 && s.charAt(i - 1) != 'e' && s.charAt(i - 1) != 'E') return false;
            }else{
    //其他都为非法
                return false;
            }
        }
        //判断最后是否整数
        return nNum;
    }
}

• 有限状态自动机*
  • 时间复杂度O(n)，空间复杂度O(1)

//小数表示可省去0，-0.4 = -.4，0.4 = .4；2.、3. = 2、3，小数点前有数，后面可以不跟数代表原数
//注意e8即10的8次幂（8次方），也可以是e-7，但题目要求必须跟整数
//题目规定是数值前后可有空格，中间不能有，这个情况要考虑清楚。s：符号、d：数字
class Solution {
    
    public boolean isNumber(String s) {
    
        Map[] states = {
    
            //0：规定0是初值，字符串表示数值，有4种起始状态，开头空格、符号、数字、前面没有数的小数点
            //其中 开头空格 还是指向states[0]，上一位是 开头空格，下一位可以是 空格、符号、数字、前面没有数的小数点
            new HashMap<>() {
    {
     put(' ', 0); put('s', 1); put('d', 2); put('.', 4); }}, 
            //1：上一位是符号，符号位后面可以是 数字、前面没有数的小数点
            new HashMap<>() {
    {
     put('d', 2); put('.', 4); }},
            //2：上一位是数字，数字的下一位可以是 数字、前面有数的小数点、e、结尾空格
            new HashMap<>() {
    {
     put('d', 2); put('.', 3); put('e', 5); put(' ', 8); }}, 
            //3：上一位是前面有数的小数点，下一位可以是 数字、e（8.e2 = 8e2，和2的情况一样）、结尾空格
            new HashMap<>() {
    {
     put('d', 3); put('e', 5); put(' ', 8); }},
            //4：上一位是前面没有数的小数点，下一位只能是 数字（符号肯定不行，e得前面有数才行） 
            new HashMap<>() {
    {
     put('d', 3); }},
            //5：上一位是e，下一位可以是 符号、数字
            new HashMap<>() {
    {
     put('s', 6); put('d', 7); }},
            //6：：上一位是e后面的符号，下一位只能是 数字
            new HashMap<>() {
    {
     put('d', 7); }},
            //7：上一位是e后面的数字，下一位可以是 数字、结尾空格
            new HashMap<>() {
    {
     put('d', 7); put(' ', 8); }},
            //8：上一位是结尾空格，下一位只能是 结尾空格
            new HashMap<>() {
    {
     put(' ', 8); }}
        };
        int p = 0;
        char t;
        //遍历字符串，每个字符匹配对应属性并用t标记，非法字符标记？
        for(char c : s.toCharArray()) {
    
            if(c >= '0' && c <= '9') t = 'd';
            else if(c == '+' || c == '-') t = 's';
            else if(c == 'e' || c == 'E') t = 'e';
            else if(c == '.' || c == ' ') t = c;
            else t = '?';
            //当前字符标记和任何一种当前规定格式都不匹配，直接返回false
            if(!states[p].containsKey(t)) return false;
            //更新当前字符的规定格式，进入下一个规定的Map数组
            p = (int)states[p].get(t);
        }
        //2（正、负整数）、3（正、负小数）、7（科学计数法）、8（前三种形式的结尾加上空格）
        //只有这四种才是正确的结尾
        return p == 2 || p == 3 || p == 7 || p == 8;
    }
}

JZ21 调整数组顺序使奇数位于偶数前面

• 双指针，左指针找偶数，右指针找奇数，然后交换
  • 时间复杂度O(n)，空间复杂度O(1)

class Solution {
    
    public int[] exchange(int[] nums) {
    
        //双指针
        int leng = nums.length;
        if(leng <= 1) return nums;
        //左指针找偶数
        int left = 0;
        //右指针找奇数
        int right = leng - 1;
        //临时变量用于交换
        int temp = 0;
        //指针相遇结束
        while(left < right){
    
            while(left < right && nums[left] % 2 == 1) left++;
            while(left < right && nums[right] % 2 == 0) right--;
            //交换
            temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
        }
        //返回结果
        return nums;
    }
}

JZ22 链表中倒数第k个节点

• 双指针，左指针指向倒数第k个节点，右指针指向null（相差k+1），然后返回左指针指向节点
  • 时间复杂度O(n)，空间复杂度O(1)

class Solution {
    
    public ListNode getKthFromEnd(ListNode head, int k) {
    
        //双指针
        ListNode left = new ListNode(0);
        ListNode right = new ListNode(0);
        left.next = head;
        right.next = head;
        //相差k+1
        while(k >= 0){
    
            right = right.next;
            k--;
        }
        //右指针指到最后一个节点时
        //左指针指向倒数第k个节点
        while(right != null){
    
            right = right.next;
            left = left.next;
        }
        //返回左指针指向节点
        return left.next;
    }
}