当前位置： 首页 > article >正文

力扣-数据结构-1【算法学习day.72】

article 2024/12/25 5:51:26

前言

###我做这类文章一个重要的目的还是给正在学习的大家提供方向（例如想要掌握基础用法，该刷哪些题？建议灵神的题单和代码随想录）和记录自己的学习过程，我的解析也不会做的非常详细，只会提供思路和一些关键点，力扣上的大佬们的题解质量是非常非常高滴！！！

这几天今天复习一下数据结构

习题

1.二进制链表转整数

题目链接:1290. 二进制链表转整数 - 力扣（LeetCode）

题面:

分析:遍历链表，然后开一个变量，每次左移一位再加上链表上的值即可

代码:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public int getDecimalValue(ListNode head) {
        int sum = 0;
        for(ListNode i = head;i!=null;i=i.next){
           sum<<=1;
           sum+=i.val;
        }
        return sum;
    }
}

2. 找出临界点之间的最小和最大距离

题目链接:2058. 找出临界点之间的最小和最大距离 - 力扣（LeetCode）

题面:

分析:我们可以定义三个变量分别记录最开始的节点索引，上一个的索引，和最后的索引，那么最小距离就是在找到一个索引后，取ans[0]和当前索引与记录的上一个节点的索引的最小值，最大值就是最后一个索引与第一个索引的超值

代码:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    int[] ans = new int[]{Integer.MAX_VALUE,-1};
    public int[] nodesBetweenCriticalPoints(ListNode head) {
        int start = -1;
        int end = -1;
        int pre = -1;
        int count = 0;
        int index = 0;
        for(ListNode i =  head;i!=null&&i.next.next!=null;i=i.next){
            index++;
            int a = i.val;
            int b = i.next.val;
            int c = i.next.next.val;
            if(b>a&&b>c){ 
                count++;
                if(count==1)start = index;
                if(index>1)ans[0] = Math.min(ans[0],index - pre);
                pre = index;
            }
            else if(b<a&&b<c){
                count++;
                if(count==1)start = index;
                if(index>1)ans[0] = Math.min(ans[0],index - pre);
                pre = index;
            }
        }
        if(count<2)return new int[]{-1,-1};
        ans[1] = pre - start;
        return ans;
    }
}

3.合并零之间的节点

题目链接:2181. 合并零之间的节点 - 力扣（LeetCode） 

题面:

分析:这题遍历链表，定义一个变量sum来计算和值，如果下一个是0，就更新链表

代码:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeNodes(ListNode head) {
        ListNode ans = new ListNode();
        ListNode node = new ListNode();
        ans.next = node;
        int sum = 0;
        int count= 0;
        for(ListNode i = head;i!=null;i=i.next){
            if(i.val==0)continue;
            sum+=i.val;
             if(i.next.val==0&&count==0){
                node.val = sum;
                sum = 0;
                count++;
            }else if(i.next.val==0){
                ListNode node2 = new ListNode();
                node2.val = sum;
                sum = 0;
                node.next = node2;
                node = node2;
            }
        }
        return ans.next;
    }
}

4. 分割链表

题目链接:725. 分隔链表 - 力扣（LeetCode）

题面:

分析:这题主要看链表中节点的个数与k之间的数学关系，例如如果count/k==0，说明肯定不够分，那么就是将链表全分为单节点，如果>0，记flag = count/k，如果count%k！=0,为了迎合题意:任意两部分的长度差距不能超过1，且前面的长度大于后面的长度，则让前count%k的长度为flag+1

代码:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode[] splitListToParts(ListNode head, int k) {
        ListNode[] ans = new ListNode[k];
        int count = 0;
        for(ListNode i = head;i!=null;i=i.next)count++;
        // System.out.println(count);
        int flag = count/k;
        if(flag==0){
            int index = 0;
            for(ListNode i = head;i!=null;i=i.next){
                 ListNode node = new ListNode(i.val);
                 ans[index++]  = node;
            }
        }else{
            int fcount = count%k;
            int index = 0;
            int gcount = 0;
            boolean su = false;
            ListNode fhead = head;
            for(ListNode i = head;i!=null||((i==null)&&su);i=i.next){
                 if(su){
                    i = fhead;
                    su = false;
                 }
                 gcount++;
                 if(fcount>0&&gcount%(flag+1)==0){
                       ListNode node = i;
                       i = i.next;
                       su = true;
                       node.next = null;
                       ans[index++] = fhead;
                       fhead = i; 
                       gcount = 0;
                       fcount--;
                 }else if(fcount==0&&gcount%flag==0){
                        ListNode node = i;
                       i = i.next;
                       su = true;
                       node.next = null;
                       ans[index++] = fhead;
                       fhead = i; 
                       gcount = 0;
                 }
                 if(i==null)break;
                 
            }
        }
        return ans;
    }
}

