前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Leetcode题解——849/950

Leetcode题解——849/950

作者头像
出其东门
发布2019-08-06 14:58:26
3380
发布2019-08-06 14:58:26
举报
文章被收录于专栏:01二进制

849. 到最近的人的最大距离

题目

https://leetcode-cn.com/problems/maximize-distance-to-closest-person/

题解

我们将有人的座位的下标记录到一个list中,剩下的事情就是要找一个点,距离list中某个元素的最大距离

以示例1为例,我们构造了一个list,为[0,4,6],那么你想找的那个点的下标一定是在0-4和4-6之间,所以只需要求出他们之间的中点距离即可。以示例2为例,我们构造了一个list,为[0],那么你想找的那个店的下标一定在0-seats.length之间,依次比较即可。

所以我们可以将此题抽象出来,假设有一个seats数组,为[a0,a1,a2.....an],其中有人的为i,j,k,那么我们要找的点就一定在0-i,i-j,j-k和k-seats.length之间,依次比较即可。

代码
代码语言:javascript
复制
public class Main {

    public static void main(String[] args) {
        Main main = new Main();
        int[] a = {1, 0, 0, 0, 1, 0, 1};
        System.out.println(main.maxDistToClosest(a));
    }

    public int maxDistToClosest(int[] seats) {
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < seats.length; i++) {
            if (seats[i] == 1)
                list.add(i);
        }
        int start = list.get(0);
        int end = seats.length - list.get(list.size() - 1) - 1;
        int max = Math.max(start, end);

        for (int i = 0; i < list.size() - 1; i++) {
            int temp = (list.get(i + 1) - list.get(i)) / 2;
            if (temp > max) max = temp;
        }

        return max;
    }
}

950. 按递增顺序显示卡牌

题目

https://leetcode-cn.com/problems/reveal-cards-in-increasing-order/

题解

提供一个新思路,以[17,13,11,2,3,5,7]为例,首先新建等长list=[1,2,3,4,5,6,7],然后对新的list按照题目的做法处理得到[1,3,5,7,4,2,6]。这时候注意[1,3,5,7,4,2,6]和[2,3,5,7,11,13,17]是一一对应的,因此我们构建对应关系[(1,2),(3,3),(5,5),(7,7),(4,11),(2,13),(6,17)] 最后按照元组的第一个元素排序得到的结果就是答案 [x1,x2,x3,x4,x5,x6,x7] -> [2,3,5,7,11,13,17] [1,2,3,4,5,6,7] -> [1,3,5,7,4,2,6] 从->右边得到对应关系,然后左边用这个对应关系就可以得到x1,x2,....x7

代码
代码语言:javascript
复制
public int[] deckRevealedIncreasing(int[] deck) {
    List<Integer> list = new ArrayList<>();
    for (int i = 0; i < deck.length; i++) {
        list.add(i + 1);
    }
    int len = list.size();
    boolean flag = true;
    for (int i = 0; i < list.size(); i++) {
        if (!flag) {
            int temp = list.get(i);
            list.remove(i);
            i--;
            list.add(temp);
            flag = true;
        } else {
            flag = false;
        }
    }
    Arrays.sort(deck);
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < len; i++) {
        map.put(list.get(i), deck[i]);
    }
    int[] result = new int[len];
    for (int i = 0; i < len; i++) {
        result[i] = map.get(i + 1);
    }
    return result;
}
本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2019-08-03,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 01二进制 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 849. 到最近的人的最大距离
    • 题目
      • 题解
        • 代码
        • 950. 按递增顺序显示卡牌
          • 题目
            • 题解
              • 代码
              领券
              问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档