头像

skymiles

Alibaba


访客:4053

离线:12小时前



skymiles
20小时前

题目描述

688.png

样例

Example:

输入: 3, 2, 0, 0
输出: 0.0625
解释: 
输入的数据依次为 N, K, r, c
第 1 步时,有且只有 2 种走法令 “马” 可以留在棋盘上(跳到(1,2)或(2,1))。对于以上的两种情况,各自在第2步均有且只有2种走法令 “马” 仍然留在棋盘上。
所以 “马” 在结束后仍在棋盘上的概率为 0.0625。


算法

(DFS+memo) O(k∗N^2)

Acwing 1116题目马走日思路,只不过为了避免重复搜索,需要多加一个memo三维数组,表示从[r,c]为原点走K步(每次走日字),能不出界概率。

Java 代码


public class Solution {

    double memo[][][] = null;
    int[] dx = new int[]{-2, -1, 1, 2, 2, 1, -1, -2};
    int[] dy = new int[]{1, 2, 2, 1, -1, -2, -2, -1};

    public double knightProbability(int N, int K, int r, int c) {
        // 从[r,c]为原点走K步(每次走日字)的不出界概率
        memo = new double[26][26][101];
        return dfs(N, r, c, K);
    }

    private double dfs(int N, int r, int c, int K) {
        if (r >= N || r < 0 || c >= N || c < 0) {
            return 0.0;
        }

        if (memo[r][c][K] != 0.0) {
            return memo[r][c][K];
        }

        if (K == 0) {
            return 1.0;
        }


        double res = 0.0;
        for (int i = 0; i < 8; i++) {
            int x = r + dx[i];
            int y = c + dy[i];
            res += 0.125 * dfs(N, x, y, K - 1);
        }
        memo[r][c][K] = res;
        return res;
    }

}




skymiles
21小时前

题目描述

Given an unsorted array of integers, find the number of longest increasing subsequence.

样例

Example 1:
Input: [1,3,5,4,7]
Output: 2
Explanation: The two longest increasing subsequence are [1, 3, 4, 7] and [1, 3, 5, 7].


Example 2:
Input: [2,2,2,2,2]
Output: 5


Explanation: The length of longest continuous increasing subsequence is 1, and there are 5 subsequences' length is 1, so output 5.

Note: Length of the given array will be not exceed 2000 and the answer is guaranteed to be fit in 32-bit signed int.


算法

(动态规划) O(n^2)

由类似LeetCode300+数据范围基本确认是dp题目,做法类似300,但新加一个数组times表示记录以i为结尾的子序列里面包含的最长上升子序列出现的组合出现次数。times[i]的数字只和dp[j] + 1 和 dp[i]之间的大小关系确定,具体看我代码注释的思路。

Java 代码

public class Solution {

    public int findNumberOfLIS(int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }

        // dp(i) 记录以i为结尾的子序列里面包含的最长上升子序列的数字个数
        // d(i) = max{1, d(j)+1},其中j<i,A[j]<=A[i], 初始值1
        int[] dp = new int[n];

        // times(i) 记录以i为结尾的子序列里面包含的最长上升子序列出现的组合出现次数
        int[] times = new int[n];
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
            times[i] = 1;
        }

        int maxLen = 1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] <= nums[j]) {
                    continue;
                }

                // 找到更长的了
                if (dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1;
                    // 这个可以这么理解:当[...j]形成的组合数是值的话,其每一种组合结尾补上[i],即[...j,i],对于组合数本身是没有增加的,还是dp值,唯独只是递增子序列的长度+1了
                    times[i] = times[j];
                } else if (dp[j] + 1 == dp[i]) {
                    // 找到一个一样长的了
                    // 现在的组合次数+counter[j]的组合次数
                    times[i] += times[j];
                }
            }
            maxLen = Math.max(maxLen, dp[i]);
        }

        int res = 0;
        for (int i = 0; i < n; i++) {
            if (dp[i] == maxLen) {
                res += times[i];
            }
        }

        return res;
    }

}




题目描述

在一个 m x n 的网格上有一个球,给定球的起点坐标 (i, j),你每次可以将这个球移动到四个方向(上下左右)相邻的格子上或者移出网格边界。然而,你最多可以移动 N 次。求出所有可以将球移出网格边界的路径数量。答案数可能很大,返回模 109+7109+7 后的结果。

