刷题汇总（更新中）

发表于 | 分类于

平时零碎刷题的总结

求数组元素和是K的倍数的子串的最大长度

美团面经的一道题

原答案连接在此：求数组元素和是K的倍数的子串的最大长度

题目要求

序列中任意个连续的元素组成的子序列称为该序列的子串。

现在给你一个序列P和一个整数K，询问元素和是K的倍数的子串的最大长度。

比如序列【1,2,3,4,5】，给定的整数K为 5，其中满足条件的子串为{5}、{2,3}、{1,2,3,4}、{1,2,3,4,5}，

那么答案就为 5，因为最长的子串为{1,2,3,4,5}；如果满足条件的子串不存在，就输出 0。

输入：

第一含一个整数N, 1 ≤ N ≤ 105 。

第二行包含 N 个整数pi ，pi表示序列P第i个元素的值。0 ≤ pi ≤ 105 。

第三行包含一个整数 K， 1 ≤ K≤ 105 。

分析

子串就是序列的一部分，注意和连续子串区分开。

遇到判断倍数的问题要用取余运算，当然正数取余取模是一样的。

不是连续的子串不好用dp，因为不好寻找状态转移方程。

大概思路如下：

先遍历一遍序列，求出钱n项和，放到数组nums内

之后对nums内每一项对k取余，得到余数的数组。

再遍历k遍，得到数组中相同余数的两个数的最大和最小坐标。

或者在求出余数的时候直接将坐标放入长度为k的数组中，这样求最大最小坐标的时候不用遍历长度为n的数组，直接从长度为k的数组读取即可。

最后在将k个长度进行比较，当然k个序列只是最差的情况。返回最大的长度的首尾坐标即可。

代码是学习他人的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
import java.util.Scanner;  
  
public class Main {  
    private int getKMaxLength(int[] nums, int[] sums, int k) {  
        int n = nums.length;  
        int[] max = new int[k];  
        int[] min = new int[k];  
        for (int i = 0; i < k; i++) { //初始化坐标，为了能区分出不更新max，min数组的情况  
            max[i] = -1;  
            min[i] = n + 1;  
        }  
  
        int mod;  
        for (int i = 0; i < n + 1; i++) {  
            mod = sums[i] % k;  
            //记录整个数组的同余前缀和的最小下标和最大下标  
            max[mod] = Math.max(max[mod], i);//相同余数的下标存进来，保留最大下标  
            min[mod] = Math.min(min[mod], i);//保留最小下标  
            // 如果 a%b = c%b ,则a-c = b*k,k为常数  
        }  
  
        //然后，同余前缀和的最大下标与最小下标之差，取差的最大值就是最大长度  
        int count = 0;  
        for (int i = 0; i < k; i++) {  
            if (max[i] != -1 && min[i] != n + 1) {//下标i从0开始，下标最大为n-1  
                count = Math.max(count, max[i] - min[i]);  
            }  
        }  
        return count;  
    }  
  
    public static void main(String[] args) {  
        Scanner sc = new Scanner(System.in);  
        int n = sc.nextInt();  
        int[] nums = new int[n];  
        int[] sums = new int[n + 1];  
        sums[0] = 0;  
        for (int i = 0; i < n; i++) {  //初始化前n项和的数组
            nums[i] = sc.nextInt();  
            sums[i + 1] = sums[i] + nums[i];  
        }//for  
  
        int k = sc.nextInt();  
        sc.close();  
        System.out.println(new Main().getKMaxLength(nums, sums, k));  
    }//main  
}

需要学习并且记住的是Scanner类的使用（网申的笔试算法可能需要用到该类），因为要从键盘读入数据，而不是直接写在代码里面。因此要熟悉Scanner类的方法。本题中使用了

Scanner sc = new Scanner(System.in);

int n = sc.nextInt();

一个初始化，一个nextInt方法。具体Scanner类的使用方法待补充。。。

leetcode 1. Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

1
2
3
4
Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

就是找到数组中和为target的两个数，返回他们的坐标。

题目看似不难，但是还挺麻烦。。。首先不知道数组是不是排序的，又不想用暴力解法$O(n^2)$ 因此就要将数组排序。那么排序之前就要保存原有的值和序号之间的关系。因此用了一个HashMap。

