Posted on | In , |
Words count in article: 214 | Reading time ≈ 1

Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

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

Note:

All numbers (including target) will be positive integers.

The solution set must not contain duplicate combinations.

Example 1:

1
2
3
4
5
6
Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
  [7],
  [2,2,3]
]

Example 2:

1
2
3
4
5
6
7
Input: candidates = [2,3,5], target = 8,
A solution set is:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        comb(result, candidates, 0, new ArrayList<Integer>(), target);
        return result;
    }
    public void comb(List<List<Integer>> result, int[] candidates, int minIndex, List<Integer> path, int target)
    {
        if(target < 0)
            return;
        else if(target == 0)
            result.add(path);
        else
        {
            for(int i=minIndex; i<candidates.length; i++)
            {
                List<Integer> newPath = new ArrayList(path);
                newPath.add(candidates[i]);
                comb(result, candidates, i, newPath, target-candidates[i]);
            }
        }
            
    }
}

Posted on | In , |
Words count in article: 563 | Reading time ≈ 2

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Example 1:

1
2
Input: [1,3,4,2,2]
Output: 2

Example 2:

1
2
Input: [3,1,3,4,2]
Output: 3

Note:

  • You must not modify the array (assume the array is read only).
  • You must use only constant, O(1) extra space.
  • Your runtime complexity should be less than O(n2).
  • There is only one duplicate number in the array, but it could be repeated more than once.
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int findDuplicate(int[] nums) {
        Arrays.sort(nums);
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nums[i-1]) {
                return nums[i];
            }
        }

        return -1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int findDuplicate(int[] nums) {
        Set<Integer> seen = new HashSet<Integer>();
        for (int num : nums) {
            if (seen.contains(num)) {
                return num;
            }
            seen.add(num);
        }

        return -1;
    }
}

链表闭环判断（Floyd’s Tortoise and Hare）

给定一个链表，返回环路开始节点，如果没有则返回空。

Floyd算法分为两个不同的阶段。第一个阶段是判断在链表中是否有环路，如果不存在就马上返回空，也就不存在第二阶段。第二个阶段就是找到环路的入口。

第一阶段

在这里，我们初始化两个指针-快的hare和慢的tortoise。接下来，hare和tortoise从同一个节点出发（头节点），tortoise每次走一个节点，hare每次走两个节点。如果他们在前进若干步后在同一个节点相遇，我们就返回这个节点，如果最终没有返回节点信息，而是返回空，则代表不存在环路。

第二阶段

由于第一阶段确定了有环路，第二阶段就是找环的入口节点。接下来初始化连个指针，ptr1：它指向头节点， ptr2：指向第一阶段找到的相遇节点。然后将他们以一次移动一个节点的速度向前移动，直到他们再次相遇为止，并返回这个节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int findDuplicate(int[] nums) {
        // Find the intersection point of the two runners.
        int tortoise = nums[0];
        int hare = nums[0];
        do {
            tortoise = nums[tortoise];//走一步
            hare = nums[nums[hare]];//走两步
        } while (tortoise != hare);

        // Find the "entrance" to the cycle.
        int ptr1 = nums[0];
        int ptr2 = tortoise;
        while (ptr1 != ptr2) {
            ptr1 = nums[ptr1];//走一步
            ptr2 = nums[ptr2];//走一步
        }

        return ptr1;
    }
}

Posted on | In , |
Words count in article: 111 | Reading time ≈ 1

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

Example 1:

1
2
3
4
5
6
Input: [3,2,3]
Output: 3
Example 2:

Input: [2,2,1,1,1,2,2]
Output: 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int majorityElement(int[] nums) {
        int n = nums.length, m = nums[0], c = 1;
        
        for(int i=1; i<n; i++)
        {
            if(nums[i] == m)
                c++;
            else if(c > 0)
                c--;
            else
            {
                m = nums[i];
                c = 1;
            }
        }
        return m;
    }
}

Posted on | In , |
Words count in article: 342 | Reading time ≈ 2

Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements of [1, n] inclusive that do not appear in this array.

Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.

Example:

1
2
3
4
5
Input:
[4,3,2,7,8,2,3,1]

Output:
[5,6]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> ret = new ArrayList<Integer>();
        
        for(int i=0; i<nums.length; i++)
        {
            int val = Math.abs(nums[i]) - 1;
            if(nums[val] > 0)
                    nums[val] = -nums[val];
        }
        
        for(int i=0; i<nums.length; i++)
        {
            if(nums[i] > 0)
                ret.add(i+1);
        }
        
        return ret;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Take input [4.3.2.7.8.2.3.1] as an example, by subtracting 1 it becomes [3.2.1.6.7.1.2.0] which is an array of index.
For the first iteration
when i = 0 , it marks the nums[3] as negative, the array become [4.3.2.-7.8.2.3.1].
when i = 1, it marks the nums[2] as negative, the array become [4.3.-2.-7.8.2.3.1].
when i = 2, it marks the nums[1] as negative, the array become [4.-3.-2.-7.8.2.3.1].
when i = 3, it marks the nums[6] as negative, the array become [4.-3.-2.-7.8.2.-3.1].
...
...
when i = 6, it marks the nums[0] as negative, the array become [-4.-3.-2.-7.8.2.-3.-1].

