发表更新algorithm / ListNode / Search1 分钟读完 (大约183个字)

Delete-Last-Nth-Node

链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/

题目：
Given the head of a linked list, remove the nth node from the end of the list and return its head.

remove_ex1

Example 1:

1
2
Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]

Example 2:

1
2
Input: head = [1], n = 1
Output: []

Example 3:

1
2
Input: head = [1,2], n = 1
Output: [1]

Constraints:

  • The number of nodes in the list is sz.
  • 1 <= sz <= 30
  • 0 <= Node.val <= 100
  • 1 <= n <= sz

解决了进阶问题： 一次循环解决问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        if(head->next == nullptr) return nullptr;
        ListNode* temp = head;
        ListNode* tail = temp->next;
        for(int i = 1; i < n && tail != nullptr; i++) tail = tail->next;
        if(tail == nullptr){
            return head->next;
        }
        else{
            while(tail->next != nullptr) {
                temp = temp->next;
                tail = tail->next;
            }
            temp->next = temp->next->next;
            return head;
        }
        
   }
};
发表更新Algorithm / KNN1 分钟读完 (大约200个字)

Get Mode and Multiplicy in Collection

project3-2

具体实现代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int getMode(int nums[], int n, int* maxCount){
    int i = 0;
    *maxCount = 1;
    int index = 0;
    while(i < n - 1){
        int tempCount = 1;
        int j;
        for(j = i; j < n - 1; j++){
            if(nums[j] == nums[j+1]){
                tempCount++;
            }else{
                break;
            }
        }
        if(*maxCount < tempCount){
            *maxCount = tempCount;
            index = j;
        }
        i = ++j;
    }
    return index;
}

测试数据生成函数如下:

1
2
3
4
5
6
7
8
9
int* randomCollection(int n, int max){
    srand(time(0));
    int* coins = new int[n];
    for(int i = 0; i < n; i++){
        coins[i] = rand() % max;
    }
    return coins;
}

测试样例展示函数如下:

1
2
3
4
5
6
7
void printCollection(int coins[], int n){
    cout << "[";
    for(int i = 0; i < n - 1; i++){
        cout << coins[i] << ",";
    }
    cout << coins[n-1] << "]" << endl;
}

测试主函数如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;

int main()
{
    int count = 300, max = 500, maxCount = 0;
    int* list = randomCollection(count, max);
    printCollection(list, count);    
    sort(list, list + count);
    printCollection(list, count); 
    cout << "the Mode is:" << list[getMode(list, count, &maxCount)] << ", the Multiplicity is:" << maxCount << endl; 
    return 0;
}

生成测试结果展示

1
2
3
4
5
$g++ -o main *.cpp
$main
[120,138,326,318,484,329,431,476,26,11,442,158,184,142,332,381,321,205,278,40,492,415,292,205,68,96,188,209,260,4,355,232,142,33,50,126,363,333,454,241,345,248,251,29,390,84,263,64,289,41,104,133,456,396,339,376,493,379,85,105,383,293,189,25,326,91,4,41,425,310,282,122,59,34,151,301,470,414,365,259,308,322,244,116,70,435,493,415,314,430,372,197,223,61,75,402,5,79,295,430,389,78,404,300,464,55,454,434,322,319,45,482,493,141,98,64,77,443,331,391,374,204,441,449,117,16,203,122,447,499,404,188,429,308,341,393,216,295,179,38,466,76,20,460,69,470,376,146,414,59,390,140,263,331,89,233,199,145,207,498,144,464,38,73,272,379,318,340,174,349,230,493,277,102,305,346,73,33,493,339,92,383,479,208,66,420,441,117,65,0,115,61,464,153,134,89,385,304,429,59,153,160,404,430,114,209,129,39,242,122,378,187,357,209,395,275,482,188,392,399,188,359,461,153,12,447,94,249,252,23,161,405,35,65,188,2,127,317,41,221,291,420,408,148,481,155,423,463,343,167,363,384,26,176,389,390,123,483,140,375,358,301,133,246,366,321,248,345,490,289,67,281,61,475,281,43,483,56,6,326,223,221,62,249,397,303,139,21,286,131,248,497,432,381,243,151,54,491,496,396]
[0,2,4,4,5,6,11,12,16,20,21,23,25,26,26,29,33,33,34,35,38,38,39,40,41,41,41,43,45,50,54,55,56,59,59,59,61,61,61,62,64,64,65,65,66,67,68,69,70,73,73,75,76,77,78,79,84,85,89,89,91,92,94,96,98,102,104,105,114,115,116,117,117,120,122,122,122,123,126,127,129,131,133,133,134,138,139,140,140,141,142,142,144,145,146,148,151,151,153,153,153,155,158,160,161,167,174,176,179,184,187,188,188,188,188,188,189,197,199,203,204,205,205,207,208,209,209,209,216,221,221,223,223,230,232,233,241,242,243,244,246,248,248,248,249,249,251,252,259,260,263,263,272,275,277,278,281,281,282,286,289,289,291,292,293,295,295,300,301,301,303,304,305,308,308,310,314,317,318,318,319,321,321,322,322,326,326,326,329,331,331,332,333,339,339,340,341,343,345,345,346,349,355,357,358,359,363,363,365,366,372,374,375,376,376,378,379,379,381,381,383,383,384,385,389,389,390,390,390,391,392,393,395,396,396,397,399,402,404,404,404,405,408,414,414,415,415,420,420,423,425,429,429,430,430,430,431,432,434,435,441,441,442,443,447,447,449,454,454,456,460,461,463,464,464,464,466,470,470,475,476,479,481,482,482,483,483,484,490,491,492,493,493,493,493,493,496,497,498,499]
the Crowd is:188, the Multiplicity is:5
发表更新Algorithm / Recursion3 分钟读完 (大约433个字)

