和为s的连续正数序列

剑指 Offer 57 - II. 和为s的连续正数序列 - 力扣（Leetcode）

题目要求

输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。

序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。

例子：

1
2
3
4
5
输入：target = 9
输出：[[2,3,4],[4,5]]
    
输入：target = 15
输出：[[1,2,3,4,5],[4,5,6],[7,8]]

提示：

1 <= target <= 10^5

思路分析

滑动窗口

  • 定义i和j两个指针，同时从下标为0的位置开始，现在滑动窗口只有一个值；
  • 若当前窗口内的值小于target，就将j++；窗口每移动一次就进行判断；
  • 若当前窗口内的值大于target，就将i++；窗口每移动一次就进行判断；
  • 若当前窗口内的值等于target，就将窗口内所有的值保存起来；

代码实现

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
30
31
32
33
class Solution {
    public int[][] findContinuousSequence(int target) {
        // 定义一个集合
        List<int[]> res = new ArrayList<>();
        int i = 1, j = 1; // 两个指针
        int sum = 1; // 窗口的和
        while(i <= target / 2){
            if(sum < target){
                j++;
                sum = sum + j;
            }else if(sum > target){
                sum = sum - i;
                i++;
            }else{
                // 找到目标值，定义数组
                int[] temp = new int[j - i +1];
                int index = 0; // 记录下标
                for(int k = i ; k <= j;k++){
                    temp[index++] = k;
                }
                // 优化速度
                sum = sum - i;
                i++;
                j++;
                sum = sum + j;
                // 将temp加入到集合
                res.add(temp);
            }
        }
        // 将集合转换为二维数组返回
        return res.toArray(new int[res.size()][]);
    }
}

翻转单词顺序

剑指 Offer 58 - I. 翻转单词顺序 - 力扣（Leetcode）

题目要求

输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串"I am a student. “，则输出"student. a am I”。

例子：

1
2
3
4
5
6
7
8
9
10
输入: "the sky is blue"
输出: "blue is sky the"
    
输入: "  hello world!  "
输出: "world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
    
输入: "a good   example"
输出: "example good a"
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个

提示：

  • 无空格字符构成一个单词。
  • 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
  • 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

思路分析

从后先前，将单词拆分开，然后进行反转即可；

代码实现

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
class Solution {
    public String reverseWords(String s) {
        // 特殊情况
        if(s == null || s.length() <= 0){
            return s;
        }
        // 删除左右两端的空格
        s = s.trim();
        // 定义StringBuilder，进行拼接
        StringBuilder builder = new StringBuilder();
        int i = s.length() - 1, j = i;
        // 循环处理
        while(i >= 0){
            // 当i>=0且值不为空格
            while(i >= 0 && s.charAt(i) != ' ') i--;
            // [i+1,i]组成一个单词
            // subString取的是开区间，所以j+1
            builder.append(s.substring(i+1,j+1) + " ");
            // 排除空格
            while(i >= 0 && s.charAt(i) == ' ') i--;
            j = i;
        }
        // 返回并排除左右两端空格
        return builder.toString().trim();
    }
}

左旋转字符串

剑指 Offer 58 - II. 左旋转字符串 - 力扣（Leetcode）

题目要求

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。

例子：

1
2
3
4
5
输入: s = "abcdefg", k = 2
输出: "cdefgab"
    
输入: s = "lrloseumgh", k = 6
输出: "umghlrlose"

提示：

1 <= k < s.length <= 10000

思路分析

使用StringBuilder进行拼接，先将k之后的部分拼接，然后再将k之前的拼接到后面即可；

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public String reverseLeftWords(String s, int n) {
        // 定义StringBuilder
        StringBuilder builder = new StringBuilder();
        // 定义字符串长度
        int len = s.length();
        // 先拼接n后面的部分
        for(int i = n; i < len; i++){
            builder.append(s.charAt(i));
        }
        // 拼接n前面的部分
        for(int i=0; i< n; i++){
            builder.append(s.charAt(i));
        }
        // 返回
        return builder.toString();
    }
}

滑动窗口的最大值

