算法练习(一)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了算法练习(一),小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2374字,纯文字阅读大概需要4分钟。
内容图文
![算法练习(一)](/upload/InfoBanner/zyjiaocheng/594/75638dae8d064f6b935f1fbf6134b3ce.jpg)
算法练习(一)
反转链表
题目描述
输入一个链表,反转链表后,输出新链表的表头。
输入
{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;
}
}
内容总结
以上是互联网集市为您收集整理的算法练习(一)全部内容,希望文章能够帮你解决算法练习(一)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。