样例

截屏.png


算法1

(动态规划) O(n^3)

1.从边界到出发点的逆向移动。令边界上的格子的初始值为1(起点),考虑经过N步之后,到达(i,j)的方案有多少。
dp[i,j,k] = dp[i-1,j,k-1] +  dp[i+1,j,k-1] + dp[i,j-1,k-1] + dp[i,j+1,k-1];

2.对于那些处在边界的格子,必须在每一步都赋值为1

Java 代码

class Solution {

    public int findPaths(int m, int n, int N, int i, int j) {
        // 从任意界外走N步到点[i,j]的方案总数
        int[][][] dp = new int[N + 1][m][n];
        for (int k = 1; k <= N; k++) {
            for (int x = 0; x < m; ++x) {
                for (int y = 0; y < n; ++y) {
                    long v1 = (x == 0) ? 1 : dp[k - 1][x - 1][y];
                    long v2 = (x == m - 1) ? 1 : dp[k - 1][x + 1][y];
                    long v3 = (y == 0) ? 1 : dp[k - 1][x][y - 1];
                    long v4 = (y == n - 1) ? 1 : dp[k - 1][x][y + 1];
                    dp[k][x][y] = (int) ((v1 + v2 + v3 + v4) % 1000000007);
                }
            }
        }

        return dp[N][i][j];
    }
}




题目描述

You have n super washing machines on a line. Initially, each washing machine has some dresses or is empty.

For each move, you could choose any m (1 ≤ m ≤ n) washing machines, and pass one dress of each washing machine to one of its adjacent washing machines at the same time .

Given an integer array representing the number of dresses in each washing machine from left to right on the line, you should find the minimum number of moves to make all the washing machines have the same number of dresses. If it is not possible to do it, return -1.

样例

Example1

Input: [1,0,5]

Output: 3

Explanation: 
1st move:    1     0 <-- 5    =>    1     1     4
2nd move:    1 <-- 1 <-- 4    =>    2     1     3    
3rd move:    2     1 <-- 3    =>    2     2     2   
Example2

Input: [0,3,0]

Output: 2

Explanation: 
1st move:    0 <-- 3     0    =>    1     2     0    
2nd move:    1     2 --> 0    =>    1     1     1     
Example3

Input: [0,2,0]

Output: -1

Explanation: 
It's impossible to make all the three washing machines have the same number of dresses. 


算法

(枚举) O(n)

这题拿到没思路,不会做,看了 解答 ,真的是奇怪的知识又增加了......

参考文献

https://leetcode-cn.com/problems/super-washing-machines/solution/chao-ji-xi-yi-ji-by-leetcode/

Java 代码

class Solution {

    public int findMinMoves(int[] machines) {
        if (machines == null || machines.length == 0) {
            return 0;
        }

        int n = machines.length, dressTotal = 0;
        for (int i = 0; i < n; i++) {
            dressTotal += machines[i];
        }

        if (dressTotal % n != 0) {
            return -1;
        }

        // 为了方便计算,我们可以将所有的 N 个数分别减去 D / N,这样若第 i 台洗衣机对应的数为正数,说明它需要拿出衣服分给别的洗衣机;若第 i 台洗衣机对应的数为负数,说明它需要从别的洗衣机得到衣服。
        int dressPerMachine = dressTotal / n;
        for (int i = 0; i < n; i++) {
            machines[i] -= dressPerMachine;
        }
        // 前缀和
        int currSum = 0;
        // 前缀和的绝对值的最大值
        int maxSum = 0;
        int res = 0, tmpRes = 0;
        for (int m : machines) {
            currSum += m;
            maxSum = Math.max(maxSum, Math.abs(currSum));
            tmpRes = Math.max(maxSum, m);
            res = Math.max(res, tmpRes);
        }

        return res;
    }
}



题目描述

Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.

You have the following 3 operations permitted on a word:

Insert a character
Delete a character
Replace a character

样例

Example 1:

Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation: 
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')
Example 2:

Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation: 
intention -> inention (remove 't')
inention -> enention (replace 'i' with 'e')
enention -> exention (replace 'n' with 'x')
exention -> exection (replace 'n' with 'c')
exection -> execution (insert 'u')

算法

