头像

念心卓

中国公民




离线:3天前


最近来访(27)
用户头像
yxc的小迷妹
用户头像
33号花卷
用户头像
JessicaZhang
用户头像
White55kai
用户头像
流年之沫_2
用户头像
缠流子
用户头像
GEEZ
用户头像
Guilting
用户头像
Judy_wfy
用户头像
AmbitionX
用户头像
需要时间
用户头像
H2O2H
用户头像
KyrleForThree
用户头像
我想上成都电子科技大学
用户头像
yangbing
用户头像
北海没有WA
用户头像
i5-12490F
用户头像
易思人
用户头像
镜城颖月


念心卓
12天前

问题

现在有一颗二叉排序树,以二叉链表的形式存储
进行中序遍历可以得到从小到大的输出序列,现在要求对二叉排序树进行变换
使得其中序遍历序列为从大到小排列。


思路

  1. 先交换当前根结点左右子树的左右孩子结点
  2. 再交换当前根结点的左右孩子结点

C语言(关键代码)——使用了C++引用

void exChangeNode(BST& T) {
    if (!T || (T->lchild == NULL && T->rchild == NULL))//如果根结点为空或根结点无左右子树,直接返回
    {
        return;
    }
    exChangeNode(T->lchild);//递归处理左子树
    exChangeNode(T->rchild);//递归处理右子树
    if (T->lchild != NULL || T->rchild != NULL)//交换当前根的左右孩子结点
    {
        BiNode* tempNode = T->lchild;
        T->lchild = T->rchild;
        T->rchild = tempNode;
    }
}

完整代码

#include <stdio.h>
#include <stdlib.h>

typedef struct BiNode {
    int data;
    struct BiNode* lchild, * rchild;
}BiNode,*BST;

void insertBST(BST &T,int data){
    if (!T)//如果根结点为空,就把当前结点当做根结点
    {
        T = (BST)calloc(1, sizeof(BiNode));
        T->data = data;
    }
    if (T->data == data)
    {
        return;//如果当前结点的值等于要插入结点的值,插入失败
    }
    else if (T->data < data)
    {
        return insertBST(T->rchild, data);
    }
    else
    {
        return insertBST(T->lchild, data);
    }
}

void creatBST(BST &T,int* datas, int len) {
    T = NULL;
    int i = 0;
    while (i < len)
    {
        insertBST(T, datas[i++]);//将结点插入到二叉排序树中

    }
}

void inOrder(BST T) {
    if (T)
    {
        inOrder(T->lchild);
        printf("%d ", T->data);
        inOrder(T->rchild);
    }
}

void exChangeNode(BST& T) {
    if (!T || (T->lchild == NULL && T->rchild == NULL))//如果根结点为空或根结点无左右子树,直接返回
    {
        return;
    }
    exChangeNode(T->lchild);//递归处理左子树
    exChangeNode(T->rchild);//递归处理右子树
    if (T->lchild != NULL || T->rchild != NULL)//交换当前根的左右孩子结点
    {
        BiNode* tempNode = T->lchild;
        T->lchild = T->rchild;
        T->rchild = tempNode;
    }
}

int main() {
    BST root;
    int n;//数据个数
    scanf("%d", &n);
    int* datas = (int*)malloc(sizeof(int) * n);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &datas[i]);
    }

    creatBST(root,datas, n);//创建二叉排序树

    printf("二叉排序树从小到大输出\n");
    inOrder(root);//中序遍历二叉排序树(如果正确的话输出应该是从小到大的)
    printf("\n");

    //现在要将二叉排序树进行一个操作,让其中序遍历从大到小输出
    //1.将根结点的左右子树的左右孩子交换
    //2.交换根结点的左右孩子

    printf("二叉排序树从大到小输出\n");
    exChangeNode(root);
    inOrder(root);

    return 0;
}



念心卓
28天前
#include <stdlib.h>
#include <stdio.h>

typedef int ElemType;

