算法设计模板总结

链表反转

链表反转, 假设链表为a->b->…->n, 需要用反转a->b之前需要记录b的next指针,因此需要三个指针即可.

反转指针的写法有两种,递归法和循环法.

递归写法

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        return reverseList(nullptr, head);
    }
    // tail是head的前一个节点,反转head
    // 最后返回反转后的头指针
    ListNode* reverseList(ListNode* tail, ListNode* head){
        if(!head) return tail;
        ListNode* next = head->next;	// 记录head的下一个节点
        head->next = tail;				// head 指向tail
        tail = head;					// tail 作为head继续递归
        return reverseList(tail, next);
    }
};

循环写法

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head){
        if(!head) return head;
        ListNode* pre = nullptr;        // 初始时head的前一个节点为空
        ListNode* mid = head;
        while(mid&&mid->next){
            ListNode* tail = mid->next;     // 记录mid的下一个节点
            mid->next = pre;
            pre = mid;
            mid = tail;
        }
        mid->next = pre;				// pre始终是mid的前一个节点,循环结束后mid指向pre
        return mid;
    }
};

回文链表判断

• 第一步,找到链表的中间节点
• 第二步,反转起始节点到中间节点的这部分链表
• 从中间节点向两边扩散,检查是否为回文链表

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution
{
public:
    bool isPalindrome(ListNode *head)
    {
        if (!head || !head->next)
            return true;
        ListNode *tail = head->next;
        ListNode *mid = head;
        bool odd = false;		// odd 判断链表长度是否为奇数
        while (tail && tail->next)
        {
            tail = tail->next;
            mid = mid->next;
            if (tail && tail->next)
            {
                tail = tail->next;
                odd = false;		// tail一次能走两步,是偶数长度的链表
            }
            else
            {
                odd = true;			// 链表这一次走一步就到了尾部,是奇数长度的链表
                break;
            }
        }
        ListNode *right = mid->next;	// 记录mid中间节点的下一个节点
        ListNode *left = reverse(head, mid);

        if (odd)
            left = left->next;			// 如果是奇数链表,左边链表左边走一位
		
        // 中间到两边开始判断,是否为回文链表
        while (right && left)
        {

            if (right->val != left->val)
                return false;

            right = right->next;
            left = left->next;
            if (!left && !right)
                break;
        }
        return true;
    }

    // 反转head到tail部分的链表
    ListNode *reverse(ListNode *head, ListNode *till)
    {
        if (!head || !head->next)
            return head;
        ListNode *pre = nullptr;
        ListNode *mid = head;
        while (mid != till && mid->next)
        {
            ListNode *tail = mid->next;
            mid->next = pre;
            pre = mid;
            mid = tail;
        }
        mid->next = pre;
        return mid;
    }
};

快速排序(分治法)

int partition(vector<int> nums, int left, int right){
	int base = nums[left];
	while(left<right){
		while(left<right&&nums[right]>base)
			right--;
		nums[left] = nums[right];
		while(left<right && nums[left]<=base)
			++left;
		nums[right] = nums[left];
	}
	nums[left] = base;
	return left;
}

void quickSort(vector<int> nums,const int left, const int right){
	if(left<right){
		int index = partition(nums, left, right);
		quickSort(nums, left, index);
		quickSort(nums, index+1, right);
	}
}

归并排序(分治法)

typedef long long LL;

LL mergeSort(VI& nums, const int low, const int high) {
	LL ans = 0;
	if (high <= low)
		return 0;
	else if (high - low == 1) {
		if (nums[low] > nums[high]) {
			swap(nums[low], nums[high]);
			ans++;
		}
		return ans;
	}
	int mid = low + (high - low) / 2;
	LL left = mergeSort(nums, low, mid);
	LL right = mergeSort(nums, mid + 1, high);
	ans = left + right;
	
	VI leftNums(nums.begin() + low, nums.begin() + mid + 1);
	VI rightNums(nums.begin() + mid + 1, nums.begin() + high + 1);
	int i = 0, j = 0, index = low;
	while (i < leftNums.size() && j < rightNums.size()) {
		if (leftNums[i] <= rightNums[j])
			nums[index++] = leftNums[i++];
		else {
			nums[index++] = rightNums[j++];
			ans += leftNums.size() - i;
		}
	}
	while (i < leftNums.size())
		nums[index++] = leftNums[i++];
	while (j < rightNums.size())
		nums[index++] = rightNums[j++];
	return ans;
}

