文章目錄
-
- 657. Robot Return to Origin
- 461. Hamming Distance
- 832. Flipping an Image
- 617. Merge Two Binary Trees
- 728. Self Dividing Numbers
- 561. Array Partition I
- 852. Peak Index in a Mountain Array
- 942. DI String Match
- 922. Sort Array By Parity II
657. Robot Return to Origin
給一個字元串，每個字元表示機器人的移動，其中U（上），D（下），L（左），R（右）
判斷機器人最後是否在原點
public boolean judgeCircle(String moves) {
int x = 0, y = 0;
for(char c: moves.toCharArray()){
if(c == 'U')y--;
else if(c == 'D')y++;
else if(c == 'L')x--;
else if(c == 'R')x++;
}
return x == 0 && y == 0;
}
461. Hamming Distance
Hamming距離，即為兩個數的二進制表示中的不同位的個數
例子:
1(0001),4(0100),第2位和第4位不同
5(0101), 3(0011),第2,3位不同
public int hammingDistance(int x, int y) {
int z = x ^ y;
int c = 0;
while(z != 0){
//if((z & 1) == 1) c++;可簡化為如下
c += z & 1;
z >>= 1;
}
return c;
}
832. Flipping an Image
水準翻轉圖像，然後反色。
給定一個矩陣，水準方向反轉，然後所有0和1互換。
public int[][] flipAndInvertImage(int[][] A) {
int len = A[0].length;
for(int[] row : A){
for(int i = 0; i <= len / 2; i++){
if(i == len / 2) {//到中間時，直接01互換
row[i] ^= 1;
break;
}
int t = row[i];//水準對稱位置的數交換，然後01互換
row[i] = row[len - i - 1] ^ 1;
row[len - i - 1] = t ^ 1;
}
}
return A;
}
617. Merge Two Binary Trees
合并兩個二叉樹
public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
TreeNode p = null;
//對各種情況分類讨論，一共四種
if(t1 == null && t2 == null){//此分類可不寫,與最後的return p;(其中p==null)合并了。
return null;
}else if(t1 == null && t2 != null) {
p = new TreeNode(t2.val);
p.left = mergeTrees(null, t2.left);
p.right = mergeTrees(null, t2.right);
}else if(t1 !=null && t2 == null) {
p = new TreeNode(t1.val);
p.left = mergeTrees(t1.left, null);
p.right = mergeTrees(t1.right, null);
}else if(t1 != null && t2 != null) {
p = new TreeNode(t1.val + t2.val);//累加目前節點值
p.left = mergeTrees(t1.left, t2.left);//遞歸合并左邊
p.right = mergeTrees(t1.right, t2.right);//遞歸合并右邊
}
return p;
}
728. Self Dividing Numbers
A self-dividing number is a number that is divisible by every digit it contains.
For example, 128 is a self-dividing number because
128 % 1 == 0 ,128 % 2 == 0, and 128 % 8 == 0
.
Also, a self-dividing number is not allowed to contain the digit zero.
Given a lower and upper number bound, output a list of every possible self dividing number, including the bounds if possible.
例如：
Input:
left = 1, right = 22
Output: [1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 15, 22]
public List<Integer> selfDividingNumbers(int left, int right) {
List<Integer> list = new ArrayList<>(right - left);//設定合理初始容量，防止經常擴容，影響性能
for(int i = left; i <= right; i++) {
int j = i;
boolean b = true;//記錄退出情況（正常退出（滿足條件）/特殊情況退出（不滿足條件））
while(j != 0) {
int k = j % 10;//取最後一位
if(k == 0 || i % k != 0) {//如果有0，或存在不能整除的數，退出循環
b = false;
break;
}
j /= 10;
}
if(b) list.add(i);//j==0正常退出循環的，就說明滿足條件
}
return list;
}
561. Array Partition I
Given an array of 2n integers, your task is to group these integers into n pairs of integer, say (a1, b1), (a2, b2), …, (an, bn) which makes sum of min(ai, bi) for all i from 1 to n as large as possible.
Input: [1,4,3,2]
Output: 4
Explanation: n is 2, and the maximum sum of pairs is 4 = min(1, 2) + min(3, 4).
Note:
- n is a positive integer, which is in the range of [1, 10000].
- All the integers in the array will be in the range of [-10000, 10000].
數組成對組合，每一對中較小的值進行求和，要想盡可能地大，那每一對中的較大值和較小值就不能差太大，是以要讓較小值盡可能接近較大值。正常思路，嘗試對數組排序，那相鄰兩個必然是相差最小的。隻需要取排序後的數組中下标為偶數的求和即可。
比如[1,4,3,2]=> [1,2,3,4]
min(1,2)+min(3,4) = 4 即為最大
public int arrayPairSum(int[] nums) {
Arrays.sort(nums);//排序
int sum = 0;
for(int i = 0; i < nums.length; i++){
if(i % 2 == 0) sum += nums[i];
}
return sum;
}
看了下其他解答，發現他們巧妙利用了Note提示的數組範圍和長度，直接用O(n)複雜度的桶排序。
public int arrayPairSum(int[] nums) {
int[] arr = new int[20001];//題目條件n [1,10000]則2n [2,20000]
for(int num : nums){//O(n)排序
arr[num + 10000]++;//因為給的數為[-10000,10000]，是以加10000防止越界
}
int sum = 0;
for(int i = 0, j = 0; i < 20001; i++){//j用來記錄目前數是第偶數還是奇數個。
int a = arr[i];
while(a-- > 0){//跳過a=0的位置
if(j++ % 2 == 0){//第偶數個才進行累加
sum += i - 10000;
}
}
}
return sum;
}
852. Peak Index in a Mountain Array
找到第一個山峰，也就是比兩邊都大的數的索引
[0, 2, 0] => 1
[0, 1, 2] => 2
[2, 1, 0] => 0
public int peakIndexInMountainArray(int[] A) {
for(int i = 0; i < A.length - 1; i++){
if(A[i] > A[i+1]){//比右邊大
if(i == 0) return 0;//如果是第一個直接傳回
if(A[i] > A[i-1]) {//比左邊大
return i;
}
}
if(i == A.length - 1 && A[i] > A[i-1) return i;//如果已經到了結尾,且比前一個數大，傳回
}
return -1;//未找到
}
官方給的最優答案，少了個邊界判斷(i < A.length - 1).感覺這個答案不太合理，比如a = [0,1,2,2],官方的結果是2,但a[2]=a[3]不符合題意。
public int peakIndexInMountainArray(int[] A) {
int i = 0;
while (i < A.length - 1 && A[i] < A[i+1]) i++;
return i;
}
942. DI String Match
Given a string S that only contains “I” (increase) or “D” (decrease), let
N = S.length
.
Return any permutation A of
[0, 1, ..., N]
such that for all
i = 0, ..., N-1
:
- If S[i] == “I”, then A[i] < A[i+1]
- If S[i] == “D”, then A[i] > A[i+1]
例1:
Input: “IDID”
Output: [0,4,1,3,2]
例2:
Input: “III”
Output: [0,1,2,3]
例3:
Input: “DDI”
Output: [3,2,0,1]
思路，先從數字上去看看規律，
例如
IDID => [0,4,1,3,2]
把字元和數字對應看，
第一個I => 0,第二個I => 1,發現從小到大遞增，
第一個D => 4,第二個D => 3,發現從大到小遞減
可以發現，和I對應的每個數都是從0遞增，和D對應的每個數，都是從N開始遞減
public int[] diStringMatch(String S) {
int N = S.length();
int[] r = new int[N + 1];//建立N+1長度數組，存放結果
int j = N, i = 0, k = 0;
for (char c : S.toCharArray()) {
if (c == 'I') {//如果為I第 k 個從 i 開始自增
//也可簡化為r[k++] = i++;
r[k] = i;
k++;
i++;
} else {//第 k 個從 j 開始遞減
r[k++] = j--;
}
}
//看了下答案，這裡可以直接寫成 r[N] = i; 因為隻剩下最後一個數，i和j其實已經相遇了。
if (S.charAt(N - 1) == 'I') {//因為循環隻有n-1次，根據最後一個字元确定變化趨勢，處理最後一個元素
r[N] = i;
} else {
r[N] = j;
}
return r;
}
922. Sort Array By Parity II
Given an array A of non-negative integers, half of the integers in A are odd, and half of the integers are even.
Sort the array so that whenever A[i] is odd, i is odd; and whenever A[i] is even, i is even.
You may return any answer array that satisfies this condition.
例：
Input: [4,2,5,7]
Output: [4,5,2,7]
Explanation: [4,7,2,5], [2,5,4,7], [2,7,4,5] would also have been accepted.
Note：
- 2 <= A.length <= 20000
- A.length % 2 == 0
- 0 <= A[i] <= 1000
奇數放到奇數下标，偶數放到偶數下标
public int[] sortArrayByParityII(int[] A) {
int[] R = new int[A.length];
for(int i = 0, j = 0, k = 0; i < A.length; i++){
if(A[i] % 2 == 0) {//偶數，放入偶下标位置
R[2 * j] = A[i];
j++;
}else {//奇數，放入奇下标位置
R[2 * k + 1] = A[i];
k++;
}
}
return R;
}
![241 Different Ways to Add Parentheses（C代碼版）[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)