leetcode解题思路分析（六十）509 - 518 题

落日映苍穹つ 2023-01-08 08:29 117阅读 0赞

1.  斐波那契  
    计算第n项斐波那契

**可以用动态规划，也可以用公式法**

class Solution { 
    public:
        int fib(int n) 
        { 
            if (n == 0) return 0;
            if (n == 1) return 1;
            
            int beforeLast = 0;
            int before = 1;
            int now = 0;
    
            for (int i = 2; i <= n; i++)
            { 
                now = before + beforeLast;
                beforeLast = before;
                before = now;
            }
            
            return now;
        }
    };

1.  找树左下角的值  
    给定一个二叉树，在树的最后一行找到最左边的值。

**每行存入队列中，然后依次取出并进入下一层即可。其实是BFS思想。**

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */
    class Solution { 
    public:
        int findBottomLeftValue(TreeNode* root)   
        { 
            if (root == NULL) return 0;
            int ret = root->val;
            queue<TreeNode *> m_queue;
    
            m_queue.push(root);
    
            while (m_queue.size())
            { 
                int size = m_queue.size();
    
                while (size)
                { 
                    TreeNode *node = m_queue.front();
                    m_queue.pop();
                    size--;
    
                    if (node->left)
                        m_queue.push(node->left);
                    if (node->right)
                      m_queue.push(node->right);
                }
    
                if (m_queue.size())
                { 
                    ret = m_queue.front()->val;
                }
            }
    
            return ret;
        }
    };

1.  自由之路  
    旋转 ring 拼出 key 字符 key\[i\] 的阶段中：  
    您可以将 ring 顺时针或逆时针旋转一个位置，计为1步。旋转的最终目的是将字符串 ring 的一个字符与 12:00 方向对齐，并且这个字符必须等于字符 key\[i\] 。  
    如果字符 key\[i\] 已经对齐到12:00方向，您需要按下中心按钮进行拼写，这也将算作 1 步。按完之后，您可以开始拼写 key 的下一个字符（下一阶段）, 直至完成所有拼写。

**说是动态规划，其实就是在暴力搜索的基础上记录下了之前查到过得资料以免多次重复工作**

class Solution { 
    public:
        int findRotateSteps(string ring, string key) { 
            vector<int> pos[26];
            for (int i = 0; i < ring.size(); i++) { 
                pos[ring[i] - 'a'].push_back(i);
            }
    
            vector<vector<int>> dp(key.size(), vector<int>(ring.size(), INT_MAX));
            for (int i = 0; i < key.size(); i++) { 
                for (auto j : pos[key[i] - 'a']) { 
                    if (i == 0) { 
                        dp[i][j] = min(dp[i][j], 0 + clac(ring.size(), 0, j) + 1);
                        continue;
                    }
                    
                    for (auto k : pos[key[i - 1] - 'a']) { 
                        dp[i][j] = min(dp[i][j], dp[i - 1][k] + clac(ring.size(), k, j) + 1);
                    }
                }
            }
    
            return *min_element(dp.back().begin(), dp.back().end());
        }
    
        int clac(int len, int a, int b) { 
            return min((len + a - b) % len, (len + b - a) % len);
        }
    };

1.  在每个树行中找最大值  
    您需要在二叉树的每一行中找到最大的值。

**一样也是用队列**

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */
    class Solution { 
    public:
        vector<int> largestValues(TreeNode* root) 
        { 
            vector<int> ret;
            if (root == NULL) return ret;
            queue<TreeNode *> m_queue;
            int max = INT_MIN;
    
            m_queue.push(root);
            do
            { 
                int size = m_queue.size();
    
                for (int i = 0; i < size; i++)
                { 
                    TreeNode *tmp = m_queue.front();
                    m_queue.pop();
    
                    if (max < tmp->val)
                    { 
                        max = tmp->val;
                    }
    
                    if (tmp->left) m_queue.push(tmp->left);
                    if (tmp->right) m_queue.push(tmp->right);
                }
    
                ret.push_back(max);
                max = INT_MIN;
            } while (m_queue.size());
    
            return ret;
        }
    };

1.  最长回文子序列  
    给定一个字符串 s ，找到其中最长的回文子序列，并返回该序列的长度。可以假设 s 的最大长度为 1000 。

**但凡涉及最长子序列，都可以采用动态规划求解。套用动态规划常见模板即可得解。**

class Solution { 
    public:
    int longestPalindromeSubseq(string s) { 
        int n = s.size();
        // dp 数组全部初始化为 0
        vector<vector<int>> dp(n, vector<int>(n, 0));
        // base case
        for (int i = 0; i < n; i++)
            dp[i][i] = 1;
        // 反着遍历保证正确的状态转移
        for (int i = n - 1; i >= 0; i--) { 
            for (int j = i + 1; j < n; j++) { 
                // 状态转移方程
                if (s[i] == s[j])
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                else
                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
        // 整个 s 的最长回文子串长度
        return dp[0][n - 1];
    }
    
    
    };

1.  超级洗衣机  
    假设有 n 台超级洗衣机放在同一排上。开始的时候，每台洗衣机内可能有一定量的衣服，也可能是空的。  
    在每一步操作中，你可以选择任意 m （1 ≤ m ≤ n） 台洗衣机，与此同时将每台洗衣机的一件衣服送到相邻的一台洗衣机。给定一个非负整数数组代表从左至右每台洗衣机中的衣物数量，请给出能让所有洗衣机中剩下的衣物的数量相等的最少的操作步数。如果不能使每台洗衣机中衣物的数量相等，则返回 -1。

**首先判断一下边界条件等，然后取出平均数，接着根据平均数计算最大流，返回值从最大流和当前流中取最值**

class Solution { 
    public:
        int findMinMoves(vector<int>& machines) { 
            int size = machines.size();
            int total = 0;
            if (size == 0) return -1;
    
            for (auto n : machines)
            { 
                total += n;
            }
    
            if (total % size != 0) return -1;
    
            int step = 0, average = total / size;
            int maxFlowCnt = 0;
    
            for (auto n : machines)
            { 
                maxFlowCnt += n - average;
                step = max(step, max(abs(maxFlowCnt), n - average));
            }
    
            return step;
        }
    };

1.  零钱兑换2  
    给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。

**本题是经典动态规划，可以和爬楼梯作为比较案例学习。相对于爬楼梯，这里的区别其实是排列和组合的区别：先给1块后给2块和掉过顺序是一样的结果，但是爬楼梯则不是，因此这里的循环内外层顺序是反的，而且也不便于使用动态规划降维**

class Solution 
    { 
    public:
        int change(int amount, vector<int>& coins) 
        { 
            if (amount == 0) return 1;
            if (coins.size() == 0) return 0;
    
            vector<int> dp(amount + 1, 0);
            dp[0] = 1;
            
            for (auto coin : coins)
            { 
                for (int i = coin; i <= amount; i++)
                { 
                    dp[i] += dp[i - coin];
                }
            }
            
            return dp[amount];
        }
    };