13. 找出数组中重复的数字
给定一个长度为 n 的整数数组 nums，数组中所有的数字都在 0∼n−1 的范围内。
数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。
请找出数组中任意一个重复的数字。
注意：如果某些数字不在 0∼n−1 的范围内，或数组中不包含重复数字，则返回 -1；
class Solution {
public int duplicateInArray(int[] nums) {
int n = nums.length;
for (int num : nums) {
if (num < 0 || num >=n) {
return -1;
}
}
for (int i = 0; i < n; i++) {
if ( i != nums[i]&&nums[nums[i]] == nums[i]){
return nums[i];
}
if ( i != nums[i]&&nums[nums[i]] != nums[i]){
int temp = nums[nums[i]];
nums[nums[i]] = nums[i];
nums[i] = temp;
}
}
return -1;
}
}数组长度为n，找出重复的数字，我们可以先想数组如果不包含重复数字的情况，这样的数组根据题意确实是存在的，下标对应的数组就是下标的数值，有重复的数字的话必定有一个下标可以对应两个数字，这样我们就可以通过遍历来求解了。
当数组下标不等于当前的数值的时候，找到当前数值对应的数组下标，将两数交换;
当数组下标等于当前的数值的时候，我们就找到了我们要的数;
注意判断的时候要排除掉已经交换好了的位置。
14. 不修改数组找出重复的数字
给定一个长度为 n+1 的数组nums，数组中所有的数均在 1∼n 的范围内，其中 n≥1。
请找出数组中任意一个重复的数，但不能修改输入的数组。
给定 nums = [2, 3, 5, 4, 3, 2, 6, 7]。 返回 2 或 3。
这题是分治思想和抽屉原理的一个结合，首先将数组一分为二，就给定的例子来说，数组被分为了[2,3,5,4]和[3,2,6,7]两个部分，我们将整个数组遍历，前半段数组对应的下标为[0,1,2,3]，当出现属于这半段数组的数值时，设置一个变量，将其累加，这里的count=10，可是本来属于这段的数组数值之和最多就是0+1+2+3=6，所以我们判定重复的数字在这段里面，然后右边界左移，循环上面的步骤
class Solution {
public int duplicateInArray(int[] nums) {
int left = 1;
int right = nums.length - 1;
while(left < right){
int mid = (left + right) / 2;
int count = 0;
for (int num : nums) {
if(left <= num && num <= mid)
count += num;
}
if(count > right - left + 1){
right = mid;
}else{
left = mid + 1;
}
}
return right;
}
}15. 二维数组中的查找
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。
请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
输入数组： [ [1,2,8,9]， [2,4,9,12]， [4,7,10,13]， [6,8,11,15] ] 如果输入查找数值为7，则返回true， 如果输入查找数值为5，则返回false。
d要从右上角开始找啊，右上角往下面是大数，往左边是小数，从右上角开始。
class Solution {
public boolean searchArray(int[][] array, int target) {
if(array.length == 0 || array[0].length == 0){
return false;
}
int x = 0;
int y = array[0].length - 1;
while(y>=0&&x<=array.length-1){
if(array[x][y] == target) {
return true;
}
if(array[x][y] > target){
y--;
}else{
x++;
}
}
return false;
}
}18. 重建二叉树
输入一棵二叉树前序遍历和中序遍历的结果，请重建该二叉树。
注意:
二叉树中每个节点的值都互不相同；
输入的前序遍历和中序遍历一定合法；
给定：
前序遍历是：[3, 9, 20, 15, 7]
中序遍历是：[9, 3, 15, 20, 7]
返回：[3, 9, 20, null, null, 15, 7, null, null, null, null]
返回的二叉树如下所示：
3
/ \
9 20
/ \
15 7前序找根，中序确定左右子树;
前序找根，中序确定左右子树;
class Solution {
public TreeNode buildTree(int[] pre, int[] in) {
if (pre.length == 0) {
return null;
}
if (pre.length == 1) {
return new TreeNode(pre[0]);
}
TreeNode root = new TreeNode(pre[0]);
int rootIndex = 0;
for (int i = 0; i < in.length; i++) {
if (in[i] == root.val) {
rootIndex = i;
break;
}
}
root.left = buildTree(Arrays.copyOfRange(pre, 1, rootIndex+1), Arrays.copyOfRange(in, 0, rootIndex));
root.right = buildTree(Arrays.copyOfRange(pre, rootIndex + 1, pre.length), Arrays.copyOfRange(in, rootIndex + 1, in.length));
return root;
}
}19. 二叉树的下一个节点
给定一棵二叉树的其中一个节点，请找出中序遍历序列的下一个节点。
注意：
如果给定的节点是中序遍历序列的最后一个，则返回空节点;
二叉树一定不为空，且给定的节点一定不是空节点；
假定二叉树是：[2, 1, 3, null, null, null, null]， 给出的是值等于2的节点。 则应返回值等于3的节点。 解释：该二叉树的结构如下，2的后继节点是3。 2 / \ 1 3
咳咳，一开始是想直接中序遍历求下一个节点的，但是题中是给一个节点，而不是给根节点，这样的话中序遍历的时间复杂度就太高了。
这题的关键在这两点：
1.根据中序遍历的性质，如果一个节点有右子树，那么他的下一个节点就是它的右子树最左节点
2.要是一个节点没有右子树的话要分两种情况：一是它是父节点的左儿子，那么它的下一个节点就是它的父节点;二是它是父节点的右儿子，要沿着父节点一直向上找，知道成为父节点的左儿子，它的父节点就是下一个节点
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode father;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode inorderSuccessor(TreeNode p) {
if(p.right!=null){
p = p.right;
while(p.left!=null){
p = p.left;
}
return p;
}
while(p.father!=null && p == p.father.right){
p = p.father;
}
return p.father;
}
}22. 旋转数组的最小数字
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
输入一个升序的数组的一个旋转，输出旋转数组的最小元素。
例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。
数组可能包含重复项。
注意：数组内所含元素非负，若数组大小为0，请返回-1。
输入：nums=[2,2,2,0,1] 输出：0
这题真是涨姿势，想了半天没想出来，看了视频一画图真的思路异常清晰。
一个升序数组，旋转之后是这样的，越高数值就越大
通过分析我们可以得出三种情况：
这样就可以设置一个变量，从后往前遍历啦
class Solution {
public int findMin(int[] nums) {
int len = nums.length - 1;
if(len < 0) return -1;
while(len > 0 && nums[0] == nums[len]) len--;
if(nums[len] >= nums[0]) return nums[0];
int left = 0;
int right = len;
while(left < right){
int mid = (left + right) / 2;
if(nums[mid] < nums[0]) right = mid;
else left = mid + 1;
}
return nums[right];
}
}
23. 矩阵中的路径
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。
路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。
如果一条路径经过了矩阵中的某一个格子，则之后不能再次进入这个格子。
注意：
输入的路径不为空；
所有出现的字符均为大写英文字母；
样例：
matrix= [ ["A","B","C","E"], ["S","F","C","S"], ["A","D","E","E"] ] str="BCCE" , return "true" str="ASAE" , return "false"
这是一个典型的可以用dfs解决的问题，首先先遍历整个数组找到开始的点，然后枚举出所有可能性，对其进行深度优先遍历，这里要注意边界条件以及不能重复进入格子。
class Solution {
public boolean hasPath(char[][] matrix, String str) {
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
if (dfs(matrix, str, 0, i, j)) {
return true;
}
}
}
return false;
}
public boolean dfs(char[][] matrix, String str, int c, int x, int y) {
if (matrix[x][y] != str.charAt(c)) return false;
if (c == str.toCharArray().length - 1) return true;
char temp = matrix[x][y];
int[] dx = {-1, 0, 1, 0};
int[] dy = {0, 1, 0, -1};
matrix[x][y] = '*';
for (int i = 0; i < 4; i++) {
int a = x + dx[i];
int b = y + dy[i];
if(a >= 0 && a < matrix.length && b >= 0 && b < matrix[a].length){
if(dfs(matrix, str, c+1, a, b)){
return true;
}
}
}
matrix[x][y] = temp;
return false;
}
}
京公网安备 11010502036488号