子相似性 III

题目描述

一个句子是由一些单词与它们之间的单个空格组成，且句子的开头和结尾没有多余空格。比方说，“Hello World” ，“HELLO” ，“hello world hello world” 都是句子。每个单词都 只 包含大写和小写英文字母。

如果两个句子 sentence1 和 sentence2 ，可以通过往其中一个句子插入一个任意的句子（可以是空句子）而得到另一个句子，那么我们称这两个句子是 相似的 。比方说，sentence1 = “Hello my name is Jane” 且 sentence2 = “Hello Jane” ，我们可以往 sentence2 中 “Hello” 和 “Jane” 之间插入 “my name is” 得到 sentence1 。

给你两个句子 sentence1 和 sentence2 ，如果 sentence1 和 sentence2 是相似的，请你返回 true ，否则返回 false 。

样例

样例输入

sentence1 = “My name is Haley”, sentence2 = “My Haley”
sentence1 = “of”, sentence2 = “A lot of words”
sentence1 = “Eating right now”, sentence2 = “Eating”
sentence1 = “Luky”, sentence2 = “Lucccky”

样例输出

true 可以往 sentence2 中 “My” 和 “Haley” 之间插入 “name is” ，得到 sentence1 。
false 没法往这两个句子中的一个句子只插入一个句子就得到另一个句子。
true 可以往 sentence2 的结尾插入 “right now” 得到 sentence1 。
false

提示

• 1 <= sentence1.length, sentence2.length <= 100
• sentence1 和 sentence2 都只包含大小写英文字母和空格。
• sentence1 和 sentence2 中的单词都只由单个空格隔开。

思路

审题还是不够细致，进入了很多误区，最后看的题解，有了点思路，然后码出了程序。

代码实现

class Solution {
    public boolean areSentencesSimilar(String sentence1, String sentence2) {
        String[] s1 = sentence1.split(" ");
        String[] s2 = sentence2.split(" ");
        int i = 0, j = 0;
        while(i < s1.length && i < s2.length && s1[i].equals(s2[i])) i++;
        while(j < s1.length && j < s2.length && s1[s1.length-j-1].equals(s2[s2.length-j-1])) j++;
        return i + j >= Math.min(s1.length, s2.length);
    }
}

极大极小游戏

题目描述

给你一个下标从 0 开始的整数数组 nums ，其长度是 2 的幂。

对 nums 执行下述算法：

设 n 等于 nums 的长度，如果 n == 1 ，终止 算法过程。否则，创建 一个新的整数数组 newNums ，新数组长度为 n / 2 ，下标从 0 开始。
对于满足 0 <= i < n / 2 的每个 偶数 下标 i ，将 newNums[i] 赋值 为 min(nums[2 * i], nums[2 * i + 1]) 。
对于满足 0 <= i < n / 2 的每个 奇数 下标 i ，将 newNums[i] 赋值 为 max(nums[2 * i], nums[2 * i + 1]) 。
用 newNums 替换 nums 。
从步骤 1 开始 重复 整个过程。
执行算法后，返回 nums 中剩下的那个数字。

样例

样例输入

nums = [1,3,5,2,4,8,2,2]

样例输出

1
重复执行算法会得到下述数组。
第一轮：nums = [1,5,4,2]
第二轮：nums = [1,4]
第三轮：nums = [1]
1 是最后剩下的那个数字，返回 1 。

提示

• 1<= nums.length <= 1024
• $1<=nums[i]<=10^9$
• nums.length 是 2 的幂

思路

题目描述没看，直接看的图片和解释。
应该很浅显易懂，很容易想到递归实现。且实现方式有点类似线段树，线段树的模版记得还是很清楚。

代码实现

class Solution {
    int[] arr;
    public int minMaxGame(int[] nums) {
        int len =  nums.length;
        arr = nums;
        return recursion(0, len-1, false);
    }

    private int recursion(int l, int r, boolean judge){
        if(l == r) return arr[l];
        int left = recursion(l, (l+r)/2, false);
        int right = recursion(((l+r)>>1)+1, r, true);
        return judge ? Math.max(left, right) : Math.min(left, right);
    }
}