之后提交的时候发现当有两个重复的数字的时候，后一个会覆盖前一个，英文HashMap不允许重复的key值。没办法，又用了一个HashMap，保存出现第二次的对应关系。因为题中说了，只有一对正确答案，所以出现三次四次均不考虑，因为就算有，他们也不是答案。如果是就违反了只有一对的原则。而且只有当返回两个一样的数字的时候，才会用到第二个HashMap，通常第一个HashMap就搞定了了。

下面说在排序好的数组中找到这两个数字。先取最大和最小的两个数字，自然就是最左边和最右边的数字了。

当二者和大于目标的时候说明两个数字必须要变小，因为最小的已经小无可小，因此只能减小最大的数，

同理 小于目标时，由于最大的大无可大，因此只能增加最小的值，而且已经计算过的值均不是正确答案 ，均是可以放弃的值。直到找到答案为止，因为本题的测试用例一定有答案，因此不用考虑其他的情况，直接输出答案即可。

最后去map中找原先这个值对应的序号，输出即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    public int[] twoSum(int[] nums, int target) {
        int [] tmp = nums;
        HashMap<Integer,Integer> map2 = new HashMap<>();
        HashMap<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if(!map.containsKey(nums[i]))
                map.put(nums[i],i);// 保存对应关系
            else
                map2.put(nums[i],i);
        }
        Arrays.sort(tmp); //排序
        int l = 0;
        int r = nums.length - 1;
        while(r > l) { // 寻找两个数的坐标
            if (tmp[l] + tmp[r] == target)
                break;
            while (tmp[l] + tmp[r] > target) 
                r--;
            while (tmp[l] + tmp[r] < target) 
                l++;
        }
        int [] result = new int [2];
        result[0] = map.get(tmp[l]);
        if(map2.containsKey(tmp[r]))
            result[1] = map2.get(tmp[r]);
        else
            result[1] = map.get(tmp[r]);
        return result;
    }
}

Leetcode 2. Add Two Numbers

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example

1
2
3
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

题目的意思是两个链表，将其看成两个十进制数，然后求和，将和表示成链表的形式。

也是挺麻烦的。。（貌似我自己写麻烦了）

首先将链表转化成数字（感觉直接用链表找值也行，不用ArrayList也可以。。。）

注意转化的时候两个链表长度可能不一样。。。。（吐槽：为啥要转化，直接从链表读值不好么。。。）

然后一位一位的加，不要问我为什么不直接求整体的和再对10取余，因为数字有可能超范围。。。。

加完之后创建链表节点添加到链表中就可以了。

