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