lintcode
程序员文章站
2022-07-15 12:15:05
...
样例
给出数组 [9,3,2,4,8]，第三大的元素是 4
给出数组 [1,2,3,4,5]，第一大的元素是 5，第二大的元素是 4，第三大的元素是 3，以此类推
挑战
要求时间复杂度为O(n)，空间复杂度为O(1)
public class Solution {
/*
* @param nums: A set of numbers.
* @return: A list of lists. All valid subsets.
*/
public List<List<Integer>> subsetsWithDup(int[] nums) {
// write your code here
//sort(nums.begin(),nums.end());
List<List<Integer>> result=new ArrayList<>();
List<Integer> temp=new ArrayList<>();
List<Integer> nums2=new ArrayList<>();
for(int i:nums){
nums2.add(i);
}
subset(result,nums2,temp,0);
return result;
}
public static void subset(List<List<Integer>> res,List<Integer> num,List<Integer> temp,int k) {
List<Integer> temp2=new ArrayList<>(temp);
if(!res.contains(temp2)){
res.add(temp2);
}
for (int i=k;i < num.size();i++) {
temp.add(num.get(i));
subset(res,num,temp,i+1);
temp.remove(num.get(i));
}
}
}9. 交叉字符串
给出三个字符串:s1、s2、s3，判断s3是否由s1和s2交叉构成。
您在真实的面试中是否遇到过这个题？
Yes
样例
比如 s1 = "aabcc" s2 = "dbbca"
- 当 s3 = "aadbbcbcac"，返回 true.
- 当 s3 = "aadbbbaccc"， 返回 false.
挑战
要求时间复杂度为O(n^2)或者更好
public class Solution {
/*
* @param s1: A string
* @param s2: A string
* @param s3: A string
* @return: Determine whether s3 is formed by interleaving of s1 and s2
*/
// 动态规划问题，逐步搜索
public boolean isInterleave(String s1, String s2, String s3) {
// write your code here
if(null == s1 || null == s2 || null == s3 || s1.length() + s2.length() != s3.length())
return false;
if(s1.length() <= 0 && s2.length() <= 0 && s3.length() <= 0)
return true;
// 初始化
boolean[][] common = new boolean[s1.length() + 1][s2.length() + 1];
for(int i = 1;i <= s1.length();i++)
{
if(s1.charAt(i - 1) == s3.charAt(i - 1))
{
common[i][0] = true;
}
}
for(int i = 1;i <= s2.length();i++)
{
if(s2.charAt(i - 1) == s3.charAt(i - 1))
{
common[0][i] = true;
}
}
// 顺序判断
for(int i = 1;i <= s1.length();i++)
{
for(int j = 1;j <= s2.length();j++)
{
if(s1.charAt(i - 1) == s3.charAt(i + j - 1))
{
common[i][j] = common[i - 1][j];
}
if(common[i][j])
{
continue;
}
if(s2.charAt(j - 1) == s3.charAt(i + j - 1))
{
common[i][j] = common[i][j - 1];
}
}
}
return common[s1.length()][s2.length()];
}
}. 数组划分
public class Solution {
/*
* @param nums: The integer array you should partition
* @param k: An integer
* @return: The index after partition
*/
public int partitionArray(int[] nums, int k) {
// write your code here
//write your code here
if(nums.length==0)
return 0;
int l=0;
int r=nums.length-1;
while(l<r){
while(l<r&&nums[l]<k)
l++;
while(l<r&&nums[r]>=k)
r--;
int temp=nums[l];
nums[l]=nums[r];
nums[r]=temp;
}
if(nums[nums.length-1]<k)
return nums.length;
return l;
}
}
32. 最小子串覆盖
public class Solution {
/*
* @param source : A string
* @param target: A string
* @return: A string denote the minimum window, return "" if there is no such a string
*/
public String minWindow(String source , String target) {
// write your code here
int[] srcHash = new int[255];
// 记录目标字符串每个字母出现次数
for(int i = 0; i < target.length(); i++){
srcHash[target.charAt(i)]++;
}
int start = 0,i= 0;
// 用于记录窗口内每个字母出现次数
int[] destHash = new int[255];
int found = 0;
int begin = -1, end = source.length(), minLength = source.length();
for(start = i = 0; i < source.length(); i++){
// 每来一个字符给它的出现次数加1
destHash[source.charAt(i)]++;
// 如果加1后这个字符的数量不超过目标串中该字符的数量，则找到了一个匹配字符
if(destHash[source.charAt(i)] <= srcHash[source.charAt(i)]) found++;
// 如果找到的匹配字符数等于目标串长度，说明找到了一个符合要求的子串
if(found == target.length()){
// 将开头没用的都跳过，没用是指该字符出现次数超过了目标串中出现的次数，并把它们出现次数都减1
while(start < i && destHash[source.charAt(start)] > srcHash[source.charAt(start)]){
destHash[source.charAt(start)]--;
start++;
}
// 这时候start指向该子串开头的字母，判断该子串长度
if(i - start < minLength){
minLength = i - start;
begin = start;
end = i;
}
// 把开头的这个匹配字符跳过，并将匹配字符数减1
destHash[source.charAt(start)]--;
found--;
// 子串起始位置加1，我们开始看下一个子串了
start++;
}
}
// 如果begin没有修改过，返回空
return begin == -1 ? "" : source.substring(begin,end + 1);
}
}33. N皇后问题
n皇后问题是将n个皇后放置在n*n的棋盘上，皇后彼此之间不能相互攻击。
给定一个整数n，返回所有不同的n皇后问题的解决方案。
每个解决方案包含一个明确的n皇后放置布局，其中“Q”和“.”分别表示一个女王和一个空位置。
样例
对于4皇后问题存在两种解决的方案：
[
[".Q..", // Solution 1
"...Q",
"Q...",
"..Q."],
["..Q.", // Solution 2
"Q...",
"...Q",
".Q.."]
]
挑战
你能否不使用递归完成？
public class Solution {
/*
* @param n: The number of queens
* @return: All distinct solutions
*/
public List<List<String>> solveNQueens(int n) {
// write your code here
List<List<String>> results = new ArrayList<>();
if (n <= 0) {
return results;
}
search(results, new ArrayList<Integer>(), n);
return results;
}
/*
* results store all of the chessboards
* cols store the column indices for each row
*/
private void search( List<List<String>> results,
ArrayList<Integer> cols,
int n) {
if (cols.size() == n) {
results.add(drawChessboard(cols));
return;
}
for (int colIndex = 0; colIndex < n; colIndex++) {
if (!isValid(cols, colIndex)) {
continue;
}
cols.add(colIndex);
search(results, cols, n);
cols.remove(cols.size() - 1);
}
}
private ArrayList<String> drawChessboard(ArrayList<Integer> cols) {
ArrayList<String> chessboard = new ArrayList<>();
for (int i = 0; i < cols.size(); i++) {
StringBuilder sb = new StringBuilder();
for (int j = 0; j < cols.size(); j++) {
sb.append(j == cols.get(i) ? 'Q' : '.');
}
chessboard.add(sb.toString());
}
return chessboard;
}
private boolean isValid(ArrayList<Integer> cols, int column) {
//cols存储了每一行Q所在的列
int row = cols.size();
//不能在同一列，且不能为对象线上的元素
for (int rowIndex = 0; rowIndex < row; rowIndex++) {
if (cols.get(rowIndex) == column) {
return false;
}
if (Math.abs(rowIndex - row) == Math.abs(column - cols.get(rowIndex))) {
return false;
}
}
return true;
}
}34. N皇后问题 II
根据n皇后问题，现在返回n皇后不同的解决方案的数量而不是具体的放置布局。
样例
比如n=4，存在2种解决方案
public class Solution {
/*
* @param n: The number of queens.
* @return: The total number of distinct solutions.
*/
public int totalNQueens(int n) {
// write your code here
// write your code here
List<List<String>> results = new ArrayList<>();
if (n <= 0) {
return results.size();
}
search(results, new ArrayList<Integer>(), n);
return results.size();
}
/*
* results store all of the chessboards
* cols store the column indices for each row
*/
private void search( List<List<String>> results,
ArrayList<Integer> cols,
int n) {
if (cols.size() == n) {
results.add(drawChessboard(cols));
return;
}
for (int colIndex = 0; colIndex < n; colIndex++) {
if (!isValid(cols, colIndex)) {
continue;
}
cols.add(colIndex);
search(results, cols, n);
cols.remove(cols.size() - 1);
}
}
private ArrayList<String> drawChessboard(ArrayList<Integer> cols) {
ArrayList<String> chessboard = new ArrayList<>();
for (int i = 0; i < cols.size(); i++) {
StringBuilder sb = new StringBuilder();
for (int j = 0; j < cols.size(); j++) {
sb.append(j == cols.get(i) ? 'Q' : '.');
}
chessboard.add(sb.toString());
}
return chessboard;
}
private boolean isValid(ArrayList<Integer> cols, int column) {
//cols存储了每一行Q所在的列
int row = cols.size();
//不能在同一列，且不能为对象线上的元素
for (int rowIndex = 0; rowIndex < row; rowIndex++) {
if (cols.get(rowIndex) == column) {
return false;
}
if (Math.abs(rowIndex - row) == Math.abs(column - cols.get(rowIndex))) {
return false;
}
}
return true;
}
}6. 翻转链表 II
/**
* Definition for ListNode
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
/*
* @param head: ListNode head is the head of the linked list
* @param m: An integer
* @param n: An integer
* @return: The head of the reversed ListNode
*/
public ListNode reverseBetween(ListNode head, int m, int n) {
// write your code here
if(m>=n||head==null)
return head;
//在头结点之前引入一个结点，因为头结点可能被翻转，这样可以使得头结点的
//翻转和普通结点一样
ListNode before=new ListNode(0);
before.next=head;
head=before;
for(int i=1;i<m;i++){
if(head==null){
return null;
}
//因为前面在头结点之前引入了一个结点，所以这里head指向m的前一个结点
head=head.next;
}
//当前结点，即M位置的结点，未移动，始终指向M所在的结点
ListNode mNode=head.next;
ListNode dangqianNode=mNode;//当前结点，后面会对其进行移动，值会改变
ListNode next=mNode.next;//当前结点的下一个结点
ListNode mQianMianDeNode=head;//M前一个位置的结点，从未改变
for(int i=m;m<n;m++){
if(next==null)
return null;
ListNode temp=next.next;//记录当前结点的下一个结点的下一个结点
next.next=dangqianNode;//改变当前结点的下一个结点链表指向的方向，
//即将下一个结点的next指向当前结点
dangqianNode=next;//将当前结点向后移动
next=temp;//将当前结点的下个结点向后移动
/*
示例过程:
如：2->3->4
2是当前结点(dangqianjiedian )
3是当前结点的下一个结点(next)
4是当前结点的下个结点的下个结点(next.next)
temp=next.next; temp=4 记录next.next
next.next=dangqianNode; 3->2 改变链表指向的方向
dangqianNode=next; dangqiangNode=3;
next=temp; next=4
*/
}
//避免链表断裂
//最开始的M之前的结点指向翻转后的当前结点
mQianMianDeNode.next=dangqianNode;
//最开始的M结点，（即还未翻转的M结点），//指向当前结点（翻转后）的下一个结点
mNode.next=next;
/*
1->2->3->4->5->null ;
M-N 翻转后 （4->3->2）
1指向翻转后当前的结点
1->4
2指向翻转后的下一个结点
2->5
完成后you有
1->4->3->2->5->null;
*/
//返回在头结点前引入的结点的下一个结点
return before.next;
}
}写出一个高效的算法来搜索m×n矩阵中的值，返回这个值出现的次数。
这个矩阵具有以下特性：
-
每行中的整数从左到右是排序的。
-
每一列的整数从上到下是排序的。
- 在每一行或每一列中没有重复的整数。
public class Solution {
/*
* @param matrix: A list of lists of integers
* @param target: An integer you want to search in matrix
* @return: An integer indicate the total occurrence of target in the given matrix
*/
public int searchMatrix(int[][] matrix, int target) {
// write your code here
if(matrix==null || matrix.length==0){
return 0;
}
int count=0;
int row=matrix.length-1;
int col=0;
while(row>=0 && col<=matrix[0].length-1){
if(target==matrix[row][col]){
count++;
row--;
col++;
}else if(target>matrix[row][col]){
col++;
}else{
row--;
}
}
return count;
}
}
42. 最大子数组 II
给定一个整数数组，找出两个 不重叠 子数组使得它们的和最大。
每个子数组的数字在数组中的位置应该是连续的。
返回最大的和。
注意事项
子数组最少包含一个数
样例
给出数组 [1, 3, -1, 2, -1, 2]
这两个子数组分别为 [1, 3] 和 [2, -1, 2] 或者 [1, 3, -1, 2] 和 [2]，它们的最大和都是 7
public class Solution {
/*
* @param nums: A list of integers
* @return: An integer denotes the sum of max two non-overlapping subarrays
*/
public int maxTwoSubArrays(List<Integer> nums) {
// write your code here
// write your code
int size = nums.size();
int[] left = new int[size];
int[] right = new int[size];
int sum = 0;
int minSum = 0;
int max = Integer.MIN_VALUE;
// 从左到右或得最大值，从右向左或得最大值，注意下表不是都从0开始，从左-右0；从右-左size-1;
for(int i = 0; i < size; i++){
// 求和
sum += nums.get(i);
//
max = Math.max(max, sum - minSum);
//
minSum = Math.min(sum, minSum);
left[i] = max;
}
sum = 0;
minSum = 0;
max = Integer.MIN_VALUE;
for(int i = size - 1; i >= 0; i--){
sum += nums.get(i);
max = Math.max(max, sum - minSum);
minSum = Math.min(sum, minSum);
right[i] = max;
}
max = Integer.MIN_VALUE;
for(int i = 0; i < size - 1; i++){
max = Math.max(max, left[i] + right[i + 1]);
}
return max;
}
}45. 最大子数组差
给定一个整数数组，找出两个不重叠的子数组A和B，使两个子数组和的差的绝对值|SUM(A) - SUM(B)|最大。
返回这个最大的差值。
注意事项
子数组最少包含一个数
样例
给出数组[1, 2, -3, 1]，返回 6
public class Solution {
/*
* @param nums: A list of integers
* @return: An integer indicate the value of maximum difference between two substrings
刚做了数组中两个子数组和的最大值，这一题是求差，感觉上题的求解思想应该是可以用的
A B 分别是两个子数组的和，则：
所以
当A>B 的时候A越大越好 B越小越好
当A<B 的时候B越大越好 A越小越好
根据上一题的思想，定义leftMax数组，leftMax[i] 表示0到 i之间元素的全局最大值，定义rightMin矩阵，rightMin [i] 表示i 到 len -1 之间元素的全局最小值
这样abs(leftMax[i] - rightMin[i+1]) 就是0到i 之间元素的最大值 减去 i + 1 到len-之间元素最小值 的绝对值，这个值得最大值就是两个子区间的 差的绝对值的最大值
注意，这样还是有问题的，只是上面提交只能通过53%
上面只是考虑的 A>B的情况，还需要考虑A<B的情况
A >B 的情况是：leftMax - rightMin
A<B 的情况是：rightMax - leftMin，具体思路参考上面的
*/
public int maxDiffSubArrays(int[] nums) {
if(nums == null || nums.length ==0)
return 0;
int len = nums.length;
int[] leftMax = new int[len];
int[] rightMin = new int[len];
int[] leftMin = new int[len];
int[] rightMax = new int[len];
int localMax = 0;
int globalMax = Integer.MIN_VALUE;
int localMin = 0;
int globalMin = Integer.MAX_VALUE;
for(int i=0;i <len ;i++){
localMax = Math.max(localMax + nums[i],nums[i]);
globalMax = Math.max(localMax,globalMax);
leftMax[i] = globalMax;
localMin = Math.min(localMin + nums[i],nums[i]);
globalMin = Math.min(localMin,globalMin);
leftMin[i] = globalMin;
}
localMin = 0;
globalMin = Integer.MAX_VALUE;
localMax = 0;
globalMax = Integer.MIN_VALUE;
for(int i=len-1;i >=0 ;i--){
localMin = Math.min(localMin + nums[i],nums[i]);
globalMin = Math.min(localMin,globalMin);
rightMin[i] = globalMin;
localMax = Math.max(localMax + nums[i],nums[i]);
globalMax = Math.max(localMax,globalMax);
rightMax[i] = globalMax;
}
int leftMAX = Integer.MIN_VALUE;
int rightMAX = Integer.MIN_VALUE;
for(int i=0;i<len-1;i++){
leftMAX = Math.max(Math.abs(leftMax[i] - rightMin[i+1]),leftMAX);
rightMAX = Math.max(Math.abs(leftMin[i] - rightMax[i+1]),rightMAX);
}
return Math.max(leftMAX,rightMAX);
}
}47. 主元素 II
给定一个整型数组，找到主元素，它在数组中的出现次数严格大于数组元素个数的三分之一。
注意事项
数组中只有唯一的主元素
样例
给出数组[1,2,1,2,1,3,3] 返回 1
public class Solution {
/*
* @param nums: a list of integers
* @return: The majority number that occurs more than 1/3
*/
public int majorityNumber(List<Integer> nums) {
// write your code
HashMap<Integer,Integer> map=new HashMap<Integer, Integer>();
map.put(nums.get(0), 1);
for(int i=1;i<nums.size();i++){
if(map.containsKey(nums.get(i))){
map.put(nums.get(i), map.get(nums.get(i))+1);
}else{
map.put(nums.get(i), 1);
}
}
Set<Integer> set=map.keySet();
Iterator<Integer> it=set.iterator();
while(it.hasNext()){
int temp=it.next();
if(map.get(temp)>nums.size()/3){
return temp;
}
}
return 0;
}
}
49. 字符大小写排序
给定一个只包含字母的字符串，按照先小写字母后大写字母的顺序进行排序。
注意事项
小写字母或者大写字母他们之间不一定要保持在原始字符串中的相对位置。
样例
给出"abAcD"，一个可能的答案为"acbAD"
public class Solution {
/*
* @param chars: The letter array you should sort by Case
* @return: nothing
*/
public void sortLetters(char[] chars) {
// write your code here
//write your code here
if(chars.length==0)
return;
int i=0;
int j=chars.length-1;
while(i<j){
while(i<j&&chars[i]>='a'&&chars[i]<='z')
i++;
while(i<j&&chars[j]>='A'&&chars[j]<='Z')
j--;
if(i<j){
char temp=chars[i];
chars[i]=chars[j];
chars[j]=temp;
}
}
}
}51. 上一个排列
给定一个整数数组来表示排列，找出其上一个排列。
注意事项
排列中可能包含重复的整数
样例
给出排列[1,3,2,3]，其上一个排列是[1,2,3,3]
给出排列[1,2,3,4]，其上一个排列是[4,3,2,1]
public class Solution {
/*
* @param nums: A list of integers
* @return: A list of integers that's previous permuation
*/
public static List<Integer> reverse(int start, int end, List<Integer> nums) {
for (int i = start, j = end; i < j; i++,j--) {
int temp = nums.get(i);
nums.set(i, nums.get(j));
nums.set(j, temp);
}
return nums;
}
public static List<Integer> previousPermuation(List<Integer> nums) {
if (nums == null || nums.size() == 0) {
return nums;
}
//Find last decreasing point before decreasing. nums[k] < nums[k+1]
int k = -1;
for (int i = nums.size()- 2; i >= 0; i--) {
if (nums.get(i) > nums.get(i + 1)) {
k = i;
break;
}
}
if (k == -1) {
return reverse(0, nums.size() - 1, nums);
}
//Find first smaller point, from right to left
int bigIndex = -1;
for (int i = nums.size() - 1; i >= 0; i--) {
if (nums.get(i) < nums.get(k)) {
bigIndex = i;
break;
}
}
//1. Swap bigger index with k; 2. Reverse the right side of k. [Try to make the smallest next permutation]
int temp = nums.get(k);
nums.set(k, nums.get(bigIndex));
nums.set(bigIndex,temp);
return reverse(k + 1, nums.size()- 1, nums);
}
}52. 下一个排列
给定一个整数数组来表示排列，找出其之后的一个排列。
注意事项
排列中可能包含重复的整数
样例
给出排列[1,3,2,3]，其下一个排列是[1,3,3,2]
给出排列[4,3,2,1]，其下一个排列是[1,2,3,4]
public class Solution {
/*
* @param nums: A list of integers
* @return: A list of integers that's previous permuation
*/
public static List<Integer> reverse(int start, int end, List<Integer> nums) {
for (int i = start, j = end; i < j; i++,j--) {
int temp = nums.get(i);
nums.set(i, nums.get(j));
nums.set(j, temp);
}
return nums;
}
public static List<Integer> previousPermuation(List<Integer> nums) {
if (nums == null || nums.size() == 0) {
return nums;
}
//Find last decreasing point before decreasing. nums[k] < nums[k+1]
int k = -1;
for (int i = nums.size()- 2; i >= 0; i--) {
if (nums.get(i) > nums.get(i + 1)) {
k = i;
break;
}
}
if (k == -1) {
return reverse(0, nums.size() - 1, nums);
}
//Find first smaller point, from right to left
int bigIndex = -1;
for (int i = nums.size() - 1; i >= 0; i--) {
if (nums.get(i) < nums.get(k)) {
bigIndex = i;
break;
}
}
//1. Swap bigger index with k; 2. Reverse the right side of k. [Try to make the smallest next permutation]
int temp = nums.get(k);
nums.set(k, nums.get(bigIndex));
nums.set(bigIndex,temp);
return reverse(k + 1, nums.size()- 1, nums);
}
}57. 三数之和
给出一个有n个整数的数组S，在S中找到三个整数a, b, c，找到所有使得a + b + c = 0的三元组。
注意事项
在三元组(a, b, c)，要求a <= b <= c。
结果不能包含重复的三元组。
样例
如S = {-1 0 1 2 -1 -4}, 你需要返回的三元组集合的是：
(-1, 0, 1)
(-1, -1, 2)
public class Solution {
/*
* @param numbers: Give an array numbers of n integer
* @return: Find all unique triplets in the array which gives the sum of zero.
*/
public List<List<Integer>> threeSum(int[] numbers) {
// write your code here
List<List<Integer>> res = new ArrayList<>();
Arrays.sort(numbers);
for (int i = 0; i < numbers.length; ++i) {
int l = i + 1, r = numbers.length - 1;
while (l < r) {
ArrayList<Integer> stepRes = new ArrayList<Integer>();
int sum = numbers[i] + numbers[l] + numbers[r];
if (sum == 0) {
stepRes.add(numbers[i]);
stepRes.add(numbers[l]);
stepRes.add(numbers[r]);
if (!res.contains(stepRes)) // 去重
res.add(stepRes);
}
if (sum <= 0) ++l;
else --r;
}
}
return res;
}
}58. 四数之和
给一个包含n个数的整数数组S，在S中找到所有使得和为给定整数target的四元组(a, b, c, d)。
注意事项
四元组(a, b, c, d)中，需要满足a <= b <= c <= d
答案中不可以包含重复的四元组。
样例
例如，对于给定的整数数组S=[1, 0, -1, 0, -2, 2] 和 target=0. 满足要求的四元组集合为：
(-1, 0, 0, 1)
(-2, -1, 1, 2)
(-2, 0, 0, 2)
public class Solution {
/*
* @param numbers: Give an array
* @param target: An integer
* @return: Find all unique quadruplets in the array which gives the sum of zero
*/
public List<List<Integer>> fourSum(int[] numbers, int target) {
// write your code here
List<List<Integer>> rst = new ArrayList<>();
if(numbers == null || numbers.length < 4) {
return rst;
}
Arrays.sort(numbers);
//Pick 1st element
for (int i = 0; i < numbers.length - 3; i++) {
if (i != 0 && numbers[i] == numbers[i - 1]) {//Check for duplicate of 1st element
continue;
}
//Pick 2nd element
for (int j = i + 1; j < numbers.length - 2; j++) {
if (j != i + 1 && numbers[j] == numbers[j - 1]) {//Check for duplicate of 2nd element
continue;
}
//Pick 3rd and 4th element
int third = j + 1;
int fourth = numbers.length - 1;
while (third < fourth) {
int sum = numbers[i] + numbers[j] + numbers[third] + numbers[fourth];
if (sum < target) {
third++;
} else if (sum > target) {
fourth--;
} else {//sum == target
ArrayList<Integer> list = new ArrayList<Integer>();
list.add(numbers[i]);
list.add(numbers[j]);
list.add(numbers[third]);
list.add(numbers[fourth]);
rst.add(list);
third++;
fourth--;
while (third < fourth && numbers[third] == numbers[third - 1]) {
third++;
}
while (third < fourth && numbers[fourth] == numbers[fourth + 1]){
fourth--;
}
}
}
}
}
return rst;
}
}59. 最接近的三数之和
给一个包含 n 个整数的数组 S, 找到和与给定整数 target 最接近的三元组，返回这三个数的和。
注意事项
只需要返回三元组之和，无需返回三元组本身
样例
例如 S = [-1, 2, 1, -4] and target = 1. 和最接近 1 的三元组是 -1 + 2 + 1 = 2.
public class Solution {
/*
* @param numbers: Give an array numbers of n integer
* @param target: An integer
* @return: return the sum of the three integers, the sum closest target.
*/
public int threeSumClosest(int[] numbers, int target) {
// write your code here
int res = Integer.MAX_VALUE;
Arrays.sort(numbers);
for (int i = 0; i < numbers.length; ++i) {
int l = i + 1, r = numbers.length - 1;
while (l < r) {
int sum = numbers[i] + numbers[l] + numbers[r];
if (Math.abs(sum - target) < Math.abs(res - target)) res = sum;
if (sum <= target) ++l;
else --r;
}
}
return res;
}
}(-1, -1, 2)
61. 搜索区间
给定一个包含 n 个整数的排序数组，找出给定目标值 target 的起始和结束位置。
如果目标值不在数组中，则返回[-1, -1]
样例
给出[5, 7, 7, 8, 8, 10]和目标值target=8,
返回[3, 4]
public class Solution {
/*
* @param A: an integer sorted array
* @param target: an integer to be inserted
* @return: a list of length 2, [index1, index2]
二分查找，
*/
public int[] searchRange(int[] A, int target) {
// write your code here
int []result=new int[2];
if(A.length==0){
result[0]=-1;
result[1]=-1;
return result;
}else if(A.length==1){
result[0]=0;
result[1]=0;
return result;
}
// 查找包含target的位置
int i=0;
int j=A.length-1;
while(i<j){
int m=(i+j)/2;
if(A[m]==target){
i=m;
break;
}else if(A[m]<target)
i=m+1;
else{
j=m-1;
}
}
// 向左找开始，向右找结束
int k=0,l=0;
if(A[i]==target){
k=i;
l=i;
while(k>=0&&target==A[k]) k--;
while(l<A.length&&target==A[l]) l++;
result[0]=k+1;
result[1]=l-1;
}
if(k==0&&l==0){
result[0]=-1;
result[1]=-1;
}
return result;
}
}62. 搜索旋转排序数组
假设有一个排序的按未知的旋转轴旋转的数组(比如，0 1 2 4 5 6 7 可能成为4 5 6 7 0 1 2)。给定一个目标值进行搜索，如果在数组中找到目标值返回数组中的索引位置，否则返回-1。
你可以假设数组中不存在重复的元素。
样例
给出[4, 5, 1, 2, 3]和target=1，返回 2
给出[4, 5, 1, 2, 3]和target=0，返回 -1
public class Solution {
/*
* @param A: an integer rotated sorted array
* @param target: an integer to be searched
* @return: an integer
二分查找
*/
public int search(int[] A, int target) {
// write your code here
if(A.length==0)
return -1;
int begin=0;
int end=A.length -1;
while(begin<=end){
int mid=begin+(end-begin)/2;
if(A[mid]==target)
return mid;
if(A[mid]>A[begin]){ //此时begin和mid肯定处在同一个递增数组上
//那么就直接运用原始的二分查找
if(A[begin]<=target&&target<A[mid])
end=mid-1;
else
begin=mid+1;
}else{ //此时mid处于第二个递增数组 begin处于第一个递增数组 自然的mid和end肯定处于第二个递增数组上
//还是直接运用原始的二分查找思想
if(A[mid]<target&&target<=A[end])
begin=mid+1;
else
end=mid-1;
}
}
return -1;
}
}63. 搜索旋转排序数组 II
跟进“搜索旋转排序数组”，假如有重复元素又将如何？
是否会影响运行时间复杂度？
如何影响？
为何会影响？
写出一个函数判断给定的目标值是否出现在数组中。
样例
给出[3,4,4,5,7,0,1,2]和target=4，返回 true
public class Solution {
/*
* @param A: an integer ratated sorted array and duplicates are allowed
* @param target: An integer
* @return: a boolean
*/
public boolean search(int[] A, int target) {
// write your code here
if(A.length==0)
return false;
int low = 0;
int high = A.length-1;
while(low <= high){
int mid = low+(high-low)/2;
if(A[mid] == target) return true;
if(A[low] < A[mid]){ // A[mid]落在左半区间
if(target >= A[low] && target < A[mid]) high = mid-1; // 目标在左半区间且在mid左边
else low = mid+1;
} else if(A[low] > A[mid]){ // A[mid]落在右半区间
if(target <= A[high] && target > A[mid]) low = mid+1; // 目标在右半区间且在mid右边
else high = mid-1;
} else //相等时顺序查找
low++;
}
return false;
}
}75. 寻找峰值
你给出一个整数数组(size为n)，其具有以下特点：
- 相邻位置的数字是不同的
- A[0] < A[1] 并且 A[n - 2] > A[n - 1]
假定P是峰值的位置则满足A[P] > A[P-1]且A[P] > A[P+1]，返回数组中任意一个峰值的位置。
注意事项
- It's guaranteed the array has at least one peak.
- The array may contain multiple peeks, find any of them.
- The array has at least 3 numbers in it.
样例
给出数组[1, 2, 1, 3, 4, 5, 7, 6]返回1, 即数值 2 所在位置, 或者6, 即数值 7 所在位置.
public class Solution {
/*
* @param A: An integers array.
* @return: return any of peek positions.
*/
public int findPeak(int[] A) {
// write your code here
int begin = 0;
int end = A.length - 1;
while(begin < end) {
int mid = begin + (end - begin)/2;
if(mid == 0)
return 1;
if(mid == A.length - 1)
return mid - 1;
if(A[mid] > A[mid - 1] && A[mid] > A[mid + 1])
return mid;
else if(A[mid] < A[mid - 1])
end = mid - 1;
else
begin = mid + 1;
}
return begin;
}
}76. 最长上升子序列
给定一个整数序列，找到最长上升子序列（LIS），返回LIS的长度。
说明
最长上升子序列的定义：
最长上升子序列问题是在一个无序的给定序列中找到一个尽可能长的由低到高排列的子序列，这种子序列不一定是连续的或者唯一的。
https://en.wikipedia.org/wiki/Longest_increasing_subsequence
样例
给出 [5,4,1,2,3]，LIS 是 [1,2,3]，返回 3
给出 [4,2,4,5,3,7]，LIS 是 [2,4,5,7]，返回 4
public class Solution {
/*
* @param nums: An integer array
* @return: The length of LIS (longest increasing subsequence)
*/
// 子序列可以不连续，子串必须连续
public int longestIncreasingSubsequence(int[] nums) {
// write your code here
if (nums == null || nums.length == 0) {
return 0;
}
int n = nums.length;
int[] dp = new int[n];
int max = 0;
for (int i = 0; i < n; i++) {
dp[i] = 1;
for (int j = 0; j < i; j++) {
// 如果[1,1,1,1,1]也是的话，判断需要加上等号。
if (nums[j] < nums[i]){
dp[i] = dp[i] > dp[j] + 1 ? dp[i] : dp[j] + 1;
}
}
if (dp[i] > max) {
max = dp[i];
}
}
return max;
}
}77. 最长公共子序列
给出两个字符串，找到最长公共子序列(LCS)，返回LCS的长度。
说明
最长公共子序列的定义：
-
最长公共子序列问题是在一组序列（通常2个）中找到最长公共子序列（注意：不同于子串，LCS不需要是连续的子串）。该问题是典型的计算机科学问题，是文件差异比较程序的基础，在生物信息学中也有所应用。
- https://en.wikipedia.org/wiki/Longest_common_subsequence_problem
样例
给出"ABCD" 和 "EDCA"，这个LCS是 "A" (或 D或C)，返回1
给出 "ABCD" 和 "EACB"，这个LCS是"AC"返回 2
public class Solution {
/*
* @param A: A string
* @param B: A string
* @return: The length of longest common subsequence of A and B
*/
public int longestCommonSubsequence(String A, String B) {
// write your code here
// 文件进行差异比较的基础，生物信息比较,动态规划
if (A == null || B == null || A.length() == 0 || B.length() == 0) {
return 0;
}
int[][] check = new int[A.length() + 1][B.length() + 1];
for (int i = 1; i <= A.length(); i++) {
for (int j = 1; j <= B.length(); j++) {
if (A.charAt(i - 1) == B.charAt(j - 1)) {
check[i][j] = check[i - 1][j - 1] + 1;
} else {
check[i][j] = Math.max(check[i][j], check[i - 1][j]);
check[i][j] = Math.max(check[i][j], check[i][j - 1]);
}
}
}
return check[A.length()][B.length()];
}
}78. 最长公共前缀
给k个字符串，求出他们的最长公共前缀(LCP)
样例
在 "ABCD" "ABEF" 和 "ACEF" 中, LCP 为 "A"
在 "ABCDEFG", "ABCEFG", "ABCEFA" 中, LCP 为 "ABC"
(-1, -1, 2)
public class Solution {
/*
* @param strs: A list of strings
* @return: The longest common prefix
*/
// 枚举法
public String longestCommonPrefix(String[] strs) {
// write your code here
if (strs == null || strs.length == 0) {
return "";
}
if (strs.length == 1) {
return strs[0];
}
String prefix = "";
int ind = 0;
while (ind < strs[0].length()) {
char c = strs[0].charAt(ind);
boolean valid = false;
for (int i = 1; i < strs.length; i++) {
if (strs[i].length() > ind && strs[i].charAt(ind) == c) {
valid = true;
} else {
valid = false;
break;
}
}
if (valid) {
prefix += "" + c;
} else {
break;
}
ind++;
}//END WHILE
return prefix;
}
}79. 最长公共子串
给出两个字符串，找到最长公共子串，并返回其长度。
注意事项
子串的字符应该连续的出现在原字符串中，这与子序列有所不同。
样例
给出A=“ABCD”，B=“CBCE”，返回 2
(-1, -1, 2)
public class Solution {
/*
* @param A: A string
* @param B: A string
* @return: the length of the longest common substring.
*/
public int longestCommonSubstring(String A, String B) {
// write your code here
if (A == null || B == null || A.length() == 0 || B.length() == 0) {
return 0;
}
int [][] D = new int[A.length() + 1][B.length() + 1];
int max = 0;
for (int i = 0; i <= A.length(); i++) {
for(int j = 0; j <= B.length(); j++) {
if (i == 0 || j == 0) {
D[i][j] = 0;
} else {
if (A.charAt(i - 1) == B.charAt(j - 1)) {
D[i][j] = D[i - 1][j - 1] + 1;
} else {
D[i][j] = 0;
}
max = Math.max(max, D[i][j]);
}
}
}
return max;
}
}83. 落单的数 II
给出3*n + 1 个的数字，除其中一个数字之外其他每个数字均出现三次，找到这个数字。
样例
给出 [1,1,2,3,3,3,2,2,4,1] ，返回 4
public class Solution {
/*
* @param A: An integer array
* @return: An integer
按位计算。int型数字占32位，如果这个数字出现3次，则与这个数字对应的每一位上的1也出现三次。使用int型数组记录每一位上1出现的次数，能被3整除则表示出现3次。最后得到的就是要求的数字。
*/
public int singleNumberII(int[] A) {
// write your code here
if(A == null || A.length == 0)
return 0;
int[] bits = new int[32];
int result = 0;
for(int i = 0; i < 32; i++){
// 对每一个数进行和1与操作，结果为0或者1，
for(int j = 0; j < A.length; j++){
bits[i] += A[j]>>i & 1;
}
// 取余3为0则次位上有3个1出现。
bits[i] = bits[i] % 3
// 移位回原来的数，得到原始数
result = result | bits[i] << i;
}
return result;
}
}84. 落单的数 III
给出2*n + 2个的数字，除其中两个数字之外其他每个数字均出现两次，找到这两个数字。
样例
给出 [1,2,2,3,4,4,5,3]，返回 1和5
public class Solution {
/*
* @param A: An integer array
* @return: An integer array
*/
public List<Integer> singleNumberIII(int[] A) {
// write your code here
if (A == null || A.length == 0) {
return null;
}
List<Integer> rst = new ArrayList<Integer>();
int xor = 0;
// 将所有数据进行异或操作
for (int i = 0; i < A.length; i++) {
xor ^= A[i];
}
// 找到为1的位置
int bitOnePos = 0;
for (int i = 0; i < 32; i++) {
if ((xor >> i & 1) == 1) {
bitOnePos = i;
}
}
// 整体异或一遍
int rstA = 0;
int rstB = 0;
for (int i = 0; i < A.length; i++) {
if ((A[i] >> bitOnePos & 1) == 1) {
rstA ^= A[i];
} else {
rstB ^= A[i];
}
}
rst.add(rstA);
rst.add(rstB);
return rst;
}
}(-1, -1, 2)
88. 最近公共祖先
给定一棵二叉树，找到两个节点的最近公共父节点(LCA)。
最近公共祖先是两个节点的公共的祖先节点且具有最大深度。
注意事项
假设给出的两个节点都在树中存在
样例
对于下面这棵二叉树
4
/ \
3 7
/ \
5 6
LCA(3, 5) = 4
LCA(5, 6) = 7
LCA(6, 7) = 7
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
* /**
*
* 普通的Binary Tree，node child 自顶向下蔓延。
方法1：O(1) sapce O(h). Recursive. 循环的截点是：
当root == null或者 A B 任何一个在findLCA底部被找到了(root== A || root == B)，那么就return 这个root.
三种情况：
1. A,B都找到，那么这个level的node就是其中一层的parent。其实，最先recursively return到的那个，就是最底的LCA parent.
2. A 或者 B 找到，那就还没有公共parent,return ��null得那个。
3. A B ��null, 那就找错了没有呗, return null
* /
*/
public class Solution {
/*
* @param root: The root of the binary search tree.
* @param A: A TreeNode in a Binary.
* @param B: A TreeNode in a Binary.
* @return: Return the least common ancestor(LCA) of the two nodes.
*/
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode A, TreeNode B) {
// write your code here
if (root == null || root == A || root == B) {
return root;
}
TreeNode left = lowestCommonAncestor(root.left, A, B);
TreeNode right = lowestCommonAncestor(root.right, A, B);
if (left != null && right != null) {//Found both A leaf and B leaf
return root;
} else if (left != null || right != null) {
return left != null ? left : right;
} else {
return null;
}
}
}91. 最小调整代价
给一个整数数组，调整每个数的大小，使得相邻的两个数的差不大于一个给定的整数target，调整每个数的代价为调整前后的差的绝对值，求调整代价之和最小是多少。
注意事项
你可以假设数组中每个整数都是正整数，且小于等于100。
样例
对于数组[1, 4, 2, 3]和target=1，最小的调整方案是调整为[2, 3, 2, 3]，调整代价之和是2。返回2。
public class Solution {
/*
* @param A: An integer array
* @param target: An integer
* @return: An integer
*/
public int MinAdjustmentCost(List<Integer> A, int target) {
// write your code here
// write your code here
if(A.size()<2) {
return 0;
}
int m = A.size();
long [][]dp = new long[m][101];
int i = 0, j = 0;
for (i = 0; i < 101; i++) {
dp[0][i] = Math.abs(A.get(0) - i);
}
for (i = 1; i < m; i++) {
for (j = 0; j < 101; j++) {
dp[i][j] = Integer.MAX_VALUE;
int dif = Math.abs(j - A.get(i));
int max = Math.min(100, j + target);
int min = Math.max(0, j - target);
for (int k = min; k <= max; k++) {
dp[i][j] = Math.min(dp[i][j], dp[i - 1][k] + dif);
}
}
}
long ans = Integer.MAX_VALUE;
for (j = 0; j < 101; j++) {
ans = Math.min(ans, dp[m - 1][j]);
}
return(int) ans;
}
}92. 背包问题
在n个物品中挑选若干物品装入背包，最多能装多满？假设背包的大小为m，每个物品的大小为A[i]
注意事项
你不可以将物品进行切割。
样例
如果有4个物品[2, 3, 5, 7]
如果背包的大小为11，可以选择[2, 3, 5]装入背包，最多可以装满10的空间。
如果背包的大小为12，可以选择[2, 3, 7]装入背包，最多可以装满12的空间。
函数需要返回最多能装满的空间大小。
public class Solution {
/**
* @param m: An integer m denotes the size of a backpack
* @param A: Given n items with size A[i]
* @return: The maximum size
*/
public int backPack(int m, int[] A) {
// write your code here
int[][] dp = new int[A.length][m + 1];//动态规划矩阵
for(int i = 0; i < A.length; i ++) {//背包空间为0时，不管要放第几个物品，可装满的背包空间为0.
dp[i][0] = 0;
}
for(int j = 1; j < m + 1; j++) {
if(A[0] <= j) {//当第0个物品的空间小于等于当前背包空间j时
dp[0][j] = A[0];//背包可装满的最大空间是第0个物品的体积
}else {//当第0个物品的空间大于当前背包空间j时
dp[0][j] = 0;//背包可装满的最大空间是0
}
for(int i = 1; i < A.length; i++) {//当放第1个到第A.length-1个物品时
if(A[i] > j) {//若该物品所占空间大于背包总空间（无论怎样腾背包空间，该物品无法放入背包
dp[i][j] = dp[i - 1][j];//背包可装满的最大空间不变
}else {//若该物品所占空间小于等于背包总空间,则需将背包空间腾出至少A[i]后，将该物品放入。放入新物品后背包最大可装满空间可能更大，也可能变小大，取大值作为背包空间为j且放第i个物品时可以有的最大可装满空间。
dp[i][j] = Math.max(dp[i-1][j - A[i]] + A[i], dp[i - 1][j]);
}
}
}
return dp[A.length - 1][m];
}
}94. 二叉树中的最大路径和
给出一棵二叉树，寻找一条路径使其路径和最大，路径可以在任一节点中开始和结束（路径和为两个节点之间所在路径上的节点权值之和）
样例
给出一棵二叉树：
1 / \ 2 3
返回 6
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/
public class Solution {
private class PathSumType {
int singlePathMax;
int combinedPathMax;
PathSumType(int singlePathMax, int combinedPathMax) {
this.singlePathMax = singlePathMax;
this.combinedPathMax = combinedPathMax;
}
}
/**
* @param root: The root of binary tree.
* @return: An integer.
*/
public int maxPathSum(TreeNode root) {
PathSumType result = helper(root);
return result.combinedPathMax;
}
public PathSumType helper(TreeNode root) {
if (root == null) {
return new PathSumType(0, Integer.MIN_VALUE);
}
//Divide
PathSumType left = helper(root.left);
PathSumType right = helper(root.right);
//Conquer
//Step 1: prepare single path max for parent-level comparison.
int singlePathMax = Math.max(left.singlePathMax, right.singlePathMax) + root.val;
singlePathMax = Math.max(singlePathMax, 0);//If less than 0, no need to keep, because it only decrease parent-level max.
//first comparison: does not include root node at all(this would be applicable when curr.val < 0, so we take this condition into account)
int combinedPathMax = Math.max(left.combinedPathMax, right.combinedPathMax);
//second comparison:
combinedPathMax = Math.max(combinedPathMax, left.singlePathMax + right.singlePathMax + root.val);
return new PathSumType(singlePathMax, combinedPathMax);
}
}95. 验证二叉查找树
给定一个二叉树，判断它是否是合法的二叉查找树(BST)
一棵BST定义为：
- 节点的左子树中的值要严格小于该节点的值。
- 节点的右子树中的值要严格大于该节点的值。
- 左右子树也必须是二叉查找树。
- 一个节点的树也是二叉查找树。
样例
一个例子：
2
/ \
1 4
/ \
3 5
上述这棵二叉树序列化为 {2,1,4,#,#,3,5}.
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/
public class Solution {
/*
* @param root: The root of binary tree.
* @return: True if the binary tree is BST, or false
*/
public int lastVal = Integer.MAX_VALUE;
public boolean firstNode = true;
public boolean isValidBST(TreeNode root) {
// write your code here
if(root == null){
return true;
}
if(!isValidBST(root.left)){
return false;
}
if(!firstNode && lastVal >= root.val){
return false;
}
//此时 root.val>=lastval 是右子树
firstNode = false;
lastVal = root.val;
if(!isValidBST(root.right)){
return false;
}
return true;
}
}98. 链表排序
在 O(n log n) 时间复杂度和常数级的空间复杂度下给链表排序。
样例
给出 1->3->2->null，给它排序变成 1->2->3->null
/**
* Definition for ListNode.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int val) {
* this.val = val;
* this.next = null;
* }
* }
*/
public class Solution {
/*
* @param head: The head of linked list.
* @return: You should return the head of the sorted linked list, using constant space complexity.
*/
public ListNode sortList(ListNode head) {
// write your code here
if(head == null || head.next == null) return head;
ListNode mid = findMid(head);
ListNode tmp = mid.next;
mid.next = null;
ListNode headleft = sortList(head);
ListNode headright = sortList(tmp);
return merge(headleft, headright);
}
public static ListNode findMid(ListNode head){
if(head == null || head.next == null) return head;
ListNode slow = head;
ListNode fast = head;
while(fast.next != null && fast.next.next != null){
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
public static ListNode merge(ListNode left, ListNode right){
if(left == null || right == null) return null;
ListNode node = new ListNode(0);
ListNode dummy = node;
while(left != null && right != null){
if(left.val < right.val){
ListNode tmp = left;
left = left.next;
dummy.next = tmp;
dummy = dummy.next;
}else{
ListNode tmp = right;
right = right.next;
dummy.next = tmp;
dummy = dummy.next;
}
}
if(left != null) dummy.next = left;
else dummy.next = right;
return node.next;
}
}99. 重排链表
给定一个单链表L: L0→L1→…→Ln-1→Ln,
重新排列后为：L0→Ln→L1→Ln-1→L2→Ln-2→…
必须在不改变节点值的情况下进行原地操作。
样例
给出链表 1->2->3->4->null，重新排列后为1->4->2->3->null。
/**
* Definition for ListNode.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int val) {
* this.val = val;
* this.next = null;
* }
* }
*/
public class Solution {
/*
* @param head: The head of linked list.
* @return: nothing
*/
public void reorderList(ListNode head) {
// write your code here
if (head == null || head.next == null) {
return;
}
ListNode mid = findMiddle(head);
ListNode tail = reverse(mid.next);
mid.next = null;
merge(head, tail);
}
private ListNode reverse(ListNode head) {
ListNode newHead = null;
while (head != null) {
ListNode temp = head.next;
head.next = newHead;
newHead = head;
head = temp;
}
return newHead;
}
private void merge(ListNode head1, ListNode head2) {
int index = 0;
ListNode dummy = new ListNode(0);
while (head1 != null && head2 != null) {
if (index % 2 == 0) {
dummy.next = head1;
head1 = head1.next;
} else {
dummy.next = head2;
head2 = head2.next;
}
dummy = dummy.next;
index ++;
}
if (head1 != null) {
dummy.next = head1;
} else {
dummy.next = head2;
}
}
private ListNode findMiddle(ListNode head) {
ListNode slow = head, fast = head.next;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
}102. 带环链表
给定一个链表，判断它是否有环。
样例
给出 -21->10->4->5, tail connects to node index 1，返回 true
/**
* Definition for ListNode.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int val) {
* this.val = val;
* this.next = null;
* }
* }
*/
public class Solution {
/*
* @param head: The first node of linked list.
* @return: True if it has a cycle, or false
*/
public boolean hasCycle(ListNode head) {
// write your code here
if (head == null || head.next == null) {
return false;
}
ListNode slow = head;
ListNode fast = head.next;
while (slow != fast) {//Compare their reference address
if (fast == null || fast.next == null) {//travel till the end
return false;//no cycle
}
slow = slow.next;
fast = fast.next.next;
}
//If slow==fast and breaks the while loop, then there must be a cycle
return true;
}
}104. Merge K Sorted Lists
合并k个排序链表，并且返回合并后的排序链表。尝试分析和描述其复杂度。
样例
给出3个排序链表[2->4->null,null,-1->null]，返回 -1->2->4->null
/**
* Definition for ListNode.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int val) {
* this.val = val;
* this.next = null;
* }
* }
*/
public class Solution {
/**
* @param lists: a list of ListNode
* @return: The head of one sorted list.
*/
public ListNode mergeKLists(List<ListNode> lists) {
// write your code here
if (lists == null || lists.size() == 0) {
return null;
}
PriorityQueue<ListNode> queue =
new PriorityQueue<ListNode>(lists.size(), new Comparator<ListNode>(){
public int compare(ListNode a, ListNode b){
return a.val - b.val;
}
});
// 把链表的头结点放入优先队列后自动排序
//populate queue with k lists' header
for (int i = 0; i < lists.size(); i++) {
if (lists.get(i) != null) {
queue.offer(lists.get(i));
}
}
// 重新整合为一个链表
ListNode dummy = new ListNode(0);
ListNode node = dummy;
while (!queue.isEmpty()) {
// 弹出最小的头
ListNode curr = queue.poll();
node.next = curr;
if (curr.next != null) {
// 放入当前头后面的节点
queue.offer(curr.next);
}
node = node.next;
}
return dummy.next;
}
}
106. 排序列表转换为二分查找树
给出一个所有元素以升序排序的单链表，将它转换成一棵高度平衡的二分查找树
样例
2
1->2->3 => / \
1 3(-1, -1, 2)
/**
* Definition for ListNode.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int val) {
* this.val = val;
* this.next = null;
* }
* }
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/
public class Solution {
/*
* @param head: The first node of linked list.
* @return: a tree node
*/
public TreeNode sortedListToBST(ListNode head) {
// write your code here
if (head == null) {
return null;
} else if (head.next == null) {
return new TreeNode(head.val);
}
// 找中间节点
ListNode mid = findMiddle(head);
// 找到根节点
TreeNode root = new TreeNode(mid.next.val);
// 排右边
TreeNode right = sortedListToBST(mid.next.next);
// 断开
mid.next = null;
// 排左边
TreeNode left = sortedListToBST(head);
root.left = left;
root.right = right;
return root;
}
public ListNode findMiddle(ListNode head) {
ListNode slow = head;
ListNode fast = head.next;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
}
107. 单词拆分 I
给出一个字符串s和一个词典，判断字符串s是否可以被空格切分成一个或多个出现在字典中的单词。
样例
给出
s = "lintcode"
dict = ["lint","code"]
返回 true 因为"lintcode"可以被空格切分成"lint code"
public class Solution {
/*
* @param s: A string
* @param dict: A dictionary of words dict
* @return: A boolean
*/
public boolean wordBreak(String s, Set<String> dict) {
// write your code
if (s == null || dict.contains(s)) {
return true;
}
boolean[] valid = new boolean[s.length() + 1];
valid[s.length()] = true;
int maxLength = calMaxLength(dict);
for (int i = s.length() - 1; i >= 0; i--) {
for (int j = i; j < s.length() && (i - j) <= maxLength; j++) {//iterate [0 ~ i]
if (valid[j + 1] && dict.contains(s.substring(i, j + 1))) {
valid[i] = true;
break;
}
}
}
return valid[0];
}
public int calMaxLength(Set<String> dict) {
int length = 0;
for (String word : dict) {
length = Math.max(length, word.length());
}
return length;
}
}113. 删除排序链表中的重复数字 II
给定一个排序链表，删除所有重复的元素只留下原链表中没有重复的元素。
样例
(-1, -1, 2)
(-1, -1, 2)
(-1, -1, 2)
(-1, -1, 2)
给出 1->2->3->3->4->4->5->null，返回 1->2->5->null
给出 1->1->1->2->3->null，返回 2->3->null
(-1, -1, 2)
/**
* Definition for ListNode
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
/*
* @param head: head is the head of the linked list
* @return: head of the linked list
*/
public ListNode deleteDuplicates(ListNode head) {
// write your code here
// write your code here
if(head == null) {
return null;
}
//新建一个链表，h节点作为头节点，将链表的第一个值赋给它
ListNode h = new ListNode(head.val);
ListNode p = h;
int temp=head.val;
while(head.next != null) {
head = head.next;
if(head.val != p.val && temp!=head.val) {
ListNode node = new ListNode(head.val);
p.next = node;
p = p.next;
}else{
temp=head.val;
}
}
return h;
}
}
(-1, -1, 2)
116. 跳跃游戏
给出一个非负整数数组，你最初定位在数组的第一个位置。
数组中的每个元素代表你在那个位置可以跳跃的最大长度。
判断你是否能到达数组的最后一个位置。
注意事项
这个问题有两个方法，一个是贪心和 动态规划。
贪心方法时间复杂度为O（N）。
动态规划方法的时间复杂度为为O（n^2）。
我们手动设置小型数据集，使大家可以通过测试的两种方式。这仅仅是为了让大家学会如何使用动态规划的方式解决此问题。如果您用动态规划的方式完成它，你可以尝试贪心法，以使其再次通过一次。
样例
A = [2,3,1,1,4]，返回 true.
A = [3,2,1,0,4]，返回 false.
public class Solution {
/*
* @param A: A list of integers
* @return: A boolean
*/
public boolean canJump(int[] A) {
// write your code here
if (A == null || A.length == 0) {
return false;
}
//By default, boolean[] can is all false
boolean[] can = new boolean[A.length];
can[0] = true;
for (int i = 1; i < A.length; i++) {
for (int j = 0; j < i; j++) {
if (can[j] && (j + A[j] >= i)) {
can[i] = true;
break;
}
}
}
return can[A.length - 1];
}
}117. 跳跃游戏 II
给出一个非负整数数组，你最初定位在数组的第一个位置。
数组中的每个元素代表你在那个位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
样例
给出数组A = [2,3,1,1,4]，最少到达数组最后一个位置的跳跃次数是2(从数组下标0跳一步到数组下标1，然后跳3步到数组的最后一个位置，一共跳跃2次)
public class Solution {
/*
* @param A: A list of integers
* @return: An integer
*/
public int jump(int[] A) {
// write your code here
if (A == null || A.length <= 1) {
return 0;
}
int index = 0;
int step = 0;
int range = 0;
int maxRange = 0;
while (index < A.length) {
if (range >= A.length - 1) {
break;
}
while (index <= range) {
maxRange = Math.max(maxRange, index + A[index]);
index++;
}
range = maxRange;
step++;
}
return step;
}
}118. 不同的子序列
给出字符串S和字符串T，计算S的不同的子序列中T出现的个数。
子序列字符串是原始字符串通过删除一些(或零个)产生的一个新的字符串，并且对剩下的字符的相对位置没有影响。(比如，“ACE”是“ABCDE”的子序列字符串,而“AEC”不是)。
样例
给出S = "rabbbit", T = "rabbit"
返回 3
public class Solution {
/*
* @param : A string
* @param : A string
* @return: Count the number of distinct subsequences
*/
public int numDistinct(String S, String T) {
// write your code here
int[][] DP = new int[T.length() + 1][S.length() + 1];
DP[0][0] = 1;
for(int i = 1; i < S.length(); i++) {
DP[0][i] = 1;
}
for (int i = 1; i < T.length(); i++) {
DP[i][0] = 0;
}
for (int i = 1; i <= T.length(); i++) {
for (int j = 1; j <= S.length(); j++){
DP[i][j] = DP[i][j - 1];
if (T.charAt(i - 1) == S.charAt(j - 1)) {
DP[i][j] += DP[i - 1][j - 1];
}
}
}
return DP[T.length()][S.length()];
}
};119. 编辑距离
给出两个单词word1和word2，计算出将word1 转换为word2的最少操作次数。
你总共三种操作方法：
- 插入一个字符
- 删除一个字符
-
替换一个字符
样例
给出 work1="mart" 和 work2="karma"
返回 3
public class Solution {
/*
* @param word1: A string
* @param word2: A string
* @return: The minimum number of steps.
*/
public int minDistance(String word1, String word2) {
// write your code here
if (word1 == null && word2 != null) {
return word2.length();
} else if (word1 != null && word2 == null) {
return word1.length();
} else if (word1 == null && word2 == null) {
return 0;
}
int[][] DP = new int[word1.length() + 1][word2.length() + 1];
for (int i = 1; i <= word1.length(); i++) {
DP[i][0] = i;
}
for (int j = 1; j <= word2.length(); j++) {
DP[0][j] = j;
}
for (int i = 1; i <= word1.length(); i++) {
for (int j = 1; j <= word2.length(); j++) {
DP[i][j] = Math.min(Math.min(DP[i - 1][j] + 1, DP[i][j - 1] + 1), word1.charAt(i - 1) == word2.charAt(j - 1) ? DP[i - 1][j - 1] : DP[i - 1][j - 1] + 1);
}
}
return DP[word1.length()][word2.length()];
}
}120. 单词接龙
给出两个单词（start和end）和一个字典，找到从start到end的最短转换序列
比如：
-
每次只能改变一个字母。
- 变换过程中的中间单词必须在字典中出现。
注意事项
-
如果没有转换序列则返回0。
-
所有单词具有相同的长度。
- 所有单词都只包含小写字母。
样例
给出数据如下：
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]
一个最短的变换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog"，
返回它的长度 5
public class Solution {
/*
* @param start: a string
* @param end: a string
* @param dict: a set of string
* @return: An integer
*/
private Queue<String> q = new LinkedList<String>();
private HashSet<String> set = new HashSet<String>();
private Set<String> dict;
private String end;
private int level = 1;
private int len = Integer.MAX_VALUE;
public int ladderLength(String start, String end, Set<String> dict) {
// write your code here
if (start == null || end == null || dict == null || start.length() != end.length()) {
return 0;
}
this.dict = dict;
this.end = end;
q.offer(start);
set.add(start);
while(!q.isEmpty()) {//BFS
int size = q.size();//Fix size
level++;
for (int k = 0; k < size; k++) {//LOOP through existing queue: for this specific level
String str = q.poll();
validateMutations(str);
}//END FOR K
}//END WHILE
return len;
}
public void validateMutations(String str) {
for (int i = 0; i < str.length(); i++) {//Alternate each letter position
for (int j = 0; j < 26; j++) {//Alter 26 letters
String newStr;
if (i == 0 && str.length() == 1) {
newStr = "" + (char)('a' + j);
}
else if (i == str.length() - 1) {
newStr = str.substring(0, i) + (char)('a' + j);
} else {
newStr = str.substring(0, i) + (char)('a' + j) + str.substring(i + 1);
}
if (!set.contains(newStr) && dict.contains(newStr)) {
if (newStr.equals(end)) {//Found end
len = Math.min(len, level);
} else {
set.add(newStr);
q.offer(newStr);
}
}
}//END FOR J
}//END FOR I
}
}(-1, -1, 2)
123. 单词搜索
给出一个二维的字母板和一个单词，寻找字母板网格中是否存在这个单词。
单词可以由按顺序的相邻单元的字母组成，其中相邻单元指的是水平或者垂直方向相邻。每个单元中的字母最多只能使用一次。
样例
给出board =
[
"ABCE",
"SFCS",
"ADEE"
(-1, -1, 2)
]
word = "ABCCED"， ->返回 true,
word = "SEE"，-> 返回 true,
word = "ABCB"， -> 返回 false.
public class Solution {
/*
* @param board: A list of lists of character
* @param word: A string
* @return: A boolean
*/
public boolean exist(char[][] board, String word) {
// write your code here
if (word == null || word.length() == 0) {
return true;
}
if (board == null) {
return false;
}
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
if (board[i][j] == word.charAt(0)) {
boolean rst = search(board, word, i, j, 0);
if (rst) {
return true;
}
}
}
}
return false;
}
public boolean search(char[][] board, String word, int i, int j, int start) {
if (start == word.length()) {
return true;
}
if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != word.charAt(start)) {
return false;
}
board[i][j] = '#';
boolean rst = search(board, word, i, j - 1, start + 1)
|| search(board, word, i, j + 1, start + 1)
|| search(board, word, i + 1, j, start + 1)
|| search(board, word, i - 1, j, start + 1);
board[i][j] = word.charAt(start);
return rst;
}
}
(-1, -1, 2)
]
word = "ABCCED"， ->返回 true,
word = "SEE"，-> 返回 true,
word = "ABCB"， -> 返回 false.
124. 最长连续序列
给定一个未排序的整数数组，找出最长连续序列的长度。
说明
要求你的算法复杂度为O(n)
样例
给出数组[100, 4, 200, 1, 3, 2]，这个最长的连续序列是 [1, 2, 3, 4]，返回所求长度 4
public class Solution {
/*
* @param num: A list of integers
* @return: An integer
*/
public int longestConsecutive(int[] num) {
// write your code here
if (num == null || num.length == 0) {
return 0;
}
int maxL = 1;
HashMap<Integer, Boolean> history = new HashMap<Integer, Boolean>();
for (int i : num) {
history.put(i, false);
}
for (int i : num) {
if (history.get(i)) {
continue;
}
//check ++ side
int temp = i;
int total = 1;
while (history.containsKey(temp + 1)) {
total++;
temp++;
history.put(temp, true);
}
//check -- side
temp = i;
while (history.containsKey(temp - 1)) {
total++;
temp--;
history.put(temp, true);
}
maxL = Math.max(maxL, total);
}
return maxL;
}
}(-1, -1, 2)
]
word = "ABCCED"， ->返回 true,
word = "SEE"，-> 返回 true,
word = "ABCB"， -> 返回 false.
125. 背包问题 II
给出n个物品的体积A[i]和其价值V[i]，将他们装入一个大小为m的背包，最多能装入的总价值有多大？
注意事项
A[i], V[i], n, m均为整数。你不能将物品进行切分。你所挑选的物品总体积需要小于等于给定的m。
样例
对于物品体积[2, 3, 5, 7]和对应的价值[1, 5, 2, 4], 假设背包大小为10的话，最大能够装入的价值为9。
public class Solution {
/*
* @param m: An integer m denotes the size of a backpack
* @param A: Given n items with size A[i]
* @param V: Given n items with value V[i]
* @return: The maximum value
*/
public int backPackII(int m, int[] A, int[] V) {
// write your code
if (A == null || m == 0) {
return 0;
}
boolean[] DP = new boolean[m + 1];
DP[0] = true;
for (int i = 1; i <= A.length; i++) {
for (int j = m; j >= 0; j--) {
if (j - A[i - 1] >= 0 && DP[j - A[i - 1]]) {
DP[j] = true;
}
}
}
for (int j = m; j >= 0; j--) {
if (DP[j]) {
return j;
}
}
return 0;
}
}]
word = "ABCCED"， ->返回 true,
word = "SEE"，-> 返回 true,
word = "ABCB"， -> 返回 false.
127. 拓扑排序
给定一个有向图，图节点的拓扑排序被定义为：
-
对于每条有向边A--> B，则A必须排在B之前
-
拓扑排序的第一个节点可以是任何在图中没有其他节点指向它的节点
找到给定图的任一拓扑排序
注意事项
你可以假设图中至少存在一种拓扑排序
样例
对于下列图：
这个图的拓扑排序可能是：
[0, 1, 2, 3, 4, 5]
或者
[0, 2, 3, 1, 5, 4]
/**
* Definition for Directed graph.
* class DirectedGraphNode {
* int label;
* ArrayList<DirectedGraphNode> neighbors;
* DirectedGraphNode(int x) { label = x; neighbors = new ArrayList<DirectedGraphNode>(); }
* };
*
*
比较特别的BFS.
几个graph的condition：
1. 可能有多个root
2. directed node, 可以direct backwards.
Steps:
Track all neighbors/childrens. 把所有的children都存在map<label, count>里面
先把所有的root加一遍，可能多个root。并且全部加到queue里面。
然后以process queue, do BFS:
Only when map.get(label) == 0, add into queue && rst.
这用map track apperance, 确保在后面出现的node, 一定最后process.
*/
public class Solution {
/*
* @param graph: A list of Directed graph node
* @return: Any topological order for the given graph.
*/
public ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {
// write your code here
ArrayList<DirectedGraphNode> rst = new ArrayList<DirectedGraphNode>();
if (graph == null || graph.size() == 0) {
return graph;
}
// 把所有节点加入hashmap,并记录每个邻居的度数
//Keep track of all neighbors in HashMap
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
for (DirectedGraphNode node : graph) {
// int keyN=node.label;
// map.put(keyN,node.neighbors.size());
for (DirectedGraphNode neighbor : node.neighbors) {
int keyN = neighbor.label;
if (map.containsKey(keyN)) {
map.put(keyN, map.get(keyN) + 1);
} else {
map.put(keyN, 1);
}
}
}
// 加入根节点
//BFS: Add root node. Note:
Queue<DirectedGraphNode> queue = new LinkedList<DirectedGraphNode>();
for (DirectedGraphNode node : graph) {
// if (map.get(node.label)==0) {
// queue.offer(node);
// rst.add(node);
// }
if (!map.containsKey(node.label)) {
queue.offer(node);
rst.add(node);
}
}
// 遍历所有的孩子节点
//BFS: go through all children
while (!queue.isEmpty()) {
DirectedGraphNode node = queue.poll();
for (DirectedGraphNode n : node.neighbors) {
int label = n.label;
map.put(label, map.get(label) - 1);
if (map.get(label) == 0) {
rst.add(n);
queue.offer(n);
}
}
}
return rst;
}
}]
word = "ABCCED"， ->返回 true,
word = "SEE"，-> 返回 true,
word = "ABCB"， -> 返回 false.
129. 重哈希
哈希表容量的大小在一开始是不确定的。如果哈希表存储的元素太多（如超过容量的十分之一），我们应该将哈希表容量扩大一倍，并将所有的哈希值重新安排。假设你有如下一哈希表：
size=3, capacity=4
[null, 21, 14, null]
↓ ↓
9 null
↓
null
哈希函数为：
int hashcode(int key, int capacity) {
return key % capacity;
}
这里有三个数字9，14，21，其中21和9共享同一个位置因为它们有相同的哈希值1(21 % 4 = 9 % 4 = 1)。我们将它们存储在同一个链表中。
重建哈希表，将容量扩大一倍，我们将会得到：
size=3, capacity=8
index: 0 1 2 3 4 5 6 7
hash : [null, 9, null, null, null, 21, 14, null]
给定一个哈希表，返回重哈希后的哈希表。
注意事项
哈希表中负整数的下标位置可以通过下列方式计算：
- C++/Java：如果你直接计算-4 % 3，你会得到-1，你可以应用函数：a % b = (a % b + b) % b得到一个非负整数。
- Python：你可以直接用-1 % 3，你可以自动得到2。
样例
给出 [null, 21->9->null, 14->null, null]
返回 [null, 9->null, null, null, null, 21->null, 14->null, null]
/**
* Definition for ListNode
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
/**
* @param hashTable: A list of The first node of linked list
* @return: A list of The first node of linked list which have twice size
*/
public ListNode[] rehashing(ListNode[] hashTable) {
// write your code here
if (hashTable == null || hashTable.length == 0) {
return hashTable;
}
//Find longest size
/*
int longest = 0;
for (int i = 0; i < hashTable.length; i++) {
ListNode node = hashTable[i];
int count = 0;
while (node != null) {
count++;
node = node.next;
}
longest = Math.max(longest, count);
}*/
//Calculate new capacity
//Just to clarify, this problem asks to double the hashtable size, rather than 'longest' times longer
// 注意hashTable.length=size;capacity=capacity;
int capacity = hashTable.length * 2;
// if (capacity == hashTable.length) {
// return hashTable;
// }
// 结果列表
ListNode[] rst = new ListNode[capacity];
for (int i = 0; i < hashTable.length; i++) {
// 遍历链表
ListNode node = hashTable[i];
while (node != null) {
ListNode newNode = new ListNode(node.val);
int hCode = hashcode(newNode.val, capacity);
// 计算位置上没有数据
if (rst[hCode] == null) {
rst[hCode] = newNode;
} else {
// 有数据加入链表
ListNode move = rst[hCode];
while (move.next != null) {
move = move.next;
}
move.next = newNode;
}
node = node.next;
}
}
return rst;
}
public int hashcode(int key, int capacity) {
if (key < 0) {
return (key % capacity + capacity) % capacity;
} else {
return key % capacity;
}
}
}
(-1, -1, 2)
]
word = "ABCCED"， ->返回 true,
word = "SEE"，-> 返回 true,
word = "ABCB"， -> 返回 false.
130. 堆化
给出一个整数数组，堆化操作就是把它变成一个最小堆数组。
对于堆数组A，A[0]是堆的根，并对于每个A[i]，A [i * 2 + 1]是A[i]的左儿子并且A[i * 2 + 2]是A[i]的右儿子。
说明
什么是堆？
- 堆是一种数据结构，它通常有三种方法：push， pop 和 top。其中，“push”添加新的元素进入堆，“pop”删除堆中最小/最大元素，“top”返回堆中最小/最大元素。
什么是堆化？
- 把一个无序整数数组变成一个堆数组。如果是最小堆，每个元素A[i]，我们将得到A[i * 2 + 1] >= A[i]和A[i * 2 + 2] >= A[i]
如果有很多种堆化的结果？
- 返回其中任何一个。
样例
给出 [3,2,1,4,5]，返回[1,2,3,4,5] 或者任何一个合法的堆数组
public class Solution {
/*
* @param A: Given an integer array
* @return: nothing
Heap用的不多. 得用一下, 才好理解。
通常default 的PriorityQueue就是给了一个现成的min-heap：所有后面的对应element都比curr element 小。
Heapify里面的siftdown的部分：
只能从for(i = n/2-1 ~ 0)， 而不能从for(i = 0 ~ n/2 -1): 必须中间开花，向上跑的时候才能确保脚下是符合heap规则的
Heapify/SiftDown做了什么？
确保在heap datastructure里面curr node下面的两个孩子，以及下面所有的node都遵循一个规律。
比如在这里，若是min-heap,就是后面的两孩子都要比自己大。若不是，就要swap。
还是要记一下min-heap的判断规律:for each element A[i], we will get A[i * 2 + 1] >= A[i] and A[i * 2 + 2] >= A[i].
siftdown时：在curr node和两个son里面小的比较。如果的确curr < son, 搞定，break while.
但若curr 并不比son小，那么就要换位子，而且继续从son的位子往下面盘查。
*/
public void heapify(int[] A) {
// write your code here
if (A == null || A.length == 0) {
return;
}
int son = 0;
int currId = 0;
int leftId = 0;
int rightId = 0;
int n = A.length;
//
for (int i = n/2 - 1; i >= 0; i--) {
currId = i;
while (currId * 2 + 1 < n) {
leftId = currId * 2 + 1;
rightId = currId * 2 + 2;
// 中间的一定比左右孩子小，找左右孩子中最小的一个
if (rightId >= n || A[leftId] <= A[rightId]) {
son = leftId;
} else {
son = rightId;
}
// 不是就交换
if (A[currId] <= A[son]) {
break;
} else {
int temp = A[currId];
A[currId] = A[son];
A[son] = temp;
}
currId = son;
}//end while
}//end for
}
}]
word = "ABCCED"， ->返回 true,
word = "SEE"，-> 返回 true,
word = "ABCB"， -> 返回 false.
135. 数字组合
给出一个候选数字的set(C)和目标数字(T),找到C中所有的组合，使找出的数字和为T。C中的数字可以无限制重复被选取。
例如,给出候选数组[2,3,6,7]和目标数字7，所求的解为：
[7]，
[2,2,3]
注意事项
-
所有的数字(包括目标数字)均为正整数。
-
元素组合(a1, a2, … , ak)必须是非降序(ie, a1 ≤ a2 ≤ … ≤ ak)。
-
解集不能包含重复的组合。
样例
给出候选set[2,3,6,7]和目标数字7
返回 [[7],[2,2,3]]
public class Solution {
/*
* @param candidates: A list of integers
* @param target: An integer
* @return: A list of lists of integers
递归，backtracking. 非常normal。需要先sort.
记得求sum时候也pass 一个sum进去，backtracking一下sum也，这样就不必每次都sum the list了。
题目里面所同一个元素可以用n次，但是，同一种solution不能重复出现。如何handle?
1. 用一个index （我们这里用了start）来mark每次recursive的起始点。
2. 每个recursive都从for loop里面的i开始，而i = start。 也就是，下一个iteration,这个数字会有机会被重复使用。
3. 同时，确定在同一个for loop里面，不同的Index上面相同的数字，不Process两遍。用一个prev 作为checker.
假如[x1, x2, y, z], where x1 == x2， 上面做法的效果:
我们可能有这样的结果: x1,x1,x1,y,z
但是不会有:x1,x2,x2,y,z
两个solution从数字上是一样的，也就是duplicated solution, 要杜绝第二种。
*/
public List<List<Integer>> combinationSum(int[] candidates, int target) {
// write your code here
List<List<Integer>> rst = new ArrayList<List<Integer>>();
List<Integer> list = new ArrayList<Integer>();
if (candidates == null || candidates.length == 0 || target < 0) {
return rst;
}
// 排序
Arrays.sort(candidates);
//
helper(rst, list, candidates, target, 0, 0);
return rst;
}
public void helper(List<List<Integer>> rst, List<Integer> list,int[] num, int target, int sum, int start) {
if (sum == target) {
rst.add(new ArrayList(list));
return;
} else if (sum > target) {//Stop if greater than target
return;
}
int prev = -1;//Repeat detection
for (int i = start; i < num.length; i++) {
if (prev != -1 && prev == num[i]) {
continue;
}
list.add(num[i]);
sum += num[i];
helper(rst, list, num, target, sum, i);
//Back track:
sum -= num[i];
list.remove(list.size() - 1);
//Repeat Detection
prev = num[i];
}
}
}(-1, -1, 2)
]
word = "ABCCED"， ->返回 true,
word = "SEE"，-> 返回 true,
word = "ABCB"， -> 返回 false.
136. 分割回文串
给定一个字符串s，将s分割成一些子串，使每个子串都是回文串。
返回s所有可能的回文串分割方案。
样例
给出 s = "aab"，返回
[
["aa", "b"],
["a", "a", "b"]
]public class Solution {
/*
* @param s: A string
* @return: A list of lists of string
很清楚的DFS Backtracking.
在遍历str的时候，考虑从每个curr spot 到 str 结尾，是能有多少种palindorme? 那就从curr spot当个字符开始算，开始back tracing.
如果所选不是palindrome， 那move on.
若所选的确是palindrome, 加到path里面，DFS去下个level，等遍历到了结尾，这就产生了一种分割成palindrome的串。
每次DFS结尾，要把这一层加的所选palindrome删掉，backtracking嘛。
*/
public List<List<String>> partition(String s) {
// write your code here
List<List<String>> rst = new ArrayList<List<String>>();
if (s == null || s.length() < 0) {
return rst;
}
ArrayList<String> path = new ArrayList<String>();
helper(s, path, 0, rst);
return rst;
}
//Check Palindrome
public boolean isPalindrome(String s){
int start = 0;
int end = s.length() - 1;
while (start < end) {
if (s.charAt(start) != s.charAt(end)) {
return false;
}
start++;
end--;
}
return true;
}
//helper:
public void helper(String s, ArrayList<String> path, int pos,
List<List<String>> rst) {
if (pos == s.length()) {
rst.add(new ArrayList<String>(path));
return;
}
for (int i = pos + 1; i <= s.length(); i++) {//i is used in s.sbustring(pos, i), which can equal to s.length()
String prefix = s.substring(pos, i);
if (!isPalindrome(prefix)) {
continue;
}
path.add(prefix);
helper(s, path, i, rst);
path.remove(path.size() - 1);
}
}
}
(-1, -1, 2)
]
word = "ABCCED"， ->返回 true,
word = "SEE"，-> 返回 true,
word = "ABCB"， -> 返回 false.
137. 克隆图
克隆一张无向图，图中的每个节点包含一个 label 和一个列表 neighbors。
数据中如何表示一个无向图？http://www.lintcode.com/help/graph/
你的程序需要返回一个经过深度拷贝的新图。这个新图和原图具有同样的结构，并且对新图的任何改动不会对原图造成任何影响。
样例
比如，序列化图 {0,1,2#1,2#2,2} 共有三个节点, 因此包含两个个分隔符#。
- 第一个节点label为0，存在边从节点0链接到节点1和节点2
- 第二个节点label为1，存在边从节点1连接到节点2
- 第三个节点label为2，存在边从节点2连接到节点2(本身),从而形成自环。
我们能看到如下的图：
1
/ \
/ \
0 --- 2
/ \
\_/(-1, -1, 2)
]
word = "ABCCED"， ->返回 true,
word = "SEE"，-> 返回 true,
word = "ABCB"， -> 返回 false.
/** * Definition for undirected graph. * class UndirectedGraphNode { * int label; * ArrayList<UndirectedGraphNode> neighbors; * UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); } * }; * * Use HashMap to mark cloned nodes. 先能复制多少Node复制多少。然后把neighbor 加上 */ public class Solution { /* * @param node: A undirected graph node * @return: A undirected graph node */ public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) { // write your code here if (node == null || node.neighbors.size() == 0) { return node; } HashMap<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<UndirectedGraphNode, UndirectedGraphNode>(); Queue<UndirectedGraphNode> queue = new LinkedList<UndirectedGraphNode>(); queue.offer(node); //process each node while (!queue.isEmpty()) { UndirectedGraphNode curr = queue.poll(); UndirectedGraphNode newNode; if (!map.containsKey(curr)) { map.put(curr, new UndirectedGraphNode(curr.label)); } newNode = map.get(curr); //Add neighbors for each node for (UndirectedGraphNode neighbor : curr.neighbors) { UndirectedGraphNode newNeighbor; if (!map.containsKey(neighbor)) { map.put(neighbor, new UndirectedGraphNode(neighbor.label)); } newNeighbor = map.get(neighbor); newNode.neighbors.add(newNeighbor); }//end for }//end while return map.get(node); } } (-1, -1, 2)]
word = "ABCCED"， ->返回 true,
word = "SEE"，-> 返回 true,
word = "ABCB"， -> 返回 false.
139. 最接近零的子数组和
给定一个整数数组，找到一个和最接近于零的子数组。返回第一个和最右一个指数。你的代码应该返回满足要求的子数组的起始位置和结束位置
样例
给出[-3, 1, 1, -3, 5]，返回[0, 2]，[1, 3]， [1, 1]， [2, 2] 或者 [0, 4]。
public class Solution {
/*
* @param nums: A list of integers
* @return: A list of integers includes the index of the first number and the index of the last number
*/
public int[] subarraySumClosest(int[] nums) {
// write your code here
ArrayList<Integer> rst = new ArrayList<Integer>();
if(nums == null || nums.length == 0) {
return rst;
}
if (nums.length == 1) {
rst.add(0); rst.add(0);
return rst;
}
int[][] culmulate = new int[nums.length][2];
culmulate[0][0] = nums[0];
culmulate[0][1] = 0;
for (int i = 1; i < nums.length; i++) {
culmulate[i][0] = culmulate[i - 1][0] + nums[i];
culmulate[i][1] = i;
}
// 排序
Arrays.sort(culmulate, new CustomComparator());
int min = Integer.MAX_VALUE;
int start = 0;
int end = 0;
//
for (int i = 0; i < nums.length - 1; i++) {
int temp = culmulate[i + 1][0] - culmulate[i][0];
// 求最小值，并记录下标
if (temp <= min) {
min = temp;
start = culmulate[i][1];
end = culmulate[i + 1][1];
}
}
// 排序后数组的位置发生了变化，
if (start < end) {
rst.add(start + 1);
rst.add(end);
} else {
rst.add(end + 1);
rst.add(start);
}
return rst;
}
class CustomComparator implements Comparator<int[]> {
public int compare(int[] a, int[] b) {
return Integer.compare(a[0], b[0]);
}
}
}(-1, -1, 2)
]
word = "ABCCED"， ->返回 true,
word = "SEE"，-> 返回 true,
word = "ABCB"， -> 返回 false.
上一篇： 40 - 用栈实现队列
下一篇： tornado 图片上传以及展示