注意最后还有进位的话要多添加一个值为1的节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/**
 * 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) {
        ArrayList<Integer> L1 = new ArrayList<>();
        ArrayList<Integer> L2 = new ArrayList<>();
        while (l1 != null) {
            L1.add(l1.val);
            l1 = l1.next;
        }
        while (l2 != null) {
            L2.add(l2.val);
            l2 = l2.next;
        }
        int len1 = L1.size();
        int len2 = L2.size();
        int len = len1 > len2 ? len1 : len2;
        ListNode result = new ListNode(0); //哨兵或者标志，为了记住返回节点
        ListNode last = new ListNode(0);
        result = last;
        int a,b,s;
        int flag = 0; // 进位标志
        for (int i = 0; i < len; i++) {
            a = i < len1 ? L1.get(i) : 0; //没有值就是0
            b = i < len2 ? L2.get(i) : 0;
            s = a + b + flag;
            if (s > 9) 
                flag = 1;
            else
                flag = 0;
            ListNode temp = new ListNode(s % 10);
            last.next = temp;
            last = temp;  
        }
        if (flag == 1)
            last.next = new ListNode(1); //最后还有进位的话，多添加一个节点
        return result.next;
    }
}

两个有序数组找第K大的数

普通解法;

两个指针，分别遍历两个数组，每次讲两个指针中较小的数向后移动一位。知道统计了k的数为止，有点像两个有序数组找相同元素的算法。

当然这样在k很大的时候效果也很一般，O(log m + log n)使用二分法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static int findk(int[] A, int al, int ar, int [] B, int bl, int br, int k) {
			
	int m = ar - al + 1;
	int n = br - bl + 1;		
	int i = al + (int) ((double)m / (m+n) * (k-1));
	int j = al + bl + (k - 1) - i;		
	int Ai_1	= i == al ? Integer.MIN_VALUE : A[i-1];
	int Bj_1 	= j == bl ? Integer.MIN_VALUE : B[j-1];
	int Ai		= i == ar+1 ? Integer.MAX_VALUE : A[i];
	int Bj		= j == br+1 ? Integer.MAX_VALUE : B[j];		
	if (Bj_1 <= Ai && Ai <= Bj)			
		return Ai;
	else if (Ai_1 <= Bj && Bj <= Ai)
		return Bj;
	if (Ai < Bj)
		return findk(A, i+1, ar, B, bl, br, k-i-1);
	else
		return findk(A, al, ar, B, j+1, br, k-j-1);		
}

递归的时候没办法用指针，就只能自己造指针了，每次传入序号的起点和终点。

维护一个 i + j + 1 = k 的等式， 因为Ai前面有i个数，Bj前面有j个数，如果正好Ai在Bj-1和Bj之间，那么Ai前面的数就有A数组的i个加上B数组的j个，Ai就是第i+j+1个数。

如果不是这样，就说明Ai太小，第K个数比Ai大，于是就将Ai前面的数字去掉，更新k以及A数组的序号。

rand5求rand7

1
2
3
4
5
6
7
8
9
int rand7()
{
    int x = 0;
    do
    {
        x = 5 * (rand5() - 1) + 1 * rand5();
    }while(x >= 21);
    return 1 + x%7;
}

x进制数的生成方法，每一位都是随机生成的：5 * (rand5() - 1) + rand5()；这里第一个5就是5进制第二位的权重，然后1就是下一位的权重；

这样生成了数字之后，数字均是等可能性的。然后求余数就可以了。

LRU

先这么写，LinkedHashMap的东西以后再补

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import java.util.LinkedHashMap;
import java.util.Map;
/**
 * 简单用LinkedHashMap来实现的LRU算法的缓存
 */
public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private int cacheSize;
    public LRUCache(int cacheSize) {
        super(cacheSize, (float) 0.75, true); //将参数固定，也可以自己定义。
        this.cacheSize = cacheSize;
    }
    //重写
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > cacheSize;
    }
}

数组存水

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static int f(int[] arr) {
    int len = arr.length;
    int maxl = arr[0];
    int maxr = arr[len-1];
    int l = 0;
    int r = len - 1;
    int ans = 0;
    while(l < r) {
        maxl = arr[l] > maxl ? arr[l] : maxl;
        maxr = arr[r] > maxr ? arr[r] : maxr;
        if (maxl > maxr) {
            ans += maxr - arr[r];
            r--;
        }
        else {
            ans += maxl - arr[l];
            l++;
        }
    return ans;
}

思路，左右两边遍历保存左右两边的极值，然后选取较小一遍存入注水量。理由，较小的一边可以直接计算的原因是有一边的极值是准确的，另一边的极值虽然待定，但是由于是选取两边极值较小的作为上限，因此待定的极值可以直接舍弃，因为他肯定不是较小的。因此就用已确定的极值作为上限。

二叉树深度

左子树的深度和右子树深度最大值加一

1
2
3
4
5
6
7
8
9
10
11
12
public static int GetTreeDepth(BinaryTreeNode root)
    {
        if (root == null)
        {
            return 0;
        }

        int left = GetTreeDepth(root.LeftChild);
        int right = GetTreeDepth(root.RightChild);

        return left >= right ? left + 1 : right + 1;
    }

二叉树LCA最近公共祖先

递归寻找：

先在左子树中找LCA再在右字树中找LCA，然后如果左右均存在，则证明一个在做一个在右，当前节点就是LCA，

不然一个存在一个不存在，就证明两个节点在同一个字树上，直接返回那个值即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static TreeNode f(TreeNode root. TreeNode p, TreeNode q) {
	if (root == null)
		return null;
	if (root == p || root == q)
		return root;
	TreeNode left =  f(root.left,p,q);
	TreeNode right = f(root.right,p,q);
	if (left != null && right != null)
		return root;
	else if (left != null) 
		return left;
	else if (right != null)
		return right;
	else
		return null;
}

如果是存在只想父亲节点的指针，就可以转化成两个链表找公共部分。

如果是排序二叉树，就是比大小，知道当前节点在两个数之间即可

k对括号全部情况

用递归来做

首先从临界的状态写代码：左右和总数分别是l.r.n

  1. r == n 说明括号全部添加完毕，可以打印输出；
  2. l == r 说明没完毕但是左右括号相等了，那么只能添加左括号 然后递归；
  3. 然后是最常见的 l > r：
    1. 首先判断左括号的数量 l==n，如果true，那么无法添加左括号，只能添加右括号，然后递归；
    2. 继续可以尝试添加左括号，然后继续递归；
    3. 如果左括号的情况全部结束了，那么就应该将左括号去除，换成右括号继续递归；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
static int count;   
public static void f(int l, int r, int n, StringBuffer sb) {
	if( r == n) {
		System.out.println(sb);
		count ++;
		return;
	}
	else if (l == r) {
		sb.append("(");
		l++;
		f(l,r,n,sb);
	}
	else {
		if (l == n) {
			sb.append(")");
			r++;
			f(l,r,n,sb);
		}
		else {
			sb.append("(");
			l++;
			f(l,r,n,sb);
			l--;
			sb.delete(l+r,sb.length());//delete方法
			sb.append(')');
			r++;
			f(l,r,n,sb);
		}
	}
}

翻转二叉树（镜像二叉树）

递归翻转左子树，右子树，再将左右子树交换。

https://zhangjiej.github.io/posts/note_of_jianzhioffer_solution_Java2/第8题

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
    public void Mirror(TreeNode root) {
        if (root == null) { // 空的时候不做任何操作
            return;
        }
        Mirror(root.left);
        Mirror(root.right);
        TreeNode temp = new TreeNode(0);
        temp = root.left;
        root.left = root.right;
        root.right = temp;
    }
}