comparison of BiTree

递归对比二叉链结构的二叉树

数据结构如下:

1
2
3
4
5
template<class T>
struct Node {
    T data;
    Node* lchild, * rchild;
};

实际方法如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <stdio.h>
using namespace std;

bool isEqual(Node<int>* bt1, Node<int>* bt2) {
	if (bt1 == NULL && bt2 == NULL)//正确的出口
		return true;
	else if (bt1 == NULL || bt2 == NULL)
		return false;
	else {
		cout << bt1->data << "," << bt2->data << endl;
		if (bt1->data != bt2->data)
			return false;
		return isEqual(bt1->lchild, bt2->lchild) && isEqual(bt1->rchild, bt2->rchild);
	}
}

生成测试二叉树函数如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//创建二叉树
//根据平衡二叉树规则生成
Node<int>* CreateBTtree(int a[], int n)
{
	Node<int>* root, * c, * pa = NULL, * p;
	int i;
	root = new Node<int>;
	root->data = a[0];
	root->lchild = root->rchild = NULL;
	for (i = 1; i < n; i++)
	{
		p = new Node<int>;
		p->lchild = p->rchild = NULL;
		p->data = a[i];
		c = root;
		while (c)
		{
			pa = c;
			if (c->data < p->data) //根节点小于待插入节点
				c = c->rchild;      //往右遍历
			else                  //根节点大于待插入节点 
				c = c->lchild;      //往左遍历
		}
		if (pa->data < p->data)
			pa->rchild = p;        //右放
		else
			pa->lchild = p;         //左放
	}
	return root;    //返回根节点
}

测试函数:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void test() {
	int a[8] = { 5, 3, 7, 2, 4, 6, 8, 9 };
	int b[8] = { 5, 3, 7, 2, 4, 6, 8, 15 };
	int c[7] = { 5, 3, 7, 2, 4, 6, 8 };
	int d[8] = { 5, 3, 7, 2, 4, 6, 8, 1 };
	Node<int>* bt1 = CreateBTtree(a, 8);
	Node<int>* bt2 = CreateBTtree(a, 8);
	Node<int>* bt3 = CreateBTtree(b, 8);
	Node<int>* bt4 = CreateBTtree(c, 7);
	Node<int>* bt5 = CreateBTtree(d, 8);
	cout << "A and B Equal or Not : " << (isEqual(bt1, bt2) ? "Equal" : "Not Equal") << endl;
	cout << "A and C Equal or Not : " << (isEqual(bt1, bt3) ? "Equal" : "Not Equal") << endl;
	cout << "A and D Equal or Not : " << (isEqual(bt1, bt4) ? "Equal" : "Not Equal") << endl;
	cout << "A and E Equal or Not : " << (isEqual(bt1, bt5) ? "Equal" : "Not Equal") << endl;
}

输出测试:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//output
5,5
3,3
2,2
4,4
7,7
6,6
8,8
9,15
A and C Equal or Not : Not Equal
5,5
3,3
2,2
4,4
7,7
6,6
8,8
9,empty
the nodes count not equal
A and D Equal or Not : Not Equal
5,5
3,3
2,2
empty,1
the nodes count not equal
A and E Equal or Not : Not Equal

