发表于 | 更新于 | 分类于

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
简单分析：
假设给出一个字符串： abcdechjil
第一个重复字符是c, 然而如果是简单暴力的话， 第一次从a开始找，找到第一个重复字符c，break，然后下一次要从b开始找
但是发现一个问题，因为b在 c的左边， 所以无论怎么样 无重复字符最长字串长度 都不会大于 从a开始遍历的长度。
所以，下一次直接从重复字符c的下一个字符d开始遍历就ok。

1
2
3
4
5
//暴力伪代码
for (int i = 0; i < n； i++)
{   
    for (int j = i + 1; j < n; j++)  
}

1.没用队列

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
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if (s.size() == 1) return 1;
        map<char,int> m;
        int n = s.size();
        int maxx = 0;
        int j = 0;
        for (int i = 0; i < n; i++) {  
            if (m.find(s[i]) != m.end()) {                                  //找到了
                int id = m[s[i]];
                for (int z = j; z < id; z++) {
                    m.erase(s[z]);
                }
                maxx = max(maxx, i - j);
                j = id + 1;
                // flag = 1;
            } else {
                maxx = max(maxx, i - j + 1);
            }
            m[s[i]] = i;
        }
        return maxx;
    }
};

2.用队列

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
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        queue<int> q;
        map<char, int> m;
        int maxx = 0;
        for (int i = 0; i < s.size(); i++) {
            if (m.find(s[i]) == m.end()) {
                q.push(s[i]);
                m[s[i]] = 1;
                int size = q.size();
                maxx = max(maxx, size);
            } else {
                while (!q.empty() && q.front() != s[i]) {
                    char c = q.front();
                    q.pop();
                    m.erase(c);
                }
                q.pop();
                q.push(s[i]);
            }
        }
        return maxx;
        
    }
};

发表于 | 更新于 | 分类于

给定一个树，按中序遍历重新排列树，使树中最左边的结点现在是树的根，并且每个结点没有左子结点，只有一个右子结点。
示例 ：

输入：[5,3,6,2,4,null,8,1,null,null,null,7,9]

   5
  / \
3    6

/ \ \
2 4 8
/ / \
1 7 9

输出：[1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]

1
\
2
\
3
\
4
\
5
\
6
\
7
\
8
\
9 

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    
    
    TreeNode* increasingBST(TreeNode* root) {
        if (root == NULL) return root;
        root->right = increasingBST(root->right);
        if (root->left) {
            TreeNode* left = root->left;
            root->left = NULL;
            TreeNode* node = left;
            while (node->right) {
                node = node->right;
            }
            node->right = root;
            return increasingBST(left);
         }
        return root;
        
    }
};

发表于 | 更新于 | 分类于

设计一个支持在平均 时间复杂度 O(1) 下，执行以下操作的数据结构。
insert(val)：当元素 val 不存在时，向集合中插入该项。
remove(val)：元素 val 存在时，从集合中移除该项。
getRandom：随机返回现有集合中的一项。每个元素应该有相同的概率被返回。

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
class RandomizedSet {
public:
    vector<int> v;
    map<int, int> m;
    bool insert(int val) {
        if (m.find(val) != m.end()) {
            return false;
        }
        v.push_back(val);
        m[val] = v.size() - 1;
        return true;
    }
        bool remove(int val) {
        if (m.find(val) == m.end()) {
            return false;
        } else {
            int i = m[val];                                //
            int last = v[v.size()-1];
            m.erase(val);
            v[i] = last;
            v.pop_back();
            if (v.size() != i)                       //
                m[last] = i;
        }
        return true;
    }
    int getRandom() {
        int n = v.size();
        return v[rand()%n];         
    }
};

发表于 | 更新于 | 分类于

1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int find(vector<int> a, int k) {
	int l = 0, r = a.size();
	int id;
	while (l <= r) {
	
		int mid = l + (r - l) / 2;
		if (a[mid] > k) { 
			id = mid;
			r = mid - 1;
		} else {
			l = mid + 1;
		}
	}
	return id;
}

2.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int binary(vector<int> v, int x) {
    int i = 0, j = v.size() - 1;
    while (i < j) {
        int mid = i + (j - i) / 2;
        if (v[mid] >= x) {
            j = mid;
        } else {
            i = mid + 1;
        }
       
    }
    
    return i;
}

发表于 | 更新于 | 分类于
功能：

