Weekly Contest 141

做了第一道后，看了下中間兩道題目，沒怎么看懂就先放著，做完最后一道，然后就沒時間了。

1089.?Duplicate Zeros

Given a fixed length?array?arr?of integers, duplicate each occurrence of zero, shifting the remaining elements to the right.

Note that elements beyond the length of the original array are not written.

Do the above modifications to the input array?in place, do not return anything from your function.

?

Example 1:

Input: [1,0,2,3,0,4,5,0]
Output: null
Explanation: After calling your function, the input array is modified to: [1,0,0,2,3,0,0,4]

Example 2:

Input: [1,2,3]
Output: null
Explanation: After calling your function, the input array is modified to: [1,2,3]

?

Note:

1. 1 <= arr.length <= 10000
2. 0 <= arr[i] <= 9

題目大意：給你一個數組，讓你改造這個數組，規則如下：1、數組長度不變。2、碰見0就將0重復一次，然后下一個數字往后移一位，查過長度的數字去掉。

解題思路：還是比較簡單的，只要看懂題目，按照題目規則我們可以先將數組保存下來，然后直接遍歷保存的數組，在原數組上直接修改。（應該還有不需要輔助數組的解法）

代碼：

class Solution {public void duplicateZeros(int[] arr) {int[] a = arr.clone();int len = arr.length;int j = 0;for(int i=0; i<len && j<len; i++) {if( a[i] == 0 ) arr[j++] = 0;if( j == len ) break;arr[j++] = a[i];}}
}

?

1092.?Shortest Common Supersequence

Given two strings?str1?and?str2,?return the shortest string that has both?str1?and?str2?as subsequences.??If multiple answers exist, you may return any of them.

(A string S is a subsequence of string T if deleting some number of characters from T (possibly 0, and the characters are chosen?anywherefrom T) results in the string S.)

?

Example 1:

Input: str1 = "abac", str2 = "cab"
Output: "cabac"
Explanation: 
str1 = "abac" is a substring of "cabac" because we can delete the first "c".
str2 = "cab" is a substring of "cabac" because we can delete the last "ac".
The answer provided is the shortest such string that satisfies these properties.

?

Note:

1. 1 <= str1.length, str2.length <= 1000
2. str1?and?str2?consist of lowercase English letters.

題目大意：題目很簡單，就是求最短公共父串。即給你兩個串str1和str2，讓你尋找一個最短字符串str既包含str1也包含str2。當然這個str可能會有多個，輸出其中一個就好。

解題思路：相當于是一個LCS變種吧。求出兩個串的LCS，然后將兩個串不在LCS中的字符在相應的LCS的“空隙”中輸出。

代碼：

    class Solution {public String shortestCommonSupersequence(String str1, String str2) {int m = str1.length();int n = str2.length();int dp[][] = new int[m + 1][n + 1];for (int i = 0; i <= m; i++) {for (int j = 0; j <= n; j++) {if (i == 0) {dp[i][j] = j;} else if (j == 0) {dp[i][j] = i;} else if (str1.charAt(i - 1) == str2.charAt(j - 1)) {dp[i][j] = 1 + dp[i - 1][j - 1];} else {dp[i][j] = 1 + Math.min(dp[i - 1][j], dp[i][j - 1]);}}}int index = dp[m][n];String str = "";int i = m, j = n;while (i > 0 && j > 0){if (str1.charAt(i - 1) == str2.charAt(j - 1)){str += (str1.charAt(i - 1));i--;j--;index--;}else if (dp[i - 1][j] > dp[i][j - 1]) {str += (str2.charAt(j - 1));j--;index--;} else {str += (str1.charAt(i - 1));i--;index--;}}while (i > 0) {str += (str1.charAt(i - 1));i--;index--;}while (j > 0) {str += (str2.charAt(j - 1));j--;index--;}str = reverse(str);return str;}String reverse(String input) {char[] temparray = input.toCharArray();int left, right = 0;right = temparray.length - 1;for (left = 0; left < right; left++, right--) {char temp = temparray[left];temparray[left] = temparray[right];temparray[right] = temp;}return String.valueOf(temparray);}}

?