logo头像
Snippet 博客主题

剑指Offer解题思路

:说明此题有疑问
:代表此题解法与参考文献不同

3 数组中重复的数字

问:在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的,但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如,如果输入长度为7的数组{2,3,1,0,2,5,3},那么对应的输出是第一个重复的数字2。

答:注意范围是0~n-1,所以利用下标。for循环遍历下标,while将遍历到的这个值swap到该放的位置上,一直等i的值是匹配(while条件)的才跳出来while;在while中,每次要if先判断下目标移动位置上的值是否已经存在,存在那就是找到重复的。方法默认的false,假设有一个重复了,导致0没有了,意味着遍历完所有的了都没有找到,那肯定的法拉瑟了。
注:numbers == null || length <= 0 是首先验证条件,直接返回false

4 二维数组的查找

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

答:从右上角(或者左下角)开始while遍历,判断值的大小来i++,或者j–;

5 替换空格

问:将一个字符串中的空格替换成 “%20”

答:分两步骤: 找空格,加在尾部;指针移动替换
1、因为一个空格要替换成三个字符(%20),所以当遍历到一个空格时,需要在尾部填充两个任意字符。
2、令 P1 指向字符串原来的末尾位置,P2 指向字符串现在的末尾位置。P1 和 P2 从后向前遍历。
3、当 P1 遍历到一个空格时,就需要令 P2 指向的位置依次填充 02%(注意是逆序的),否则就填充上 P1 指向字符的值。
4、只有当P2 > P1 && P1 >= 0 才进行上述步骤。
注:
在步骤1中,遍历的条件只能是 i<= p1; 不能用i < str.length() 因为str长度在变!
str.charAt(i) == ‘ ‘ //charAt(i) 和 str.setCharAt(i,’x’) 都是单引号;String要获取某下标的元素得用charAt,区别于数组的a[i]。
str.append(“ “) //str.append(String s) 双引号
str.toString() //将StringBuffer 转换成String

6 从尾到头打印链表

问:输入一个链表,按链表从尾到头的顺序返回一个ArrayList
答:

  • 堆栈法
    栈具有后进先出的特点,在遍历链表时将值按顺序放入栈中,最后出栈的顺序即为逆序。
    注:import java.util.Stack; //导包,自己手动加的
    listNode.val //获取listNode当前的值
    listNode = listNode.next; //下一个节点
    listNode != null //是否遍历完了

  • 递归法

7 重建二叉树(难)

问:根据二叉树的前序遍历和中序遍历的结果,重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
答:前序遍历序列的第一个元素 1 就是二叉树的根节点,中序遍历序列的根节点 1 把这个序列分成两半部分,分别是[4,7,2]和[5,3,8,6],左半分部是根节点的左子树,右半分布是根节点的右子树。
基于这个特点,我们可以采用递归的方法来做,其大致逻辑如下。
1、通过前序序列第一个元素确定根节点(例如 1)。
2、通过根节点把中序序列分成两个序列,一个是左子树序列([4,7,2)],一个是右子树序列([5,3,8,6)]。
3、通过左右子树的中序序列可以求出前序遍历的左右子树序列(左:[2,4,7],右:[3,5,8,6])。
4、左右子树的前序序列第一个元素分别是根节点的左右儿子。

8 二叉树的下一个结点(空,树)

9 用两个栈实现队列

问:用两个栈来实现一个队列,完成队列的 Push 和 Pop 操作。
答:
push: 只push就行
pop: 总是返回2的pop。如果2为空,就将1的全部pop到1里面。先判断2是否为空,抛异常。最后return 是stack2.pop();
注意:2为空时,注意pop异常 public int pop() throws Exception{ throw new Exception(“queue is empty”);} //前面throw有s,后面没有s.

10.1 斐波那契数列

问:现在要求输入一个整数n,请你输出斐波那契数列的第n项(从0开始,第0项为0)。 n<=39
答:因为n限制了范围,用最基础的大小为40的数组来保存,不用递归了。

10.2 矩形覆盖

问:我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形,总共有多少种方法?