typedef struct BiNode{
    ElemType data;
    struct BiNode *lchild,*rchild;
}BiNode,*BSTree;
bool InsertBST(BSTree &root,int data){
    if(!root){//如果root == NULL ,直接插入作为树根即可
        root = (BSTree)calloc(1,sizeof(BiNode));
        root->data = data;
        return true;//表示插入成功
    }
    if(root->data == data){
        return false;//表示插入失败
    }else if(root->data > data){
        return InsertBST(root->lchild,data);
    }else{
        return InsertBST(root->rchild,data);
    }
}
void CreatBST(BSTree &root, ElemType *datas, int len){
    root = NULL;//初始化树为空
    int i = 0;
    while(i < len){
        InsertBST(root,datas[i++]);//插入结点
    }
}
void InOrder(BSTree T){
    if(T != NULL){
        InOrder(T->lchild);
        printf("%d ",T->data);
        InOrder(T->rchild);
    }
}
//非递归查找(代码较为简洁)
bool SearchBST(BSTree T,ElemType target){
    while(T != NULL){//树为空,或者找到了要查找的值,就退出循环
        if(T->data < target){
            T = T->rchild;
        }else if(T->data > target){
            T = T->lchild;
        }else{
            return true;//表示找到了该结点
        }
    }
    return false;
}
int main(){
    BSTree root;
    int len;//数据长度
    scanf("%d",&len);
    ElemType *datas = (ElemType *)malloc(sizeof(ElemType)*len);//数据
    for(int i = 0; i < len; i++)
        scanf("%d",&datas[i]);

    //创建二叉排序树
    CreatBST(root,datas,len);

    //二叉树的遍历
    //中序遍历
    InOrder(root);
    printf("\n");

    //二叉排序树的查找
    ElemType target;
    scanf("%d",&target);
    //1.非递归
    if(SearchBST(root,target)){
        printf("该值在二叉排序树中存在");
    }else{
        printf("该值在二叉排序树中不存在");
    }
    free(datas);
    return 0;
}



念心卓
30天前
#include <stdlib.h>
#include <stdio.h>

//快排
void QuickSort(int *arr,int left,int right){
    if(left < right){
        int pivot = arr[left+right>>1];//选取中间位置元素为基准元素,避免快排出现O(n^2)的时间复杂度

        int low = left - 1;
        int high = right + 1;

        while(low < high){
            while(arr[++low] < pivot);
            while(arr[--high] > pivot);
            if(low < high){
                int temp = arr[low];
                arr[low] = arr[high];
                arr[high] = temp;
            }
        }

        QuickSort(arr,left,high);//递归处理左
        QuickSort(arr,high+1,right);//递归处理右
    }

}

//折半查找
int BinarySearch(int *arr, int target,int len){
    int low = 0;
    int high = len - 1;
    while(low <= high){
        int mid = (low + high) / 2;
        if(arr[mid] == target){
            return mid;
        }else if(arr[mid] < target){
            low = mid + 1;
        }else{
            high = mid - 1;
        }
    }
    return -1;//未找到返回-1;
}
int main(){
    int len;
    scanf("%d",&len);
    int *arr = (int *)malloc(sizeof(int) * len);
    for(int i = 0; i < len; i++){
        scanf("%d",&arr[i]);
    }

    //折半查找开始之前,首先要对序列进行排序,因为这是折半查找的必要条件
    QuickSort(arr,0,len-1);

    int target;//查找的目标值
    scanf("%d",&target);
    //折半查找
    int index = BinarySearch(arr,target,len);
    printf("%d",index);
    free(arr);
    return 0;
}



念心卓
30天前

一般线性表的顺序查找

采用了最普通查找方法,并且这里引用了哨兵可以避免很多不必要的判断语句


#include <stdlib.h>
#include <stdio.h>

typedef int ElemType;

//定义查找表的数据结构
typedef struct{
    ElemType *datas;
    int Len;//顺序表的长度
}SSTable;

int Search_Seq(int target,SSTable sqTable){
    sqTable.datas[0] = target;//把要查找的目标元素放入“哨兵”中
    int i;
    for(i = sqTable.Len; sqTable.datas[i] != target; i--);
    return i;//返回查找到元素的位置
}

int main(){
    SSTable sqTable;
    scanf("%d",&sqTable.Len);//输入数据长度
    int target;
    scanf("%d",&target);

    //第0个位置不放元素,用来充当哨兵    
    sqTable.datas = (ElemType)malloc(sizeof(int)*(sqTable.Len+1));
    for(int i = 1; i < sqTable.Len+1; i++)
        scanf("%d",&sqTable.datas[i]);
    int index = Search_Seq(target,sqTable);
    printf("%d\n",index-1);//(是下标);若这里没找到,那么返回的就是-1
    return 0;
}



