LeetCode 热题 100（四）：48. 旋转图像、240. 搜索二维矩阵 II、234. 回文链表

一.48. 旋转图像

题目要求：就是一个顺时针的旋转过程。

 思路：观察矩阵，得出翻转前第i行的第J个元素  等于  翻转后倒数第i列的第J个元素，举例说明，第1行第2个元素为“2”，翻转后到了 倒数第1列的第2个元素。说白了只需要针对翻转前的第i行和翻转后的倒数第i列

代码：

class Solution {public void rotate(int[][] matrix) {int n = matrix.length;int[][] matrix_new = new int[n][n];// 按照思路对新矩阵存值for (int i = 0; i < n; ++i) {for (int j = 0; j < n; ++j) {matrix_new[j][n - i - 1] = matrix[i][j];}}for (int i = 0; i < n; ++i) {for (int j = 0; j < n; ++j) {matrix[i][j] = matrix_new[i][j];}}}
}

二.240. 搜索二维矩阵 II

题目要求：编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

• 每行的元素从左到右升序排列。
• 每列的元素从上到下升序排列

思路：这个题可以直接使用双层for循环暴力破解； 也可以使用二分查找

代码：

class Solution {public boolean searchMatrix(int[][] matrix, int target) {for (int[] row : matrix) {int a = search(row, target);// 务必注意这里只要找到了就直接return true 而不是找不到return falseif (a >= 0)return true;}return false;}// 二分查找即可public int search(int[] nums, int target){int l = 0;int r = nums.length - 1;while (l <= r){int mid = l +((r - l) >> 1);if (nums[mid] > target)r = mid - 1;else if (nums[mid] < target)l = mid + 1;elsereturn mid;}return -1;}
}

三、234. 回文链表

题目要求：

 思路：因为链表无法使用双指针做，所以先将链表的值复制到数组中，然后使用双指针进行判断。

代码：

class Solution {public boolean isPalindrome(ListNode head) {// 将链表的值复制到数组中List<Integer> vals = new ArrayList<Integer>();ListNode cur = head;while (cur != null){vals.add(cur.val);cur = cur.next;}// 双指针判断是否回文int l = 0;int r = vals.size() - 1;while (l < r){if (vals.get(l) != vals.get(r))return false;l++;r--;}return true;}
}