(动态规划) O(mn)
先考虑最后一步,那至少必须是A[m - 1] == B[n - 1], 要达到这个目的,分成4种情况:
1. 在A串末尾插入B串最后一个字符B[n - 1]
2. A串和B串末尾字符本身就一样
3. A串末尾字符换成B[n - 1]
4. A串末尾删除一个字符

share.jpg

Java 代码

class Solution {

    public int minDistance(String a, String b) {

        int m = a.length();
        int n = b.length();

        // 表示a的前i个字符和b的前j个字符最小的编辑距离
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                dp[i][j] = 0x3f3f3f3f;
                if (i== 0) {
                    dp[i][j] = j;
                    continue;
                }
                if (j == 0) {
                    dp[i][j] = i;
                    continue;
                }

                dp[i][j] = Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
                if (a.charAt(i - 1) == b.charAt(j - 1)) {
                    dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - 1]);
                }
            }
        }

        return dp[m][n];
    }
}



skymiles
13天前

题目描述

Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

Example:

Input: “aab”
Output: 1
Explanation: The palindrome partitioning [“aa”,”b”] could be produced using 1 cut.

算法

(动态规划) O(n^3)

尼玛,我这样写也过了。。。。。。判断j到i-1之前的子串是否是回文,我用的是遍历求法。而且每换一次划分,就需要重算一个是否回文。感觉之后再做这题,需要优化这个判断回文的复杂度。应该是可以优化到O(n^2)的

bad_ac.png

tm.png

Java 代码

class Solution {
    public int minCut(String s) {
        if (s == null || s.equals("")) {
            return 0;
        }

        int n = s.length();
        if (n == 1) {
            return 0;
        }

        // 前i个字符串最少可以划分成dp[i]个回文串
        int dp[] = new int[n + 1];
        dp[0] = 0;

        for (int i = 1; i <= n; i++) {
            dp[i] = Integer.MAX_VALUE;
            for (int j = 0; j <= i - 1; j++) {
                if (isPalindrome(s.substring(j, i - 1 + 1))) {
                    dp[i] = Math.min(dp[i], dp[j] + 1);
                }
            }
        }

        return dp[n] - 1;
    }

    public boolean isPalindrome(String s) {
        int low = 0;
        int high = s.length() - 1;
        //当字符串有奇数个字符时,不用检查中间字符
        while (low < high) {
            if (s.charAt(low) != s.charAt(high)) {
                return false;
            }
            low++;
            high--;
        }
        return true;
    }
}



skymiles
15天前

题目描述

你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组,计算你在不触动警报装置的情况下,能够偷窃到的最高金额。

示例 1:

输入: [2,3,2]
输出: 3
解释: 你不能先偷窃 1 号房屋(金额 = 2),然后偷窃 3 号房屋(金额 = 2), 因为他们是相邻的。
示例 2:

输入: [1,2,3,1]
输出: 4
解释: 你可以先偷窃 1 号房屋(金额 = 1),然后偷窃 3 号房屋(金额 = 3)。
  偷窃到的最高金额 = 1 + 3 = 4 。


算法

(动态规划) O(n)

思路

本题为环形版本打家劫舍,正常来说碰到环形问题,都可以将原数组添加到环上,然后做处理。
两种情况
    1. 偷下标[0, n - 2]之间的房子, 当然边界可以偷可以不偷,看结果大小
    2. 偷下标[1, n - 1]之间的房子
只要对这两种情况求出相应的最高金额即可,用dp[i]表示偷第i栋以及之前的房子获得的金额。

hr2.jpg

Java 代码

public class Solution {

    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }

        if (n == 1) {
            return nums[0];
        }

        return Math.max(hepler(nums, 0, n - 2), hepler(nums, 1, n - 1));
    }

    private int hepler(int[] nums, int start, int end) {
        if (end - start == 0) {
            return nums[start];
        }

        if (end - start == 1) {
            return Math.max(nums[start], nums[end]);
        }

        // dp[i]表示偷第i栋以及之前的房子获得的金额
        int[] dp = new int[end - start + 1];
        dp[0] = nums[start];
        dp[1] = Math.max(nums[start], nums[start + 1]);

        for (int i = 2; i < dp.length; i++) {
            // 1. 偷第i栋房,i-1就不能偷了
            // 2. 不偷第i栋房,直接看dp[i-1]能偷多少就行了
            dp[i] = Math.max(dp[i - 2] + nums[start + i], dp[i - 1]);
        }

        return dp[dp.length - 1];
    }

}





