环形链表
1.给定一个链表，判断链表中是否有环。
将快指针的移动速度设置为慢指针的两倍，将快慢指针同时遍历链表，若此链表存在环的时候，遍历过程中必然存在快慢指针指向同一个元素的时候。
且此时快慢指针相遇点到入环点的距离，等于头结点到入环点的距离
设相遇时slow走的路程为S1，fast走的路程为S2，设相遇点为p;起点为s,入环点为e;
有S2=2*S1。 S1= sp, S2=sp+pp(fast绕了一圈)
所以有sp=pp，sp=se+ep,pp = pe+ep,所以se = pe这个等式很关键
/**
* 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||head.next==null){
return false;
}
ListNode slow=head,fast=slow;
while(fast!=null&&fast.next!=null){
slow=slow.next;
fast=fast.next.next;
if(slow==fast){
return true;
}
}
return false;
}
}
2.给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
用到java中内置contains方法和startsWith() 方法
作用：是判断是否存在包含关系的，
比如说集合a =[1,2,3,4]，b=1，那么a就包含b；
contains返回的是布尔类型true 和false，包含的话就返回true，不包含的话就返回false
startsWith() 方法用于检测字符串是否以指定的前缀开
public boolean startsWith(String prefix, int toffset)
prefix -- 前缀。
toffset -- 字符串中开始查找的位置。
BFS剪枝方法
package leetcode;
import java.util.*;
public class test {
String str;
static Set<Integer> cache = new HashSet<Integer>();;
List<String> list;
public static void main(String[] args){
List<String> name = new ArrayList();
test aa = new test();
name.add("leet");
name.add("coe");
name.add("code");
name.add("lee");
name.add("tecode");
System.out.println(aa.wordBreak("leetecodecoe",name));
Iterator<Integer> it = cache.iterator();
while (it.hasNext()) {
Integer str = it.next();
System.out.println(str);
}
}
boolean wordBreak(String s, List<String> wordDict) {
str = s;
cache=new HashSet<Integer>();
list=wordDict;
return wordBreak(0);
}
boolean wordBreak(int d){
System.out.println("d的值为："+d);
if(d == str.length())return true;
if(cache.contains(d))return false;//无需再次重复计算，因为以这个点开头已经判断不能了，剪枝
for(String word : list){
if(str.startsWith(word,d)){//从d位置开始查找，是否以指定的word开头
if(wordBreak(d+word.length())){
return true;
}
cache.add(d+word.length());//已经为false的 就是从这个点开始找 不存在以这个点开头且满足的单词 不满足的点
}
}
return false;
}
List<String> name = new ArrayList();
}
/*
d的值为：0
d的值为：4
d的值为：3
d的值为：9
d的值为：12
true
4
*/
3.给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
异或,不是对十进制异或,而是与之对应的二进制异或得出结果,如0000 ^ 0001,异或规则是:不同则为1,相同则为0,可以发现,0 ^ 任何数就等于该数本身,如果数组为{1,2,2},如1 ^ 2,就等于0001 ^ 0010,异或之后则为0011,如果再 ^ 2,就是遇见了第二个2,则为0011^0010,可得0001,就是剩下的数1,简单来说从0开始时,异或一个数相当于加上这个数,再异或这个数时,相当于减掉这个数,最后剩下的就是唯一存在的数了
学习java8的Stream（流）https://www.jianshu.com/p/314e284652d2
class Solution {
public int singleNumber(int[] nums) {
return Arrays.stream(nums).reduce((x, y) -> x ^ y).getAsInt();
}
}
题目变形
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。
将每个数想象成32位的二进制，对于每一位的二进制的1和0累加起来必然是3N或者3N+1， 为3N代表目标值在这一位没贡献，3N+1代表目标值在这一位有贡献(改位等于=1)，然后将所有有贡献的位|（或运算）起来就是结果。这样做的好处是如果题目改成K个一样，只需要把代码改成cnt%k，很通用
class Solution {
public int singleNumber(int[] nums) {
int sum = 0;
for(int i = 0;i < 32 ;i++){
int mask = 1 << i;
int cnt = 0;
for(int j=0;j<nums.length;j++){
if((nums[j]&mask)!=0){
cnt++;
}
}
if(cnt%3!=0){
sum |=mask;
}
}
return sum;
}
}
再变形题目
给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。
看注释
class Solution {
public int[] singleNumber(int[] nums) {
//将所有元素异或,得到的结果为出现一次的A^B
//其他出现两次的数在异或中抵消为0了
int xorResult = 0;
for(int i :nums){
xorResult ^=i;
}
//从后往前找出第一位为1的位置，那就是他俩的区别了
//tempRes为A^B的结果,通过右移diffNum的方式和它进行与操作，得到tempRes第一位为1的位置
int diffNum = 1;
while ((xorResult & diffNum) == 0) {
diffNum <<= 1;
}
//根据元素种类进行分类
//通过最低位为1的那个位进行划分，如
// 01 1 1 ^
// 00 0 1
// 01 1 0
//其中结果中最低位的1和diffNum 进行 &操作可以区分这两个数，其余数都属偶数个不用管，与运算为1表示这位数在这个位置是1，与另外一个数是有区别的(=0) 然后用异或还原成原来的数 因为偶数个异或为0 ，且和0异或该数不变
int resultA = 0, resultB = 0;
for(int j : nums){
if((diffNum & j) == 0){
resultA ^= j;
}else{
resultB ^= j;
}
}
return new int[]{resultA,resultB};
}
}
4.给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
哈希映射
这道题本身如果通过暴力遍历的话也是很容易解决的，时间复杂度在 O(n2)
由于哈希查找的时间复杂度为 O(1)，所以可以利用哈希容器 map 降低时间复杂度
1.遍历数组 nums，i 为当前下标，每个值都判断map中是否存在target-nums[i]的 key 值
2.如果存在则找到了两个值，如果不存在则将当前的(nums[i],i)存入 map 中，继续遍历直到找到为止
3.如果最终都没有结果则抛出异常
时间复杂度：O(n)
注意，该目标元素不能是 nums[i]nums[i] 本身！
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for(int i = 0; i< nums.length; i++) {
if(map.containsKey(target - nums[i])) {
return new int[] {map.get(target-nums[i]),i};
}
map.put(nums[i], i);
}
throw new IllegalArgumentException("No two sum solution");
}
}
map的put方法的时间复杂度为O（1），get方法的时间复杂度为O(1)~O(n)。
那么containKey()方法的时间复杂度呢，其实和get方法的时间复杂度是一样的，也是O(1)~O(n)
5.给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 1位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
思路
- 将两个链表看成是相同长度的进行遍历，如果一个链表较短则在前面补 0，比如
987 + 23 = 987 + 023 = 1010 - 每一位计算的同时需要考虑上一位的进位问题，而当前位计算结束后同样需要更新进位值
- 如果两个链表全部遍历完毕后，进位值为 1，则在新链表最前方添加节点 1
- 小技巧：对于链表问题，返回结果为头结点时，通常需要先初始化一个预先指针 pre，该指针的下一个节点指向真正的头结点head。使用预先指针的目的在于链表初始化时无可用节点值，而且链表构造过程需要指针移动，进而会导致头指针丢失，无法返回结果。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
//构造新链表
ListNode pre = new ListNode(0);
ListNode cur = pre;
//进位值
int carry = 0;
while(l1 != null || l2 != null) {
int x = l1 == null ? 0 : l1.val;//用0补全
int y = l2 == null ? 0 : l2.val;
int sum = x + y + carry;
carry = sum / 10;
sum = sum % 10;
cur.next = new ListNode(sum);
cur = cur.next;
if(l1 != null)
l1 = l1.next;
if(l2 != null)
l2 = l2.next;
}
if(carry == 1) {
cur.next = new ListNode(carry);
}
return pre.next;//真正的头节点为pre.next
}
}
6.给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
这道题主要用到思路是
滑动窗口.什么是滑动窗口?其实就是一个队列,比如例题中的abcabcbb，进入这个队列（窗口）为abc满足题目要求，当再进入a，队列变成了abca，这时候不满足要求。所以，我们要移动这个队列！如何移动？我们只要把队列的左边的元素移出就行了，直到满足题目要求！
一直维持这样的队列，找出队列出现最长的长度时候，就是解！
时间复杂度：O(n)
我们将字符存储在当前窗口 [i, j)（最初 j = i）中。 然后我们向右侧滑动索引 j，如果它不在窗口中，我们会继续滑动 j。直到 s[j] 已经存在于 窗口中。此时，我们找到的没有重复字符的最长子字符串将会以索引 i 开头。如果我们对所有的 i 这样做，就可以得到答案。
package leetcode;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
public class Solution {
public static int lengthOfLongestSubstring(String s) {
int n = s.length(), ans = 0;
Map<Character, Integer> map = new HashMap<>(); // 当前字符索引
// 尝试扩大范围[i，j]
for (int j = 0, i = 0; j < n; j++) {
if (map.containsKey(s.charAt(j))) {//判断是否存在某个键
// s[j] 在 [i, j) 范围内有与 j ′重复的字符，我们不需要逐渐增加 i 。 我们可以直接跳过 [i，j']范围内的所有元素，并将 i 变为 j' + 1。
i = Math.max(map.get(s.charAt(j)), i);//得到这个键的值与i比较
}
ans = Math.max(ans, j - i + 1);
map.put(s.charAt(j), j + 1);//存入键值 字符和它的位置加1 因为字符位置从0开始
}
return ans;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String str = scanner.next();
System.out.println(lengthOfLongestSubstring(str));
}
}
7.给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。
中位数被用来:将一个集合划分为两个长度相等的子集，其中一个子集中的元素总是大于另一个子集中的元素。
思路查看
package leetcode;
public class Solution {
public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
int n=nums1.length;
int m=nums2.length;
if(n>m) {
return findMedianSortedArrays(nums2,nums1);
}
int Rmin1 = 0,Lmax1 = 0,Rmin2 = 0,Lmax2 = 0,c1,c2,l=0,r=2*n;
//r=2*n,数组1是的长度2n+1,但是二分法是二分下标,r表示最大下标不是长度,hi=2n+1-1 =2n.
while(l<=r) {//二分
c1=(l+r)/2;
c2=(n+m)-c1;
Lmax1=(c1==0)?Integer.MIN_VALUE:nums1[(c1-1)/2];
Rmin1=(c1==2*n)?Integer.MAX_VALUE:nums1[c1/2];
Lmax2=(c2==0)?Integer.MIN_VALUE:nums2[(c2-1)/2];
Rmin2=(c2==2*m)?Integer.MAX_VALUE:nums2[c2/2];
if(Lmax1>Rmin2) {
r=c1-1;
}else if(Lmax2>Rmin1) {
l=c1+1;
}else {
break;
}
}
return (Math.min(Rmin1, Rmin2)+Math.max(Lmax1,Lmax2))/2.0;
}
public static void main(String[] args) {
int[] a1= {2,3};
int[] a2= {4,7};
System.out.println(findMedianSortedArrays(a1, a2));
}
}
8.给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
在 O(n^2)的时间内解决这个问题。
我们观察到回文中心的两侧互为镜像。因此，回文可以从它的中心展开，并且只有2n - 1个这样的中心。
你可能会问，为什么会是2n - 1个，而不是 n 个中心？原因在于所含字母数为偶数的回文的中心可以处于两字母之间（例如abba的中心在两个b之间）。
package leetcode;
public class Solution {
public static String longestPalindrome(String s) {
if(s==null||s.length()==0) {
return "";
}
int start = 0,end=0;
for(int i=0,l=s.length();i<l;i++) {
int len1=expandAroundCenter(s,i,i);
int len2=expandAroundCenter(s,i,i+1);//中心是俩个字符之间的情况
int len=Math.max(len1, len2);
if(len>end-start) {//这个就举例一下abasubbaabb
end=i+len/2;
start=i-(len-1)/2;
}
}
return s.substring(start, end+1);
}
public static int expandAroundCenter(String s, int left, int right) {
int L=left,R=right;
while(L>=0&&R<s.length()&&s.charAt(L)==s.charAt(R)) {
L--;
R++;
}
return R-L-1;
}
public static void main(String[] args) {
String str="sabccbad";
System.out.println(longestPalindrome(str));
}
}
9.垂直的两条线段将会与坐标轴构成一个矩形区域，较短线段的长度将会作为矩形区域的宽度，两线间距将会作为矩形区域的长度，而我们必须最大化该矩形区域的面积。
双指针法,头尾俩个指针，每次向内移动长度较短的，来达到获取最大面积
public class Solution {
public int maxArea(int[] height) {
int maxarea = 0, l = 0, r = height.length - 1;
while (l < r) {
maxarea = Math.max(maxarea, Math.min(height[l], height[r]) * (r - l));
if (height[l] < height[r])
l++;
else
r--;
}
return maxarea;
}
}
10.给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。注意：答案中不可以包含重复的三元组。
排序+双指针
1.首先对数组进行排序，排序后固定一个数nums[i]，再使用左右指针指向nums[i]后面部分的两端，数字分别为nums[L]和nums[R]]，计算三个数的和sum判断是否满足为 0，满足则添加进结果集
2.如果nums[i]大于 00，则三数之和必然无法等于 0，结束循环
3.如果nums[i] == nums[i-1]，则说明该数字重复，会导致结果重复，所以应该跳过
4.当sum == 0时，nums[L] == nums[L+1]则会导致结果重复，应该跳过，L++
5.当sum == 0时，nums[R] == nums[R−1]则会导致结果重复，应该跳过，R--
时间复杂度：O(n^2),n为数组长度
package leetcode;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Solution {
public static List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
if(nums==null||nums.length<3) {
return result;
}
Arrays.sort(nums);//排序
for(int i=0,l=nums.length;i<l;i++) {
if(nums[i]>0)break;
if(i!=0) {
if(nums[i]==nums[i-1])continue;
}
int L=i+1,R=l-1;
while(L<R) {
if(nums[i]+nums[L]+nums[R]==0) {
result.add(Arrays.asList(nums[i],nums[L],nums[R]));
while(L<R &&nums[L]==nums[L+1])L++;
while(L<R &&nums[R]==nums[R-1])R--;
L++;R--;
}else if(nums[i]+nums[L]+nums[R]<0) {
L++;
}else {
R--;
}
}
}
return result;
}
public static void main(String[] args) {
int[] a= {-1, 0, 1, 2, -1, -4};
System.out.println(threeSum(a));
}
}
