【Java數據結構】——五道算法題讓你靈活運用Map和Set

目錄

一.只出現一次的數字

二.寶石與石頭

三.舊鍵盤

四.給定一個數組,統計每個元素出現的次數

五.前K個高頻單詞


一.只出現一次的數字

136. 只出現一次的數字 - 力扣(LeetCode)

算法原理:我們將nums中每個元素都存入到set中去,但是存入是有條件的,如果不存在就加進去,如果已經存在了那么我們就就將那個值移除。然后循環結束后我們看到只剩下一個元素,然后我們再次遍歷這個數組,因為set中就包含了一個元素,那么如果遍歷后那個數存在在set中,那么就返回那個值,否則返回-1;

class Solution {public int singleNumber(int[] nums) {HashSet<Integer> set=new HashSet<>();for(int x:nums){if(!set.contains(x)){set.add(x);//不包含就增加}else{set.remove(x);//包含就刪除}}//集合中只有一個元素for(int x:nums){if(set.contains(x)){return x;}//然后遍歷,如果包含就返回x}return -1;//     TreeSet<Integer> set=new TreeSet<>();//     for(int x:nums){//         if(!set.contains(x)){//             set.add(x);//不包含就增加//         }else{//             set.remove(x);//包含就刪除//         }//     }//     //集合中只有一個元素//     for(int x:nums){//         if(set.contains(x)){//             return x;//         }//     }//     return -1;// }
}

二.寶石與石頭

771. 寶石與石頭 - 力扣(LeetCode)

算法原理:我們設定一個HashSet,然后先將寶石中的字符串各個字符都存入到set中去,然后繼續遍歷石頭字符串,如果石頭中的字符串在set中,那么就計數++

class Solution {public int numJewelsInStones(String jewels, String stones) {HashSet<Character>set=new HashSet<>();//先讓寶石里面的各個字符都放進hashset中for(char x:jewels.toCharArray()){set.add(x);}//ToCharArray( )的用法,將字符串對象中的字符轉換為一個字符數組。int sum=0;//然后遍歷石頭里的各個字符,判斷是否包含在set里面,如果包含就sum++for(char ch:stones.toCharArray()){if(set.contains(ch)){sum++;}}return sum;}
}

toCharArray是將字符串轉為字符數組。


三.舊鍵盤

舊鍵盤 (20)__牛客網 (nowcoder.com)

題目解析:

