LeetCode Algorithm 0031 - 0035
文章目录
- LeetCode Algorithm 0031 - 0035
0031 - Next Permutation (Medium)
Problem Link: https://leetcode.com/problems/next-permutation/description/
Description
Implement next permutation , which rearranges numbers into the lexicographically next greater permutation of numbers.
If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).
The replacement must be in-place and use only constant extra memory.
Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1
Solution C++
#pragma once
#include "pch.h"
// Problem: https://leetcode.com/problems/next-permutation/description/
namespace P31NextPermutation
{
class Solution
{
public:
void nextPermutation(vector<int>& nums)
{
// 看了好久题目，才看懂是要干什么。
// 不存在
if (nums.empty() || nums.size() == 1)
{
return;
}
int turningIndex;
// 寻找转折点
for (turningIndex = nums.size() - 2; turningIndex >= 0; turningIndex--)
{
if (nums[turningIndex + 1] > nums[turningIndex])
{
break;
}
}
if (turningIndex >= 0)
{
int swapIndex;
// 寻找交换点
for (swapIndex = nums.size() - 1; swapIndex >= 0; swapIndex--)
{
if (nums[swapIndex] > nums[turningIndex])
{
break;
}
}
SwapNumber(nums, turningIndex, swapIndex);
}
// 翻转数组
int startIndex = turningIndex + 1;
int endIndex = nums.size() - 1;
while (startIndex < endIndex)
{
SwapNumber(nums, startIndex, endIndex);
startIndex++;
endIndex--;
}
}
private:
// 交换两个数字
inline void SwapNumber(vector<int>& nums, int leftIndex, int rightIndex)
{
int tmp = nums[leftIndex];
nums[leftIndex] = nums[rightIndex];
nums[rightIndex] = tmp;
}
};
}
0032 - Longest Valid Parentheses (Hard)
Problem Link: https://leetcode.com/problems/longest-valid-parentheses/description/
Description
Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.
Example 1:
Input: "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()"
Example 2:
Input: ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()"
Solution C++
#pragma once
#include "pch.h"
// Problem: https://leetcode.com/problems/longest-valid-parentheses/description/
namespace P32LongestValidParentheses
{
class Solution
{
public:
static const char k_LeftBracket = '(';
static const char k_RightBracket = ')';
public:
int longestValidParentheses(string s)
{
if (s.empty())
{
return 0;
}
int maxLen = 0;
stack<int> chStack;
chStack.push(-1);
for (int i = 0; i < s.size(); i++)
{
if (s[i] == k_LeftBracket)
{
chStack.push(i);
}
else if (s[i] == k_RightBracket)
{
chStack.pop();
if (chStack.size() == 0)
{
chStack.push(i);
}
else
{
maxLen = max(maxLen, i - chStack.top());
}
}
}
return maxLen;
}
};
}
0033 - Search in Rotated Sorted Array (Medium)
Problem Link: https://leetcode.com/problems/search-in-rotated-sorted-array/description/
Description
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.
Your algorithm’s runtime complexity must be in the order of O(log n).
Example 1:
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Example 2:
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1
Solution C++
#pragma once
#include "pch.h"
// Problem: https://leetcode.com/problems/search-in-rotated-sorted-array/description/
namespace P33SearchInRotatedSortedArray
{
class Solution
{
public:
int search(vector<int>& nums, int target)
{
if (nums.empty())
{
return -1;
}
int minIndex = 0;
int maxIndex = nums.size() - 1;
while (minIndex < maxIndex)
{
int midIndex = (minIndex + maxIndex) / 2;
if (nums[0] > target)
{
if (nums[0] > nums[midIndex])
{
if (nums[midIndex] < target)
{
minIndex = midIndex + 1;
}
else
{
maxIndex = midIndex;
}
}
else
{
minIndex = midIndex + 1;
}
}
else
{
if (nums[minIndex] > nums[midIndex])
{
maxIndex = midIndex;
}
else
{
if (nums[midIndex] < target)
{
minIndex = midIndex + 1;
}
else
{
maxIndex = midIndex;
}
}
}
}
if (minIndex == maxIndex && nums[minIndex] == target)
{
return minIndex;
}
else
{
return -1;
}
}
};
}
0034 - Find First and Last Position of Element in Sorted Array (Medium)
Problem Link: https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/
Description
Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.
Your algorithm’s runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1].
Example 1:
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
Example 2:
Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]
Solution C++
#pragma once
#include "pch.h"
// Problem: https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/description/
namespace P34FindFirstAndLastPositionOfElementInSortedArray
{
class Solution
{
public:
vector<int> searchRange(vector<int>& nums, int target)
{
if (nums.empty())
{
return { -1, -1 };
}
if (nums.size() == 1)
{
return nums[0] == target ? vector<int>({ 0, 0 }) : vector<int>({ -1, -1 });
}
int startIndex = 0;
int endIndex = nums.size() - 1;
while (startIndex < endIndex)
{
int midIndex = (startIndex + endIndex) / 2;
if (nums[midIndex] < target)
{
startIndex = midIndex + 1;
}
else
{
endIndex = midIndex;
}
}
if (nums[startIndex] != target)
{
return { -1, -1 };
}
int size = nums.size();
while (startIndex >= 0 && nums[startIndex] == target)
{
startIndex--;
}
while (endIndex < size && nums[endIndex] == target)
{
endIndex++;
}
return { startIndex + 1, endIndex - 1 };
}
};
}
0035 - Search Insert Position (Easy)
Problem Link: https://leetcode.com/problems/search-insert-position/description/
Description
Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You may assume no duplicates in the array.
Example 1:
Input: [1,3,5,6], 5
Output: 2
Example 2:
Input: [1,3,5,6], 2
Output: 1
Example 3:
Input: [1,3,5,6], 7
Output: 4
Example 4:
Input: [1,3,5,6], 0
Output: 0
Solution C++
#pragma once
#include "pch.h"
// Problem: https://leetcode.com/problems/search-insert-position/description/
namespace P35SearchInsertPosition
{
class Solution
{
public:
int searchInsert(vector<int>& nums, int target)
{
if (nums.empty())
{
return 0;
}
int startIndex = 0;
int endIndex = nums.size() - 1;
while (startIndex < endIndex)
{
int midIndex = (startIndex + endIndex) / 2;
if (nums[midIndex] < target)
{
startIndex = midIndex + 1;
}
else
{
endIndex = midIndex;
}
}
return nums[startIndex] >= target ? startIndex : startIndex + 1;
}
};
}