手撕代码基础

一.链表类
1.链表基础操作:

//NODE
type struct Node{
	int num;
	struct Node *next;
}node;
//INSERT
 p = (LinkList)malloc(sizeof(LNode));
 p->next = x ;
 p->next = l->next;
 l->next = p;
 //DELETE
 p = L;
 while() p = p->next;
 q = p->next;p->next=q->next;
 free(q);

2.链表倒置：

LinkNode prev = null;
LinkNode next = null;
while (node != null){
next = node.next;
node.next = prev;
prev = node;
node = next;}
return prev;

3.循环链表:

p = head;
q = head->next;
while (p!=NULL &&q!=NULL&&q->next!=NULL&&p!=q) {
	p = p->next;//p每次走一步
	q = q->next->next;//q每次走两步
}

4.两个链表的第一个公共节点:
遍历两个链表得到它们的长度a、b，在较长链表上先走a-b步，然后一起遍历直到有相同节点。时间复杂度O(m+n)。
5.链表快排：

pNode* partition(pNode* start,pNode* end){
    int num = start->val;
    pNode* p = start;
    pNode* q = start->next;
    while(q != end){
        if(q->val < num){
            p = p->next;
            swap(p->val,q->val);
        }
        q = q->next;
    }
    swap(p->val,start->val);
    return p;
}
void quick_sort(pNode* start,pNode* end){
    if(start != end){
        pNode* index = partition(start,end);
        quick_sort(start,index);
        quick_sort(index->next,end);
    }
}

6.合并两个有序链表：

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    if (l1 == null) {
        return l2; 
    }
    if (l2 == null) {
        return l1; 
    }
    ListNode head = null;
    if (l1.val < l2.val) {
        head = l1;
        head.next = mergeTwoLists(l1.next, l2);
    } else {
        head = l2;
        head.next = mergeTwoLists(l1, l2.next);
    }
    return head;
}

二.二叉树类
1.找最近公共子节点：

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {  
        //发现目标节点则通过返回值标记该子树发现了某个目标结点  
        if(root == null || root == p || root == q) return root;  
        //查看左子树中是否有目标结点，没有为null  
        TreeNode left = lowestCommonAncestor(root.left, p, q);  
        //查看右子树是否有目标节点，没有为null  
        TreeNode right = lowestCommonAncestor(root.right, p, q);  
        //都不为空，说明做右子树都有目标结点，则公共祖先就是本身  
        if(left!=null&&right!=null) return root;  
        //如果发现了目标节点，则继续向上标记为该目标节点  
        return left == null ? right : left;  
    }

2.非递归的先序、中序、后虚遍历
先序：

void preorder(binode* root){
    if (root==nullptr) return;
    binode *p=root;
    stack<binode*> s;
    while (p!=nullptr || !s.empty()){
        while (p!= nullptr){
            cout<<p->val;
            s.push(p);
            p=p->left;
        }
        if (!s.empty()){
            p=s.top();
            s.pop();
            p=p->right;
        }
    }
}

中序：

void midorder(binode* root){
    if (root==nullptr) return;
    binode *p=root;
    stack<binode*> s;
    while (p!=nullptr || !s.empty()){
        while (p!= nullptr){
            s.push(p);
            p=p->left;
        }
        if (!s.empty()){
            p=s.top();
            cout<<p->val;
            s.pop();
            p=p->right;
        }
    }
}

后序：

void postorder(binode* root){
    if (root==nullptr) return;
    binode *p=root;
    stack<binode*> s;
    stack<binode*> t;
    while (p!=nullptr || !s.empty()){
        while (p!= nullptr){
            s.push(p);
            t.push(p);
            p=p->right;
        }
        if (!s.empty()){
            p=s.top();
            s.pop();
            p=p->left;
        }
    }
    while (!t.empty()) {
        p=t.top();
        t.pop();
        cout<<p->val;
    }
}

3.二叉树层次遍历：

void layerorder(binode* root){
    if(root== nullptr)
        return;
    binode* p;
    queue<binode*> q;
    q.push(root);
    while (!q.empty()){
        p = q.front();
        q.pop();
        cout<<p->val;
        if(p->left!= nullptr){
            q.push(p->left);
        }
        if(p->right!= nullptr){
            q.push(p->right);
        }
    }
}

4.二叉搜索树中第K小的元素:

public int kthSmallest(TreeNode root, int k) {
    int count = countNodes(root.left);

    if (k <= count) {
        return kthSmallest(root.left, k);
    } else if (k > count + 1) {
        return kthSmallest(root.right, k - 1 - count);
    }
    return root.val;
}
public int countNodes(TreeNode n) {
    if (n == null) return 0;
    return 1 + countNodes(n.left) + countNodes(n.right);
}

三.排序和查找类
1.快排：

void quickSort(vector<int> &num, int l, int r) {
    if (l >= r)  return;
    int i = l, j = r, x = num[l];
    while (i < j) {
        while (i < j && num[j] >= x)//从右向左找到第一个小于x的
            j--;
        if (i < j)
            num[i++] = num[j];//填坑之后i++
        while (i < j && num[i] <= x)//从左向右找第一个大于x的数
            i++;
        if (i < j)
            num[j--] = num[i];
    }
    num[i] = x;     //把最开始取出来的x放到i处
    quickSort(num, l, i - 1);//以i为中间值，分左右两部分递归调用
    quickSort(num, i + 1, r);
}