一：进程内存管理
它有助于进程进行内存管理，主要体现在：
1.内存完整性：由于虚拟内存对进程的”欺骗”，每个进程都认为自己获取的内存是一块连续的地址。我们在编写应用程序时，就不用考虑大块地址的分配，总是认为系统有足够的大块内存即可。
2.安全：由于进程访问内存时，都要通过页表来寻址，操作系统在页表的各个项目上添加各种访问权限标识位，就可以实现内存的权限控制。
二：数据共享
通过虚拟内存更容易实现内存和数据的共享。
在进程加载系统库时，总是先分配一块内存，将磁盘中的库文件加载到这块内存中，在直接使用物理内存时，由于物理内存地址唯一，即使系统发现同一个库在系统内加载了两次，但每个进程指定的加载内存不一样，系统也无能为力。
而在使用虚拟内存时，系统只需要将进程的虚拟内存地址指向库文件所在的物理内存地址即可。如上文图中所示，进程 P1 和 P2 的 B 地址都指向了物理地址 C。
而通过使用虚拟内存使用共享内存也很简单，系统只需要将各个进程的虚拟内存地址指向系统分配的共享内存地址即可。
三：SWAP
虚拟内存可以让帮进程”扩充”内存。
我们前文提到了虚拟内存通过缺页中断为进程分配物理内存，内存总是有限的，如果所有的物理内存都被占用了怎么办呢？
Linux 提出 SWAP 的概念，Linux 中可以使用 SWAP 分区，在分配物理内存，但可用内存不足时，将暂时不用的内存数据先放到磁盘上，让有需要的进程先使用，等进程再需要使用这些数据时，再将这些数据加载到内存中，通过这种”交换”技术，Linux 可以让进程使用更多的内存。

发表于 | 更新于 | 分类于

给定一个结点，找出这个结点的后继结点
中序遍历：左 中 右
情况分类：
一：结点的右子树不为空
返回右子树的最左结点
二：结点的右子树为空
1.如果这个结点是根结点，直接返回NULL
2.如果这个结点是父节点的左儿子，直接返回父亲结点
3.如果这个结点是父节点的右儿子，不断向上找第一个结点，这个结点是他父亲结点的左儿子

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
// Definition for a Node.
/*
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* parent;
};
*/
class Solution {
public:
    Node* inorderSuccessor(Node* node) {
        
        if (node->right) {
            Node* p = node->right;
            while (p->left) {
                p = p->left;
            }
            return p;
        } else {
            if (node->parent == NULL) 
                return NULL;
            if (node->parent->left == node) 
                return node->parent;
            else {
                    Node *p = node->parent;
                    while (p && p->right == node) {
                        node = p;
                        p = p->parent;
                    }
                    return p;
            }
        }
    }
};

