数据结构与算法之RandomPool结构和岛问题

青旅半醒 2021-12-19 14:43 131阅读 0赞

# 数据结构与算法之RandomPool结构和岛问题 #

--------------------

## 目录 ##

1.  RandomPool结构
2.  岛问题

--------------------

### 1. RandomPool结构  ###

###### （一）题目概述 ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70]

###### （二）思路分析 ######

1.  完成上述功能需要创建两个hashmap结构  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 1]
2.  insert操作：直接往里面添加数据即可。
3.  getRandom操作：因为知道hashmap里size个数，所以可以根据size得到随机值，取出即可
4.  delete操作：因为删除一个元素后会产生一个空位，所以可以在取出后用最后一个元素添上空位，size减1。

###### （三）代码实现 ######

import java.util.HashMap;
    
    public class Code_02_RandomPool {
        
    
    	public static class Pool<K> {
        
    		private HashMap<K, Integer> keyIndexMap;
    		private HashMap<Integer, K> indexKeyMap;
    		private int size;
    
    		public Pool() {
        
    			this.keyIndexMap = new HashMap<K, Integer>();
    			this.indexKeyMap = new HashMap<Integer, K>();
    			this.size = 0;
    		}
    
    		public void insert(K key) {
        
    			if (!this.keyIndexMap.containsKey(key)) {
        
    				this.keyIndexMap.put(key, this.size);
    				this.indexKeyMap.put(this.size++, key);
    			}
    		}
    
    		public void delete(K key) {
        
    			if (this.keyIndexMap.containsKey(key)) {
        
    				int deleteIndex = this.keyIndexMap.get(key);
    				int lastIndex = --this.size;
    				K lastKey = this.indexKeyMap.get(lastIndex);
    				this.keyIndexMap.put(lastKey, deleteIndex);
    				this.indexKeyMap.put(deleteIndex, lastKey);
    				this.keyIndexMap.remove(key);
    				this.indexKeyMap.remove(lastIndex);
    			}
    		}
    
    		public K getRandom() {
        
    			if (this.size == 0) {
        
    				return null;
    			}
    			int randomIndex = (int) (Math.random() * this.size); // 0 ~ size -1
    			return this.indexKeyMap.get(randomIndex);
    		}
    
    	}
    
    	public static void main(String[] args) {
        
    		Pool<String> pool = new Pool<String>();
    		pool.insert("nu");
    		pool.insert("li");
    		pool.insert("a");
    		System.out.println(pool.getRandom());
    		System.out.println(pool.getRandom());
    		System.out.println(pool.getRandom());
    		System.out.println(pool.getRandom());
    		System.out.println(pool.getRandom());
    		System.out.println(pool.getRandom());
    
    	}
    
    }

--------------------

### 2. 岛问题  ###

###### （一）题目概述 ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 2]

###### （二）思路 ######

1.  判断二维数组的合理性，不合理返回null。遍历N,M获取二维数组长宽，和创建一个变量记录岛的数量
2.  遍历每一个元素，如果元素为1，res++，进入感染函数
3.  将元素1的位置赋值为2，然后递归它的上下左右。

###### （三）代码实现 ######

public class Code_03_Islands {
        
    
    	public static int countIslands(int[][] m) {
        
    		if (m == null || m[0] == null) {
        
    			return 0;
    		}
    		int N = m.length;
    		int M = m[0].length;
    		int res = 0;
    		for (int i = 0; i < N; i++) {
        
    			for (int j = 0; j < M; j++) {
        
    				if (m[i][j] == 1) {
        
    					res++;
    					infect(m, i, j, N, M);
    				}
    			}
    		}
    		return res;
    	}
    
    	public static void infect(int[][] m, int i, int j, int N, int M) {
        
    		if (i < 0 || i >= N || j < 0 || j >= M || m[i][j] != 1) {
        
    			return;
    		}
    		m[i][j] = 2;
    		infect(m, i + 1, j, N, M);
    		infect(m, i - 1, j, N, M);
    		infect(m, i, j + 1, N, M);
    		infect(m, i, j - 1, N, M);
    	}
    
    	public static void main(String[] args) {
        
    		int[][] m1 = {
          {
         0, 0, 0, 0, 0, 0, 0, 0, 0 }, 
    				        {
         0, 1, 1, 1, 0, 1, 1, 1, 0 }, 
    				        {
         0, 1, 1, 1, 0, 0, 0, 1, 0 },
    				        {
         0, 1, 1, 0, 0, 0, 0, 0, 0 }, 
    				        {
         0, 0, 0, 0, 0, 1, 1, 0, 0 }, 
    				        {
         0, 0, 0, 0, 1, 1, 1, 0, 0 },
    				        {
         0, 0, 0, 0, 0, 0, 0, 0, 0 }, };
    		System.out.println(countIslands(m1));
    
    		int[][] m2 = {
          {
         0, 0, 0, 0, 0, 0, 0, 0, 0 }, 
    						{
         0, 1, 1, 1, 1, 1, 1, 1, 0 }, 
    						{
         0, 1, 1, 1, 0, 0, 0, 1, 0 },
    						{
         0, 1, 1, 0, 0, 0, 1, 1, 0 }, 
    						{
         0, 0, 0, 0, 0, 1, 1, 0, 0 }, 
    						{
         0, 0, 0, 0, 1, 1, 1, 0, 0 },
    						{
         0, 0, 0, 0, 0, 0, 0, 0, 0 }, };
    		System.out.println(countIslands(m2));
    
    	}
    
    }

编译结果：  
![在这里插入图片描述][20190630215233529.png]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70]: /images/20211219/6ec809b686c24acab88381fb3f281497.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 1]: /images/20211219/bc7c05977c9e402fa0550dbc5ce758f9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 2]: /images/20211219/5abb64aca1294a3fbae128934c3985ff.png
[20190630215233529.png]: /images/20211219/a6d1b777a85d48b792bbf1b80b0e9ab3.png