LRU题目姊妹篇，个人认为这道题难度比LRU大，主要需要记录访问次数，如果访问次数一致再按照LRU访问时间。解题思路参考了力扣官方文章
C++里可以使用set（底层红黑树），排序依据是访问次数和访问时间，因此需要重载比较运算符。
方法一AC代码:
struct Node {
int m_cnt, m_time, m_key, m_value;
Node(int cnt, int time, int key, int value):m_cnt(cnt), m_time(time), m_key(key), m_value(value){}
bool operator < (co......
实现LRU，巧合的是工作当中有实际使用该算法。
class LRUCache {
public:
LRUCache(int capacity) :m_capacity(capacity) {}
int get(int key) {
auto it = cache.find(key);
if(it == cache.end())
return -1;
visited(it);
return it->second.first;
}
void put(int key, int value) {
auto it = cache.find(key);
if(it != cache.end......
暴力破解与最直观的写法：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public......
首先贴出来第一遍写的AC代码，目的就是为了AC，后面从可读性、性能等方面优化。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };......
这道题目，个人认为非常经典，虽然看到题目要求计算不同BST个数，一般会联想到动态规划，但动态规划如何求解递推方程成为了最大的难点。
在之前的题目中我们解决了台阶问题，递推方程相对简单:
定义f(n)表示走到第n台阶可能的走法（每次可以走一个台阶或者两个台阶），那么递推方程：
f(n)=f(n-1)+f(n-2)表示走到第n台阶走法等于走到第n-1台阶的走法加上走到n-2台阶的走法。
而96这道题相对没有那么好写递推公式。
显而易见对这道题目而言DP[n]表示数字n对应不同BST数目，dp[0]=dp[1]=1
dp[2]推导方法为：1 2都可以为根节点：
当1为根节点时左子树为D......
BRUTE FORCE暴力破解方法如下:
class Solution {
public:
int maxArea(vector<int>& height) {
//BRUTE FORCE
int res = 0;
int size = height.size();
for(int i = 0;i<size;i++)
{
for(int j=i+1;j<size;j++)
{
res = max(res,(j - i) * min(height[i],height[j]));
}
}
return res;
}
};
不出意料的Time Limit......
动态规划解法,这里的dp[i][j]表示word1[0----i]变化到word2[0----j]所需要的最小操作步骤。
class Solution {
public:
int minDistance(string word1, string word2) {
int m = word1.size(),n = word2.size();
vector<vector<int>> dp(m+1,vector<int>(n + 1,0));
for(int i = 0;i <= m;i++) dp[i][0] = i;
for(int j = 0;j......
首先尝试暴力破解方法(暴力破解加记忆化，减少重复计算，否则会超时)：
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
if(amount < 1) return 0;
count.resize(amount);
return helper(coins,amount);
}
private:
vector<int> count;
int helper(vector<int>& coins,int amount)
{
if(amount......
这道题有个非常巧妙的方法：
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
vector<int> res;
for(int i = 0;i < nums.size();i++)
{
auto it = lower_bound(res.begin(),res.end(),nums[i]);
if(it == res.end()){
res.push_back(nums[i]);
}
else
*it = nums[i];
}
return res.size();
}
......
假期的周末晚上，刷起来leetcode，2021年第一题，动态规划，走你。
class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
vector<int> mini = triangle[triangle.size() - 1];
for(int i = triangle.size() - 2;i >= 0;i--)
for(int j = 0;j < triangle[i].size();j++)
mini[j] = triangle[i......