眯眯眼猫头鹰的小树杈

Owned By Deer&Owl

发表于 更新于 分类于 ，

题目要求

原题地址：https://leetcode.com/problems/longest-valid-parentheses/#/description

1
2
3
4
5
Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

For "(()", the longest valid parentheses substring is "()", which has length = 2.

Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.

一个括号序列，求出其中成对括号的最大长度

阅读全文 »

发表于 更新于 分类于 ，

题目要求

此处为原题地址

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

Note: The solution set must not contain duplicate quadruplets.

For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0.

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

也就是从数组中找到所有四个数字，这四个数字的和为目标值。这四个数字的组合不能重复。

这题的核心思路请参考我的另一篇博客three-sum，即如何找到三个数字，使其和为目标值。

阅读全文 »

发表于 更新于 分类于 ，

题目要求

1
2
3
4
5
6
7
8
9
Given an array of integers sorted in ascending order, find the starting and ending position of a given target value.

Your algorithm's runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

即 在一个有序排列的数组中，找到目标值所在的起始下标和结束下标。如果该目标值不在数组中，则返回[-1,-1]
题目中有一个特殊要求是时间复杂度为O(logn),也就是在暗示我们，不能只是单纯的按照顺序遍历数组，要尽量减去无效遍历。所以这题的核心思路为二分法遍历。

阅读全文 »

发表于 更新于 分类于 ，

题目要求

1
2
3
Divide two integers without using multiplication, division and mod operator.

If it is overflow, return MAX_INT.

在不使用乘法，除法和求余操作的情况下，计算两个整数相除的结果。如果溢出了，则返回最大值。

在这里核心思路是使用逆向二分法和递归的思路来进行计算。其中一个难点在于如何处理溢出的情况。在这里我们使用取值范围更广的long来处理数值溢出的场景。其次我们将所有的正负值运算从递归中提取出来，直接判断结果的正负情况并直接在返回最后结果时添上正负值

阅读全文 »

发表于 更新于 分类于 ，

题目要求

Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.
The Sudoku board could be partially filled, where empty cells are filled with the character '.'.
    
Note:
A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.

一个数独合法的标准如下

  1. 每一行每一列必须包含1-9之间的每一个数字（包括1和9）
  2. 每一个小的正方形矩阵中必须包含1-9之间的每一个数字（包括1和9）

所以总体思路就是遍历数独，判断行、列以及每一个小的正方形中的数字是否合法

如图所示的数独就是一个合法的数独

阅读全文 »

发表于 更新于 分类于 ，

题目要求

1
2
3
4
5
6
7
8
9
10
11
12
13
Given a set of candidate numbers (C) (without duplicates) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:
All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.
For example, given candidate set [2, 3, 6, 7] and target 7, 
A solution set is: 
[
  [7],
  [2, 2, 3]
]

一个整数数组，数组中的值不重复，要求在数组中找到所有的子数组，子数组满足元素的和为目标值的条件

阅读全文 »

发表于 更新于 分类于 ，

参考

思路和leetcode39 combination sum 非常类似，只是这里需要增加进行重复处理的部分。请参考我对leetcode39进行解答的这篇博客。

题目要求

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

Each number in C may only be used once in the combination.

Note:
All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.
For example, given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8, 
A solution set is: 
[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

题目中新添的要求包括数组中存在重复值，而且数组中每个值只可以使用一次。

思路与代码

这题与leetcode39的思路基本相同，利用递归的方法记录前一次情况作为下一次的初始情况。需要注意的是，既然数组中存在重复的值，就要注意可能会将重复的情况加入结果数组。
例如，如果数组为[2,2,2,6],目标值为8，可能会在结果数组中出现多次[2,6]
同样的，在进行递归的子遍历的时候也要注意，可能会出现重复值，例如数组为[2,2,2,6],目标值为10，则结果集[2,2,6]也可能出现多次，所以在子遍历中也要记得去除重复情况。
代码如下

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
38
39
40
41
public class CombinationSum2_40 {
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        int length = candidates.length;
        for(int i = 0 ; i<length ; i++){
            //去除外围重复情况
            if(i>0 && candidates[i] == candidates[i-1]){continue;}
            if(candidates[i] == target){
                result.add(Arrays.asList(candidates[i]));
            }else{
                List<Integer> temp = new ArrayList<Integer>();
                temp.add(candidates[i]);
                combinationSum2(candidates, target-candidates[i], i+1, temp);
            }
        }
        return result;
    }
    
    public void combinationSum2(int[] candidates, int target, int startAt, List<Integer> currentList){
        for(int i = startAt ; i<candidates.length ; i++){
            if(candidates[i] == target){
                currentList.add(candidates[i]);
                result.add(currentList);
                return;
            }
            if(candidates[i] > target){
                return;
            }
            if(candidates[i] < target){
                List<Integer> temp = new ArrayList<Integer>(currentList);
                temp.add(candidates[i]);
                combinationSum2(candidates, target-candidates[i], i+1, temp);
            }
            //去除自遍历中的重复情况
            while(i<candidates.length-1 && candidates[i] == candidates[i+1]){i++;}
        }
    }
    
}

发表于 更新于 分类于 ，

题目要求

1
2
3
4
5
6
You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

Follow up:
Could you do this in-place?

也就是在不创造一个新的数组的情况下，将一个二维数组中的元素顺时针旋转90度

阅读全文 »

发表于 更新于 分类于 ，

题目要求

1
2
3
4
5
6
7
8
9
10
11
Given an array of strings, group anagrams together.

For example, given: ["eat", "tea", "tan", "ate", "nat", "bat"], 
Return:

[
  ["ate", "eat","tea"],
  ["nat","tan"],
  ["bat"]
]
Note: All inputs will be in lower-case.

将含有相同的字母但是排序可能不同的单词分类至不同的数组

阅读全文 »
0%