答:如果使用2x1的矩形来覆盖2x8的矩形的话,设有f(n)中覆盖放法。首先,第一个2x1的矩形有两种放法,第一种,竖着放,剩下的部分有f(7)种,第二种横着放,剩下的部分有f(6)种。则一共有f(8) = f(7) + f(6)。很明显这又是著名的Fibonacci数列。但是不要用递归,因为时间复杂度太大;用循环好处是,数列中间项保存起来,一直到求到了目标n。
注:pre2 = pre1; pre1 = result; 注意先后顺序,以免pre1被覆盖了。

10.3 跳台阶

问:一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。
答:跳 n 阶台阶,可以先跳 1 阶台阶,再跳 n-1 阶台阶;或者先跳 2 阶台阶,再跳 n-2 阶台阶。又是斐波那契数列,算法同上一模一样,也是避免用递归。

10.4 变态跳台阶

问:一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
答:f(n)=2f(n-1) 等比数列 f(n) = 2的(n-1)次方

11 旋转数组的最小数字

问:把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。
NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。
答:(1)array[mid] > array[high];
出现这种情况array类似[3, 4, 5, 0, 1, 2],此时最小数字移动在mid的右边。low = mid + 1;
(2)array[mid] == array[high]
出现这种情况array类似[0, 1, 1, 1, 1,]或者[1, 1, 1, 0, 1],此时最小数字不好判断在mid左边还是右边,这个时候只能一个个的试
high = high - 1;
(3)array[mid] < array[high]:
出现这种情况的array类似[2,2,3,4,5,6,6],此时最小数字一定就是array[mid]或者在mid的左边。因为右边必然都是递增的。high = mid

12 矩阵中的路径(空。回溯法)

13 机器人的运动范围(空。回溯法)

14 剪绳子

问:给定一个正整数 n,将其拆分为至少两个正整数的和,并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
答:(贪心法)尽可能多剪长度为 3 的绳子,并且不允许有长度为 1 的绳子出现。如果出现了,就从已经切好长度为 3 的绳子中拿出一段与长度为 1 的绳子重新组合,把它们切成两段长度为 2 的绳子。
证明:当 n >= 5 时,3(n - 3) - n = 2n - 9 > 0,且 2(n - 2) - n = n - 4 > 0。因此在 n >= 5 的情况下,将绳子剪成一段为 2 或者 3,得到的乘积会更大。又因为 3(n - 3) - 2(n - 2) = n - 5 >= 0,所以剪成一段长度为 3 比长度为 2 得到的乘积更大。
所以先判断 n 的值 n<2 reutrn 0; n==2 reutrn 1; n==3 reutrn 2; 其余的值按照所提的贪心算法(包括4)

15 二进制中 1 的个数

位运算有5种,与(&),或(|),异或(^),左移(<<最左边的n位丢弃,后面补0),右移(>>稍微复杂,需要判断第一位。如果,无符号数值,用0填补左边;如果有符号数值,用第一位的数填补。)
问:输入一个整数,输出该数二进制表示中 1 的个数。
答:1、把一个整数减去1,会使得最右边的1变成0,并且后面的0全部变成1。再和原整数做与运算,就会使得原整数的最右边的1变为0,计数器+1
2、再将得到的这个数重复上述操作,只要这个数不为0
3、返回计数器的数

16 数值的整数次方

问:给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。(实现pow方法)
答:这个题目不难,关键在于exponent的边界,0(return);1(return);和负数都要分析,用一个isNegative = true,来表示负数,并且将exponent = -exponent;,最后return isNegative?/1pow:pow

因为 (x)^(n/2) 可以通过递归求解,并且每次递归 n 都减小一半,因此整个算法的时间复杂度为 O(logN)。

17 打印从 1 到最大的 n 位数(空。回溯法)

18.1 删除链表的节点

问:给定单向链表的头指针和一个要删除的节点的值,定义一个函数删除该节点。返回删除后的链表的头节点。(链接题目略有改动)
答:首先进行是否为null的判断。
判断这个节点是不是最后一个节点。也就是tobeDelete.next == null。
如果该节点不是尾节点,比如 h->i->j->?,如果想删除i。按照传统思路,从头节点开始遍历,找到指向节点i的节点(也就是h),将h指向j即可,但是需要顺序查找,复杂度为O(n)。换个思路,既然j不为null,也就是j后面还指向了别的,那可以删除j,是等效删除了i。
具体做法,将j节点的值赋给i节点上,并且让i节点指向j的下一个节点。这样就不用遍历来找指向i的节点了。复杂度是O(1)。
如果该节点是尾节点,要分两种情况,1、链表只有一个节点,也就是 head == tobeDelete,删除后就什么都没了,head=null; 2、一直while找到尾部,条件为cur.next != tobeDelete