2.归并：

void mergearr(int* a, int begin, int mid, int end, int *temp){// 归并排序单元使用
    int i=begin, j=mid+1;
    int m = mid, n = end;
    int k = 0;
    while (i <= m && j<= n){
        if (a[i]<a[j])
            temp[k++]=a[i++];
        else
            temp[k++]=a[j++];
    }
    while (i<=m)
        temp[k++]=a[i++];
    while (j<=n)
        temp[k++]=a[j++];
    for (i=0;i<k;i++){
        a[begin+i]=temp[i];
    }
}
void _merge_sort(int* a, int begin, int end, int *temp){// 归并排序算子
    if(begin<end) {
        int mid = (begin + end) / 2;
        _merge_sort(a, begin, mid, temp);
        _merge_sort(a, mid + 1, end, temp);
        mergearr(a, begin, mid, end,temp);
    }
}
int* MergeSort(int *a, int len){// 归并排序
    int *temp = new int[len];
    _merge_sort(a,0,len-1,temp);
    return temp;
}

3.堆：

void HeapAdjust(int k[],int p,int n){//大顶堆的构造，传入的i是父节点
    int i,temp;
    temp = k[p];
    for (i = 2 * p; i <= n;i*=2)    //逐渐去找左右孩子结点
    {
        //找到两个孩子结点中最大的
        if (i < n&&k[i] < k[i + 1])
            i++;
        //父节点和孩子最大的进行判断，调整，变为最大堆
        if (temp >= k[i])
            break;
        //将父节点数据变为最大的，将原来的数据还是放在temp中，
        k[p] = k[i];    //若是孩子结点的数据更大，我们会将数据上移，为他插入的点提供位置
        p = i;
    }
    //当我们在for循环中找到了p子树中，满足条件的点，我们就加入数据到该点p,注意：p点原来数据已经被上移动了，若没有找到，就是相当于对其值不变
    //插入
    k[p] = temp;
}
void HeapSort(int k[], int n){//大顶堆排序
    int i;
    //首先将无序数列转换为大顶堆
    for (i = n / 2; i > 0;i--) //注意由于是完全二叉树，所以我们从一半向前构造，传入父节点
        HeapAdjust(k, i, n);
    //上面大顶堆已经构造完成，我们现在需要排序，每次将最大的元素放入最后，然后将剩余元素重新构造大顶堆，将最大元素放在剩余最后
    for (i = n; i >1;i--){
        swap(k, 1, i);
        HeapAdjust(k, 1, i - 1);
    }
}

4.二分：

int getkey (int* a, int key, int low, int high){
    int mid = (low+high)/2;
    if (low>high) return -1;
    if (a[mid]==key) return mid;
    else if (a[mid]<key)
        return getkey(a,key,mid+1,high);
    else
        return getkey(a,key,low,mid-1);
}

四.图类
1.DFS：(普遍递归就行了。。)

public void DFSWithStack(TreeNode root) {
     if (root != null)
         return;
     Stack<TreeNode> stack = new Stack<>();
     stack.push(root);
 
     while (!stack.isEmpty()) {
         TreeNode treeNode = stack.pop();
         //在这里处理遍历到的TreeNode   
         if (treeNode.right != null)
             stack.push(treeNode.right);
 
         if (treeNode.left != null)
             stack.push(treeNode.left);
     }
}

2.BFS：

public void BFSWithQueue(TreeNode root) {
    Queue<TreeNode> queue = new LinkedList<>();
    if (root != null)
        queue.add(root);
    while (!queue.isEmpty()) {
        TreeNode treeNode = queue.poll();
        //在这里处理遍历到的TreeNode节点
        if (treeNode.left != null)
            queue.add(treeNode.left);
        if (treeNode.right != null)
            queue.add(treeNode.right);
    }
}

3.最短路径问题：
任意两点间的最短路，floyd算法，时间复杂度过高O(n^3)；

for(int k = 1; k <= n; k++)
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            if(e[i][j] > e[i][k]+e[k][j]) 
                e[i][j] = e[i][k]+e[k][j];

单源最短路，Dijkstra，基于贪心，无法处理负边；

for(int i = 1; i <= n; i++) dis[i] = e[1][i]; //初始化dis为源点到各点的距离
for(int i = 1; i <= n; i++) book[i] = 0; 
book[1] = 1; //初始时P集合中只有源点
for(int i = 1; i <= n-1; i++) //做n-1遍就能把Q遍历空
{
    int min = INF;
    int u;
    for(int j = 1; j <= n; j++) //寻找Q中最近的结点
    {
        if(book[j] == 0 && dis[j] < min)
        {
            min = dis[j];
            u = j;
        }
    }
    book[u] = 1; //加入到P集合
    for(int v = 1; v <= n; v++) //对u的所有出边进行松弛
    {
        if(e[u][v] < INF) 
        {
            if(dis[v] > dis[u] + e[u][v]) 
                dis[v] = dis[u] + e[u][v];
        }
    }
}