剑指 Offer 59 - I. 滑动窗口的最大值 - 力扣（Leetcode）

题目要求

给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。

例子：

1
2
3
4
5
6
7
8
9
10
11
12
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7] 
解释: 

  滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

提示：

你可以假设 k 总是有效的，在输入数组 不为空 的情况下，1 ≤ k ≤ nums.length。

思路分析

队列

  • 新建一个队列，通过不断扩大滑动窗口，每当滑动窗口出现一个值，就将它与队列顶部的元素进行比较，如果新的值比队列顶部的值大，就将队列的值都出队，然后将新的值放入队列；
  • 如果比队列顶部值小，就将它加入到队列里；
  • 当我们不断滑动窗口，还需要判断队列顶部的值是否还在窗口内，如果不在需要把它出队；
  • 当滑动窗口达到最大值，就将队列顶部元素保存，每次滑动窗口移动，队列顶部的值若发生改变，也将其保存；

代码实现

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
30
31
32
33
34
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        // 特殊情况
        if(nums == null || nums.length <= 1){
            return nums;
        }
        // 定义一个队列
        LinkedList<Integer> queue = new LinkedList<>();
        // 定义数组保存结果
        int[] res = new int[nums.length - k +1];
        int index = 0;

        // 循环遍历
        for(int i=0;i<nums.length;i++){
            // 若队列不为空，且队列顶部的元素小于当前遍历的元素
            while(!queue.isEmpty() && nums[queue.peekLast()] <= nums[i]){
                // 将队列所有值出队
                queue.pollLast();
            }
            // 将下标加入队列       
            queue.add(i);
            // 检查队列顶部元素是否在滑动窗口内
            if(queue.peekLast() - k == queue.peek()){
                // 出队
                queue.poll();
            }
            // 若窗口达到最大值
            if(i+1 >= k){
                res[index++] = nums[queue.peek()];
            }
        }
        return res;
    }
}

队列的最大值

面试题59 - II. 队列的最大值 - 力扣（Leetcode）

题目要求

请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。

若队列为空，pop_front 和 max_value 需要返回 -1

例子：

1
2
3
4
5
6
7
8
9
输入: 
["MaxQueue","push_back","push_back","max_value","pop_front","max_value"]
[[],[1],[2],[],[],[]]
输出: [null,null,null,2,1,2]

输入: 
["MaxQueue","pop_front","max_value"]
[[],[],[]]
输出: [null,-1,-1]

提示：

  • 1 <= push_back,pop_front,max_value的总操作数 <= 10000
  • 1 <= value <= 10^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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class MaxQueue {
    // 维护一个队列和一个双端队列
    Queue<Integer> q;
    Deque<Integer> d;

    public MaxQueue() {
        // 初始化
        q = new LinkedList<Integer>();
        d = new LinkedList<Integer>();
    }
    
    public int max_value() {
        // 若双端队列不为空，则返回队列顶部元素，否则返回-1
        if(d.isEmpty()){
            return -1;
        }
        return d.peekFirst();
    }
    
    public void push_back(int value) {
        // 若双端队列不为空，且队双端队列部值小于目标值
        while(!d.isEmpty() && d.peekLast() < value){
            // 从双端队列尾部一直删除元素
            d.pollLast();
        }
        // 直到队列顶部值大于目标值，将value添加到双端队列和队列
        d.offerLast(value);
        q.offer(value);
    }
    
    public int pop_front() {
        // 队列为空，返回-1
        if (q.isEmpty()) {
            return -1;
        }
        // 弹出队列的一个元素，并用flag记录
        int flag = q.poll(); 
        // 判断队列弹出元素是否和双端队列顶部元素相等
        if(flag == d.peekFirst()){
            // 弹出双端队列顶部元素
            d.pollFirst();
        }
        // 返回flag
        return flag;
    }
}

/**
 * Your MaxQueue object will be instantiated and called as such:
 * MaxQueue obj = new MaxQueue();
 * int param_1 = obj.max_value();
 * obj.push_back(value);
 * int param_3 = obj.pop_front();
 */