数组中逆序对个数(分治法)

int64_t reverseNum(vector<int> nums, int low, int high){
	uint64_t ans = 0;
	if(low>=high)
		return ans;
	else if(high - low == 1){
		if(nums[low]>nums[high]){
			swap(nums[low], nums[high]);
			++ans;
		}
		return ans;
	}
	int mid = low + (high-low)/2;
	int64_t left = reverseNum(nums, low, mid);
	int64_t right = reverseNum(nums, mid+1, high);
	ans += left + right;
	vector<int> leftNums(nums.begin()+low, nums.begin()+mid+1);
	vector<int> rightNums(nums.begin()+mid+1, nums.begin()+high+1);
	int i = 0, j = 0, index = low;
	
	while( i<leftNums.size() && j< rightNums.size() ){
		if(leftNums[i]<=rightNums[j])
			nums[index++] = leftNums[i++];
		else{
			nums[index++] = rightNums[j++];
			ans += leftNums.size()-i;	// 
		}
	}
	while(i<leftNums.size())
		nums[index++] = leftNums[i++];
	while(j<rightNums.size())
		nums[index++] = rightNums[j++];
	return ans;
}

平面最近点对(分治法)

double minDistance(vector<Point>& points, CI low, CI high) {
	if (low >= high)
		return 0;
	else if (low == high - 1) {
		double dis = distance(points[low], points[high]);
		if (points[low].y > points[high].y)
			swap(points[low], points[high]);
		return dis;
	}

	int mid = low + (high - low) / 2;
	int middle = points[mid].x;
	double left = minDistance(points, low, mid);
	double right = minDistance(points, mid, high);
	double ans = min(left, right);
	auto f = [](const Point& p1, const Point& p2)->bool {return p1.y < p2.y; };
	sort(points.begin() + low, points.begin() + high + 1, f);
	vector<Point> tmp;
	for (int i = low; i < high; ++i) {
		if (abs(points[i].x - middle) <= ans)
			tmp.emplace_back(points[i]);
	}

	for (int i = 0; i < tmp.size(); ++i) {
		for (int j = i + 1; j < min(static_cast<int>(tmp.size()), i + 12); ++j)
			ans = min(ans, distance(tmp[i], tmp[j]));
	}
	return ans;
}

并查集

class UnionFind{
public:
    vector<int> sz; // 表示每个集合的大小
    vector<int> parent; // 表示每个顶点最终的父节点
                        // 初始化每个顶点父节点是其自身
    int cnt;
    UnionFind(const int n){
        sz.assign(n, 1);
        cnt = n;
        parent.resize(n, 0);
        for(int i = 0; i < n; ++i)
            parent[i] = i;
    }

    // 找某个节点的父亲节点,注意返回值不能是 bool类型，必须是整数类型
    int find(const int x){
        if(x!=parent[x])
            parent[x] = find(parent[x]);
        return parent[x];
    }

    // 合并两个节点
    bool merge(const int x, const int y){
        int px = find(x);
        int py = find(y);
        if(px==py)  return false;
        if(sz[px]>=sz[py]){
            sz[px]+=sz[py];
            parent[py] = px;
        }
        else{
            sz[py]+=sz[px];
            parent[px] = py;
        }
        --cnt;
        return true;
    }
    int getCnt(){return cnt;}
};

prime 算法

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<double> VD;
typedef vector<VD> VVD;