18.2 删除链表中重复的结点

问:在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留,返回链表头指针。 例如,链表1->2->3->3->4->4->5 处理后为 1->2->5
:1、非null判断。如果 pHead == null || pHead.next == null,return
2、如果 pHead.val == next.val,说明重复,但可能多个连续重复,所以要while,一直找到不重复的。 while(pHead.val == next.val),空指针没有值,会报错,所以while条件要加上next != null
3、如果不满足2,那就简单了,顺延head,检查下一个即可。

19 正则表达式匹配(空)

问:请实现一个函数用来匹配包括’.’和’‘的正则表达式。模式中的字符’.’表示任意一个字符,而’‘表示它前面的字符可以出现任意次(包含0次)。 在本题中,匹配是指字符串的所有字符匹配整个模式。例如,字符串”aaa”与模式”a.a”和”abaca”匹配,但是与”aa.a”和”ab*a”均不匹配
答:

20 表示数值的字符串

问:请实现一个函数用来判断字符串是否表示数值(包括整数和小数)。例如,字符串”+100”,”5e2”,”-123”,”3.1416”和”-1E-16”都表示数值。 但是”12e”,”1a3.14”,”1.2.3”,”+-5”和”12e+4.3”都不是。
答:
[] : 字符集合
() : 分组
? : 重复 0 ~ 1 次
+ : 重复 1 ~ n 次
* : 重复 0 ~ n 次
. : 任意字符
\\. : 转义后的 .
\\d : 数字

1、首先进行非null判断
2、(A)(B)(C) 三部分组成
A:整数。整体有没有都行。正负号:有没有都行。数字部分:有没有都行(.2是合法的),所以是0~n。
B:小数。整体有没有都行。点. 数字部分:不能没有数字(3. 是不合法的)1~n
C:指数。整体有没有都行。Ee:必须有。正负号:有没有都行。数字部分:1~n
注:String str = new String(charArray); //将一个char类型的数组,转换成字符串
str.matches(“ “); //参数为正则表达式,是否匹配,返回值为布尔型

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

问:输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位置不变。
答:创建一个新数组,时间复杂度 O(N),空间复杂度 O(N)。
1、找出奇数的个数 oddCount
2、int[] copy = array.clone(); int i = 0; int j = oddCount; 遍历copy里的元素分类奇数和偶数,覆盖array里的元素,i++或者j++
注意:.clone() 方法:创建并返回此对象的副本。

22 链表中倒数第 K 个结点

问:输入一个链表,输出该链表中倒数第k个结点。
答:双指针
1、head非空判断
2、设链表的长度为 N。设置两个指针 P1 和 P2,先让 P1 移动 K 个节点
3、此时让 P1 和 P2 同时移动,可以知道当 P1 移动到链表结尾时,P2 移动到第 倒数第K个节点处。
注意:还应该进行k的值不大于链表的长度,但由于无法像数组那样获取链表的长度,所以在第二步骤中,while(p1!=null && k>0) ,等while结束后,判断k>0就返回false。这样一来第一步可以省掉了

23 链表中环的入口结点

问:一个链表中包含环,请找出该链表的环的入口结点。要求不能使用额外的空间。
:双指针,快慢指针。思路更简洁,代码同CyC。
两个指针fast和slow,fast以slow两倍速度前进,
如果没有环,那么fast和slow不会相遇此时返回null;
如果有环,那fast和slow肯定会再次相遇.相遇的时候,fast刚好比slow多走了一圈环的长度。
环
用图来描述下,当fast与slow相遇时,fast走过的距离为a + b + c + b,而slow走过的距离为
a + b,因为fast是slow速度的两倍,则有a+b+c+b = 2*(a+b),得出a=c;
此时第三个指针p从x处,以和slow指针相同的速度前进,当它两相遇时,即为环的起点Y处!这一步就没有快指针的事情了,所以可以让fast来行使p的作用,注意每次移动一格。