发表于 | 更新于 | 分类于 
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
/**
 * Definition for a binary tree node.
 * struct c {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* result;
    bool isInside(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == NULL) {
            return 0;
        }
        bool left, right;
        left = isInside(root->left, p, q);
        right = isInside(root->right, p, q);
        if ((right && left) || ((root == p || root == q) && (left || right))) {
             result = root;
             return 0;
         }
         if (left || right || root == p || root == q)
             return 1;
         return 0;
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        isInside(root, p, q);
        return result;
    }
};

发表于 | 更新于 | 分类于 
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
//给出出栈顺序  求所有进栈的序列 || 给出入栈顺序 求出栈顺序 
void print(stack<int> v) { 
	while (v.size() != 0) {
		cout<<v.top()<<" ";
		v.pop();
	}
	cout<<endl;
}
//a存放入栈序列，b模拟入栈， c存放可能的出栈的序列
void dfs(stack<int> a, stack<int> b, stack<int> c) {           
	
	if (a.size() == 0 && b.size() == 0 ) {
		print(c);	
		return;
	} 
	
	if (a.size() != 0) {		//入栈 
		int val = a.top();
		b.push(val);
		a.pop();
		dfs(a, b, c);
		b.pop();
		a.push(val);
	} 
	if (b.size() != 0) {		//出栈 
		int val = b.top();
		c.push(val);
		b.pop();
		dfs(a, b, c);
		c.pop();
		b.push(val);
	}
	
	return;
}

发表于 | 更新于 | 分类于

给定一个二叉树，原地将它展开为链表。
例如，给定二叉树
1
/ \
2 5
/ \ \
3 4 6
展开为：
1-2-3-4-5-6

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* last;
    void flatten(TreeNode* root) {
        if (root == NULL) return;
        flatten(root->right);
        flatten(root->left);
        root->right = last;
        root->left = NULL;
        last = root;
    }
};

链接：https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list

发表于 | 更新于 | 分类于

一个含有循环链表的链表怎么求它开始循环的入口？
给出一个循环链表的例子：
1->2->3->4->5->3 最后5又指向了3，也就是说3->4->5->3形成了一个环
假设非环形的长度是x, 环形的长度是y, 链表总长度是n = x + y
思路：
两个指针， fast一次走两步， slow一次走一步， 总有一次他们会在环的某一个位置相遇。
于是可以列出关系表达式：
fast = 2slow (一个走一步，一个走两步，走了相同的时间)
fast = slow + ny (fast比slow多走了n圈的环)
2slow = slow + ny -> slow = ny
得出了关键的表达式： slow = ny, 假设一下slow处于环形起点的时候，n*y 圈之后还会回到起点。但是，slow是从链表的起点开始的，所以从入口要回退x步， 就是fast和slow相遇的点， 也就是说 非环形的链表长度x 等于 fast和slow最后相遇的节点到环形入口的长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* fast = head;
        ListNode* slow = head;
        
        while (fast != NULL && fast->next != NULL) {
            fast = fast->next->next;
            slow = slow->next;
            if (fast == slow) {
                break;
            }
        }
        if (fast == NULL || fast->next == NULL) 
            return NULL; 
        fast = head;
   
        while(fast != slow) {
            fast = fast->next;
            slow = slow->next;
        } 
        return fast;
    }
};

发表于 | 更新于 | 分类于

输入: 1->2->3->3->4->4->5
输出: 1->2->5

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
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode* h = NULL;
        ListNode* pre = NULL;
        ListNode* cur = head;
        ListNode* r = NULL;
        while (cur != NULL) {
            if (juge(pre, cur) && juge(cur, cur->next)) {
                if (h == NULL) {
                    h = new ListNode(cur->val);
                    r = h;
                } else {
                    r->next = new ListNode(cur->val);
                    r = r->next;
                }
            }
            pre = cur;
            cur = cur->next;
        }
        return h;
    }
    bool juge(ListNode* node1, ListNode* node2) {
        if (node1 == NULL || node2 == NULL || node1->val != node2->val) {
            return true;
        }
        return false;
    }
};

发表于 | 更新于 | 分类于

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

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
class Solution {
public:
    ListNode* reverse(ListNode* root) {
        ListNode* pre = NULL;
        ListNode* node = root;
        ListNode* next;
        while (node != NULL) {
            next = node->next;
            node->next = pre;
            pre = node;
            node = next;
        }
        return pre;
    }
    
    ListNode* reverseKGroup(ListNode* head, int k) {
        if (head == NULL || head->next == NULL || k == 1) return head;
        ListNode* result = new ListNode(-1);
        ListNode* r = result;
        
        while (head != NULL) {
            int i;
            ListNode* start = head;
            ListNode* next;
            for (i = 1; i < k && head != NULL; i++) head = head->next;
            if (i <= k && head == NULL) {
                r->next = start;
                break;
            } else {
                next = head->next;
                head->next = NULL;
                r->next = reverse(start);
                r = start;
                head = next;
            }
        }
        return result->next;
    }
};

发表于 | 更新于 
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
class LRUCache {
public:
    list<int> link;
    map<int, int> m;
    int capacity;
    LRUCache(int capacity) {
        this->capacity = capacity;
    }
    
    int get(int key) {
        if(m.find(key) == m.end()) {
            return -1;
        } else {
            link.remove(key);
            link.push_front(key);
        }
        return m[key];
    }
    
    void put(int key, int value) {
        if (m.find(key) != m.end()) {       //已存在
            m[key] = value;
            link.remove(key);
            link.push_front(key);
        } else {                            //不存在
            if (m.size() >= capacity) {
                int keyLast = link.back();
                link.pop_back();
                m.erase(keyLast);
                
                link.push_front(key);
                m[key] = value;
            } else {
                m[key] = value;
                link.push_front(key);
            }
        }
    }
};

发表于 | 更新于 | 分类于

给一个有序的数组，那代码的时间复杂度就是O(n^2)拉。
最好就是取一个要排序数组中所有值的中值，（很难）

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
class Solution {
public:

    int partition(vector<int>& nums, int left, int right) {
       
       int mid = (left + right) / 2;
        if (nums[left] > nums[right]) 
            swap(nums[left], nums[right]);
        if (nums[mid] > nums[right])
            swap(nums[mid], nums[right]);
        if (nums[mid] > nums[left])
            swap(nums[mid], nums[left]);                //把中值换到最左边
        
        int val = nums[left];   
        int i = left, j = right;                        //填坑法
        while (i < j) {
           while (i < j && nums[j] >= val) j--;
           nums[i] = nums[j]; 
           while (i < j && nums[i] <= val) i++;
            nums[j] = nums[i];
        }
        nums[i] = val; 
        return i;
    }
 
    void sort(vector<int>& nums, int left, int right) {
        if (left >= right)
            return;
        int mid = partition(nums, left, right);
        sort(nums, left, mid-1);
        sort(nums, mid + 1, right);
    }
    vector<int> sortArray(vector<int>& nums) {
        
        sort(nums, 0, nums.size()-1);
        return nums;
    }
};

没有优化的快排贴一下：
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
int pattern(int l,int r)
{
	int i = l,j = r;
	while(i<j)
	{
		while(i<j && a[i]<=a[j])
			j--;
		if(i<j)
			swap(a[i],a[j]);
		while(i<j && a[i]<=a[j])
			i++;
		if(i<j)
			swap(a[i],a[j]);
	}
	return i;
}

void sort(int i,int j)
{
	if(i<j)
	{
		int mid = pattern(i,j);
		sort(i,mid-1);
		sort(mid+1,j);
	}
}

发表于 | 更新于 | 分类于

优化1 没有进行过交换结束
优化2 通过记录最后交换的位置，及终点的位置
优化3 波浪排序+优化1+优化2

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
#if 0
#include<bits/stdc++.h>                       
using namespace std;                      
int a[10000];
int n;
void sort(int a[], int n) {
	bool flag = 0;
	int k = n-1;
	int last;
	for (int i = 0; i < n-1; i++) {
		flag = 0;
		for (int j = 0; j < k; j++) {
			sum++;
			if (a[j] > a[j+1]) {
				flag = 1;
				last = j;
				swap(a[j], a[j+1]);
			}
		}
		if (flag == 0) {
			break;
		}
		k = last;
	}
}
int main()
{
	while(1) {
		sum = 0;
		cin>>n;
		for (int i = 0; i < n; i++) {
			a[i] = rand() % n;
		}		
		sort(a, n);
		for(int i = 0; i < n; i++)
			 cout<<a[i]<<" "; 
	
	}
} 

#endif

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
#if 0                      //波浪排序 就上两种优化
#include<bits/stdc++.h>
using namespace std;
int a[100000],n;
void sort(int a[], int n) {
	int left = 0, right = n-1;
	int flag = 0;
	int last;
	while (left < right) {
		for (int i = left; i < right; i++) {
			sum++;
			if (a[i] > a[i+1]) {
				swap(a[i], a[i+1]);
				flag = 1;
				last = i;
			}
		}
		if (flag == 0) break;
		right = last;
		flag = 0;
		for (int j = last; j > left; j--) {
			sum++;
			if (a[j] < a[j-1]) {
				swap(a[j], a[j-1]);
				flag = 1;
				last = j;
			}
		}
		if (flag == 0) break;
		left = last;
	}
}
int main()
{
	while(1) {
		cin>>n;
		for (int i = 0; i < n; i++) {
			a[i] = rand() % n;
		}		
		sort(a, n);
		for(int i = 0; i < n; i++)
			 cout<<a[i]<<" "; 
	
	}
}  
#endif

发表于 | 更新于 | 分类于

一：归并实现
1.递归写法
2.非递归写法，数组模拟递归（STL里源码思路）
二:插入实现

归并递归写法：

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
class Solution {
public:
    ListNode* merge(ListNode* left, ListNode* right) {
        ListNode* result = new ListNode(-1);
        ListNode* r = result;
        while (left != NULL && right != NULL) {
            if (left->val <= right->val) {
                r->next = left;
                r = r->next;
                left = left->next;
            } else {
                r->next = right;
                r = r->next;
                right = right->next;
            }
        }
        if (left != NULL) r->next = left;
        if (right != NULL) r->next = right;
        return result->next;
    }
    ListNode* sortList(ListNode* head) {
        if (head == NULL || head ->next == NULL) return head;
        ListNode* pre = NULL;
        ListNode* fast = head, *slow = head;
        while (fast != NULL && fast->next != NULL) {
            pre = slow;
            fast = fast->next->next;
            slow = slow->next;
        }
        pre->next = NULL;
        ListNode* left = sortList(head);
        ListNode* right = sortList(slow);
        return merge(left, right);
    }
};

归并非递归写法：
第二种着实很难理解，模拟了很久。敬畏敬畏。大道至简，就是这样哇。

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
class Solution {
public:
    ListNode* merge(ListNode* l1, ListNode* l2) {
        ListNode* result = new ListNode(-1);
        ListNode* r = result;
        while (l1 && l2) {
            if (l1->val <= l2->val) {
                r->next = l1;
                r = r->next;
                l1 = l1->next;
            } else {
                r->next = l2;
                r = r->next;
                l2 = l2->next;
            }
        }
        if (l1) {
            r->next = l1;
        }
        if (l2) {
            r->next = l2;
        }
        return result->next;
    }
    ListNode* table[64] = {NULL};
    int fill = 0;
    int i = 0;
    ListNode* carry;
    ListNode* sortList(ListNode* head) {
        if  (head == NULL || head->next == NULL) return head;
        while (head != NULL) {
            ListNode* next = head->next;
            head->next = carry;
            carry = head;
            i = 0;
            while (i < fill && table[i]) {
                table[i] = merge(carry, table[i]);
                carry = NULL;
                swap(carry, table[i++]);
            }
            swap(carry, table[i]);
            if(i == fill) fill++;
            head = next;
        }   
         ListNode* result;
        for (int i = 1; i < fill; i++) {
            table[i] = merge(table[i], table[i-1]);
        }
        return table[fill-1];
    }
};

插入排序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        ListNode* result = new ListNode(INT_MIN);
        ListNode* r = result;
        ListNode* next;
        while (head != NULL) {
            next = head->next;
            ListNode* r = result;
            while (r != NULL && r->next != NULL && r->next->val < head->val) {
                r = r->next;
            }
            head->next = r->next;
            r->next = head;
            
            head = next;
        }
        return result->next;
    }
};

发表于 | 更新于 | 分类于

一：

线程和进程各自有什么区别和优劣呢？

  • 进程是资源分配的最小单位，线程是程序执行的最小单位。
  • 进程有自己的独立地址空间，每启动一个进程，系统就会为它分配地址空间，建立数据表来维护代码段、堆栈段和数据段，这种操作非常昂贵。而线程是共享进程中的数据的，使用相同的地 址空间，因此CPU切换一个线程的花费远比进程要小很多，同时创建一个线程的开销也比进程要小很多。
  • 线程之间的通信更方便，同一进程下的线程共享全局变量、静态变量等数据，而进程之间的通信需要以通信的方式（IPC)进行。不过如何处理好同步与互斥是编写多线程程序的难点。
  • 但是多进程程序更健壮，多线程程序只要有一个线程死掉，整个进程也死掉了，而一个进程死掉并不会对另外一个进程造成影响，因为进程有自己独立的地址空间。

发表于 | 更新于 | 分类于 
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
//全排列 
#if 0
#include<bits/stdc++.h>
using namespace std;
void fun(int a[],int k,int m)
{
	if(k == m)
	{
		for(int i=0; i<=m; i++)
			cout<<a[i]<<" ";
		cout<<endl;
	}
	for(int i=k; i<=m; i++)
	{
		swap(a[k],a[i]);
		fun(a,k+1,m);
		swap(a[k],a[i]);
	}
}


int main()
{
	int n;
	int a[100];
	cin>>n; 
	for(int i=0; i<n; i++)
	{	
		cin>>a[i];
	}
	fun(a,0,n-1);
	
}
#endif

发表于 | 更新于 | 分类于 
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
1.KMP
/*KMP算法 
查询字符串a中 是否包含 字符串b    
ababcabcacbab
abcac
*/
    