// 边的定义
struct Edge {
	int from, to;
	double dis;
	Edge(CI f, CI t, CD d) :from(f), to(t), dis(d) {};
	bool operator < (const Edge& e)const { return this->dis > e.dis; };
};

// 图用邻接矩阵存储的Prime算法
double MST(const VVD& graph) {
	double ans = 0;
	VI visit(graph.size(), 0);
	priority_queue<Edge> myQueue;
	for (int i = 0; i < graph.size(); ++i) {
		myQueue.emplace(0, i, graph[0][i]);
	}
	VD dis(graph[0]);
	while (!myQueue.empty()) {
		Edge e = myQueue.top();
		myQueue.pop();
		if (visit[e.to] == 1)
			continue;
		visit[e.to] = 1;
		ans += e.dis;
		dis[e.to] = e.dis;
		for (int i = 0; i < graph.size(); ++i)
			if (visit[i] == 0 && graph[e.to][i] < dis[i])
				myQueue.emplace(e.to, i, graph[e.to][i]);
	}
	return ans;
}

kruskal算法(贪心法)

// 边的定义
struct Edge {
	int from, to;
	double dis;
	Edge(CI f, CI t, CD d) :from(f), to(t), dis(d) {};
	bool operator < (const Edge& e)const { return this->dis < e.dis; };
};

// kruskal算法,需要用到并查集
double MST(const vector<Edge> edgeVec,const int vertex) {
	sort(edgeVec.begin(), edgeVec.end());

    QuickUnion qu(vertex);
    double ans = 0;
    int edgCnt = 0;
    for(auto&e :edgeVec){
        if(qu.merge(e.from, e.to)){
            ans += e.dis;
            edgCnt++;
            if(edgCnt==vertex-1)
                break;
        }
    }
    return ans;
}

dijkstra算法(贪心法)

typedef vector<int> VI;
typedef vector<VI> VVI;

// 边的定义
struct Edge {
	int from, to;
	int dis;
	Edge(CI f, CI t, CD d) :from(f), to(t), dis(d) {};
	bool operator < (const Edge& e)const { return this->dis > e.dis; };
};

// 图用邻接矩阵存储的, 优先级队列实现,,计算start到target的最近距离
int dijkstra(const VVI& graph, const int start, const int target) {
	VI dis(graph.size(), INT_MAX);
	dis[start] = 0;
	VI visit(graph.size(), 0);
	priority_queue<Edge> myQueue;
	myQueue.emplace(start, start, 0);
	while(!myQueue.empty()){
		Edge e = myQueue.top();
		myQueue.pop();
		if(visit[e.to]==1)
			continue;
		visit[e.to] = 1;
		dis[e.to]= e.dis;
		for(int i = 0;i<graph.size();++i){
			if( visit[i]==0 && dis[i]- graph[e.to][i]> dis[e.to])
				myQueue.emplace(e.to, i, dis[e.to]+ graph[e.to][i])
		}
	}
	return dis[target];
}

spfa(动态规划)

typedef vector<int> VI;
typedef vector<VI> VVI;

// 图用邻接矩阵存储, 队列实现的spfa算法,计算start到target的最近距离
int spfa(const VVI& graph, const int start, const int target) {
	vector<int> dis(graph.size(), INT_MAX);
	dis[start] = 0;
	queue<int> myQueue;
	VI enqueue(graph.size(), 0);
	myQueue.push(start);
	enqueue[start] = 1;
	while(!myQueue.empty()){
		int topNode = myQueue.front();
		myQueue.pop();
		enqueue[topNode] = 0;
		for(int i = 0;i<graph.size();++i){
			if(dis[i]- graph[topNode][i]> dis[topNode]){
				dis[i] = dis[topNode]+graph[topNode][i];
				if(enqueue[i]==0){
					myQueue.emplace(i);
					enqueue[i] = 1;
				}
			}
		}
	}
	return dis[target];
}