算法

Scroll Down

快速排序

原理:

  1. 从数组中随机指定一个数据作为基准(简单起见,通常将下标为0的数据作为基准)
  2. 数组中剩下的每个数与基准数据进行比较
  3. 比基准数据小的放到基准数据左边,比基准数据大的放到基准数据右边
  4. 遍历完一遍以后,数组会被分割为两部分:左边部分的数据都小于基准数据,右边部分的数据都大于基准数据
  5. 然后将这两部分看成两个数组,重复步骤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();
    }
}