算法练习(一)
2021/4/8 20:25:49
本文主要是介绍算法练习(一),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
算法练习(一)
反转链表
题目描述
输入一个链表,反转链表后,输出新链表的表头。
输入
{1,2,3}
返回值
{3,2,1}
题解
public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } } public class Solution { public ListNode ReverseList(ListNode head) { //判断链表为空或长度为1的情况 if(head==null||head.next==null){ return head; } ListNode pre = null;//当前节点的前一个节点 ListNode next = null;//当前节点的下一个节点 while(head!=null){ next = head.next;//记录当前节点的下一个节点位置 head.next = pre;//让当前节点指向前一个结点位置。完成反转 pre = head;//pre向右走 head = next;//当前节点继续向右走 } return pre; } }
解析
以3个节点为例:a b c
用pre记录当前节点的前一个节点
用next记录当前节点的后一个节点
- 当前节点a不为空,进入循环,先记录a的下一个节点位置next = b;再让a的指针指向pre
- 移动pre和head的位置,正因为刚才记录了下一个节点的位置,所以该链表没有断,我们让head走向b的位置。
- 当前节点为b不为空,先记录下一个节点的位置,让b指向pre的位置即a的位置,同时移动pre和head
- 当前节点c不为空,记录下一个节点的位置,让c指向b,同时移动pre和head,此时head为空,跳出,返回pre。
判断链表中是否有环
题目描述
判断给定的链表中是否有环。如果有环则返回true,否则返回false。
你能给出空间复杂度的解法么?
题解
/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public boolean hasCycle(ListNode head) { if(head==null) return false; //快慢两个指针 ListNode slow = head; ListNode fast = head; while(fast!=null && fast.next!=null){ //慢指针每次走一步 slow = slow.next; //快指针每次走两步 fast=fast.next.next; //如果相遇,说明有环,直接返回true if(slow==fast) return true; } //否则就是没环 return false; } }
解析
快慢指针,慢指针针每次走一步,快指针每次走两步,如果相遇就说明有环,如果有一个为空说明没有环。
最小的K个数
题目描述
给定一个数组,找出其中最小的K个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4。如果K>数组的长度,那么返回一个空的数组
输入
[4,5,1,6,2,7,3,8],4
返回值
[1,2,3,4]
题解
import java.util.ArrayList; public class Solution { public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) { if(k>input.length){ return new ArrayList(); } ArrayList<Integer> output = new ArrayList(); while(k>0){ int sign=999; int m=0; for(int i=0;i<input.length;i++){ if(sign>input[i]) { sign = input[i]; m = i; } } input[m]=9999; output.add(sign); k--; } return output; } }
这篇关于算法练习(一)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?