眯眯眼猫头鹰的小树杈

Owned By Deer&Owl

发表于 更新于 分类于 ，

题目要求

1
2
3
4
5
6
7
8
9
10
11
Given an absolute path for a file (Unix-style), simplify it.

For example,
path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"
click to show corner cases.

Did you consider the case where path = "/../"?
In this case, you should return "/".
Another corner case is the path might contain multiple slashes '/' together, such as "/home//foo/".
In this case, you should ignore redundant slashes and return "/home/foo".

简化unix风格的绝对路径。
这里简单说一下unix风格的路径：

  • .表示当前文件夹，即不进行任何操作
  • ..表示返回上层文件夹，如果已经至根目录，则不进行任何操作
  • /表示路径的分割线，多个连续的/等价于/

这里我们需要将复杂的unix路径，例如/a/./b/../../c/简化成最简形式/c

阅读全文 »

发表于 更新于 分类于 ，

题目要求

1
2
3
4
5
6
7
8
9
Validate if a given string is numeric.

Some examples:
"0" => true
" 0.1 " => true
"abc" => false
"1 a" => false
"2e10" => true
Note: It is intended for the problem statement to be ambiguous. You should gather all requirements up front before implementing one.

写一个算法 判断输入的字符串是否是数字。
这道题的需求给的较为模糊，对于什么是数字并没有给出明确的定义。这里我要给出几个特殊的情况来说明数字究竟是什么。

  1. 空值返回false
  2. 字符串前后的空白字符不影响字符串最终的结果
  3. 1.以及.1都是符合标准的小数，但是**.**不符合
  4. e的前后必须有数字，e前的数字可以为整数或是小数，e后的数字必须为正/负整数/0
    阅读全文 »

发表于 更新于 分类于 ，

题目要求

1
2
3
4
5
6
7
8
9
10
11
12
Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note:
You are not suppose to use the library's sort function for this problem.
    
Follow up:
A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0's, 1's, and 2's, then overwrite array with total number of 0's, then 1's and followed by 2's.

Could you come up with an one-pass algorithm using only constant space?

假设一个数组中存在3个数字0，1，2。将数组中的数字排序，尽量实现O(n)时间复杂度。

阅读全文 »

发表于 更新于 分类于 ，

题目要求

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

Integers in each row are sorted from left to right.
The first integer of each row is greater than the last integer of the previous row.
For example,

Consider the following matrix:

[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
Given target = 3, return true.

假设存在这样一个二维数组，该数组从左到右，从上到下均递增，且下一行第一个值比上一行最后一个值大。要求从里面找到一个目标值，存在则返回true，否则返回false

一维二分法

熟悉二分法的知道，在一个有序的一维数组中，可以只用O(lgn)的时间复杂度就可以从中判读出目标值是否存在。我们可以先对第一列上的值进行一次二分法遍历，确定了行后再在行中进行第二次的二分法遍历。总计的时间复杂度为O(lgn），代码如下： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public boolean searchMatrix(int[][] matrix, int target) {
    int row = matrix.length;
    if(row==0){
        return false;
    }
    int column = matrix[0].length;
    if(column==0){
        return false;
    }
    
    int leftPointer = 0, rightPointer=row-1;
    
    while(leftPointer<=rightPointer){
        int mid = (leftPointer+rightPointer) / 2;
        if(matrix[mid][0]<=target && matrix[mid][column-1]>=target){
            leftPointer = 0;
            rightPointer = column-1;
            while(leftPointer<=rightPointer){
                int columnMid = (leftPointer + rightPointer) / 2;
                if(matrix[mid][columnMid] == target){
                    return true;
                }else if(matrix[mid][columnMid] < target){
                    rightPointer = columnMid-1;
                }else{
                    leftPointer = columnMid + 1;
                }
            }
            return false;
        }else if(target<matrix[mid][0]){
            rightPointer = mid-1;
        }else {
            leftPointer = mid + 1;
        }
    }
    return false;
    
}

二维二分法

如何能之间在二维数组上使用二分法呢。其实只要我们找到相应的左指针和右指针以及其对应的中间位置上的值即可。其实这个二维数组完全可以看成一个连续的一维数组，位于二维数组[i,j]位置可以看成一维数组中下标为[i*column+j].由此我们知道，左右指针对应中间节点在二维数组的下标为[mid/column][mid%column]。代码如下： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public boolean searchMatrix2(int[][] matrix, int target){
    if(matrix==null || matrix.length==0 || matrix[0].length==0){
        return false;
    }
    int row = matrix.length;
    int column = matrix[0].length;
    int left = 0;
    int right = row*column-1;
    while(left<=right){
        int mid = (left + right) / 2;
        int tempVal = matrix[mid/column][mid%column];
        if(tempVal == target){
            return true;
        }else if(tempVal < target){
            left = mid + 1;
        }else{
            right = mid - 1;
        }
    }
    return false;
}

发表于 更新于 分类于 ，

题目要求

1
2
3
4
5
6
7
8
9
10
11
12
13
Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

For example,
If n = 4 and k = 2, a solution is:

[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

有整数从1到n，问从中任选两个数有多少排列组合的结果（顺序无关）

阅读全文 »

发表于 更新于 分类于 ，

题目要求

1
2
3
4
5
6
7
Follow up for "Remove Duplicates":
What if duplicates are allowed at most twice?

For example,
Given sorted array nums = [1,1,1,2,2,3],

Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3. It doesn't matter what you leave beyond the new length.

Remove Duplicates I 可以参考我的这篇博客
这题中添加了一个要求，就是允许存在两个重复值。

阅读全文 »

发表于 更新于 分类于 ，

题目要求

1
The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.

For example,
There exist two distinct solutions to the 4-queens puzzle:

[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

这里的王后相当于国际围棋的王后，该王后一共有三种移动方式：水平、垂直，对角线。问要如何将n个王后布局在n*n的棋盘中保证她们不会互相伤害捏？

阅读全文 »

发表于 更新于 分类于 ，

题目要求

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Given a set of distinct integers, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,3], a solution is:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

类似的题目有：
leetcode60 Permutation Sequence 可以参考这篇博客
leetcode77 Combinations 可以参考这篇博客

阅读全文 »

发表于 更新于 分类于 ，

题目要求

1
2
3
4
5
6
7
Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.

将小于x的值放在前面，大于等于x的值放在后面，移动的过程中不改变数字之间的相对顺序。

阅读全文 »

发表于 更新于 分类于 ，

题目要求

1
2
3
4
5
Write a program to solve a Sudoku puzzle by filling the empty cells.

Empty cells are indicated by the character '.'.

You may assume that there will be only one unique solution.

也就是给出一个解决数独的方法，假设每个数独只有一个解决方案。

阅读全文 »
0%