算法刷题-O(1) 时间插入、删除和获取随机元素、汇总区间

时间：2023-02-07 11:18:29

O(1) 时间插入、删除和获取随机元素

设计一个支持在_平均 _时间复杂度 **O(1) 下， **执行以下操作的数据结构。 注意: 允许出现重复元素。

  1. insert(val)：向集合中插入元素 val。
  2. remove(val)：当 val 存在时，从集合中移除一个 val。
  3. getRandom：从现有集合中随机获取一个元素。每个元素被返回的概率应该与其在集合中的数量呈线性相关。

示例:

// 初始化一个空的集合。 
RandomizedCollection collection = new RandomizedCollection(); 
// 向集合中插入 1 。返回 true 表示集合不包含 1 。 
collection.insert(1); 
// 向集合中插入另一个 1 。返回 false 表示集合包含 1 。集合现在包含 [1,1] 。 
collection.insert(1); 
// 向集合中插入 2 ，返回 true 。集合现在包含 [1,1,2] 。 
collection.insert(2); 
// getRandom 应当有 2/3 的概率返回 1 ，1/3 的概率返回 2 。 
collection.getRandom(); 
// 从集合中删除 1 ，返回 true 。集合现在包含 [1,2] 。 
collection.remove(1); 
// getRandom 应有相同概率返回 1 和 2 。 
collection.getRandom();

答案：

class RandomizedCollection {
    private Map<Integer, Set<Integer>> map;
    private List<Integer> list;
    private Random random;
    private int size = 0;
    public RandomizedCollection() {
        map = new HashMap<>();
        list = new ArrayList<>();
        random = new Random();
    }
    public boolean insert(int val) {
        if (map.containsKey(val)) {
            Set<Integer> indexes = map.get(val);
            list.add(size, val);
            indexes.add(size);
            size++;
            return false;
        } else {
            Set<Integer> indexes = new HashSet<>();
            map.put(val, indexes);
            list.add(size, val);
            indexes.add(size);
            size++;
            return true;
        }
    }
    public boolean remove(int val) {
        if (!map.containsKey(val)) {
            return false;
        }
        Set<Integer> indexes = map.get(val);
        if (list.get(size - 1) == val) {
            indexes.remove(size - 1);
            size--;
        } else {
            Iterator<Integer> it = indexes.iterator();
            int index = it.next();
            it.remove();
            int last = list.get(size - 1);
            list.set(index, last);
            Set<Integer> set = map.get(last);
            set.remove(size - 1);
            set.add(index);
            size--;
        }
        if (indexes.size() == 0) {
            map.remove(val);
        }
        return true;
    }
    public int getRandom() {
        return list.get(random.nextInt(size));
    }
}
/**
 * Your RandomizedCollection object will be instantiated and called as such:
 * RandomizedCollection obj = new RandomizedCollection();
 * boolean param_1 = obj.insert(val);
 * boolean param_2 = obj.remove(val);
 * int param_3 = obj.getRandom();
 */

汇总区间

给定一个无重复元素的有序整数数组 nums 。 返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表。也就是说，nums 的每个元素都恰好被某个区间范围所覆盖，并且不存在属于某个范围但不属于 nums 的数字 x 。 列表中的每个区间范围 [a,b] 应该按如下格式输出：

  • "a->b" ，如果 a != b
  • "a" ，如果 a == b

示例 1： 输入：nums = [0,1,2,4,5,7] 输出：["0->2","4->5","7"] 解释：区间范围是： [0,2] --> "0->2" [4,5] --> "4->5" [7,7] --> "7" 示例 2： 输入：nums = [0,2,3,4,6,8,9] 输出：["0","2->4","6","8->9"] 解释：区间范围是： [0,0] --> "0" [2,4] --> "2->4" [6,6] --> "6" [8,9] --> "8->9" 示例 3： 输入：nums = [] 输出：[] 示例 4： 输入：nums = [-1] 输出：["-1"] 示例 5： 输入：nums = [0] 输出：["0"]

提示：

  • 0 <= nums.length <= 20
  • -231 <= nums[i] <= 231 - 1
  • nums 中的所有值都 互不相同
  • nums 按升序排列
class Solution {
    public List<String> summaryRanges(int[] nums) {
        List<String> list = new ArrayList<>();
        int pre = 0;
        int next = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i + 1 < nums.length && nums[i + 1] - nums[i] == 1) {
                next = i + 1;
            } else {
                if (next < i)
                    next = i;
                if (pre != next) {
                    list.add(nums[pre] + "->" + nums[next]);
                    pre = i + 1;
                }
                if (pre == next) {
                    list.add(nums[pre] + "");
                    pre = i + 1;
                }
            }
        }
        return list;
    }
}

改写字符串

键盘录入一个字符串，将字符串中的大写改成小写，小写改成大写，数字改成*。例如heLLO123,输出后为HEllo***

import java.util.Scanner;
public class Transfer {
    public static void main(String[] args) {
    String str = "";
    Scanner s = new Scanner(System.in);
    System.out.println("请输入您想输入的字符串：");
    str = s.next();
    StringBuffer sb = new StringBuffer();
    int i;
    for (i = 0; i <= str.length() - 1; i++) {
        char ch;
        if (str.charAt(i) >= 'a' && str.charAt(i) <= 'z') {
            ch = (char) (str.charAt(i) - 32); 
        } else if (str.charAt(i) >= 'A' && str.charAt(i) <= 'Z') {
            ch = (char) (str.charAt(i) + 32); 
        } else if (str.charAt(i) >= '0' && str.charAt(i) <= '9') {
            ch = '*'; 
        } else {
            ch = str.charAt(i); 
        }
        sb.append(ch); 
    }
    String trStr = sb.toString(); 
    System.out.println(sb.toString());
  }
}

本文内容到此结束了， 如有收获欢迎点赞????收藏????关注✔️，您的鼓励是我最大的动力。 如有错误❌疑问????欢迎各位大佬指出。 主页：共饮一杯无的博客汇总????‍????

保持热爱，奔赴下一场山海。????????????

标签：

相关文章