眯眯眼猫头鹰的小树杈

Owned By Deer&Owl

发表于 更新于 分类于 ，

题目要求

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example:

    Input: "babad"
    
    Output: "bab"

Note: "aba" is also a valid answer.

Example:

    Input: "cbbd"
    
    Output: "bb"

翻译过来就是说：在一个字符串中寻找最长的子字符串，该字符串是回数（即从左往右和从右往左读的结果是相同的）。该字符串的最大长度为1000

阅读全文 »

发表于 更新于 分类于 ，

题目要求

1
2
3
4
5
6
7
8
9
The count-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 111221, ...

1 is read off as "one 1" or 11.
11 is read off as "two 1s" or 21.
21 is read off as "one 2, then one 1" or 1211.
Given an integer n, generate the nth sequence.

Note: The sequence of integers will be represented as a string.

英文的题目有点绕口，所以去网上找了一下题目的意思。
题目的核心逻辑在于将口语化的数数字转化为字符串。
例如
如果一串数字是1，则是1个1，对应的字符串为11
如果一串数字是11，则是2个1，对应的字符串为21
如果一串数字是1211，则是1个1，接着1个2，接着2个1，对应的字符串为111221
题目中输入n，则方法对第n-1个数数字结果再一次进行数数字，并返回字符串
所以输入1对应1，输入2则是对前一个1进行数数字得到11（1个1），输入3则是对11进行数数字得到21（2个1），并以此类推下去

阅读全文 »

发表于 更新于 分类于 ，

题目要求

1
2
3
4
5
6
7
8
9
10
11
Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

For example, given array S = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

输入一个整数数组，从中找到所有的三个整数组成一个数组，这三个整数的和为0。要求不包括重复的结果

阅读全文 »

发表于 更新于 分类于 ，

题目要求

1
2
3
4
5
6
7
8
9
10
Given a linked list, remove the nth node from the end of list and return its head.

For example,

   Given linked list: 1->2->3->4->5, and n = 2.

   After removing the second node from the end, the linked list becomes 1->2->3->5.
Note:
Given n will always be valid.
Try to do this in one pass.

题意就是，从链表中移除倒数第n个节点（前提是这个被移除的节点一定存在）

阅读全文 »

发表于 更新于 分类于 ，

题目要求

1
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

翻译过来就是：将两个有序的链表组合成一个新的有序的链表

阅读全文 »

发表于 更新于 分类于 ，

题目要求

1
2
3
4
Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.

即：寻找数列中的一个子数列，该数列中的值得和是所有子数列中最大的。

阅读全文 »

发表于 更新于 分类于 ，

题外话

鉴于这一题的核心思路和leetcode15的思路相同，可以先写一下15题并参考一下我之前的一篇博客

题目要求

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

1
2
3
For example, given array S = {-1 2 1 -4}, and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

翻译过来就是，假设一个有n的元素的整数数组S，从S中找到三个值，这三个值的距离输入的目标值最近。返回这三个值的和。

阅读全文 »

发表于 更新于 分类于 ，

题目要求

1
2
3
Given a digit string, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below.
1
2
3
4
5
Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.

也就是说，将数字对应的字母的排列组合的的所有可能结果都枚举出来，顺序不唯一。

leetcode给这道题目加了一个标签很有意思，叫做Backtracking。点进去之后又很多类似的题目。这种类型的题目一般需要求出上一种情况的前提下才可以得知下一种情况。比如我必须先得知按下“2”后所有字母的可能值，才能在计算出“22”对应的可能值

阅读全文 »

发表于 更新于 分类于 ，

题目要求

1
2
3
4
5
6
7
Suppose an array sorted in ascending order 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
3
4
5
6
7
8
9
10
11
12
13
14
15
public int search(int[] nums, int target){ 
    int left = 0;
    int right = nums.length - 1;
    while(left<=right){
        if(nums[left]==target){
            return left;
        }
        if(nums[right] == target){
            return right;
        }
        left++;
        right--;
    }
    return -1;
}

思路二：二分法查找

思路一并没有充分利用条件，及这个数组是由两个有序的子数组合成的。这里我们可以使用二分法的一个变形的算法。先找到中间节点，这个中间节点如果不是在左顺序子数组，就一定在右顺序子数组，反之亦成立。这样我们就可以变相的使用二分法将区间范围逐渐缩小，直至找到目标值。
这里相比于思路一，更适用于目标节点在中间的情况，而思路一在目标节点分布在数组两侧会效率更高。

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
public int search(int[] nums, int target){ 
    int left = 0;
    int right = nums.length - 1;
    while(left<=right){
        int mid = (left + right)/2;
        int midNum = nums[mid];
        if(midNum==target){
            return mid;
        }
        if(nums[left]<=midNum){
            if(nums[left]<=target && midNum>target){
                right = mid - 1;
            }else{
                left = mid + 1;
            }
        }
        if (midNum <= nums[right]){
            if (target > midNum && target <= nums[right])
                left = mid + 1;
             else
                right = mid - 1;
        }
    }
    return -1;
}

发表于 更新于 分类于 ，

题目要求

1
2
3
4
5
6
Given a linked list, swap every two adjacent nodes and return its head.

For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.

Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

翻译过来就是：将链表中相邻两个节点交换顺序，并返回最终的头节点。

阅读全文 »
0%