Java教程
[算法艺术]数组-Java语言
文章目录
- 算法是一门艺术！
- 1.旋转数组
- 题目大意：
- 多次反转：
- 环形旋转：
- 使用临时数组：
- 2.存在重复元素
- 题目大意：
- 排序：
- 哈希表：
- 3.只出现一次的数字
- 题目大意：
- 哈希表
- 位运算
- 4.两个数组的交集 II
- 题目大意：
- 排序+双指针：
- 5.加一
- 题目大意：
- 6.移动零
- 题目大意：
- 一次遍历：
- 两次遍历：
- 7.两数之和
- 题目大意：
- 暴力枚举：
- 哈希表：
- 8.有效的数独
- 题目大意：
- 暴力枚举：
- 位运算：
- 9. 旋转图像
- 题目大意：
- 上上下下左右左右偏偏：
- 跳棋式：
算法是一门艺术！
1.旋转数组
Leetcode189.
Given an array, rotate the array to the right by k steps, where k is non-negative.
题目大意：
给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。示例 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];
}
}
}
2.存在重复元素
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.
题目大意：
给定一个整数数组，判断是否存在重复元素。 如果存在一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。示例 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）
3.只出现一次的数字
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）
位运算
思路：
异或规律：
- a^a=0；自己和自己异或等于0
- a^0=a；任何数字和0异或还等于他自己
- a^ b ^ c=a ^ c ^ b；异或运算具有交换律
题目中出现一次的数字只有一个，其余数字出现两次，异或后，出现两次的数字为0，出现一次的等于它自己。
AC代码：
class Solution {
public int singleNumber(int[] nums) {
int res = 0;
for(int i : nums){
res ^= i;
}
return res;
}
}
时间复杂度：O（N）(遍历数组)
空间复杂度：O（1）
4.两个数组的交集 II
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;
}
}
5.加一
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;
}
}
6.移动零
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.
题目大意：
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。示例:
输入: [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;
}
}
}
7.两数之和
Leetcode1.
Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
题目大意：
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 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[]{};
}
}
8.有效的数独
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.
题目大意：
判断一个 9x9 的数独是否有效。验证已经填入的数字是否有效即可。数字 1-9 在每一行只能出现一次。数字 1-9 在每一列只能出现一次。数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。示例 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;
}
}
9. 旋转图像
Leetcode48.
You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).
题目大意：
给定一个 n × n 的二维矩阵 matrix 表示一个图像。将图像顺时针旋转 90 度。示例 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;
}
}
}
······持续更新中
-
大厂数据结构与算法教程：入门级详解12-26
-
大厂算法与数据结构教程：新手入门指南12-26
-
Python编程入门指南12-26
-
数据结构高级教程：新手入门及初级提升指南12-26
-
并查集入门教程：从零开始学会并查集12-26
-
大厂数据结构与算法入门指南12-26
-
大厂算法与数据结构入门教程12-26
-
二叉树入门教程：轻松掌握基础概念与操作12-26
-
初学者指南：轻松掌握链表12-26
-
平衡树入门教程：轻松理解与应用12-26
-
数据结构入门教程：轻松掌握基本概念与应用12-26
-
数据结构与算法入门指南12-26
-
算法面试攻略：从零开始的入门指南12-26
-
Python编程基础：变量与类型12-26
-
算法与数据结构高级：新手入门教程12-26