最大连续子串和

dp公式：以第i个数为末尾的子串的最大和为

sum[i]=max(sum[i-1]+a[i],a[i])

再找出所有最大和中最大的数即可

剑指offer-3的第十题https://zhangjiej.github.io/posts/note_of_jianzhioffer_solution_Java3/

1
2
3
4
5
6
7
8
9
10
public static int max(int a[], int len)  
{  
    int sum = a[0];
    int max = 0;
    for (int i=1; i<len; i++) {  
        sum = (sum + a[i]) > a[i] ? sum + a[i] : a[i];
        max = sum > max ? sum : max;
    }  
    return max;  
}

leetcode 43 字符串相乘

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public String multiply(String num1, String num2) {
        int len1 = num1.length();
        int len2 = num2.length();
        int [] array = new int [len1 + len2];
        for(int i = len1 - 1; i >= 0; i-- ){
            for (int j = len2 - 1; j >= 0; j --) {
                int a = num1.charAt(i) - '0';
                int b = num2.charAt(j) - '0';
                int tmp = a * b;
                tmp += array[i+j+1];
                array[i+j] += tmp / 10;
                array[i+j+1] = tmp % 10;
            }
        }
        StringBuilder sb = new StringBuilder();
        for (int k = 0; k < array.length; k++)
            if (!(array[k] == 0 && sb.length() == 0))
            sb.append(array[k]);

        return sb.length() == 0 ? "0" : sb.toString();
    }
}

leetcode 46 全排列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        dfs (result, new ArrayList<Integer>() , nums, new boolean[nums.length] );
        return result;
    }
    
    private void dfs (List<List<Integer>> list, List<Integer> tmp, int[] nums, boolean[] used) {
        if (tmp.size() == nums.length) {
            list.add(new ArrayList<>(tmp));
            return;
        }
        for (int i = 0; i < nums.length; i ++ ) {
            if (used[i] == false) {
                used[i] = true;
                tmp.add(nums[i]);
                dfs(list, tmp, nums, used);
                tmp.remove(tmp.size() - 1);
                used[i] = false;
            }
        }
    }
}

leetcode 15 3Sum

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < nums.length - 2; i ++) {
            if (i > 0 && nums[i] == nums[i-1]) {
                continue;
            }
            int l = i + 1;
            int r = nums.length - 1;
            int sum = 0 - nums[i];
            
            while (l < r) {
                if (nums[l] + nums[r] == sum) {
                    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[l] + nums[r] < sum) l++;
                else if (nums[l] + nums[r] > sum) r--;
            }
        }
        return result;
    }
}

