藍橋杯刷題JAVA（3）

1. 移除元素

給你一個數組 nums 和一個值 val，你需要 原地 移除所有數值等于 val 的元素，并傳回移除後數組的新長度。

不要使用額外的數組空間，你必須僅使用 O(1) 額外空間并 原地 修改輸入數組。

元素的順序可以改變。你不需要考慮數組中超出新長度後面的元素。

class Solution {
    public int removeElement(int[] nums, int val) {
        if(nums.length == 0)
            return 0;
        if(nums.length == 1)
            if(nums[0] == val)
                return 0;
            else
                return 1;
        int length = 0;
        
        for(int index = 0; index < nums.length; index++)
            if(nums[index] != val)
                nums[length++] = nums[index];
        return length;
    }
}
           

經驗：

此處的length傳回與之前那題不同，需要思考後輸出。

2.實作strStr

實作 strStr() 函數。

給定一個 haystack 字元串和一個 needle 字元串，在 haystack 字元串中找出 needle 字元串出現的第一個位置 (從0開始)。如果不存在，則傳回 -1。

class Solution {
    public int strStr(String haystack, String needle) {
        return haystack.indexOf(needle);
    }
}
           

本意應當是KMP。。然而調内置函數就解決了。。

3.搜尋插入位置

給定一個排序數組和一個目标值，在數組中找到目标值，并傳回其索引。如果目标值不存在于數組中，傳回它将會被按順序插入的位置。

你可以假設數組中無重複元素。

class Solution {
    public int searchInsert(int[] nums, int target) {
        if(target < nums[0])
            return 0;
        for(int i = 0; i < nums.length; i++){
            if(target == nums[i])
                return i;
            if(target > nums[i] && i + 1 < nums.length && target < nums[i + 1])
                return i + 1;
        }
        return nums.length;
    }
}
           

經驗：

注意頭尾以及短路邏輯

4.外觀數列

class Solution {
    public String countAndSay(int n) {
        if(n == 1)
        	return "1";
        if(n == 2)
        	return "11";
        if(n == 3)
        	return "21";
        String  targetString = countAndSay(n - 1);
        String[] splitstringarray = new String[targetString.length() * 2];
        for(int i = 0; i < splitstringarray.length; i++)
        	splitstringarray[i] = new String();
        int count = 0;
        char flag = targetString.charAt(0);
        int flagindex = 0;
        for(int i = 0; i < targetString.length(); i++) {
        	if(flag != targetString.charAt(i) && i != targetString.length() - 1) {
        		splitstringarray[count++] = targetString.substring(flagindex, i);
        		flag = targetString.charAt(i);
        		flagindex = i;
        	}else if(flag != targetString.charAt(i) && i == targetString.length() - 1) {
        		splitstringarray[count++] = targetString.substring(flagindex, i);
        		splitstringarray[count++] = targetString.substring(i);
        	}
        	else if(flag == targetString.charAt(i) && i == targetString.length() - 1)
        		splitstringarray[count++] = targetString.substring(flagindex);
        	
        }
        
        String resultString = new String();
        for(int i = 0; i < count; i++) {
        	resultString = resultString.concat(String.valueOf(splitstringarray[i].length()));
        	resultString = resultString.concat(String.valueOf(splitstringarray[i].charAt(0)));
        }
        return resultString;
    }
}
           

經驗：

事實上不需要用splitstringarray來裝載最後再統計，直接在周遊的過程中就可以處理掉了，還會省略很多惡心的bug（譬如指針越界，溢出等問題），這樣子就可以沈略掉很多初始化的時候存在的bug了，尤其是nullpointerexception。

5.最大子序列和

給定一個整數數組 nums ，找到一個具有最大和的連續子數組（子數組最少包含一個元素），傳回其最大和。

class Solution {
    public int maxSubArray(int[] nums) {
    	int res = 0;
    	int max = -100001;
    	for(int i = 0; i < nums.length; i++) {
    		res += nums[i];
    		if(res > max)
    			max = res;
    		if(res < 0)
    			res = 0;
    	}
    	return max;
    }
}

class Solution(object):
	//DP，原數組上操作
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
         """
        for i in range(1, len(nums)):
            nums[i]= nums[i] + max(nums[i-1], 0)
        return max(nums)
           

經驗：

DP思想，負值不加入連續子序列即為0。

6.最後一個單詞

給你一個字元串 s，由若幹單詞組成，單詞之間用空格隔開。傳回字元串中最後一個單詞的長度。如果不存在最後一個單詞，請傳回 0 。

單詞 是指僅由字母組成、不包含任何空格字元的最大子字元串。

class Solution {
    public int lengthOfLastWord(String s) {
    	String[] splitStrings = s.split(" ");
    	if(splitStrings.length == 0)
    		return 0;
    	else 
			return splitStrings[splitStrings.length - 1].length();
    }
}

class Solution {
    public int lengthOfLastWord(String s) {
        int length = 0;
        for (int i = s.length() - 1; i >= 0; i--) {
            if (s.charAt(i) != ' ') {
                length++;
            } else if (length != 0) {
                return length;
            }
        }
        return length;
    }
}
           

經驗：

年輕的人還在倒序周遊找，直接split沖鋒完事兒。第二版本的代碼可以判斷尾部空格，比較巧妙

7.加一

給定一個由 整數 組成的 非空 數組所表示的非負整數，在該數的基礎上加一。

最高位數字存放在數組的首位， 數組中每個元素隻存儲單個數字。

你可以假設除了整數 0 之外，這個整數不會以零開頭。

class Solution {
    public int[] plusOne(int[] digits) {
    	if(digits.length == 1 && digits[0] != 9)
    		return new int[] {digits[0] + 1};
    	else if(digits.length == 1 && digits[0] == 9)
    		return new int[] {1, 0};
        int alert = 0;
    	int i = digits.length - 1;
    	digits[i] = (digits[i] + 1) % 10;
    	if(digits[i] == 0)
			alert = 1;
		else
			alert = 0;
    	i--;
    	while (alert > 0 && i >= 0) {
    		digits[i] = (digits[i] + alert) % 10;
        	if(digits[i] == 0) {
        		alert = 1;
        		i--;
        	}else
    			alert = 0;        	
		}
    	if(i < 0) {
    		int[] newarray = new int[digits.length + 1];
    		for(int ii = 1; ii < digits.length + 1; ii++)
    			newarray[ii] = digits[ii - 1];
    		newarray[0] = 1;
    		return newarray;
    	}else {
			return digits;
		}
    }
}
           

經驗：

自己的算法個位數易出錯，雖然時間和空間上效果可觀。

改進會明白這個alert是沒有意義的，因為如果不進位直接傳回結果即可，隻要循環周遊一直在執行就說明一定有進位産生，是以直接加1即可。