Combination Sum III leetcode

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

Ensure that numbers within the set are sorted in ascending order.

Example 1:

Input: k = 3, n = 7

Output:

[[1,2,4]]

Example 2:

Input: k = 3, n = 9

Output:

[[1,2,6], [1,3,5], [2,3,4]]

public class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if (k <= 0) {
            return res;
        }
        List<Integer> tem = new ArrayList<Integer>();
        helper(res, tem, k, n, 1, 0, 0);
        return res;
    }
    public void helper(List<List<Integer>> res, List<Integer> tem, int k, int n, int pos, int sum, int count) {
        if (sum == n && count == k) {
            res.add(new ArrayList<Integer>(tem));
            return;
        }

        for (int i = pos; i <= 9; i++) {
            tem.add(i);
            helper(res, tem, k, n, i + 1, sum + i, count+1);
            tem.remove(tem.size() - 1);
        }
    }
}

Kth Largest Element in an Array leetcode

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

For example,
Given [3,2,1,5,6,4] and k = 2, return 5.
用quick selecte的方法

//pivot为left
public class Solution {
    public int findKthLargest(int[] nums, int k) {
        return find(nums, 0, nums.length - 1, nums.length - k);
    }
    public int find (int[] nums, int i, int j, int k) {
        int left = i;
        int right = j;
        int pivot = nums[left];
        while (left < right) {//为< 不是<=
            while (left < right && nums[right] > pivot) {//必须先right--
                right--;
            }
            while (left < right && nums[left] <= pivot) {
                left++;
            }
            
            swap(nums, left, right);
            
        }
        swap(nums,right, i);
        if (left == k) {
            return nums[k];
        } else if (left < k) {
            return find(nums, left + 1, j, k);
        } else {
            return find(nums, i, left - 1, k);
        }
    }
    public void swap(int[] nums, int i, int j) {
        int tem = nums[i];
        nums[i] = nums[j];
        nums[j] = tem;
    }
}
//pivot为right
public class Solution {
    public int findKthLargest(int[] nums, int k) {
        return find(nums, 0, nums.length - 1, nums.length - k);
    }
    public int find (int[] nums, int i, int j, int k) {
        int left = i;
        int right = j;
        int pivot = nums[right];
        while (left < right) {
            while (left < right && nums[left] < pivot) {//右pivot时候先左边 反之亦然
                left++;
            }
            while (left < right && nums[right] >= pivot) {
                right--;
            }
            if (left < right) {//此判定可有可无, 因为不会出现left> right情况
                swap(nums, left, right);
            }
            
        }
        swap(nums,left, j);
        if (left == k) {
            return nums[k];
        } else if (left < k) {
            return find(nums, left + 1, j, k);
        } else {
            return find(nums, i, left - 1, k);
        }
    }
    public void swap(int[] nums, int i, int j) {
        int tem = nums[i];
        nums[i] = nums[j];
        nums[j] = tem;
    }
}

Priority Queue的解法

public class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> queue = new PriorityQueue<Integer>();
        for (int i : nums) {
            queue.offer(i);
        }
        for (int i = 0; i < nums.length - k ; i++) {
            queue.poll();
        }
        return queue.peek();
    }
}

House Robber II leetcode

Note: This is an extension of House Robber.

After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

第一次去掉第一家保留最后一家 第二次去掉最后一家保留第一家, 计算能抢得最大值, 然后拿结果比较取最大的.

public class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        } else if (nums.length == 1) {
            return nums[0];
        } else if (nums.length == 2) {
            return Math.max(nums[0], nums[1]);
        }
        //include the first one
        int[] dp = new int[nums.length];
        dp[0] = 0;
        dp[1] = nums[0];
        for (int i = 2; i < nums.length; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
        }
        //include the last one
        int [] dr = new int[nums.length];
        dr[0] = 0;
        dr[1] = nums[1];
        for (int i = 2; i < nums.length; i++) {
            dr[i] = Math.max(dr[i - 1], dr[i - 2] + nums[i]);
        }
        return Math.max(dp[nums.length - 1], dr[nums.length - 1]);
    }
}

Minimum Size Subarray Sum leetcode

Given an array of n positive integers and a positive integer s, find the minimal length of a subarray of which the sum ≥ s. If there isn't one, return 0 instead.

For example, given the array [2,3,1,2,4,3] and s = 7,
the subarray [4,3] has the minimal length under the problem constraint.

用滑动窗口的做法

public class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int left = 0;
        int right = 0;
        int sum = 0;
        int min = Integer.MAX_VALUE;
        while (right < nums.length) {
            sum += nums[right];
            while (sum >= s) {
                sum -= nums[left];
                min = Math.min(min, right - left + 1);
                left++;
            }
            right++;
        }
        if (min == Integer.MAX_VALUE) {
            return 0;
        } else {
            return min;
        }
        
    }
}

Isomorphic Strings

Given two strings s and t, determine if they are isomorphic.

Two strings are isomorphic if the characters in s can be replaced to get t.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.

For example,
Given "egg", "add", return true.

Given "foo", "bar", return false.

Given "paper", "title", return true.

public class Solution {
    public boolean isIsomorphic(String s, String t) {
        if (s == null && t == null) {
            return true;
        } else if (s == null || t == null) {
            return false;
        } else if (s.length() != t.length()) {
            return false;
        }
        HashMap<Character, Character> map1 = new HashMap<Character, Character>();
        HashMap<Character, Character> map2 = new HashMap<Character, Character>();
        for (int i = 0; i < s.length(); i++) {
            char c1 = s.charAt(i);
            char c2 = t.charAt(i);
            if (map1.containsKey(c1)) {
                if (map1.get(c1) != c2) {
                    return false;
                }
            }
            if (map2.containsKey(c2)) {
                if (map2.get(c2) != c1) {
                    return false;
                }
            }
            map1.put(c1, c2);
            map2.put(c2, c1);
        }
        return true;
    }
}

Count Primes leetcode

Description:

Count the number of prime numbers less than a non-negative number, n.

厄拉多塞筛法(Sieve of Eeatosthese):
从第一个质数开始 把所有他的倍数都去掉, 那么下一个没有被去掉的肯定是质数, 依次循环到sqrt(n)

public class Solution {
    public int countPrimes(int n) {
        if(n <= 2) {
            return 0;
        }
        boolean[] map = new boolean[n];
        for (int i = 2; i <= Math.sqrt(n); i++) {
            //如果n=100, 那么只需要递加到10就可以, 之后的11* 11 > 100, 而11*(2到10)都已经在2到10时候剪去过了
            if (map[i] == false) {
                for (int j = i + i; j < n; j += i) {
                    map[j] = true;
                }
            }
        }
        int count = 0;
        for (int i = 2; i < n; i++) {
            if (map[i] == false) {
                count++;
            } 
        }
        return count;
    }
}

Happy Number leetcode

Write an algorithm to determine if a number is "happy".

A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.

Example: 19 is a happy number

• 12 + 92 = 82
• 82 + 22 = 68
• 62 + 82 = 100
• 12 + 02 + 02 = 1

public class Solution {
    public boolean isHappy(int n) {
        HashSet<Integer> set = new HashSet<Integer>();
        while (!set.contains(n)) {
            set.add(n);
            int newn = 0;
            while (n != 0) {
                newn += (n % 10) * (n % 10);//注意要有()
                n /= 10;
            }
            if (newn == 1) {
                return true;
            } else {
                n = newn;
            }
        }
        return false;
    }
}