1、非null判断 pHead == null || pHead.next == null 。
2、do{}while(); //用这个结构的循环,因为第一步的时候 fast = slow = pHead; 如果用while,就不通过了。
3、相遇后,两个慢指针,while

24 反转链表

与第六题类似,从尾到头打印链表
问:输入一个链表,反转链表后,输出新链表的表头。
答:

  • 堆栈法

25 合并两个排序的链表

问:输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。

1、非null判断
2、新建一个空链表 ListNode listAll = null; 等效于 ListNode newlist = new ListNode(-1);
2、合并过程中,首先比较两个链表的首节点哪个小,较小的节点作为新链表的首节点
3、这一步是递归过程。新链表的下一个节点就一直是比较 第二步较小节点的下一个 与 第二步较大节点。再次进行上面逻辑的比较。

26 树的子结构

问:输入两棵二叉树A,B,判断B是不是A的子结构。(ps:我们约定空树不是任意一个树的子结构)
答:

  • 递归法
    1、写两个函数,主函数HasSubtree, 用到递归。return isSubtreeWithRoot(root1, root2) || HasSubtree(root1.left, root2) || HasSubtree(root1.right, root2);
    2、功能函数 isSubtreeWithRoot ,判断下以这个为根节点,是不是相同的。第一步如果root2为空,return true;第二步如果root1 为空(第一步没进入if,隐含root2不为空),return false;第三步,判断下根节点值是否相等,不相等,也就不用判断下面的子节点了,直接return false。最后用到递归判断下左右子节点的情况,子节点又可以看作新的root。return isSubtreeWithRoot(root1.left, root2.left) && isSubtreeWithRoot(root1.right, root2.right);

27 二叉树的镜像

问:操作给定的二叉树,将其变换为源二叉树的镜像。
答:1、定义一个功能函数,输入一个根节点,将他的左右叶子换换。 swap()
2、主函数Mirror 用递归。一个树如果为空,直接return; 否则执行 swap(root);swap(root.left);swap(root.right);

28 对称的二叉树

问:请实现一个函数,用来判断一颗二叉树是不是对称的。注意,如果一个二叉树同此二叉树的镜像是同样的,定义其为对称的。我们规定一个空二叉树是对称的。
答:
1、写功能函数,给两个节点root1,root2,判断是否对称。如果两个节点同时都为空,返回true;如果两个节点有一个为空,返回true。接下来的情况就是两个节点都不为空,那先判断下节点的值是否相等,不相等直接return false。最后递归调用本函数判断 root1左叶子与 root2右叶子 并且 root1右叶子与root2左叶子。
2、写主函数,调用功能函数就行。
注:节点的值为 root.val

29 顺时针打印矩阵

问:输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字,例如,如果输入如下4 X 4矩阵: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.
  注意矩阵,不一定是正方形,所以每一次的逼近后,都要判断
:不断地收缩矩阵的边界
定义四个变量代表范围,up、down、left、right
1、向右走存入整行的值,当存入后,该行再也不会被遍历,代表上边界的 up 加一,同时判断是否和代表下边界的 down 交错
2、向下走存入整列的值,当存入后,该列再也不会被遍历,代表右边界的 right 减一,同时判断是否和代表左边界的 left 交错
3、向左走存入整行的值,当存入后,该行再也不会被遍历,代表下边界的 down 减一,同时判断是否和代表上边界的 up 交错
4、向上走存入整列的值,当存入后,该列再也不会被遍历,代表左边界的 left 加一,同时判断是否和代表右边界的 right 交错

30 包含 min 函数的栈

问:定义栈的数据结构,请在该类型中实现一个能够得到栈中所含最小元素的min函数(时间复杂度应为O(1))。
注意:保证测试中不会当栈为空的时候,对栈调用pop()或者min()或者top()方法。

答:题目只让定义min()
可以利用Stack的已有方法
boolean empty(); // 测试此堆栈是否为空。
E peek(); // 查看此堆栈顶部的对象,而不从堆栈中删除它。
E pop(); // 删除此堆栈顶部的对象,并将该对象作为此函数的值返回。
E push(E item); // 将对象推送到此堆栈的顶部。