G:\GithubProjects\C++\TrashCodes\Debug\TrashCodes.exe (进程 17836)已退出，代码为 0。
要在调试停止时自动关闭控制台，请启用“工具”->“选项”->“调试”->“调试停止时自动关闭控制台”。
按任意键关闭此窗口. . .
发表更新C++ / Sort3 分钟读完 (大约382个字)

QuickSort-快速排序

QuickSort

具体C++代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89

#include <iostream>
#include <vector> 
#include <cstdlib>
#include <ctime>
#include <sstream>
#define random(a,b) (rand()%(b-a)+a)
using namespace std;

//vector作为局部变量是不被允许返回的, 当需要处理一个vector并得到处理结果, 必须外部输入一个vector引用。
bool intRandomRange(vector<int>& res, int min, int max, int count) {
    srand((int)time(0));
    for (int i = 0; i < count; i++)
    {
        res.push_back((int)random(min, max));
    }
    return true;
}
//使用stringstream转换生成string, 用于测试
string vector2string(vector<int>& vec) {
    stringstream ss;
    for (int i = 0; i < vec.size(); ++i)
    {
        if (i != 0)
            ss << ",";
        ss << vec[i];
    }
    return ss.str();
}
bool contrastByOrder(int left, int right, bool bigger, bool equal) {
    if (equal)
        if (bigger)//升序比较
            return left >= right;
        else
            return left <= right;
    else
        if (bigger)
            return left > right;
        else
            return left < right;
    
}

//递归式快排_主体
int quickSort_main(vector<int>& vec, int left, int right, bool ascending) {
    int mid = left++;
    while (left <= right) {
        while (left <= right && contrastByOrder(vec[right], vec[mid], ascending, false))// vec[mid] < vec[right]|ascending = true;
            right--;
        if (left <= right) {
            swap(vec[mid], vec[right]);
            mid = right;//复位, 确保该轮中对比的数据仍不变
        }
        while (left <= right && contrastByOrder(vec[mid], vec[left], ascending, true))// vec[left] <= vec[mid]|ascending = true;
            left++;
        if (left <= right) {
            swap(vec[mid], vec[left]);
            mid = left;//复位
        }
    }
    return mid;
}
//递归式快排_递归体
void quickSort_Rp(vector<int>& vec, int left, int right, bool ascending) {
    if (left > right)//递归出口
        return;
    int mid = quickSort_main(vec, left, right, ascending);
    quickSort_Rp(vec, left, mid - 1, ascending);
    quickSort_Rp(vec, mid + 1, right, ascending);
}
//递归式快速排序_入口
bool quickSort(vector<int>& vec, bool ascending) {
    int count = vec.size();
    if (count <= 1)//无需排序的状态
        return false;
    quickSort_Rp(vec, 0, vec.size() - 1, ascending);
    return true;
}

int main()
{
    vector<int> test;
    intRandomRange(test, 0, 10, 10);
    cout << vector2string(test) << endl;
    if (quickSort(test, false))
        cout << vector2string(test) << endl;
    else
        cout << "No Need to Quick Sort" << endl;
}
关注我

链接

归档

标签

2PC1
3PC1
AI1
Algorithm1
AppServ1
BiTree1
Bitcoin1
C++4
CSS1
Cloud1
Cloud Computing3
Cloud Security1
Comparison1
Compute virtualization1
Course of Princeton University1
Cryptocurrency Technologies1
Cryptography1
Economics2
English3
English, Course, Review1
Github1
Github Action1
Go1
Greedy Algorithm1
Hexo1
Leetcode1
Lite-Travel1
MTD2
Macroeconomics1
Market-Economy1
Microeconomics1
Moving Target Defense2
NP hard1
Normative-economics1
Paper2
Philosophy1
Planned-Economy1
Positive-economics1
Program1
Security1
Shell6
Storage Virtualization1
Translation1
VM migration1
algorithm1
big data1
cryptology1
data analyze1
diary1
docker1
elastic-search2
hexo1
java5
kibana1
linux1
log1
mathematics1
mysql1
paper1
phpMyAdmin1
program2
python2
review1
security2
tech survey2
test3
themes1
translation1
writing6
writing, framework1
准备2
商志1
基本知识1
基础学习1
基础知识1
实操2
小作文1
感想1
政治1
数学1
数学一1
考公1
考研5
英语3
词汇1
问题2
面试1
高等数学1

订阅更新

You need to set client_id and slot_id to show this AD unit. Please set it in _config.yml.

follow.it

分类

最新文章

×