在一个长度为n+1的数组里的所有数字都在1~n的范围内,所以数组中至少存在一个数字是重复的。 请找出数组中任意一个重复的数字,但不能修改输入的数组。 例如输入长度为8的数组{2,3,5,4,3,2,6,7},那么对应的输出是重复的数字2或者3。
public class Sl {
/**
* 思路:二路计数,由于n+1长度的数组都在1-n之间,所以可以用区间个数来找重复的数
* 比如,如果数组长度为8,则数字都在1-7之间,将数字的区间分为[1-4]和[5-7]
* 然后如果数组中的数在[1-4]中的数超过了4个,则重复的数一定在这个区间中。
* 否则就在[5-7]中。然后对区间再次划分,比如如果重复的数在[1-4]中,将区间划分为[1-2]和[3-4],重复上述步骤。
* 最后如果发现重复数字在[3-4]中,就查找3出现的次数和4出现的次数,就能找到那个重复的数
*/
public int findRepeatNumber(int[] nums) {
if (nums.length < 2 || nums == null) {
return -1;
}
//定义初始区间
int start = 1;
int end = nums.length - 1;
while (start <= end) {
// 中位数
int mid = ((end - start) >> 1) + start;
// 统计区间中的数字的数量
int count = countRange(nums, start, mid);
// 如果此时区间只有一个数,判断count是否>1,大于一说明就是这个数重复,不大于一说明找不到重复的数
if (start == end) {
if (count > 1)
return start;
else
return -1;
}
if (count > mid - start + 1) {
end = mid;
} else {
start = mid + 1;
}
}
return -1;
}
// 用来统计[start,end]中的数组个数
private int countRange(int[] nums, int start, int end) {
int count = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] >= start && nums[i] <= end) {
count++;
}
}
return count;
}
}
/**
* 找出数组中重复的数字。
* <p>
* 在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
* <p>
* 示例 1:
* 输入:
* [2, 3, 1, 0, 2, 5, 3]
* 输出:2 或 3
* <p>
* 限制:
* 2 <= n <= 100000
*/
public class 剑指Offer03数组中重复的数字 {
/**
* 思路:利用哈希桶思想,从头开始遍历数组,如果nums[i] == i,说明放置正确,跳过
* 如果nums[i] != i;就把nums[i]放到nums[nums[i]]上去,一直到nums[i] == i为止。
* 如果在放置nums[i]的过程中发现nums[nums[i]] == nums[i],说明nums[i]重复了
*/
public int findRepeatNumber(int[] nums) {
for (int i = 0; i < nums.length; i++) {
while (nums[i] != i) {
if (nums[nums[i]] == nums[i]) {
return nums[i];
}
int temp = nums[i];
nums[i] = nums[temp];
nums[temp] = temp;
}
}
return -1;
}
}
/**
* 在一个 n * m 的二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。
* 请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
* <p>
* 示例:
* 现有矩阵 matrix 如下:
* [
* [1, 4, 7, 11, 15],
* [2, 5, 8, 12, 19],
* [3, 6, 9, 16, 22],
* [10, 13, 14, 17, 24],
* [18, 21, 23, 26, 30]
* ]
* 给定 target = 5,返回 true。
* 给定 target = 20,返回 false。
* 限制:
* 0 <= n <= 1000
* 0 <= m <= 1000
*/
public class 剑指Offer04二维数组中的查找 {
/**
* 思路:nums[0].leng = n。选取数组右上角的数字nums[0][n-1],比较target和nums[0][n-1]的大小。
* 如果target > nums[0][n-1],说明target只能在nums[0][n-1]的下面,于是排除第一行,即nums[0]。
* 如果target < nums[0][n-1],说明target只能在nums[0][n-1]的左边,于是排除最后一列,即nums[i][n-1]。
* 依次类推,每次选择右上角进行排除,直到找到target为止
*/
public boolean findNumberIn2DArray(int[][] matrix, int target) {
boolean found = false;
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return found;
// 先定义指针
int downMax = matrix.length - 1; // 往下搜索的边界
int rightMax = matrix[0].length - 1; // 往右搜索的边界
int downCurr = 0;
int rightCurr = matrix[0].length - 1; // 初始化一开始从右上角搜索
while (downCurr >= 0 && rightCurr >= 0 && downCurr <= downMax && rightCurr <= rightMax) {
if (matrix[downCurr][rightCurr] == target) {
found = true;
break;
} else if (matrix[downCurr][rightCurr] < target) {
downCurr++;
} else {
rightCurr--;
}
}
return found;
}
}
/**
* 输入一个链表的头节点,从尾到头反过来返回每个节点的值(用数组返回)。
* 示例 1:
* 输入:head = [1,3,2]
* 输出:[2,3,1]
*/
public class 剑指Offer06从尾到头打印链表 {
/**
* 思路:利用栈先进后出来倒序打印
*/
public int[] reversePrint(ListNode head) {
Stack<ListNode> stack = new Stack<>();
ListNode curr = head;
while (curr != null) {
stack.push(curr);
curr = curr.next;
}
int[] res = new int[stack.size()];
for (int i = 0; i < res.length; i++){
res[i] = stack.pop().val;
}
return res;
}
}
class CQueue {
private Stack<Integer> stack1, stack2;
public CQueue() {
stack1 = new Stack<>();
stack2 = new Stack<>();
}
public void appendTail(int value) {
stack1.push(value);
}
public int deleteHead() {
if (!stack2.isEmpty()) {
return stack2.pop();
} else if (!stack1.isEmpty()) {
while (!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
return stack2.pop();
} else {
return -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。
* 来源:力扣(LeetCode)
* 链接:https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof
* 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
*/
public class 剑指Offer10_I斐波那契数列 {
public int fib1(int n) {
if (n == 0) return 0;
if (n <= 2) return 1;
int[] arr = new int[2];
arr[1] = 1;
for (int i = 2; i <= n; i++) {
arr[i % 2] = (arr[(i - 1) % 2] + arr[(i - 2) % 2]) % 1000000007;
}
return arr[n % 2];
}
public int fib(int n) {
if (n == 0 || n == 1) return n;
int f1 = 0;
int f2 = 1;
for (int i = 2; i <= n; i++) {
int temp = (f1 + f2) % 1000000007;
f1 = f2;
f2 = temp;
}
return f2;
}
}
/**
* 请设计一个函数,用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。
* 路径可以从矩阵中的任意一格开始,每一步可以在矩阵中向左、右、上、下移动一格。
* 如果一条路径经过了矩阵的某一格,那么该路径不能再次进入该格子。
* 例如,在下面的3×4的矩阵中包含一条字符串“bfce”的路径(路径中的字母用加粗标出)。
* <p>
* [["a","b","c","e"],
* ["s","f","c","s"],
* ["a","d","e","e"]]
* <p>
* 但矩阵中不包含字符串“abfb”的路径,因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后,路径不能再次进入这个格子。
* <p>
*
* <p>
* 示例 1:
* <p>
* 输入:board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
* 输出:true
* 示例 2:
* <p>
* 输入:board = [["a","b"],["c","d"]], word = "abcd"
* 输出:false
* <p>
* 来源:力扣(LeetCode)
* 链接:https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof
* 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
*/
public class 剑指Offer12矩阵中的路径 {
/**
* 思路,DFS
*
* @param board
* @param word
* @return
*/
public boolean exist(char[][] board, String word) {
if (word.length() == 0 || word == null) {
return true;
}
int x = board.length;
int y = board[0].length;
char[] wordArr = word.toCharArray();
boolean[][] used = new boolean[x][y];
for (int i = 0; i < x; i++) {
for (int j = 0; j < y; j++) {
if (board[x][y] == wordArr[0] && dfs(board, wordArr, used, 0, x, y)) {
return true;
}
}
}
return false;
}
private boolean dfs(char[][] board, char[] wordArr, boolean[][] used, int path, int x, int y) {
boolean res = false;
if (path == wordArr.length) {
return true;
}
if (x >= 0 && y >= 0 && x < board.length && y < board[0].length
&& board[x][y] == wordArr[path] && !used[x][y]) {
used[x][y] = true;
res = dfs(board, wordArr, used, path + 1, x - 1, y)
|| dfs(board, wordArr, used, path + 1, x, y + 1)
|| dfs(board, wordArr, used, path + 1, x + 1, y)
|| dfs(board, wordArr, used, path + 1, x, y - 1);
used[x][y] = false;
}
return res;
}
}
/**
* 地上有一个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。请问该机器人能够到达多少个格子?
*
*
*
* 示例 1:
*
* 输入:m = 2, n = 3, k = 1
* 输出:3
* 示例 2:
*
* 输入:m = 3, n = 1, k = 0
* 输出:1
* 提示:
*
* 1 <= n,m <= 100
* 0 <= k <= 20
*
* 来源:力扣(LeetCode)
* 链接:https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof
* 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
*/
public class 剑指Offer13机器人的运动范围 {
public int movingCount(int m, int n, int k) {
if (m == 0 || n == 0) {
return 0;
}
boolean[][] visited = new boolean[n][m];
return dfs(0, 0, n, m, k, visited);
}
private int dfs(int x, int y, int xMax, int yMax, int k, boolean[][] visited) {
if (x < 0 || y < 0 || x >= xMax || y >= yMax || sum(x) + sum(y) > k || visited[x][y]) {
return 0;
}
visited[x][y] = true;
return 1 + dfs(x + 1, y, xMax, yMax, k, visited) + dfs(x, y + 1, xMax, yMax, k, visited);
}
private int sum(int x) {
int sum = 0;
while(x != 0) {
sum += x % 10;
x = x / 10;
}
return sum;
}
}
/**
* 在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数。
* 示例 1:
* 输入: [7,5,6,4]
* 输出: 5
*/
public class 剑指Offer51数组中的逆序对 {
/**
* 利用归并排序的思想,在合并排序的时候,如果右边数组的数小于左边数组的数,那么右边数组的这个数一定小于左边数组的所有数
*/
int[] leftArray;
int res;
public int reversePairs(int[] nums) {
res = 0;
int n = nums.length;
leftArray = new int[n >> 1];
sort(nums, 0, n);
for (int i : nums) {
System.out.print(i + " ");
}
return res;
}
private void sort(int[] nums, int begin, int end) {
if ((end - begin) < 2) return;
int mid = begin + ((end - begin) >> 1);
sort(nums, begin, mid);
sort(nums, mid, end);
merge(nums, begin, mid, end);
}
private void merge(int[] nums, int begin, int mid, int end) {
int leftBegin = 0;
int leftEnd = mid - begin;
int rightBegin = mid;
int rightEnd = end;
int sortPoint = begin;
for (int i = 0; i < leftEnd; i++) {
leftArray[i] = nums[begin + i];
}
while (leftBegin < leftEnd) {
if (rightBegin < rightEnd && nums[rightBegin] < leftArray[leftBegin]) {
nums[sortPoint++] = nums[rightBegin++];
res += leftEnd - leftBegin;
} else {
nums[sortPoint++] = leftArray[leftBegin++];
}
}
}
}
我的博客即将同步至腾讯云+社区,邀请大家一同入驻:/developer/support-plan?invite_code=t2p93xifq7dh