定义两个空栈dataStack 和 minStack(辅助),在push方法执行的时候,dataStack照单全收;minStack每次也会收一个,但是注意如果小就收小的,否则就重复一个minStack顶上的值,这样的目的是如果执行POP,可以帮下面小的抗一下,又可以保证这个确实是dataStack中的最小值。妙哉!
public void push(int node) {
dataStack.push(node);
minStack.push(minStack.isEmpty() ? node : Math.min(minStack.peek(), node));
}

31 栈的压入、弹出序列(空。没读懂题目)

32.1 从上往下打印二叉树

问:从上往下打印出二叉树的每个节点,同层节点从左至右打印。
答:用队列 LinkedList实现了List 和 Deque 接口,具有先进先出的特性。将树的节点作为元素放入队列中。用ArrayList 来放遍历打印的结果。
LinkedList 方法
boolean offer(E e) // 将指定的元素添加为此列表的尾部(最后一个元素)。
E poll() // 检索并删除此列表的头(第一个元素)。

1、非null判断
2、加入root节点到队列中
3、while(!queue.isEmpty){
int count = queue.size();
while(count–>0){
取出来队列的一个节点,将值放入ArrayList
分别判断这个节点的左右叶子是否为空,如果不为空,加入队列
}
}
注意:导入import java.util.LinkedList;

32.2 把二叉树打印成多行

问:从上到下按层打印二叉树,同一层结点从左至右输出。每一层输出一行。
答:和上题不同之处在于,ArrayList<ArrayList> ret = new ArrayList<>();
并在内部那个while结束之后,将ArrayList list 放入 ret。

32.3 按之字形顺序打印二叉树

问:请实现一个函数按照之字形打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右至左的顺序打印,第三行按照从左到右的顺序打印,其他行以此类推
答:和上一个题的不同之处在于,要定义一个boolean isReverse = false;
在内部那个while结束后,判断下 isReverse
static void Collections.reverse(List<?> list) // 反转指定列表中元素的顺序。在原来list基础上修改的,不会返回值
再将isReverse = !isReverse;
注意:再导入import java.util.Collections;

33 二叉搜索树的后序遍历序列

