已经放假一个礼拜了,这个礼拜刷 Leetcode 还是以找一些感觉为主,都是 Leetcode 上 pick one 做的简单题和中等难度的题

611. Valid Triangle Number

Given an array consists of non-negative integers, your task is to count the number of triplets chosen from the array that can make triangles if we take them as side lengths of a triangle.
Example 1:

Input: [2,2,3,4]
Output: 3
Explanation:
Valid combinations are:
2,3,4 (using the first 2)
2,3,4 (using the second 2)
2,2,3

Note:
The length of the given array won't exceed 1000.
The integers in the given array are in the range of [0, 1000].

暴力

循环取数组中的三条边,判断是否满足构成三角形,若满足 count++

class Solution {
    public int triangleNumber(int[] nums) {
        int count = 0;
		for (int i = 0; i < nums.length - 2; i++) {
			for (int j = i + 1; j < nums.length - 1; j++) {
				for (int k = j + 1; k < nums.length; k++) {
					if (nums[i] + nums[j] > nums[k] && nums[i] + nums[k] > nums[j] && nums[j] + nums[k] > nums[i]) {
						count++;
					}
				}
			}
		}
		return count;
    }
}

二分查找

对数组排序,前两条边用循环,第三条边根据三角形构造规则使用二分查找找对最大的那个符合条件的值,count加上对应的个数

class Solution {
    static int binarySearch(int[] nums, int l, int r, int x) {
		while (r >= l && r < nums.length) {
			int mid = (l + r) / 2;
			if (nums[mid] >= x)
				r = mid - 1;
			else
				l = mid + 1;
		}
		return l;
	}
	public static int triangleNumber(int[] nums) {
		int count = 0;
		Arrays.sort(nums);
		for (int i = 0; i < nums.length - 2; i++) {
			int k = i + 2;
			for (int j = i + 1; j < nums.length - 1 && nums[i] != 0; j++) {
				k = binarySearch(nums, k, nums.length - 1, nums[i] + nums[j]);
				count += k - j - 1;
			}
		}
		return count;
	}
}

674. Longest Continuous Increasing Subsequence

My solution

因为是要连续,所以直接 O(n) 的循环比较前后两个大小即可

class Solution {
    public int findLengthOfLCIS(int[] nums) {
        if (nums.length == 0) {
			return 0;
		}
		int count = 1;
		int maxCount = 1;
		for (int i = 0; i < nums.length - 1; i++) {
			if (nums[i] < nums[i+1]) {
				count++;
			} else {
				maxCount = Math.max(count, maxCount);
				count = 1;
			}
		}
		return Math.max(count, maxCount);
    }
}

342. Power of Four

My Solution

按照我的这个做法,有很多需要考虑的条件,因此我在不断 Wrong Answer 后加上一些限制条件才过了这道题。

class Solution {
    public boolean isPowerOfFour(int num) {
        if (num == 0) {
            return false;
        }
        while(num != 1) {
			if (num % 4 != 0 || num == -1) {
				return false;
			}
			num = num / 4;
			
		}
		return true;
    }
}

One line

 public boolean isPowerOfFour(int num) {
        return num > 0 && (num&(num-1)) == 0 && (num & 0x55555555) != 0;
        //0x55555555 is to get rid of those power of 2 but not power of 4
        //so that the single 1 bit always appears at the odd position 
    }

287. Find the Duplicate Number

My Solution

对数组排序,若前后有相等的情况,则返回该数

class Solution {
    public int findDuplicate(int[] nums) {
        Arrays.sort(nums);
		for (int i = 0; i < nums.length - 1; i++) {
			if (nums[i] == nums[i+1]) return nums[i];
		}
		return 0;
    }
}

时间复杂度:Arrays.sort 的时间复杂度为 nlogn

集合

因为集合中的元素是唯一的,每读入一个元素,放到集合中,若之后的已经存在在这个集合中,则重复,输出

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;
    }
}

虽然时间复杂度为 O(n) 但是不知道为啥 leetcode 的时间比我的那个方法还慢??

896. Monotonic Array

My Solution

class Solution {
    public boolean isMonotonic(int[] A) {
        if (A.length <= 1) return true;
        boolean isSet = false;
        boolean isUp = false;
        for (int i = 0; i < A.length - 1; i++) {
            if (!isSet && A[i] < A[i+1]) {
                isSet = true;
                isUp = true;
            } else if (!isSet && A[i] > A[i+1]) {
                isSet = true;
                isUp = false;
            } else if ((isSet && isUp && A[i] > A[i+1]) || (isSet && !isUp && A[i] < A[i+1])) {
                return false;
            }
        }
        return true;
    }
}

860. Lemonade Change

My Solution

class Solution {
    public boolean lemonadeChange(int[] bills) {
        int five = 0;
        int ten = 0;
        int twen = 0;
        for (int i = 0; i < bills.length; i++) {
            if (bills[i] == 5) {
                five++;
            } else if (bills[i] == 10) {
                if (five == 0) {
                    return false;
                }
                five--;
                ten++;
            } else if (bills[i] == 20) {
                if ((ten == 0 && five <3) || (ten > 0 && five == 0)) {
                    return false;
                }
                if (ten != 0) {
                    ten--;
                    five--;
                    twen++;
                } else {
                    five -= 3;
                    twen++;
                }
            }
        }
        return true;
    }
}