Leetcode189.
Given an array, rotate the array to the right by k steps, where k is non-negative.
示例 1:
输入: nums = [1,2,3,4,5,6,7], k = 3 输出: [5,6,7,1,2,3,4] 解释: 向右旋转 1 步: [7,1,2,3,4,5,6] 向右旋转 2 步: [6,7,1,2,3,4,5] 向右旋转 3 步: [5,6,7,1,2,3,4]
示例 2:
输入:nums = [-1,-100,3,99], k = 2 输出:[3,99,-1,-100] 解释: 向右旋转 1 步: [99,-1,-100,3] 向右旋转 2 步: [3,99,-1,-100]
提示:
1 <= nums.length <= 2 * 104 -231 <= nums[i] <= 231 - 1 0 <= k <= 105
图解:
AC代码:
class Solution { public void rotate(int[] nums, int k) { int len = nums.length; // 特例检验:k = len, k = 0 // 移动3位%长度3 = 0,是len,不是len-1 // 移动0位%长度3 = 0,start < end k %= len; reverse(nums, 0, len - 1); // 旋转k个数,那就是第k-1的位置 reverse(nums, 0, k - 1); reverse(nums, k, len - 1); } public void reverse(int[] nums, int start, int end){ while(start < end){ int temp = nums[start]; nums[start++] = nums[end]; nums[end--] = temp; } } }
图解:
分步演示:
AC代码:
特例:len = 0、len = k,原地打转,所以每次先判断是否下一个用过,若用过,移至下一位重新开始!
class Solution { public void rotate(int[] nums, int k) { int index = 0; // 当前值 int cur = nums[index]; int len = nums.length; // 储存下一个位置是否用过 boolean[] isUse = new boolean[len]; for(int i = 0; i < len; i++){ // 下一个位置坐标 index = (index + k) % len; if(isUse[index]){ index = (index + 1) % len; cur = nums[index]; i--; }else{ isUse[index] = true; int temp = nums[index]; nums[index] = cur; cur = temp; } } } }
图解:
AC代码:
class Solution { public void rotate(int[] nums, int k) { int len = nums.length; int[] temp = Arrays.copyOfRange(nums, 0, len); for(int i = 0; i < len; i++){ nums[(i+k) % len] = temp[i]; } } }
Leetcode217.
Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.
示例 1:
输入: [1,2,3,1] 输出: true
示例 2:
输入: [1,2,3,4] 输出: false
示例 3:
输入: [1,1,1,3,3,4,3,2,4,2] 输出: true
思路:
数组升序(从小到大排序后,相同必相邻)+判断相邻是否相同
AC代码:
class Solution { public boolean containsDuplicate(int[] nums) { int len = nums.length; Arrays.sort(nums); for(int i = 0; i < len - 1; i++){ if(nums[i] == nums[i + 1]){ return true; } } return false; } }
时间复杂度:O(NlogN)
空间复杂度:O(logN)(考虑递归调用栈的深度)
思路:
用哈希表来检测是否存在当前字符,若存在直接返回结果。
AC代码:
class Solution { public boolean containsDuplicate(int[] nums) { Set<Integer> set = new HashSet<Integer>(); for(int i : nums){ if(!set.add(i)){ return true; } } return false; } }
时间复杂度:O(N)
空间复杂度:O(N)
Leetcode136.
Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.
示例 1:
输入: [2,2,1] 输出: 1
示例 2:
输入: [4,1,2,1,2] 输出: 4
思路:
同上一题:哈希判断是否存在+若存在移除+输出仅剩的一个
AC代码:
class Solution { public int singleNumber(int[] nums) { Set<Integer> set = new HashSet<Integer>(); for(int i : nums){ if(!(set.add(i))){ set.remove(i); } } return (int)set.toArray()[0]; } }
时间复杂度:O(N)
空间复杂度:O(N)
思路:
异或规律:
题目中出现一次的数字只有一个
,其余数字出现两次
,异或后,出现两次的数字为0,出现一次的等于它自己。
AC代码:
class Solution { public int singleNumber(int[] nums) { int res = 0; for(int i : nums){ res ^= i; } return res; } }
时间复杂度:O(N)(遍历数组)
空间复杂度:O(1)
Leetcode350.
Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must appear as many times as it shows in both arrays and you may return the result in any order.
示例 1:
输入:nums1 = [1,2,2,1], nums2 = [2,2] 输出:[2,2]
示例 2:
输入:nums1 = [4,9,5], nums2 = [9,4,9,8,4] 输出:[4,9]
说明:
输出结果中每个元素出现的次数,应与元素在两个数组中出现次数的最小值一致。
我们可以不考虑输出结果的顺序。
进阶:
如果给定的数组已经排好序呢?你将如何优化你的算法?
如果 nums1 的大小比 nums2 小很多,哪种方法更优?
如果 nums2 的元素存储在磁盘上,内存是有限的,并且你不能一次加载所有的元素到内存中,你该怎么办?
思路:数组排序+双指针指向同一值为交集
AC代码:
class Solution { public int[] intersect(int[] nums1, int[] nums2) { // 先对两个数组进行排序 Arrays.sort(nums1); Arrays.sort(nums2); // 双指针 int i = 0, j = 0; int len1 = nums1.length, len2 = nums2.length; List<Integer> list = new ArrayList<>(); // 匹配相同的 while(i < len1 && j < len2){ if(nums1[i] < nums2[j]){ i++; }else if(nums1[i] > nums2[j]){ j++; }else{ list.add(nums1[i]); i++; j++; } } int[] res = new int[list.size()]; for(int k = 0; k < res.length; k++){ res[k] = list.get(k); } return res; } }
Leetcode66.
Given a non-empty array of decimal digits representing a non-negative integer, increment one to the integer.
示例 1:
输入:digits = [1,2,3] 输出:[1,2,4] 解释:输入数组表示数字 123。
示例 2:
输入:digits = [4,3,2,1] 输出:[4,3,2,2] 解释:输入数组表示数字 4321。
示例 3:
输入:digits = [0] 输出:[1]
提示:
1 <= digits.length <= 100 0 <= digits[i] <= 9
思路:末位是否进位+进位是否数组长度是否改变
图解:三种情况:
所指数字是9吗?不是则输出,是则变为0,然后指向上一位,若上一位不存在,新建一个位1.
AC代码:
class Solution { public int[] plusOne(int[] digits) { int len = digits.length; for(int i = len - 1; i >= 0; i--){ if(digits[i] != 9){ digits[i] ++; return digits; }else{ digits[i] = 0; } } int[] temp = new int[len + 1]; temp[0] = 1; return temp; } }
Leetcode283.
Given an integer array nums, move all 0’s to the end of it while maintaining the relative order of the non-zero elements.
示例:
输入: [0,1,0,3,12] 输出: [1,3,12,0,0]
说明:
必须在原数组上操作,不能拷贝额外的数组。 尽量减少操作次数。
思路:参考快速排序
的思想,找分割点:0
,不等于0的元素放到数组左边
,等于0的元素放到右边
图解:
AC代码:
class Solution { public void moveZeroes(int[] nums) { // 标记0的位置 int i = 0; // 标记要交换的位置 int j = 0; int len = nums.length; for(i = 0; i < len; i++){ if(nums[i] != 0){ // 交换 int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; j++; } } } }
时间复杂度:O(N)遍历数组
空间复杂度:O(1)指针
思路:双指针
AC代码:
class Solution { public void moveZeroes(int[] nums) { int i = 0; int j = 0; int len = nums.length; for(i = 0; i < len; i++){ if(nums[i] != 0){ nums[j] = nums[i]; j++; } } for(; j < len; j++){ nums[j] = 0; } } }
Leetcode1.
Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
示例 1:
输入:nums = [2,7,11,15], target = 9 输出:[0,1] 解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1] 。
示例 2:
输入:nums = [3,2,4], target = 6 输出:[1,2]
示例 3:
输入:nums = [3,3], target = 6 输出:[0,1]
提示:
2 <= nums.length <= 104 -109 <= nums[i] <= 109 -109 <= target <= 109 只会存在一个有效答案
AC代码:
class Solution { public int[] twoSum(int[] nums, int target) { int len = nums.length; for(int i = 0; i < len; i++){ for(int j = i + 1; j < len; j++){ if(nums[i] + nums[j] == target){ return new int[]{i,j}; } } } return new int[]{}; } }
时间复杂度:O(N^2)
空间复杂度:O(1)
class Solution { public int[] twoSum(int[] nums, int target) { Map<Integer,Integer> map = new HashMap<>(); int len = nums.length; for(int i = 0; i < len; i++){ // 判断有无一个数+该数=目标值 if(map.containsKey(target - nums[i])){ return new int[]{map.get(target - nums[i]),i}; } map.put(nums[i],i); } return new int[]{}; } }
Leetcode36.
Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:
Each row must contain the digits 1-9 without repetition.
Each column must contain the digits 1-9 without repetition.
Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.
示例 1:
输入:board = [["5","3",".",".","7",".",".",".","."] ,["6",".",".","1","9","5",".",".","."] ,[".","9","8",".",".",".",".","6","."] ,["8",".",".",".","6",".",".",".","3"] ,["4",".",".","8",".","3",".",".","1"] ,["7",".",".",".","2",".",".",".","6"] ,[".","6",".",".",".",".","2","8","."] ,[".",".",".","4","1","9",".",".","5"] ,[".",".",".",".","8",".",".","7","9"]] 输出:true
示例 2:
输入:board = [["8","3",".",".","7",".",".",".","."] ,["6",".",".","1","9","5",".",".","."] ,[".","9","8",".",".",".",".","6","."] ,["8",".",".",".","6",".",".",".","3"] ,["4",".",".","8",".","3",".",".","1"] ,["7",".",".",".","2",".",".",".","6"] ,[".","6",".",".",".",".","2","8","."] ,[".",".",".","4","1","9",".",".","5"] ,[".",".",".",".","8",".",".","7","9"]] 输出:false 解释:除了第一行的第一个数字从 5 改为 8 以外,空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。
提示:
board.length == 9 board[i].length == 9 board[i][j] 是一位数字或者 '.'
思路:遍历整个数独,对 行、列、3X3宫格分别判断某数是否出现过两次
AC代码:
class Solution { public boolean isValidSudoku(char[][] board) { int len = board.length; // 行、列、3X3宫格 分别储存值,数字出现的次数 int[][] line = new int[len][len]; int[][] row = new int[len][len]; int[][] box = new int[len][len]; for(int i = 0; i < len; i++){ for(int j = 0; j < len; j++){ if(board[i][j] == '.')continue; // 得到对应的值,减去1对应数组下标 int num = board[i][j] - '0' - 1; int k = (i/3)*3 + j/3; // 若之前存在该数字 if(line[i][num] == 1 || row[j][num] == 1 || box[k][num] == 1){ return false; } // 标记该数字已出现一次 line[i][num] = 1; row[j][num] = 1; box[k][num] = 1; } } return true; } }
思路:两种结果(0、1)
+ 9个位置
(状态、数值)
图解:
AC代码:
class Solution { public boolean isValidSudoku(char[][] board) { int len = board.length; int[] row = new int[len]; int[] line = new int[len]; int[] box = new int[len]; int shift = 0; for (int i = 0; i < len; i++) { for (int j = 0; j < len; j++) { if (board[i][j] == '.')continue; shift = 1 << (board[i][j] - '0'); int k = (i / 3) * 3 + j / 3; // 与运算后若大于零说明有位置之前出现过 if ((row[i] & shift) > 0 || (line[j] & shift) > 0 || (box[k] & shift) > 0) return false; // 将该位置0变为1 row[i] |= shift; line[j] |= shift; box[k] |= shift; } } return true; } }
Leetcode48.
You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).
示例 1:
输入:matrix = [[1,2,3],[4,5,6],[7,8,9]] 输出:[[7,4,1],[8,5,2],[9,6,3]]
示例 2:
输入:matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]] 输出:[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]
示例 3:
输入:matrix = [[1]] 输出:[[1]]
示例 4:
输入:matrix = [[1,2],[3,4]] 输出:[[3,1],[4,2]]
提示:
matrix.length == n matrix[i].length == n 1 <= n <= 20 -1000 <= matrix[i][j] <= 1000
思路:原地操作:交换
: 上下交换、对角线交换
图解:
AC代码:
class Solution { public void rotate(int[][] matrix) { int len = matrix.length; // 上下交换 for(int i = 0; i < len/2; i++){ int[] temp = matrix[i]; matrix[i] = matrix[len - 1 -i]; matrix[len - 1 -i] = temp; } // 对角线交换 for(int i = 0; i < len; i++){ for(int j = i + 1; j < len; j++){ int temp = matrix[i][j]; matrix[i][j] = matrix[j][i]; matrix[j][i] = temp; } } } }
思路:跳棋式 交换四个数
图解:
AC代码:
class Solution { public void rotate(int[][] matrix) { int len = matrix.length; // 由于对称,只需要交换 1/4 for (int i = 0; i < len / 2; i++) for (int j = i; j < len- i - 1; j++) { // 跳棋式 交换四个数 int temp = matrix[i][j]; int m = len - j - 1; int n = len - i - 1; matrix[i][j] = matrix[m][i]; matrix[m][i] = matrix[n][m]; matrix[n][m] = matrix[j][n]; matrix[j][n] = temp; } } }
······持续更新中