[LeetCode C++实现]1502. Can Make Arithmetic Progression From Sequence

方法一:排序

class Solution {

public:

bool canMakeArithmeticProgression(vector<int>& arr) {

sort(arr.begin(),arr.end());

int diff = arr[1] - arr[0];

for(int i = 1;i < arr.size();i++)

{

if(arr[i] - arr[i-1] != diff)

return false;

}

return true;

}

};

运行效率:

Runtime: 4 ms, faster than 65......

[LeetCode C++实现]151. Reverse Words in a String

class Solution {

public:

string reverseWords(string s) {

int size = s.size();

int i = 0,j = 0;

while(i < size)

{

//skip spaces

while(i < size && s[i] == ' ')

i++;

if(i < size && j > 0)

s[j++] = ' ';

int start = j;

while(i < size && s[i] != ' ')

s[j++] = s[i++];......

[LeetCode C++实现]1551. Minimum Operations to Make Array Equal

比较直观好理解的解法:

class Solution {

public:

int minOperations(int n) {

int res = 0;

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

{

int num = 2*(i-1) + 1;

if(num > n)

res += num -n;

}

return res;

}

};

运行效率:

Runtime: 0 ms, faster than 100.00% of C++ online submissions for Minimum Operations to Make Array Equal......

[LeetCode C++实现]319. Bulb Switcher

最直观最容易想的方法,暴力破解方法:

class Solution {

public:

int bulbSwitch(int n) {

vector<int> state(n,0);

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

{

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

{

state[j] ^= 1;

}

}

return count(state.begin(),state.end(),1);

}

};

执行结果:

Time Limit Exceeded

Details

Last executed input

10000......

[LeetCode C++实现]1773. Count Items Matching a Rule

最直观的解法:

class Solution {

public:

int countMatches(vector<vector<string>>& items, string ruleKey, string ruleValue) {

int index = (ruleKey == "type")? 0 : (ruleKey == "color") ? 1: 2;

int res = 0;

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

{

if(items[i][index] == ruleValue)

res += 1;

}......

[LeetCode C++实现]1381. Design a Stack With Increment Operation

先使用最直观的解法:

class CustomStack {

public:

CustomStack(int maxSize) {

m_maxsize = maxSize;

}

void push(int x) {

if(m_elem.size() >= m_maxsize)

return;

m_elem.push(x);

}

int pop() {

if(m_elem.empty())

return -1;

int x = m_elem.top();

m_elem.pop();

return x;

}

void increment(int k, int val) {

sta......

[LeetCode C++实现]1305. All Elements in Two Binary Search Trees

首先用最直观的解法,先将两个binary search tree的元素插入到vector,然后排序。

/**

* 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) {}

......

[LeetCode C++实现]1437. Check If All 1's Are at Least Length K Places Away

先用最直白的解法AC:

class Solution {

public:

bool kLengthApart(vector<int>& nums, int k) {

int n = nums.size();

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

{

if(nums[i] == 1)

{

int cnt = k;

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

{

if(nums[j] == 1)

{

if(cnt > 0)

return false;

break;

}

if(nums[j] ......

[LeetCode C++实现]1769. Minimum Number of Operations to Move All Balls to Each Box

常规暴力破解方法,时间复杂度O(n2):

class Solution {

public:

vector<int> minOperations(string boxes) {

int n = boxes.size();

vector<int> res;

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

{

int distance = 0;

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

{

if(i == j) continue;

if('1' == boxes[j])

distance += abs(i-j);

}

res.push_back(d......

[LeetCode C++实现]494. Target Sum

递归解法

递归解法,开始解法存在超时,优化方法是将vector的长度放在类成员中或通过参数传递,如果在helper中每次求nums.size()会导致运行超时。

class Solution {

private:

//目标和个数

int count;

//vector大小,减少递归函数里查询O(n)复杂度

int size;

public:

int findTargetSumWays(vector<int>& nums, int S) {

size = nums.size();

helper(nums,0,0,S);

return count;

}

private:......