java算法入門(mén)之有效的括號(hào)刪除有序數(shù)組中的重復(fù)項(xiàng)實(shí)現(xiàn)strStr
也許，我們永遠(yuǎn)都不會(huì)知道自己能走到何方，遇見(jiàn)何人，最后會(huì)變成什么樣的人，但一定要記住，能讓自己登高的，永遠(yuǎn)不是別人的肩膀，而是挑燈夜戰(zhàn)的自己，人生的道路剛剛啟程，當(dāng)你累了倦了也不要迷茫，回頭看一看，你早已不再是那個(gè)年少輕狂的少年。
1、LeetCode 20.有效的括號(hào)
題目
給定一個(gè)只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判斷字符串是否有效。
有效字符串需滿(mǎn)足：
左括號(hào)必須用相同類(lèi)型的右括號(hào)閉合。
左括號(hào)必須以正確的順序閉合。
小編菜解
public static boolean isValid(String s) {
if (s.length()%2 != 0) return false;
Map<Character,Character> hashMap = new HashMap<Character,Character>(){{
put(')','(');
put('}','{');
put(']','[');
}};
//"{[]}"
Queue<Character> queue = new LinkedList<Character>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if(hashMap.containsKey(c)){
char t = queue.peek();
System.out.println(t);//這個(gè)地方彈出的是{
char tt = hashMap.get(c);//而這個(gè)對(duì)應(yīng)的是],,上一處peek應(yīng)該取得[
System.out.println(tt);
System.out.println(queue.peek() != hashMap.get(c));
if (queue.isEmpty() || queue.peek() != hashMap.get(c)){
return false;
}
queue.poll();
}else{
queue.offer(c);
}
}
return queue.isEmpty();
}
思路及算法
判斷括號(hào)的有效性可以使用「?！惯@一數(shù)據(jù)結(jié)構(gòu)來(lái)解決。
當(dāng)我們遇到一個(gè)右括號(hào)時(shí)，我們需要將一個(gè)相同類(lèi)型的左括號(hào)閉合。此時(shí)，我們可以取出棧頂?shù)淖罄ㄌ?hào)并判斷它們是否是相同類(lèi)型的括號(hào)。如果不是相同的類(lèi)型，或者棧中并沒(méi)有左括號(hào)，那么字符串 ss 無(wú)效，返回 \text{False}False。為了快速判斷括號(hào)的類(lèi)型，我們可以使用哈希表存儲(chǔ)每一種括號(hào)。哈希表的鍵為右括號(hào)，值為相同類(lèi)型的左括號(hào)。
在遍歷結(jié)束后，如果棧中沒(méi)有左括號(hào)，說(shuō)明我們將字符串 ss 中的所有左括號(hào)閉合，返回True，否則返回False。
注意到有效字符串的長(zhǎng)度一定為偶數(shù)，因此如果字符串的長(zhǎng)度為奇數(shù)，我們可以直接返回False，省去后續(xù)的遍歷判斷過(guò)程。
大神解法
public static boolean isValid(String s){
int n = s.length();
if (n % 2 == 1) {
return false;
}
Map<Character, Character> pairs = new HashMap<Character, Character>() {{
put(')', '(');
put(']', '[');
put('}', '{');
}};
Deque<Character> stack = new LinkedList<Character>();
for (int i = 0; i < n; i++) {
char ch = s.charAt(i);
if (pairs.containsKey(ch)) {
if (stack.isEmpty() || stack.peek() != pairs.get(ch)) {
return false;
}
stack.pop();
} else {
stack.push(ch);
}
}
return stack.isEmpty();
}
思路和我的思路完全一致，就是我使用的是單向隊(duì)列，結(jié)果就是失敗，加油吧！
2、LeetCode 26.刪除有序數(shù)組中的重復(fù)項(xiàng)
題目
給你一個(gè)有序數(shù)組 nums ，請(qǐng)你 原地 刪除重復(fù)出現(xiàn)的元素，使每個(gè)元素 只出現(xiàn)一次 ，返回刪除后數(shù)組的新長(zhǎng)度。
不要使用額外的數(shù)組空間，你必須在 原地 修改輸入數(shù)組 并在使用 O(1) 額外空間的條件下完成。
說(shuō)明:
為什么返回?cái)?shù)值是整數(shù)，但輸出的答案是數(shù)組呢?
請(qǐng)注意，輸入數(shù)組是以「引用」方式傳遞的，這意味著在函數(shù)里修改輸入數(shù)組對(duì)于調(diào)用者是可見(jiàn)的。
小編菜解初版
public static Integer[] removeDuplicates(Integer[] nums) {
if(nums == null || nums.length == 0){
return nums;
}
List<Integer> tempList = Arrays.asList(nums);
for (int i = tempList.size() - 1; i >= 0; i--) {
Integer current = tempList.get(i);
if(i-1>0){
Integer next = tempList.get(i - 1);
if(next == current){
tempList.remove(current);
}
}
}
Integer[] ret = new Integer[tempList.size()];
tempList.toArray(ret);
return ret;
}
為什么為這樣呢？我記得list是可以remove的啊，百思不得其解，查一下源碼，猛然發(fā)現(xiàn)
Arrays的內(nèi)部類(lèi)ArrayList和java.util.ArrayList都是繼承AbstractList，remove、add等方法在AbstractList中是默認(rèn)throw UnsupportedOperationException而且不作任何操作。java.util.ArrayList重寫(xiě)這些方法而Arrays的內(nèi)部類(lèi)ArrayList沒(méi)有重寫(xiě)，所以會(huì)拋出異常。
小編菜解改進(jìn)版
public static Integer[] removeDuplicates(Integer[] nums) {
if(nums == null || nums.length == 0){
return nums;
}
List<Integer> tempList = Arrays.asList(nums);
List<Integer> list = new ArrayList<>(tempList);
for (int i = list.size() - 1; i >= 0; i--) {
Integer current = list.get(i);
if(i-1>0){
Integer next = list.get(i - 1);
if(next == current){
list.remove(current);
}
}
}
Integer[] ret = new Integer[list.size()];
list.toArray(ret);
return ret;
}
不報(bào)錯(cuò)了，結(jié)果也對(duì)，perfect！
思路及算法
相等的元素在數(shù)組中的下標(biāo)一定是連續(xù)的。利用數(shù)組有序的特點(diǎn)，可以通過(guò)雙指針的方法刪除重復(fù)元素。
大神解法
public static int removeDuplicates2(Integer[] nums) {
int n = nums.length;
if (n == 0) {
return 0;
}
int fast = 1, slow = 1;
while (fast < n) {
if (nums[fast] != nums[fast - 1]) {
nums[slow] = nums[fast];
++slow;
}
++fast;
}
return slow;
}
我去，無(wú)情。我的解法果然很菜，題意都沒(méi)讀懂，人家要的是長(zhǎng)度，你返回一個(gè)數(shù)組，作甚？？
3、LeetCode 28.實(shí)現(xiàn)strStr
題目
實(shí)現(xiàn) strStr() 函數(shù)。
給你兩個(gè)字符串 haystack 和 needle ，請(qǐng)你在 haystack 字符串中找出 needle 字符串出現(xiàn)的第一個(gè)位置（下標(biāo)從 0 開(kāi)始）。如果不存在，則返回 -1 。
說(shuō)明：
當(dāng) needle 是空字符串時(shí)，我們應(yīng)當(dāng)返回什么值呢？這是一個(gè)在面試中很好的問(wèn)題。
對(duì)于本題而言，當(dāng) needle 是空字符串時(shí)我們應(yīng)當(dāng)返回 0 。這與 C 語(yǔ)言的 strstr() 以及 Java 的 indexOf() 定義相符。
小編菜解
public static int strStr(String haystack, String needle) {
if(haystack == null || !haystack.contains(needle)){
return -1;
}
if(needle == ""){
return 0;
}
int strLg = haystack.length();
int findLg = needle.length();
for (int i = 0; i < strLg; i++) {
char c = haystack.charAt(i);
if (c == needle.charAt(0) && i+findLg <= strLg){
String temp = haystack.substring(i,i + findLg);
if (temp.equals(needle)){
return i;
}
}
}
return -1;
}
沒(méi)看出有什么問(wèn)題，可是提交總是提示解答錯(cuò)誤，也是無(wú)奈。
大神解法
public static int strStr(String haystack, String needle) {
int strLg = haystack.length();
int findLg = needle.length();
for (int i = 0; i+findLg <= strLg; i++) {
boolean flag = true;
for (int j = 0; j < findLg; j++) {
if (haystack.charAt(i+j)!=needle.charAt(j)){
flag = false;
break;
}
}
if (true == flag){
return i;
}
}
return -1;
}
感覺(jué)大神的解法還沒(méi)我的解法簡(jiǎn)單呢？可我的為何一直提交都是出錯(cuò)，哎，無(wú)奈。
到此這篇關(guān)于java算法入門(mén)之有效的括號(hào)刪除有序數(shù)組中的重復(fù)項(xiàng)實(shí)現(xiàn)strStr的文章就介紹到這了,更多相關(guān)Java算法strStr內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
SpringBoot啟動(dòng)器Starters使用及原理解析
這篇文章主要介紹了SpringBoot啟動(dòng)器Starters使用及原理解析,文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-04-04
springboot+nginx+https+linux實(shí)現(xiàn)負(fù)載均衡加域名訪問(wèn)簡(jiǎn)單測(cè)試
這篇文章主要介紹了springboot+nginx+https+linux實(shí)現(xiàn)負(fù)載均衡加域名訪問(wèn)簡(jiǎn)單測(cè)試，本文通過(guò)實(shí)例代碼給大家介紹的非常詳細(xì)，具有一定的參考借鑒價(jià)值 ,需要的朋友可以參考下2019-05-05
SPI的全稱(chēng)是服務(wù)提供接口，可以用其來(lái)啟動(dòng)框架的擴(kuò)展和替換組件。本文將利用SPI實(shí)現(xiàn)解耦，文中的示例代碼講解詳細(xì)，具有一定的借鑒價(jià)值，需要的可以參考一下2023-04-04
Java語(yǔ)言中flush()函數(shù)作用及使用方法詳解
這篇文章主要介紹了Java語(yǔ)言中flush函數(shù)作用及使用方法詳解，具有一定借鑒價(jià)值,需要的朋友可以參考下2018-01-01
Spring中異步注解@Async的使用、原理及使用時(shí)可能導(dǎo)致的問(wèn)題及解決方法
這篇文章主要介紹了Spring中異步注解@Async的使用、原理及使用時(shí)可能導(dǎo)致的問(wèn)題及解決方法,本文通過(guò)實(shí)例代碼給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2020-07-07
這篇文章主要介紹了RabbitMQ中的Channel和Exchange詳解,創(chuàng)建和銷(xiāo)毀TCP連接很耗時(shí),打開(kāi)太多TCP連接,耗操作系統(tǒng)資源,并發(fā)量大到一定程度,系統(tǒng)的吞吐量會(huì)降低,使用一個(gè)connection多channel的方式,可以提升連接的利用率,需要的朋友可以參考下2023-08-08
Java實(shí)現(xiàn)多選批量刪除功能(vue+Element)
這篇文章主要為大家詳細(xì)介紹了Java實(shí)現(xiàn)多選批量刪除功能，包括前端vue實(shí)現(xiàn)代碼文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-08-08
SpringBoot使用Apache Tika實(shí)現(xiàn)多種文檔的內(nèi)容解析
在日常開(kāi)發(fā)中,我們經(jīng)常需要解析不同類(lèi)型的文檔,如PDF、Word、Excel、HTML、TXT等,Apache Tika是一個(gè)強(qiáng)大的內(nèi)容解析工具,可以輕松地提取文檔中的內(nèi)容和元數(shù)據(jù)信息,本文將通過(guò)SpringBoot和Apache Tika的結(jié)合,介紹如何實(shí)現(xiàn)對(duì)多種文檔格式的內(nèi)容解析2024-12-12
Mybatis一對(duì)多查詢(xún)列表屬性處理示例詳解
使用MyBatis進(jìn)行多表聯(lián)查的關(guān)鍵是構(gòu)建數(shù)據(jù)庫(kù)中表的字段和java中對(duì)象的屬性的映射關(guān)系,下面這篇文章主要給大家介紹了關(guān)于Mybatis一對(duì)多查詢(xún)列表屬性處理的相關(guān)資料,需要的朋友可以參考下2023-05-05
Spring中allowedOriginPatterns和allowedOrigins方法有何不同詳解
這篇文章主要給大家介紹了關(guān)于Spring中allowedOriginPatterns和allowedOrigins方法有何不同,allowedOriginPatterns和allowedOrigins都是用來(lái)設(shè)置允許跨域請(qǐng)求的來(lái)源,需要的朋友可以參考下2023-10-10