剑指 Offer 03. 数组中重复的数字

题目【难度简单】

找出数组中重复的数字。
在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例 1：

  1. 输入：
  2. [2, 3, 1, 0, 2, 5, 3]
  3. 输出：2 或 3

限制：

  1. 2 <= n <= 100000

思路

方法一：利用hashset，这个比较简单，直接看代码即可。
原地交换：
主要思想上是首先循环，然后判断该下标位置上的数字是否与下标相等，不想等的话，把这个数字放到它该在的位置去（35 就放到a[35]）,然后让a[35]的数字交换过来，如果这个数字交换过来于下标想等，就存放下来，不相等继续交换，如果发现这个地方已经有等于下标的数了，那么就找到了重复数字。

代码

  1. class Solution {
  2.     public int findRepeatNumber(int[] nums) {
  3.         HashSet<Integer> set = new HashSet<Integer>();
  4.         for(int i: nums){
  5.             if (set.contains(i)){
  6.                 return i;
  7.             }
  8.             set.add(i);
  9.         }
  10.         return -1;    
  11.     }
  12. }
  1. class Solution {
  2.     public int findRepeatNumber(int[] n) {
  3.         int t= 0;
  4.         for(int i=0;i<n.length;i++){
  5.             if(n[i]!=i){
  6.                 t = n[n[i]];
  7.                 n[n[i]] = n[i];
  8.                 if (n[i]==t){
  9.                     return t;
  10.                 }else{
  11.                     n[i] = t;
  12.                 }
  13.             }else{
  14.                 continue;
  15.             }
  16.         }
  17.         return -1;
  18.     }   
  19. }

剑指 Offer 04. 二维数组中的查找

难度中等371收藏分享切换为英文接收动态反馈
在一个 n m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
*示例:
现有矩阵 matrix 如下：

  1. [
  2.   [1,   4,  7, 11, 15],
  3.   [2,   5,  8, 12, 19],
  4.   [3,   6,  9, 16, 22],
  5.   [10, 13, 14, 17, 24],
  6.   [18, 21, 23, 26, 30]
  7. ]

给定 target = 5，返回 true。
给定 target = 20，返回 false。
限制：

  1. 0 <= n <= 1000
  2. 0 <= m <= 1000

思路

解题

  1. class Solution {
  2.     public boolean findNumberIn2DArray(int[][] matrix, int target) {
  3.         if  (matrix.length ==0){
  4.             return false;
  5.         }else if (matrix[0].length==0){
  6.             return false;
  7.         }
  9.         int row = matrix.length;
  10.         int col = matrix[0].length;
  11.         int j=0,i=row-1;
  12.         while (i>=0 && j<col){
  13.             if (target<matrix[i][j]){       //  目标太小 往上边寻找
  14.                 i--;
  15.             }else if(target>matrix[i][j]){  //  目标太大 往右边寻找
  16.                 j++;
  17.             }else{
  18.                 return true;
  19.             }
  21.         }
  22.         return false;
  23.     }
  24. }

剑指 Offer 06. 从尾到头打印链表

难度简单164收藏分享切换为英文接收动态反馈
输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
示例 1：

  1. 输入：head = [1,3,2]
  2. 输出：[2,3,1]

解题

方法一利用栈

  1. /**
  2.  * Definition for singly-linked list.
  3.  * public class ListNode {
  4.  *     int val;
  5.  *     ListNode next;
  6.  *     ListNode(int x) { val = x; }
  7.  * }
  8.  */
  9. class Solution {
  10.     public int[] reversePrint(ListNode head) {
  11.         Stack<Integer> st = new Stack<Integer>();
  12.         // 遍历 入栈
  13.         // 链表不知道长度，用while循环
  14.         while(head != null){
  15.             int temp = head.val;
  16.             st.push(temp);
  17.             head = head.next;
  18.         }
  19.         int len = st.size();
  20.         int[] arr = new int[len];
  21.         for(int i=0;i<len;i++){
  22.             arr[i] = st.pop();
  23.         }
  24.     return arr;
  25.     }
  26. }

剑指 Offer 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]。不能使用除法。
示例:

  1. 输入: [1,2,3,4,5]
  2. 输出: [120,60,40,30,24]

提示：

  • 所有元素乘积之和不会溢出 32 位整数

  • a.length <= 100000

    思路

    定义一个新数组，第一次遍历存放每个数左边的累乘积（只需将最新的左边一个数数组上一次的累乘积），然后从后面往前第二次遍历，存放每个数右边的累乘积左边累乘积对应相乘。

    代码

    ``` class Solution{ public int[] constructArr(int[] a){

    1.   //测试用例 有个[] 要注意
    2.   if(a.length==0){
    3.       return a;
    4.   }
    6.   int[] b = new int[a.length];
    7.   b[0] = 1;
    8.   int tmp = 1;
    9.   for (int i = 1; i < b.length; i++) {
    10.       b[i]  = a[i-1] * b[i-1];
    11.   }
    13.   for (int k=b.length-2; k>=0; k--){
    14.       tmp = tmp*a[k+1];
    15.       b[k] = b[k]*tmp;
    16.   }
    17.   return b;

    } }

```

空间复杂度 O(1) ) 时间复杂度(n)