For the second iteration
find nums[4] = 8 and nums[5] = 2 which > 0;
which means 4 and 5 are not in the index array[3.2.1.6.7.1.2.0].
by adding 1, 5 and 6 are not in the input[4.3.2.7.8.2.3.1]
return[5.6]

Posted on | In , |
Words count in article: 103 | Reading time ≈ 1

Given an array nums, write a function to move all 0’s to the end of it while maintaining the relative order of the non-zero elements.

Example:

1
2
Input: [0,1,0,3,12]
Output: [1,3,12,0,0]

Note:

You must do this in-place without making a copy of the array.
Minimize the total number of operations.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public void moveZeroes(int[] nums) {
        int zero = 0, l = 0, r = nums.length;
        while(l < r)
        {
            if(nums[l] != 0)
            {
                int tmp = nums[zero];
                nums[zero++]  =  nums[l];
                nums[l] = tmp;
            }
            l++;
        }
    }
}

Posted on | In , |
Words count in article: 139 | Reading time ≈ 1

Given a set of distinct integers, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

1
2
3
4
5
6
7
8
9
10
11
12
Input: nums = [1,2,3]
Output:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> ret = new ArrayList<>();
        dfs(nums, 0, new ArrayList<>(), ret);
        return ret;
    }
    
    void dfs(int[] nums, int idx, List<Integer> path, List<List<Integer>> ret)
    {
        ret.add(path);
        for(int i=idx; i<nums.length; i++)
        {
            List<Integer> p = new ArrayList<>(path);
            p.add(nums[i]);
            dfs(nums, i+1, p, ret);
        }
    }
}

Posted on | In , |
Words count in article: 146 | Reading time ≈ 1

Given an array nums of n integers where n > 1, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Example:

1
2
Input:  [1,2,3,4]
Output: [24,12,8,6]

Note: Please solve it without division and in O(n).

Follow up:
Could you solve it with constant space complexity? (The output array does not count as extra space for the purpose of space complexity analysis.)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] answer = new int[nums.length];
        int length = nums.length;
        
        answer[0] = 1;
        for(int i=1; i<length; i++)
        {
            answer[i] = nums[i-1] * answer[i-1];
        }
        
        int R=1;
        
        for(int i=length-1; i>=0; i--)
        {
            answer[i] = answer[i] * R;
            R *= nums[i];
        }
        
        return answer;
    }
}

Posted on | In , |
Words count in article: 200 | Reading time ≈ 1

Given a non-empty array of integers, return the k most frequent elements.

1
2
3
4
5
6
7
8
Example 1:

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
Example 2:

Input: nums = [1], k = 1
Output: [1]

Note:

You may assume k is always valid, 1 ≤ k ≤ number of unique elements.

Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        
        for(int i=0; i<nums.length; i++)
            map.put(nums[i], map.containsKey(nums[i]) ? map.get(nums[i]) + 1 : 1);
        
        List<Map.Entry<Integer, Integer>> list = new LinkedList<>(map.entrySet());
        
        Collections.sort(list, new Comparator<Map.Entry<Integer, Integer>>(){
           public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2){
               return o2.getValue().compareTo(o1.getValue());
           }
        });
        
        List<Integer> res = new ArrayList<>();
        for(int i=0; i<k; i++)
            res.add((Integer) list.get(i).getKey());
        return res;
    }
}

Posted on | In , |
Words count in article: 121 | Reading time ≈ 1

Reverse a singly linked list.

Example:

1
2
Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

Follow up:

A linked list can be reversed either iteratively or recursively. Could you implement both?

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null)
            return head;
        ListNode prev = null;
        ListNode curr = head;
        prev = new ListNode(curr.val);
        curr = curr.next;
        while(curr != null)
        {
            ListNode temp = new ListNode(curr.val);
            temp.next = prev;
            prev = temp;
            curr = curr.next;
        }
        return prev;
    }
}

Posted on | In , |
Words count in article: 164 | Reading time ≈ 1

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:

1
2
3
4
5
6
7
[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

DFS 回溯的味道

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
class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<String>();
        Stack<String> stack = new Stack<String>();
        Stack<int[]> gen = new Stack<int[]>();
        stack.push("");
        gen.push(new int[]{n, 0});
        while(!stack.isEmpty())
        {
            String s = stack.pop();
            int open = gen.peek()[0];
            int close = gen.pop()[1];
            
            if(open == 0 && close == 0)
                result.add(s);
            if(open > 0)
            {
                stack.push(s + "(");
                gen.push(new int[]{open - 1, close + 1});
            }
            if(close > 0)
            {
                stack.push(s + ")");
                gen.push(new int[]{open,close - 1});
            }
        }
        return result;
    }
}