刷题记录帖

刷题
每天至少三道 找到手感

33. Search in Rotated Sorted Array
class Solution {
    public int search(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int start = 0;
        int end = nums.length - 1;
        while (start <= end) {
            int mid = (start + end) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[start] == target) {
                return start;
            }
            if (nums[mid] >= nums[start]) {
                if (target <= nums[mid] && target >= nums[start]) {
                    end = mid - 1;
                }else {
                    start = mid + 1;
                }
            } else {
                if (target >= nums[mid] && nums[start] >= target) {
                    start = mid + 1;
                } else {
                    end = mid -1 ;
                }
            }
        }
         return -1;
    }
}

2018.12.01
265. Paint House II
256. Paint House
class Solution {
    public int minCostII(int[][] costs) {
                if (costs == null || costs.length == 0) {
            return 0;
        }
        int min = 0;
        int min_sec = 0;
        int index = -1;
        for (int i = 0; i < costs.length; i++) {
            int currentMin = Integer.MAX_VALUE;
            int currentSecMin = Integer.MAX_VALUE;
            int currentIndex = -1;
            for (int j =0; j < costs[0].length; j++) {
                costs[i][j] += (j != index? min: min_sec);
                if (costs[i][j] < currentMin) {
                    currentSecMin = currentMin;
                    currentMin = costs[i][j];
                    currentIndex = j;
                } else if (costs[i][j] < currentSecMin) {
                    currentSecMin = costs[i][j];
                }
            }
            min  = currentMin;
            min_sec = currentSecMin;
            index = currentIndex;
        }
        return min;
    }
}


两题解法通用，动态规划， 记住前一个第二小

class Solution {
    public int rob(int[] nums) {
        /*
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int[] dp = new int[nums.length + 1];
        dp[0] = 0;
        dp[1] = nums[0];
        for (int i = 2; i < nums.length + 1; i++) {
            dp[i] = Math.max(dp[i - 2] + nums[i -1], dp[i - 1]);
        }
        return dp[nums.length];
        */
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        int max = nums[0];
        int previousMax = 0;
        for (int i = 1; i < nums.length; i++) {
            int currentMax = Math.max(max, nums[i] + previousMax);
            previousMax = max;
            max = currentMax;
        }
        return max;
    }
}

11。30.2018  152. Maximum Product Subarray
class Solution {
    public int maxProduct(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int max_current = nums[0];
        int min_current = nums[0];
        int max = nums[0];
        for (int i = 1; i < nums.length; i++) {
            int max_here = Math.max(Math.max(max_current * nums[i], min_current * nums[i]), nums[i]);
            int min_here = Math.min(Math.min(max_current * nums[i], min_current * nums[i]), nums[i]);

            max_current = max_here;
            min_current = min_here;

            max = Math.max(max, max_current);
        }
        return max;
    }
}

用户1234 发表于 2018-11-30 16:29
11。30.2018  152. Maximum Product Subarray
class Solution {
    public int maxProduct(int[] nums)  ...

198. House Robber
lass Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int max = 0;
        int rob = 0;
        int notRob = 0;
        for (int i = 0; i < nums.length; i++) {
            int currentRob = notRob + nums[i];
            notRob = Math.max(notRob, rob);
            rob = currentRob;
        }
        return Math.max(rob, notRob);
    }
}

221. Maximal Square
class Solution {
    public int maximalSquare(char[][] matrix) {
        if(matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }
        int[][] dp = new int[matrix.length + 1][matrix[0].length + 1];
        int max = 0;
        for (int i = 1; i < matrix.length + 1; i++) {
            for (int j = 1; j < matrix[0].length + 1; j++) {
                if (matrix[i - 1][j - 1] == '1') {
                     //思考这一步怎么得出来的
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                    max = Math.max(dp[i][j], max);
                }
               
            }
        }
        return max * max;
    }
}

213. House Robber II
class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        if (nums.length == 1) {
            return nums[0];
        }
        return Math.max(rob1(nums, 0, nums.length - 1),
                        rob1(nums, 1, nums.length));
    }
    public int rob1(int[] nums, int start , int end) {
        if (start >= end) {
            return 0;
        }
        int max = nums[start];
        int previousMax = 0;
        for (int i = start + 1; i < end; i++) {
            int currnet = Math.max(max, previousMax + nums[i]);
             previousMax = max;
             max = currnet;
        }
        return max;
    }
}

121. Best Time to Buy and Sell Stock
class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length < 2) {
            return 0;
        }
        int max = 0;
        int minPrice = prices[0];
        for (int i = 1; i < prices.length; i++) {
            max = Math.max(max, prices[i] - minPrice);
            minPrice = Math.min(minPrice, prices[i]);
        }
        return max;
    }
}

122. Best Time to Buy and Sell Stock II
class Solution {
    public int maxProfit(int[] prices) {
        int max = 0;
        for (int i = 1; i < prices.length; i++) {
            max = prices[i] > prices[i - 1]? max + prices[i] - prices[i - 1] : max;
        }
        return max;
    }
}

像楼主学习！！