leetcode 33 Search in Rotated Sorted Array

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int search(int[] nums, int target) {
        if (nums.length == 0 || nums == null) 
            return -1;
        int l = 0; int r = nums.length-1;
        int f = nums[0];
        while(l <= r) {
            int mid = (l + r) /2 ;

            if (target == nums[mid])
                return mid;
            if (nums[mid] < f && target >= f) {r = mid-1;}
            else if (nums[mid] >= f && target < f) {l = mid +1;}
            else if (nums[mid] < target) {l = mid + 1;}
            else {r = mid - 1;}
            
        } 
        return -1;
    }
}

9月6号美团笔试第二题 区间统计

给定n，k，t 其中n是序列的长度，k是子序列的长度，t是频率，要求找出序列中满足条件的长度为k的连续子序列的长度，条件是子序列中某个数字出现的频率大于等于t，第一行输入nkt，第二行输入n个数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public static void main(String[] args) {
       Scanner sc=new Scanner(System.in);
       while(sc.hasNext()){
           int n=sc.nextInt();
           int k=sc.nextInt();
           int t=sc.nextInt();
           int N =100005;
           int[] cnt = new int[N];
           int[] a = new int[N];
           int ans = 0;
           int res = 0;
           for(int i = 0; i < n; ++ i) {
               a[i] = sc.nextInt();
               cnt[a[i]] ++;
               if(cnt[a[i]] == t) {
                   ans ++;
               }
               if (i >= k-1) {
               	if (ans > 0)
               		res ++;
               	cnt[a[i-k+1]]--;
               	if (cnt[a[i-k+1]] == t-1)
               		ans--;
               }
           }
           System.out.println(res);
       }
   }

扫描序列，保存每个元素出现的计数。同时保存大于等于t的计数出现的次数。对于每一个子序列（i-k+1，i）判断条件就是次数大于0就可以，每次前进一步更新两个计数并且判断这两个计数与t的关系从而更新次数。

9月6号美团笔试第一题 图的遍历

题目大意，一个图，N个点，N-1条边，要求遍历这个图，最短的步数是多少。

分析：其实N个点N-1条边是一个树，不会是有环的图。题目转变成了遍历一个树，就变成了从根节点出发，到每一个叶子节点，每条边走两遍，一来一回，只不过最深的那一条路径走一遍只去不回就是最短的步数。

2（N-1）-dep所以问题又退化成了找一个树的最大深度（高度）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
import java.util.*;

public class test {
	public static HashMap<Integer,ArrayList<Integer>> e;
	public static int ans;
	public static void dfs(int x, int dep) {//dep表示根节点走到x节点需要的步数
		ArrayList<Integer> list = e.get(x);
		for (Integer i : list) {
			if (!e.containsKey(i)) {
        //dep+1是到i节点的步数，i是叶子节点，其父节点是x
        //for循环内的每一个i是同一层节点，dep应该相同，都是传进来时的dep，不能写dep++
	  			ans = ans > dep+1? ans : dep+1;
	            continue;
	        }
            //i节点不是叶子节点，继续搜索
	        dfs(i, dep+1);
	    }
	}
	public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()){
            int n=sc.nextInt();
            HashMap<Integer,ArrayList<Integer>> map = new HashMap<>();
            for(int i = 1; i < n; ++ i) {
            	int x=sc.nextInt();
            	int y=sc.nextInt();
            	ArrayList<Integer> tmpx;
            	if (map.containsKey(x))
            		tmpx = map.get(x);
            	else
            		tmpx = new ArrayList<>();
            	tmpx.add(y);               			
            	map.put(x,tmpx);
            }
            e = map;
            ans = 0;
            dfs(1,0); 
            System.out.println(2*n-2-ans);
        }
    }
}

待优化，使用map写起来好费劲。

Leetcode 792 Number of Matching Subsequences

预处理S，保存每个字符出现的位置，然后依次寻找匹配字符时带匹配的字符可能出现的最小的位置。

比如上一个字符出现在5号，那么下一个字符出现位置必须大于5，就去对应的数组中找，没找到大于5的数就是不合格

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