void getNext(string str) {
	int k = 0;
	for (int i = 1; i < str.size(); i++) {
		while (k > 0 && str[i] != str[k])
			k = next[k-1];                               //精髓
		if (str[i] == str[k]) k++;
		next[i] = k;
	}
} 

int kmp(string s1, string s2) {
	int i = 0, j = 0;
	for (i = 0; i < s1.size() && j < s2.size(); i++) {
		 if (s1[i] == s2[j]) {
		 	j++;
		 } else {
		 	j = next[j-1];                          //需要感受
		 }
	}
	if (j == s2.size()) return i - s2.size();          //返回第一次匹配的的下标
	return -1; 
}
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
2.背包问题  
//     01背包问题  
// f[i][j]代表了 前i个物品的时候 容量为j的时候的最大的价值量，其中j必须是从v ...0的，因为每一个物品要选一次！！！ 

{
	
	int m,n;                 //m:背包的容量 n:物品的个数 
	cin>>m>>n; 
	int w[n+10];			   //每个物品的重量 
	int c[n+10];				//每个物品的价值 
	int f[m+10];             //f[k]代表 k个物品的时候，能装的最大的价值 
	memset(f,0,sizeof(f));
	for(int i=0; i<n; i++)
	{
		cin>>w[i]>>c[i];
	}
	for(int i=0; i<n; i++)
	{
		for(int v = m; v>=w[i]; v--)
		{
			f[v] = max(f[v],f[v-w[i]] + c[i]);
		}	
	} 
	cout<<f[m]<<endl;		
}


