【華為OD題庫-034】字符串化繁為簡-java

題目

給定一個輸入字符串,字符串只可能由英文字母(a ~ z、A ~ Z)和左右小括號()組成。當字符里存在小括號時,小括號是成對的,可以有一個或多個小括號對,小括號對不會嵌套,小括號對內可以包含1個或多個英文字母也可以不包含英文字母。當小括號對內包含多個英文字母時,這些字母之間是相互等效的關系,而且等效關系可以在不同的小括號對之間傳遞,即當存在a和b等效和存在b和c等效時,a和c 也等效,另外,同一個英文字母的大寫字和小寫字母也相互等效(即使它們分布在不同的括號對里)。
要對這個輸入字符串做簡化,輸出一個新的字符串,輸出字符串里只需保留輸入字符串里的沒有被小括號對包含的字符(按照輸入字符串里的字符順序),并將每個字符替換為在小括號對里包含的字典序最小的等效字符。如果簡化后的字符串為空,請輸出為"0"
示例:輸入字符串為"never(dont)live(run)up(f)()“,初始等效字符集合為(d,o,n,t,r,u,n),由于等效關系可以傳遞,因此最終等效字符集合為(d,n,o,r,t,u),將輸入字符串里的剩余部分按字典序最小的等效字符替換后得到"devedlivedp”
輸入描述
input string
輸入為1行,代表輸入字符串
輸出描述
output string
輸出為1行,代表輸出字符串
備注
輸入字符串的長度在1~100000之間
示例1:
輸入∶
()abd
輸出:
abd
說明:
輸入字符串里沒有被小括號包含的字符串為"abd",其中每個字符沒有等效字符,輸出為"abd"
示例2:
輸入∶
(abd)demand(fb)()for
輸出:
aemanaaor
說明:
等效字符集為(a,b,d, f),輸入字符串里沒有被小括號包含的字符串集合為demandfor”,將其中字符替換為字典序最小的等效字符后輸出為:“aemanaaor”
示例3:
輸入∶
happy(xyz)new(wxy)year(t)
輸出:
happwnewwear
說明:
等效字符集為(w,x,y,z),輸入字符串里沒有被小括號包含的字符串集合為"happynewyear”,將其中字符替換為字典序最小的等效字等后輸出為:“happwnewwear”

思路

比如輸入的字符串為:NeVeD(dont)Live(Drun)up(f)()
按照題意:
先提取小括號(括號內字符數大于1)里的字符:dontDrun,去重后為,dDontru。由于大小寫是等效的,所以這里如果轉為全小寫并去重排序后的結果為:dnortu。于是現在需要將原來字符串中的d,n,o,r,t,u,全部轉為d。得到字符串:deVedLivedp
但是當我們全轉為大寫時,將原來字符串中的d,n,o,r,t,u,全部轉為D,得到結果:DeVeDLiveDp
題目應該是對輸出字符串是忽略大小寫的,否則按照不同方式處理會得到不同的結果。
解題思路如下:

  1. 首先提取小括號內的字符放入set中去重,小括號內字符個數大于1時才放入set
  2. 將其他字符(非小括號內的字符)組成新字符串:newStr
  3. 對set中的字符按照字典序排序,并轉為字符數組:chars
  4. 對newStr中遍歷,當某個字符出現在chars中時,將它替換為chars[0]
  5. 最后輸出newStr即可

