发表于 | 分类于

In MATLAB, there is a very useful function called ‘reshape’, which can reshape a matrix into a new one with different size but keep its original data.

You’re given a matrix represented by a two-dimensional array, and two positive integers r and c representing the row number and column number of the wanted reshaped matrix, respectively.

The reshaped matrix need to be filled with all the elements of the original matrix in the same row-traversing order as they were.

If the ‘reshape’ operation with given parameters is possible and legal, output the new reshaped matrix; Otherwise, output the original matrix.

Example 1:

1
2
3
4
5
6
7
8
9
Input: 
nums = 
[[1,2],
 [3,4]]
r = 1, c = 4
Output: 
[[1,2,3,4]]
Explanation:
The row-traversing of nums is [1,2,3,4]. The new reshaped matrix is a 1 * 4 matrix, fill it row by row by using the previous list.

Example 2:

1
2
3
4
5
6
7
8
9
10
Input: 
nums = 
[[1,2],
 [3,4]]
r = 2, c = 4
Output: 
[[1,2],
 [3,4]]
Explanation:
There is no way to reshape a 2 * 2 matrix to a 2 * 4 matrix. So output the original matrix.

Note:
The height and width of the given matrix is in range [1, 100].
The given r and c are all positive.
Show Company Tags
Show Tags

解法1：O(MN)

主要就是掌握一个二维数组的index对应的行列的求法。
Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public class Solution {
    public int[][] matrixReshape(int[][] nums, int r, int c) {
        
        if (nums == null || nums[0] == null) {
            return null;
        }
        
        int row = nums.length;
        int col = nums[0].length;
        
        // check for dimension match
        if (row * col != r * c) {
            return nums;
        }
        
        int[][] res = new int[r][c];
        for (int i = 0; i < r; ++i) {
            for (int j = 0; j < c; ++j) {
                // calculate the original index
                int index = i * c + j;
                res[i][j] = nums[index / col][index % col];
            }
        }
        
        return res;
    }
}

发表于 | 分类于

Given an integer array, you need to find one continuous subarray that if you only sort this subarray in ascending order, then the whole array will be sorted in ascending order, too.

You need to find the shortest such subarray and output its length.

Example 1:
Input: [2, 6, 4, 8, 10, 9, 15]
Output: 5
Explanation: You need to sort [6, 4, 8, 10, 9] in ascending order to make the whole array sorted in ascending order.
Note:
Then length of the input array is in range [1, 10,000].
The input array may contain duplicates, so ascending order here means <=.

解法1：O(NlogN)

这题的思路是从一个sorted过的array出发，然后再用两个指针从两端往里面找和sorted之后的结果不一样的位置。
Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int[] sorted = nums.clone();
        Arrays.sort(sorted);
        // two pointers from left and from right
        int len = 0;
        for (int i = 0; i < nums.length; ++i) {
            if (nums[i] == sorted[i]) {
                len++;
            } else {
                break;
            }
        }
        for (int i = nums.length - 1; i >= 0; --i) {
            if (nums[i] == sorted[i]) {
                len++;
            } else {
                break;
            }
        }
        return Math.max(0, nums.length - len);
    }
}

解法2：O(N)

这个解法是从discuss里看来的，照搬他的解释：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
It turns out that the two boundary indices i and j can be found in linear time, if we take advantage of the following three properties:
nums[0, i - 1] and nums[j + 1, n - 1] are both sorted.
nums[i] != nums_sorted[i] and nums[j] != nums_sorted[j].
nums[i - 1] <= min and max <= nums[j + 1], where min and max are the minimum and maximum values of subarray nums[i, j].
The first and third properties guarantee that the subarray nums[0, i - 1] will be exactly the same as subarray nums_sorted[0, i - 1], and the subarray nums[j + 1, n - 1] exactly the same as nums_sorted[j + 1, n - 1], while the second property ensures that i will be the first index at which the two elements of nums and nums_sorted are different and j be the last such index.
Since we aim at the shortest subarrays, from the first property alone, we need to find the two longest sorted subarrays starting at index 0 and ending at index n - 1, respectively. Assume the two subarrays are nums[0, l] and nums[r, n - 1]. If there is overlapping between these two subarrays, i.e.l >= r, then the whole array is sorted so 0 will be returned. Otherwise, the input array is not sorted. However, we cannot say sorting nums[l, r] will leave the whole array sorted, because at this moment the third property may not be satisfied.
To guarantee the third property, assume min and max are the minimum and maximum values of subarray nums[l, r], then we need to decrease l as long as nums[l] > min, and increase r as long as nums[r] < max. After this is done, it can be shown that the second property will be met automatically, and nums[l + 1, r - 1] will be the shortest subarray we are looking for (that is, i = l + 1 and j = r - 1).
Finding the longest subarrays and the maximum and minimum values of the middle subarray takes one-pass. Ensuring the third property requires a second pass. Therefore we have this two-pass solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int findUnsortedSubarray(int[] nums) {
    int l = 0, r = nums.length - 1, max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
    while (l < r && nums[l] <= nums[l + 1]) l++;
    if (l >= r) return 0;
    while (nums[r] >= nums[r - 1]) r--;
    for (int k = l; k <= r; k++) {
        max = Math.max(max, nums[k]);
        min = Math.min(min, nums[k]);
    }
    while (l >= 0 && min < nums[l]) l--;
    while (r < nums.length && nums[r] < max) r++;
    return (r - l - 1);
}

