现对这66道题目进行了粗略的划分，整理如下：

数组(11道)：

剑指Offer_编程题01：二维数组中的查找

剑指Offer_编程题06：旋转数组的最小数字(指针)

剑指Offer_编程题13：调整数组顺序使奇数位于偶数前面

剑指Offer_编程题28：数组中出现次数超过一半的数字

剑指Offer_编程题30：连续子数组的最大和

剑指Offer_编程题32：把数组排成最小的数

剑指Offer_编程题35：数组中的逆序对(归并排序)

剑指Offer_编程题37：数字在排序数组中出现的次数

剑指Offer_编程题40：数组中只出现一次的数字

剑指Offer_编程题50：数组中重复的数字

剑指Offer_编程题51：构建乘积数组

链表(8道)：

必须掌握题型：单链表反转；链表中环的检测；两个有序的链表合并；删除链表倒数第n个结点；求链表的中间结点

剑指Offer_编程题03：从尾到头打印链表

剑指Offer_编程题14：链表中倒数第k个结点

剑指Offer_编程题15：反转链表

剑指Offer_编程题16：合并两个排序的链表

剑指Offer_编程题25：复杂链表的复制

剑指Offer_编程题36：两个链表的第一个公共结点

剑指Offer_编程题55：链表中环的入口结点

剑指Offer_编程题56：删除链表中重复的结点

栈(3道)：

剑指Offer_编程题05：用两个栈实现队列

剑指Offer_编程题20：包含min函数的栈

剑指Offer_编程题21：栈的压入、弹出序列

字符串(8道)：

剑指Offer_编程题02：替换空格

剑指Offer_编程题27：字符串的排列

剑指Offer_编程题34：第一个只出现一次的字符

剑指Offer_编程题34：左旋转字符串

剑指Offer_编程题44：翻转单词顺序列

剑指Offer_编程题49：把字符串转换成整数

剑指Offer_编程题52：正则表达式匹配

剑指Offer_编程题53：表示数值的字符串

其他(15道)：

剑指Offer_编程题11：二进制中1的个数

剑指Offer_编程题12：数值的整数次方

剑指Offer_编程题19：顺时针打印矩阵

剑指Offer_编程题29：最小的K个数

剑指Offer_编程题59：整数中1出现的次数（从1到n整数中1出现的次数）

剑指Offer_编程题33：丑数

剑指Offer_编程题41：和为S的连续正数序列

剑指Offer_编程题42：和为s的两个数字

剑指Offer_编程题30：扑克牌顺子

剑指Offer_编程题46：孩子们的游戏(圆圈中最后剩下的数)_约瑟夫环

剑指Offer_编程题48：不用加减乘除的加法

剑指Offer_编程题54：字符流中第一个不重复的字符

剑指Offer_编程题63：数据流中的中位数(堆)

剑指Offer_编程题64：滑动窗口的最大值(双向队列)

递归：

剑指Offer_编程题35：数组中的逆序对

剑指Offer_编程题16：合并两个排序的链表

剑指Offer_编程题27：字符串的排列

剑指Offer_编程题52：正则表达式匹配

剑指Offer_编程题07：斐波那契数列

剑指Offer_编程题08：跳台阶

剑指Offer_编程题09：变态跳台阶

剑指Offer_编程题10：矩形覆盖

回溯法(2道)：

剑指Offer（六十五）：矩阵中的路径

剑指Offer（六十六）：机器人的运动范围

二叉树(12道)：

剑指Offer_编程题04：重建二叉树

剑指Offer_编程题17：树的子结构

剑指Offer_编程题18：二叉树的镜像

剑指Offer_编程题22：从上往下打印二叉树

剑指Offer_编程题24：二叉树中和为某一值的路径

剑指Offer_编程题38：二叉树的深度

剑指Offer_编程题39：平衡二叉树

剑指Offer_编程题57：二叉树的下一个结点

剑指Offer_编程题58：对称的二叉树

剑指Offer_编程题59：按之字顺序打印二叉树

剑指Offer_编程题60：把二叉树打印成多行

剑指Offer_编程题61：序列化二叉树

二叉搜索树(3道)：

剑指Offer_编程题23：二叉搜索树的后序遍历序列

剑指Offer_编程题26：二叉搜索树与双向链表

剑指Offer_编程题62：二叉搜索树的第k个结点

     之前立帖挖坑搞定leetcode, 现在再挖一坑, 尝试剑指offer
两者都是针对找工作的应用习题, 特别注重编程算法之类, 但大都考察基础, 重中之重.
主要阵地:
http://ac.jobdu.com/hhtproblems.php
已开栏 sword_offer


应该时常运用.

转载本文章请标明作者和出处

本文出自《Darwin的程序空间》

