月度归档： 2021年7月

几张卡牌 排成一行，每张卡牌都有一个对应的点数。点数由整数数组 cardPoints 给出。

每次行动，你可以从行的开头或者末尾拿一张卡牌，最终你必须正好拿 k 张卡牌。

你的点数就是你拿到手中的所有卡牌的点数之和。

给你一个整数数组 cardPoints 和整数 k，请你返回可以获得的最大点数。

 

示例 1：

输入：cardPoints = [1,2,3,4,5,6,1], k = 3
输出：12
解释：第一次行动，不管拿哪张牌，你的点数总是 1 。但是，先拿最右边的卡牌将会最大化你的可获得点数。最优策略是拿右边的三张牌，最终点数为 1 + 6 + 5 = 12 。

示例 2：

输入：cardPoints = [2,2,2], k = 2
输出：4
解释：无论你拿起哪两张卡牌，可获得的点数总是 4 。

示例 3：

输入：cardPoints = [9,7,7,9,7,7,9], k = 7
输出：55
解释：你必须拿起所有卡牌，可以获得的点数为所有卡牌的点数之和。

示例 4：

输入：cardPoints = [1,1000,1], k = 1
输出：1
解释：你无法拿到中间那张卡牌，所以可以获得的最大点数为 1 。 

示例 5：

输入：cardPoints = [1,79,80,1,1,1,200,1], k = 3
输出：202

 

提示：

• 1 <= cardPoints.length <= 10^5
• 1 <= cardPoints[i] <= 10^4
• 1 <= k <= cardPoints.length

\n

题解

上手直接开始想象下，k次取牌，那么这k张牌可以分为两个部分，从左边取的left张，和从右边取的right张，且left+right = k

那么接下来就是挨个情况求和，然后求出一个最大值了，假设求得的合为sum,左边求得的合为sum_left，右边求得的合为sum_right，就有sum = sum_left + sum_right。

那么分别分情况来，假设left是每次减一个位置，right是每次加一个位置

第一次，左边left_1个的时候，右边对应right_1个有sum_1 = sum_left_1 + sum_right_1

第二次，左边left_2个的时候，右边对应right_2个有sum_2 = sum_left_2 + sum_right_2

第三次，哦，不是，这时候我们可以看到sum_left_2 = sum_left_1 – 第left_1位的值，sum_right_2 = sum_right_1 + 第right_2位的值

这样基本的模式就可以看出来了，就是窗口模式，如果还没明白的话，试想着将cardPoints 数组首位相连，连接成一个环状，这样是不是就显而易见了。

直接上代码

import java.util.Arrays;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int maxScore(int[] cardPoints, int k) {
        int maxSum = 0;
        //左边全选拉满来一次作为基本值
        for (int i = 0; i < cardPoints.length && i < k; i++) {
            maxSum += cardPoints[i];
        }
        if (k >= cardPoints.length){
            //如果k的值比cardPoints长度长，或者等于长度
            return maxSum;
        }
        //此时左边取了k个，右边取了0个
        //那么继续滑动窗口左边减一个，右边加一个
        int lastSum = maxSum;
        for (int right = 1; right <= k; right++) {
            lastSum = lastSum - cardPoints[k-right] + cardPoints[cardPoints.length-1-(right-1)];
            maxSum = Math.max(maxSum, lastSum);
        }

        return maxSum;
    }
}

既然我们已经用了滑动窗口，那么不妨可以再回来看下这个数组

除去头和尾巴的两段连起来做滑动窗口，其实可以把中间没有选择的cardPoints.length-k张牌作为另一个滑动窗口来看待，那么相对的，就是要求这个滑动窗口取得最大值的时候，再拿所有合减去这个最大的值就是所求目标值

逻辑基本相同的代码省略

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

示例 1:

输入: [1,3,5,6], 5
输出: 2

示例 2:

输入: [1,3,5,6], 2
输出: 1

示例 3:

输入: [1,3,5,6], 7
输出: 4

示例 4:

输入: [1,3,5,6], 0
输出: 0

\n

题解

把头尾情况单独处理了去掉，剩下的用二分法无限逼近目标位置，得到left的值

之后再再小区间内做个遍历循环，二分法本身应该是有办法可以取到准确的目标位置的，但是这个里面边界判断的情况实在是有点头疼，于是就取个巧，最终位置无限逼近之后，再前后扩展一位进行大小判断

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public static int searchInsert(int[] nums, int target) {
        //请在此作答
        if(null==nums || nums.length == 0 || target < nums[0] || nums[0] == target){
            return 0;
        }
        if (nums[nums.length-1] == target){
            return nums.length-1;
        }
        if (nums[nums.length-1] < target){
            return nums.length;
        }
        int left = 0;
        int right = nums.length-1;

        while (left < right){
            int mid = left + (right-left)/2;
            if (nums[mid] == target){
                return mid;
            }
            if (nums[mid] > target){
                right = mid-1;
            }else{
                left = mid+1;
            }

        }
        for (int i = left-1; i <= left+1; i++) {
            if (i<0 || i>= nums.length){
                continue;
            }
            if (nums[i] == target){
                return i;
            }
            if (nums[i] < target && nums[i+1] > target){
                return i+1;
            }
        }

        return left;



    }
}
//leetcode submit region end(Prohibit modification and deletion)

给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，在字符串中增加空格来构建一个句子，使得句子中所有的单词都在词典中。返回所有这些可能的句子。

说明：

• 分隔时可以重复使用字典中的单词。
• 你可以假设字典中没有重复的单词。

示例 1：

输入:
s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
输出:
[
  "cats and dog",
  "cat sand dog"
]

示例 2：

输入:
s = "pineapplepenapple"
wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
输出:
[
  "pine apple pen apple",
  "pineapple pen apple",
  "pine applepen apple"
]
解释: 注意你可以重复使用字典中的单词。

示例 3：

输入:
s = "catsandog"
wordDict = ["cats", "dog", "sand", "and", "cat"]
输出:
[]

\n

题解

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    private List<String> res = new ArrayList<>();
    private HashSet<String> hashSet;
    private String testString;

    public List<String> wordBreak(String s, List<String> wordDict) {
        char[] chars = s.toCharArray();
        hashSet = new HashSet<>(wordDict);
        testString = s;
        List<String> stringList = new ArrayList<>();
        traceback(0,stringList);
        return res;
    }


    /**
     * 回溯模板
     * 这里的边界需要仔细考虑下。不过可以套个简单的方法
     * 假如字符串长度为1，那么截取的话应该是从index=0，截取到index=1
     * 所以最终的终止位置应该是和字符串的长度一致的
     */
    private void traceback(int startPosition,List<String> stringList){
        if (startPosition == testString.length()){
            res.add(listToString(stringList));
        }
        for (int endPosition = startPosition+1;endPosition<= testString.length();endPosition++){
            String subString = testString.substring(startPosition,endPosition);
//            System.out.println(subString);
            if (!hashSet.contains(subString)){
                continue;
            }
            stringList.add(subString);
            //向下嵌套
            traceback(endPosition,stringList);
            //退一次操作
            stringList.remove(stringList.size()-1);
        }
    }


    /**
     * 数组转换字符串的方法
     * @param stringList
     * @return
     */
    private String listToString(List<String> stringList){
        StringBuilder sb = new StringBuilder();
        for (String str: stringList){
            if (sb.length()>0){
                sb.append(" ");
            }
            sb.append(str);
        }
        return sb.toString();
    }

}
//leetcode submit region end(Prohibit modification and deletion)