问:二叉搜索树特点:每个节点的值大于其任意((左侧子节点的值,小于其任意**右节点的值。
输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。假设输入的数组的任意两个数字都互不相同。
答:另外建立一个功能函数。递归判断。private boolean verify(int [] sequence, int first, int last)
如果last<=first //已经递归到最后了,返回true;
//下面是重点
1、定义根节点的值 //也就是序列的最后一个元素
2、找出左右树的分界线 //从头到尾开始遍历,左边<根<右。因为是后序,所以找出左 右分界线就是看什么时候不满足元素的值<root的值
3、找出树的左右树之后,遍历所有右边的叶子是不是大于根节点的值,不满足就返回false
4、到了这一步,说明当前序列的根节点满足二叉树的特点,接下来要判断左右子树是不是也满足。

34 二叉树中和为某一值的路径

问:输入一颗二叉树的根节点和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中,数组长度大的数组靠前)
:
1、定义两个全局变量allList(最终结果集) 和 list(路径临时变量),
ArrayList<ArrayList> allList=new ArrayList<>();
ArrayList list=new ArrayList<>();
2、下面才开始写方法里的东西
3、root非null判断,返回allList;
3、list.add(根节点的值)
4、如果根节点的值等于target并且已经没有孩子节点。最终添加入结果集中,必须添加的是list的副本。
5、需要注意的是不论路径的值是否等于输入整数值,都要回退,即使用remove函数移除路径上list的最后一个节点。

35 (空,复杂链表不会)

36 二叉搜索树与双向链表

问:输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。
答:另写一个功能方法。inorder来完成排序,中序遍历。
1、非null判断。
2、 inorder(node.left);//这四行完成了双向指向
node.left = pre;
if(pre!= null){
pre.right = node;
}
pre = node;
inorder(node.right);
3、写主函数,inorder()后
再写个while方法找头节点

序列化二叉树(空,不会反序列)

38 字符串的排列(空,待做)

注:布尔型默认是false

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

问:数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。如果不存在则输出0。
答:多数投票问题。count来计数。
1、定义result的值为数组中的第一个元素,count = 1;
2、当遍历到的元素和统计元素相等时,令 count++,否则令 count–。
如果遍历时,count == 0了,令result 等于遍历到的这个值并且count =1 重新开始数数。继续查找就能找出 result。
3、遍历完了之后,无论这个值是不是次数符合要求,都会返回一个result,所以要判断result是否合理。只需要再遍历一次,等于的话count2++ 就行。

40 最小的 K 个数

41.1 数据流中的中位数

问:如何得到一个数据流中的中位数?如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值,那么中位数就是所有数值排序之后中间两个数的平均值。
答:用两个堆,大顶堆和小顶堆,大顶堆放较小的数,小顶堆放较大的数,这样子两个堆的根就是中位数。
注意:如何建立大顶堆 小顶堆。
private PriorityQueue right = new PriorityQueue<>(); //小顶堆
private PriorityQueue left = new PriorityQueue<>((o1, o2) -> o2 - o1); //大顶堆

字符流中第一个不重复的字符

问:请实现一个函数用来找出字符流中第一个只出现一次的字符。例如,当从字符流中只读出前两个字符 “go” 时,第一个只出现一次的字符是 “g”。当从该字符流中读出前六个字符“google” 时,第一个只出现一次的字符是 “l”
答:一共有256个字符(0~255),建立一个数组用来计数。
建立一个LinkedList 每次插入进去后,计数器加一,都要while检查队列头的字符在count中是不是大于1,是的话就吐出来,说明不符合

42 连续子数组的最大和

问:{6, -3, -2, 7, -15, 1, 2, 2},连续子数组的最大和为 8(从第 0 个开始,到第 3 个为止)。
:令最大值max 和 前面数组和preSum为 为数组中第一个元素
接下来从第二个元素开始遍历nums[i],如果preSum是正数,那就加上这个nums[i],否认就从当前这个点作为起始点即令preSum = nums[i]。
每一次这个遍历之后,都要看看max的值和preSum作比较

45 把数组排成最小的数

问:输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。例如输入数组{3,32,321},则打印出这三个数字能排成的最小数字为321323。
答:可以看成是一个排序问题,在比较两个字符串 S1 和 S2 的大小时,应该比较的是 S1+S2 和 S2+S1 的大小,如果 S1+S2 < S2+S1,那么应该把 S1 排在前面,否则应该把 S2 排在前面。

46 解码方法

问:给定一个数字,按照如下规则翻译成字符串:1 翻译成“a”,2 翻译成“b”… 26 翻译成“z”。一个数字有多种翻译可能,例如 12258 一共有 5 种,分别是 abbeh,lbeh,aveh,abyh,lyh。实现一个函数,用来计算一个数字有多少种不同的翻译方法。
答:

47 礼物的最大价值

问: 在一个 m*n 的棋盘的每一个格都放有一个礼物,每个礼物都有一定价值(大于 0)。从左上角开始拿礼物,每次向右或向下移动一格,直到右下角结束。给定一个棋盘,求拿到礼物的最大价值。

答: 动态规划建立一个同大小的 dp 矩阵的话,需要判断边界 i =0 j=0 情况,分四种情况讨论
也可以建立一个dp[r+1][c+1] 大小的矩阵,这样的话就只要一种情况。dp[i+1][j+1] = board[i][j] + Math.max(dp[i+1][j], dp[i][j+1]);

49 丑数

50 第一个只出现一次的字符位置

问:在一个字符串中找到第一个只出现一次的字符,并返回它的位置。
答:字符256个,用一个大小为256的数组用来计数。计数完之后再遍历一遍str,看他在数组中的位置是否为1。

51 数组中的逆序对

52 两个链表的第一个公共结点

答:两个链表接起来

54 二叉查找树的第 K 个结点

答:二叉查找树,又名二叉搜索树。中序遍历得结果就是有序的。

56 数组中只出现一次的数字

问:一个整型数组里除了两个数字之外,其他的数字都出现了两次,找出这两个数。
答:位运算

  1. 全部异或,得到两个融合在一起的xy = bitmask
  2. xy柔和在一个bitmask,其中的1必定是两者不一样的位,bitmask & (-bitmask) = bitmask & (~bitamsk + 1) = diff ,得到bitmask是保留位中最右边 1 ,且将其余的 1 设位 0 的方法。由此来区分x y 。注意这一步是并。
  3. 再次遍历,如果与diff 不为0,就异或进来,最后得到一个x
  4. 因为 x ^ y = bitmask
    所以 y = bitmask ^ x

57.2 和为 S 的连续正数序列

问: 输出所有和为S的连续正数序列。序列内按照从小至大的顺序,序列间按照开始数字从小到大的顺序
答:双指针

58.1 翻转单词顺序列

问:Input:”I am a student.”; Output:”student. a am I”
答: 不使用额外空间 先旋转每个单词,再旋转整个字符串。

58.2 左旋转字符串

问: Input: S=”abcXYZdef” K=3; Output:”XYZdefabc”
答:先将 “abc” 和 “XYZdef” 分别翻转,得到 “cbafedZYX”,然后再把整个字符串翻转得到 “XYZdefabc”。

59 滑动窗口的最大值

问:输入数组 以及 滑动窗口的大小。 输出最大的
答:暴力

60 n个骰子的点数

动态规划

61

62 圆圈中最后剩下的数

用数组模拟环

63 股票的最大利润

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
/*
找出数组的最大的差值
*/
public int maxProfit(int[] prices) {
int max=0;
for(int min=0, j=1; j<prices.length;j++){
if(prices[j]>prices[min]){
max = Math.max(max, prices[j] - prices[min]);
}else{
min = j;
}
}
return max;

}
}