念心卓
1个月前

题目描述

输入一系列整数,利用所给数据建立一个二叉搜索树,并输出其前序、中序和后序遍历序列。

输入格式

第一行一个整数 n,表示输入整数数量。

第二行包含 n 个整数。

输出格式

共三行,第一行输出前序遍历序列,第二行输出中序遍历序列,第三行输出后序遍历序列。

输入中可能有重复元素,但是输出的二叉树遍历序列中重复元素不用输出。

数据范围

1≤n≤100,
输入元素取值范围 [1,1000]。


输入样例:

5
1 6 5 9 8

输出样例:

1 6 5 9 8
1 5 6 8 9
5 8 9 6 1

注意:

如果里面代码有不懂的,可以去查看我的分享和相应问题的题解,写的比较详细

C 代码(使用了C++引用)

#include <stdio.h>
#include <stdlib.h>

typedef struct BiNode {
    int data;
    struct BiNode* lchild, * rchild;
}BiNode, * BSTree;

typedef struct LinkNode {
    BiNode* data;//存放的数据为树结点
    struct LinkNode* next;
}LinkNode, * LinkStack;

//初始化链栈
void initStack(LinkStack& S) {
    S = (LinkStack)malloc(sizeof(LinkNode));
    S->next = NULL;
}

//判断栈是否为空
bool EmptyStack(LinkStack S) {
    if (S->next) {
        return false;
    }
    return true;
}

//元素进栈
void Push(LinkStack& S, BSTree p) {
    LinkNode* node = (LinkNode*)malloc(sizeof(LinkNode));
    //头插法
    node->data = p;
    node->next = S->next;
    S->next = node;
}

//元素出栈
void Pop(LinkStack& S, BSTree& p) {
    if (EmptyStack(S))
        return;
    LinkNode* tempNode = (LinkNode*)malloc(sizeof(LinkNode));
    tempNode = S->next;
    p = tempNode->data;
    S->next = tempNode->next;
    free(tempNode);
}

//查看栈顶元素(非出栈)
void GetTop(LinkStack S, BSTree& p) {
    if (EmptyStack(S))
        return;
    p = S->next->data;
}

//二叉排序树的结点插入
void BSTInsert(BSTree& T, int data) {
    if (!T) {//如果原树为空,新插入的结点直接当做根结点
        T = (BSTree)calloc(1, sizeof(BiNode));
        T->data = data;
        return;
    }
    else if (data == T->data) {//相同元素插入失败
        return;
    }
    else if (data < T->data) {
        BSTInsert(T->lchild, data);
    }
    else {
        BSTInsert(T->rchild, data);
    }
}

//创建二叉排序树
void CreatBST(BSTree& T, int* arr, int len) {
    T = NULL;
    int i = 0;
    while (len--) {
        BSTInsert(T, arr[i]);
        i++;
    }
}

//先序遍历非递归法
void PreOrder2(BSTree T) {
    LinkStack S;
    initStack(S);
    BSTree p = T;
    while (p || !EmptyStack(S))
    {
        if (p)
        {
            printf("%d ", p->data);
            Push(S, p);
            p = p->lchild;
        }
        else
        {
            Pop(S, p);
            p = p->rchild;
        }
    }
}