//完全背包问题
{
	int m,n;                 //m:背包的容量 n:物品的个数 
	cin>>m>>n; 
	int w[n+10];			   //每个物品的重量 
	int c[n+10];				//每个物品的价值 
	int f[m+10];             //f[k]代表 k个物品的时候，能装的最大的价值 
	memset(f,0,sizeof(f));
	for(int i=0; i<n; i++)
	{
		cin>>w[i]>>c[i];
	}
	for(int i=0; i<n; i++)
	{
		for(int v = w[i]; v<=m; v++)
		{
			f[v] = max(f[v],f[v-w[i]] + c[i]);
		}	
	} 
	cout<<f[m]<<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
3.最大上升 子序列 
/*给出 [4,2,4,5,3,7]，LIS 是 [2,4,5,7]，返回 4
*/

int fun(int a[],int n)
{
	int b[n];                    //截至到i 最大的上升子序列 的个数 
	for(int i=0; i<n; i++)
		b[i] = 1;
	for(int i=1; i<n; i++)
	{
		int max = -1;
		for(int j=0; j<i; j++)                        //找出前面比  此时的x 小的，并且 连续数最 大的   ~！！！ 
		{
			if(a[j] < a[i] && b[j] > max)
			{
				max = b[j];		
			}
		}
		if(max != -1)
			b[i] = max +1;
	}
	int maxx = 0;
	for(int i=0; i<n; i++)
		maxx = max(b[i],maxx);
	return maxx;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
最大子数组和
4.{
    int a[] = {1, -2, 3, -4, 5, 6, -7};
	int n = sizeof(a) / sizeof(int);
	int max = INT_MIN;
	int k = INT_MIN;
	for (int i = 0; i < n; i++) {
		if (k > 0) {
			k += a[i];	
		} else {
			k = a[i];
		}
		if (k > max) {
			max = k;
		}
	}    
  }

发表于 | 更新于 | 分类于 
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
//排序算法有 冒泡  / 快排/ 选择/堆排序/  归并 / 桶排序 /

//1.冒泡排序
#if 0
#include<bits/stdc++.h>
using namespace std;

void sort(int a[],int n)
{
	for(int i=0; i<n-1; i++)
	{
		for(int j=0; j<n-i-1; j++)          //
		{
			if(a[j] > a[j+1])
				swap(a[j],a[j+1]);
		} 
	} 
}
int  main()
{
	int a[1000];
	int n;
	cin>>n;
	
	for(int i=0; i<n; i++)
		cin>>a[i];
	sort(a,n);
	
	for(int i=0; i<n; i++)
		cout<<a[i]<<" ";
	
}
#endif 


//1.1 快速排序
 #if 0
#include<bits/stdc++.h>
using namespace std;
int a[1000];
int pattern(int l,int r)
{
	int i = l,j = r;
	while(i<j)
	{
		while(i<j && a[i]<=a[j])
			j--;
		if(i<j)
			swap(a[i],a[j]);
		while(i<j && a[i]<=a[j])
			i++;
		if(i<j)
			swap(a[i],a[j]);
	}
	return i;
}

void sort(int i,int j)
{
	if(i<j)
	{
		int mid = pattern(i,j);
		sort(i,mid-1);
		sort(mid+1,j);
	}
}

int  main()
{
	
	int n;
	cin>>n;
	
	for(int i=0; i<n; i++)
		cin>>a[i];
	sort(0,n-1);
	
	for(int i=0; i<n; i++)
		cout<<a[i]<<" ";
	
}
#endif
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
//2.选择排序

#if 0
#include<bits/stdc++.h>
using namespace std;

void sort(int a[],int n)
{
	int num;
	for(int i=0; i<n-1; i++)
	{
		num = i;
		for(int j=i+1; j<n; j++)          
		{
			if(a[j] > a[num])
				num = j;
		} 
		if(num != i)
			swap(a[num],a[i]);
	} 
}
int main()
{
		int a[1000];
	int n;
	cin>>n;
	
	for(int i=0; i<n; i++)
		cin>>a[i];
	sort(a,n);
	
	for(int i=0; i<n; i++)
		cout<<a[i]<<" ";
	
}
#endif
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
//3. 归并排序
#if 0
#include<bits/stdc++.h>
using namespace std;
int r[1000],r1[1000];
void merge(int s,int m,int t)
{
	int i=s,j=m+1,k=s;   

	while(i<=m && j<=t)
	{
		if(r[i]<=r[j])       	
			r1[k++] = r[i++];
		else
			r1[k++] = r[j++];
	}

	
		while(i<=m)
			r1[k++] = r[i++];
		while(j<=t)
			r1[k++] = r[j++];
				
	for(int z=s; z<=t; z++)
	  	r[z] = r1[z];
		

}
void sort(int s,int t)
{

	if(s>=t)
		return;
		
		int m = (s+t)/2;
		sort(s,m);
		sort(m+1,t);
		merge(s,m,t);
}

int main()
{

	int n;
	cin>>n;
	for(int i=0; i<n; i++)
	{
		cin>>r[i];
	}
	sort(0,n-1);
	
	for(int i=0; i<n; i++)
		cout<<r1[i]<<" "; 
			      
}
#endif
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
//4.堆排序

#if 0
#include<bits/stdc++.h>
using namespace std;
int a[100000];
int n;

void sift(int s,int t)
{
	int i=s,j=2*s;
	while(j<=t)
	{
	
		if(a[j+1] > a[j] && j<t)
			j++;
		if(a[i] > a[j])
			break;
		else
		{
			swap(a[i],a[j]);
			i = j;
			j = 2*i;
		}
	
	}

}

void sort(int n)
{
	for(int i=n/2; i>=1; i--)  
	{
		sift(i,n);
	}
	
	for(int i=1; i<n; i++)
	{
		swap(a[1],a[n-i+1]);
		sift(1,n-i); 
		
	}
}


int main()
{

	cin>>n;
	for(int i=1; i<=n; i++)
	{
		a[i] = n-i;
	}
	sort(n);
	
	for(int i=1; i<=n; i++)
		cout<<a[i]<<" ";
			
}
#endif
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
90
91
92
93
94
95
96
97
98
99
100
101
//基数排序

#if 0
#include<bits/stdc++.h>
using namespace std;
int head;
struct Node
{
	int key;
	int next;
};
struct QueueNode
{
	int front,rear;
};

void distribute(Node r[],int n,QueueNode q[],int m)
{
	int i = 0;                     							//默认为0   最后的next为 -1 
	while(1)
	{
		int key = r[i].key;
		if(q[key].front==-1)
		{
			q[key].front = i;
		}
		else
		{
			r[q[key].rear].next = i;
		} 
		q[key].rear = i;
		i = r[i].next;
		
		
		if(i == -1)
			break;
	}
	
}

void collection(Node r[],int n,QueueNode q[],int m)
{
	int k = 0;
	while(q[k].front==-1)
		k++;
	int first = q[k].front;
	int last = q[k].rear;
	head = first;
	
	while(k<m)
	{
		k++;
		if(q[k].front!=-1)
		{
			r[last].next = q[k].front;
			last = q[k].rear;
		}
	}
	r[last].next = -1;
}

void bucketSort(Node r[],int n,QueueNode q[],int m)
{
	for(int i=0; i<n; i++)
		r[i].next = i+1;
	r[n-1].next = -1;

	for(int i=0; i<m; i++)
	{
		q[i].front = q[i].rear = -1;	
	}  
	
	
	distribute(r,n,q,m);
	collection(r,n,q,m);
		
		
}

int main()
{
	Node r[1000];
	QueueNode q[1000];
	
	int n;
	cin>>n;
	
	for(int i=0; i<n; i++)
		r[i].key = n-i;
	
	bucketSort(r,n,q,100);	
	
	
	while(head!=-1)
	{
		cout<<r[head].key<<" ";
		head = r[head].next;
	}
	
}
#endif
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
//插入排序
#if 0
#include<bits/stdc++.h>
using namespace std;

void sort(int a[],int n)
{
	for(int i=2; i<=n; i++)
	{
		a[0] = a[i];
		int j;
		for(j=i-1; a[j] > a[0]; j--)
		{
			a[j+1] = a[j];
		}
		a[j+1] = a[0];
	}
}


int main()
{
	int a[100];
	int n;
	cin>>n;
	for(int i=1; i<=n; i++)
		cin>>a[i];
	sort(a,n);
	
	for(int i=1; i<=n; i++)
		cout<<a[i]<<" ";
	
}
#endif
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

//希尔排序
#if 0 
#include<bits/stdc++.h>
using namespace std;

void sort(int a[],int n)
{
	for(int d=n/2; d>=1; d/=2)
	{
		for(int i=d+1; i<=n; i++)
		{
			a[0] = a[i];
			int j;
			for(j=i-d; j>0&&a[0]<a[j]; j-=d)
			{
				a[j+d] = a[j];
			}
			a[j+d] = a[0];
		}
	}
}

int main()
{
	int a[100];
	int n;
	cin>>n;
	for(int i=1; i<=n; i++)
		cin>>a[i];
	sort(a,n);
	
	for(int i=1; i<=n; i++)
		cout<<a[i]<<" ";
}
#endif

golang版本如下：

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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
func sortArray(nums []int) []int {
    // quickSort(nums, 0, len(nums)-1)
    // mergeDfsSort(nums, 0, len(nums)-1)
    choiceSort(nums)
    return nums
}


// 选择排序
func choiceSort(nums []int) {
    n := len(nums)
    for i := 1; i < n; i++ {
        insertVal := nums[i]
        j := i-1
        for j >= 0 && nums[j] > insertVal {
            nums[j+1] = nums[j]
            j--
        }

        nums[j+1] = insertVal
    }
}



// 归并排序
func mergeDfsSort(nums []int, left, right int) {
    if left >= right {
        return
    }

    mid := left + (right-left) / 2
    mergeDfsSort(nums, left, mid)
    mergeDfsSort(nums, mid+1, right)

    mergeOnce(nums, left, mid, mid+1, right)
}

func mergeOnce(nums []int, aLeft, aRight, bLeft, bRight int) {
    numsTemp := make([]int, 0, bRight-aLeft+1)

    i, j := aLeft, bLeft
    for i <= aRight && j <= bRight {
        if nums[i] <= nums[j] {
            numsTemp = append(numsTemp, nums[i])
            i++
        } else {
            numsTemp = append(numsTemp, nums[j])
            j++
        }
    }

    for i <= aRight {
        numsTemp = append(numsTemp, nums[i])
        i++
    }
    for j <= bRight {
        numsTemp = append(numsTemp, nums[j])
        j++
    }

    copy(nums[aLeft:bRight+1], numsTemp)
}


// 快速排序
// 优化： https://chat.deepseek.com/share/ae3mlc7vdq4z6sm4iz
// 优化可以使用随机基准，避免数组本身是有序的情况下 复杂度上升到O(n2)
func quickSort(nums []int, left, right int) {
    if left >= right {
        return
    }

    mid := quickSortPartitionV1(nums, left, right)
    quickSort(nums, left, mid-1)
    quickSort(nums, mid+1, right)
}

func quickSortPartition(nums []int, left, right int) int {
    i, j := left, right

    for i < j {
        for i < j && nums[i] <= nums[j] {
            j--
        }
        if i < j {
            nums[i], nums[j] = nums[j], nums[i]
        }

        for i < j && nums[i] <= nums[j] {
            i++
        }
        if i < j {
            nums[i], nums[j] = nums[j], nums[i]
        }
    }

    return i
}

// 优化之后的版本
func quickSortPartitionV1(nums []int, left, right int) int {
    randomIndex := left + rand.Intn(right-left+1)
    nums[left], nums[randomIndex] = nums[randomIndex], nums[left]

    i, j := left, right

    for i < j {
        for i < j && nums[i] <= nums[j] {
            j--
        }
        if i < j {
            nums[i], nums[j] = nums[j], nums[i]
        }

        for i < j && nums[i] <= nums[j] {
            i++
        }
        if i < j {
            nums[i], nums[j] = nums[j], nums[i]
        }
    }

    return i
}