關鍵在于第1、2步,即將輸入字符串分離為括號內字符和括號外字符兩部分
我們可以使用棧stack來實現,使用sb(StringBuilder)存放括號外的字符,使用set存放括號內的字符,將輸入字符串轉為chars數組,遍歷chars:

  1. 如果stack為空時,說明沒有出現括號,直接把字符加入sb
  2. 如果stack不為空或者字符串為(時,說明已經出現了括號,或者第一次出現括號,直接把字符加入stack
  3. 如果遇到 ),代表一對括號結束,應該清除stack。并且還需要根據括號對中的字符數量判斷是否加入set中。怎么判斷數量?此時stack中的字符為:(、若干字符(stack.size-1),如果字符數量大于1,那么應該將stack中除最后一個(外的字符加入set。

最后考慮特殊情況,比如按照括號對分離后sb為空,直接輸出0,set為空,則直接輸出sb.toString()

題解

package hwod;import java.util.*;public class StringSimplifying {public static void main(String[] args) {Scanner sc = new Scanner(System.in);String str = sc.nextLine();System.out.println(stringSimplifying(str));}private static String stringSimplifying(String str) {Set<Character> set = new HashSet<>();//存儲括號內的字符StringBuilder sb = new StringBuilder();//存儲括號外的字符LinkedList<Character> queue = new LinkedList<>();for (int i = 0; i < str.length(); i++) {if (str.charAt(i) == ')') {if (queue.size() - 1 > 1) {while (queue.size() > 1) {set.add(Character.toLowerCase(queue.pollLast()));//大小寫等效,全轉為小寫}}queue.clear();continue;}if (str.charAt(i) == '(' || !queue.isEmpty()) {queue.addLast(str.charAt(i));continue;}sb.append(str.charAt(i));}if (sb.length() == 0) {return "0";}if (set.size() == 0) {return sb.toString();}ArrayList<Character> chars = new ArrayList<>(set);Collections.sort(chars);final char[] newChars = sb.toString().toCharArray();for (int i = 0; i < newChars.length; i++) {if (chars.contains(Character.toLowerCase(newChars[i]))) {newChars[i] = chars.get(0);}}return String.valueOf(newChars);}
}

推薦

如果你對本系列的其他題目感興趣,可以參考華為OD機試真題及題解(JAVA),查看當前專欄更新的所有題目。

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

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

相關文章

Jenkins Ansible 參數構建

首先在Jenkins中創建自由項目 在web端配置完成后在另一臺機子上下載nginx 在gitlab端創建項目并創建文件配置代碼 在有Jenkins的機器上下載Ansible [rootslave1 ~]# yum -y install epel-release [rootslave1 ~]# yum -y install ansible再進入下載nginx機器中克隆gitlab項目…

Android 框架層AIDL 添加接口

文章目錄 AIDL的原理構建AIDL的流程往凍結的AIDL中加接口 AIDL的原理 可以利用ALDL定義客戶端與服務均認可的編程接口&#xff0c;以便二者使用進程間通信 (IPC) 進行相互通信。在 Android 中&#xff0c;一個進程通常無法訪問另一個進程的內存。因此&#xff0c;為進行通信&a…

卷積神經網絡(AlexNet)鳥類識別

文章目錄 一、前言二、前期工作1. 設置GPU&#xff08;如果使用的是CPU可以忽略這步&#xff09;2. 導入數據3. 查看數據 二、數據預處理1. 加載數據2. 可視化數據3. 再次檢查數據4. 配置數據集 三、AlexNet (8層&#xff09;介紹四、構建AlexNet (8層&#xff09;網絡模型五、…

微信小程序image組件圖片設置最大寬度 寬高自適應

問題描述&#xff1a;在使用微信小程序image組件的時候&#xff0c;在不確定圖片寬高情況下 想給一個最大寬度讓圖片自適應&#xff0c;按比例&#xff0c;image的widthfiex和heightFiex并不能滿足&#xff08;只指定最大寬/高并不會生效&#xff09; 問題解決&#xff1a;使用…

居家適老化設計第二十九條---衛生間之花灑

無電源 燈光顯示 無障礙扶手型花灑 以上產品圖片均來源于淘寶 侵權聯系刪除 居家適老化衛生間的花灑通常具有以下特點和功能&#xff1a;1. 高度可調節&#xff1a;適老化衛生間花灑可通過調節高度&#xff0c;滿足不同身高的老年人使用需求&#xff0c;避免彎腰或過高伸展造…

【開源】基于Vue.js的固始鵝塊銷售系統

項目編號&#xff1a; S 060 &#xff0c;文末獲取源碼。 \color{red}{項目編號&#xff1a;S060&#xff0c;文末獲取源碼。} 項目編號&#xff1a;S060&#xff0c;文末獲取源碼。 目錄 一、摘要1.1 項目介紹1.2 項目錄屏 二、功能模塊2.1 數據中心模塊2.2 鵝塊類型模塊2.3 固…

qgis添加xyz柵格瓦片

方式1&#xff1a;手動一個個添加 左側瀏覽器-XYZ Tiles-右鍵-新建連接 例如添加高德瓦片地址 https://wprd01.is.autonavi.com/appmaptile?langzh_cn&size1&style7&x{x}&y{y}&z{z} 雙擊即可呈現 收集到的一些圖源&#xff0c;僅供參考&#xff0c;其中一…

【C++學習手札】模擬實現list

? &#x1f3ac;慕斯主頁&#xff1a;修仙—別有洞天 ??今日夜電波&#xff1a;リナリア—まるりとりゅうが 0:36━━━━━━?&#x1f49f;──────── 3:51 &#x1f504; ?? ? ??…

聊聊httpclient的staleConnectionCheckEnabled

序 本文主要研究一下httpclient的staleConnectionCheckEnabled staleConnectionCheckEnabled org/apache/http/client/config/RequestConfig.java public class RequestConfig implements Cloneable {public static final RequestConfig DEFAULT new Builder().build();pr…

【ARM 嵌入式 編譯 Makefile 系列 18 -- Makefile 中的 export 命令詳細介紹】

文章目錄 Makefile 中的 export 命令詳細介紹Makefile 使用 export導出與未導出變量的區別示例&#xff1a;導出變量以供子 Makefile 使用 Makefile 中的 export 命令詳細介紹 在 Makefile 中&#xff0c;export 命令用于將變量從 Makefile 導出到由 Makefile 啟動的子進程的環…

qgis添加wms服務

例如添加geoserver的wms服務 左右瀏覽器-WMS/WMTS-右鍵-新建連接 URL添加geoserver的wms地址 http://{ip}:{port}/geoserver/{workspace}/wms 展開wms目錄&#xff0c;雙擊相應圖層即可打開

Spark---基于Yarn模式提交任務

Yarn模式兩種提交任務方式 一、yarn-client提交任務方式 1、提交命令 ./spark-submit --master yarn --class org.apache.spark.examples.SparkPi ../examples/jars/spark-examples_2.11-2.3.1.jar 100 或者 ./spark-submit --master yarn–client --class org.apache.s…

三菱PLC應用[集錦]

三菱PLC應用[集錦] 如何判斷用PNP還是NPN的個人工作心得 10&#xff5e;30VDC接近開關與PLC連接時&#xff0c;如何判斷用PNP還是NPN的個人工作心得: 對于PLC的開關量輸入回路。我個人感覺日本三菱的要好得多&#xff0c;甚至比西門子等赫赫大名的PLC都要實用和可靠&#xff01…

vulnhub4

靶機地址: https://download.vulnhub.com/admx/AdmX_new.7z 信息收集 fscan 掃一下 ┌──(kali?kali)-[~/Desktop/Tools/fscan] └─$ ./fscan_amd64 -h 192.168.120.138 ___ _ / _ \ ___ ___ _ __ __ _ ___| | __ / /_\/____/ __|/ …

LeetCode | 622. 設計循環隊列

LeetCode | 622. 設計循環隊列 OJ鏈接 思路&#xff1a; 我們這里有一個思路&#xff1a; 插入數據&#xff0c;bank往后走 刪除數據&#xff0c;front往前走 再插入數據&#xff0c;就循環了 那上面這個方法可行嗎&#xff1f; 怎么判斷滿&#xff0c;怎么判斷空&#xff1…

模電知識點總結(二)二極管

系列文章目錄 文章目錄 系列文章目錄二極管二極管電路分析方法理想模型恒壓降模型折線模型小信號模型高頻/開關 二極管應用整流限幅/鉗位開關齊納二極管變容二極管肖特基二極管光電器件光電二極管發光二極管激光二極管太陽能電池 二極管 硅二極管&#xff1a;死區電壓&#xf…

今年注冊電氣工程師考試亂象及就業前景分析

1、注冊電氣工程師掛靠價格 # 2011年以前約為5萬一年&#xff0c;2011年開始強制實施注冊電氣執業制度&#xff0c;證書掛靠價格開始了飛漲&#xff0c;2013年達到巔峰&#xff0c;供配電15萬一年&#xff0c;發輸變電20-25萬一年&#xff0c;這哪里是證書&#xff0c;簡直就是…

Docker kill 命令

docker kill&#xff1a;殺死一個或多個正在運行的容器。 語法&#xff1a; docker kill [OPTIONS] CONTAINER [CONTAINER...]OPTIONS說明&#xff1a; -s&#xff1a;向容器發送一個信號 描述&#xff1a; docker kill子命令會殺死一個或多個容器。容器內的主進程被發送S…

C語言數組的距離(ZZULIOJ1200:數組的距離)

題目描述 已知元素從小到大排列的兩個數組x[]和y[]&#xff0c; 請寫出一個程序算出兩個數組彼此之間差的絕對值中最小的一個&#xff0c;這叫做數組的距離 。 輸入&#xff1a;第一行為兩個整數m, n(1≤m, n≤1000)&#xff0c;分別代表數組f[], g[]的長度。第二行有m個元素&a…

如何在Simulink中使用syms?換個思路解決報錯:Function ‘syms‘ not supported for code generation.

問題描述 在Simulink中的User defined function使用syms函數&#xff0c;報錯simulink無法使用外部函數。 具體來說&#xff1a; 我想在Predefined function定義如下符號函數作為輸入信號&#xff0c;在后續模塊傳入函數參數賦值&#xff0c;以實現一次定義多次使用&#xf…