[数据结构与算法]力扣day21

91. 解码方法

动态规划，爬楼梯

     public static int numDecodings(String s) {
        int n = s.length();
        s = " " + s;
        char[] cs = s.toCharArray();
        int[] f = new int[n + 1];
        f[0] = 1;
        for (int i = 1; i <= n; i++) {
            // a : 代表「当前位置」单独形成 item
            // b : 代表「当前位置」与「前一位置」共同形成 item
            int a = cs[i] - '0', b = (cs[i - 1] - '0') * 10 + (cs[i] - '0');
            // 如果 a 属于有效值，那么 f[i] 可以由 f[i - 1] 转移过来
            if (1 <= a && a <= 9) f[i] = f[i - 1];
            // 如果 b 属于有效值，那么 f[i] 可以由 f[i - 2] 或者 f[i - 1] & f[i - 2] 转移过来
            if (10 <= b && b <= 26) f[i] += f[i - 2];
        }
        return f[n];
     }

92.反转链表2

头插法

    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode node=new ListNode();
        node.next=head;
        ListNode i=node;
        ListNode j=node.next;
        //找到插入头和第一个交换的元素
        for (int step = 0; step < left-1; step++) {
            i=i.next;
            j=j.next;
        }
        // 1 2 3 4 5
        for (int k = 0; k < right-left; k++) {
            ListNode nextNode=j.next;   // next=3
            j.next=j.next.next;     //2->4
            nextNode.next=i.next;   //3->2
            i.next=nextNode;        //1->3   1 3 2 4 5 
        }
        return node.next;
    }

93.复原IP地址

        List<String> result = new ArrayList<>();

        public List<String> restoreIpAddresses(String s) {
            if (s.length() > 12) return result; // 算是剪枝了
            backTrack(s, 0, 0);
            return result;
        }

        // startIndex: 搜索的起始位置， pointNum:添加逗点的数量
        private void backTrack(String s, int startIndex, int pointNum) {
            if (pointNum == 3) {// 逗点数量为3时，分隔结束
                // 判断第四段?字符串是否合法，如果合法就放进result中
                if (isValid(s,startIndex,s.length()-1)) {
                    result.add(s);
                }
                return;
            }
            for (int i = startIndex; i < s.length(); i++) {
                if (isValid(s, startIndex, i)) {
                    s = s.substring(0, i + 1) + "." + s.substring(i + 1);    //在str的后?插??个逗点
                    pointNum++;
                    backTrack(s, i + 2, pointNum);// 插?逗点之后下?个?串的起始位置为i+2
                    pointNum--;// 回溯
                    s = s.substring(0, i + 1) + s.substring(i + 2);// 回溯删掉逗点
                } else {
                    break;
                }
            }
        }

        // 判断字符串s在左闭?闭区间[start, end]所组成的数字是否合法
        private Boolean isValid(String s, int start, int end) {
            if (start > end) {
                return false;
            }
            if (s.charAt(start) == '0' && start != end) { // 0开头的数字不合法
                return false;
            }
            int num = 0;
            for (int i = start; i <= end; i++) {
                if (s.charAt(i) > '9' || s.charAt(i) < '0') { // 遇到?数字字符不合法
                    return false;
                }
                num = num * 10 + (s.charAt(i) - '0');
                if (num > 255) { // 如果?于255了不合法
                    return false;
                }
            }
            return true;
        }

95.不同的二叉搜索树

太抽象了，如果换成别的可能好想，树结构这么看抽象了

    public List<TreeNode> generateTrees(int n) {
        return generateTrees(1, n);
    }

    private List<TreeNode> generateTrees(int start, int end) {
        List<TreeNode> curRes = new LinkedList<>();
        if (start > end) {
            curRes.add(null);
            return curRes;
        }
        for (int i = start; i <= end; i++) {
            List<TreeNode> leftNodeList = generateTrees(start, i - 1);
            List<TreeNode> rightNodeList = generateTrees(i + 1, end);

            for (TreeNode leftNode : leftNodeList) {
                for (TreeNode rightNode : rightNodeList) {
                    curRes.add(new TreeNode(i, leftNode, rightNode));
                }
            }
        }

        return curRes;
    }

96.不同的二叉搜索树

    public int numTrees(int n) {
        if (n <= 2) return n;
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                //一共i个结点，除去自身还有i-1个
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }
        return dp[n];
    }