leetcode刷题总结801-850

801. 使序列递增的最小交换次数

　　描述：

　　思路：

class Solution {
public:
    int minSwap(vector<int>& A, vector<int>& B) {
        int res = 0;
        vector<vector<int>> dp(A.size(),vector(2,0));
        dp[0][0] = 0;
        dp[0][1] = 1;
        for(int i = 1;i < A.size();i++)
        {
            if(A[i-1]<A[i]&&B[i-1]<B[i]){
                if(A[i-1]<B[i] && B[i-1]<A[i]){//任意交换或者不交换，取最优值
                    dp[i][0] = min(dp[i-1][0],dp[i-1][1]);
                    dp[i][1] = min(dp[i-1][0],dp[i-1][1])+1;
                }else{
                    dp[i][0] = dp[i-1][0];//不交换，则上个位置也不能交换
                    dp[i][1] = dp[i-1][1]+1; //交换，则上个位置也必须交换
                }
            }else{
                dp[i][0] = dp[i-1][1];// 不交换，则上个位置必须交换
                dp[i][1] = dp[i-1][0]+1;// 交换，则上个位置不能交换
            }
        }
        return min(dp[A.size()-1][0],dp[A.size()-1][1]);
    }
};

807. 保持城市天际线

　　描述：

　　思路：先对从上到下，从左到右统计。统计完后对每个坐标进行可以增添高度的统计。

808. 分汤

　　描述：

　　思路：

　　转移方程：dp[i][j] = 0.25 * (dp[i-100][j] + dp[i-75][j-25] + dp[i-50][j-50] + dp[i-75][j-25])

　　将N缩小为原来的25分之一的转移方程：dp[i][j] = 0.25 * (dp[i-4][j] + dp[i-3][j-1] + dp[i-2][j-2] + dp[i-3][j-1])

809. 情感丰富的文字　　

　　描述：

　　思路：

　　　　我们首先将 S 拆分成若干组相同的字母，并存储每组字母的长度。例如当 S 为 abbcccddddaaaaa 时，可以得到 5 组字母，它们分别为 abcda，长度为 [1, 2, 3, 4, 5]。

　　　　对于 words 中的每个单词 word，如果它可以扩张得到 S，那么它必须和 S 有相同的字母组。对于每一组字母，假设 S 中有 c1 个，word 中有 c2 个，那么会有下面几种情况：

　　　　如果 c1 < c2，那么 word 不能扩张得到 S；

　　　　如果 c1 >= 3，那么只要添加 c1 - c2 个字母即可；

　　　　如果 c1 < 3，由于在扩张时至少需要添加到 3 个字母，所以此时不能添加字母，必须有 c1 == c2。

　　　　如果 word 的包含的字母组中的每个字母都满足上述情况，那么 word 可以扩张得到 S。

813. 最大平均值和的分组

　　描述：

　　思路：

　　　　dp(i, k) = max(dp(j, k - 1) + average(j + 1, i))
　　　　dp(i, 0) = average(0, i)

814. 二叉树剪枝

　　描述：

　　思路：

class Solution {
    public TreeNode pruneTree(TreeNode root) {
        return containsOne(root) ? root : null;
    }

    public boolean containsOne(TreeNode node) {
        if (node == null) return false;
        boolean a1 = containsOne(node.left);
        boolean a2 = containsOne(node.right);
        if (!a1) node.left = null;
        if (!a2) node.right = null;
        return node.val == 1 || a1 || a2;
    }
}

815. 公交路线

　　描述：

　　思路：广度优先。。。看到最少最低首先想到广度。

817. 链表组件

　　描述：

　　思路：线性扫描即可。

820. 单词的压缩编码

　　描述：
　　　　

　　思路：先set。然后对set去除所有substring(i,length)的字符。然后再计算+1.

825. 适龄的朋友

　　描述：

　　思路：

class Solution {
    public int numFriendRequests(int[] ages) {
        int[] count = new int[121];
        for (int age: ages) count[age]++;

        int ans = 0;
        for (int ageA = 0; ageA <= 120; ageA++) {
            int countA = count[ageA];
            for (int ageB = 0; ageB <= 120; ageB++) {
                int countB = count[ageB];
                if (ageA * 0.5 + 7 >= ageB) continue;
                if (ageA < ageB) continue;
                if (ageA < 100 && 100 < ageB) continue;
                ans += countA * countB;
                if (ageA == ageB) ans -= countA;
            }
        }

        return ans;
    }
}

View Code

829. 连续整数求和

　　描述：

　　思路：

class Solution {
    public int consecutiveNumbersSum(int N) {
        int ans = 0;
        for (int start = 1; start <= N; ++start) {
            int target = N, x = start;
            while (target > 0)
                target -= x++;
            if (target == 0) ans++;
        }
        return ans;
    }
}

836. 矩形重叠

　　描述：

　　思路：

　　　　class Solution {
　　　　　　public boolean isRectangleOverlap(int[] rec1, int[] rec2) {
　　　　　　　　return !(rec1[2] <= rec2[0] || // left
　　　　　　　　　　　　rec1[3] <= rec2[1] || // bottom
　　　　　　　　　　　　rec1[0] >= rec2[2] || // right
　　　　　　　　　　　　rec1[1] >= rec2[3]); // top
　　　　　　}
　　　　}

837. 新21点

　　描述：

　　思路：

//注意动态规划中规划的重复，比如这个题就有重复，可以用窗口完成之前的记录

var new21Game = function (N, K, W) {
 let dp = new Array(N + 1).fill(0)
 dp[0] = 1
 let windowSum = 0
 for (let i = 1; i < N + 1; i++) {
   if (i - W - 1 >= 0) { // 甩掉的dp[i - W - 1]要存在呀
     windowSum -= dp[i - W - 1] // 甩掉上一次window左端
   }
   if (i - 1 < K) { // 新纳入的dp[i - 1]要存在呀，分数i<=K，i-1<K
     windowSum += dp[i - 1]// 纳入上一次window的右侧一项
   }
   dp[i] = windowSum * (1 / W)
 }
 let res = 0
 for (let i = K; i <= N; i++) {
   res += dp[i]
 }
 return res
};

View Code

841. 钥匙和房间

　　描述：

　　思路：

class Solution {
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        boolean[] seen = new boolean[rooms.size()];
        seen[0] = true;
        Stack<Integer> stack = new Stack();
        stack.push(0);

        //At the beginning, we have a todo list "stack" of keys to use.
        //'seen' represents at some point we have entered this room.
        while (!stack.isEmpty()) { // While we have keys...
            int node = stack.pop(); // Get the next key 'node'
            for (int nei: rooms.get(node)) // For every key in room # 'node'...
                if (!seen[nei]) { // ...that hasn't been used yet
                    seen[nei] = true; // mark that we've entered the room
                    stack.push(nei); // add the key to the todo list
                }
        }

        for (boolean v: seen)  // if any room hasn't been visited, return false
            if (!v) return false;
        return true;
    }
}