1.移动零
- move-zeroes(easy)
LeetCode
思路：
1、建立两个指针，前置指针负责判断当前的值是否是0，如果为0，对下一位进行判断；如果不为零，则把当前的值放到cur指针指向的位置，cur++
//2020年11月9日
class Solution {
public void moveZeroes(int[] nums) {
int pre = 0;
int cur = 0;
while(pre != nums.length){
if(nums[pre] == 0){
pre++;
}else{
nums[cur++] = nums[pre++];
}
}
while(cur != nums.length){
nums[cur++] = 0;
}
}
}2、一次遍历,利用快排的思想
class Solution {
public void moveZeroes(int[] nums) {
if(nums == null) return ;
int i = 0;
for(int j=0;j<nums.length;++j){
if(nums[j]!=0){
int temp = nums[j];
nums[j] = nums[i];
nums[i++] = temp;
}
}
}
}2.重塑矩阵
- reshape-the-matrix(easy)
LeetCode
思路：
1、对给出的二维数组进行遍历，将遍历到的元素放到队列中，再遍历生成的数组，将队列中的元素放进去
class Solution {
public int[][] matrixReshape(int[][] nums, int r, int c) {
int[][] matrix = new int[r][c];
if(nums == null || r * c != nums.length * nums[0].length){
return nums;
}
int count = 0;
Queue <Integer> queue = new LinkedList < > ();
for(int i=0;i<nums.length;i++){
for(int j=0;j<nums[0].length;j++){
queue.add(nums[i][j]);
}
}
for(int i=0;i<r;i++){
for(int j=0;j<c;j++){
matrix[i][j] = queue.remove();
}
}
return matrix;
}
}2、
class Solution {
public int[][] matrixReshape(int[][] nums, int r, int c) {
int m = nums.length;
int n = nums[0].length;
if ((m * n) != (r * c)) {
return nums;
}
int[][] reshapedNums = new int[r][c];
int index = 0;
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
reshapedNums[i][j] = nums[index / n][index % n];
index++;
}
}
return reshapedNums;
}
}
3.最大连续1的个数
- max-consecutive-ones(easy)
LeetCode
思路：
1、设置一个pre保存当前1的个数，每往下走一步就把当前的pre和要返回的count进行比较，取最大值
class Solution {
public int findMaxConsecutiveOnes(int[] nums) {
int pre = 0;
int count = 0;
for(int i=0;i<nums.length;i++){
pre = nums[i] == 0 ? 0 : pre+1;
count = Math.max(count,pre);
}
return count;
}
}4.搜索二维矩阵 II
- search-a-2d-matrix-ii(Medium)
LeetCode
思路：
1、因为矩阵的特性，我们可以从右上角开始走，当当前值比target大时就往左走，比target小时就往下走
public boolean searchMatrix(int[][] matrix, int target) {
if(matrix.length <= 0 || matrix[0].length <=0) return false;
int curX = 0;
int curY = matrix[0].length - 1;
while(curX >=0 && curX < matrix.length && curY >= 0 && curY < matrix[0].length){
if(matrix[curX][curY] < target){
curX++;
}else if(matrix[curX][curY] > target){
curY--;
}else{
return true;
}
}
return false;
}2、遍历
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
for(int i=0;i<matrix.length;i++){
for(int j=0;j<matrix[0].length;j++){
if(matrix[i][j] == target) return true;
}
}
return false;
}
}5.有序矩阵中第K小的元素
- kthSmallest(Medium)
LeetCode
思路：
1、二分查找
二维数组本质上是一个一维数组，可以用二分查找来解决问题
设二维数组的左上角节点为left，右下角节点为right，
用两者的值求中间值，去check函数中进行判断当前数组比mid小的值是否比k多，
如果比k多，说明右边界需要移动到mid;如果小于等于k的话,就移动左边界
直到left等于right等于mid，返回left
//2020年11月11日
class Solution {
public int kthSmallest(int[][] matrix, int k) {
int len = matrix.length;
int left = matrix[0][0];
int right = matrix[len-1][len-1];
while(left<right){
int mid = (left + right) / 2;
if(check(matrix,mid,k,len)){
right = mid;
}else{
left = mid + 1;
}
}
return left;
}
public boolean check(int[][] arr,int mid,int k,int len){
int num = 0;
int i = len -1;
int j = 0;
while(i >= 0 && j < len){
if(arr[i][j] <= mid){
num += i+1;
j++;
}else{
i--;
}
}
return num >= k;
}
}6.错误的集合
- set-mismatch(easy)
LeetCode
思路：
1、本来想用HashMap的，但是一想如果数值在N以内的话好像数组更方便
//2020年11月12日
public int[] findErrorNums(int[] nums) {
int[] res = new int[2];
int len = nums.length;
if(nums.length < 1) return res;
int[] arr = new int[len];
for(int i=0;i<len;i++){
if(arr[nums[i]-1] >= 1){
arr[nums[i]-1]++;
}else{
arr[nums[i]-1]=1;
}
}
for(int i=0;i<len;i++){
if(arr[i] > 1){
res[0] = i+1;
}else if(arr[i] == 0){
res[1] = i+1;
}
}
return res;
}7. 寻找重复数
- find-the-duplicate-number(Medium)
LeetCode
- 不能更改原数组（假设数组是只读的）。
- 只能使用额外的 O(1) 的空间。
- 时间复杂度小于 O(n2) 。
- 数组中只有一个重复的数字，但它可能不止重复出现一次。
思路：
1、这题要是没有这限制条件的话，我TM直接双重循环/两次循环+数组就解出来了，但是它要求使用额外的 O(1) 的空间，且时间复杂度小于 O(n2)，突然感觉被针对了。
这题其实有个很关键的条件，其数字都在 1 到 n 之间（包括 1 和 n），这样我们就可以用二分查找的变式来解决这个问题。
数组的下标作为左右边界，求mid，遍历整个数组找到小于等于mid的数，
如果得到的count与mid相等，则重复的数不在左边界到mid之间，移动左边界
如果得到的count>mid，则重复的数不在右边界到mid之间，移动右边界
一直移动移动，当left == right时，最后就不动了，得到的left就是我们要的值
//2020年11月13日
public int findDuplicate(int[] nums) {
int left = 1;
int right = nums.length - 1;
while(left <= right){
int mid = left + (right - left) / 2;
int count = 0;
for(int i=0;i<nums.length;i++){
if(nums[i] <= mid){
count++;
}
}
if(count > mid){
right = mid - 1;
}else{
left = mid + 1;
}
}
return left;
}8. 数组的度
- Degree of an Array (Easy)
LeetCode
思路：
一开始我是想设置一个求数组的degree的函数，然后双重循环求出每一个数组的度，得到与其相等的那个最小的长度
但是结果就是超时了，可能这个解法实在是太笨了吧
看了别人的解析，主要的思路如下：
设置三个HashMap，left用来存当前数字第一次出现的位置，right存当前数组最后一次出现的位置，count用来存数字的个数(度)
然后求出整个数组的度，再次遍历这个数组，如果当前的数字个数与整个数组的度不一样，直接跳出进行下一次循环，
如果相等，则用right-left+1与len进行比较，取最小
//2020年11月15日
public int findShortestSubArray(int[] nums) {
HashMap<Integer,Integer> left = new HashMap();
HashMap<Integer,Integer> right = new HashMap();
HashMap<Integer,Integer> count = new HashMap();
for(int i=0;i<nums.length;i++){
int num = nums[i];
count.put(num,count.getOrDefault(num,0)+1);
right.put(num,i);
if(!left.containsKey(num)){
left.put(num,i);
}
}
int degree = 0;
for(int i=0;i<nums.length;i++){
degree = Math.max(degree,count.get(nums[i]));
}
int len = nums.length;
for(int i=0;i<nums.length;i++){
if(count.get(nums[i]) != degree) continue;
len = Math.min(len,right.get(nums[i])-left.get(nums[i])+1);
}
return len;
}9. 托普利茨矩阵
- toeplitz-matrix (Easy)
LeetCode
思路：
双重循环，每遍历到一个数，去检查当前元素与其左上角元素是否一致，如果不一致，就不托普利茨矩阵，否则就是
//2020年11月17日
public boolean isToeplitzMatrix(int[][] matrix) {
for (int r = 0; r < matrix.length; ++r)
for (int c = 0; c < matrix[0].length; ++c)
if (r > 0 && c > 0 && matrix[r-1][c-1] != matrix[r][c])
return false;
return true;
}
京公网安备 11010502036488号