class Solution {
    public int count;
    public List<List<Integer>> str;
    public int numMatchingSubseq(String S, String[] words) {
        str = new ArrayList<>();
        for (int i = 0; i < 128; i ++) {
            List<Integer> tmp = new ArrayList<>();
            str.add(tmp);
        }
        char[] ch = S.toCharArray();   
        for (int i = 0; i < S.length(); i ++) {
            str.get(ch[i]).add(i);
        }
        count = 0;
        for (int i = 0; i < words.legnth; i++) {
            if(isContain(word))
                count++;
        }
        return count;
    }
    public boolean isContain(String s) {
        char[] ch = s.toCharArray();
        int target = -1;
        for (char c : ch) {
            List<Integer> list = str.get(c);
            int index = halfSearch(list, target);
            if (index < 0)
                return false;
            target = list.get(index);
        }
        return true;
    }
    // 找到list中第一个比n大的数的角标，找不到返回-1
    public int halfSearch(List<Integer> list, int n) {
    	int l = 0; int r = list.size()-1;
        int res = r;
        if (r >= 0 && list.get(r) <= n)
            // 验证r，因为后面都是list.get(mid) > n，初始的r不会验证到
        	res = -1;
        int mid ;
        while (l <= r) { //小于等于可以保证每一个值都检测到
            mid = (l + r)/2;
            if (list.get(mid) <= n) {
                l = mid + 1;
            }
            if (list.get(mid) > n){
                res = mid;
                r = mid - 1;
            }
        }
        return res;
    }
}

collections.binatySearch(list,value)

Parameters:
list the list to be searched.
key the key to be searched for.
Returns:
the index of the search key, if it is contained in the list; otherwise, (-(insertion point) - 1). The insertion point is defined as the point at which the key would be inserted into the list: the index of the first element greater than the key, or list.size() if all elements in the list are less than the specified key. Note that this guarantees that the return value will be >= 0 if and only if the key is found.
Throws:
ClassCastException - if the list contains elements that are not mutually comparable (for example, strings and integers), or the search key is not mutually comparable with the elements of the list.

1
2
3
List<Integer> intList = Arrays.asList(1, 2, 18, 36, 89, 99);  
// -4
	System.out.println(Collections.binarySearch(intList, 33));

leetcode 4. Median of Two Sorted Arrays

使用二分法

第一个数组找到m1个元素范围0到n1，第二个数组找到m2=k-m1个元素 k是长度的中位数（n1+n2+1）/2

最后中位数在总长度下是第k个元素，Ck-1或者是Ck-1与Ck的和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int n1 = nums1.length;
        int n2 = nums2.length;
        if (n1 > n2) 
            return findMedianSortedArrays(nums2, nums1);
        int l = 0, r = n1, k = (n1 + n2 + 1) / 2;
        // k是元素个数，因此n1+n2为偶数，加不加一都一样，n1+n2为奇数，就需要加一，因此可以统一成（n1+n2+1）/ 2
        // l和r表示个数的范围，因此退出是l = r 就是m1 所以r 的初值就是n1
        while (l < r) {

            int mid1 = (l + r) / 2; //l<r 的时候，mid1 一定小与r，但是mid1可能等于l，因此下面更新时l一定是mid+1不然会死循环
            int mid2 = k - mid1;
            System.out.println("l="+l+"r="+r+"K="+k+"m1="+mid1+"m2="+mid2);  
            if (nums1[mid1] < nums2[mid2 - 1])
                l = mid1+1;
            else
                r = mid1;
        }
        int m1 = l, m2 = k - l;
        int c1 = Math.max(m1 <= 0 ? Integer.MIN_VALUE : nums1[m1 - 1], 
                          m2 <= 0 ? Integer.MIN_VALUE : nums2[m2 - 1]);
 
        if ((n1 + n2) % 2 == 1)
            return c1;    
        
        int c2 = Math.min(m1 >= n1 ? Integer.MAX_VALUE : nums1[m1], 
                          m2 >= n2 ? Integer.MAX_VALUE : nums2[m2]);
                System.out.println("Ans c1="+c1+"c2="+c2);  

                
        return (c1 + c2) * 0.5;
    }
}