[公开]西南四环路大修及环境提升-道路照明设施消隐改造工程（辅路）中标公告

215/MyAlgorithm

/LeetCode/0189 Rotate Array.cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
void rotate(vector<int>& nums, int k) {
int n = nums.size();
k = k % n;
reverse(nums.begin(), nums.end());
reverse(nums.begin(), nums.begin() + k);
reverse(nums.begin() + k, nums.end());
}
};

// 滑动窗口法
class Solution1 {
public:
void rotate(vector<int>& nums, int k) {
int n = nums.size();
k = k % n;
vector<int> tmp(nums.begin() + n - k, nums.end());
tmp.insert(tmp.end(), nums.begin(), nums.begin() + n - k);
nums = tmp;
}
};

int main() {
vector<int> nums = {1, 2, 3, 4, 5, 6, 7};
int k = 3;
Solution1 s1;
s1.rotate(nums, k);
for (auto num : nums) {
cout << num << " ";
}
return 0;
}

/LeetCode/0459 Repeated Substring Pattern.cpp
#include <iostream>
#include <string>
#include <vector>
using namespace std;

class Solution {
public:
string longestPalindrome(string s) {
int n = s.size();
vector<vector<int>> dp(n, vector<int>(n, 0));
int left = 0, right = 0;
for (int i = n - 1; i >= 0; i--) {
for (int j = i; j < n; j++) {
if (s[i] == s[j] && (j - i <= 1 || dp[i + 1][j - 1])) {
dp[i][j] = 1;
if (j - i + 1 > right - left + 1) {
left = i;
right = j;
}
}
}
}
return s.substr(left, right - left + 1);
}
};

int main() {
string s = "babad";
Solution s1;
cout << s1.longestPalindrome(s) << endl;
return 0;
}

/LeetCode/0083 Remove Duplicates from Sorted List.cpp
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
int n = nums.size();
vector<int> res(n, -1);
int top = 0;
queue<int> q;
for (int i = 0; i < n; i++) {
while (top > 0 && nums[i] > nums[q.front()]) {
res[q.front()] = nums[i];
q.pop();
top--;
}
q.push(i);
top++;
}
for (int i = 0; i < n; i++) {
while (top > 0 && nums[i] > nums[q.front()]) {
res[q.front()] = nums[i];
q.pop();
top--;
}
}
return res;
}
};

int main() {
vector<int> nums = {1, 2, 1};
Solution s1;
vector<int> res = s1.nextGreaterElements(nums);
for (auto num : res) {
cout << num << " ";
}
return 0;
}

/LeetCode/0147 Insertion Sort List.cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <assert.h>
using namespace std;

class Solution {
public:
int reversePairs(vector<int>& nums) {
int res = 0;
for (int i = 0; i < nums.size(); i++) {
for (int j = i + 1; j < nums.size(); j++) {
if (nums[i] > nums[j] * 2) {
res++;
}
}
}
return res;
}
};

int main() {
vector<int> nums = {1, 3, 2, 3, 1};
Solution s1;
cout << s1.reversePairs(nums) << endl;
return 0;
}

/LeetCode/0448 Find All Numbers Disappeared in an Array.cpp
#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
vector<int> findDisappearedNumbers(vector<int>& nums) {
int n = nums.size();
vector<int> ans;
for (int i = 0; i < n; i++) {
while (nums[i] != i + 1) {
if (nums[nums[i] - 1] == nums[i]) break;
swap(nums[i], nums[nums[i] - 1]);
}
}
for (int i = 0; i < n; i++) {
if (nums[i] != i + 1) {
ans.push_back(i + 1);
}
}
return ans;
}
};

int main() {
vector<int> nums = {4,3,2,7,8,2,3,1};
Solution s1;
vector<int> ans = s1.findDisappearedNumbers(nums);
for (auto num : ans) {
cout << num << " ";
}
return 0;
}

/LeetCode/086 Partition List.cpp
#include <iostream>
#include <vector>
#include