leetcode算法题解(Java版)-13-经典反转链表
一、简单二分搜索
题目描述
Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You may assume no duplicates in the array.
Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0
思路
- 题目很简单,二分就能通过
代码
public class Solution { public int searchInsert(int[] A, int target) { //二分查找 int left = 0; int right = A.length-1; while(left<=right){ int mid = (left+right)/2; if(A[mid]==target){ return mid; } else if(A[mid]<target){ left = mid+1; } else{ right = mid-1; } } return left; } }
二、反转链表
题目描述
Reverse a linked list from position m to n. Do it in-place and in one-pass.
For example:
Given1->2->3->4->5->NULL, m = 2 and n = 4,
return1->4->3->2->5->NULL.
Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.
思路
- 经典的题目,值得反复推敲。设置两个指针,一个指向m的位置,一个指向m之前的那个位置,不断刷新这两个指针的next,达到反转的效果。
- 注意,这两个指针本身不变化,变化的是他们的next.
- 这样做,满足了题意中的:do it in-place and in one-place
代码
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode reverseBetween(ListNode head, int m, int n) { ListNode dummy = new ListNode(0); dummy.next = head; ListNode start = head; ListNode prestart = dummy; for(int i=1;i<m;i++){ prestart = start; start = start.next; } ListNode tem; for(int i=0;i<n-m;i++){ tem = start.next; start.next = tem.next; tem.next = prestart.next; prestart.next = tem; } return dummy.next; } }
三、深搜
题目描述
Given a collection of integers that might contain duplicates, S, return all possible subsets.
Note:
Elements in a subset must be in non-descending order.
The solution set must not contain duplicate subsets.
For example,
If S =[1,2,2], a solution is:
[ [2], [1], [1,2,2], [2,2], [1,2], [] ]
思路
- 题目要列出所有不重复的,用所给数组中数字组成的非递减数列。
- 深搜解决问题:注意到不能有重复的数字,之前好像做过类似的题目,今天又碰到了,也就是要让拿的数字不能和已经拿过的一样。
if(start>i&&num[i]==num[i-1]
代码
import java.util.ArrayList; import java.util.Arrays; public class Solution { ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>(); public ArrayList<ArrayList<Integer>> subsetsWithDup(int[] num) { if(num==null||num.length==0){ return res; } Arrays.sort(num); findAll(num,0,new ArrayList<>()); return res; } public void findAll(int [] num,int start,ArrayList<Integer> list){ res.add(new ArrayList<Integer>(list)); for(int i=start;i<num.length;i++){ if(i>start&&num[i]==num[i-1]){ continue; } list.add(num[i]); findAll(num,i+1,list); list.remove(list.size()-1); } } }
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
JavaScript高级程序设计学习(三)之变量、作用域和内存问题
这次讲的主要是变量,作用域和内存问题。 任何一门编程语言,都涉及这三个。 变量,比如全局变量,局部变量等,作用域,也分全局作用域和方法作用域,内存问题,在java中就涉及到一个垃圾回收的问题,由于java中涉及到jvm,因此可以自动垃圾回收和内存分配,而不需要手动。 一、变量 每个变量都有其类型,数据类型。在java中分基本数据类型和引用数据类型,js同样如此。 面试题:java的基本数据类型有哪些,及其所占字节?引用类型有哪些? java基本数据类型分别为int(4),float(4),double(8),char(2),boolean(1),long(8),byte(2),short(2) 引用类型例如String或对象,枚举等,当然也可以回答说除了上述的基本数据类型外,都是引用数据类型。 题外分享到此为止,下面进入正题: (1)js的基本数据类型有哪些? 昨天的基本概念就说了,不过今天是系统的说, 基本数据类型分别为String,Number,null,Boolean,undefined 引用数据类型分别为Object,Array等 基本类型值指的是 简单的数据段,而引用类型值...
- 下一篇
虚拟的python环境virtualenv
有了大概的了解之后,看下具体的安装,只是介绍ubuntu下的安装: 通过命令: sudo apt-get install python-virtualenv或者 sudo pip install virtualenv 然后建立一个测试目录: mkdir testvirtual cd testvirtual 然后创建一个虚拟环境: virtualenv env1 cd切换到该目录下,执行命令: source bin/activate 你会发现在shell提示符前面多了(env1)这个提示,这就说明你已经是在虚拟环境中,在这个里面你可以安装任意的python库,而不用担心会把系统自带的python库搞乱。 另外有一个工具,封装了创建虚拟环境的过程,不需要再使用source [路径]来创建,只需使用一个命令,不需考虑路径。这个额外的工具就是:virtualenvwrapper。 通过如下命令进行安装: pip install virtualenvwrapper 在当前的命令窗口中输入 source /usr/share/virtualenvwrapper/virtual...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- CentOS6,CentOS7官方镜像安装Oracle11G
- SpringBoot2编写第一个Controller,响应你的http请求并返回结果
- Windows10,CentOS7,CentOS8安装MongoDB4.0.16
- SpringBoot2整合Thymeleaf,官方推荐html解决方案
- Springboot2将连接池hikari替换为druid,体验最强大的数据库连接池
- MySQL8.0.19开启GTID主从同步CentOS8
- CentOS8编译安装MySQL8.0.19
- 2048小游戏-低调大师作品
- CentOS7安装Docker,走上虚拟化容器引擎之路
- CentOS6,7,8上安装Nginx,支持https2.0的开启