【算法题】

给一个数组和一个距离k

在数组中是否存在距离k内相等的数

package pers.wmx.leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * Given an array of integers and an integer k,
 * find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and
 * the absolute difference between i and j is at most k.
 *
 * Example 1:s
 * Input: nums = [1,2,3,1], k = 3
 * Output: true
 *
 * Example 2:
 * Input: nums = [1,0,1,1], k = 1
 * Output: true
 *
 * Example 3:
 * Input: nums = [1,2,3,1,2,3], k = 2
 * Output: false
 *
 **/
public class LeetCode_219_ContainsDuplicateII {

    public boolean containsNearbyDuplicate(int[] nums, int k) {

        Map<Integer,Integer> record = new HashMap<>();
        for (int i = 0; i <nums.length ; i++) {
            if(!record.containsKey(nums[i])){
                record.put(nums[i],i);
            }else{
                Integer index = record.get(nums[i]);

                //计算相等 2 数的距离
                if(Math.abs(index-i) <= k){
                    return true;
                }else{
                    //覆盖
                    record.put(nums[i],i);
                }
            }
        }

        return false;
    }

}

变形一下

给定一个整数数组，判断数组中是否有两个不同的索引 i 和 j，使得 nums [i] 和 nums [j] 的差的绝对值最大为 t，并且 i 和 j 之间的差的绝对值最大为 ķ。

示例 1:

输入: nums = [1,2,3,1], k = 3, t = 0
输出: true
示例 2:

输入: nums = [1,0,1,1], k = 1, t = 2
输出: true
示例 3:

输入: nums = [1,5,9,1,5,9], k = 2, t = 3
输出: false

定义一个结构

class Elment{
    int index;
    int value;
    public Elment(int index,int value){
        this.index=index;
        this.value=value;
    }
}

 public boolean containsNearbyAlmostDuplicate1(int[] nums, int k, int t) {
        List<Elment> list = new ArrayList<Elment>();
        for(int i=0;i<nums.length;i++){
            Elment ele = new Elment(i,nums[i]);
            list.add(ele);
        }

        //按照value 排序
        Collections.sort(list,new Comparator<Elment>() {
            @Override
            public int compare(Elment o1, Elment o2) {
                long l = (long)o1.value - (long)o2.value;
                if(l == 0){
                    return 0;
                }
                else if(l<0){
                    return -1;
                }
                return 1;
            }
        });
        for(int i=0;i<list.size();i++){
            for(int j=i+1;j<list.size();j++){
                long l = (long)list.get(i).value - (long)list.get(j).value;
                if(Math.abs(l) <= t){
                    if(Math.abs(list.get(i).index-list.get(j).index) <= k){
                        return true;
                    }
                }else{
                    //由于list是按序的 不存在绝对值小于t的就直接break
                    break;
                }
            }
        }
        return false;
    }

【SQL 题】

某城市开了一家新的电影院，吸引了很多人过来看电影。该电影院特别注意用户体验，专门有个 LED显示板做电影推荐，上面公布着影评和相关电影描述。

作为该电影院的信息部主管，您需要编写一个 SQL查询，找出所有影片描述为非 boring (不无聊) 的并且 id 为奇数 的影片，结果请按等级 rating 排列。

例如，下表 cinema:

+———+———–+————–+———–+
| id | movie | description | rating |
+———+———–+————–+———–+
| 1 | War | great 3D | 8.9 |
| 2 | Science | fiction | 8.5 |
| 3 | irish | boring | 6.2 |
| 4 | Ice song | Fantacy | 8.6 |
| 5 | House card| Interesting| 9.1 |
+———+———–+————–+———–+
对于上面的例子，则正确的输出是为：

+———+———–+————–+———–+
| id | movie | description | rating |
+———+———–+————–+———–+
| 5 | House card| Interesting| 9.1 |
| 1 | War | great 3D | 8.9 |
+———+———–+————–+———–+

select *
from cinema
where id % 2 > 0
and description != 'boring'
order by rating desc

转载请注明：汪明鑫的个人博客 » 每周一练（11）