快速排序
原理：
- 从数组中随机指定一个数据作为基准（简单起见，通常将下标为0的数据作为基准）
- 数组中剩下的每个数与基准数据进行比较
- 比基准数据小的放到基准数据左边，比基准数据大的放到基准数据右边
- 遍历完一遍以后，数组会被分割为两部分：左边部分的数据都小于基准数据，右边部分的数据都大于基准数据
- 然后将这两部分看成两个数组，重复步骤2和3，直到每个数组中的元素个数为1（即不能再次分割）
递归方法
C++ 实现
class Solution {
public:
/**
* 将给定数组排序
* @param arr int整型vector 待排序的数组
* @return int整型vector
*/
int partition(vector<int>& vec, int left, int right){
int pivot = vec[left];
while(left<right){
while(left<right && vec[right]>=pivot){
right--;
}
vec[left] = vec[right];
while(left<right && vec[left]<=pivot){
left++;
}
vec[right] = vec[left];
}
vec[left] = pivot;
return left;
}
void QuickSort(vector<int>& vec, int left, int right){
if(left<right){
int pivot = partition(vec, left, right);
QuickSort(vec, left, pivot-1);
QuickSort(vec, pivot+1, right);
}
}
vector<int> MySort(vector<int>& arr) {
QuickSort(arr, 0, arr.size()-1);
return arr;
}
};
Python3 实现
class Solution:
def MySort(self , arr):
""" 调用方法 """
self.quickSort(arr, 0, len(arr)-1)
return arr
def partition(self, arr, left, right):
"""分割数组的第1种实现"""
pivot = arr[left]
while left<right:
while left<right and arr[right]>=pivot: right-=1
arr[left] = arr[right]
while left<right and arr[left]<=pivot: left+=1
arr[right] = arr[left]
arr[left] = pivot
return left
def partition2(self, arr, left, right):
"""分割数组的第2种实现"""
pivot = left
index = pivot+1
i = index
while i<=right:
if arr[i]<arr[pivot]:
arr[index], arr[i] = arr[i], arr[index]
index += 1
i += 1
arr[pivot], arr[index-1] = arr[index-1], arr[pivot]
return index -1
def quickSort(self, arr, left, right):
""" 递归方法进行排序 """
if left<right:
pivot = self.partition(arr, left, right)
self.quickSort(arr, left, pivot-1)
self.quickSort(arr, pivot+1, right)
Java实现
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 将给定数组排序
* @param arr int整型一维数组 待排序的数组
* @return int整型一维数组
*/
public int[] MySort (int[] arr) {
// write code here
qSort(arr, 0, arr.length-1);
return arr;
}
public void qSort(int[] arr, int start, int end){
if(start>=end) return ;
int low=start,high=end;
int pviot = arr[low];
while(low<high){
while(low<high&&arr[high]>=pviot) high--;
while(low<high&&arr[low]<=pviot) low++;
int tmp = arr[low];
arr[low] = arr[high];
arr[high] = tmp;
}
int tmp = arr[low];
arr[low] = arr[start];
arr[start] = tmp;
qSort(arr, start, low-1);
qSort(arr, low+1, end);
}
}
有效括号
C++实现
class Solution {
public:
bool isValid(string s) {
int n = s.size();
if(n%2==1){
return false;
}
stack<char> c_stack;
unordered_map<char, char> c_map = {{'(', ')'}, {'{', '}'}, {'[', ']'}};
for(char c:s){
if(!c_map.count(c)){
if(c_stack.empty() || c_map[c_stack.top()]!=c){
return false;
}
c_stack.pop();
}else{
c_stack.push(c);
}
}
return c_stack.empty();
}
};
Java实现
import java.util.*;
class Solution {
public boolean isValid(String s) {
int n = s.length();
if(n%2==1) return false;
Deque<Character> stack= new LinkedList<Character>();
HashMap<Character, Character> map = new HashMap<Character, Character>();
map.put('(',')');
map.put('[',']');
map.put('{','}');
for(int i=0;i<n;i++){
char c = s.charAt(i);
if(!map.containsKey(c)){
if(stack.isEmpty()||map.get(stack.peek())!=c){
return false;
}
stack.pop();
}else{
stack.push(c);
}
}
return stack.isEmpty();
}
}
有序数组去重
给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
例如：
给定数组 nums = [1,1,2],
函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。
解题思路
采用双指针方式处理。
- 初始指针 i, j 位置为 0
- 指针 j 先向右移动
- 比较指针 i,j 元素是否相同，若指针i，j元素相同则指针 j 继续向右移动；反之将指针 j 元素复制到指针 i + 1 处元素
- 当指针 j 移动到数组末尾时则停止
C++实现
public static int solution (int[] nums) {
int i = 0, j = 0;
while (true) {
// 指针 j 向右移动
j++;
// 指针 j 移动到数组末尾则退出，说明数组元素都判断了去重
if (j >= nums.length) {
break;
}
if (nums[j] == nums[i]) {
// 指针 i, j 元素相同，说明重复元素；
// 指针 j 继续向右移动
continue;
} else {
// 指针 i, j 元素不相同；则将指针 j 元素复制到 指针 i 后一位，这样就保证指针 i 后元素不重复
nums[i + 1] = nums[j];
// 指针 i 向右移动，继续处理
i++;
}
}
return i + 1;
}
评论区