數(shù)據(jù)結(jié)構(gòu)——數(shù)組
直接解
【劍指offer】03.數(shù)組中重復(fù)的數(shù)字
//03. 數(shù)組中重復(fù)的數(shù)字
// 找出數(shù)組中重復(fù)的數(shù)字。
// 力扣
// 在一個(gè)長度為 n 的數(shù)組 nums 里的所有數(shù)字都在 0～n-1 的范圍內(nèi)。
// 數(shù)組中某些數(shù)字是重復(fù)的，但不知道有幾個(gè)數(shù)字重復(fù)了，也不知道每
// 個(gè)數(shù)字重復(fù)了幾次。請(qǐng)找出數(shù)組中任意一個(gè)重復(fù)的數(shù)字。
// 牛客
// 在一個(gè)長度為n的數(shù)組里的所有數(shù)字都在0到n-1的范圍內(nèi)。 數(shù)組中某些數(shù)
// 字是重復(fù)的，但不知道有幾個(gè)數(shù)字是重復(fù)的。也不知道每個(gè)數(shù)字重復(fù)幾次
// 。請(qǐng)找出數(shù)組中第一個(gè)重復(fù)的數(shù)字。 例如，如果輸入長度為7的數(shù)組{2,3,
// 1,0,2,5,3}，那么對(duì)應(yīng)的輸出是第一個(gè)重復(fù)的數(shù)字2。
// 返回描述：
// 如果數(shù)組中有重復(fù)的數(shù)字，函數(shù)返回true，否則返回false。
// 如果數(shù)組中有重復(fù)的數(shù)字，把重復(fù)的數(shù)字放到參數(shù)duplication[0]中。（ps
// :duplication已經(jīng)初始化，可以直接賦值使用。）
排序法
把數(shù)組排成升序，再遍歷找相鄰重復(fù)數(shù)
// 時(shí)間復(fù)雜度 O(nlogn)：3 ms, 在所有 Java 提交中擊敗了59.39%的用戶
// 空間復(fù)雜度 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，存不進(jìn)就是遇到重復(fù)了
// 時(shí)間復(fù)雜度 O(n)： 5 ms, 在所有 Java 提交中擊敗了49.49%的用戶
// 空間復(fù)雜度 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])) { // 如果存不進(jìn)hashset，說明遇到重復(fù)
result = nums[i];
return result; // 返回遍歷數(shù)
}
}
return result;
}
}
// 牛客
// ?？皖}目要求時(shí)間復(fù)雜度 O(N)，空間復(fù)雜度 O(1)，因此比較嚴(yán)格一點(diǎn)
// 運(yùn)行時(shí)間 14ms
// 占用內(nèi)存 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++
// 這里要特別注意~返回任意重復(fù)的一個(gè)，賦值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;
}
}
原地置換
找重復(fù)的數(shù)，且數(shù)取值在數(shù)組長度范圍內(nèi)，大部分?jǐn)?shù)肯定是不重復(fù)的，將它們擺放成數(shù)字和索引相同的數(shù)組，即{0, 2, 3, 1}我們希望擺成{0, 1, 2, 3}。如果數(shù)組有兩個(gè)2，那么原來2的位置有一個(gè)2，就會(huì)發(fā)現(xiàn)重復(fù)。
// 時(shí)間復(fù)雜度 O(n)：1 ms, 在所有 Java 提交中擊敗了90.57%的用戶
// 空間復(fù)雜度 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) {
// 若遍歷數(shù)與索引不等
if (nums[i] != i) {
// System.out.println(nums[i]);
// 若遍歷數(shù)與以遍歷數(shù)為索引的對(duì)應(yīng)數(shù)相等（遇重復(fù)）
if (nums[i] == nums[nums[i]]) {
return nums[nums[i]]; // 直接返回結(jié)果
}
//交換：遍歷數(shù)與以遍歷數(shù)為索引的對(duì)應(yīng)數(shù)
swap(nums, i);
} // (交換后)確認(rèn)遍歷數(shù)與索引相等之后，再右移索引
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++
// 這里要特別注意~返回任意重復(fù)的一個(gè)，賦值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. 二維數(shù)組中的查找
題目描述
// 04. 二維數(shù)組中的查找
// 在一個(gè) n * m 的二維數(shù)組中，每一行都按照從左到右遞增的順序排序，
// 每一列都按照從上到下遞增的順序排序。請(qǐng)完成一個(gè)函數(shù)，輸入這樣的
// 一個(gè)二維數(shù)組和一個(gè)整數(shù)，判斷數(shù)組中是否含有該整數(shù)。
// 限制：
// 0 <= n <= 1000
// 0 <= m <= 1000
題解
// 時(shí)間復(fù)雜度 O(M + N): 18 ms
// 空間復(fù)雜度 O(1): 43.1 MB
// 從矩陣右上角開始遍歷，則左邊的數(shù)一定比右邊的數(shù)小，
// 下邊的數(shù)一定比上面的數(shù)大。
// 比較遍歷數(shù)和target。
// 若遍歷數(shù)大，target小，說明target在遍歷數(shù)左邊，遍歷位置左移。
// 如果遍歷數(shù)小，target大，說明target在遍歷數(shù)下面，遍歷位置下移
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;
// 初始化遍歷起始點(diǎn)索引，起始點(diǎn)為右上角
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移動(dòng)在先，造成越界，加一個(gè)i的不越界判定
if (i <= rows-1 && matrix[i][j] > target) {
j--;
}
}
return false;
}
}
【劍指offer】29. 順時(shí)針打印矩陣
題目描述
// 力扣
// 輸入一個(gè)矩陣，按照從外向里以順時(shí)針的順序依次打印出每一個(gè)數(shù)字。
// ?？?// 輸入一個(gè)矩陣，按照從外向里以順時(shí)針的順序依次打印出每一個(gè)數(shù)字
// ，例如，如果輸入如下4 X 4矩陣： 1 2 3 4 5 6 7 8 9 10 11 12 13 14
// 15 16 則依次打印出數(shù)字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.
題解
// ?？?// printRes函數(shù)中，下行和左列要加一個(gè)row1和row2不相等的判斷和
// col1和col2的判斷，防止重復(fù)遍歷。而matrix = [[1,2,3],[4,5,6],[7,8,9]]
// 中的實(shí)例比較特殊，我們需要遍歷中心的元素5，所以我們?cè)趐rintRes函數(shù)
// 中的前兩個(gè)for循環(huán)都不設(shè)置row1和row2相等的判斷和col1和col2的判斷。
// 運(yùn)行時(shí)間：16ms
// 占用內(nèi)存：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) {
// 一個(gè)while循環(huán)遍歷一圈
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位置開始,因?yàn)閞ow1位置以前的元素在上行遍歷過)
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[]的轉(zhuǎn)換
// 執(zhí)行用時(shí)：5 ms, 在所有 Java 提交中擊敗了9.34%的用戶
// 內(nèi)存消耗：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[] 存儲(chǔ)，中間不經(jīng)過arraylist
// 執(zhí)行用時(shí)：1 ms, 在所有 Java 提交中擊敗了97.37%的用戶
// 內(nèi)存消耗：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. 數(shù)組中出現(xiàn)次數(shù)超過一半的數(shù)字
題目描述
// 39. 數(shù)組中出現(xiàn)次數(shù)超過一半的數(shù)字
// 力扣
// 數(shù)組中有一個(gè)數(shù)字出現(xiàn)的次數(shù)超過數(shù)組長度的一半，請(qǐng)找出這個(gè)數(shù)字。
// 你可以假設(shè)數(shù)組是非空的，并且給定的數(shù)組總是存在多數(shù)元素。
// 牛客
// 數(shù)組中有一個(gè)數(shù)字出現(xiàn)的次數(shù)超過數(shù)組長度的一半，請(qǐng)找出這個(gè)數(shù)字。例
// 如輸入一個(gè)長度為9的數(shù)組{1,2,3,2,2,2,5,4,2}。由于數(shù)字2在數(shù)組中出現(xiàn)
// 了5次，超過數(shù)組長度的一半，因此輸出2。如果不存在則輸出0。
題解
/// 直接法 /
// 排序，然后逐個(gè)遍歷數(shù)
// 直接法無法在?？屯ㄟ^
// 力扣
//
// 執(zhí)行用時(shí)：3 ms, 在所有 Java 提交中擊敗了34.81%的用戶
// 內(nèi)存消耗：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];
}
}
多數(shù)投票法我做了個(gè)ppt放在代碼下面，感興趣可以看看。
多數(shù)投票法
// 比較好的方法
// 如果某個(gè)數(shù)字符合條件，那么它出現(xiàn)的次數(shù)就比其他所有數(shù)字出現(xiàn)的次數(shù)加起來還要多。
// 具體可以看看這個(gè) https://www.zhihu.com/question/49973163/answer/617122734
// 力扣
// 不驗(yàn)證的話，就是取出現(xiàn)次數(shù)最多的數(shù)字
// 執(zhí)行用時(shí)：1 ms, 在所有 Java 提交中擊敗了99.99%的用戶
// 內(nèi)存消耗：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;
}
}
// 力扣
// 加上驗(yàn)證環(huán)節(jié)
// 執(zhí)行用時(shí)：2 ms, 在所有 Java 提交中擊敗了60.11%的用戶
// 內(nèi)存消耗：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;
}
}
// 驗(yàn)證環(huán)節(jié)
int count = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] == max)
count++;
}
return count >= nums.length / 2 + 1 ? max : 0;
}
}
// ?？?// 牛客必須要有驗(yàn)證環(huán)節(jié)，否則無法通過，所以?？鸵垡獓?yán)格（嚴(yán)謹(jǐn)）
// 運(yùn)行時(shí)間：12ms
// 占用內(nèi)存：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;
}
}
// 驗(yàn)證環(huán)節(jié)
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個(gè)數(shù)
題目描述
// 力扣
// 輸入整數(shù)數(shù)組 arr ，找出其中最小的 k 個(gè)數(shù)。例如，輸入4、5、1、6、
// 2、7、3、8這8個(gè)數(shù)字，則最小的4個(gè)數(shù)字是1、2、3、4。
// ?？?// 輸入n個(gè)整數(shù)，找出其中最小的K個(gè)數(shù)。例如輸入4,5,1,6,2,7,3,8這8個(gè)數(shù)字
// ，則最小的4個(gè)數(shù)字是1,2,3,4。
題解
// 暴力法 //
// 力扣
// 暴力法，能通過但沒有意義
// 執(zhí)行用時(shí)：8 ms, 在所有 Java 提交中擊敗了64.97%的用戶
// 內(nèi)存消耗：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;
}
}
如果用數(shù)組表示堆的話，根據(jù)層序順序標(biāo)號(hào)規(guī)則，將層序標(biāo)號(hào)對(duì)應(yīng)到數(shù)組索引中，那么在數(shù)組索引中找二叉樹左右結(jié)點(diǎn)可以通過如下規(guī)律：找結(jié)點(diǎn)的左節(jié)點(diǎn)：索引2，找結(jié)點(diǎn)的右結(jié)點(diǎn)：索引2+1，找結(jié)點(diǎn)的父結(jié)點(diǎn)：索引 / 2（整數(shù)除法，要去除小數(shù)點(diǎn)）。
/// 最大堆法 ///
// 比較好的方法
// ?？?// 運(yùn)行時(shí)間：15ms
// 占用內(nèi)存：9944k
import java.util.ArrayList;
import java.util.PriorityQueue; // 利用優(yōu)先隊(duì)列構(gòu)建堆
import java.util.Comparator; // 比較器
public class Solution {
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
if (k > input.length || k < 0) // 如果k值有問題，返回空數(shù)組
return new ArrayList<>();
// 優(yōu)先隊(duì)列默認(rèn)是最小堆（最小值置頂），將其修改成最大堆（最大值置頂）
// 得到構(gòu)建好的最大堆maxHeap
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2.compareTo(o1);
}
});
// for循環(huán)遍歷input中的元素，將其放入num中
for (int num: input) {
maxHeap.add(num);
// 由于是最大堆，所以最大值一定會(huì)被置頂
// 當(dāng)堆中元素超過k（達(dá)到k+1）了，那么置頂元素一定比其余k個(gè)數(shù)大，
// 將其彈出。input所有元素被遍歷過，且在堆中被比較過大小，
// 所以能在堆中留下的k個(gè)數(shù)就是input里最小的k個(gè)數(shù)。
if (maxHeap.size() > k)
maxHeap.poll();
}
// 將堆以ArrayList格式返回
return new ArrayList<>(maxHeap);
}
}
// 力扣
// 執(zhí)行用時(shí)：25 ms, 在所有 Java 提交中擊敗了13.48%的用戶
// 內(nèi)存消耗：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);
}
}
}
// 力扣
// 執(zhí)行用時(shí)：27 ms, 在所有 Java 提交中擊敗了11.67%的用戶
// 內(nèi)存消耗：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;
}
}
}
/ 快速選擇法 /
// 快速選擇和快排很類似
// ?？?// 運(yùn)行時(shí)間：14ms
// 占用內(nèi)存：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); // 快選主函數(shù)
// 此時(shí)input前k個(gè)元素即為最小的k個(gè)元素
for (int i = 0; i < k; i++)
res.add(input[i]); // 將前k個(gè)元素存入res中
return res;
}
// 快速選擇函數(shù)
// 找k個(gè)最小值
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，停止循環(huán)
break;
if (size > k) // 最小的k個(gè)數(shù)一定在前size個(gè)數(shù)中
high = size - 1; // 右邊界high左移
else // size < k // 在右側(cè)數(shù)組中繼續(xù)找最小的k個(gè)數(shù)
low = size + 1; // 左邊界low右移
}
}
// 切分函數(shù)，我們希望使數(shù)組切分值的左邊都是小元素，右邊都是大元素
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; // 返回
}
// 交換函數(shù)
private void swap(int[] input, int i, int j) {
int t = input[i];
input[i] = input[j];
input[j] = t;
}
}
// 力扣
// 執(zhí)行用時(shí)：3 ms, 在所有 Java 提交中擊敗了83.07%的用戶
// 內(nèi)存消耗：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. 把數(shù)組排成最小的數(shù)
題目描述
// 45. 把數(shù)組排成最小的數(shù)
// 力扣
// 輸入一個(gè)非負(fù)整數(shù)數(shù)組，把數(shù)組里所有數(shù)字拼接起來排成一個(gè)數(shù)，
// 打印能拼接出的所有數(shù)字中最小的一個(gè)。
// ?？?// 輸入一個(gè)正整數(shù)數(shù)組，把數(shù)組里所有數(shù)字拼接起來排成一個(gè)數(shù)，打印
// 能拼接出的所有數(shù)字中最小的一個(gè)。例如輸入數(shù)組{3，32，321}，則
// 打印出這三個(gè)數(shù)字能排成的最小數(shù)字為321323。
題解
// 力扣
// 執(zhí)行用時(shí)：6 ms, 在所有 Java 提交中擊敗了77.89%的用戶
// 內(nèi)存消耗：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; // 取數(shù)組nums的長度，即為字符組的長度
String res = ""; // 答案存儲(chǔ)在res中
String[] strlist = new String[len]; // 創(chuàng)建與nums同尺寸的String list
for (int i = 0; i < len; i++)
strlist[i] = Integer.toString(nums[i]); // 轉(zhuǎn)字符串后排入String list
// 給字符組list排序，lambda表達(dá)式來自定義比較器。
// 原本是比較字符組每一個(gè)元素（字母）的大小來升序，
// 現(xiàn)在是比較字符組每一個(gè)元素加起來組成的字符的大小來升序
Arrays.sort(strlist, (s1, s2) -> (s1 + s2).compareTo(s2 + s1));
// 排序后，將list所有元素按順序存入res
for (String s : strlist)
res += s;
return res; // 最后返回res
}
}
// 牛客
// 運(yùn)行時(shí)間：100ms
// 占用內(nèi)存：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;
}
}
// ?？?// 比較器修改的另一種寫法
// 運(yùn)行時(shí)間：14ms
// 占用內(nèi)存：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. 滑動(dòng)窗口的最大值
題目描述
// 59. 滑動(dòng)窗口的最大值
// 力扣
// 給定一個(gè)數(shù)組 nums 和滑動(dòng)窗口的大小 k，請(qǐng)找出所有滑動(dòng)窗口里的最大值。
// ?？?// 給定一個(gè)數(shù)組和滑動(dòng)窗口的大小，找出所有滑動(dòng)窗口里數(shù)值的最大值。例
// 如，如果輸入數(shù)組{2,3,4,2,6,2,5,1}及滑動(dòng)窗口的大小3，那么一共存在6個(gè)
// 滑動(dòng)窗口，他們的最大值分別為{4,4,6,6,6,5}； 針對(duì)數(shù)組{2,3,4,2,6,2,5,
// 1}的滑動(dòng)窗口有以下6個(gè)： {[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]}。
// 窗口大于數(shù)組長度的時(shí)候，返回空
題解
最大堆法
// 最大堆
// 牛客
// 推薦方法。
// 構(gòu)建最大堆maxHeap，構(gòu)建答案保存數(shù)組res，
// 先把窗口范圍size內(nèi)的元素放入maxHeap，之后堆頂元素（最大值）放入res，
// 然后構(gòu)建左指針i，右指針j，for循環(huán)右移兩個(gè)指針，之前的左指針遍歷元素
// 在maxHeap中去掉，加入右指針的新遍歷元素，構(gòu)成新的maxHeap（窗口遍歷元素）
// 再次把堆頂最大值放入res，如此循環(huán)。
// 運(yùn)行時(shí)間：14ms，超過75.10%用Java提交的代碼
// 占用內(nèi)存：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;
}
}
// 力扣
// 執(zhí)行用時(shí)：93 ms, 在所有 Java 提交中擊敗了5.11%的用戶
// 內(nèi)存消耗：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;
}
}
隊(duì)列方法
// 雙端隊(duì)列
// 雙端隊(duì)列法旨在用雙端隊(duì)列deque來維護(hù)窗口元素特別是窗口的最大值元素。
//
// 先排除特殊情況，如果size比nums長度還大，或者size比0小，直接返回空數(shù)組。
//
// 定義雙端隊(duì)列deque（用鏈表代替），定義相應(yīng)大小的答案保存數(shù)組res，
// 第一個(gè)for循環(huán)將nums中的前size個(gè)元素nums[i]從尾部存入deque。由于我們不需要
// deque窗口元素中的所有值，而是只要窗口元素中的最大值，所以如果deque不
// 為空且將要存入的nums[i]，比deque的尾部元素要大，在nums[i]存入deque之前，
// 我們將deque尾部元素循環(huán)移除，直到deque尾部元素大于等于nums[i]，
// 或者直到deque元素已經(jīng)排空了，這時(shí)候再將nums[i]存入，這樣子deque的頭部
// 元素一定是deque中的最大值元素，并且deque頭部到尾部的元素呈現(xiàn)降序的排序。
// 第一個(gè)for循環(huán)起初始化窗口的作用，將nums中前size個(gè)元素放入deque并規(guī)范成
// 降序鏈表，我們可以輕松從頭部取到窗口最大值。
//
// 定義res遍歷索引j，初始化為0，如果deque初始化好了（非空），將deque的
// 頭部元素（窗口最大值）存入res[0]中，j右移。
//
// 第二個(gè)for循環(huán)，從nums的size索引開始遍歷nums的元素nums[i]，則nums[i]
// 為窗口的右索引元素，則窗口的左索引元素為nums[i - size]，在循環(huán)內(nèi)，
// 條件判斷：如果deque的頭部元素（窗口最大值）等于左索引元素，則將
// deque中的頭部元素去除。
// 然后調(diào)用while循環(huán)，與第一個(gè)for循環(huán)初始化deque時(shí)相似，如果deque不為空
// 且將要存入的nums[i]，比deque的尾部元素要大，在nums[i]存入deque之前，
// 我們將deque尾部元素循環(huán)移除，直到deque尾部元素大于等于nums[i]，
// 或者直到deque元素已經(jīng)排空了，這時(shí)候再將nums[i]存入。窗口完成一格移動(dòng)，
// 將res[j]位置賦值為deque的頭部元素（窗口最大值），j右移。
// 第二個(gè)for循環(huán)，主要是完成窗口移動(dòng)的過程，通過雙端鏈表和插入元素前的
// 貪心刪除元素，來維護(hù)一個(gè)降序的雙端鏈表，所以頭部元素就是窗口最大值。
//
// 如此循環(huán)，最后返回res即可。
//
// 執(zhí)行用時(shí)：15 ms, 在所有 Java 提交中擊敗了48.97%的用戶
// 內(nèi)存消耗：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. 撲克牌中的順子
// 力扣
// 從撲克牌中隨機(jī)抽5張牌，判斷是不是一個(gè)順子，即這5張牌是不是連續(xù)的
// 。2～10為數(shù)字本身，A為1，J為11，Q為12，K為13，而大、小王為 0 ，
// 可以看成任意數(shù)字。A 不能視為 14。
// 牛客
// LL今天心情特別好,因?yàn)樗ベI了一副撲克牌,發(fā)現(xiàn)里面居然有2個(gè)大王,2個(gè)小王
// (一副牌原本是54張^_^)...他隨機(jī)從中抽出了5張牌,想測(cè)測(cè)自己的手氣,看看能
// 不能抽到順子,如果抽到的話,他決定去買體育彩票,嘿嘿?。 凹t心A,黑桃3,小王
// ,大王,方片5”,“Oh My God!”不是順子.....LL不高興了,他想了想,決定大\小 王
// 可以看成任何數(shù)字,并且A看作1,J為11,Q為12,K為13。上面的5張牌就可以變成“1
// ,2,3,4,5”(大小王分別看作2和4),“So Lucky!”。LL決定去買體育彩票啦。 現(xiàn)在
// ,要求你使用這幅牌模擬上面的過程,然后告訴我們LL的運(yùn)氣如何， 如果牌能組成
// 順子就輸出true，否則就輸出false。為了方便起見,你可以認(rèn)為大小王是0。
題解
// 力扣
// 先排除特殊情況，nums中不足5個(gè)牌直接false，
// 創(chuàng)建計(jì)數(shù)數(shù)組pokerList，記錄每種牌出現(xiàn)的次數(shù)，有14種牌所以長度為14，
// 創(chuàng)建最大最小值max和min，用于記錄5張牌的最大最小值，
// for循環(huán)遍歷手牌num，出現(xiàn)次數(shù)累計(jì)一次pokerList[num]++，
// 如果num是0，跳過判斷遍歷下一張牌，
// 不是0的話，如果出現(xiàn)次數(shù)pokerList[num]大于1，說明有對(duì)子，有對(duì)子的牌
// 無法構(gòu)成順子，直接false。
// 以上不滿足的話，如果num小于min，把min更新為num，
// 如果num大于max，把max更新為num。
// 循環(huán)結(jié)束，我們可以得到手牌中的最大值max和最小值min，
// 在沒有重復(fù)對(duì)子的前提下，如果max-min的值小于等于4，則必定構(gòu)成順子，
// 返回true。比如max是5，min是1，說明其他三張牌一定是4 3 2和 0 這四種
// 情況，所以一定構(gòu)成順子。
// 執(zhí)行用時(shí)：1 ms, 在所有 Java 提交中擊敗了91.68%的用戶
// 內(nèi)存消耗：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);
}
}
// ?？?// 運(yùn)行時(shí)間：13ms,超過72.54%用Java提交的代碼
// 占用內(nèi)存：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. 構(gòu)建乘積數(shù)組
題目描述
// 66. 構(gòu)建乘積數(shù)組
// 力扣
// 給定一個(gè)數(shù)組 A[0,1,…,n-1]，請(qǐng)構(gòu)建一個(gè)數(shù)組 B[0,1,…,n-1]，其中 B[i]
// 的值是數(shù)組 A 中除了下標(biāo) i 以外的元素的積, 即 B[i]=A[0]×A[1]×…×A[i-1]
// ×A[i+1]×…×A[n-1]。不能使用除法。
// 牛客
// 給定一個(gè)數(shù)組A[0,1,...,n-1],請(qǐng)構(gòu)建一個(gè)數(shù)組B[0,1,...,n-1],其中B中的元素
// B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1]。不能使用除法。（注意：規(guī)
// 定B[0] = A[1] * A[2] * ... * A[n-1]，B[n-1] = A[0] * A[1] * ... * A[n-
// 2];）
// 對(duì)于A長度為1的情況，B無意義，故而無法構(gòu)建，因此該情況不會(huì)存在。
題解
暴力 ///
// 【偽解法】
// 力扣
// 無法通過
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;
}
}
// 力扣
// 可以看著實(shí)例來理解
// 輸入: [1,2,3,4,5]
// 輸出: [120,60,40,30,24]
//
// 計(jì)算b[i]是除a[i]以外所有的a中元素的乘積，
// 我們可以把i看做一個(gè)分界線，在i移動(dòng)的時(shí)候，把a(bǔ)中的元素分成了
// 左右兩邊，我們按照左右兩半邊來分別進(jìn)行計(jì)算。
// 例如：實(shí)例中乘積為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
// 可以發(fā)現(xiàn)，左半邊其實(shí)在逐漸往一個(gè)方向累乘，右半邊也是。
// 我們只需將兩邊分開累乘賦值給b，即可高效地完成運(yùn)算。
//
// 第一個(gè)for循環(huán)，從左往右遍歷a和b，索引記為i，遍歷到len-2為止，
// a[0]對(duì)b[0]沒有貢獻(xiàn)， 我們將b[0]初始化為1，
// 將a[i]累乘到product中，將product賦給b[i+1]，完成左半邊的累乘。
//
// 第二個(gè)for循環(huán)，從右往左遍歷a和b，遍歷到1為止，a[i]累乘到product，
// b由于之前已經(jīng)計(jì)算過了，所以product再累乘到b[i - 1]元素。
// 左右半邊計(jì)算完，則b元素就累乘完了，直接返回b。
// 執(zhí)行用時(shí)：2 ms, 在所有 Java 提交中擊敗了80.14%的用戶
// 內(nèi)存消耗：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;
}
}
// ?？?// 運(yùn)行時(shí)間：9ms超過99.07%用Java提交的代碼
// 占用內(nèi)存：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;
}
}
特殊解——?jiǎng)討B(tài)規(guī)劃
【劍指offer】10.1 斐波那契數(shù)列
題目描述
// 力扣
// 寫一個(gè)函數(shù)，輸入 n ，求斐波那契（Fibonacci）數(shù)列的第 n 項(xiàng)。
// 斐波那契數(shù)列的定義如下：
// F(0) = 0, F(1) = 1
// F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
// 斐波那契數(shù)列由 0 和 1 開始，之后的斐波那契數(shù)就是由之前的兩
// 數(shù)相加而得出。
// 答案需要取模 1e9+7（1000000007），如計(jì)算初始結(jié)果為：1000000008
// ，請(qǐng)返回 1。
題解
// ?？?
暴力遞歸法 /
// 遞歸可以，但是很暴力
public class Solution {
public int Fibonacci(int n) {
if (n == 1)
return 1;
if (n == 0)
return 0;
// 根據(jù)定義直接遞歸法
return Fibonacci(n - 1) + Fibonacci(n - 2);
}
}
// 動(dòng)態(tài)規(guī)劃 /
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]; // 循環(huán)遞推
}
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;
}
}
// 力扣
// 力扣如果用遞歸方法會(huì)發(fā)現(xiàn)直接報(bào)時(shí)間復(fù)雜度超了
/// 動(dòng)態(tài)規(guī)劃
// 執(zhí)行用時(shí)：0 ms , 在所有 Java 提交中擊敗了 100.00% 的用戶
// 內(nèi)存消耗： 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），
// 如計(jì)算初始結(jié)果為：1000000008，請(qǐng)返回 1。
sum = (a + b) % 1000000007;
a = b;
b = sum;
}
return a;
}
}
// 執(zhí)行用時(shí)：0 ms, 在所有 Java 提交中擊敗了100.00%的用戶
// 內(nèi)存消耗：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 青蛙跳臺(tái)階問題
題目描述
// 10.2. 青蛙跳臺(tái)階問題
// 力扣
// 一只青蛙一次可以跳上1級(jí)臺(tái)階，也可以跳上2級(jí)臺(tái)階。求該青蛙跳上一
// 個(gè) n 級(jí)的臺(tái)階總共有多少種跳法。
// 答案需要取模 1e9+7（1000000007），如計(jì)算初始結(jié)果為：1000000008
// ，請(qǐng)返回 1。
// ?？?// 一只青蛙一次可以跳上1級(jí)臺(tái)階，也可以跳上2級(jí)。求該青蛙跳上一個(gè)n級(jí)的
// 臺(tái)階總共有多少種跳法（先后次序不同算不同的結(jié)果）。
題解
// 實(shí)際上跟斐波那契數(shù)列是一個(gè)意思，青蛙要么跳1步，f(1)=1
// ，要么跳2步，f(2)=2
// 如果是臺(tái)階n階，計(jì)算所有的跳法，
// 首先青蛙跳第一步的時(shí)候存在跳1階和跳2階兩種情況
// 跳1階，還剩下n-1階，那么就是f(n-1)種跳法。
// 跳2階，還剩下n-2階，那么就是f(n-2)種跳法。
// 所有情況加起來，就是最終n階臺(tái)階跳法，其實(shí)就是f(n)=f(n-1)+f(n-2)。
// 其實(shí)和斐波那契數(shù)列一樣的算法。
// ?？?
// 暴力遞歸解，不可取
// 運(yùn)行時(shí)間：317ms
// 占用內(nèi)存：9584k
public class Solution {
public int JumpFloor(int target) {
if (target < 3)
return target;
return JumpFloor(target - 1) + JumpFloor(target - 2);
}
}
// 動(dòng)態(tài)規(guī)劃
// 運(yùn)行時(shí)間：9ms
// 占用內(nèi)存：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;
}
}
// 力扣
// 執(zhí)行用時(shí)：0 ms, 在所有 Java 提交中擊敗了100.00%的用戶
// 內(nèi)存消耗：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; // 根據(jù)數(shù)值要求做修改
prev1 = prev2;
prev2 = f;
}
return f;
}
}
// f(n-1) + f(n-2) = f(n)
// 好理解版
// 執(zhí)行用時(shí)：0 ms, 在所有 Java 提交中擊敗了100.00%的用戶
// 內(nèi)存消耗：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的小矩形橫著或者豎著去覆蓋更大的矩形。
// 請(qǐng)問用n個(gè)2*1的小矩形無重疊地覆蓋一個(gè)2*n的大矩形，總共有多少種方法？
// 比如n=3時(shí)，2*3的矩形塊有3種覆蓋方法
題解
// 如果圖畫出來就明白了，其實(shí)還是斐波那契數(shù)列問題。
// 要找有多少種方法，而不關(guān)心放了多少塊，
// 所以其實(shí)2*1小矩形有單塊豎放和兩塊橫放兩種放法，
// 其中橫放必須要兩塊一起橫放。明白了這點(diǎn)，那么：
// 當(dāng)n=1時(shí)，需要覆蓋面積為2*1，總共有f(1)=1種放法
// 當(dāng)n=2時(shí)，需要覆蓋面積為2*2，總共有f(2)=2種放法(兩個(gè)橫放和兩個(gè)豎放)
// 當(dāng)n=n時(shí)，需要覆蓋面積為2*n，第一步可以豎放可以橫放，
// 假設(shè)第一步是豎放，則還剩下2*(n-1)覆蓋面積，有f(n-1)種放法，
// 假設(shè)第一步是橫放，還剩下2*(n-2)覆蓋面積，有f(n-2)種放法，
// 那么總的方法數(shù)為所有放法加起來，所以f(n) = f(n-1) + f(n-2)
// 牛客
// 暴力遞歸法，不推薦
// 運(yùn)行時(shí)間：320ms
// 占用內(nèi)存：9560k
public class Solution {
public int RectCover(int target) {
if (target <= 2)
return target;
return RectCover(target - 1) + RectCover(target - 2);
}
}
// 運(yùn)行時(shí)間：9ms
// 占用內(nèi)存：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 變態(tài)跳臺(tái)階
題目描述
// 10.4 變態(tài)跳臺(tái)階
// 一只青蛙一次可以跳上1級(jí)臺(tái)階，也可以跳上2級(jí)……它也可以跳上n級(jí)。
// 求該青蛙跳上一個(gè)n級(jí)的臺(tái)階總共有多少種跳法。
題解
// ?？?// 動(dòng)態(tài)規(guī)劃
// n級(jí)臺(tái)階，第一步有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)中的每一項(xiàng)都可以按一樣的循環(huán)來展開。
// 運(yùn)行時(shí)間：10ms
// 占用內(nèi)存：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];
}
}
// 運(yùn)行時(shí)間：13ms,超過69.65%用Java提交的代碼
// 占用內(nèi)存：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];
}
}
// 數(shù)學(xué)解
// 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，為等比數(shù)列，
// 根據(jù)定義可以計(jì)算第n項(xiàng)的值為f(1)*2^(n-1)
// 運(yùn)行時(shí)間：10ms
// 占用內(nèi)存：9688k
public class Solution {
public int JumpFloorII(int target) {
return (int) Math.pow(2, target - 1);
}
}
【劍指offer】42. 連續(xù)子數(shù)組的最大和
題目描述
// 42. 連續(xù)子數(shù)組的最大和
// 力扣
// 輸入一個(gè)整型數(shù)組，數(shù)組中的一個(gè)或連續(xù)多個(gè)整數(shù)組成一個(gè)子數(shù)組。
// 求所有子數(shù)組的和的最大值。
// 要求時(shí)間復(fù)雜度為O(n)。
// ?？?// 輸入一個(gè)整型數(shù)組，數(shù)組里有正數(shù)也有負(fù)數(shù)。數(shù)組中的一個(gè)或連續(xù)多個(gè)整
// 數(shù)組成一個(gè)子數(shù)組。求所有子數(shù)組的和的最大值。要求時(shí)間復(fù)雜度為 O(n).
題解
// 暴力法
// 暴力法在力扣無法通過
// 牛客
// 運(yùn)行時(shí)間：10ms
// 占用內(nèi)存：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;
}
}
// 動(dòng)態(tài)規(guī)劃 //
// ?？?// 運(yùn)行時(shí)間：10ms
// 占用內(nèi)存：9544k
public class Solution {
public int FindGreatestSumOfSubArray(int[] array) {
if (array.length == 0)
return 0;
int max = array[0]; // 將max初始化為array第一個(gè)元素
int pathSum = 0; // 當(dāng)前遍歷子數(shù)組路徑的和記為pathSum
for (int val: array) { // 遍歷array中的元素記為val
if (pathSum <= 0) // 如果pathSum不是正值,加val也不會(huì)使val增多
pathSum = val; // 還不如直接令pathSum修改為當(dāng)前的val
else // 如果pathSum是正值，不管val是正是負(fù)，都會(huì)對(duì)val有增加
pathSum += val; // 所以此時(shí)pathSum直接累加val
if (pathSum >= max) // 每次運(yùn)算將大數(shù)保存至max
max = pathSum;
}
return max;
}
}
// 看完上面的注釋，還需要補(bǔ)充一點(diǎn)的是：
// 這道題需要連續(xù)的子數(shù)組，我們遍歷數(shù)組一定是從左往右，
// val是一定要加的，不可能跳過val去加下一個(gè)，而pathSum是之
// 前遍歷的子數(shù)組的和，是可以保留也可以放棄的。
// 因此pathSum的處理上，我們通過判斷pathSum對(duì)val值的增益與否，
// 來選擇是否累加val，還是直接將pathSum重置為val。
// （而不是判斷val的正負(fù)與否來累加，因?yàn)関al是一定要加的。）
// 力扣
// 執(zhí)行用時(shí)：1 ms, 在所有 Java 提交中擊敗了97.97%的用戶
// 內(nèi)存消耗：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. 禮物的最大價(jià)值
題目描述
// 47. 禮物的最大價(jià)值
// 力扣
// 在一個(gè) m*n 的棋盤的每一格都放有一個(gè)禮物，每個(gè)禮物都有一定的價(jià)值
// （價(jià)值大于 0）。你可以從棋盤的左上角開始拿格子里的禮物，并每次
// 向右或者向下移動(dòng)一格、直到到達(dá)棋盤的右下角。給定一個(gè)棋盤及其上
// 面的禮物的價(jià)值，請(qǐng)計(jì)算你最多能拿到多少價(jià)值的禮物？
題解
// 題解其實(shí)不難，就是動(dòng)態(tài)規(guī)劃，權(quán)衡對(duì)哪個(gè)方向（左還是上）求和累計(jì)的值最大
// 那個(gè)方向累計(jì)和最大就累加哪個(gè)方向的值。
// 本題要的是最大值，而不是路徑，我們只需要得到左上到右下的最大值即可。
// 因此同樣是動(dòng)態(tài)規(guī)劃，可以根據(jù)動(dòng)態(tài)規(guī)劃存儲(chǔ)方式的不同來優(yōu)化。
// 力扣
// 本地dp
// 執(zhí)行用時(shí)：3 ms, 在所有 Java 提交中擊敗了80.03%的用戶
// 內(nèi)存消耗：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];
}
}
示意圖：
則最后有：
// 力扣
// 單數(shù)組維護(hù)dp存儲(chǔ)
// 執(zhí)行用時(shí)：2 ms, 在所有 Java 提交中擊敗了97.66%的用戶
// 內(nèi)存消耗：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]已經(jīng)被賦值了，Math.max中的dp[i]為
// 上一行的i列的dp值。
dp[i] = Math.max(dp[i], dp[i - 1]) + row[i];
}
}
return dp[col - 1];
}
}
示意圖：
特殊解——二分法
【劍指offer】11. 旋轉(zhuǎn)數(shù)組的最小數(shù)字
題目描述
// 力扣
// 11. 旋轉(zhuǎn)數(shù)組的最小數(shù)字
// 把一個(gè)數(shù)組最開始的若干個(gè)元素搬到數(shù)組的末尾，我們稱之為數(shù)組的
// 旋轉(zhuǎn)。輸入一個(gè)遞增排序的數(shù)組的一個(gè)旋轉(zhuǎn)，輸出旋轉(zhuǎn)數(shù)組的最小元
// 素。例如，數(shù)組 [3,4,5,1,2] 為 [1,2,3,4,5] 的一個(gè)旋轉(zhuǎn)，該數(shù)組
// 的最小值為1。
// ?？?把一個(gè)數(shù)組最開始的若干個(gè)元素搬到數(shù)組的末尾，我們稱之為數(shù)組的旋轉(zhuǎn)。
輸入一個(gè)非遞減排序的數(shù)組的一個(gè)旋轉(zhuǎn)，輸出旋轉(zhuǎn)數(shù)組的最小元素。
NOTE：給出的所有元素都大于0，若數(shù)組大小為0，請(qǐng)返回0。
題解
// 二分查找
// 力扣
// 執(zhí)行用時(shí)：14 ms, 在所有 Java 提交中擊敗了38.70%的用戶
// 內(nèi)存消耗：38.7 MB, 在所有 Java 提交中擊敗了22.10%的用戶
// ?？?// 運(yùn)行時(shí)間：177ms
// 占用內(nèi)存：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); // 可以打印中間結(jié)果試試
if (numbers[start] == numbers[mid] && numbers[mid] == numbers[end]) { // 如果三索引數(shù)相等，直接for循環(huán)遍歷找最小值
return findMin(numbers, start, end);
}
else if (numbers[mid] <= numbers[end]) { // 這里取end索引和mid索引數(shù)判斷比較方便。
// 因?yàn)槿绻l(fā)生翻轉(zhuǎn)，翻轉(zhuǎn)部分的所有數(shù)值都會(huì)比左邊第一個(gè)數(shù)值要?。ɑ蛳嗟龋?。
// 如果end索引數(shù)比mid索引數(shù)大（或相等），最小值一定在左半邊，end移到mid位置。
end = mid;
}
else // 否則（如果mid索引數(shù)比end索引數(shù)大），start移動(dòng)到mid+1位置
start = mid + 1;
}
return numbers[start]; // 直到start與end索引相遇，直接返回該索引數(shù)
}
// findMin：從左到右，for循環(huán)遍歷找最小值（根據(jù)題意，從左到右遇到的第一個(gè)小數(shù)即為最小數(shù)）
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]
// 運(yùn)行時(shí)間：171ms 超過87.93%用Java提交的代碼
// 占用內(nèi)存：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];
}
}
// 直接解
// 牛客
// 運(yùn)行時(shí)間：204ms
// 占用內(nèi)存：28728KB
// 力扣
// 執(zhí)行用時(shí)：0 ms, 在所有 Java 提交中擊敗了100.00%的用戶
// 內(nèi)存消耗：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. 數(shù)字在排序數(shù)組中出現(xiàn)的次數(shù)
題目描述
// 53. 數(shù)字在排序數(shù)組中出現(xiàn)的次數(shù)
// 力扣
// 統(tǒng)計(jì)一個(gè)數(shù)字在排序數(shù)組中出現(xiàn)的次數(shù)。
// ?？?// 統(tǒng)計(jì)一個(gè)數(shù)字在升序數(shù)組中出現(xiàn)的次數(shù)。
題解
// 二分查找
// ?？?// 二分查找法，構(gòu)建二分查找函數(shù)binarysearch，
// binarysearch函數(shù)，輸入arr和k，通過二分查找方法找到k數(shù)字(的重復(fù)集)，
// 并返回k數(shù)字(的重復(fù)集)末端的下一位索引。
// 具體情況：arr首端索引left，arr末端索引right，對(duì)半找中點(diǎn)索引
// mid = (left + right) / 2，如果中點(diǎn)索引arr[mid]不大于目標(biāo)k，則
// left更新到mid的下一位索引mid+1，如此循環(huán)，直到left到達(dá)第一個(gè)大于
// k的元素的索引。
//
// 主函數(shù)GetNumberOfK則調(diào)用兩次binarysearch，第一次調(diào)用binarysearch(array, k)
// 找k之后第一個(gè)大于k的元素（第一次調(diào)用找到k重復(fù)集的length索引）。
// 第二次調(diào)用binarysearch(array, k - 1)找k-1之后第一個(gè)大于k-1的元素(就是k)，
// （第二次調(diào)用找到k重復(fù)集的0索引），兩個(gè)返回值相減，就是k的出現(xiàn)次數(shù)（k
// 重復(fù)集的長度）
// 運(yùn)行時(shí)間：11ms，超過84.49%用Java提交的代碼
// 占用內(nèi)存：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;
}
}
// 力扣
// 執(zhí)行用時(shí)：0 ms, 在所有 Java 提交中擊敗了100.00%的用戶
// 內(nèi)存消耗：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中缺失的數(shù)字
題目描述
// 53.2 0～n-1中缺失的數(shù)字
// 力扣
// 一個(gè)長度為n-1的遞增排序數(shù)組中的所有數(shù)字都是唯一的，并且每個(gè)數(shù)字都
// 在范圍0～n-1之內(nèi)。在范圍0～n-1內(nèi)的n個(gè)數(shù)字中有且只有一個(gè)數(shù)字不在該
// 數(shù)組中，請(qǐng)找出這個(gè)數(shù)字。
題解
/ 直接法
// 直接法不通用，還是得想想其他方法。
// 力扣
// 根據(jù)題意，說明元素和索引必須相等，不相等說明索引對(duì)應(yīng)的元素缺失，
// 就直接返回索引。如果遍歷完沒發(fā)現(xiàn)元素索引的沖突，說明缺失的就是末端元素
// 直接返回末端的下一位索引。
// 執(zhí)行用時(shí)：0 ms, 在所有 Java 提交中擊敗了100.00%的用戶
// 內(nèi)存消耗：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，對(duì)半取中間位索引mid = (left + right) / 2
// ,如果遍歷的元素nums[mid]和mid相等，說明缺失元素的位置在右半邊，left更新
// 為mid+1,否則（如果遍歷元素nums[mid]>mid），說明缺失元素在左半邊，
// right更新為mid-1，left和right相遇時(shí)即為缺失元素的索引位置，直接返回即可
// 執(zhí)行用時(shí)：0 ms, 在所有 Java 提交中擊敗了100.00%的用戶
// 內(nèi)存消耗：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. 矩陣中的路徑
// 力扣
// 請(qǐng)?jiān)O(shè)計(jì)一個(gè)函數(shù)，用來判斷在一個(gè)矩陣中是否存在一條包含某
// 字符串所有字符的路徑。路徑可以從矩陣中的任意一格開始，
// 每一步可以在矩陣中向左、右、上、下移動(dòng)一格。如果一條路
// 徑經(jīng)過了矩陣的某一格，那么該路徑不能再次進(jìn)入該格子。例
// 如，在下面的3×4的矩陣中包含一條字符串“bfce”的路徑（路徑
// 中的字母用加粗標(biāo)出）。
// [["a","b","c","e"],
// ["s","f","c","s"],
// ["a","d","e","e"]]
// 但矩陣中不包含字符串“abfb”的路徑，因?yàn)樽址牡谝粋€(gè)字符b占
// 據(jù)了矩陣中的第一行第二個(gè)格子之后，路徑不能再次進(jìn)入這個(gè)格子。
// 牛客
// 請(qǐng)?jiān)O(shè)計(jì)一個(gè)函數(shù)，用來判斷在一個(gè)矩陣中是否存在一條包含某字符串所
// 有字符的路徑。路徑可以從矩陣中的任意一個(gè)格子開始，每一步可以在
// 矩陣中向左，向右，向上，向下移動(dòng)一個(gè)格子。如果一條路徑經(jīng)過了矩
// 陣中的某一個(gè)格子，則該路徑不能再進(jìn)入該格子。 例如
// [["a","b","c","e"],
// ["s","f","c","s"],
// ["a","d","e","e"]]
// 矩陣中包含一條字符串"bcced"的路徑，但是矩陣中不包含"abcb"路徑，因
// 為字符串的第一個(gè)字符b占據(jù)了矩陣中的第一行第二個(gè)格子之后，路徑不能
// 再次進(jìn)入該格子。
題解
/// 回溯搜索法 ///
構(gòu)建待搜索矩陣同尺寸的布爾矩陣marked，用于標(biāo)記該位置元素是否被使用過。
設(shè)置路徑步長pathLen，用于同步搜索目標(biāo)的長度。
遍歷待搜索矩陣matrix每一個(gè)位置的元素，對(duì)該位置的元素做所有方向的搜索，搜索不到就回溯到原狀態(tài)，之前修改的marked和pathLen要重置。
// ?？?
// 運(yùn)行時(shí)間 12ms
// 占用內(nèi)存 9592KB
public class Solution {
private final static int[][] next = {{0,-1}, {0,1}, {-1,0}, {1,0}}; // 左右上下四個(gè)方向
private int rows;
private int cols;
// 解題函數(shù)
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]; // 標(biāo)記狀態(tài)矩陣，可標(biāo)記某元素是否被使用，回溯后使用狀態(tài)被清空
char[][] matrix = buildMatrix(array); // 題目給的數(shù)組char[]轉(zhuǎn)化為矩陣char[][]
// 兩層for循環(huán)，遍歷待搜索矩陣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，搜索目標(biāo)str，狀態(tài)標(biāo)記矩陣marked(初始化為全false), 遍歷行r，遍歷列c，已遍歷的路徑步長pathLen(初始化為0)
// 每一次backTracking搜索，路徑長度pathLen將+1，搜索失敗，則回溯進(jìn)行下一次for遍歷
// pathLen又會(huì)重置為0，marked也會(huì)重置為全false。
private boolean backTracking(char[][] matrix, char[] str, boolean[][] marked, int r, int c, int pathLen) {
if (pathLen == str.length) // 如果遍歷路徑步長等于搜索目標(biāo)str的長度，返回true
return true;
if (r < 0 || r >= rows || c < 0 || c >= cols) // 如果遍歷行和列超出邊界，返回false,（回到上一次marked的標(biāo)記和路徑步數(shù)pathLen，即進(jìn)行了回溯）
return false;
if (marked[r][c]) // 如果遍歷元素被使用過，返回false，進(jìn)行回溯
return false;
if (matrix[r][c] != str[pathLen]) // 如果搜索矩陣遍歷元素與當(dāng)前路徑步數(shù)對(duì)應(yīng)的搜索目標(biāo)字符不相等，返回false，進(jìn)行回溯
return false; // 換言之，不返回false，說明遍歷元素與對(duì)應(yīng)目標(biāo)字符是一致的。
marked[r][c] = true; // 當(dāng)前元素標(biāo)記為已被使用
// 開始以當(dāng)前遍歷元素matrix[r][c]為起點(diǎn)進(jìn)行搜索，for循環(huán)取next中左右上下四個(gè)方向，遞歸backTracking進(jìn)行搜索
// 路徑pathLen+1
for (int[] dic : next) {
if (backTracking(matrix, str, marked, r + dic[0], c + dic[1], pathLen + 1)) {
return true;
}
}
// 當(dāng)前遍歷元素搜索結(jié)束，未發(fā)現(xiàn)目標(biāo)，元素標(biāo)記重置回false
marked[r][c] = false;
return false; // 搜索結(jié)束，返回false。進(jìn)行回溯
}
// 將數(shù)組char[]轉(zhuǎn)為矩陣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;
}
}
// 力扣
// 和牛客原理是一樣的
// 執(zhí)行用時(shí)：7 ms, 在所有 Java 提交中擊敗了40.96%的用戶
// 內(nèi)存消耗：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;
}
}
// 差不多的實(shí)現(xiàn)
// 執(zhí)行用時(shí)：8 ms, 在所有 Java 提交中擊敗了24.52%的用戶
// 內(nèi)存消耗：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. 機(jī)器人的運(yùn)動(dòng)范圍
題目描述
// 13. 機(jī)器人的運(yùn)動(dòng)范圍
// 力扣
// 地上有一個(gè)m行n列的方格，從坐標(biāo) [0,0] 到坐標(biāo) [m-1,n-1] 。
// 一個(gè)機(jī)器人從坐標(biāo) [0, 0] 的格子開始移動(dòng)，它每次可以向左、
// 右、上、下移動(dòng)一格（不能移動(dòng)到方格外），也不能進(jìn)入行坐標(biāo)
// 和列坐標(biāo)的數(shù)位之和大于k的格子。例如，當(dāng)k為18時(shí)，機(jī)器人能
// 夠進(jìn)入方格 [35, 37] ，因?yàn)?+5+3+7=18。但它不能進(jìn)入方格 [
// 35, 38]，因?yàn)?+5+3+8=19。請(qǐng)問該機(jī)器人能夠到達(dá)多少個(gè)格子？
// ?？?// 地上有一個(gè)m行和n列的方格。一個(gè)機(jī)器人從坐標(biāo)0,0的格子開始移動(dòng)，
// 每一次只能向左，右，上，下四個(gè)方向移動(dòng)一格，但是不能進(jìn)入行坐
// 標(biāo)和列坐標(biāo)的數(shù)位之和大于k的格子。 例如，當(dāng)k為18時(shí)，機(jī)器人能夠
// 進(jìn)入方格（35,37），因?yàn)?+5+3+7 = 18。但是，它不能進(jìn)入方格（35
// ,38），因?yàn)?+5+3+8 = 19。請(qǐng)問該機(jī)器人能夠達(dá)到多少個(gè)格子？
題解
// 力扣
// 本題使用的方法為深度優(yōu)先搜索(DFS)，方法和12題的回溯法很像，
// 但其實(shí)回溯法是DFS的特殊情況。
// 執(zhí)行用時(shí)：2 ms, 在所有 Java 提交中擊敗了43.58%的用戶
// 內(nèi)存消耗：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;
// 解題函數(shù)
public int movingCount(int m, int n, int k) {
this.rows = m;
this.cols = n;
this.k = k;
if (rows == 0 || cols == 0) // 行或者列其中一個(gè)為0，則返回0
return 0;
if (k == 0) // 如果k為0，則能到達(dá)位置只有(0,0)這第一個(gè)位置
return 1;
boolean[][] marked = new boolean[rows][cols]; // 定義與搜索矩陣同尺寸的標(biāo)記矩陣marked
dfs(marked, 0, 0); // 開始深度優(yōu)先搜索遞歸，起始位置為左上角(0,0)
return count; // 搜索完畢，返回計(jì)數(shù)
}
// 定義搜索函數(shù)
// 輸入標(biāo)記矩陣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) // 超過數(shù)位和的上限，返回
return;
count++; // 如果滿足條件，成功計(jì)數(shù)一次
marked[r][c] = true; // 該位置標(biāo)記為已被使用
// System.out.println(markedToString(marked)); // 打印marked矩陣
for (int[] n : next)
dfs(marked, r + n[0], c + n[1]);
}
// 定義函數(shù)：位數(shù)之和
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函數(shù)（不是必須）
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();
}
}
// 換一種位數(shù)加法的寫法
// 執(zhí)行用時(shí)：2 ms, 在所有 Java 提交中擊敗了44.08%的用戶
// 內(nèi)存消耗：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;
}
}
// ?？?// 思路和力扣是一樣的
// 運(yùn)行時(shí)間：11ms
// 占用內(nèi)存：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]);
}
// 定義函數(shù)：位數(shù)之和
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函數(shù)（不是必須）
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. 調(diào)整數(shù)組順序使奇數(shù)位于偶數(shù)前面
題目描述
// 力扣
// 輸入一個(gè)整數(shù)數(shù)組，實(shí)現(xiàn)一個(gè)函數(shù)來調(diào)整該數(shù)組中數(shù)字的順序，
// 使得所有奇數(shù)位于數(shù)組的前半部分，所有偶數(shù)位于數(shù)組的后半部分。
// ?？?// 輸入一個(gè)整數(shù)數(shù)組，實(shí)現(xiàn)一個(gè)函數(shù)來調(diào)整該數(shù)組中數(shù)字的順序，使得所有
// 的奇數(shù)位于數(shù)組的前半部分，所有的偶數(shù)位于數(shù)組的后半部分，并保證奇
// 數(shù)和奇數(shù)，偶數(shù)和偶數(shù)之間的相對(duì)位置不變。
// ?？偷念}目要難一點(diǎn)點(diǎn)，需要保證奇數(shù)之間，偶數(shù)之間的相對(duì)位置不變。
題解
// 雙指針法 ///
// 力扣
// 執(zhí)行用時(shí)：3 ms, 在所有 Java 提交中擊敗了29.92%的用戶
// 內(nèi)存消耗：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) { // 頭指針找偶數(shù)，尾指針找奇數(shù)
temp = nums[head]; // 偶數(shù)存臨時(shí)變量
nums[head] = nums[end]; // 奇數(shù)放前面
nums[end] = temp;
end -= 1;
head += 1;
}
else if (nums[head] % 2 == 0) { // 頭指針找偶數(shù),尾指針沒找到奇數(shù)
end -= 1;
continue;
}
else if (nums[end] % 2 != 0) { // 尾指針找奇數(shù)，頭指針沒找到
head += 1;
continue;
}
else {
end -= 1;
head += 1;
}
}
return nums;
}
}
// 簡(jiǎn)化一下
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;
}
}
/ 直接法 /
// ?？?// 運(yùn)行時(shí)間：9ms
// 占用內(nèi)存：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;
}
}
}
// 判斷是否是偶數(shù)
private boolean isEven(int x) {
return (x % 2 == 0);
}
}
// 力扣
// 執(zhí)行用時(shí)：4 ms, 在所有 Java 提交中擊敗了9.50%的用戶
// 內(nèi)存消耗：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;
}
// 判斷是否是偶數(shù)
private boolean isEven(int x) {
return (x % 2 == 0);
}
}
冒泡
// ?？?// 運(yùn)行時(shí)間：9ms
// 占用內(nèi)存：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;
}
}
}
}
// 判斷是否是偶數(shù)
private boolean isEven(int x) {
return (x % 2 == 0);
}
}
【劍指offer】51. 數(shù)組中的逆序?qū)?/h4>
題目描述
// 51. 數(shù)組中的逆序?qū)?
// 力扣
// 在數(shù)組中的兩個(gè)數(shù)字，如果前面一個(gè)數(shù)字大于后面的數(shù)字，則這兩
// 個(gè)數(shù)字組成一個(gè)逆序?qū)Α］斎胍粋€(gè)數(shù)組，求出這個(gè)數(shù)組中的逆序?qū)?// 的總數(shù)。
// ?？?// 在數(shù)組中的兩個(gè)數(shù)字，如果前面一個(gè)數(shù)字大于后面的數(shù)字，則這兩個(gè)數(shù)
// 字組成一個(gè)逆序?qū)?。輸入一個(gè)數(shù)組,求出這個(gè)數(shù)組中的逆序?qū)Φ目倲?shù)P。
// 并將P對(duì)1000000007取模的結(jié)果輸出。 即輸出P%1000000007
題解
暴力法 ///
// 最直觀的的做法是兩個(gè)for循環(huán)全部遍歷比對(duì)一輪
// 但是這種做法時(shí)間復(fù)雜度無法通過。
// 力扣
// 無法通過
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;
}
}
歸并排序法
// ?？?// 根據(jù)題意，前大后小的兩個(gè)數(shù)字構(gòu)成一個(gè)逆序?qū)Α?// 直接寫一個(gè)歸并排序，在merge函數(shù)當(dāng)nums[l]<nums[r]時(shí)，記錄逆序?qū)€(gè)數(shù)
// 運(yùn)行時(shí)間：235ms
// 占用內(nèi)存：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合并有序數(shù)組，所以左子數(shù)組是升序的，右子數(shù)組也是升序的
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右移如果出現(xiàn)了nums[l]>nums[r],
// 說明l到mid的數(shù)，跟nums[r]都組成逆序?qū)Α＃w并排序，左子數(shù)組元
// 素排序后還會(huì)在左子數(shù)組，右子數(shù)組元素排序后還會(huì)在右子數(shù)組）
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++];
}
}
// 力扣
// 執(zhí)行用時(shí)：37 ms, 在所有 Java 提交中擊敗了61.83%的用戶
// 內(nèi)存消耗：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++];
}
}
特殊解——位運(yùn)算
【劍指offer】56. 數(shù)組中數(shù)字出現(xiàn)的次數(shù)
題目描述
// 56. 數(shù)組中數(shù)字出現(xiàn)的次數(shù)
// 力扣
// 一個(gè)整型數(shù)組 nums 里除兩個(gè)數(shù)字之外，其他數(shù)字都出現(xiàn)了兩次
// 。請(qǐng)寫程序找出這兩個(gè)只出現(xiàn)一次的數(shù)字。要求時(shí)間復(fù)雜度是O(
// n)，空間復(fù)雜度是O(1)。
// ?？?// 一個(gè)整型數(shù)組里除了兩個(gè)數(shù)字之外，其他的數(shù)字都出現(xiàn)了兩次。請(qǐng)寫
// 程序找出這兩個(gè)只出現(xiàn)一次的數(shù)字。
題解
集合輔助解
集合輔助
// 第一時(shí)間能想到的簡(jiǎn)單方法，好理解但不是最優(yōu)
// 力扣
// 定義一個(gè)集合set，遍歷nums中的所有元素nums[i]，并將nums[i]存入set中
// 如果存不進(jìn)，說明nums[i]出現(xiàn)了2次，在set中刪除nums[i]，留下來的就
// 都是只出現(xiàn)過一次的元素了，提取出來存入數(shù)組res中，返回即可。
// 執(zhí)行用時(shí)：13 ms, 在所有 Java 提交中擊敗了10.23%的用戶
// 內(nèi)存消耗：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;
}
}
// ?？?// 運(yùn)行時(shí)間：11ms，超過59.56%用Java提交的代碼
// 占用內(nèi)存：11092KB，超過51.92%用Java提交的代碼
import java.util.*;
public class Solution {
/**
* 代碼中的類名、方法名、參數(shù)名已經(jīng)指定，請(qǐng)勿修改，直接返回方法規(guī)定的值即可
*
*
* @param array int整型一維數(shù)組
* @return int整型一維數(shù)組
*/
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;
}
}
最優(yōu)解
/// 位運(yùn)算法 /
// 位運(yùn)算法才是真正要學(xué)的最優(yōu)解法
// 首先需要說明，異或操作 ^ 的性質(zhì)包括：
// 交換律
// 結(jié)合律
// A ^ 0 = A;
// A ^ A = 0
// 問題一：
// 假設(shè)nums只存在1個(gè)只出現(xiàn)過1次的數(shù)字，為A，其他數(shù)字都出現(xiàn)了2次
// 且nums數(shù)組為{10, 10, A, 2, 5, 5, 2}，那么我們把數(shù)字全部異或起來
// 就可以把A分離出來，
// 即 10^10^A^2^5^5^2 = 10^10^2^2^5^5^A (交換律) = 0^0^0^A = A
// 如果把題目換成這樣，本題就做完了，可惜換不得。
//
// 問題二：
// 題目中，數(shù)組nums存在2個(gè)只出現(xiàn)1次的數(shù)字，假設(shè)為A，B。
// 其他數(shù)字都出現(xiàn)了兩次，我們假設(shè)nums數(shù)組為{10, 10, A, 2, 5, B, 5, 2}。
// 那么我們是否可以把這道題分解為兩個(gè)問題一來解決呢？
// 化繁為簡(jiǎn)，先把nums中所有元素異或起來，得到
// 10^10^A^2^5^B^5^2 = A^B。
// A B肯定是不同的數(shù)，既然是不同的數(shù)，A B一定存在某一位(假設(shè)是第x位)
// 上的數(shù)是不同的，而在二進(jìn)制視角中，數(shù)字要么是1要么是0，
// 所以在第x位上要么A是1,B是0，要么B是1,A是0，這樣才有A B在第x位上的
// 數(shù)是不同的。所以A B的異或A^B，在第x位上一定等于1 (1^0=1)。
//
// 我們用 A^B第x位上的1，來把問題二分解成問題一。
// 我們?cè)O(shè)置一個(gè)輔助參數(shù) one=1（二進(jìn)制00000001），循環(huán)左移和A^B來做
// 邏輯與運(yùn)算，來找這個(gè)第x位，如果one & (A^B) == 0，one就左移，
// 直到one & (A^B) != 0，說明找到了第x位。
//
// 然后循環(huán)遍歷nums中的數(shù)，記為num，還記得第x位上要么A是1,B是0，
// 要么B是1,A是0，我們把num和one直接做與運(yùn)算，
// 用if條件判斷，把所有邏輯與的結(jié)果是1的數(shù)字，全部異或到int x參數(shù)上。
// 用if條件判斷，把所有邏輯與的結(jié)果是0的數(shù)字，全部異或到int y參數(shù)上。
// 這樣，不管第x位上A B是0還是1，我們都把它們分開到了不同的地方去異或
// 就把問題二分解成了兩個(gè)問題一。最后直接返回x和y就行~
// 力扣
// 執(zhí)行用時(shí)：1 ms, 在所有 Java 提交中擊敗了100.00%的用戶
// 內(nèi)存消耗：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};
}
}
// 牛客
// ?？捅攘鄱嗔艘稽c(diǎn)，需要把小的數(shù)排在前面，其他都一樣
// 運(yùn)行時(shí)間：13ms，超過24.78%用Java提交的代碼
// 占用內(nèi)存：11092KB，超過51.91%用Java提交的代碼
public class Solution {
/**
* 代碼中的類名、方法名、參數(shù)名已經(jīng)指定，請(qǐng)勿修改，直接返回方法規(guī)定的值即可
*
*
* @param array int整型一維數(shù)組
* @return int整型一維數(shù)組
*/
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 數(shù)組中數(shù)字出現(xiàn)的次數(shù)
題目描述
// 56.2 數(shù)組中數(shù)字出現(xiàn)的次數(shù)
// 力扣
// 在一個(gè)數(shù)組 nums 中除一個(gè)數(shù)字只出現(xiàn)一次之外，其他數(shù)字都出現(xiàn)
// 了三次。請(qǐng)找出那個(gè)只出現(xiàn)一次的數(shù)字。
題解
// 力扣
// 在一個(gè)數(shù)組 nums 中除一個(gè)數(shù)字只出現(xiàn)一次之外，其他數(shù)字都出現(xiàn)了三次
// 。請(qǐng)找出那個(gè)只出現(xiàn)一次的數(shù)字。
// 創(chuàng)建計(jì)數(shù)數(shù)組count，記錄所有nums元素在二進(jìn)制表示下每一位出現(xiàn)1的次數(shù)
// 比如count[0]就是nums所有元素在最低位出現(xiàn)1的次數(shù)。
//
// 一個(gè)雙for循環(huán)，第一個(gè)for遍歷nums的元素num，第二個(gè)for遍歷計(jì)數(shù)數(shù)組索引j，
// 也就是從低到高遍歷num的每一位二進(jìn)制位。
// 如果num & 1為1，則當(dāng)前邏輯運(yùn)算結(jié)果1累加到count[j]中，然后
// num整體右移1一格num = num >>> 1，j也右移一位，即開始遍歷下一位
// 二進(jìn)制位，再和1做邏輯與，如此循環(huán)。第二層for循環(huán)走一輪能找出一個(gè)num的
// 所有位出現(xiàn)1的次數(shù)，并記錄到count的相應(yīng)位置中。
// 兩個(gè)for循環(huán)之后，能把所有nums的元素的所有位出現(xiàn)的1累計(jì)到count的相應(yīng)位置
// 第二個(gè)for循環(huán)，倒序遍歷count，索引為i，索引的計(jì)數(shù)元素為count[i]，
// 由于需要找出的目標(biāo)元素target出現(xiàn)了1次，其他元素都出現(xiàn)了3次，
// 所以其他元素對(duì)應(yīng)的二進(jìn)制位出現(xiàn)1的次數(shù)一定是3的倍數(shù)，如果該位出現(xiàn)
// 1的次數(shù)不是3的倍數(shù)，無法整除3，說明該位一定出現(xiàn)了target的1。我們將
// 余數(shù)或邏輯運(yùn)算賦給變量res中，然后res左移，i左移，如此循環(huán)，可以把
// count中所有位中屬于target的二進(jìn)制1賦給res，使得res等于target。
// 最后返回res即可。
// 執(zhí)行用時(shí)：5 ms, 在所有 Java 提交中擊敗了85.82%的用戶
// 內(nèi)存消耗：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;
}
}
// 啰嗦一點(diǎn)的寫法，比較好理解
// 執(zhí)行用時(shí)：14 ms, 在所有 Java 提交中擊敗了48.98%的用戶
// 內(nèi)存消耗：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的兩個(gè)數(shù)字
題目描述
// 57. 和為s的兩個(gè)數(shù)字
// 力扣
// 輸入一個(gè)遞增排序的數(shù)組和一個(gè)數(shù)字s，在數(shù)組中查找兩個(gè)數(shù)，
// 使得它們的和正好是s。如果有多對(duì)數(shù)字的和等于s，則輸出任意
// 一對(duì)即可。
// ?？?// 輸入一個(gè)遞增排序的數(shù)組和一個(gè)數(shù)字S，在數(shù)組中查找兩個(gè)數(shù)，
// 使得他們的和正好是S，如果有多對(duì)數(shù)字的和等于S，輸出兩個(gè)
// 數(shù)的乘積最小的。
題解
// 力扣
// 前后雙指針，求的和sum與target比較，
// sum大了，右指針左移，減小sum，
// sum小了，左指針右移，增大sum。
// 執(zhí)行用時(shí)：2 ms, 在所有 Java 提交中擊敗了94.94%的用戶
// 內(nèi)存消耗：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];
}
}
// 牛客
// 運(yùn)行時(shí)間：10ms，超過89.79%用Java提交的代碼
// 占用內(nèi)存：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的兩個(gè)數(shù)字
題目描述
// 57.2 和為s的兩個(gè)數(shù)字
// 力扣
// 輸入一個(gè)正整數(shù) target ，輸出所有和為 target 的連續(xù)正整數(shù)序列
// （至少含有兩個(gè)數(shù)）。
// 序列內(nèi)的數(shù)字由小到大排列，不同序列按照首個(gè)數(shù)字從小到大排列。
// ?？?// 小明很喜歡數(shù)學(xué),有一天他在做數(shù)學(xué)作業(yè)時(shí),要求計(jì)算出9~16的和,他馬上
// 就寫出了正確答案是100。但是他并不滿足于此,他在想究竟有多少種連續(xù)
// 的正數(shù)序列的和為100(至少包括兩個(gè)數(shù))。沒多久,他就得到另一組連續(xù)正
// 數(shù)和為100的序列:18,19,20,21,22?，F(xiàn)在把問題交給你,你能不能也很快
// 的找出所有和為S的連續(xù)正數(shù)序列? Good Luck!
題解
// ?？?// 思路簡(jiǎn)單，但是能做出來還是不容易的。
// 從前面初始化兩個(gè)指針left和right，由于至少包含2個(gè)數(shù)，且必須是正整數(shù)
// 所以left初始化為1（left至少為1），right比left大，right至少為2，
// 累計(jì)的數(shù)組和至少為3，所以初始化累計(jì)和sum為3，
// 開始比較sum與target大小，如果sum比target小，需要窗口擴(kuò)大，right右移
// 右移之后sum累加right，如果sum比target大，需要窗口縮小，left右移，
// sum累減left，之后left再右移（注意是先指針移動(dòng)還是先操作sum加減）
// 直到sum等于target，將left到right之間所有元素存入新指定的ArrayList中
// 再存入res中。
// 運(yùn)行時(shí)間：15ms,超過87.63%用Java提交的代碼
// 占用內(nèi)存：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;
}
}
// 力扣
// 執(zhí)行用時(shí)：2 ms, 在所有 Java 提交中擊敗了97.62%的用戶
// 內(nèi)存消耗：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. 股票的最大利潤
題目描述
文章來源：http://www.zghlxwxcb.cn/news/detail-473398.html
// 63. 股票的最大利潤
// 力扣
// 假設(shè)把某股票的價(jià)格按照時(shí)間先后順序存儲(chǔ)在數(shù)組中，請(qǐng)問買賣該
// 股票一次可能獲得的最大利潤是多少？
題解文章來源地址http://www.zghlxwxcb.cn/news/detail-473398.html
// 貪心算法
// 力扣
// 初始化min
// 執(zhí)行用時(shí)：2 ms, 在所有 Java 提交中擊敗了66.58%的用戶
// 內(nèi)存消耗：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;
}
}
到了這里，關(guān)于【劍指offer】數(shù)據(jù)結(jié)構(gòu)——數(shù)組的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
