眯眯眼猫头鹰的小树杈

Owned By Deer&Owl

发表于 更新于 分类于 ，

题目要求

1
2
3
4
5
6
7
8
9
10
11
12
Given a collection of distinct numbers, return all possible permutations.

For example,
[1,2,3] have the following permutations:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

也就是得出所有可能的排列组合结果

阅读全文 »

发表于 更新于 分类于 ，

题目要求

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

翻译过来就是说，输入一个整数数组，该整数数组按照下标顺序代表一个数字，例如[1,2,3]代表整数123，要求改变数组中元素的顺序，找到比当前数字大的生成数中的最小值。如果当前数字代表的整数值已经是所有排列组合中的最大值，则返回当前数字组成的最小值。

思路分析

如何才能找到一个值，不是过大也不是过小呢？其实，找到这几个数字所有排列组合的可能性，然后再和当前数字一一进行比较其实也是一个思路。可是这意味着大量无用的数字的生成和比较。想要知道如何生成所有排列组合结果，可以参考我的这篇博客
换句话说，我们要尽量用最少的比较的到最小的结果。一个数字中的各个位上的数如何调整顺序才能获得一个最小的更大值。首先，可以将低位移到高位，只要低位的数字比高位上的数字大。但是，为了确保的到尽可能小的最大值，一定要将移动的位确保越小越好。其次，要保证移动之后，高位以后的值为最小值。
综上所述，思路如下：

  1. 由最低位（下表为nums.length-2)开始，由低往高遍历，找到可以进行替换的最小位。
  2. 可以替换的条件是，比当前位低的位上存在一个数，该数比当前位上的值大，且不存在另一个比该值小且比当前位上值大的数
  3. 替换数值后，该进行替换的位后序的位上的值应当保证为最小值。
    例如[1，3，2]，将百位上的值和个位上的值替换以后，还要保证百位以后的值为最小值，所以最后的结果为[2,1,3]

实现代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public void nextPermutation(int[] nums) {
    for(int i = nums.length - 2 ; i>=0 ; i--){
        //寻找可以替换的最低位
        for(int j = i+1 ; j<nums.length ; j++){
            if(nums[i]<nums[j]){
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
                //确保替换位的后续位的值最小
                Arrays.sort(nums, i+1, nums.length);
                return;
            }
        }
        //若当前位不可替换，则自当前位开始排序，以保证下一位可以在不进行完整遍历的前提下找到最小的更大值
        Arrays.sort(nums,i,nums.length);
    }
}

发表于 更新于 分类于 ，

题目要求

1
2
3
4
5
6
7
8
9
Given a collection of numbers that might contain duplicates, return all possible unique permutations.

For example,
[1,1,2] have the following unique permutations:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

对于其基础题PermutationsI请参考我的另一篇博客
这里添加的难度在于，排列组合的数字中可能存在重复。这就需要想方法，将结果集中重复的结果删去。而这里，我参考了另一名答题者的答案，在试图将数字添入结果集中时，就判断会不会产生重复的结果，从而使避免重复。

阅读全文 »

发表于 更新于 分类于 ，

题目要求

1
2
3
4
5
6
7
8
You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.

For example, given:
s: "barfoothefoobarman"
words: ["foo", "bar"]

You should return the indices: [0,9].
(order does not matter).

输入一个字符串s和一个字符串数组words，其中words中的每个word的长度都相等。在字符串中找到所有子字符串的起始下标，只要该子字符串满足words中所有单词的连接结果（顺序无关）

阅读全文 »

发表于 更新于 分类于 ，

题目要求

1
2
3
4
5
6
7
8
9
10
11
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

即生成成对的括号，其中括号的数量为n

阅读全文 »

发表于 更新于 分类于 ，

题目要求

1
2
3
4
Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:
You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. The number of elements initialized in nums1 and nums2 are m and n respectively.

将两个有序数组合并至其中一个数组并且该新数组仍然有序。

阅读全文 »

发表于 更新于 分类于 ，

题目要求

1
2
3
4
5
6
7
8
9
10
Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

For example:
A = [2,3,1,1,4], return true.

A = [3,2,1,0,4], return false.

翻译过来就是，假设有一个数组，该数组中的元素全部都是非负整数。当前起点为数组中下标为零的位置，要走到数组的最后一个下标。其中，数组中每一个元素代表当前下标下可以前进的最大步数。如果可以从起点走向终点，那么返回true，否则返回false

阅读全文 »

发表于 更新于 分类于 ，

题目要求

1
2
3
4
5
Given a collection of intervals, merge all overlapping intervals.

For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

输入一系列区间，将出现交叉的区间合并起来，并将合并后的区间返回。这里需要注意的是，区间的大小顺序无关，即输出为[1,2],[3,4]和[3,4],[1,2]都是可以的

阅读全文 »

发表于 更新于 分类于 ，

题目要求

1
2
3
4
5
Given a list, rotate the list to the right by k places, where k is non-negative.

For example:
Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.

其实这题的描述有些不妥当，确切的说是将最右侧的节点依次移到最左侧作为头结点，一直移动到右侧第k个节点后结束。
还是以1->2->3->4->5->NULL为例
k=1 结果为：5->1->2->3->4->NULL
k=2 结果为：4->5->1->2->3->NULL
k=3 结果为：3->4->5->1->2->NULL
k=4 结果为：2->3->4->5->1->NULL
k=5 结果为：1->2->3->4->5->NULL
k=6 结果为：5->1->2->3->4->NULL

换句话说 当k的值超过了list的长度len的时候，移动k次等价于移动k%len次

阅读全文 »

发表于 更新于 分类于 ，

题目要求

1
2
3
4
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For example, 
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

假设这些是一些间隔的木板，问最多能够装多少水。也就是一个区域性的短板问题。其实一个区间能够乘的最大水量，取决于它的左右最近且最高的木板的长度。当然除了通过多个区间的和来计算总体的盛水量，还可以通过横向的划分来计算盛水量。这些将在接下来中的代码一一分析。官方也提供了一些答案，这里将给出相应的java实现的版本。

阅读全文 »
0%