650 2 Keys Keyboard
class Solution {
public int minSteps(int n) {
int res = 0;
for(int i=2;i<=n;i++){
while(n%i == 0){
res+= i;
n=n/i;
}
}
return res;
}
}
738 Monotone Increasing Digits
class Solution {
public int monotoneIncreasingDigits(int N) {
char[] cArray = String.valueOf(N).toCharArray();
int i = 1;
while (i < cArray.length && cArray[i - 1] <= cArray[i]) i++;
while (i > 0 && i < cArray.length && cArray[i - 1] > cArray[i]) cArray[--i]--;
for (int k = i + 1; k < cArray.length; k++){
cArray[k] = '9';
}
return Integer.parseInt(String.valueOf(cArray));
}
}
406 Queue Reconstruction by Height
class Solution {
public int[][] reconstructQueue(int[][] people) {
Arrays.sort(people, (a, b) -> (a[0] != b[0] ? b[0] - a[0] : a[1] - b[1]));
List<int[]> ans = new ArrayList<>();
for (int[] p : people){
ans.add(p[1], p);
}
return ans.toArray(new int[people.length][]);
}
}
498 Diagonal Traverse
class Solution {
public int[] findDiagonalOrder(int[][] matrix) {
if (matrix == null || matrix.length == 0) return new int[0];
int n = matrix.length, m = matrix[0].length;
int[] ans = new int[n * m];
int row = 0, col = 0, d = 0;
int[] x_moves = {-1, 1};
int[] y_moves = {1, -1};
for (int i = 0; i < m * n; i++){
ans[i] = matrix[row][col];
row += x_moves[d];
col += y_moves[d];
if (col >= m) {row += 2; col = m - 1; d = 1 - d;}
if (row >= n) {col += 2; row = n - 1; d = 1 - d;}
if (row < 0) {row = 0; d = 1 - d;}
if (col < 0) {col = 0; d = 1 - d;}
}
return ans;
}
}
540 Single Element in a Sorted Array
https://leetcode.com/problems/single-element-in-a-sorted-array/discuss/100754
class Solution {
public int singleNonDuplicate(int[] nums) {
int start = 0, end = nums.length - 1;
while (start < end){
int mid = start + (end - start) / 2;
if (mid % 2 == 1) mid--;
if (nums[mid] != nums[mid + 1]) end = mid;
else start = mid + 2;
}
return nums[start];
}
}
539 Minimum Time Difference
class Solution {
public int findMinDifference(List<String> timePoints) {
List<Integer> times = new ArrayList<>();
for (String time : timePoints){
int h = Integer.parseInt(time.substring(0, 2));
int m = Integer.parseInt(time.substring(3));
times.add(60 * h + m);
}
Collections.sort(times, (a, b) -> (a - b));
int minTime = Integer.MAX_VALUE;
for (int i = 1; i < times.size(); i++){
minTime = Math.min(minTime, times.get(i) - times.get(i - 1));
}
int corner = times.get(0) + (1440 - times.get(times.size() - 1));
return Math.min(minTime, corner);
}
}
722 Remove Comments
class Solution {
public List<String> removeComments(String[] source) {
boolean inBlock = false;
StringBuilder newLine = new StringBuilder();
List<String> ans = new ArrayList<>();
for (String line : source){
if (!inBlock) newLine = new StringBuilder();
int i = 0;
while (i < line.length()){
if (!inBlock && i + 1 < line.length() && line.charAt(i) == '/' && line.charAt(i + 1) == '*'){
inBlock = true;
i++;
}
else if (inBlock && i + 1 < line.length() && line.charAt(i) == '*' && line.charAt(i + 1) == '/'){
inBlock = false;
i++;
}
else if (!inBlock && i + 1 < line.length() && line.charAt(i) == '/' && line.charAt(i + 1) == '/'){
break;
}
else if (!inBlock){
newLine.append(line.charAt(i));
}
i++;
}
if (newLine.length() > 0 && !inBlock){
ans.add(newLine.toString());
}
}
return ans;
}
}
338 Counting Bits
class Solution {
public int[] countBits(int num) {
int[] dp = new int[num + 1];
int offset = 1;
for (int i = 1; i <= num; i++){
if (offset * 2 == i){
offset *= 2;
}
dp[i] = dp[i - offset] + 1;
}
return dp;
}
}
554 Brick Wall
class Solution {
public int leastBricks(List<List<Integer>> wall) {
if (wall == null || wall.size() == 0) return 0;
Map<Integer, Integer> hash = new HashMap<>();
int max = 0;
for (List<Integer> row : wall){
int length = 0;
for (int i = 0; i < row.size() - 1; i++){
length += row.get(i);
hash.put(length, hash.getOrDefault(length, 0) + 1);
max = Math.max(max, hash.get(length));
}
}
return wall.size() - max;
}
}
419 Battleships in a Board
class Solution {
public int countBattleships(char[][] board) {
if (board == null || board.length == 0) return 0;
int count = 0;
for (int i = 0; i < board.length; i++){
for (int j = 0; j < board[0].length; j++){
if (board[i][j] == '.') continue;
if (i > 0 && board[i - 1][j] == 'X') continue;
if (j > 0 && board[i][j - 1] == 'X') continue;
count++;
}
}
return count;
}
}
391 Perfect Rectangle
The right answer must satisfy two conditions:
- the large rectangle area should be equal to the sum of small rectangles
- count of all the points should be even, and that of all the four corner points should be one
class Solution {
public boolean isRectangleCover(int[][] rectangles) {
int x1 = Integer.MAX_VALUE;
int y1 = Integer.MAX_VALUE;
int x2 = Integer.MIN_VALUE;
int y2 = Integer.MIN_VALUE;
Set<String> hash = new HashSet<>();
int area = 0;
for (int[] rec : rectangles){
area += (rec[2] - rec[0]) * (rec[3] - rec[1]);
x1 = Math.min(x1, rec[0]);
y1 = Math.min(y1, rec[1]);
x2 = Math.max(x2, rec[2]);
y2 = Math.max(y2, rec[3]);
String s1 = rec[0] + "#" + rec[1];
String s2 = rec[2] + "#" + rec[1];
String s3 = rec[2] + "#" + rec[3];
String s4 = rec[0] + "#" + rec[3];
if (!hash.add(s1)) hash.remove(s1);
if (!hash.add(s2)) hash.remove(s2);
if (!hash.add(s3)) hash.remove(s3);
if (!hash.add(s4)) hash.remove(s4);
}
if (!hash.contains(x1 + "#" + y1) || !hash.contains(x2 + "#" + y2) || !hash.contains(x2 + "#" + y1) || !hash.contains(x1 + "#" + y2) || hash.size() != 4) return false;
return area == (x2 - x1) * (y2 - y1);
}
}