[置顶]关于博主

52coder.net是很早之前与同学一起脑洞的域名:中文名可以叫做-我爱程序员。我记得那年冬天孟非主持的非诚勿扰很火,我信誓旦旦的说以后要做一个网站,专门去为程序员解决个人问题,于是就有了现在的这个域名52coder.net。当时比较热衷于论坛,折腾过Discuz,在读书时折腾过,最多的时候同时在线人数超过1000,论坛的注册人数达到了2w左右,现在却早已忘记当初因为什么原因关闭论坛。

博客开始于2017年6月,希望博客用来记录自己的学习过程,渐渐通过几个月的时间喜欢上写点东西,目前学习的内容主要有C语言、数据结构、Linux系统编程、算法、LeetCode等,如果针对文章中的内容有任何疑......

[LeetCode C++实现]1663. Smallest String With A Given Numeric Value

贪心算法,从最后向前填充构造字典序列最小值,字符串初始为n个'a',这样在保证了字符串长度,如果不预先从k中减去n个a,那么在我们计算过程中,有可能会生成小于n个字符的结果,处理起来比较麻烦。

class Solution {

public:

//计算生成字典序最小字符串,贪心算法,从后面开始先使用最大z

string getSmallestString(int n, int k) {

string res(n,'a');

k -= n;

int i = n - 1;

while(k > 0) {

int fill = min(k,25);

k -= 25;

re......

[LeetCode C++实现]460. LFU Cache

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......

[LeetCode C++实现]146. LRU Cache

实现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......

[LeetCode C++实现]1019. Next Greater Node In Linked List

暴力破解与最直观的写法:

/**

* 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......

[LeetCode C++实现]61. Rotate List

首先贴出来第一遍写的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) {}

* };......

[LeetCode C++实现]96. Unique Binary Search Trees

这道题目,个人认为非常经典,虽然看到题目要求计算不同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......

[LeetCode C++实现]11. Container With Most Water

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......

[LeetCode C++实现]72. Edit Distance

动态规划解法,这里的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......

[LeetCode C++实现]322. Coin Change

首先尝试暴力破解方法(暴力破解加记忆化,减少重复计算,否则会超时):

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......