处理负边可以用Bellman-Ford。

for(int i = 1; i <= n; i++) dis[i] = INF;
dis[1] = 0; //初始化dis数组，只有1号的距离为0
for(int k = 1; k <= n-1; k++) //进行n-1轮松弛
    for(int i = 1; i <= m; i++) //枚举每一条边
        if(dis[v[i]] > dis[u[i]] + w[i]) //尝试进行松弛
            dis[v[i]] = dis[u[i]] + w[i];

4.最小生成树
prim算法：

int[] lowcost = new int[vertexSize];  // 定义一维数组，存放用于比较最小权值的顶点权值，0代表已经比较过
System.arraycopy(matrix[0], 0, lowcost, 0, vertexSize);  // 初始化数组为第一个顶点的权值
int sum = 0;

for (int i = 0; i < vertexSize; i++) {// 循环比较
    int min = -1;// 先比较找出最小的权值节点
    for (int j = 0; j < vertexSize; j++) {
        if (lowcost[j] > 0 && lowcost[j] < MAX_WEIGHT) {
            if (min == -1 || lowcost[min] > lowcost[j]) {
                min = j;
            }
        }
    }
    if (min == -1) {// 判断是否全部为0，找不到最小值
        break;
    }
    System.out.println("访问到了节点：" + min + "，权值：" + lowcost[min]);
    sum += lowcost[min];
    lowcost[min] = 0; // 将当前节点的值修改成0
    for (int j = 0; j < vertexSize; j++) {// 将存放最小权值的数组与下一个节点的所有连接点对比，找出最小权值
        if (matrix[min][j] < lowcost[j]) {
            lowcost[j] = matrix[min][j];
        }
    }
}

kruskal:

public void createMinSpanTreeKruskal() {
    int[] parent = new int[edgeSize]; // 定义一个一维数组，下标为连线的起点，值为连线的终点
    for (int i = 0; i < edgeSize; i++) {
        parent[i] = 0;
    }
    int sum = 0;
    for (Edge edge : edges) {
        int start = find(parent, edge.start);// 找到起点和终点在临时连线数组中的最后连接点
        int end = find(parent, edge.end);
        if (start != end) {// 通过起点和终点找到的最后连接点是否为同一个点，是则产生回环
            parent[start] = end;// 没有产生回环则将临时数组中，起点为下标，终点为值
            System.out.println("访问到了节点：{" + start + "," + end + "}，权值：" + edge.weight);
            sum += edge.weight;
        }
    }
    System.out.println("最小生成树的权值总和：" + sum);
}
private int find(int parent[], int index) {//获取集合的最后节点
    while (parent[index] > 0) {
        index = parent[index];
    }
    return index;
}

五.基础算法
1.全排列：

private static void permutation(int[] array, int index) {
       if (index == array.length - 1)
           System.out.println(Arrays.toString(array));

       for (int i = index; i < array.length; i++) {
           swap(array, i, index);
           permutation(array, index + 1);
           swap(array, i, index);
       }
   }

2.数组子集：

res = []
for i in range(1<<len(nums)):# 子集总共有多少个集合
    tmp = []
    for j in range(len(nums)):# 当前子集集合的生成
        if i & 1 << j:  # 当前子集集合包含第j字符的判断
            tmp.append(nums[j])
    res.append(tmp)
return res

3.极大数相加相减相乘：
（不想写

4.奇偶排序，给一个数组，让奇数在前面偶数在后面，或者偶数在前面奇数在后面：
先计算出奇数的个数count，然后用双指针来遍历，一个从头遍历到count，一个从数组尾部遍历到count。从前向后找到一个偶数的下标，从后向前找到一个奇数的下标，然后交换对应的值。直到遍历完整个数组。时间复杂度为O（n），空间复杂度为O（1）。

int front = 0,end = arr.length-1;//设置两个指针，一个指向头部，一个指向尾部
if (arr.length == 0){//数组长度为0则返回
    return;
}
while (front < end){
    while (front < arr.length && arr[front]%2 == 1){//从前往后找偶数
        front++;
    }
    while (end >= 0 && arr[end]%2 == 0){//从后往前找奇数
        end--;
    }
    if (front < end){//将前面的偶数与后面奇数交换位置
        int temp = arr[front];
        arr[front] = arr[end];
        arr[end] = temp;
    }
}

六.贪心和DP
1.LEETCODE322硬币问题：

public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount+1];
        for(int i = 0; i <= amount; i++){
            dp[i] = Integer.MAX_VALUE-5;
        }
        dp[0] = 0;
        for(int i = 1; i <= amount; i++){
            for(int j = 0; j < coins.length; j++){
                if(i >= coins[j]){
                    dp[i] = Math.min(dp[i], dp[i - coins[j]]+1);
                }
            }
        }
        if(dp[amount] == Integer.MAX_VALUE-5) return -1;
        return dp[amount];
    }
}

七.位运算类

八.数组类