//先序遍历递归法
void PreOrder(BSTree T) {
    if (T) {
        printf("%d ", T->data);
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
}

//中序遍历非递归法
void InOrder2(BSTree T) {
    LinkStack S;
    initStack(S);
    BSTree p = T;
    while (p || !EmptyStack(S)) {
        if (p) {
            Push(S, p);
            p = p->lchild;
        }
        else {
            Pop(S, p);
            printf("%d ", p->data);
            p = p->rchild;
        }
    }
}

//中序遍历递归法
void InOrder(BSTree T) {
    if (T) {
        InOrder(T->lchild);
        printf("%d ", T->data);
        InOrder(T->rchild);
    }
}

//后序遍历非递归法
void PostOrder2(BSTree T) {
    LinkStack S;
    initStack(S);
    BiNode* pre = NULL;//标记刚刚访问过的结点
    BSTree p = T;
    while (p || !EmptyStack(S))
    {
        if (p)
        {
            Push(S, p);
            p = p->lchild;
        }
        else
        {
            //查看当前栈顶元素
            GetTop(S, p);
            if (p->rchild && p->rchild != pre)//右子树存在,且没被访问过
                p = p->rchild;
            else
            {
                Pop(S, p);
                printf("%d ", p->data);
                pre = p;
                p = NULL;
            }
        }
    }
}

//后序遍历递归法
void PostOrder(BSTree T) {
    if (T) {
        PostOrder(T->lchild);
        PostOrder(T->rchild);
        printf("%d ", T->data);
    }
}

int main() {
    int n;
    scanf("%d", &n);
    int* arr = (int*)malloc(sizeof(int) * n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
    BSTree root;
    CreatBST(root, arr, n);
    //PreOrder(root);//递归法
    PreOrder2(root);
    printf("\n");
    //InOrder(root);//递归法
    InOrder2(root);//非递归法
    printf("\n");
    //PostOrder(root);//递归法
    PostOrder2(root);//非递归法
    free(arr);
    return 0;
}



念心卓
2个月前

问题

删除有序数组中的重复元素

思路:

用快慢指针
1. 让慢指针指向数组第一个元素,快指针指向数组的第二个元素
2. 判断快慢指针所指的元素是否相等
3. 若相等,则快指针后移
4. 若不相等,把快指针所指的元素赋值给慢指针后移一个的位置,之后快指针后移

int removeDuplicates(int* nums, int numsSize) {
    if (numsSize == 0) {
        return 0;
    }
    int fast = 1, slow = 0;
    while (fast < numsSize) {
        if (nums[fast] != nums[slow]) {
            nums[++slow] = nums[fast++];
        }else{
            fast++;
        }
    }
    return slow+1;//新数组长度
}

复杂度分析

时间复杂度为O(n)
空间复杂度为O(1)




念心卓
2个月前

题目描述

一个单链表中有 m 个结点,每个结点上的元素的绝对值不超过 n。

现在,对于链表中元素的绝对值相等的结点,仅保留第一次出现的结点而删除其余绝对值相等的结点。

请输出筛选后的新链表。

例如,单链表 21 -> -15 -> -15 -> -7 -> 15,在进行筛选和删除后,变为21 -> -15 -> -7


输入样例:

21->-15->-15->-7->15

输出样例:

21->-15->-7

数据范围
1≤m≤1000,
1≤n≤10000


思路:

这道题我是采用的空间换时间
1. 使用辅助数组记录链表中已经出现过的值,从而只对链表进行一次扫描
2. 因为结点的值的绝对值<=n,所以申请n+1(0~n)个空间的辅助数组即可
3. 结点的表示数组的下标,对应的位置的值取0或1,0表示该结点的值未出现过,1则代表出现过
4. 如果数组的值==0,保留该结点,反之删除该结点


C 代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 * 
 * Note: The returned array must be malloced, assume caller calls free().
 */

typedef struct ListNode LNode;

struct ListNode* filterList(struct ListNode* head) {
    //本题整体上我采用的是空间换时间
    LNode *tempHead = (LNode *)malloc(sizeof(LNode));//创建一个虚拟头结点方便操作
    tempHead->next = head;
    int *arr = (int *)malloc(sizeof(int) * 10001);
    for(int i = 0; i < 10001; i++)//初始化数组
        arr[i] = 0;

    while(tempHead->next){
       int data =  abs(tempHead->next->val);//将结点元素的绝对值保存到data中
       if(arr[data] == 0){//表示该结点的val没有出现过
           arr[data] = 1;//设置为出现过
           tempHead = tempHead->next;
       }else{
           LNode *temp = tempHead->next;
           tempHead->next = temp->next;
           free(temp);
       }
    }
    free(arr);
    return head;
}



念心卓
2个月前

题目描述

判断单链表中是否存在环,如果存在就输出环的入口结点,否则输出NULL


思路:

  1. 设置两个快慢指针,快的每次走两步,慢的每次走一步
  2. 如果存在环,那么快慢指针一定会相遇
  3. 相遇的时候,就重新设置一个指针,指回初始结点,然后慢指针不动
  4. 接下来两者每次都走一步,当两者相遇时,就是环的入口结点

PS:对于这道题,表面上是链表的题,其实是一道数学的证明题,读者可以再网上搜索本题的证明。

C代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

typedef struct ListNode LNode;
struct ListNode *entryNodeOfLoop(struct ListNode *head) {
    LNode *fast = head,*slow = head;//设置两个快慢指针
    while(fast&& fast->next){
        slow = slow->next;//慢指针每次走一步
        if(!fast->next) return NULL;
        fast = fast->next->next;//快指针每次走两步
        if(fast == slow){//如果快慢指针相遇,表明存在环
            LNode *p1 = head;//此时就让一个指针重新回到初始位置
            while(p1 != slow){//之后这两个指针同时移动(每次都走一步),当他们相遇时,就是环入口结点
                p1 = p1->next;
                slow = slow->next;
            }
            return p1;//返回入口结点
        }
    }
    return NULL;
}




念心卓
2个月前

题目描述

给定一个只包含大写字母的字符串 S,请你输出其中出现次数最多的字母。

如果有多个字母均出现了最多次,按字母表顺序依次输出所有这些字母。


输入格式

一个只包含大写字母的字符串 S。

输出格式

若干个大写字母,代表答案。


数据范围
对于 100% 的评测用例,1≤|S|≤106。


输入样例:

BABBACAC

输出样例:

AB

Java代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        Map<Character, Integer> map = new TreeMap();//按照key排序的map集合,防止后面再次排序
        BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
        String str = buf.readLine();

        for (int i = 0; i < str.length(); i++) {
            char ch = str.charAt(i);
            if(map.containsKey(ch)){//如果集合包含这个元素,则让其value+1
                map.put(ch, map.get(ch)+1);
            }else{
                map.put(ch, 1);//否则把他放入集合中
            }
        }
        int max = 1;
        for (Map.Entry<Character, Integer> entry : map.entrySet()) {
            if(max < entry.getValue()){
                max = entry.getValue();//找到最大的value
            }
        }
        for (Map.Entry<Character, Integer> entry : map.entrySet()) {
            if(entry.getValue() == max){
                System.out.print(entry.getKey());//根据最大的value输出key值
            }

        }
    }

}