64

使用递归解法最重要的是指定返回条件,但是本题无法直接使用 if 语句来指定返回条件。

条件与 && 具有短路原则,即在第一个条件语句为 false 的情况下不会去执行第二个条件语句。利用这一特性,将递归的返回条件取非然后作为 && 的第一个条件语句,递归的主体转换为第二个条件语句,那么当递归的返回条件为 true 的情况下就不会执行递归的主体部分,递归返回。

本题的递归返回条件为 n <= 0,取非后就是 n > 0;递归的主体部分为 sum += Sum_Solution(n - 1),转换为条件语句后就是 (sum += Sum_Solution(n - 1)) > 0。

65 不用加减乘除做加法


首先看十进制是如何做的: 5+7=12,三步走
第一步:相加各位的值,不算进位,得到2。
第二步:计算进位值,得到10. 如果这一步的进位值为0,那么第一步得到的值就是最终结果。

第三步:重复上述两步,只是相加的值变成上述两步的得到的结果2和10,得到12。

同样我们可以用三步走的方式计算二进制值相加: 5-101,7-111 第一步:相加各位的值,不算进位,得到010,二进制每位相加就相当于各位做异或操作,101^111。

第二步:计算进位值,得到1010,相当于各位做与操作得到101,再向左移一位得到1010,(101&111)<<1。

第三步重复上述两步, 各位相加 010^1010=1000,进位值为100=(010&1010)<<1。
继续重复上述两步:1000^100 = 1100,进位值为0,跳出循环,1100为最终结果。

68.1二叉查找树树中两个节点的最低公共祖先

从根节点开始遍历树
如果节点 pp 和节点 qq 都在右子树上,那么以右孩子为根节点继续 1 的操作
如果节点 pp 和节点 qq 都在左子树上,那么以左孩子为根节点继续 1 的操作
如果条件 2 和条件 3 都不成立,这就意味着我们已经找到节 pp 和节点 qq 的 LCA 了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root ==null){
return root;
}
if(root.val < p.val && root.val < q.val){
return lowestCommonAncestor(root.right, p, q);
}
if(root.val > p.val && root.val > q.val){
return lowestCommonAncestor(root.left, p, q);
}

return root;

}

68.2 普通二叉树中两个节点的最低公共祖先

在左右子树中查找是否存在 p 或者 q,如果 p 和 q 分别在两个子树中,那么就说明根节点就是最低公共祖先。

1
2
3
4
5
6
7
8
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root==null || root ==p || root ==q){
return root;
}
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
return left==null? right : right==null? left: root;
}