5.链表组件

题目链接:817. 链表组件 - 力扣（LeetCode） 

题面:

分析:哈希表

代码:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public int numComponents(ListNode head, int[] nums) {
        Map<Integer,Integer> map = new HashMap<>();
        for(int a:nums){
            map.put(a,1);
        }
        int ans = 0;
        int count = 0;
        for(ListNode i = head;i!=null;i = i.next){
            if(map.getOrDefault(i.val,-1)==1){
                count++;
                continue;
            }else{
                if(count>0){
                    ans++;
                    count = 0;
                }
            }
        }
        if(count>0)ans++;
        return ans;
    }
}

6.移除链表元素

题目链接:203. 移除链表元素 - 力扣（LeetCode） 

题面:

分析:定义一个虚拟头结点会简单些

代码: 

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode fhead  = new ListNode();
        fhead.next = head;
        ListNode pre = fhead;
        for(ListNode i = head;i!=null;i = i.next){
            if(i.val==val){
                pre.next = i.next;
            }else{
                pre = i;
            }
        }
        return fhead.next;
    }
}

7.从链表中移除在数组中存在的节点

题目链接:3217. 从链表中移除在数组中存在的节点 - 力扣（LeetCode）

题面:

分析:在上一题的基础上加个哈希表

代码:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode modifiedList(int[] nums, ListNode head) {
        Map<Integer,Integer> map = new HashMap<>();
        for(int a:nums){
            map.put(a,1);
        }
        ListNode fhead = new ListNode();
        fhead.next = head;
        int count = 0;
        ListNode pre = fhead;
        for(ListNode i = head;i!=null;i = i.next){
            if(map.getOrDefault(i.val,-1)==1){
                pre.next = i.next;
            }else{
                pre = i;
            }
        }
        return fhead.next;
    }
}

8.删除排序链表中的重复元素

题目链接:83. 删除排序链表中的重复元素 - 力扣（LeetCode）

题面:

分析:和上面题类似

代码:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode fhead = new ListNode(Integer.MIN_VALUE);
        fhead.next = head;
        ListNode pre = fhead;
        for(ListNode i = head;i!=null;i = i.next){
            if(i.val == pre.val){
                pre.next = i.next;
            }else{
                pre = i;
            }
        }
        return fhead.next;
    }
}

9.删除排序链表中的重复元素II

题目链接:82. 删除排序链表中的重复元素 II - 力扣（LeetCode）

题面:

分析:这题有许多小问题需要考虑，值得细做 

代码:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode fhead = new ListNode(Integer.MAX_VALUE);
        fhead.next = head;
        ListNode pre = fhead;
        ListNode flag = fhead;
        int count = 1;
        boolean su  = false;
        for(ListNode i = head;i!=null;i = i.next){
            su = false;
            if(i.val!=pre.val&&count>=2){
                flag.next = i;
                count = 1;
                su = true;
            }else if(i.val==pre.val){
                count++;
            }
            if(i.val!=head.val&&i.val!=pre.val&&!su){
                flag = pre;
            }
            pre = i;
        }
        if(count>=2)flag.next = null;
        return fhead.next;
    }
}

10.删除链表中的节点

题目链接:237. 删除链表中的节点 - 力扣（LeetCode） 

题面:

分析:让node等于node的下一个节点的值，以此类推，但题目需要链表长度减一，那么倒数第二个节点应该指向null，如果i.next.next==null，说明此时遍历到的i就是倒数第二个节点

代码:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public void deleteNode(ListNode node) {
        for(ListNode  i = node;i!=null;i=i.next){
             i.val = i.next.val;
             if(i.next.next==null){
               i.next = null;
                break;
            }
        }
    }
}

11.合并两个链表

题目链接:1669. 合并两个链表 - 力扣（LeetCode） 

题面:

代码:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeInBetween(ListNode list1, int a, int b, ListNode list2) {
        ListNode fhead = new ListNode();
        fhead.next = list1;
        ListNode pre = fhead;
        int index = 0;
        boolean su = true;
        for(ListNode i = list1;i!=null;i=i.next){
             if(index==a){
                su = false;
             }
             if(su)pre = i;
             if(index==b){
                pre.next = list2;
                for(ListNode j = list2;j!=null;j = j.next){
                    if(j.next==null){
                        j.next = i.next;
                        break;
                    }
                }
                break;
             }
             index++;
        }
        return fhead.next;
    }
}