念心卓
2个月前

题目描述

求链表的第一个公共结点

样例

给出两个链表如下所示:
A:        a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3

输出第一个公共节点c1

思路:

常规思想:
本意极易联想到“蛮”方法:在第一个链表上遍历每一个结点,之后再遍历第二个链表上的每一个结点。
若找到了相同的结点,则找到了他们的公告结点。
显然这种方法的时间复杂度为O(len1*len2).

本题思想:
1. 求两个链表的公共结点,在求之前,可以先考虑先将两个链表的尾端对齐
因为从第一个公共结点开始,两个链表的后面的所有结点一定是完全重合的。
2. 之后再分别得到两个链表的长度,让长的链表先进行移动,移动的距离就是两个链表的长度之差
3. 之后两个链表的头部就对齐了,这样就可以同步的进行比较,找出相同的

例如:

A:      a1 → a2 → c1 → c2 → c3
B: b1 → b2 → b3 → c1 → c2 → c3

显然这种方法消耗的时间主要是求长度,所以时间复杂度为O(len1+len2).


C代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode* List;
int Length(List list){
    int len = 0;
    while(list){
        len++;
        list = list->next;
    }   
    return len;
}
struct ListNode *findFirstCommonNode(struct ListNode *headA, struct ListNode *headB) {
    int lenA = Length(headA);
    int lenB = Length(headB);
    List LongList,ShortList;//分别表示长的链表和短的链表
    int dist;//表示两个链表长度之差
    if(lenA < lenB){
        LongList = headB;//如果链表a的长度小于b的长度,那么较长的一个就是b链表
        ShortList = headA;
        dist = lenB - lenA;//得到表长的差
    }else{
        LongList = headA;
        ShortList = headB;
        dist = lenA - lenB;
    }

    while(dist--){//先将较长的链表移动链表差值个位置
        LongList = LongList->next;
    }

    while(LongList){
        if(LongList == ShortList){
            return LongList;
        }else{
            LongList = LongList->next;
            ShortList = ShortList->next;
        }
    }

    return NULL;
}