发表于 | 分类于

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.

Example 1:

1
2
3
4
Input: [1,4,3,2]
Output: 4
Explanation: n is 2, and the maximum sum of pairs is 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：

这题其实是一个数学题，先排序之后每两个组成一组的话选出的最小值的和是最大的。
Java

1
2
3
4
5
6
7
8
9
10
11
12
public class Solution {
    public int arrayPairSum(int[] nums) {
        Arrays.sort(nums);
        
        int sum = 0;
        for (int i = 0; i <nums.length; i = i + 2) {
            sum += nums[i];
        }
        
        return sum;
    }
}

发表于 | 分类于

Suppose you have a long flowerbed in which some of the plots are planted and some are not. However, flowers cannot be planted in adjacent plots - they would compete for water and both would die.

Given a flowerbed (represented as an array containing 0 and 1, where 0 means empty and 1 means not empty), and a number n, return if n new flowers can be planted in it without violating the no-adjacent-flowers rule.

Example 1:

1
2
Input: flowerbed = [1,0,0,0,1], n = 1
Output: True

Example 2:

1
2
Input: flowerbed = [1,0,0,0,1], n = 2
Output: False

Note:
The input array won’t violate no-adjacent-flowers rule.
The input array size is in the range of [1, 20000].
n is a non-negative integer which won’t exceed the input array size.

解法1：

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public class Solution {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        
        if (flowerbed == null || flowerbed.length == 0) {
            return false;
        }        
        
        // traverse from left to right
        int i = 0;
        int size = flowerbed.length;
        
        while (n > 0) {
            if (i < size && flowerbed[i] == 1) {
                i += 2;
            } else if (i >= size) {
                break;
            } else {
                // check left & right 
                if ((i == 0 || flowerbed[i - 1] == 0) && (i == size - 1 || flowerbed[i + 1] == 0)) {
                    flowerbed[i] = 1;
                    n--;
                    i += 2;
                } else {
                    i += 1;
                }
            }
        }
        
        return n == 0;
    }
}

发表于 | 分类于

Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.

For example,
Given n = 3,

You should return the following matrix:

1
2
3
4
5
[
 [ 1, 2, 3 ],
 [ 8, 9, 4 ],
 [ 7, 6, 5 ]
]

解法1：

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public class Solution {
    public int[][] generateMatrix(int n) {
        int level = (n + 1) / 2;
        int[][] res = new int[n][n];
        // fill by level
        
        int num = 1;
        for (int i = 0; i < level; ++i) {
            int lastrow = n - i - 1;
            int lastcol = n - i - 1;
            
            // move right
            for (int j = i; j <= lastcol; ++j) {
                res[i][j] = num;
                num++;
            }
            
            // move down
            for (int j = i + 1; j <= lastrow; ++j) {
                res[j][lastcol] = num;
                num++;
            }
            
            // move left
            for (int j = lastcol - 1; j >= i; --j) {
                res[lastrow][j] = num;
                num++;
            }
            
            // move up
            for (int j = lastrow - 1; j > i; --j) {
                res[j][i] = num;
                num++;
            }
        }
        
        return res;
    }
}

发表于 | 分类于

Given a string, sort it in decreasing order based on the frequency of characters.

Example 1:

1
2
3
4
5
6
7
8
9
Input:
"tree"
Output:
"eert"
Explanation:
'e' appears twice while 'r' and 't' both appear once.
So 'e' must appear before both 'r' and 't'. Therefore "eetr" is also a valid answer.

Example 2:

1
2
3
4
5
6
7
8
9
Input:
"cccaaa"
Output:
"cccaaa"
Explanation:
Both 'c' and 'a' appear three times, so "aaaccc" is also a valid answer.
Note that "cacaca" is incorrect, as the same characters must be together.

Example 3:

1
2
3
4
5
6
7
8
9
Input:
"Aabb"
Output:
"bbAa"
Explanation:
"bbaA" is also a valid answer, but "Aabb" is incorrect.
Note that 'A' and 'a' are treated as two different characters.

