数据结构——数组
直接解
【剑指offer】03.数组中重复的数字
//03. 数组中重复的数字
// 找出数组中重复的数字。
// 力扣
// 在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。
// 数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每
// 个数字重复了几次。请找出数组中任意一个重复的数字。
// 牛客
// 在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数
// 字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次
// 。请找出数组中第一个重复的数字。 例如，如果输入长度为7的数组{2,3,
// 1,0,2,5,3}，那么对应的输出是第一个重复的数字2。
// 返回描述：
// 如果数组中有重复的数字，函数返回true，否则返回false。
// 如果数组中有重复的数字，把重复的数字放到参数duplication[0]中。（ps
// :duplication已经初始化，可以直接赋值使用。）
排序法
把数组排成升序，再遍历找相邻重复数
// 时间复杂度 O(nlogn)：3 ms, 在所有 Java 提交中击败了59.39%的用户
// 空间复杂度 O(1)：45.9 MB, 在所有 Java 提交中击败了96.69%的用户
import java.util.Arsrays;
class Solution {
public int findRepeatNumber(int[] nums) {
if (nums == null || nums.length <= 0) {
return -1;
}
Arrays.sort(nums);
for (int i=0; i < nums.length-1; i++) {
if (nums[i] == nums[i+1]) {
return nums[i];
}
}
return -1;
}
}
集合法
很粗暴，直接存hashset，存不进就是遇到重复了
// 时间复杂度 O(n)： 5 ms, 在所有 Java 提交中击败了49.49%的用户
// 空间复杂度 O(n)：48.1 MB, 在所有 Java 提交中击败了23.18%的用户
import java.util.*;
class Solution {
public int findRepeatNumber(int[] nums) {
Set<Integer> set = new HashSet<>();
int result = -1;
if (nums == null || nums.length <= 0) {
return result;
}
for (int i=0; i <= nums.length-1; i++) {
if (!set.add(nums[i])) { // 如果存不进hashset，说明遇到重复
result = nums[i];
return result; // 返回遍历数
}
}
return result;
}
}
// 牛客
// 牛客题目要求时间复杂度 O(N)，空间复杂度 O(1)，因此比较严格一点
// 运行时间 14ms
// 占用内存 10048KB
import java.util.HashSet;
public class Solution {
// Parameters:
// numbers: an array of integers
// length: the length of array numbers
// duplication: (Output) the duplicated number in the array number,length of duplication array is 1,so using duplication[0] = ? in implementation;
// Here duplication like pointor in C/C++, duplication[0] equal *duplication in C/C++
// 这里要特别注意~返回任意重复的一个，赋值duplication[0]
// Return value: true if the input is valid, and there are some duplications in the array number
// otherwise false
public boolean duplicate(int numbers[],int length,int [] duplication) {
if (length == 0)
return false;
HashSet<Integer> set = new HashSet<>();
for (int i = 0; i < length; i++) {
if (!set.add(numbers[i])) {
duplication[0] = numbers[i];
return true;
}
}
return false;
}
}
原地置换
找重复的数，且数取值在数组长度范围内，大部分数肯定是不重复的，将它们摆放成数字和索引相同的数组，即{0, 2, 3, 1}我们希望摆成{0, 1, 2, 3}。如果数组有两个2，那么原来2的位置有一个2，就会发现重复。
// 时间复杂度 O(n)：1 ms, 在所有 Java 提交中击败了90.57%的用户
// 空间复杂度 O(1)：45.8 MB, 在所有 Java 提交中击败了98.14%的用户
class Solution {
public int findRepeatNumber(int[] nums) {
if (nums == null || nums.length <= 0) {
return -1;
}
int i = 0; // 初始化索引i
while (i <= nums.length-1) {
// 若遍历数与索引不等
if (nums[i] != i) {
// System.out.println(nums[i]);
// 若遍历数与以遍历数为索引的对应数相等（遇重复）
if (nums[i] == nums[nums[i]]) {
return nums[nums[i]]; // 直接返回结果
}
//交换：遍历数与以遍历数为索引的对应数
swap(nums, i);
} // (交换后)确认遍历数与索引相等之后，再右移索引
else {
i++;
}
}
return -1;
}
// 定义交换方法
private void swap(int[] list, int i) {
int temp = list[list[i]];
list[list[i]] = list[i];
list[i] = temp;
}
}
// 牛客
import java.util.HashSet;
public class Solution {
// Parameters:
// numbers: an array of integers
// length: the length of array numbers
// duplication: (Output) the duplicated number in the array number,length of duplication array is 1,so using duplication[0] = ? in implementation;
// Here duplication like pointor in C/C++, duplication[0] equal *duplication in C/C++
// 这里要特别注意~返回任意重复的一个，赋值duplication[0]
// Return value: true if the input is valid, and there are some duplications in the array number
// otherwise false
public boolean duplicate(int numbers[],int length,int [] duplication) {
if (length == 0)
return false;
int i = 0;
while (i < length) {
if (numbers[i] != i){
if (numbers[i] == numbers[numbers[i]]) {
duplication[0] = numbers[numbers[i]];
return true;
}
swap(numbers, i);
}
else
i++;
}
return false;
}
// 使得numbers[i]和numbers[numbers[i]]交换
private void swap(int[] numbers, int i) {
int temp = numbers[numbers[i]];
numbers[numbers[i]] = numbers[i];
numbers[i] = temp;
}
}
【剑指offer】04. 二维数组中的查找
题目描述
// 04. 二维数组中的查找
// 在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，
// 每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的
// 一个二维数组和一个整数，判断数组中是否含有该整数。
// 限制：
// 0 <= n <= 1000
// 0 <= m <= 1000
题解
// 时间复杂度 O(M + N): 18 ms
// 空间复杂度 O(1): 43.1 MB
// 从矩阵右上角开始遍历，则左边的数一定比右边的数小，
// 下边的数一定比上面的数大。
// 比较遍历数和target。
// 若遍历数大，target小，说明target在遍历数左边，遍历位置左移。
// 如果遍历数小，target大，说明target在遍历数下面，遍历位置下移
class Solution {
public boolean findNumberIn2DArray(int[][] matrix, int target) {
// 排除特殊情况
if (matrix == null || matrix.length <= 0 || matrix[0].length <= 0) {
return false;
}
// 取matrix的行和列
int rows = matrix.length, cols = matrix[0].length;
// 初始化遍历起始点索引，起始点为右上角
int i = 0, j = cols-1;
while (i <= rows-1 && j >= 0) {
System.out.println(i + " " + j);
if (matrix[i][j] == target) { return true;}
if (matrix[i][j] < target) {
i++;
}
// 防止之前i移动在先，造成越界，加一个i的不越界判定
if (i <= rows-1 && matrix[i][j] > target) {
j--;
}
}
return false;
}
}
【剑指offer】29. 顺时针打印矩阵
题目描述
// 力扣
// 输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。
// 牛客
// 输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字
// ，例如，如果输入如下4 X 4矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14
// 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.
题解
// 牛客
// printRes函数中，下行和左列要加一个row1和row2不相等的判断和
// col1和col2的判断，防止重复遍历。而matrix = [[1,2,3],[4,5,6],[7,8,9]]
// 中的实例比较特殊，我们需要遍历中心的元素5，所以我们在printRes函数
// 中的前两个for循环都不设置row1和row2相等的判断和col1和col2的判断。
// 运行时间：16ms
// 占用内存：9752k
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> printMatrix(int [][] matrix) {
int row1 = 0; // 行上边界
int row2= matrix.length - 1; // 行下边界
int col1 = 0; // 列左边界
int col2 = matrix[0].length - 1; // 列右边界
ArrayList<Integer> res = new ArrayList<>();
while (row1 <= row2 && col1 <= col2) {
// 一个while循环遍历一圈
res = printRes(matrix, row1, row2, col1, col2, res);
row1++; row2--; col1++; col2--; // 缩圈
}
return res;
}
private ArrayList<Integer> printRes(int[][] matrix, int row1, int row2, int col1, int col2, ArrayList<Integer> res) {
// 上行
for (int i = col1; i <= col2; i++) {
res.add(matrix[row1][i]);
}
// 右列(右列要从row1+1位置开始,因为row1位置以前的元素在上行遍历过)
for (int i = row1 + 1; i <= row2; i++) {
res.add(matrix[i][col2]);
}
// 下行(下行要从col2-1开始,col2以前的位置被右列遍历过)
if (row1 != row2) {
for (int i = col2 - 1; i >= col1; i--)
res.add(matrix[row2][i]);
}
// 左列(左列在空间位置上,row2以下和row1以上的位置都被遍历过)
if (col1 != col2) {
for (int i = row2 - 1; i > row1; i--)
res.add(matrix[i][col1]);
}
return res;
}
}
// 力扣
// 力扣还需要考虑ArrayList到int[]的转换
// 执行用时：5 ms, 在所有 Java 提交中击败了9.34%的用户
// 内存消耗：39.5 MB, 在所有 Java 提交中击败了94.34%的用户
class Solution {
public int[] spiralOrder(int[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return new int[0];
}
int row1 = 0; // 行上边界
int row2= matrix.length - 1; // 行下边界
int col1 = 0; // 列左边界
int col2 = matrix[0].length - 1; // 列右边界
ArrayList<Integer> res = new ArrayList<>();
while (row1 <= row2 && col1 <= col2) {
res = printRes(matrix, row1, row2, col1, col2, res);
row1++; row2--; col1++; col2--; // 缩圈
}
int[] result = toIntList(res);
return result;
}
private ArrayList<Integer> printRes(int[][] matrix, int row1, int row2, int col1, int col2, ArrayList<Integer> res) {
for (int i = col1; i <= col2; i++) {
res.add(matrix[row1][i]);
}
for (int i = row1 + 1; i <= row2; i++) {
res.add(matrix[i][col2]);
}
if (row1 != row2) {
for (int i = col2 - 1; i >= col1; i--)
res.add(matrix[row2][i]);
}
if (col1 != col2) {
for (int i = row2 - 1; i > row1; i--)
res.add(matrix[i][col1]);
}
return res;
}
private int[] toIntList(ArrayList<Integer> res) {
int[] result = new int[res.size()];
for (int i = 0; i < res.size(); i++) {
result[i] = res.get(i);
}
return result;
}
}
// 更好的办法是直接用int[] 存储，中间不经过arraylist
// 执行用时：1 ms, 在所有 Java 提交中击败了97.37%的用户
// 内存消耗：39.5 MB, 在所有 Java 提交中击败了85.60%的用户
class Solution {
int[] res;
int t = 0;
public int[] spiralOrder(int[][] matrix) {
if (matrix.length == 0)
return new int[0];
int row1 = 0;
int row2 = matrix.length - 1;
int col1 = 0;
int col2 = matrix[0].length - 1;
this.res = new int[(row2 + 1) * (col2 + 1)];
while (row1 <= row2 && col1 <= col2) {
cyclePrint(matrix, row1, row2, col1, col2);
row1++;row2--;col1++;col2--;
}
return res;
}
private void cyclePrint(int[][] matrix, int row1, int row2, int col1, int col2) {
for (int i = col1; i <= col2; i++) { // 上边
res[t++] = matrix[row1][i];
}
for (int i = row1 + 1; i <= row2; i++) { // 右边
res[t++] = matrix[i][col2];
}
if (row1 != row2) {
for (int i = col2 - 1; i >= col1; i--) { // 下边
res[t++] = matrix[row2][i];
}
}
if (col1 != col2) {
for (int i = row2 - 1; i > row1; i--) { // 左边
res[t++] = matrix[i][col1];
}
}
}
}
【剑指offer】39. 数组中出现次数超过一半的数字
题目描述
// 39. 数组中出现次数超过一半的数字
// 力扣
// 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
// 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
// 牛客
// 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例
// 如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现
// 了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
题解
/// 直接法 /
// 排序，然后逐个遍历数
// 直接法无法在牛客通过
// 力扣
//
// 执行用时：3 ms, 在所有 Java 提交中击败了34.81%的用户
// 内存消耗：41.7 MB, 在所有 Java 提交中击败了59.53%的用户
class Solution {
public int majorityElement(int[] nums) {
if (nums.length == 0)
return -1;
if (nums.length == 1)
return nums[0];
Arrays.sort(nums);
int len = nums.length / 2 + 1;
int count = 1;
int i = 0;
while (i < nums.length) {
if (nums[i] != nums[i + 1])
count = 1;
else {
count++;
i++;
}
if (count >= len)
break;
}
return nums[i];
}
}
多数投票法我做了个ppt放在代码下面，感兴趣可以看看。
多数投票法
// 比较好的方法
// 如果某个数字符合条件，那么它出现的次数就比其他所有数字出现的次数加起来还要多。
// 具体可以看看这个 https://www.zhihu.com/question/49973163/answer/617122734
// 力扣
// 不验证的话，就是取出现次数最多的数字
// 执行用时：1 ms, 在所有 Java 提交中击败了99.99%的用户
// 内存消耗：41.9 MB, 在所有 Java 提交中击败了38.26%的用户
class Solution {
public int majorityElement(int[] nums) {
int max = nums[0];
for (int i = 1, count = 1; i < nums.length; i++) {
if (nums[i] == max)
count++;
else
count--;
if (count == 0) {
max = nums[i];
count = 1;
}
}
return max;
}
}
// 力扣
// 加上验证环节
// 执行用时：2 ms, 在所有 Java 提交中击败了60.11%的用户
// 内存消耗：41.8 MB, 在所有 Java 提交中击败了44.96%的用户
class Solution {
public int majorityElement(int[] nums) {
int max = nums[0];
for (int i = 1, count = 1; i < nums.length; i++) {
if (nums[i] == max)
count++;
else
count--;
if (count == 0) {
max = nums[i];
count = 1;
}
}
// 验证环节
int count = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] == max)
count++;
}
return count >= nums.length / 2 + 1 ? max : 0;
}
}
// 牛客
// 牛客必须要有验证环节，否则无法通过，所以牛客要力扣要严格（严谨）
// 运行时间：12ms
// 占用内存：9556k
public class Solution {
public int MoreThanHalfNum_Solution(int [] array) {
int max = array[0];
for (int i = 1, count = 1; i < array.length; i++) {
if (array[i] == max)
count++;
else
count--;
if (count <= 0) {
max = array[i];
count = 1;
}
}
// 验证环节
int count = 0;
for (int i = 0; i < array.length; i++) {
if (array[i] == max)
count++;
}
return count >= array.length / 2 + 1 ? max : 0;
}
}
【剑指offer】40. 最小的k个数
题目描述
// 力扣
// 输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、
// 2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
// 牛客
// 输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字
// ，则最小的4个数字是1,2,3,4。
题解
// 暴力法 //
// 力扣
// 暴力法，能通过但没有意义
// 执行用时：8 ms, 在所有 Java 提交中击败了64.97%的用户
// 内存消耗：40 MB, 在所有 Java 提交中击败了17.80%的用户
import java.util.Arrays;
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
int[] res = new int[k];
Arrays.sort(arr);
for (int i = 0; i < k; i++) {
res[i] = arr[i];
}
return res;
}
}
如果用数组表示堆的话，根据层序顺序标号规则，将层序标号对应到数组索引中，那么在数组索引中找二叉树左右结点可以通过如下规律：找结点的左节点：索引2，找结点的右结点：索引2+1，找结点的父结点：索引 / 2（整数除法，要去除小数点）。
/// 最大堆法 ///
// 比较好的方法
// 牛客
// 运行时间：15ms
// 占用内存：9944k
import java.util.ArrayList;
import java.util.PriorityQueue; // 利用优先队列构建堆
import java.util.Comparator; // 比较器
public class Solution {
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
if (k > input.length || k < 0) // 如果k值有问题，返回空数组
return new ArrayList<>();
// 优先队列默认是最小堆（最小值置顶），将其修改成最大堆（最大值置顶）
// 得到构建好的最大堆maxHeap
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2.compareTo(o1);
}
});
// for循环遍历input中的元素，将其放入num中
for (int num: input) {
maxHeap.add(num);
// 由于是最大堆，所以最大值一定会被置顶
// 当堆中元素超过k（达到k+1）了，那么置顶元素一定比其余k个数大，
// 将其弹出。input所有元素被遍历过，且在堆中被比较过大小，
// 所以能在堆中留下的k个数就是input里最小的k个数。
if (maxHeap.size() > k)
maxHeap.poll();
}
// 将堆以ArrayList格式返回
return new ArrayList<>(maxHeap);
}
}
// 力扣
// 执行用时：25 ms, 在所有 Java 提交中击败了13.48%的用户
// 内存消耗：39.6 MB, 在所有 Java 提交中击败了77.55%的用户
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Comparator;
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
if (k > arr.length || k <= 0)
return new int[0];
PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2.compareTo(o1);
}
});
for (int num: arr) {
maxHeap.add(num);
if (maxHeap.size() > k)
maxHeap.poll();
}
int[] res = new int[k];
ArrayList<Integer> kmin = new ArrayList<>(maxHeap);
toResList(kmin, res, k);
return res;
}
public void toResList(ArrayList<Integer> kmin, int[] res, int k) {
for (int i = 0; i < kmin.size(); i++) {
res[i] = kmin.get(i);
}
}
}
// 力扣
// 执行用时：27 ms, 在所有 Java 提交中击败了11.67%的用户
// 内存消耗：40.1 MB, 在所有 Java 提交中击败了8.06%的用户
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Comparator;
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
if (k > arr.length || k <= 0)
return new int[0];
PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2.compareTo(o1);
}
});
for (int num: arr) {
maxHeap.add(num);
if (maxHeap.size() > k)
maxHeap.poll();
}
int[] res = new int[k];
toResList(maxHeap, res);
return res;
}
public void toResList(PriorityQueue<Integer> maxHeap, int[] res) {
int i = 0;
for (int num : maxHeap) {
res[i++] = num;
}
}
}
/ 快速选择法 /
// 快速选择和快排很类似
// 牛客
// 运行时间：14ms
// 占用内存：9924k
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
ArrayList<Integer> res = new ArrayList<>();
if (k > input.length || k <= 0)
return res;
findKthSmallest(input, k); // 快选主函数
// 此时input前k个元素即为最小的k个元素
for (int i = 0; i < k; i++)
res.add(input[i]); // 将前k个元素存入res中
return res;
}
// 快速选择函数
// 找k个最小值
public void findKthSmallest(int[] input, int k) {
int low = 0, high = input.length - 1; // 初始化左右边界
while (low < high) {
int size = partition(input, low, high);
if (size == k) // 直到size等于k，停止循环
break;
if (size > k) // 最小的k个数一定在前size个数中
high = size - 1; // 右边界high左移
else // size < k // 在右侧数组中继续找最小的k个数
low = size + 1; // 左边界low右移
}
}
// 切分函数，我们希望使数组切分值的左边都是小元素，右边都是大元素
private int partition(int[] input, int low, int high) {
int split = input[low]; // 切分值初始化
int i = low, j = high + 1; // 双指针i，j遍历input元素
while (true) {
// i从左往右移，遍历到不小于split的元素为止
while (i != high && input[++i] < split);
// j从右往左移，遍历到不大于split的元素位置
while (j != low && input[--j] > split);
if (i >= j)
break;
// input[i]比split大,input[j]比split小，交换位置
swap(input, i, j);
}
swap(input, low, j); // input[j]比split值本身要小，交换位置
return j; // 返回
}
// 交换函数
private void swap(int[] input, int i, int j) {
int t = input[i];
input[i] = input[j];
input[j] = t;
}
}
// 力扣
// 执行用时：3 ms, 在所有 Java 提交中击败了83.07%的用户
// 内存消耗：39.8 MB, 在所有 Java 提交中击败了51.36%的用户
import java.util.ArrayList;
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
if (k > arr.length || k <= 0)
return new int[0];
findKSmallest(arr, k);
int[] res = new int[k];
for (int i = 0; i < k; i++) {
res[i] = arr[i];
}
return res;
}
public void findKSmallest(int[] arr, int k) {
int low = 0, high = arr.length - 1;
while (true) {
int size = partition(arr, low, high);
if (size == k)
break;
if (size > k)
high = size - 1;
else
low = size + 1;
}
}
private int partition (int[] arr, int low, int high) {
int split = arr[low];
int i = low, j = high + 1;
while (true) {
while (i < high && arr[++i] < split);
while (j > low && arr[--j] > split);
if (i >= j)
break;
swap(arr, i, j);
}
swap(arr, low, j);
return j;
}
private void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
【剑指offer】45. 把数组排成最小的数
题目描述
// 45. 把数组排成最小的数
// 力扣
// 输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，
// 打印能拼接出的所有数字中最小的一个。
// 牛客
// 输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印
// 能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则
// 打印出这三个数字能排成的最小数字为321323。
题解
// 力扣
// 执行用时：6 ms, 在所有 Java 提交中击败了77.89%的用户
// 内存消耗：38 MB, 在所有 Java 提交中击败了60.99%的用户
import java.util.Arrays;
class Solution {
public String minNumber(int[] nums) {
if (nums == null || nums.length == 0)
return "";
int len = nums.length; // 取数组nums的长度，即为字符组的长度
String res = ""; // 答案存储在res中
String[] strlist = new String[len]; // 创建与nums同尺寸的String list
for (int i = 0; i < len; i++)
strlist[i] = Integer.toString(nums[i]); // 转字符串后排入String list
// 给字符组list排序，lambda表达式来自定义比较器。
// 原本是比较字符组每一个元素（字母）的大小来升序，
// 现在是比较字符组每一个元素加起来组成的字符的大小来升序
Arrays.sort(strlist, (s1, s2) -> (s1 + s2).compareTo(s2 + s1));
// 排序后，将list所有元素按顺序存入res
for (String s : strlist)
res += s;
return res; // 最后返回res
}
}
// 牛客
// 运行时间：100ms
// 占用内存：15052KB
import java.util.ArrayList;
import java.util.Arrays;
public class Solution {
public String PrintMinNumber(int [] numbers) {
if (numbers == null || numbers.length == 0)
return "";
String res = "";
int len = numbers.length;
String[] strList = new String[len];
for (int i = 0; i < len; i++)
strList[i] = Integer.toString(numbers[i]);
Arrays.sort(strList, (s1, s2) -> (s1 + s2).compareTo(s2 + s1));
for (String s: strList)
res += s;
return res;
}
}
// 牛客
// 比较器修改的另一种写法
// 运行时间：14ms
// 占用内存：9988KB
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
public class Solution {
public String PrintMinNumber(int [] numbers) {
if (numbers == null || numbers.length == 0)
return "";
String res = "";
int len = numbers.length;
String[] strList = new String[len];
for (int i = 0; i < len; i++)
strList[i] = Integer.toString(numbers[i]);
Arrays.sort(strList, new Comparator<String>() {
@Override
public int compare(String s1, String s2) {
return (s1 + s2).compareTo(s2 + s1);
}
});
for (String s: strList)
res += s;
return res;
}
}
【剑指offer】59. 滑动窗口的最大值
题目描述
// 59. 滑动窗口的最大值
// 力扣
// 给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。
// 牛客
// 给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例
// 如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个
// 滑动窗口，他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,
// 1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}，
// {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {
// 2,3,4,2,6,[2,5,1]}。
// 窗口大于数组长度的时候，返回空
题解
最大堆法
// 最大堆
// 牛客
// 推荐方法。
// 构建最大堆maxHeap，构建答案保存数组res，
// 先把窗口范围size内的元素放入maxHeap，之后堆顶元素（最大值）放入res，
// 然后构建左指针i，右指针j，for循环右移两个指针，之前的左指针遍历元素
// 在maxHeap中去掉，加入右指针的新遍历元素，构成新的maxHeap（窗口遍历元素）
// 再次把堆顶最大值放入res，如此循环。
// 运行时间：14ms，超过75.10%用Java提交的代码
// 占用内存：9744KB，超过9.76%用Java提交的代码
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Comparator;
public class Solution {
public ArrayList<Integer> maxInWindows(int [] num, int size) {
ArrayList<Integer> res = new ArrayList<Integer>();
if (size > num.length || size < 1)
return res;
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2.compareTo(o1);
}
});
for (int i = 0; i < size; i++) {
maxHeap.add(num[i]);
}
res.add(maxHeap.peek());
for (int i = 0, j = i + size; j < num.length; i++, j++) {
maxHeap.remove(num[i]);
maxHeap.add(num[j]);
res.add(maxHeap.peek());
}
return res;
}
}
// 力扣
// 执行用时：93 ms, 在所有 Java 提交中击败了5.11%的用户
// 内存消耗：46.4 MB, 在所有 Java 提交中击败了74.46%的用户
class Solution {
public int[] maxSlidingWindow(int[] num, int size) {
ArrayList<Integer> res = new ArrayList<Integer>();
if (size > num.length || size < 1)
return toIntList(res);
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2.compareTo(o1);
}
});
for (int i = 0; i < size; i++) {
maxHeap.add(num[i]);
}
res.add(maxHeap.peek());
for (int i = 0, j = i + size; j < num.length; i++, j++) {
maxHeap.remove(num[i]);
maxHeap.add(num[j]);
res.add(maxHeap.peek());
}
return toIntList(res);
}
private int[] toIntList(ArrayList<Integer> res) {
int[] result = new int[res.size()];
for (int i = 0; i < result.length; i++) {
result[i] = res.get(i);
}
return result;
}
}
队列方法
// 双端队列
// 双端队列法旨在用双端队列deque来维护窗口元素特别是窗口的最大值元素。
//
// 先排除特殊情况，如果size比nums长度还大，或者size比0小，直接返回空数组。
//
// 定义双端队列deque（用链表代替），定义相应大小的答案保存数组res，
// 第一个for循环将nums中的前size个元素nums[i]从尾部存入deque。由于我们不需要
// deque窗口元素中的所有值，而是只要窗口元素中的最大值，所以如果deque不
// 为空且将要存入的nums[i]，比deque的尾部元素要大，在nums[i]存入deque之前，
// 我们将deque尾部元素循环移除，直到deque尾部元素大于等于nums[i]，
// 或者直到deque元素已经排空了，这时候再将nums[i]存入，这样子deque的头部
// 元素一定是deque中的最大值元素，并且deque头部到尾部的元素呈现降序的排序。
// 第一个for循环起初始化窗口的作用，将nums中前size个元素放入deque并规范成
// 降序链表，我们可以轻松从头部取到窗口最大值。
//
// 定义res遍历索引j，初始化为0，如果deque初始化好了（非空），将deque的
// 头部元素（窗口最大值）存入res[0]中，j右移。
//
// 第二个for循环，从nums的size索引开始遍历nums的元素nums[i]，则nums[i]
// 为窗口的右索引元素，则窗口的左索引元素为nums[i - size]，在循环内，
// 条件判断：如果deque的头部元素（窗口最大值）等于左索引元素，则将
// deque中的头部元素去除。
// 然后调用while循环，与第一个for循环初始化deque时相似，如果deque不为空
// 且将要存入的nums[i]，比deque的尾部元素要大，在nums[i]存入deque之前，
// 我们将deque尾部元素循环移除，直到deque尾部元素大于等于nums[i]，
// 或者直到deque元素已经排空了，这时候再将nums[i]存入。窗口完成一格移动，
// 将res[j]位置赋值为deque的头部元素（窗口最大值），j右移。
// 第二个for循环，主要是完成窗口移动的过程，通过双端链表和插入元素前的
// 贪心删除元素，来维护一个降序的双端链表，所以头部元素就是窗口最大值。
//
// 如此循环，最后返回res即可。
//
// 执行用时：15 ms, 在所有 Java 提交中击败了48.97%的用户
// 内存消耗：47.5 MB, 在所有 Java 提交中击败了12.75%的用户
import java.util.LinkedList;
class Solution {
public int[] maxSlidingWindow(int[] num, int size) {
if (size > num.length || size < 1)
return new int[0];
Deque<Integer> queue = new LinkedList<>();
int[] res = new int[num.length - size + 1];
for (int i = 0; i < size; i++) {
while (!queue.isEmpty() && queue.peekLast() < num[i]) {
queue.removeLast();
}
queue.addLast(num[i]);
}
int j = 0;
if (!queue.isEmpty())
res[j++] = queue.peekFirst();
for (int i = size; i < num.length; i++) {
if (!queue.isEmpty() && queue.peekFirst() == num[i - size]) {
queue.removeFirst();
}
while (!queue.isEmpty() && queue.peekLast() < num[i]) {
queue.removeLast();
}
queue.addLast(num[i]);
res[j++] = queue.peekFirst();
}
return res;
}
}
【剑指offer】61. 扑克牌中的顺子
题目描述
// 61. 扑克牌中的顺子
// 力扣
// 从扑克牌中随机抽5张牌，判断是不是一个顺子，即这5张牌是不是连续的
// 。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，
// 可以看成任意数字。A 不能视为 14。
// 牛客
// LL今天心情特别好,因为他去买了一副扑克牌,发现里面居然有2个大王,2个小王
// (一副牌原本是54张^_^)...他随机从中抽出了5张牌,想测测自己的手气,看看能
// 不能抽到顺子,如果抽到的话,他决定去买体育彩票,嘿嘿！！“红心A,黑桃3,小王
// ,大王,方片5”,“Oh My God!”不是顺子.....LL不高兴了,他想了想,决定大\小 王
// 可以看成任何数字,并且A看作1,J为11,Q为12,K为13。上面的5张牌就可以变成“1
// ,2,3,4,5”(大小王分别看作2和4),“So Lucky!”。LL决定去买体育彩票啦。 现在
// ,要求你使用这幅牌模拟上面的过程,然后告诉我们LL的运气如何， 如果牌能组成
// 顺子就输出true，否则就输出false。为了方便起见,你可以认为大小王是0。
题解
// 力扣
// 先排除特殊情况，nums中不足5个牌直接false，
// 创建计数数组pokerList，记录每种牌出现的次数，有14种牌所以长度为14，
// 创建最大最小值max和min，用于记录5张牌的最大最小值，
// for循环遍历手牌num，出现次数累计一次pokerList[num]++，
// 如果num是0，跳过判断遍历下一张牌，
// 不是0的话，如果出现次数pokerList[num]大于1，说明有对子，有对子的牌
// 无法构成顺子，直接false。
// 以上不满足的话，如果num小于min，把min更新为num，
// 如果num大于max，把max更新为num。
// 循环结束，我们可以得到手牌中的最大值max和最小值min，
// 在没有重复对子的前提下，如果max-min的值小于等于4，则必定构成顺子，
// 返回true。比如max是5，min是1，说明其他三张牌一定是4 3 2和 0 这四种
// 情况，所以一定构成顺子。
// 执行用时：1 ms, 在所有 Java 提交中击败了91.68%的用户
// 内存消耗：35.8 MB, 在所有 Java 提交中击败了59.10%的用户
class Solution {
public boolean isStraight(int[] nums) {
if (nums.length != 5)
return false;
int[] pokerList = new int[14];
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for (int num: nums) {
pokerList[num]++;
if (num == 0)
continue;
else if (pokerList[num] > 1)
return false;
if (num < min)
min = num;
if (num > max)
max = num;
}
return (max - min <= 4);
}
}
// 牛客
// 运行时间：13ms,超过72.54%用Java提交的代码
// 占用内存：9600KB,超过6.93%用Java提交的代码
public class Solution {
public boolean IsContinuous(int [] numbers) {
if (numbers.length != 5)
return false;
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
int[] poker = new int[14];
for (int num: numbers) {
poker[num]++;
if (num == 0)
continue;
else if (poker[num] > 1)
return false;
if (num < min)
min = num;
if (num > max)
max = num;
}
return (max - min <= 4);
}
}
【剑指offer】66. 构建乘积数组
题目描述
// 66. 构建乘积数组
// 力扣
// 给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中 B[i]
// 的值是数组 A 中除了下标 i 以外的元素的积, 即 B[i]=A[0]×A[1]×…×A[i-1]
// ×A[i+1]×…×A[n-1]。不能使用除法。
// 牛客
// 给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1],其中B中的元素
// B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1]。不能使用除法。（注意：规
// 定B[0] = A[1] * A[2] * ... * A[n-1]，B[n-1] = A[0] * A[1] * ... * A[n-
// 2];）
// 对于A长度为1的情况，B无意义，故而无法构建，因此该情况不会存在。
题解
暴力 ///
// 【伪解法】
// 力扣
// 无法通过
class Solution {
public int[] constructArr(int[] a) {
int[] b = new int[a.length];
for (int i = 0; i < b.length; i++) {
int num = 1;
for (int j = 0; j < a.length; j++) {
if (j == i)
continue;
num *= a[j];
}
b[i] = num;
}
return b;
}
}
// 力扣
// 可以看着实例来理解
// 输入: [1,2,3,4,5]
// 输出: [120,60,40,30,24]
//
// 计算b[i]是除a[i]以外所有的a中元素的乘积，
// 我们可以把i看做一个分界线，在i移动的时候，把a中的元素分成了
// 左右两边，我们按照左右两半边来分别进行计算。
// 例如：实例中乘积为b[3]=30的a元素，包括1 2 3和5，左半边就是1 2 3。
// 乘积为b[2]=40的a元素，包括1 2 4和5，左半边是1 2
// 乘积为b[1]=60的a元素，包括1 3 4和5，左半边是1
// 可以发现，左半边其实在逐渐往一个方向累乘，右半边也是。
// 我们只需将两边分开累乘赋值给b，即可高效地完成运算。
//
// 第一个for循环，从左往右遍历a和b，索引记为i，遍历到len-2为止，
// a[0]对b[0]没有贡献， 我们将b[0]初始化为1，
// 将a[i]累乘到product中，将product赋给b[i+1]，完成左半边的累乘。
//
// 第二个for循环，从右往左遍历a和b，遍历到1为止，a[i]累乘到product，
// b由于之前已经计算过了，所以product再累乘到b[i - 1]元素。
// 左右半边计算完，则b元素就累乘完了，直接返回b。
// 执行用时：2 ms, 在所有 Java 提交中击败了80.14%的用户
// 内存消耗：51.3 MB, 在所有 Java 提交中击败了26.55%的用户
class Solution {
public int[] constructArr(int[] a) {
if (a == null || a.length == 0)
return new int[0];
int len = a.length;
int[] b = new int[len];
int product = 1;
b[0] = product;
for (int i = 0; i <= len - 2; i++) {
product *= a[i];
b[i + 1] = product;
}
product = 1;
for (int i = len - 1; i >= 1; i--) {
product *= a[i];
b[i - 1] *= product;
}
return b;
}
}
// 牛客
// 运行时间：9ms超过99.07%用Java提交的代码
// 占用内存：9732KB超过2.41%用Java提交的代码
import java.util.ArrayList;
public class Solution {
public int[] multiply(int[] A) {
if (A == null || A.length == 0)
return new int[0];
int len = A.length;
int[] B = new int[len];
int product = 1;
B[0] = 1;
for (int i = 0; i <= len - 2; i++) {
product *= A[i];
B[i + 1] = product;
}
product = 1;
for (int i = len - 1; i >= 1; i--) {
product *= A[i];
B[i - 1] *= product;
}
return B;
}
}
特殊解——动态规划
【剑指offer】10.1 斐波那契数列
题目描述
// 力扣
// 写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项。
// 斐波那契数列的定义如下：
// F(0) = 0, F(1) = 1
// F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
// 斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两
// 数相加而得出。
// 答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008
// ，请返回 1。
题解
// 牛客
暴力递归法 /
// 递归可以，但是很暴力
public class Solution {
public int Fibonacci(int n) {
if (n == 1)
return 1;
if (n == 0)
return 0;
// 根据定义直接递归法
return Fibonacci(n - 1) + Fibonacci(n - 2);
}
}
// 动态规划 /
public class Solution {
public int Fibonacci(int n) {
if (n <= 1) {
return n;
}
int[] f = new int[n + 1];
f[1] = 1;
// 从0,1开始，从头推到f[n]
for (int i = 2; i <= n; i++) {
f[i] = f[i - 2] + f[i - 1]; // 循环递推
}
return f[n];
}
}
public class Solution {
public int Fibonacci(int n) {
if (n <= 1) {
return n;
}
int pre1 = 0, pre2 = 1;
int f = 0;
for (int i = 2; i <= n; i++) {
f = pre2 + pre1;
pre1 = pre2;
pre2 = f;
}
return f;
}
}
// 力扣
// 力扣如果用递归方法会发现直接报时间复杂度超了
/// 动态规划
// 执行用时：0 ms , 在所有 Java 提交中击败了 100.00% 的用户
// 内存消耗： 35.2 MB, 在所有 Java 提交中击败了83.53%的用户
class Solution {
public int fib(int n) {
int a = 0, b = 1, sum;
for (int i = 0; i < n; i++) {
// 答案要求需要取模 1e9+7（1000000007），
// 如计算初始结果为：1000000008，请返回 1。
sum = (a + b) % 1000000007;
a = b;
b = sum;
}
return a;
}
}
// 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
// 内存消耗：35.3 MB, 在所有 Java 提交中击败了46.56%的用户
class Solution {
public int fib(int n) {
if (n == 0 || n == 1)
return n;
int[] dp = new int[n + 1];
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i < n + 1; i++) {
dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007;
}
return dp[n];
}
}
【剑指offer】10.2 青蛙跳台阶问题
题目描述
// 10.2. 青蛙跳台阶问题
// 力扣
// 一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一
// 个 n 级的台阶总共有多少种跳法。
// 答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008
// ，请返回 1。
// 牛客
// 一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的
// 台阶总共有多少种跳法（先后次序不同算不同的结果）。
题解
// 实际上跟斐波那契数列是一个意思，青蛙要么跳1步，f(1)=1
// ，要么跳2步，f(2)=2
// 如果是台阶n阶，计算所有的跳法，
// 首先青蛙跳第一步的时候存在跳1阶和跳2阶两种情况
// 跳1阶，还剩下n-1阶，那么就是f(n-1)种跳法。
// 跳2阶，还剩下n-2阶，那么就是f(n-2)种跳法。
// 所有情况加起来，就是最终n阶台阶跳法，其实就是f(n)=f(n-1)+f(n-2)。
// 其实和斐波那契数列一样的算法。
// 牛客
// 暴力递归解，不可取
// 运行时间：317ms
// 占用内存：9584k
public class Solution {
public int JumpFloor(int target) {
if (target < 3)
return target;
return JumpFloor(target - 1) + JumpFloor(target - 2);
}
}
// 动态规划
// 运行时间：9ms
// 占用内存：9688k
public class Solution {
public int JumpFloor(int target) {
if (target < 3)
return target;
int prev1 = 1, prev2 = 2;
int f = 0;
for (int i = 2; i < target; i++) {
f = prev1 + prev2;
prev1 = prev2;
prev2 = f;
}
return f;
}
}
// 力扣
// 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
// 内存消耗：35.4 MB, 在所有 Java 提交中击败了61.21%的用户
class Solution {
public int numWays(int n) {
if (n == 0)
return 1;
if (n < 3)
return n;
int prev1 = 1, prev2 = 2;
int f = 0;
for (int i = 2; i < n; i++) {
f = (prev1 + prev2) % 1000000007; // 根据数值要求做修改
prev1 = prev2;
prev2 = f;
}
return f;
}
}
// f(n-1) + f(n-2) = f(n)
// 好理解版
// 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
// 内存消耗：35.2 MB, 在所有 Java 提交中击败了60.02%的用户
class Solution {
public int numWays(int n) {
if (n == 0)
return 1;
if (n <= 2)
return n;
int[] dp = new int[n];
dp[0] = 1;
dp[1] = 2;
for (int i = 2; i < n; i++) {
dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007;
}
return dp[n - 1];
}
}
【剑指offer】10.3 矩形覆盖
题目描述
// 10. 矩形覆盖
// 我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。
// 请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
// 比如n=3时，2*3的矩形块有3种覆盖方法
题解
// 如果图画出来就明白了，其实还是斐波那契数列问题。
// 要找有多少种方法，而不关心放了多少块，
// 所以其实2*1小矩形有单块竖放和两块横放两种放法，
// 其中横放必须要两块一起横放。明白了这点，那么：
// 当n=1时，需要覆盖面积为2*1，总共有f(1)=1种放法
// 当n=2时，需要覆盖面积为2*2，总共有f(2)=2种放法(两个横放和两个竖放)
// 当n=n时，需要覆盖面积为2*n，第一步可以竖放可以横放，
// 假设第一步是竖放，则还剩下2*(n-1)覆盖面积，有f(n-1)种放法，
// 假设第一步是横放，还剩下2*(n-2)覆盖面积，有f(n-2)种放法，
// 那么总的方法数为所有放法加起来，所以f(n) = f(n-1) + f(n-2)
// 牛客
// 暴力递归法，不推荐
// 运行时间：320ms
// 占用内存：9560k
public class Solution {
public int RectCover(int target) {
if (target <= 2)
return target;
return RectCover(target - 1) + RectCover(target - 2);
}
}
// 运行时间：9ms
// 占用内存：9652k
public class Solution {
public int RectCover(int target) {
if (target <= 2)
return target;
int f = 0;
int prev1 = 1, prev2 = 2;
for (int i = 3; i <= target; i++) {
f = prev1 + prev2;
prev1 = prev2;
prev2 = f;
}
return f;
}
}
public class Solution {
public int rectCover(int target) {
if (target == 0)
return 0;
if (target <= 2)
return target;
int[] dp = new int[target];
dp[0] = 1;
dp[1] = 2;
for (int i = 2; i < target; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[target - 1];
}
}
【剑指offer】10.4 变态跳台阶
题目描述
// 10.4 变态跳台阶
// 一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。
// 求该青蛙跳上一个n级的台阶总共有多少种跳法。
题解
// 牛客
// 动态规划
// n级台阶，第一步有n种跳法：1,2,3，...,n，记为F(n)
// 跳1阶，剩下n-1阶，有F(n-1)种跳法
// 跳2阶，剩下n-2阶，有F(n-2)种跳法
// ...
// 跳n-1阶，剩下1阶，只有1中跳跳法
// 有:
// F(n) = F(n-1) + F(n-2) + ... + F(1) + 1
// F(n- 1) = F(n-2) + F(n-3) + .. + F(1) + 1
// ...
// F(2) = F(1) + 1
// F(1) = 1
// 可以看到F(n)中的每一项都可以按一样的循环来展开。
// 运行时间：10ms
// 占用内存：9560k
import java.util.Arrays;
public class Solution {
public int JumpFloorII(int target) {
int[] f = new int[target];
Arrays.fill(f, 1);
for (int i = 1; i < target; i++){
for (int j = 0; j < i; j++) {
f[i] = f[i] + f[j];
}
}
return f[target - 1];
}
}
// 运行时间：13ms,超过69.65%用Java提交的代码
// 占用内存：9704KB,超过3.29%用Java提交的代码
// f(n)
// f(n-1) + f(n-2) + f(n-3) + ... + f(2) + f(1) + f(0)
// f(0) = 1, f(1) = 2, f(2) =
public class Solution {
public int jumpFloorII(int n) {
if (n == 0)
return 0;
if (n <= 2)
return n;
int[] dp = new int[n + 1];
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i < n + 1; i++) {
for (int j = 0; j < i; j++) {
dp[i] += dp[j];
}
}
return dp[n];
}
}
// 数学解
// f(n) = f(n-1) + f(n-2) + f(n-3) + .. + f(1)
// f(n-1) = f(n-2) + f(n-3) + .. + f(1)
// 所以有f(n) - f(n-1) = f(n-1)，则，f(n)/f(n-1)=2，为等比数列，
// 根据定义可以计算第n项的值为f(1)*2^(n-1)
// 运行时间：10ms
// 占用内存：9688k
public class Solution {
public int JumpFloorII(int target) {
return (int) Math.pow(2, target - 1);
}
}
【剑指offer】42. 连续子数组的最大和
题目描述
// 42. 连续子数组的最大和
// 力扣
// 输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。
// 求所有子数组的和的最大值。
// 要求时间复杂度为O(n)。
// 牛客
// 输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整
// 数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为 O(n).
题解
// 暴力法
// 暴力法在力扣无法通过
// 牛客
// 运行时间：10ms
// 占用内存：9448k
public class Solution {
private int max = 0;
public int FindGreatestSumOfSubArray(int[] array) {
if (array.length == 0)
return 0;
max = array[0];
for (int i = 0; i < array.length; i++) {
int pathSum = 0;
for (int j = i; j < array.length; j++) {
pathSum += array[j];
if (pathSum >= max)
max = pathSum;
}
}
return max;
}
}
// 动态规划 //
// 牛客
// 运行时间：10ms
// 占用内存：9544k
public class Solution {
public int FindGreatestSumOfSubArray(int[] array) {
if (array.length == 0)
return 0;
int max = array[0]; // 将max初始化为array第一个元素
int pathSum = 0; // 当前遍历子数组路径的和记为pathSum
for (int val: array) { // 遍历array中的元素记为val
if (pathSum <= 0) // 如果pathSum不是正值,加val也不会使val增多
pathSum = val; // 还不如直接令pathSum修改为当前的val
else // 如果pathSum是正值，不管val是正是负，都会对val有增加
pathSum += val; // 所以此时pathSum直接累加val
if (pathSum >= max) // 每次运算将大数保存至max
max = pathSum;
}
return max;
}
}
// 看完上面的注释，还需要补充一点的是：
// 这道题需要连续的子数组，我们遍历数组一定是从左往右，
// val是一定要加的，不可能跳过val去加下一个，而pathSum是之
// 前遍历的子数组的和，是可以保留也可以放弃的。
// 因此pathSum的处理上，我们通过判断pathSum对val值的增益与否，
// 来选择是否累加val，还是直接将pathSum重置为val。
// （而不是判断val的正负与否来累加，因为val是一定要加的。）
// 力扣
// 执行用时：1 ms, 在所有 Java 提交中击败了97.97%的用户
// 内存消耗：45 MB, 在所有 Java 提交中击败了42.77%的用户
class Solution {
public int maxSubArray(int[] nums) {
if (nums.length == 0)
return 0;
int max = nums[0];
int pathSum = 0;
for (int val: nums) {
if (pathSum <= 0)
pathSum = val;
else
pathSum += val;
if (pathSum >= max)
max = pathSum;
}
return max;
}
}
【剑指offer】47. 礼物的最大价值
题目描述
// 47. 礼物的最大价值
// 力扣
// 在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值
// （价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次
// 向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上
// 面的礼物的价值，请计算你最多能拿到多少价值的礼物？
题解
// 题解其实不难，就是动态规划，权衡对哪个方向（左还是上）求和累计的值最大
// 那个方向累计和最大就累加哪个方向的值。
// 本题要的是最大值，而不是路径，我们只需要得到左上到右下的最大值即可。
// 因此同样是动态规划，可以根据动态规划存储方式的不同来优化。
// 力扣
// 本地dp
// 执行用时：3 ms, 在所有 Java 提交中击败了80.03%的用户
// 内存消耗：41.1 MB, 在所有 Java 提交中击败了58.97%的用户
class Solution {
public int maxValue(int[][] grid) {
if (grid == null || grid.length == 0)
return 0;
int row = grid.length, col = grid[0].length;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (i == 0 && j == 0)
continue;
if (i == 0)
grid[i][j] += grid[i][j - 1];
else if (j == 0)
grid[i][j] += grid[i - 1][j];
else
grid[i][j] += Math.max(grid[i][j - 1], grid[i - 1][j]);
}
}
return grid[row - 1][col - 1];
}
}
示意图：
则最后有：
// 力扣
// 单数组维护dp存储
// 执行用时：2 ms, 在所有 Java 提交中击败了97.66%的用户
// 内存消耗：41.1 MB, 在所有 Java 提交中击败了58.97%的用户
class Solution {
public int maxValue(int[][] grid) {
if (grid == null || grid[0].length == 0)
return 0;
int col = grid[0].length;
int[] dp = new int[col];
for (int[] row : grid) {
dp[0] += row[0];
for (int i = 1; i < col; i++) {
// 如果dp[i]没有赋值，则肯定Math给的是dp[i - 1]
// 如果dp[i]已经被赋值了，Math.max中的dp[i]为
// 上一行的i列的dp值。
dp[i] = Math.max(dp[i], dp[i - 1]) + row[i];
}
}
return dp[col - 1];
}
}
示意图：
特殊解——二分法
【剑指offer】11. 旋转数组的最小数字
题目描述
// 力扣
// 11. 旋转数组的最小数字
// 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的
// 旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元
// 素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组
// 的最小值为1。
// 牛客
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。
NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
题解
// 二分查找
// 力扣
// 执行用时：14 ms, 在所有 Java 提交中击败了38.70%的用户
// 内存消耗：38.7 MB, 在所有 Java 提交中击败了22.10%的用户
// 牛客
// 运行时间：177ms
// 占用内存：28280k
class Solution {
public int minArray(int[] numbers) {
if (numbers.length == 0) {
return 0;
}
int start = 0, end = numbers.length - 1;
while (start < end) {
int mid = (start + end) / 2;
// System.out.println("start: " + start + " mid: " + mid + " end: " + end); // 可以打印中间结果试试
if (numbers[start] == numbers[mid] && numbers[mid] == numbers[end]) { // 如果三索引数相等，直接for循环遍历找最小值
return findMin(numbers, start, end);
}
else if (numbers[mid] <= numbers[end]) { // 这里取end索引和mid索引数判断比较方便。
// 因为如果发生翻转，翻转部分的所有数值都会比左边第一个数值要小（或相等）。
// 如果end索引数比mid索引数大（或相等），最小值一定在左半边，end移到mid位置。
end = mid;
}
else // 否则（如果mid索引数比end索引数大），start移动到mid+1位置
start = mid + 1;
}
return numbers[start]; // 直到start与end索引相遇，直接返回该索引数
}
// findMin：从左到右，for循环遍历找最小值（根据题意，从左到右遇到的第一个小数即为最小数）
public static int findMin(int[] numbers, int start, int end) {
for (int i = start; i <= end; i++) {
if (numbers[start] > numbers[i]) {
return numbers[i];
}
}
return numbers[start];
}
}
// 牛客
// [3,3,3,4,1]
// [3,4,1,3,3]
// [4,1,3,3,3]
// 运行时间：171ms 超过87.93%用Java提交的代码
// 占用内存：28412KB 超过9.02%用Java提交的代码
import java.util.ArrayList;
public class Solution {
public int minNumberInRotateArray(int [] arr) {
int len = arr.length;
if (len == 0)
return 0;
int left = 0, right = len - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (arr[left] == arr[mid] && arr[right] == arr[mid])
return findMin(arr, left, right);
if (arr[right] >= arr[mid]) {
right = mid;
}
else {
left = mid + 1;
}
}
return -1;
}
private int findMin(int[] arr, int left, int right) {
for (int i = left; i <= right; i++) {
if (arr[left] > arr[i])
return arr[i];
}
return arr[left];
}
}
// 直接解
// 牛客
// 运行时间：204ms
// 占用内存：28728KB
// 力扣
// 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
// 内存消耗：38.3 MB, 在所有 Java 提交中击败了70.89%的用户
public class Solution {
public int minNumberInRotateArray(int [] array) {
if(array.length == 0){
return 0;
}
else{
for(int i = 0; i < array.length - 1; i++){
if(array[i + 1] - array[i] < 0){
return array[i+1];
}
}
return array[0];
}
}
}
【剑指offer】53. 数字在排序数组中出现的次数
题目描述
// 53. 数字在排序数组中出现的次数
// 力扣
// 统计一个数字在排序数组中出现的次数。
// 牛客
// 统计一个数字在升序数组中出现的次数。
题解
// 二分查找
// 牛客
// 二分查找法，构建二分查找函数binarysearch，
// binarysearch函数，输入arr和k，通过二分查找方法找到k数字(的重复集)，
// 并返回k数字(的重复集)末端的下一位索引。
// 具体情况：arr首端索引left，arr末端索引right，对半找中点索引
// mid = (left + right) / 2，如果中点索引arr[mid]不大于目标k，则
// left更新到mid的下一位索引mid+1，如此循环，直到left到达第一个大于
// k的元素的索引。
//
// 主函数GetNumberOfK则调用两次binarysearch，第一次调用binarysearch(array, k)
// 找k之后第一个大于k的元素（第一次调用找到k重复集的length索引）。
// 第二次调用binarysearch(array, k - 1)找k-1之后第一个大于k-1的元素(就是k)，
// （第二次调用找到k重复集的0索引），两个返回值相减，就是k的出现次数（k
// 重复集的长度）
// 运行时间：11ms，超过84.49%用Java提交的代码
// 占用内存：9608KB，超过5.82%用Java提交的代码
public class Solution {
public int GetNumberOfK(int[] array , int k) {
return binarysearch(array, k) - binarysearch(array, k - 1);
}
public int binarysearch(int[] arr, int k) {
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (arr[mid] <= k) {
left = mid + 1;
}
else { // k < arr[mid]
right = mid - 1;
}
}
return left;
}
}
// 力扣
// 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
// 内存消耗：41.3 MB, 在所有 Java 提交中击败了70.38%的用户
class Solution {
public int search(int[] nums, int target) {
return binarysearch(nums, target) - binarysearch(nums ,target - 1);
}
public int binarysearch(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (arr[mid] <= target)
left = mid + 1;
else // target < arr[mid]
right = mid - 1;
}
return left;
}
}
【剑指offer】53.2 0～n-1中缺失的数字
题目描述
// 53.2 0～n-1中缺失的数字
// 力扣
// 一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都
// 在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该
// 数组中，请找出这个数字。
题解
/ 直接法
// 直接法不通用，还是得想想其他方法。
// 力扣
// 根据题意，说明元素和索引必须相等，不相等说明索引对应的元素缺失，
// 就直接返回索引。如果遍历完没发现元素索引的冲突，说明缺失的就是末端元素
// 直接返回末端的下一位索引。
// 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
// 内存消耗：39 MB, 在所有 Java 提交中击败了50.07%的用户
class Solution {
public int missingNumber(int[] nums) {
for (int i = 0; i < nums.length; i++) {
if (i != nums[i])
return i;
}
return nums.length;
}
}
// 二分查找 ///
// 力扣
// 二分查找法和53题是一样的，
// 初始化首尾指针left和right，对半取中间位索引mid = (left + right) / 2
// ,如果遍历的元素nums[mid]和mid相等，说明缺失元素的位置在右半边，left更新
// 为mid+1,否则（如果遍历元素nums[mid]>mid），说明缺失元素在左半边，
// right更新为mid-1，left和right相遇时即为缺失元素的索引位置，直接返回即可
// 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
// 内存消耗：38.9 MB, 在所有 Java 提交中击败了60.99%的用户
class Solution {
public int missingNumber(int[] nums) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] == mid)
left = mid + 1;
else // nums[mid] > mid
right = mid - 1;
}
return left;
}
}
特殊解——回溯搜索/DFS/BFS
【剑指offer】12. 矩阵中的路径
题目描述
// 12. 矩阵中的路径
// 力扣
// 请设计一个函数，用来判断在一个矩阵中是否存在一条包含某
// 字符串所有字符的路径。路径可以从矩阵中的任意一格开始，
// 每一步可以在矩阵中向左、右、上、下移动一格。如果一条路
// 径经过了矩阵的某一格，那么该路径不能再次进入该格子。例
// 如，在下面的3×4的矩阵中包含一条字符串“bfce”的路径（路径
// 中的字母用加粗标出）。
// [["a","b","c","e"],
// ["s","f","c","s"],
// ["a","d","e","e"]]
// 但矩阵中不包含字符串“abfb”的路径，因为字符串的第一个字符b占
// 据了矩阵中的第一行第二个格子之后，路径不能再次进入这个格子。
// 牛客
// 请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所
// 有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在
// 矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩
// 阵中的某一个格子，则该路径不能再进入该格子。 例如
// [["a","b","c","e"],
// ["s","f","c","s"],
// ["a","d","e","e"]]
// 矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因
// 为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能
// 再次进入该格子。
题解
/// 回溯搜索法 ///
构建待搜索矩阵同尺寸的布尔矩阵marked，用于标记该位置元素是否被使用过。
设置路径步长pathLen，用于同步搜索目标的长度。
遍历待搜索矩阵matrix每一个位置的元素，对该位置的元素做所有方向的搜索，搜索不到就回溯到原状态，之前修改的marked和pathLen要重置。
// 牛客
// 运行时间 12ms
// 占用内存 9592KB
public class Solution {
private final static int[][] next = {{0,-1}, {0,1}, {-1,0}, {1,0}}; // 左右上下四个方向
private int rows;
private int cols;
// 解题函数
public boolean hasPath(char[] array, int rows, int cols, char[] str) {
if (rows == 0 || cols == 0)
return false;
this.rows = rows;
this.cols = cols;
boolean[][] marked = new boolean[rows][cols]; // 标记状态矩阵，可标记某元素是否被使用，回溯后使用状态被清空
char[][] matrix = buildMatrix(array); // 题目给的数组char[]转化为矩阵char[][]
// 两层for循环，遍历待搜索矩阵matrix的所有元素，第r行第c列元素为matrix[c][r]
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (backTracking(matrix, str, marked, r, c, 0)) {
return true;
}
}
}
return false;
}
// 回溯搜索法
// 输入变量：待搜索矩阵matrix，搜索目标str，状态标记矩阵marked(初始化为全false), 遍历行r，遍历列c，已遍历的路径步长pathLen(初始化为0)
// 每一次backTracking搜索，路径长度pathLen将+1，搜索失败，则回溯进行下一次for遍历
// pathLen又会重置为0，marked也会重置为全false。
private boolean backTracking(char[][] matrix, char[] str, boolean[][] marked, int r, int c, int pathLen) {
if (pathLen == str.length) // 如果遍历路径步长等于搜索目标str的长度，返回true
return true;
if (r < 0 || r >= rows || c < 0 || c >= cols) // 如果遍历行和列超出边界，返回false,（回到上一次marked的标记和路径步数pathLen，即进行了回溯）
return false;
if (marked[r][c]) // 如果遍历元素被使用过，返回false，进行回溯
return false;
if (matrix[r][c] != str[pathLen]) // 如果搜索矩阵遍历元素与当前路径步数对应的搜索目标字符不相等，返回false，进行回溯
return false; // 换言之，不返回false，说明遍历元素与对应目标字符是一致的。
marked[r][c] = true; // 当前元素标记为已被使用
// 开始以当前遍历元素matrix[r][c]为起点进行搜索，for循环取next中左右上下四个方向，递归backTracking进行搜索
// 路径pathLen+1
for (int[] dic : next) {
if (backTracking(matrix, str, marked, r + dic[0], c + dic[1], pathLen + 1)) {
return true;
}
}
// 当前遍历元素搜索结束，未发现目标，元素标记重置回false
marked[r][c] = false;
return false; // 搜索结束，返回false。进行回溯
}
// 将数组char[]转为矩阵char[][]
public char[][] buildMatrix(char[] array) {
char[][] matrix = new char[rows][cols];
int idx = 0;
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
matrix[r][c] = array[idx++];
}
}
return matrix;
}
}
// 力扣
// 和牛客原理是一样的
// 执行用时：7 ms, 在所有 Java 提交中击败了40.96%的用户
// 内存消耗：40.1 MB, 在所有 Java 提交中击败了87.40%的用户
class Solution {
private int rows;
private int cols;
private final int[][] next = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}}; // 左右上下
public boolean exist(char[][] board, String word) {
this.rows = board.length;
this.cols = board[0].length;
char[] wordarray = word.toCharArray();
if (rows == 0 || cols == 0)
return false;
boolean[][] marked = new boolean[rows][cols];
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (backTracking(board, wordarray, marked, r, c, 0)) {
return true;
}
}
}
return false;
}
public boolean backTracking(char[][] matrix, char[] str, boolean[][] marked, int r, int c, int pathLen) {
if (pathLen == str.length)
return true;
if (r < 0 || r >= rows || c < 0 || c >= cols)
return false;
if (marked[r][c])
return false;
if (matrix[r][c] != str[pathLen])
return false;
marked[r][c] = true;
for (int[] dic : next) {
if (backTracking(matrix, str, marked, r + dic[0], c + dic[1], pathLen + 1))
return true;
}
marked[r][c] = false;
return false;
}
}
// 差不多的实现
// 执行用时：8 ms, 在所有 Java 提交中击败了24.52%的用户
// 内存消耗：40.4 MB, 在所有 Java 提交中击败了22.69%的用户
class Solution {
int[][] direction = {{-1,0}, {1,0}, {0,1}, {0,-1}};
boolean[][] used;
char[][] board;
String word;
public boolean exist(char[][] board, String word) {
int row = board.length;
int col = board[0].length;
this.used = new boolean[row][col];
this.board = board;
this.word = word;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (search(row, col, i, j, 0))
return true;
}
}
return false;
}
private boolean search(int row, int col, int i, int j, int wi) {
if (wi == word.length()) {
return true;
}
if (i < 0 || i >= row || j < 0 || j >= col || wi > word.length()) {
return false;
}
if (used[i][j]) {
return false;
}
if (board[i][j] != word.charAt(wi)) {
return false;
}
used[i][j] = true;
for (int[] dic: direction) {
int x = dic[0];
int y = dic[1];
if (search(row, col, i + x, j + y, wi + 1))
return true;
}
used[i][j] = false;
return false;
}
}
【剑指offer】13. 机器人的运动范围
题目描述
// 13. 机器人的运动范围
// 力扣
// 地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。
// 一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、
// 右、上、下移动一格（不能移动到方格外），也不能进入行坐标
// 和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能
// 够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [
// 35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？
// 牛客
// 地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，
// 每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐
// 标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够
// 进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35
// ,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？
题解
// 力扣
// 本题使用的方法为深度优先搜索(DFS)，方法和12题的回溯法很像，
// 但其实回溯法是DFS的特殊情况。
// 执行用时：2 ms, 在所有 Java 提交中击败了43.58%的用户
// 内存消耗：35.4 MB, 在所有 Java 提交中击败了84.10% 的用户
class Solution {
private int rows;
private int cols;
private int k;
private int[][] digitSum;
private static final int[][] next = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
private int count = 0;
// 解题函数
public int movingCount(int m, int n, int k) {
this.rows = m;
this.cols = n;
this.k = k;
if (rows == 0 || cols == 0) // 行或者列其中一个为0，则返回0
return 0;
if (k == 0) // 如果k为0，则能到达位置只有(0,0)这第一个位置
return 1;
boolean[][] marked = new boolean[rows][cols]; // 定义与搜索矩阵同尺寸的标记矩阵marked
dfs(marked, 0, 0); // 开始深度优先搜索递归，起始位置为左上角(0,0)
return count; // 搜索完毕，返回计数
}
// 定义搜索函数
// 输入标记矩阵marked，行索引r(初始化为0)，列索引c(初始化为0)
private void dfs(boolean[][] marked, int r, int c) {
if (r < 0 || r >= rows || c < 0 || c >= cols) // 超过正常矩阵边界，返回
return;
if (marked[r][c]) // 该位置已被遍历过，返回
return;
if ((digitSum(r) + digitSum(c)) > k) // 超过数位和的上限，返回
return;
count++; // 如果满足条件，成功计数一次
marked[r][c] = true; // 该位置标记为已被使用
// System.out.println(markedToString(marked)); // 打印marked矩阵
for (int[] n : next)
dfs(marked, r + n[0], c + n[1]);
}
// 定义函数：位数之和
public int digitSum(int n) {
int n0 = n / 1000000000;
int n1 = n % 1000000000 / 100000000;
int n2 = n % 100000000 / 10000000;
int n3 = n % 10000000 / 1000000;
int n4 = n % 1000000 / 1000000;
int n5 = n % 100000 / 10000;
int n6 = n % 10000 / 1000;
int n7 = n % 1000 / 100;
int n8 = n % 100 / 10;
int n9 = n % 10;
int sum = n0 + n1 + n2 + n3 + n4 + n5 + n6 +n7 + n8 + n9;
return sum;
}
// 打印marked的toString函数（不是必须）
public String markedToString(boolean[][] marked) {
StringBuilder res = new StringBuilder();
for (int i = 0; i < marked.length; i++) {
res.append("[");
for (int j = 0; j < marked[0].length; j++) {
if (marked[i][j])
res.append(" true ");
else
res.append(" false ");
}
res.append("]");
res.append("\r\n");
}
return res.toString();
}
}
// 换一种位数加法的写法
// 执行用时：2 ms, 在所有 Java 提交中击败了44.08%的用户
// 内存消耗：35.6 MB, 在所有 Java 提交中击败了38.95%的用户
class Solution {
int[][] direction = new int[][] {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
boolean[][] used;
int count = 0;
public int movingCount(int m, int n, int k) {
this.used = new boolean[m][n];
search(m, n, 0, 0, k);
return count;
}
private void search(int m, int n, int i, int j, int k) {
if (digitSum(i, j) > k)
return;
if (i < 0 || i >= m || j < 0 || j >= n)
return;
if (used[i][j])
return;
used[i][j] = true;
count++;
for (int[] dic: direction) {
int x = dic[0];
int y = dic[1];
search(m, n, i + x, j + y, k);
}
}
private int digitSum(int row, int col) {
int res = 0;
int a = row;
int b = col;
while (a != 0) {
res += a % 10;
a = a / 10;
}
while (b != 0) {
res += b % 10;
b = b / 10;
}
return res;
}
}
// 牛客
// 思路和力扣是一样的
// 运行时间：11ms
// 占用内存：9692k
public class Solution {
private int rows;
private int cols;
private int threshold;
private int[][] digitSum;
private static final int[][] next = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
private int count = 0;
public int movingCount(int threshold, int rows, int cols) {
this.rows = rows;
this.cols = cols;
this.threshold = threshold;
if (rows == 0 || cols == 0)
return 0;
if (threshold == 0)
return 1;
boolean[][] marked = new boolean[rows][cols];
dfs(marked, 0, 0);
return count;
}
private void dfs(boolean[][] marked, int r, int c) {
if (r < 0 || r >= rows || c < 0 || c >= cols)
return;
if (marked[r][c])
return;
if ((digitSum(r) + digitSum(c)) > threshold)
return;
count++;
marked[r][c] = true;
// System.out.println(markedToString(marked));
for (int[] n : next)
dfs(marked, r + n[0], c + n[1]);
}
// 定义函数：位数之和
public int digitSum(int n) {
int n0 = n / 1000000000;
int n1 = n % 1000000000 / 100000000;
int n2 = n % 100000000 / 10000000;
int n3 = n % 10000000 / 1000000;
int n4 = n % 1000000 / 1000000;
int n5 = n % 100000 / 10000;
int n6 = n % 10000 / 1000;
int n7 = n % 1000 / 100;
int n8 = n % 100 / 10;
int n9 = n % 10;
int sum = n0 + n1 + n2 + n3 + n4 + n5 + n6 +n7 + n8 + n9;
return sum;
}
// 打印marked的toString函数（不是必须）
public String markedToString(boolean[][] marked) {
StringBuilder res = new StringBuilder();
for (int i = 0; i < marked.length; i++) {
res.append("[");
for (int j = 0; j < marked[0].length; j++) {
if (marked[i][j])
res.append(" true ");
else
res.append(" false ");
}
res.append("]");
res.append("\r\n");
}
return res.toString();
}
}
特殊解——排序
【剑指offer】21. 调整数组顺序使奇数位于偶数前面
题目描述
// 力扣
// 输入一个整数数组，实现一个函数来调整该数组中数字的顺序，
// 使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。
// 牛客
// 输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有
// 的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇
// 数和奇数，偶数和偶数之间的相对位置不变。
// 牛客的题目要难一点点，需要保证奇数之间，偶数之间的相对位置不变。
题解
// 双指针法 ///
// 力扣
// 执行用时：3 ms, 在所有 Java 提交中击败了29.92%的用户
// 内存消耗：46.4 MB, 在所有 Java 提交中击败了77.86%的用户
class Solution {
public int[] exchange(int[] nums) {
int head = 0;
int end = nums.length - 1;
int temp = 0;
while (head < end) {
if (nums[head] % 2 == 0 && nums[end] % 2 != 0) { // 头指针找偶数，尾指针找奇数
temp = nums[head]; // 偶数存临时变量
nums[head] = nums[end]; // 奇数放前面
nums[end] = temp;
end -= 1;
head += 1;
}
else if (nums[head] % 2 == 0) { // 头指针找偶数,尾指针没找到奇数
end -= 1;
continue;
}
else if (nums[end] % 2 != 0) { // 尾指针找奇数，头指针没找到
head += 1;
continue;
}
else {
end -= 1;
head += 1;
}
}
return nums;
}
}
// 简化一下
class Solution {
public int[] exchange(int[] nums) {
int[] res = new int[nums.length];
int t = 0, l = 0, r = nums.length - 1;
while (l <= r) {
if (isEven(nums[t])) {
res[r--] = nums[t++];
}
else {
res[l++] = nums[t++];
}
}
return res;
}
private boolean isEven(int x) {
boolean res = false;
if (x % 2 == 0) res = true;
return res;
}
}
/ 直接法 /
// 牛客
// 运行时间：9ms
// 占用内存：9780k
public class Solution {
public void reOrderArray(int[] array) {
int[] dummy = array.clone(); // 用于遍历，原array用于修改
int head = 0;
int countOdd_end = 0;
for (int x : array) {
if (!isEven(x))
countOdd_end += 1;
}
for (int x : dummy) {
if (isEven(x)) {
array[countOdd_end++] = x;
}
else {
array[head++] = x;
}
}
}
// 判断是否是偶数
private boolean isEven(int x) {
return (x % 2 == 0);
}
}
// 力扣
// 执行用时：4 ms, 在所有 Java 提交中击败了9.50%的用户
// 内存消耗：47.8 MB, 在所有 Java 提交中击败了12.24%的用户
public class Solution {
public int[] exchange(int[] array) {
int[] dummy = array.clone();
int head = 0;
int countOdd_end = 0;
for (int x : array) {
if (!isEven(x))
countOdd_end += 1;
}
for (int y : dummy) {
if (isEven(y)) {
array[countOdd_end++] = y;
}
else {
array[head++] = y;
}
}
return array;
}
// 判断是否是偶数
private boolean isEven(int x) {
return (x % 2 == 0);
}
}
冒泡
// 牛客
// 运行时间：9ms
// 占用内存：9652k
public class Solution {
public void reOrderArray(int[] array) {
int len = array.length;
int temp = 0;
for (int i = len - 1; i > 0; i--) {
for (int j = 0; j < i; j++) {
if (isEven(array[j]) && !isEven(array[j + 1])) {
temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
}
// 判断是否是偶数
private boolean isEven(int x) {
return (x % 2 == 0);
}
}
【剑指offer】51. 数组中的逆序对
题目描述
// 51. 数组中的逆序对
// 力扣
// 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两
// 个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对
// 的总数。
// 牛客
// 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数
// 字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。
// 并将P对1000000007取模的结果输出。 即输出P%1000000007
题解
暴力法 ///
// 最直观的的做法是两个for循环全部遍历比对一轮
// 但是这种做法时间复杂度无法通过。
// 力扣
// 无法通过
class Solution {
public int reversePairs(int[] nums) {
int count = 0;
if (nums.length < 2)
return 0;
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[i] > nums[j])
count++;
}
}
return count;
}
}
归并排序法
// 牛客
// 根据题意，前大后小的两个数字构成一个逆序对。
// 直接写一个归并排序，在merge函数当nums[l]<nums[r]时，记录逆序对个数
// 运行时间：235ms
// 占用内存：33856KB
public class Solution {
int count = 0;
public int InversePairs(int[] nums) {
int[] temp = new int[nums.length];
mergesort(nums, 0, nums.length - 1, temp);
return count % 1000000007;
}
private void mergesort(int[] nums, int left, int right, int[] temp) {
if (left < right) {
int mid = (left + right) / 2;
mergesort(nums, left, mid, temp);
mergesort(nums, mid + 1, right, temp);
merge(nums, left, mid, right, temp);
}
}
// merge合并有序数组，所以左子数组是升序的，右子数组也是升序的
private void merge(int[] nums, int left, int mid, int right, int[] temp) {
int l = left;
int r = mid + 1;
int t = 0;
// 之前一直是nums[l]<=nums[r]，l右移如果出现了nums[l]>nums[r],
// 说明l到mid的数，跟nums[r]都组成逆序对。（归并排序，左子数组元
// 素排序后还会在左子数组，右子数组元素排序后还会在右子数组）
while (l <= mid && r <= right) {
if (nums[l] <= nums[r])
temp[t++] = nums[l++];
else {
temp[t++] = nums[r++];
count += mid - l + 1;
count = count % 1000000007;
}
}
while (l <= mid) {
temp[t++] = nums[l++];
}
while (r <= right) {
temp[t++] = nums[r++];
}
t = 0;
while (left <= right)
nums[left++] = temp[t++];
}
}
// 力扣
// 执行用时：37 ms, 在所有 Java 提交中击败了61.83%的用户
// 内存消耗：48.3 MB, 在所有 Java 提交中击败了37.82%的用户
class Solution {
public int count = 0;
public int reversePairs(int[] nums) {
int[] temp = new int[nums.length];
mergesort(nums, 0, nums.length - 1, temp);
return count;
}
private void mergesort(int[] nums, int left, int right, int[] temp) {
if (left< right) {
int mid = (left + right) / 2;
mergesort(nums, left, mid, temp);
mergesort(nums, mid + 1, right, temp);
merge(nums, left, mid, right, temp);
}
}
private void merge(int[] nums, int left, int mid, int right, int[] temp) {
int l = left;
int r = mid + 1;
int t = 0;
while (l <= mid && r <= right) {
if (nums[l] <= nums[r])
temp[t++] = nums[l++];
else {
temp[t++] = nums[r++];
count += mid - l + 1;
}
}
while (l <= mid)
temp[t++] = nums[l++];
while (r <= right)
temp[t++] = nums[r++];
t = 0;
while (left <= right)
nums[left++] = temp[t++];
}
}
特殊解——位运算
【剑指offer】56. 数组中数字出现的次数
题目描述
// 56. 数组中数字出现的次数
// 力扣
// 一个整型数组 nums 里除两个数字之外，其他数字都出现了两次
// 。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(
// n)，空间复杂度是O(1)。
// 牛客
// 一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写
// 程序找出这两个只出现一次的数字。
题解
集合辅助解
集合辅助
// 第一时间能想到的简单方法，好理解但不是最优
// 力扣
// 定义一个集合set，遍历nums中的所有元素nums[i]，并将nums[i]存入set中
// 如果存不进，说明nums[i]出现了2次，在set中删除nums[i]，留下来的就
// 都是只出现过一次的元素了，提取出来存入数组res中，返回即可。
// 执行用时：13 ms, 在所有 Java 提交中击败了10.23%的用户
// 内存消耗：39.7 MB, 在所有 Java 提交中击败了97.13%的用户
import java.util.HashSet;
class Solution {
public int[] singleNumbers(int[] nums) {
HashSet<Integer> set = new HashSet<Integer>();
for (int i = 0; i < nums.length; i++) {
if (!set.add(nums[i]))
set.remove(nums[i]);
}
int[] res = new int[set.size()];
int i = 0;
for (int num: set) {
res[i++] = num;
}
return res;
}
}
// 牛客
// 运行时间：11ms，超过59.56%用Java提交的代码
// 占用内存：11092KB，超过51.92%用Java提交的代码
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param array int整型一维数组
* @return int整型一维数组
*/
public int[] FindNumsAppearOnce (int[] array) {
HashSet<Integer> set = new HashSet<Integer>();
for (int i = 0; i < array.length; i++) {
if (!set.add(array[i]))
set.remove(array[i]);
}
int[] res = new int[set.size()];
int i = 0;
for (int num: set) {
res[i++] = num;
}
return res;
}
}
最优解
/// 位运算法 /
// 位运算法才是真正要学的最优解法
// 首先需要说明，异或操作 ^ 的性质包括：
// 交换律
// 结合律
// A ^ 0 = A;
// A ^ A = 0
// 问题一：
// 假设nums只存在1个只出现过1次的数字，为A，其他数字都出现了2次
// 且nums数组为{10, 10, A, 2, 5, 5, 2}，那么我们把数字全部异或起来
// 就可以把A分离出来，
// 即 10^10^A^2^5^5^2 = 10^10^2^2^5^5^A (交换律) = 0^0^0^A = A
// 如果把题目换成这样，本题就做完了，可惜换不得。
//
// 问题二：
// 题目中，数组nums存在2个只出现1次的数字，假设为A，B。
// 其他数字都出现了两次，我们假设nums数组为{10, 10, A, 2, 5, B, 5, 2}。
// 那么我们是否可以把这道题分解为两个问题一来解决呢？
// 化繁为简，先把nums中所有元素异或起来，得到
// 10^10^A^2^5^B^5^2 = A^B。
// A B肯定是不同的数，既然是不同的数，A B一定存在某一位(假设是第x位)
// 上的数是不同的，而在二进制视角中，数字要么是1要么是0，
// 所以在第x位上要么A是1,B是0，要么B是1,A是0，这样才有A B在第x位上的
// 数是不同的。所以A B的异或A^B，在第x位上一定等于1 (1^0=1)。
//
// 我们用 A^B第x位上的1，来把问题二分解成问题一。
// 我们设置一个辅助参数 one=1（二进制00000001），循环左移和A^B来做
// 逻辑与运算，来找这个第x位，如果one & (A^B) == 0，one就左移，
// 直到one & (A^B) != 0，说明找到了第x位。
//
// 然后循环遍历nums中的数，记为num，还记得第x位上要么A是1,B是0，
// 要么B是1,A是0，我们把num和one直接做与运算，
// 用if条件判断，把所有逻辑与的结果是1的数字，全部异或到int x参数上。
// 用if条件判断，把所有逻辑与的结果是0的数字，全部异或到int y参数上。
// 这样，不管第x位上A B是0还是1，我们都把它们分开到了不同的地方去异或
// 就把问题二分解成了两个问题一。最后直接返回x和y就行~
// 力扣
// 执行用时：1 ms, 在所有 Java 提交中击败了100.00%的用户
// 内存消耗：40.2 MB, 在所有 Java 提交中击败了34.85%的用户
class Solution {
public int[] singleNumbers(int[] nums) {
int x = 0, y = 0, t = 0, one = 1;
for (int num : nums)
t ^= num;
while ((t & one) == 0)
one <<= 1;
for (int num : nums) {
if ((num & one) != 0)
x ^= num;
else
y ^= num;
}
return new int[] {x, y};
}
}
// 牛客
// 牛客比力扣多了一点，需要把小的数排在前面，其他都一样
// 运行时间：13ms，超过24.78%用Java提交的代码
// 占用内存：11092KB，超过51.91%用Java提交的代码
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param array int整型一维数组
* @return int整型一维数组
*/
public int[] FindNumsAppearOnce (int[] array) {
int x = 0, y = 0, t = 0, one = 1;
for (int num : array)
t ^= num;
while ((t & one) == 0)
one <<= 1;
for (int num : array) {
if ((num & one) != 0)
x ^= num;
else
y ^= num;
}
int[] res = new int[] {y, x};
if (res[0] > res[1]) {
int temp = res[0];
res[0] = res[1];
res[1] = temp;
}
return res;
}
}
【剑指offer】56.2 数组中数字出现的次数
题目描述
// 56.2 数组中数字出现的次数
// 力扣
// 在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现
// 了三次。请找出那个只出现一次的数字。
题解
// 力扣
// 在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次
// 。请找出那个只出现一次的数字。
// 创建计数数组count，记录所有nums元素在二进制表示下每一位出现1的次数
// 比如count[0]就是nums所有元素在最低位出现1的次数。
//
// 一个双for循环，第一个for遍历nums的元素num，第二个for遍历计数数组索引j，
// 也就是从低到高遍历num的每一位二进制位。
// 如果num & 1为1，则当前逻辑运算结果1累加到count[j]中，然后
// num整体右移1一格num = num >>> 1，j也右移一位，即开始遍历下一位
// 二进制位，再和1做逻辑与，如此循环。第二层for循环走一轮能找出一个num的
// 所有位出现1的次数，并记录到count的相应位置中。
// 两个for循环之后，能把所有nums的元素的所有位出现的1累计到count的相应位置
// 第二个for循环，倒序遍历count，索引为i，索引的计数元素为count[i]，
// 由于需要找出的目标元素target出现了1次，其他元素都出现了3次，
// 所以其他元素对应的二进制位出现1的次数一定是3的倍数，如果该位出现
// 1的次数不是3的倍数，无法整除3，说明该位一定出现了target的1。我们将
// 余数或逻辑运算赋给变量res中，然后res左移，i左移，如此循环，可以把
// count中所有位中属于target的二进制1赋给res，使得res等于target。
// 最后返回res即可。
// 执行用时：5 ms, 在所有 Java 提交中击败了85.82%的用户
// 内存消耗：39.3 MB, 在所有 Java 提交中击败了73.60%的用户
class Solution {
public int singleNumber(int[] nums) {
int[] count = new int[32];
for (int num : nums) {
for (int j = 0; j < count.length; j++) {
count[j] += num & 1;
num >>>= 1;
}
}
int res = 0, three = 3;
for (int i = count.length - 1; i >= 0; i--) {
res <<= 1;
res |= count[i] % three;
}
return res;
}
}
// 啰嗦一点的写法，比较好理解
// 执行用时：14 ms, 在所有 Java 提交中击败了48.98%的用户
// 内存消耗：39.4 MB, 在所有 Java 提交中击败了52.13%的用户
class Solution {
public int singleNumber(int[] nums) {
int[] count = new int[32];
int res = 0;
for (int num: nums) {
int one = 1;
for (int j = 0; j < 32; j++) {
if ((num & one) == one) count[j]++;
one = one << 1;
}
}
for (int i = count.length - 1; i >= 0; i--) {
res = res << 1;
int temp = count[i] % 3;
if (temp == 0)
continue;
else
res = res | count[i] % 3;
}
return res;
}
}
特殊解——双指针
【剑指offer】57. 和为s的两个数字
题目描述
// 57. 和为s的两个数字
// 力扣
// 输入一个递增排序的数组和一个数字s，在数组中查找两个数，
// 使得它们的和正好是s。如果有多对数字的和等于s，则输出任意
// 一对即可。
// 牛客
// 输入一个递增排序的数组和一个数字S，在数组中查找两个数，
// 使得他们的和正好是S，如果有多对数字的和等于S，输出两个
// 数的乘积最小的。
题解
// 力扣
// 前后双指针，求的和sum与target比较，
// sum大了，右指针左移，减小sum，
// sum小了，左指针右移，增大sum。
// 执行用时：2 ms, 在所有 Java 提交中击败了94.94%的用户
// 内存消耗：55.3 MB, 在所有 Java 提交中击败了72.04%的用户
class Solution {
public int[] twoSum(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left < right) {
if (nums[left] + nums[right] > target) {
right--;
}
else if (nums[left] + nums[right] < target) {
left++;
}
else {
return new int[]{nums[left], nums[right]};
}
}
return new int[0];
}
}
// 牛客
// 运行时间：10ms，超过89.79%用Java提交的代码
// 占用内存：9512KB，超过10.62%用Java提交的代码
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
ArrayList<Integer> res = new ArrayList<Integer>(2);
int left = 0, right = array.length - 1;
while (left < right) {
if (array[left] + array[right] > sum)
right--;
else if (array[left] + array[right] < sum)
left++;
else {
res.add(array[left]);
res.add(array[right]);
return res;
}
}
return res;
}
}
【剑指offer】57.2 和为s的两个数字
题目描述
// 57.2 和为s的两个数字
// 力扣
// 输入一个正整数 target ，输出所有和为 target 的连续正整数序列
// （至少含有两个数）。
// 序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。
// 牛客
// 小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上
// 就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续
// 的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正
// 数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快
// 的找出所有和为S的连续正数序列? Good Luck!
题解
// 牛客
// 思路简单，但是能做出来还是不容易的。
// 从前面初始化两个指针left和right，由于至少包含2个数，且必须是正整数
// 所以left初始化为1（left至少为1），right比left大，right至少为2，
// 累计的数组和至少为3，所以初始化累计和sum为3，
// 开始比较sum与target大小，如果sum比target小，需要窗口扩大，right右移
// 右移之后sum累加right，如果sum比target大，需要窗口缩小，left右移，
// sum累减left，之后left再右移（注意是先指针移动还是先操作sum加减）
// 直到sum等于target，将left到right之间所有元素存入新指定的ArrayList中
// 再存入res中。
// 运行时间：15ms,超过87.63%用Java提交的代码
// 占用内存：9984KB超过2.76%用Java提交的代码
import java.util.ArrayList;
public class Solution {
public ArrayList<ArrayList<Integer>> FindContinuousSequence(int target) {
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
if (target < 2)
return res;
int left = 1, right = 2;
int sum = 3;
while (left < right) {
if (sum < target) {
right++;
sum += right;
}
else if (sum > target) {
sum -= left;
left++;
}
else {
ArrayList<Integer> list = new ArrayList<>();
for (int i = left; i <= right; i++) {
list.add(i);
}
res.add(list);
sum -= left;
left++;
}
}
return res;
}
}
// 力扣
// 执行用时：2 ms, 在所有 Java 提交中击败了97.62%的用户
// 内存消耗：36.8 MB, 在所有 Java 提交中击败了17.75%的用户
import java.util.ArrayList;
class Solution {
public int[][] findContinuousSequence(int target) {
ArrayList<int[]> res = new ArrayList<>();
int left = 1, right = 2;
int sum = 3;
while (left < right) {
if (sum < target) {
right++;
sum += right;
}
else if (sum > target) {
sum -= left;
left++;
}
else {
int[] list = new int[right - left + 1];
int j = 0;
for (int i = left; i <= right; i++) {
list[j++] = i;
}
res.add(list);
sum -= left;
left++;
}
}
int[][] result = res.toArray(new int[res.size()][]);
return result;
}
}
特殊解——贪心算法
【剑指offer】63. 股票的最大利润
题目描述
文章来源：https://www.toymoban.com/news/detail-473398.html
// 63. 股票的最大利润
// 力扣
// 假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该
// 股票一次可能获得的最大利润是多少？
题解文章来源地址https://www.toymoban.com/news/detail-473398.html
// 贪心算法
// 力扣
// 初始化min
// 执行用时：2 ms, 在所有 Java 提交中击败了66.58%的用户
// 内存消耗：38.2 MB, 在所有 Java 提交中击败了71.67%的用户
class Solution {
public int maxProfit(int[] prices) {
if (prices.length == null || prices.length == 0)
return 0;
int minPrice = prices[0];
int profit = Integer.MIN_VALUE;
for (int p : prices) {
minPrice = Math.min(p, minPrice);
profit = Math.max(profit, (p - minPrice));
}
return profit;
}
}
到了这里，关于【剑指offer】数据结构——数组的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