12.从链表中移除节点

题目链接:2487. 从链表中移除节点 - 力扣（LeetCode） 

题面:

分析:首先将链表中的值存到数组里去，然后从后往前遍历数组，并不断更新当前索引右边数字集合的最大值，如果当前索引所对应的值小于最大值，那么将当前位置标记成一个值（不在节点取值范围内），如果大于，就更新最大值，然后遍历链表，将标记的位置的节点删掉就行 

代码:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    int mu = 100005;
    public ListNode removeNodes(ListNode head) {
        int[] arr = new int[100005];
        int count = 0;
        for(ListNode i = head;i!=null;i=i.next){
            arr[count++] = i.val;
        }
        int max = arr[count-1];
        for(int i = count-2;i>=0;i--){
            if(arr[i]<max){
                arr[i] = mu;
            }else{
                max = arr[i];
                arr[i] = 0;
            }
        }
        ListNode fhead = new ListNode();
        fhead.next = head;
        ListNode pre  = fhead;
        int index = 0;
        for(ListNode i = head;i!=null;i=i.next){
            if(arr[index++]==mu){
                pre.next = i.next;
            }else{
                pre = i;
            }
        }
        return fhead.next;
    }
}

13.在链表中插入最大公约数

题目链接:2807. 在链表中插入最大公约数 - 力扣（LeetCode） 

题面: 

分析:这里用到了辗转相除法快速求最大公约数

代码:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode insertGreatestCommonDivisors(ListNode head) {
        if(head.next==null)return head;
        for(ListNode i = head;i!=null;i=i.next.next){
            int val = gcd(i.val,i.next.val);
            ListNode node = new ListNode(val);
            ListNode next = i.next;
            i.next = node;
            node.next = next;
            if(i.next.next.next==null)break;
        }
        return head;
    }
    public int gcd(int a,int b){
        return b==0?a:gcd(b,a%b);
    }
}

14.循环有序列表的插入

题目链接: LCR 029. 循环有序列表的插入 - 力扣（LeetCode）

题面:

贴上大佬代码:

class Solution {
    public Node insert(Node he, int x) {
        Node t = new Node(x);
        t.next = t;
        if (he == null) return t;
        Node ans = he;
        int min = he.val, max = he.val;
        while (he.next != ans) {
            he = he.next;
            min = Math.min(min, he.val);
            max = Math.max(max, he.val);
        }
        if (min == max) {
            t.next = ans.next;
            ans.next = t;
        } else {
            while (!(he.val == max && he.next.val == min)) he = he.next;
            while (!(x <= min || x >= max) && !(he.val <= x && x <= he.next.val)) he = he.next;
            t.next = he.next;
            he.next = t;
        }
        return ans;
    }
}

后言

上面是力扣数据结构相关，下一篇是其他的习题，希望有所帮助，一同进步，共勉！

 

 

 

 

 

 

 

 

 


http://www.kler.cn/a/450319.html

相关文章：

  • 美国加州房价数据分析01
  • vue中proxy代理配置(测试二)
  • SpringBoot简单使用Stomp
  • 【每日学点鸿蒙知识】AVCodec、SmartPerf工具、web组件加载、监听键盘的显示隐藏、Asset Store Kit
  • C/C++基础错题归纳
  • MVC 发布
  • 【微信小程序】3|首页搜索框 | 我的咖啡店-综合实训
  • Linux——字符设备驱动控制LED
  • 高性能Web网关：OpenResty 基础讲解
  • 汽车IVI中控开发入门及进阶（46）：FFmpeg
  • 常用网络协议
  • STM32高级物联网通信之以太网通讯
  • go语言并发文件备份，自动比对自动重命名（逐行注释）
  • 在【Arduino IDE】中在线下载和离线下载【ESP系列开发板的SDK】
  • Leetcode打卡：吃苹果的最大数目
  • 【直播电商】领域研究的综述（2024）·国内外混合方法分析—推文分析—2024-12-24
  • 电脑不小心删除了msvcr120.dll文件怎么办？“缺失msvcr120.dll文件”要怎么解决？
  • 监控易助力某市水利规划设计研究院信息化运维升级成功案例
  • 【算法day19】回溯：分割与子集问题
  • Qt如何将系统中使用的qDebug、qWarning等输出的信息显示到自定义的界面上或保存到文件中
  • Docker之技术架构【八大架构演进之路】
  • 验证面试常见问题系列
  • Python基础知识回顾
  • Apache Jmeter Liunx环境部署与接口压测
  • Typesense：开源的高速搜索引擎
  • 多个方向说下nginx和apache的区别