  • 我們輸入第一行 (鍵盤沒壞) ——7_This_is_a_test
  • 輸入第二行? ?(鍵盤壞了)—— _hs_s_a_es

我們看到壞掉的字符有? 7T i i t t 但是我們本題說明了,只輸出大寫,所以在第一行輸入的時候,t和T都是一樣的。而且題目也限制了,每個壞鍵只輸出一次。

倆個條件:1.每個壞鍵只輸出一次? ?2.只輸出大寫(說明在輸入第一行中,t和T都是一樣的)

算法原理:

我們用str1記錄第一行,用str2記錄第二行。我們先將str2遍歷一遍,將str2中每個元素都存入到set中,然后遍歷str2字符串,如果遇到不包含的元素,我們就輸出,但是如果后面遇到同樣 比如 上面的字符串7_This_is_a_test,中i出現了倆次,題目規定壞鍵只能輸出一次。所以這時候我們就再定義一個set2,倆個條件,那個元素既不包含str1,也不包含在str2中,我們才輸出,并且讓那個值加到set2中。

所以我們 看到倆個條件,每個壞鍵只能輸出一次,所以當前面已經出現的字符,我們就不能在輸出了,此時就需要在創建一個set2,還有一個條件就是 不區分大小寫,T和t都是同一個字母,所以哪個已經輸出了,那么t就不能輸出了,所以我們直接將倆個字符串的每個字符都弄成大寫。

import java.util.*;// 注意類名必須為 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的區別while (in.hasNextLine()) { // 注意 while 處理多個 caseString str1 = in.nextLine();String str2 = in.nextLine();func(str1,str2);}}private static void func(String str1,String str2){HashSet<Character> set1=new HashSet<>();for(char ch: str2.toUpperCase().toCharArray()){set1.add(ch);}//先將字符串2放入set中//然后再遍歷字符串1,如果字符串1中有元素不包含再字符串1和字符串2中,那么就輸出,并且將該字符加進set2中HashSet<Character> set2=new HashSet<>();//先轉大寫,然后轉字符數組for(char ch:str1.toUpperCase().toCharArray()){if(!set1.contains(ch) && !set2.contains(ch)){System.out.print(ch);set2.add(ch);}}}
}

我們需要先將字符串的每個元素轉成大寫,然后轉成字符數組。


四.給定一個數組,統計每個元素出現的次數

解題思路:

map中有個方法是get(),獲取key得到value,我們依次遍歷array數組,如果我們獲取到key,如果返回的value值是空,我們就put假如到map中,并計入key和value=1,如果value值不等于空,那么我們就先獲取當前key的value值,然后讓value值加1.

//給定一個數組,然后輸出每個元素出現的個數int[] array={1,2,3,3,1,4};HashMap<Integer,Integer>map=new HashMap<>();for(Integer x:array){if(map.get(x)==null){//如果x出現個數是null,那么我們就將value設置1map.put(x,1);}else{//如果3出現了1次之后,我們要先獲取3對應的個數,然后+1int value=map.get(x);map.put(x,value+1);}}for (Map.Entry<Integer,Integer>entry: map.entrySet()){System.out.println("key: "+entry.getKey()+"  value: "+entry.getValue());}

?然后Map中有個Entry<K,V>,調用entrySet()就能得到所有的key-value映射關系。


五.前K個高頻單詞

692. 前K個高頻單詞 - 力扣(LeetCode)

算法原理:

1.首先我們要記錄每個字符串出現的次數(請看第4題)

2.遍歷好統計的Map,把每組數據存儲到小根堆中

如果頻率相同,按字母比較(從小到大)——大根堆,頻率不同,按頻率高到低(從大到小)——小根堆。

//遍歷好統計的Map,把每組數據存儲到小根堆中PriorityQueue<Map.Entry<String,Integer>>minHeap =new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {@Overridepublic int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {//放元素的時候 如果頻率相同 我們轉變為大根堆-》按照單詞的字典序if(o1.getValue().compareTo(o2.getValue()) == 0) {return o2.getKey().compareTo(o1.getKey());}//放元素的時候 如果頻率不同 我們轉變為小根堆-》按照頻率大小排序return o1.getValue().compareTo(o2.getValue());}});//小根堆 o1在前o2在后  大根堆o1在后o2在前

因為我們要分情況 建大堆 還是建小堆。


然后遍歷Map,利用Map的entrySet(),找前k個出現單詞數最多的,你要找頻率最大單詞,如果堆的元素小于k,那么我們就直接將Map的鍵值對都offer進去,如果大于k,我們就要先獲取堆頂元素,然后判斷堆頂元素的value值是不是小于當前的entry的value,如果小于,那么就將堆頂刪除,然后讓offer當前的元素,如果大于,就繼續循環,如果堆頂的value等于entry的value(說明出現的頻率是相等的)那么,我們就要比較當前堆頂的key值和entry的key值是大于還是小于,如果大于,那么就要將當前的刪除,然后offer當前entry值。


class Solution {public List<String> topKFrequent(String[] words, int k) {//先統計每個單詞出現個數Map<String,Integer>map=new HashMap<>();for (String word:words) {if(map.get(word)==null){map.put(word,1);}else{int val=map.get(word);map.put(word,val+1);}}//遍歷好統計的Map,把每組數據存儲到小根堆中PriorityQueue<Map.Entry<String,Integer>>minHeap =new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {@Overridepublic int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {//放元素的時候 如果頻率相同 我們轉變為大根堆-》按照單詞的字典序if(o1.getValue().compareTo(o2.getValue()) == 0) {return o2.getKey().compareTo(o1.getKey());//大根堆}return o1.getValue().compareTo(o2.getValue());//小根堆}//小根堆 o1在前o2在后  大根堆o1在后o2在前});for (Map.Entry<String,Integer> entry:map.entrySet()) {if(minHeap.size()<k){//map里面的元素小于k,那么直接進堆就行了minHeap.offer(entry);}else {//你要找最大的頻率的單詞Map.Entry<String,Integer>top=minHeap.peek();//如果棧頂的元素個數小于現在的元素,那么就讓棧頂刪除,將他放入棧中//小根堆堆頂元素是最小的,如果比堆頂元素還小,那么就放入if(top.getValue().compareTo(entry.getValue())<0){minHeap.poll();minHeap.offer(entry);}else{//def->2  abc->2if(top.getValue().compareTo(entry.getValue())==0){//頻率相同,按字母順序if(top.getKey().compareTo(entry.getKey())>0){//getKey()得到key值minHeap.poll();minHeap.offer(entry);}}}}}//2 3 4List<String>ret=new ArrayList<>();for (int i = 0; i <k ; i++) {Map.Entry<String,Integer>top=minHeap.poll();ret.add(top.getKey());}//拿到的是 2 3 4,然后需要逆置Collections.reverse(ret);//Collections是逆置return ret;}
}

好好的生活,來又去,去又來。

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/news/717666.shtml
繁體地址,請注明出處:http://hk.pswp.cn/news/717666.shtml
英文地址,請注明出處:http://en.pswp.cn/news/717666.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

C/C++嵌入式開發環境搭建,Qt交叉編譯,cmake交叉編譯,clion/vscode遠程開發

目錄 交叉編譯簡介cmake 交叉編譯clion 交叉編譯vscode 遠程嵌入式開發Qt交叉編譯1.安裝交叉編譯工具2.交叉編譯qt庫3.將交叉編譯的Qt庫復制到板子上4.安裝和配置 Qt Creator&#xff0c;支持交叉編譯5.QT嵌入式開發6.QT嵌入式開發報錯解決QIconvCodec::convertToUnicode: usin…

ASUS華碩天選5筆記本電腦FX607JV原裝出廠Win11系統下載

ASUS TUF Gaming F16 FX607JV天選五原廠Windows11系統 適用型號&#xff1a; FX607JU、FX607JI、FX607JV、 FX607JIR、FX607JVR、FX607JUR 下載鏈接&#xff1a;https://pan.baidu.com/s/1l963wqxT0q1Idr98ACzynQ?pwd0d46 提取碼&#xff1a;0d46 原廠系統自帶所有驅動、…

TypeScript中 “ <> “ 語法 和 “ : “ 怎么使用

在 TypeScript 中&#xff0c;尖括號語法(<Type>)和as關鍵字(value as Type)都是用于類型斷言&#xff0c;而冒號(:)用于類型注解。這三種語法在不同的場景下使用&#xff1a; 尖括號語法和as關鍵字&#xff1a; 尖括號語法(<Type>value)&#xff1a; 這種語法在…

[LeetBook]【學習日記】鏈表反轉

來源于「Krahets」的《圖解算法數據結構》 https://leetcode.cn/leetbook/detail/illustration-of-algorithm/ 鏈表反轉的遞歸要點 遞歸終止條件為當前節點為空&#xff0c;表明遍歷到了鏈表尾部遞歸函數傳入參數為當前節點的下一個節點按照是否重新開辟存儲空間分類下面只寫…

python自動化學習--3.8python操作EXCEL文件python日志收集處理

1、Excel文件處理 安裝 openpxl 第三方庫 openpxl 模塊三大組件: 1、工作簿 &#xff08;包含多個sheet工作表&#xff09; 2、工作表 &#xff08;某個數據包含在某個工作表&#xff09; 3、單元格 1、創建excel工作簿 import openpyxl"""Excel表格的創建…

【簡說八股】Spring事務失效可能是哪些原因?

Spring事務介紹 Spring事務是指在Spring框架中對數據庫操作進行管理的一種機制&#xff0c;它確保一組數據庫操作要么完全執行成功&#xff08;提交&#xff09;&#xff0c;要么完全不執行&#xff08;回滾&#xff09;&#xff0c;從而保持數據一致性和完整性。 Spring框架…

GotoXy控制臺光標的位置更新

光標控制解釋 控制臺的光標更新方法, 用于控制數據輸出位置 void gotoXY(int x, int y)//新函數&#xff1a;更新光標 {COORD c;c.X x;c.Y y;SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE), c); }代碼解釋 這段代碼定義了一個名為 gotoXY 的函數&#xff0c;…

設計模式-裝飾者模式應用實踐

裝飾者模式&#xff08;Decorator Pattern&#xff09;是一種結構型設計模式&#xff0c;它允許動態地向一個現有的對象添加新的功能&#xff0c;同時不改變其結構。這種模式通過創建一個裝飾類來包裝原有的類&#xff0c;提供額外的行為。 下面是一個使用 Java 實現裝飾者模式…

【Spring Boot】實現全局異常處理

1.定義基礎異常接口類 /*** description: 服務接口類* author: MrVK* date: 2021/4/19 21:39*/ public interface BaseErrorInfoInterface {/*** 錯誤碼* return*/String getResultCode();/*** 錯誤描述* return*/String getResultMsg(); } 2.定義錯誤處理枚舉類 /*** desc…

小伙伴詢問AI該怎么學習?本人的一點總結,以思維導圖呈現

如有需要思維導圖的在后臺請留郵箱&#xff0c;相關知識結構目錄 部分導圖

nn.Linear() 使用提醒

原本以為它是和nn.Conv2d()一樣&#xff0c;就看第二個維度的數值&#xff0c;今天才知道&#xff0c;它是只看最后一個維度的數值&#xff01;&#xff01;&#xff01; 例子1 Descripttion: Result: Author: Philo Date: 2024-02-27 14:33:50 LastEditors: Philo LastEditT…

git使用merge命令把dev分支的mian.js文件和src下面的vuex文件夾以及config文件夾單獨合并到master分支上

使用 git merge 命令來單獨合并特定文件或文件夾到另一個分支通常不是最直接的方法&#xff0c;因為 merge 命令是用來合并兩個分支的所有更改的。然而&#xff0c;你可以通過 git cherry-pick 命令或者通過創建臨時補丁&#xff08;patch&#xff09;來實現這一點。 下面是一個…

秒殺的時候怎么使用Redis?

商品信息存儲&#xff1a;在Redis中存儲秒殺商品的庫存信息。可以使用Redis的Hash數據類型&#xff0c;將商品ID作為字段&#xff0c;庫存數量作為值存儲在Hash中。例如&#xff0c;HSET seckill_goods stock_1 100表示商品ID為stock_1的商品庫存數量為100。 秒殺訂單存儲&…

如何使用“Ubuntu 20.04桌面版,安裝MariaDB數據庫“?win10系統?

1、更新軟件包 sudo apt update 2、 安裝MariaDB服務器和客戶端 sudo apt install mariadb-server mariadb-client 3、 查看MeriaDB是否運行 service mysql status :q"退回命令行狀態 4、 設置MariaDB root用戶的密碼 sudo mysql_secure_installation 5、 MariaD…

斐波那契數列模型----三步問題

面試題 08.01. 三步問題 - 力扣&#xff08;LeetCode&#xff09; 1、狀態表示&#xff1a; 題目要求&#xff1a;上到n階臺階&#xff0c;有多少種方法。那么n逐漸簡化&#xff0c;上1階臺階有多少種方法&#xff1b;上2階臺階有多少種方法……直到上n階臺階有多少種方法。 …

c++ [[nodiscard]]關鍵字詳解

如果一個函數聲明了[[nodiscard]]&#xff0c;則該函數的返回值不能沒有承接&#xff0c;如果沒有承接&#xff0c;就會編譯報warning [[nodiscard]]是c17新特性&#xff0c;但本地用c11標準編譯也能編譯過&#xff0c;尚不清楚原因&#xff0c;c20加入了warning后的額外文字描…

代碼隨想錄第45天|● 70. 爬樓梯 (進階) ● 322. 零錢兌換 ● 279.完全平方數

文章目錄 ● 70. 爬樓梯 &#xff08;進階&#xff09;思路&#xff1a;- 排列 先value后weight代碼&#xff1a; ● 322. 零錢兌換思路&#xff1a;代碼 ● 279.完全平方數思路&#xff1a;代碼 ● 70. 爬樓梯 &#xff08;進階&#xff09; 思路&#xff1a;- 排列 先value后…

如何提升計算機性能

04 穿越功耗墻&#xff0c;我們該從哪些方面提升“性能”&#xff1f; 上一講&#xff0c;在講 CPU 的性能時&#xff0c;我們提到了這樣一個公式&#xff1a; 程序的 CPU 執行時間 指令數CPIClock Cycle Time 這么來看&#xff0c;如果要提升計算機的性能&#xff0c;我們可以…

zookeeper框架

事務ID Znode的創建刪除&#xff0c;更改內容等都是作為zookeeper的事務進行執行的。 對于每一個事務請求&#xff0c;zookeeper都會為其分配一個全局唯一的事務ID&#xff0c;從ID可以識別出事務的全局順序。 節點特性 czxid:create zxid,數據節點創建時的事務ID mzxid&…

基于ZYNQ的PCIE高速數據采集卡的設計(一)

作為信息處理的第一步&#xff0c;數據采集的作用越來越重要。目前&#xff0c;數據采集已經在航 空、民用、軍事、醫療等領域得到廣泛應用。隨著相關技術的不斷發展&#xff0c;信號頻率越 來高&#xff0c;帶寬越來越大&#xff0c;使得數據采集技術逐漸向高速大數據的方向…