算法笔记之每周刷题整理

本周关键词：状态压缩DP，树状数组，归并排序，拓扑排序。

题目一：完成所有工作的最短时间 hrad

方法一：状压DP

n个工作分配给k个工人，求让每个工人的最大工作时长最小。观察数据范围：k,n (1~12),考虑状态压缩。枚举出n种工作的所有分配状态。

设dp[i][j]表示i个工人分配了j状态工作的最大时长，j用来表示状态。那么Dij= min(max(dp[i][k],max(j-k))) k表示所有j的子集。

public int minimumTimeRequired(int[] jobs, int k) {
    int n = jobs.lenth;
    int m = 1<<n;
    
    int[][] dp = new int[n][m];
    int[] sum = new int[m];
    
    for(int i=1;i<m;i++){
        int j = Integer.numberOfTrailingZeros(i),x = i^(1<<j);
        sum[i] = sum[x] + jobs[j];
        dp[0][i] = sum[i];
    }
    
    for(int i=1;i<k;i++){
        for(int j=1;j<m;j--){
            int maxn = Integer.MAX_VALUE;
            for(int k=j;k!=0;k=(k-1)&j) {
                maxn = Math.min(maxn,Math.Max(sum[k],dp[i-1][j-k]));
            }
        }
    }
    return dp[k-1][m-1];
}

题目二：最长递增子序列 mid

求数组中严格递增的最长子序列长度

方法一：暴力DP

时间复杂度 O(n^2)
空间复杂度 O(n)

class Solution {
    public int lengthOfLIS(int[] nums) {
		int n = num.length;
        int[] dp = new int[n];
        Arrays.fill(dp,1);
        
        for(int i=1;i<n;i++){
            for(int j=0;j<i;j++){
                dp[i] = Math.max(dp[i],dp[j]+1);
            }
        }
        
        int res = 0;
        for(int num : dp) res = Math.max(num,res);
        
        return res;
    }
}

方法二： DP+二分

更改状态定义，dp[i]表示的是长度为i的递增子序列的最小结尾，那么根据贪心性，如果dp[i]越小，那么后续可能的递增序列越长，起码不会短。同时可以保证dp一定是递增的。如果dp[i]==5,dp[i-1]==7,那么长度为i的递增序列的最大值为5，一定存在i-1序列的最大值<5,故dp[i-1]<7;

那么，遍历nums，在dp中找到dp[i-1]<nums[k]<dp[i]，那么dp[i] = nums[k],此过程可以二分法加速。

时间复杂度：O(nLogn)
空间复杂度：O(n)

class Solution {
    public int lengthOfLIS(int[] nums) {
		List<Integer> dp = new ArrayList<>();
        dp.add(nums[0]);
        for(int i=1;i<nums.length;i++){
            if(nums[i]>dp.get(dp.size()-1)) {
                dp.add(nums[i]);
            }else{
                dp.set(bitSearch(dp,nums[i]),nums[i]);
            }
            //System.out.println(dp.toString());
        }
        return dp.size();
    }
    public int bitSearch(List<Integer> dp,int k){
        int i = 0,j = dp.size()-1;
        int res = 0;
        while(i<=j) {
            int mid = (i+j)>>1;
            if(dp.get(mid)==k) return mid;
            if(dp.get(mid)>k){
                res = mid;
                j = mid-1;
            }else{
                i = mid+1;
            }
        }
        return res;
    }
}

题目三: 递增的三元子序列 mid

解法一: DP

与最长递增子序列求解一致，只不过此时只需保证dp的长度>=3即可。

时间复杂度：O(n)
空间复杂度：O(1)

class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        dp = [nums[0]]
        for num in nums:
            if num > dp[-1]: 
                dp.append(num)
                if len(dp)>=3: return True
            else:
                for i in range(len(dp)):
                    if dp[i]>=num:
                        dp[i] = num
                        break
		return False

题目四：矩阵中的最长递增路径 hard

解法一：拓扑排序+DP

矩阵点之间的最长递增可以抽象成：值小的点对于值大的点有一条有向边。整个矩阵可以抽象成一个有向图，同时递增是单向的，所以最后图是有向无环图。所以可以通过拓扑排序获得线程序列，更具线性序列进行DP。

时间复杂度： O(n)
空间复杂度：O(n)

class Solution {
    public int longestIncreasingPath(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int[] dx = new int[]{1,-1,0,0};
        int[] dy = new int[]{0,0,1,-1};
        int[][] inDegree = new int[m][n];
        Deque<Integer> queue = new LinkedList<>();
        List<Integer> topo = new LinkedList<>();
        // topo
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                for(int k=0;k<4;k++){
                    int x = i+dx[k], y = j+dy[k];
                    if (x>=0 && x<m && y>=0 && y<n && matrix[i][j] > matrix[x][y]) inDegree[i][j]++;
                }
            }
        }
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(inDegree[i][j]==0) queue.offerLast(i*n+j);
            }
        }

        while (!queue.isEmpty()) {
            Integer top = queue.pollFirst();
            topo.add(top);
            int i = top/n, j = top%n;
            for(int k=0;k<4;k++){
                int x = i+dx[k], y = j+dy[k];
                if(x>=0 && x<m && y>=0 && y<n && matrix[x][y] > matrix[i][j]) {
                    inDegree[x][y]--;
                    if(inDegree[x][y] == 0) queue.offerLast(x*n+y);
                }
                
            }
        }
        // dp
        int res = 0;
        int[] dp = new int[n*m];
        //Arrays.fill(dp,1);
        
        for(int i=topo.size()-1;i>=0;i--) {
            int point = topo.get(i);
            int u = point/n, v = point%n;
            for(int k=0;k<4;k++){
                int x = u+dx[k], y = v+dy[k];
                if(x>=0 && x<m && y>=0 && y<n && matrix[u][v] < matrix[x][y]) dp[point] = Math.max(dp[point],dp[x*n+y]);
            }
            dp[point]+=1;
            res = Math.max(res,dp[point]);
        }
        return res;
    }
}

题目五：停在原地的方案数 hard

解法一：2dDP

盲目dfs本题会超时，考虑：k步走到i=0的位置可以由k-1步走到i=1位置的方案数量获得，dp[i][j] = dp[i-1][j+1]+dp[i-1][j-1]

时间复杂度：O(n*k)
空间复杂度：O(n**2)/O(N)

1
2