skymiles
15天前

题目描述

你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。

 

示例 1:

输入:[1,2,3,1]
输出:4
解释:偷窃 1 号房屋 (金额 = 1) ,然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。
示例 2:

输入:[2,7,9,3,1]
输出:12
解释:偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9),接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。
 

提示:

0 <= nums.length <= 100
0 <= nums[i] <= 400

算法

(动态规划) O(n)
如果房屋数量大于两间,应该如何计算能够偷窃到的最高总金额呢?有两个选项:

- 偷窃第 k 间房屋,那么就不能偷窃第 k-1 间房屋,偷窃总金额为前 k-2 间房屋的最高总金额与第 k 间房屋的金额之和。

- 不偷窃第 k 间房屋,偷窃总金额为前 k-1 间房屋的最高总金额。

在两个选项中选择偷窃总金额较大的选项就是答案。

用 dp[i] 表示前 i间房屋能偷窃到的最高总金额,那么就有如下的状态转移方程

Java 代码

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return nums[0];
        }

        // dp[i]表示偷第i栋以及之前的房子获得的金额
        int dp[] = new int[n];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < n; i++) {
            // 1. 偷第i栋房,i-1就不能偷了 
            // 2. 不偷第i栋房,直接看dp[i-1]能偷多少就行了 
            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
        }

        return dp[n - 1];
    }
}



skymiles
15天前

题目描述

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

Example:

Input:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.


算法

(动态规划) O(m*n)
实在比较简单,不写过程了, 思路就是转移时候每个点[i,j] 只会从 [i-1, j] 和 [i, j-1]转移过来。
定义二维数组dp[i][j]就可以了。
空间复杂度先不优化了。

Java 代码

public class Solution {

    public int minPathSum(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }

        int m = grid.length;
        int n = grid[0].length;

        // 表示(0, 0)走到(m-1, n-1)的路径最小数字总和
        int[][] dp = new int[m][n];
        dp[0][0] = grid[0][0];

        // 第一行
        for (int j = 1; j < n; j++) {
            dp[0][j] = dp[0][j - 1] + grid[0][j];
        }

        // 第一列
        for (int i = 1; i < m; i++) {
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }

        return dp[m - 1][n - 1];
    }
}




skymiles
15天前

题目描述

给定一个未经排序的整数数组,找到最长且连续的的递增序列,并返回该序列的长度。

示例 1:

输入: [1,3,5,4,7]
输出: 3
解释: 最长连续递增序列是 [1,3,5], 长度为3。
尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的,因为5和7在原数组里被4隔开。
示例 2:

输入: [2,2,2,2,2]
输出: 1
解释: 最长连续递增序列是 [2], 长度为1。

注意:数组长度不会超过10000。


算法

(动态规划) O(n)
步骤一:确定状态
       最长连续上升序列,一定是以某个元素nums[j] (j<=i)为结尾,但是不一定是当前这位置nums[i]。
       分两种情况:
       1. nums[j]一个就是组成最长连续上升序列,之前是下降的序列。
       2. nums[j-1] < nums[j],所以问题可以看子问题求以某个元素nums[j-1]为结尾的长度 + 1

       状态: dp[i] 取得以nums[i]为结尾的最长连续上升序列长度

步骤二:确定转移方程
       dp[i] = 1 (nums[i-1] >= nums[i])  or  dp[i-1] + 1 (nums[i-1] < nums[i])


步骤三:确定初始状态/边界状态
       dp数组初始值都为 = 1

步骤四:计算顺序遍历计算dp[0], dp[1], dp[2]...dp[n - 1]

Java 代码

public class Solution {

    public static int findLengthOfLCIS(int[] nums) {
        int n = nums.length;
        if (n == 0 || n == 1) {
            return n;
        }

        int res = 1;
        //  以下标i结尾的的最长上升序列个数
        int[] dp = new int[n];
        dp[0] = 1;
        for (int i = 1; i < n; i++) {
            dp[i] = 1;
            if (nums[i] > nums[i - 1]) {
                dp[i] = dp[i - 1] + 1;
            } else {
                dp[i] = 1;
            }
            res = Math.max(res, dp[i]);
        }

        return res;
    }
}