LeetCode 1378、1277、2944

2024-04-18 08:52

文章标签 leetcode 1277 1378 2944

本文主要是介绍LeetCode 1378、1277、2944，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1378
二级排序，compare函数必须是static的

class Solution {
public:struct node {int val;int priority;};static bool compare(const node &n1, const node &n2) {if (n1.priority == n2.priority) {return n1.val < n2.val;}return n1.priority < n2.priority;}int getKth(int lo, int hi, int k) {vector<node> vec(hi - lo + 1, node());for (int i = lo; i <= hi; i++) {vec[i -lo].val = i;int d = i;int p = 0;while(d != 1) {if (d % 2 == 0) {d /= 2;} else {d = d * 3 + 1;}p++;}vec[i-lo].priority=p;}sort(vec.begin(), vec.end(), compare);return vec[k - 1].val;}
};

1277
动态规划，dp[i][j]表示以[i,j]为右下角时，所能拼成的最大的正方形边长

class Solution {
public:int countSquares(vector<vector<int>>& matrix) {int ans = 0;int m = matrix.size();int n = matrix[0].size();std::vector<std::vector<int>> dp(m, std::vector<int>(n, 0));for(int i = 0; i < m; i++) {for(int j = 0; j < n; j++) {if(i == 0 || j == 0) {dp[i][j] = matrix[i][j];ans += dp[i][j];continue;}if (matrix[i][j]) {dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;}ans += dp[i][j];}}return ans;}
};

2944
动态规划，dp[0][size]的赋值需要注意细节

class Solution {
public:int minimumCoins(std::vector<int>& prices) {int size = prices.size();std::vector<std::vector<int>> dp(2, std::vector<int>(size, 0));// dp[0][size]  free// dp[1][size]  no freefor (int i = 0; i < size; i++) {if (i == 0) {dp[0][0] = prices[i];dp[1][0] = prices[i];continue;}dp[1][i] = prices[i] + (dp[0][i - 1] > dp[1][i -1] ? dp[1][i -1] : dp[0][i -1]);int min = INT_MAX;for(int j = (i) / 2; j < i; j++){min = min > dp[1][j] ? dp[1][j] : min;}dp[0][i] = min == INT_MAX ? 0 : min;}return dp[0][size -1] < dp[1][size - 1] ? dp[0][size -1] : dp[1][size - 1];}
};