[LeetCode C++实现]45. 跳跃游戏 II

[LeetCode C++实现]45. 跳跃游戏 II

date:2021-07-12 23:30

url:LeetCode45

class Solution {

public:

int jump(vector<int>& nums) {

int size = nums.size();

int right = 0,step = 0,end = 0;

for(int i = 0;i < size - 1;i++)

{

if(i <= right)

{

right = max(right,i + nums[i]);

if(i == end)

{

end =......

[LeetCode C++实现]55.跳跃游戏

class Solution {

public:

bool canJump(vector<int>& nums) {

int size = nums.size();

int right = 0;

for(int i = 0;i < size;i++)

{

if(i <= right)

{

right = max(right,i + nums[i]);

if(right >= size - 1)

return true;

}else

return false;

}

return false;

}

};

这道题的思路是贪心,从前往后计算能够到达的最远距......

[LeetCode C++实现]179. Largest Number

讨论区看到一个解法,非常的清晰,缺点是需要构造一个vector,因此空间复杂度较高。

class Solution {

public:

string largestNumber(vector<int>& nums) {

vector<string> strs;

for(auto num:nums)

strs.push_back(to_string(num));

sort(strs.begin(),strs.end(),[](const string& s1,const string& s2){return s1 + s2 > s2 +......

程序员面试金典-面试题 03.03. 堆盘子

堆盘子。设想有一堆盘子,堆太高可能会倒下来。因此,在现实生活中,盘子堆到一定高度时,我们就会另外堆一堆盘子。请实现数据结构SetOfStacks,模拟这种行为。SetOfStacks应该由多个栈组成,并且在前一个栈填满时新建一个栈。此外,SetOfStacks.push()和SetOfStacks.pop()应该与普通栈的操作方法相同(也就是说,pop()返回的值,应该跟只有一个栈时的情况一样)。 进阶:实现一个popAt(int index)方法,根据指定的子栈,执行pop操作。

当某个栈为空时,应当删除该栈。当栈中没有元素或不存在该栈时,pop,popAt 应返回 -1.

示例1......

程序员面试金典-面试题 08.05. 递归

递归乘法。 写一个递归函数,不使用 * 运算符, 实现两个正整数的相乘。可以使用加号、减号、位移,但要吝啬一些。

由于题目要求使用递归函数实现,方法一:

class Solution {

public:

int multiply(int A, int B) {

if(A == 0 || B == 0)

return 0;

if(A < B)

return B + multiply(A-1,B);

else

return A + multiply(A, B-1);

}

};

之所以要判断A与B的大小,是因为使用小的作为循环次数,可以提高效率。

方法二:分治法

clas......

[LeetCode C++实现]41. First Missing Positive

class Solution {

public:

int firstMissingPositive(vector<int>& nums) {

int n = nums.size();

for(int i = 0;i < n;i++)

{

if(nums[i] <= 0)

nums[i] = n + 1;

}

for (int i = 0; i < n; ++i) {

int num = abs(nums[i]);

if (num <= n) {

nums[num - 1] = -abs(nums[num - 1]);

}

}

for(int i......

[LeetCode C++实现]29. Divide Two Integers

class Solution {

public:

int divide(int dividend, int divisor) {

if(dividend == INT_MIN && divisor == -1) return INT_MAX;

long long A = llabs(dividend),B = llabs(divisor),ans = 0;

while(A >= B)

{

long long base = B,m = 1;

while(base << 1 <= A)

{

base <<= 1;

m <<= 1;

......

[LeetCode C++实现]912. Sort an Array

冒泡排序

class Solution {

public:

vector<int> sortArray(vector<int>& nums) {

for(int i = nums.size()-1;i > 0;i--)

{

for(int j = 0;j < i;j++)

if(nums[j] > nums[j+1])

swap(nums[j],nums[j+1]);

}

return nums;

}

};

执行结果:

Time Limit Exceeded

Details

Last executed input

[5864,-1......

[LeetCode C++实现]1114. Print in Order

#include <semaphore.h>

class Foo {

protected:

sem_t firstJobDone;

sem_t secondJobDone;

public:

Foo() {

sem_init(&firstJobDone, 0, 0);

sem_init(&secondJobDone, 0, 0);

}

void first(function<void()> printFirst) {

// printFirst() outputs "first". Do not change or remove th......

[剑指offer C++实现]剑指 Offer 43. 1~n 整数中 1 出现的次数

输入一个整数 n ,求1~n这n个整数的十进制表示中1出现的次数。

例如,输入12,1~12这些整数中包含1 的数字有1、10、11和12,1一共出现了5次。

class Solution {

public:

int countDigitOne(int n) {

int res = 0;

for(int i = 1;i <= n;i++)

{

res += helper(i);

}

return res;

}

private:

int helper(int n)

{

int cnt = 0;

while(n)

{

if(n%10 == 1)

cnt++;

n /= 10;

}

r......