LeetCode #33 Search in Rotated Sorted Array

题目:

Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.

 

分析:

在一个旋转过的有序数组中查找一个数,如果该数不存在,返回-1。

方法一:

首先通过二分查找找出数组中最小值的位置。这样我们可以将数组分成2段,使得每一段都是有序的。之后看要查找的数(target)的值落在哪一段,然后再在这一段里进行一次二分查找即可。

方法二:(推荐)

对于每一轮二分查找,中点的左侧和右侧必然有有一边是有序的。我们看看target是不是在有序的这个范围内,是的话就查这一边,不是的话就查另一边。

Continue reading LeetCode #33 Search in Rotated Sorted Array

已知前序遍历、中序遍历、后序遍历结果其中之二,生成二叉树

一、已知前序遍历和中序遍历

假设我们用2个数组preorder和inorder来表示前序和中序遍历的结果。

要生成的二叉树的任意子树都对应于preorder和inorder的某个子数组。该子树的根节点对应于preorder子数组的第一个元素,然后在inorder中查找该该元素。对于inorder中的的子数组,根节点元素左侧的子数组对应左子树,右侧的子数组对应右子树。之后使用递归重复该过程。

下面给出一段Java示例代码:

Continue reading 已知前序遍历、中序遍历、后序遍历结果其中之二,生成二叉树

LeetCode #133 Clone Graph (拷贝图)

题目:

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors

 

分析:

拷贝一个图。每个节点中用List存储它的邻居节点。

基本思路就是遍历原图,使用一个map来记录已经访问过的节点以及它和新节点的对应关系。

遍历可以考虑DFS或者BFS。下面的代码是使用BSF实现的。

Continue reading LeetCode #133 Clone Graph (拷贝图)

LeetCode #148 Sort List (链表合并排序)

题目:

Sort a linked list in O(n log n) time using constant space complexity.

 

分析:

排序一个链表。要求O(nlogn)时间,O(1)空间。

说到O(nlogn)时间,首先想到的是合并排序。虽然合并排序对于数组是O(n)空间,但是对于链表却可以做到O(1)空间。

Continue reading LeetCode #148 Sort List (链表合并排序)

LeetCode #71 Simplify Path (路径化简)

题目:

Given an absolute path for a file (Unix-style), simplify it.
For example,
path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"

 

分析:

路径化简。

基本思路就是使用栈来模拟进入某一路径或者返回上一级。

注意以下边界情况:

  • "/../" 应化简为 "/"
  • "/home//foo/" 应化简为 "/home/foo"

Continue reading LeetCode #71 Simplify Path (路径化简)

LeetCode #260 Single Number III (查找数组中2个不成对的数)

题目:

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.
For example:
Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].

Note:

  1. The order of the result is not important. So in the above example, [5, 3] is also correct.
  2. Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

 

分析:

数组中除了2个数以外,其他所有的数都是成对的。要求把这2个数找出来。

本题也用到了异或运算的性质:A^A = 0, A^B^A = B

首先遍历数组,将数组中所有的数进行异或之后,得到值就等于不成对的两个数的异或值。例如,对于[1,2,1,3,2,5],异或所有的数得到6,这也正是其中不成对的两个数3和5的异或结果。

得到这两个数的异或结果有什么用的?怎样把他们分开?

我们知道,既然两个数不成对,那么他们之间至少存在一个二进制位是不同的。我们可以通过这个不同的位来区分这两个数。对于异或运算的结果,1表示原来的两个数在这一位上不同。现在找到异或结果的任何一个置为1的位即可。还是看刚才的例子,3和5的异或运算如下:

      3 (0011)
xor   5 (0101)
=     6 (0110)

Continue reading LeetCode #260 Single Number III (查找数组中2个不成对的数)

LeetCode #222 Count Complete Tree Nodes (完全二叉树节点个数)

题目:

Given a complete binary tree, count the number of nodes.

 

分析:

给定一个完全二叉树的根节点,求该完全二叉树节点的个数。

完全二叉树就是:除最后一层外,每一层上的节点数均达到最大值;在最后一层上只缺少右边的若干结点。

本题的关键就是求二叉树最后一层的节点个数。对此我们可以使用二分查找。

使用一个整数来表示从根节点到叶子节点的路径,每一位代表方向(0向左,1向右)。例如,1个4层的二叉树,如果路径为5,写成二进制是101,就代表从根节点出发,右,左,右。

通过二分查找,我们可以得到最后一层第一个空节点的位置,也就知道了最后一层有几个几点。然后加上上面几层的节点数就是答案。

Continue reading LeetCode #222 Count Complete Tree Nodes (完全二叉树节点个数)

LeetCode #215 Kth Largest Element in an Array (查找数组中第K大的数)

题目:

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.
For example,
Given [3,2,1,5,6,4] and k = 2, return 5.
Note: 
You may assume k is always valid, 1 ≤ k ≤ array's length.

 

分析:

查找无序数组中第K大的数。

最简单暴力的方法就是先对整个数组排序,然后返回 nums[k-1] 即可。时间复杂度O(nlogn)。

有没有更高效的方法呢?我们不妨参考快速排序的思路,但是不对整个数列排序。

partition(int[] a, int lo, int hi)方法和快速排序一样,选取该分段中的第一个数为标兵(pivot)。所有大于pivot的数放到其左侧,小于pivot的数放到其右侧。最后返回pivot的位置。在经过一次partition方法之后,根据k和pivot的位置,来选择是对左侧部分还是对右侧部分继续进行partition。该方法时间复杂度为O(n)。

Continue reading LeetCode #215 Kth Largest Element in an Array (查找数组中第K大的数)

LeetCode #43 Multiply Strings (非负整数高精度乘法)

题目:

Given two numbers represented as strings, return multiplication of the numbers as a string.

Note: The numbers can be arbitrarily large and are non-negative.

 

分析:

任意长度非负整数乘法。

基本思路就是模拟用竖式手算乘法的过程。

注意处理进位和乘0的情况。

Continue reading LeetCode #43 Multiply Strings (非负整数高精度乘法)