leetCode刷题记录
（1）Linked List Cycle
Total Accepted: 13297 Total Submissions: 38411Given a linked list, determine if it has a cycle in it.Follow up:Can you solve it without using extra space?（url：http://oj.leetcode.com/problems/linked-list-cycle/）
1，如果原有数据list可以改变的话，能够在O（n）级别上实现，算法如下：
遍历该list，验证当前访问的node的next值是不是head，如果不是，则更改next引用为head，遍历的过程中一直执行该过程，只要发现有一个元素通过next引用可以访问到head，则证明该list中存在环
缺点：变量完之后链表的本身引用结构被破坏了。
下述代码accept
/**
* 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 temp = head;
ListNode hold = head;
while(temp!=null){
if(temp.next==null){
return false;
}
else{
if( temp.next==head){
return true;
}
}
hold = temp;
temp = temp.next;
hold.next = head;
}
return false;
}
}
2, 如果原有数据list中node有其他存储空间，例如有空余的属性值可以使用该属性值作为标志位来区别访问前的访问后的节点。
3，如果能够确定node里面的节点属于某一个范围。则可以利用数字的大小来做为标识位。在数的大小范围很小的时候（小于int/2），可以使用node.val+MaxInt/2来做为标识位的同时，保持原有的数据信息。在执行完后进行数据还原。（这个解决办法的复杂度为O（n），同时能保护原有数据信息）
4，暴力法，不做标记，依次遍历每一个node.next的元素是不是之前曾经访问过的，两个for循环，复杂度O（n2）。
下述代码时间在处理一个非常大的list时时间超时
/**
* 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 temp;
ListNode hold = head;
while(hold!=null){
temp = head;
while(temp!=hold ){
if(hold.next==null)
{
return false;
}else{
while(temp!=hold){
if(hold.next==temp){
return true;
}
temp = temp.next;
}
if(hold.next==hold){
return true;
}
}
}
if(temp.next==hold){
return true;
}
hold = hold.next;
}
return false;
}
}
&&：本题的注意点：
测试用例，空list，单元素循环list，双元素循环list
循环list通过next访问是无限循环，所以需要设置好截至条件：返回值，断链等
（2）Linked List Cycle
（3）Single Number
Given an array of integers, every element appears twice except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
测试用例：单元素数组
本题的解法：
1.利用set不存储重复数据的特性，找出所有单个数据集合，然后2*sum（set）-sum（all）
这种解法的复杂度为O（n），遍历数组，每个数组元素查询，插入HashSet，查询和插入的复杂度为O（1），所以，总体复杂度为O（n）
需要额外的存储内存，HashSet
public class Solution {
public int singleNumber(int[] A){
int allSum = 0;
int numSum = 0;
Object[] numArr;
Set set = new HashSet();
for(int i=0;i<A.length;i++){
allSum += A[i];
set.add(A[i]);
}
numArr = set.toArray();
for(int i=0;i<set.size();i++){
numSum += Integer.parseInt(numArr[i].toString());
}
return numSum*2-allSum;
}
}
2.使用HashMap，key为值，value为次数建立HashMap的复杂度为O（n），转成list，然后根据list遍历查询次数为1的项（可优化？）
最新文章
- Ubuntu/Mint更换阿里云源
- 微信分享JS函数(原创)[已失效]
- CentOS搭建VPN
- windows 安装mysql 步骤
- 在Winform开发框架中实现对数据库的加密支持
- 动态调用webservice 接口
- (转)安装程序发布利器——InstallShield 2011 Limited Edition
- 初步认识 Web Service
- C# 扩展方法使用
- SuSE的命令安装软件 zypper
- Js删除数组函数
- Ubuntu下定时任务和自启动任务的部署
- python学习——读取染色体长度（五：从命令行输入染色体长度）
- 【论文阅读】Sequence to Sequence Learning with Neural Network
- 【转载】opencv实现人脸检测
- datepart in ssis
- JMeter（二十二）与其它工具对比（转载）
- R语言colorRampPalette函数-创建颜色梯度(渐变色)
- Python zipfile 编码问题
- Window History对象