class Solution {
public boolean isPalindrome(int x) {
if (x < 0) return false;
int y = x;
int z = 0;
while (y > 0){
int k = y % 10;
z = z * 10 + k;
y = y / 10;
}
return x == z;
}
}
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int p1 = m - 1;
int p2 = n - 1;
for (int i = m + n - 1; i >= 0; i--){
if (p1 >= 0 && p2 >= 0) {
if (nums1[p1] > nums2[p2]) {
nums1[i] = nums1[p1--];
} else {
nums1[i] = nums2[p2--];
}
} else if (p2 >= 0) {
nums1[i] = nums2[p2--];
} else {
break;
}
}
}
}.
class Solution {
public int longestConsecutive(int[] nums) {
HashSet<Integer> hashSet = new HashSet<>();
for (int num:nums){
hashSet.add(num);
}
int maxCount = 0;
for (int num:hashSet){
//不是最小的
if (!hashSet.contains(num - 1)) {
int cur = num;
int count = 1;
while (hashSet.contains(cur + 1)) {
cur++;
count++;
}
maxCount = Math.max(maxCount, count);
}
}
return maxCount;
}
}
class Solution {
public boolean containsDuplicate(int[] nums) {
HashSet<Integer> hashSet = new HashSet<>();
for (int num:nums){
if (hashSet.contains(num)) return true;
hashSet.add(num);
}
return false;
}
}
class Solution {
public int[] productExceptSelf(int[] nums) {
int left = 1;
int length = nums.length;
int[] result = new int[length];
for (int i = 0; i < length; i++){
result[i] = left;
left = left * nums[i];
}
int right = 1;
for (int i = length - 1; i >= 0; i--){
result[i] = result[i] * right;
right = right * nums[i];
}
return result;
}
}
class Solution {
public boolean judgeCircle(String moves) {
int j = 0;
int k = 0;
for (int i = 0; i < moves.length(); i++){
char c = moves.charAt(i);
if (c == 'R') {
j++;
} else if (c == 'L') {
j--;
} else if (c == 'U') {
k++;
} else {
k--;
}
}
return j == 0 && k == 0;
}
}
class Solution {
public boolean isStraight(int[] nums) {
int maxValue = Integer.MIN_VALUE;
int minValue = Integer.MAX_VALUE;
HashSet<Integer> hashSet = new HashSet<>();
for (int i = 0; i < nums.length; i++){
if (nums[i] == 0) continue;
if (maxValue < nums[i]) {
maxValue = nums[i];
}
if (minValue > nums[i]) {
minValue = nums[i];
}
if (hashSet.contains(nums[i])) return false;
hashSet.add(nums[i]);
}
// System.out.println(maxValue + " " + minValue);
return maxValue - minValue < 5;
}
}
class Solution {
public boolean isStraight(int[] nums) {
Arrays.sort(nums);
int zeroIndex = 0;
for (int i = 0; i < nums.length - 1; i++){
if (nums[i] == 0) {
zeroIndex++;
continue;
}
if (nums[i] == nums[i + 1]) return false;
}
// System.out.println(nums[nums.length - 1] + " " + nums[zeroIndex]);
return nums[nums.length -1] - nums[zeroIndex] < 5;
}
}
class Solution {
public void rotate(int[][] matrix) {
int n = matrix.length;
int[][] result = new int[n][n];
for (int i = 0; i < n; i++){
for (int j = 0; j < n; j++){
result[j][n - 1 - i] = matrix[i][j];
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
matrix[i][j] = result[i][j];
}
}
}
}
class Solution {
public void rotate(int[][] matrix) {
int n = matrix.length;
//对角线转置
for (int i = 0; i < n; i++) {
int index = i;
while (index < n) {
int temp = matrix[i][index];
matrix[i][index] = matrix[index][i];
matrix[index][i] = temp;
index++;
}
}
//镜像交换
for (int i = 0; i < n; i++) {
int left = 0;
int right = n - 1;
while (left < right) {
int temp = matrix[i][left];
matrix[i][left] = matrix[i][right];
matrix[i][right] = temp;
left++;
right--;
}
}
}
}
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> result = new ArrayList<>();
if (matrix == null || matrix.length == 0) return result;
int left = 0;
int right = matrix[0].length - 1;
int up = 0;
int down = matrix.length - 1;
while (true) {
for (int col = left; col <= right; col++) {
result.add(matrix[up][col]);
}
if (++up > down) {
break;
}
for (int row = up; row <= down; row++) {
result.add(matrix[row][right]);
}
if (--right < left) {
break;
}
for (int col = right; col >= left; col--) {
result.add(matrix[down][col]);
}
if (--down < up) {
break;
}
for (int row = down; row >= up; row--) {
result.add(matrix[row][left]);
}
if (++left > right) {
break;
}
}
return result;
}
}
class Solution {
public int[][] generateMatrix(int n) {
int[][] result = new int[n][n];
int left = 0;
int right = n - 1;
int up = 0;
int down = n - 1;
int index = 1;
while (true) {
for (int col = left; col <= right; col++) {
// System.out.println(col);
result[up][col] = index++;
}
if (++up > down) break;
for (int row = up; row <= down; row++) {
result[row][right] = index++;
}
if (--right < left) break;
for (int col = right; col >= left; col--) {
result[down][col] = index++;
}
if (--down < up) break;
for (int row = down; row >= up; row--) {
result[row][left] = index++;
}
if (++left > right)break;
}
return result;
}
}
class Solution {
public void setZeroes(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
boolean[] cols = new boolean[n];
boolean[] rows = new boolean[m];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == 0) {
rows[i] = true;
cols[j] = true;
}
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (cols[j] || rows[i]) matrix[i][j] = 0;
}
}
}
}
class Solution {
public void setZeroes(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
boolean col = false;
boolean row = false;
for (int j = 0; j < n; j++) {
if (matrix[0][j] == 0) {
col = true;
break;
}
}
for (int i = 0; i < m; i++) {
if (matrix[i][0] == 0) {
row = true;
break;
}
}
//扫描标记
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (matrix[i][j] == 0) {
matrix[i][0] = 0;
matrix[0][j] = 0;
}
}
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (matrix[i][0] == 0 || matrix[0][j] == 0) matrix[i][j] = 0;
}
}
if (col) {
for (int j = 0; j < n; j++) {
matrix[0][j] = 0;
}
}
if (row) {
for (int i = 0; i < m; i++) {
matrix[i][0] = 0;
}
}
}
}
class Solution {
public boolean isValidSudoku(char[][] board) {
boolean[][] rows = new boolean[9][9];
boolean[][] cols = new boolean[9][9];
boolean[][] grids = new boolean[9][9];
for (int i = 0; i < 9; i++){
for (int j = 0; j < 9; j++){
char c = board[i][j];
if (c != '.') {
int index = c - '1';
int gridIndex = i / 3 * 3 + j / 3;
if (rows[i][index] || cols[j][index] || grids[gridIndex][index]) {
return false;
} else {
rows[i][index] = true;
cols[j][index] = true;
grids[gridIndex][index] = true;
}
}
}
}
return true;
}
}
class Solution {
public boolean isValidSudoku(char[][] board) {
int[][] rows = new int[9][9];
int[][] cols = new int[9][9];
int[][][] grids = new int[3][3][9];
for (int i = 0; i < 9; i++){
for (int j = 0; j < 9; j++){
char c = board[i][j];
if (c != '.') {
int index = c - '1';
rows[i][index]++;
cols[j][index]++;
grids[i / 3][j / 3][index]++;
if (rows[i][index] > 1 || cols[j][index] > 1 || grids[i / 3][j / 3][index] > 1) return false;
}
}
}
return true;
}
}
class Solution {
public void gameOfLife(int[][] board) {
int m = board.length;
int n = board[0].length;
for (int i = 0; i < m; i++){
for (int j = 0; j < n; j++){
//统计四周活细胞数量
int count = 0;
for (int k = -1; k <= 1; k++){
for (int g = -1; g <= 1; g++){
int ii = i + k;
int jj = j + g;
if (ii == i && jj == j) continue;
if ((ii >= 0 && ii < m) && (jj >= 0 && jj < n) && Math.abs(board[ii][jj]) == 1) count++;
}
}
if (board[i][j] == 1 && (count < 2 || count > 3)) board[i][j] = -1;
if (board[i][j] == 0 && count == 3) board[i][j] = 2;
}
}
for (int i = 0; i < m; i++){
for (int j = 0; j < n; j++){
if (board[i][j] == -1) board[i][j] = 0;
else if (board[i][j] == 2) board[i][j] = 1;
}
}
}
}
class Solution {
public int countBattleships(char[][] board) {
int m = board.length;
int n = board[0].length;
int result = 0;
for (int i = 0; i < m; i++){
for (int j = 0; j < n; j++){
if (board[i][j] == 'X') {
if (i > 0 && board[i - 1][j] == 'X') continue;
if (j > 0 && board[i][j - 1] == 'X') continue;
result++;
}
}
}
return result;
}
}
class Solution {
public int islandPerimeter(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int result = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
result += 4;
if (i > 0 && grid[i - 1][j] == 1) result -= 2;
if (j > 0 && grid[i][j - 1] == 1) result -= 2;
}
}
}
return result;
}
}
class Solution {
public int[] findDiagonalOrder(int[][] mat) {
int m = mat.length;
int n = mat[0].length;
int i = 0;
int j = 0;
int index = 0;
int[] result = new int[m * n];
//右上角
int dir = 1;
while (index < m * n) {
result[index++] = mat[i][j];
int ni = i;
int nj = j;
if (dir == 1) {
ni = i - 1;
nj = j + 1;
} else {
ni = i + 1;
nj = j - 1;
}
//超过边界处理
if (index < m * n && (ni < 0 || ni >= m || nj < 0 || nj >= n)) {
if (dir == 1) {
ni = j + 1 < n ? i : i + 1;
nj = j + 1 < n ? j + 1 : j;
} else {
ni = i + 1 < m ? i + 1 : i;
nj = i + 1 < m ? j : j + 1;
}
dir = dir == 1 ? -1 : 1;
}
i = ni;
j = nj;
}
return result;
}
}
class Solution {
public void rotate(int[][] matrix) {
int n = matrix.length;
//水平反转
for (int i = 0; i < n / 2; i++) {
for (int j = 0; j < n; j++) {
int temp = matrix[i][j];
matrix[i][j] = matrix[n - 1 - i][j];
matrix[n - 1 - i][j] = temp;
}
}
//主对角线
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
int temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
}
}
