ShizhengLee

4.9万

rsy

StkOvflow

bre

six_one
hanwenwang
4ppleS
hulian425

yangdaxian

IF_3
lorendw7
EdwardNygma
shinyruo319
Oinng

class Solution {
public:
int nthUglyNumber(int n) {
vector<int> q(1, 1);
int i = 0, j = 0, k = 0;
while ( -- n) {
int t = min(q[i] * 2, min(q[j] * 3, q[k] * 5)); // 三路归并的最小值
q.push_back(t);
if (t == q[i] * 2) i ++;
if (t == q[j] * 3) j ++;
if (t == q[k] * 5) k ++;
}
return q.back(); // 返回q序列的最后一个值
}
};


class Solution {
public:
int lengthOfLongestSubstring(string s) {
if (s.empty()) return 0;
if (s.size() == 1) return 1;
int res = 0, left = -1;
unordered_map<char, int> hash;
for (int i = 0; i < s.length(); i ++) {
if (hash.find(s[i]) != hash.end()) { // s[i]在hash表中，就更新左指针left
left = max(hash[s[i]], left);
}
hash[s[i]] = i; //更新右指针
res = max(res, i - left);
}
return res;
}
};



class Solution {
public:
int maxValue(vector<vector<int>>& grid) {
int n = grid.size(), m = grid[0].size();
vector<vector<int>> f(n + 1, vector<int>(m + 1));
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= m; j ++) {
f[i][j] = max(f[i -1][j], f[i][j - 1]) + grid[i -1][j - 1];
}
}
return f[n][m];
}
};



class Solution {
public:
int getTranslationCount(string s) {
int n = s.size();
vector<int> f(n + 1);
f[0] = 1;
for (int i = 1; i <= n; i ++) {
f[i] = f[i - 1];
int t = (s[i - 2] - '0') * 10 + s[i - 1] - '0';
if (t >= 10 && t <= 25)  f[i] += f[i- 2];
}
return f[n];
}
};



ShizhengLee
1个月前
class Solution {
public:

static bool cmp(int a, int b) {
auto as = to_string(a), bs = to_string(b);
return as + bs < bs + as; // 字符串拼接后比较: ab < ba; string这里的“+” 就是拼接到一起
}

string printMinNumber(vector<int>& nums) {
sort(nums.begin(), nums.end(), cmp);
string res;
for (auto x: nums) res += to_string(x);
return res;
}
};



ShizhengLee
1个月前
class Solution {
public:
int findNthDigit(int n) {
if (!n) return 0;

long long i = 1; // i表示位数，从1位开始枚举
long long s = 9; // s表示这一位共有多少个数
long long base = 1; // base表示这位数的第一个数是多少,初始时是1位数，base = 1

// 第一步：确定n属于几位数，比如4位数，4位数中可能是1000~9999
// 当前n大于i位的所有数
while (n > i * s) {
n -= i * s;
i ++;
s *= 10;
base *= 10; // 位数 + 1，base 乘10
}

// 第二步：确定是几位数的第几个数，可以确定具体是哪个数字中的某一位，比如1234这个数中的某一位
// n / i 上取整: 所求的第n位属于第几个i位数
int number = base + (n + i - 1) / i - 1;

//第三步：属于那个数的第几位
// 余数， n % i
int r = n % i ? n % i : i;

// 求number的第r位数字是多少
for (int j = 0; j < i - r; j ++) number /= 10;

return number % 10;

}
};



ShizhengLee
8个月前
class Solution {
public:
int numberOf1Between1AndN_Solution(int n) {
vector<int> a;
while(n) a.push_back( n % 10), n/= 10;
int res =0;
for(int i = a.size()-1; i>=0; i--){
int d = a[i];
int left =0, right =0, power =1;
for(int j = a.size()-1; j>i ;j--) left = left*10 +a[j];
for(int j= i-1; j>=0; j--){
right = right * 10 + a[j];
power *= 10;
}

if(d ==0) res += left * power;
else if(d ==1) res +=   left * power + right +1;
else  res += (left +1) *power;
}
return res;

}
};



ShizhengLee
8个月前
class Solution {
public:

int maxSubArray(vector<int>& nums) {
int res = INT_MIN, s = 0;
for (auto x : nums) {
// 如果以前一个数结尾的子数组和的最大值<0,
// 则当前数结尾的子数组和的最大值直接为x

// 否则的话，以当前数结尾的子数组的最大值就等于
// s(以前一个数结尾的最大值)  + x(当前数)
if (s < 0) s = 0;
s += x;

res = max(res, s);
}
return res;
}
};



ShizhengLee
8个月前
class Solution {
public:
priority_queue<int> max_heap;
priority_queue<int, vector<int>, greater<int>> min_heap;

void insert(int num){
max_heap.push(num);
if (min_heap.size() && max_heap.top() > min_heap.top()) {
auto minv = min_heap.top(), maxv = max_heap.top();
max_heap.pop(), min_heap.pop();
max_heap.push(minv), min_heap.push(maxv);
}

if (max_heap.size() > min_heap.size() + 1) {
min_heap.push(max_heap.top());
max_heap.pop();
}
}

double getMedian(){
int num = max_heap.size() + min_heap.size();
if (num & 1)  return max_heap.top();
else return (min_heap.top() + max_heap.top()) / 2.0;

}
};



ShizhengLee
8个月前
class Solution {
public:
vector<int> getLeastNumbers_Solution(vector<int> input, int k) {
priority_queue<int> heap;
for (auto x : input) {
heap.push(x);
if (heap.size() > k) heap.pop();
}

vector<int> res;
while(heap.size()) {
res.push_back(heap.top());
heap.pop();
}

reverse(res.begin(), res.end());
return res;
}
};