解法1：

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class Solution {
    public String frequencySort(String s) {
        Map<Character, Integer> map = new HashMap<Character,Integer>();
        for (char c: s.toCharArray()) {
            map.put(c, map.getOrDefault(c,0) + 1);
        }
        
        List<Map.Entry<Character, Integer>> list = new ArrayList<>(map.entrySet());
        Comparator<Map.Entry<Character,Integer>> comparator = new Comparator<Map.Entry<Character, Integer>>() {
            public int compare(Map.Entry<Character, Integer> left, Map.Entry<Character, Integer> right) {
                return right.getValue().compareTo(left.getValue());
            }
        };
        
        list.sort(comparator);
        
        // Create String
        StringBuffer ss = new StringBuffer();
        for (Map.Entry<Character, Integer> entry : list) {
            for (int i = 0; i < entry.getValue(); ++i) {
                ss.append(entry.getKey());
            }
        }
        
        return ss.toString();
        
    }
}

发表于 | 分类于

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

Integers in each row are sorted from left to right.
The first integer of each row is greater than the last integer of the previous row.
For example,

Consider the following matrix:

[
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
Given target = 3, return true.

解法1：Binary Search O(logMN) MN = total # of elements

Java

1

发表于 | 分类于

Given a collection of intervals, merge all overlapping intervals.

For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

解法1：O(NlogN) Time

先排序之后再合并比较简单。只要检查后面的start是否比前面的end小就可以了。

Java
主要是锻炼一下Java中用Collections.sort(list, comparator)的用法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
public class Solution {
    public List<Interval> merge(List<Interval> intervals) {
        if (intervals == null || intervals.size() == 0) {
            return intervals;
        }
        
        Comparator<Interval> comparator = new Comparator<Interval>() {
            public int compare(Interval left, Interval right) {
                return left.start - right.start;
            }
        };
        // Sort the interval based on the start 
        Collections.sort(intervals, comparator);
        
        List<Interval> res = new ArrayList<Interval>();
        res.add(intervals.get(0));
        for (int i = 1; i < intervals.size(); ++i) {
            Interval current = intervals.get(i);
            Interval previous = res.get(res.size() - 1);
            if (current.start <= previous.end) {
                previous.end = Math.max(current.end, previous.end);
            } else {
                res.add(current);
            }
        }
        return res;
    }
}

发表于 | 分类于

Given an integer, convert it to a roman numeral.

Input is guaranteed to be within the range from 1 to 3999.

解法1：

主要的思路是要先构造出来罗马数字中的“根”数。也就是说，除了那么1,5,10,50,100,500,1000的数字，还有那些需要特殊处理的，比如40.
然后得算法就简单了，就遍历一遍dict， 每当找出来一个比当前base小的数就计算出需要重复几遍，比如III。
然后更新base数值。
Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Solution {
    public String intToRoman(int n) {
        // Write your code here
        
         
        String dict[] = new String[]{"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
        int base[] = new int[]{1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        
        String res = "";
        for (int i = 0; i < dict.length; i++) {
            if (n >= base[i]) {
                
                int count = n / base[i];
                n = n % base[i];
                for (int j = 0; j < count; j++) {
                    res += dict[i];
                }
            }
        }
        
        return res;
        
    }
}

发表于 | 分类于

Implement atoi to convert a string to an integer.

Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.

Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.

解法1：

这题要考虑的corner case比较多，也是这题的难点。
corner case有：
empty string
string with space
string with positive or negative sign
string with non-digit numbers
overflow integer
对于overflow的处理有两种情况。一个是当前的total乘以10之后超过Integer.MAX_VALUE，由于不能直接比total * 10 > Integer.MAX_VALUE, 我们可以换一种比法。
用Integer.MAX_VALUE / 10 < total 表示判断标准。
但是这又有一种情况就是Integer.MAX_VALUE / 10 是整数除法，可能会有遗漏的情况是最后一位不同。
那么就需要排除Integer.MAX_VALUE / 10 == total && Integer.MAX_VALUE % 10 < digit 的情况。
Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public class Solution {
    public int myAtoi(String str) {
        if (str == null || str.isEmpty() || str.trim().isEmpty()) {
            return 0;
        }
        
        str = str.trim();
        
        boolean isNegative = false;
        if (str.charAt(0) == '-') {
            isNegative = true;
            str = str.substring(1);
        } else if (str.charAt(0) == '+') {
            str = str.substring(1);
        }
        
        // check if all characters are digits
        int total = 0;
        for (int i = 0; i < str.length(); ++i) {
            char ch = str.charAt(i);
            if (ch < '0' || ch >'9') {
                break;
            }
            
            int digit = ch - '0';
            if (Integer.MAX_VALUE/10 < total || (Integer.MAX_VALUE/10 == total && Integer.MAX_VALUE % 10 < digit)) {
                return isNegative ? Integer.MIN_VALUE : Integer.MAX_VALUE;
            }
            
            total = total * 10 + digit;
        }
        
        
        return isNegative ? (-1) * total : total;
    }
}