翻转单词顺序 java-打乱单词顺序app

剑指Offer 1-5 1.赋值运算函数 2.实现Singleton模式

设计一个类，我们只能生成该类的一个实例。

懒汉式

线程安全

双重校验锁*

 if (singleton == null) {
  synchronized (Singleton.class) {
  if (singleton == null) {  
      singleton = new Singleton();  
  ...

静态内部类*

    private static class SingletonHolder {  
      private static final Singleton INSTANCE = 
                                                new Singleton();  
      }  
      public static final Singleton getInstance() {  
          return SingletonHolder.INSTANCE;  
      ...

枚举*

public enum Singleton {  
  INSTANCE;  
  public void whateverMethod() {  
  ...

3.二维数组中的查找

在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

4.替换字符串中的空格

请实现一个函数，把字符串中的每个空格替换成"%20"。例如输入“We are happy.”，则输出“We%20are%20happy.”。

5.从尾到头打印链表

输入一个链表的头结点，从尾到头反过来打印出每个结点的值。

递归

6-10 6.重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

7.用两个栈实现队列

用两个栈实现一个队列。分别完成在队列尾部插入结点和在队列头部删除结点的功能。

8.旋转数组的最小数字

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。

9.斐波那契数列

一只青蛙一次可以跳上1 级台阶，也可以跳上2 级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

用 2×1的小矩形横着或者竖着去覆盖更大的矩形。请问用8个2×1的小矩形无重叠地覆盖一个2×8的大矩形，总共有多少种方法？

10.二进制中1的个数

请实现一个函数，输入一个整数翻转单词顺序 java，输出该数二进制表示中 1 的个数。

考虑负数

11-15 11.数值的整数次方

实现函数 double Power（double base, int exponent），求 base的exponent次方。

12.打印1到最大的n位数*

输入数字n，按顺序打印出从1最大的n位十进制数。比如输入3，则打印出1、2、3一直到最大的3位数即999。

13.在O（1）时间删除链表结点

给定单向链表的头指针和一个结点指针，定义一个函数在 O（1）时间删除该结点。

14.调整数组顺序使奇数位于偶数前面

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。

15.链表中倒数第k个结点

输入一个链表，输出该链表中倒数第 k 个结点。

16-20 16.反转链表

定义一个函数翻转单词顺序 java，输入一个链表的头结点，反转该链表并输出反转后链表的头结点。

17.合并两个排序的链表

输入两个递增排序的链表，合并这两个链表并使新链表中的结点仍然是按照递增排序的。

18.树的子结构

输入两棵二叉树A和B，判断B是不是A的子结构。

19.二叉树的镜像

完成一个函数，输入一个二叉树，该函数输出它的镜像。

20.顺时针打印矩阵

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。

21-25 21.包含min函数的栈

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的min函数。

22.栈的压入、弹出序列

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。

23.从上往下打印二叉树

从上往下打印出二叉树的每个结点，同一层的结点按照从左到右的顺序打印。

24.二叉搜索树的后序遍历序列

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。

25.二叉树中和为某一值的路径*

输入一棵二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。

26-30* 26.复杂链表的复制

在复杂链表中，每个结点除了有一个m_pNext指针指向下一个结点外，还有一个m_pSibling 指向链表中的任意结点或者NULL。

27.二叉搜索树与双向链表

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

28.字符串的排列

输入一个字符串，打印出该字符串中字符的所有排列。

29.数组中出现次数超过一半的数字

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

30.最小的k个数

输入n个整数，找出其中最小的k个数。

31-35 31.连续子数组的最大和

输入一个整型数组，数组里有正数也有负数。数组中一个或连续的多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O（n）。

32.从1到n整数中1出现的次数*

输入一个整数n，求从1到n这n个整数的十进制表示中1出现的次数。

解法

33.把数组排成最小的数

输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。

 Arrays.sort(strs, new Comparator<String>() {
      @Override
      public int compare(String o1, String o2) {
          String s1 = o1 + o2;
          String s2 = o2 + o1;
          return s1.compareTo(s2);
  ...

34.丑数

我们把只包含因子2、3和5的数称作丑数（Ugly Number）。求按从小到大的顺序的第1500个丑数。

35.第一个只出现一次的字符

在字符串中找出第一个只出现一次的字符。如输入"abaccdeff"，则输出’b’。

36-40 36.数组中的逆序对*

在数组中的两个数字如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

在比较时加入全局变量count

data[start]>=data[index]

count = mid+1-start

37.两个链表的第一个公共结点

输入两个链表，找出它们的第一个公共结点。

38.数字在排序数组中出现的次数

统计一个数字在排序数组中出现的次数。例如输入排序数组{1,2, 3,3,3,3,4,5}和数字3，由于3在这个数组中出现了4次，因此输出4。

39.二叉树的深度

输入一棵二叉树的根结点，求该树的深度。

     if (root == null) return true;
     boolean condition = Math.abs(getDepth(root.left) - getDepth(root.right)) <= 1;
     return condition && isBalanced(root.left) && isBalanced(root.right);

40.数组中只出现一次的数字

一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是 O（n），空间复杂度是O（1）。

40-45 41.和为s的两个数字VS和为s的连续正数序列

输入一个正数s，打印出所有和为s的连续正数序列（至少含有两个数）。例如输入15，由于1+2+3+4+5=4+5+6=7+8=15，所以结果打印出3个连续序列1～5、4～6和7～8。

42.翻转单词顺序 VS左旋转字符串

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如输入字符串"abcdefg"和数字2，该函数将返回左旋转2位得到的结果"cdefgab"。

43.n个骰子的点数*

把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。

44.扑克牌的顺子

从扑克牌中随机抽 5张牌，判断是不是一个顺子，即这 5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王可以看成任意数字。

45.圆圈中最后剩下的数字*

0,1,…,n-1这n个数字排成一个圆圈，从数字0开始每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。

循环链表模拟

46-50 46.求1+2+…+n

求1+2+…+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。

private static int sum(int n) {
      int sum = n;
      boolean result = (n > 0) && ((sum += sum(n - 1)) > 0);
      return sum;
  ...

47.不用加减乘除做加法

写一个函数，求两个整数之和，要求在函数体内不得使用+、-、×、÷四则运算符号。

private static int add(int a, int b) {
      while (b != 0) {
          int temp = a ^ b;
          b = (a & b) << 1;
          a = temp;
      }
      return a;
  ...

48.不能被继承的类 49.把字符串转换成整数 50.求两个结点的最低公共祖先