本文题目和部分解题思路来源自《剑指offer》第二版



开始行动，你已经成功一半了，献给正在奋斗的我们

题目
给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中 B 中的元素 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法


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



提示
所有元素乘积之和不会溢出 32 位整数
a.length <= 100000



解题分析
题目要求不能使用除法，所以你求出所有的数的乘积，然后再除以每个数构结果集的第一想法就流产了；
这道题就是要求结果数组上的每一个数，都是原数组除了这个位置的数的乘积；


以第二个节点为例，其实就是这个当前节点元素所有在原数组左边的元素乘积乘以原数组在这个索引右边的元素乘积；
那么我们的做法就是，先把每一个元素的左边的乘积和右边的乘积都算出来，然后新的数组的元素就等于这个元素左边的乘积加上右边的乘积；
如上图中的示例，所有左边的乘积为：



这个数组上所有的位置上的数都是原数组此位置上的书的左边的所有元素的乘积
如上图中的示例，所有右边的乘积为：



这个数组上所有的位置上的数都是原数组此位置上的书的右边的所有元素的乘积，
最后所求数组即使这两个数据的相同位置索引的乘积构成的新数组；


然后我们使用累乘，少定义两个数组即可完成最优算法；
代码
ps：这里笔者使用的jdk为1.8、Python3.7版本

java实现

class Solution {
    public int[] constructArr(int[] a) {
        if (Objects.isNull(a) || a.length == 0) {
            return new int[]{};
        }
        int[] res = new int[a.length];
        int left = 1;
        for (int i = 0; i < res.length; i++) {
            res[i] =left;
            left *= a[i];
        }
        int right = 1;
        for (int i = res.length - 1; i >= 0; i--) {
            res[i] *= right;
            right *= a[i];
        }
        return res;
    }
}


Python实现

class Solution:
    def constructArr(self, a: List[int]) -> List[int]:
        if a is None or len(a) == 0:
            return []
        res = [None] * len(a)
        left = 1
        for i in range(len(a)):
            res[i] = left
            left *= a[i]
        right = 1
        for i in reversed(range(len(a))):
            res[i] *= right
            right *= a[i]
        return res






喜欢的朋友可以加我的个人微信，我们一起进步

剑指Offer——丑数


前言

    参照《剑指Offer》，通过洞悉其思想并消化吸收，改为java实现，供自己以后巩固。


 

package cn.edu.ujn.offersword;
 
import java.util.Scanner;
 
public class C5_34_UglyNumber {
 
/**
 * @date 2016-09-16
 * @number 01
 * @author SHQ
 * 丑数
 * 题目描述
 *把只包含因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含因子7。习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
 * 思路
 *空间换时间
 *根据丑数的定义，丑数应该是另一个丑数乘以2，3，或5所得(1除外)。故非丑数不在计算范围之内。额外创建一个数组，用于存放已确定的丑数。
 *通过设置3个变量，用于标记第一个大于最大丑数的位置，并将3个变量中的最小丑数作为下一个丑数。 同时避免重复计算。
 * 空间复杂度O(n);
 */
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while(in.hasNextInt()){
int index = in.nextInt();
System.out.println(GetUglyNumber_Solution2(index));
}
}
// 超时
    private static int GetUglyNumber_Solution(int index) {
    	if(index <= 0){
    	return 0;
    	}
    	int cnt = 0;
    	int number = 1;
    	while(cnt < index){
    	if(isUgly(number)){
    	cnt++;
    	}
    	number++;
    	}
    	return number;
    }
    
    private static boolean isUgly(int num){
    	while(num % 2 == 0)
    	num /= 2;
    	while(num % 3 == 0)
    	num /= 3;
    	while(num % 5 == 0)
    	num /= 5;
    	return num == 1 ? true : false;
    
    }
    
    private static int GetUglyNumber_Solution2(int index) {
    	if(index <= 0){
    	return 0;
    	}
    	int [] arr = new int [index];
    	arr[0] = 1;
    	int index2 = 0, index3 = 0, index5 = 0, nextIndex = 1;
    	while(nextIndex < index){
    	System.out.print(arr[nextIndex-1] + " ");
    	int min = min(arr[index2]*2, arr[index3]*3, arr[index5]*5);
    	arr[nextIndex] = min;
    	while(arr[index2] * 2 <= arr[nextIndex])
    	index2++;
    	while(arr[index3] * 3 <= arr[nextIndex])
    	index3++;
    	while(arr[index5] * 5 <= arr[nextIndex])
    	index5++;
    	nextIndex++;
    	}
    	return arr[nextIndex-1];
    }
    
    private static int min(int a, int b, int c){
    	int min = (a > b) ? b : a;    
    	return min > c ? c : min;
    }
}

美文美图