=## 数组中的重复数字
class Solution {
public int findRepeatNumber(int[] nums) {
Set<Integer> set = new HashSet<Integer>();
for(int i =0;i<nums.length;i++){
if(set.contains(nums[i])){
return nums[i];
}
set.add(nums[i]);
}
return Integer.MAX_VALUE;
}
}
由于数组元素的值都在指定的范围内，这个范围恰恰好与数组的下标可以一一对应；
因此看到数值，就可以知道它应该放在什么位置，这里数字nums[i] 应该放在下标为 i 的位置上，这就像是我们人为编写了哈希函数，这个哈希函数的规则还特别简单；
而找到重复的数就是发生了哈希冲突；
类似问题还有「力扣」第 41 题： 缺失的第一个正数、「力扣」第 442 题： 数组中重复的数据、「力扣」第 448 题： 找到所有数组中消失的数字 。
分析：这个思路利用到了数组的元素值的范围恰好和数组的长度是一样的，因此数组本身可以当做哈希表来用。遍历一遍就可以找到重复值，但是修改了原始数组。
public class Solution {
public int findRepeatNumber(int[] nums) {
int len = nums.length;
for (int i = 0; i < len; i++) {
// 如果当前的数 nums[i] 没有在下标为 i 的位置上，就把它交换到下标 i 上
// 交换过来的数还得做相同的操作，因此这里使用 while
// 可以在此处将数组输出打印，观察程序运行流程
// System.out.println(Arrays.toString(nums));
while (nums[i] != i) {
if (nums[i] == nums[nums[i]]) {
// 如果下标为 nums[i] 的数值 nums[nums[i]] 它们二者相等
// 正好找到了重复的元素，将它返回
return nums[i];
}
swap(nums, i, nums[i]);
}
}
throw new IllegalArgumentException("数组中不存在重复数字！");
}
private void swap(int[] nums, int index1, int index2) {
int temp = nums[index1];
nums[index1] = nums[index2];
nums[index2] = temp;
}
}
class Solution {
public boolean findNumberIn2DArray(int[][] matrix, int target) {
if(matrix==null){
return false;
}
int n = matrix.length;
if(n==0){
return false;
}
int m = matrix[0].length;
if(m==0){
return false;
}
int i = 0;
int j = m-1;
while(i<n&&j>=0){
if(matrix[i][j]>target){
j--;
}else if(matrix[i][j]<target){
i++;
}else{
return true;
}
}
return false;
}
}
class Solution {
public String replaceSpace(String s) {
if(s.length()==0){
return "";
}
StringBuilder sb = new StringBuilder();
int n = s.length();
for(int i =0;i<n;i++){
if(s.charAt(i)==' '){
sb.append("%20");
}else{
sb.append(s.charAt(i));
}
}
return sb.toString();
}
}
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public int[] reversePrint(ListNode head) {
if(head==null){
return new int[0];
}
int n =0;
Stack<Integer> stack = new Stack<Integer>();
ListNode node = head;
while(node!=null){
n++;
stack.push(node.val);
node = node.next;
}
int[] ans = new int[n];
int i =0;
while(!stack.isEmpty()){
ans[i] = stack.pop();
i++;
}
return ans;
}
}
class Solution {
ArrayList<Integer> tmp = new ArrayList<Integer>();
public int[] reversePrint(ListNode head) {
recur(head);
int[] res = new int[tmp.size()];
for(int i = 0; i < res.length; i++)
res[i] = tmp.get(i);
return res;
}
void recur(ListNode head) {
if(head == null) return;
recur(head.next);
tmp.add(head.val);
}
}
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
if(preorder.length==0||inorder.length==0){
return null;
}
HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
for(int i =0;i< inorder.length;i++){
map.put(inorder[i],i);
}
return helper(preorder,0,preorder.length-1,inorder,0,inorder.length-1,map);
}
public TreeNode helper(int[] preorder,int start,int end,int[] inorder,int start1,int end1,HashMap
