面试题58-Ⅰ、58-Ⅱ、59-Ⅰ、59-Ⅱ

面试题58-Ⅰ.翻转单词顺序

面试题58-Ⅰ、58-Ⅱ、59-Ⅰ、59-Ⅱ

双指针

  • 倒序遍历字符串 s ,记录单词左右索引边界 i , j ;

  • 每确定一个单词的边界,则将其添加至单词列表 res ;

  • 最终,将单词列表拼接为字符串,并返回即可。

面试题58-Ⅰ、58-Ⅱ、59-Ⅰ、59-Ⅱ

class Solution {
    public String reverseWords(String s) {
    	s = s.trim(); //删除首尾空格
    	int i = s.length() - 1, j = i;
    	StringBuilder res = new StringBuilder();
    	while(i >= 0) {
    		while(i >= 0 && s.charAt(i) != ' ') i--; //搜索首个空格
    		res.append(s.substring(i + 1, j + 1)).append(" "); //添加单词
    		while(i >= 0 && s.charAt(i) == ' ') i--; //跳过单词间的空格
    		j = i; //j指向下个单词的尾字符
    	}
    	return res.toString().trim();
    }
}
  • 时间复杂度 O(N) : 其中 N 为字符串 s 的长度,线性遍历字符串。
  • 空间复杂度 O(N) : 新建的 list(Python) 或 StringBuilder(Java) 中的字符串总长度 ≤ N ,占用 O(N) 大小的额外空间。

分割+倒序

以空格为分割符完成字符串分割后,若两单词间有 x > 1 个空格,则在单词列表 strs 中,此两单词间会多出 x - 1 个 “空单词” (即 “” )。解决方法:倒序遍历单词列表,并将单词逐个添加至 StringBuilder ,遇到空单词时跳过。

面试题58-Ⅰ、58-Ⅱ、59-Ⅰ、59-Ⅱ

class Solution {
    public String reverseWords(String s) {
		String[] strs = s.trim().split(" "); //删除首尾空格,分割字符串
		StringBuilder sb = new StringBuilder();
		for(int i = str.length - 1; i >= 0; i--) {
			if(strs[i].equals("")) continue; //遇到空单词则跳过
			sb.append(strs[i]).append(" "); //将单词拼接至 StringBuilder
		}
		return sb.toString().trim(); //转化为字符串,删除尾部空格,并返回
    }
}
  • 时间复杂度 O(N) : 总体为线性时间复杂度,各函数时间复杂度和参考资料链接如下。

    • split() 方法: 为 O(N) ;
    • trim() 和 strip() 方法: 最差情况下(当字符串全为空格时),为 O(N) ;
    • join() 方法: 为 O(N) ;
    • reverse() 方法: 为 O(N) ;
  • 空间复杂度 O(N) : 单词列表 strs 占用线性大小的额外空间。

————————————————————————————————————————

面试题58-Ⅱ.左旋转字符串

面试题58-Ⅰ、58-Ⅱ、59-Ⅰ、59-Ⅱ

字符串切片

获取字符串 s[n:] 切片和 s[:n] 切片,使用 “+” 运算符拼接并返回即可。
面试题58-Ⅰ、58-Ⅱ、59-Ⅰ、59-Ⅱ

class Solution {
    public String reverseLeftWords(String s, int n) {
		return s.substring(n, s.length()) + s.substring(0, n);
    }
}
  • 时间复杂度 O(N) : 其中 N 为字符串 s 的长度,字符串切片函数为线性时间复杂度(参考资料);
  • 空间复杂度 O(N) : 两个字符串切片的总长度为 N 。

列表遍历拼接

  • 新建一个 list(Python)、StringBuilder(Java) ,记为 res ;

  • 先向 res 添加 “第 n + 1 位至末位的字符” ;

  • 再向 res 添加 “首位至第 n 位的字符” ;

  • 将 res 转化为字符串并返回。

面试题58-Ⅰ、58-Ⅱ、59-Ⅰ、59-Ⅱ

class Solution {
    public String reverseLeftWords(String s, int n) {
		StringBuilde sb = new StringBuilder();
		for(int i = n; i < s.length(); i++)
			sb.append(s.charAt(i));
		for(int i = 0; i < n; i++) 
			sb.append(s.charAt(i));
		return sb.toString();
    }
}

利用求余进行优化

class Solution {
    public String reverseLeftWords(String s, int n) {
		StringBuilde sb = new StringBuilder();
		for(int i = n; i < n + s.length(); i++)
			sb.append(s.charAt(i % s.length()));
		return sb.toString();
    }
}
  • 时间复杂度 O(N) : 线性遍历 s 并添加,使用线性时间;
  • 空间复杂度 O(N) : 新建的辅助 res 使用 O(N) 大小的额外空间。

————————————————————————————————————————

面试题59-Ⅰ.滑动窗口的最大值

面试题58-Ⅰ、58-Ⅱ、59-Ⅰ、59-Ⅱ

双向队列

面试题58-Ⅰ、58-Ⅱ、59-Ⅰ、59-Ⅱ

  • 1.遍历数组,将 “数” 存放在双向队列中,并用 L,R 来标记窗口的左边界和右边界。队列中保存的并不是真的 “数”,而是该数值对应的数组下标位置,并且数组中的数要从大到小排序。如果当前遍历的数比队尾的值大,则需要弹出队尾值,直到队列重新满足从大到小的要求。

  • 2.刚开始遍历时,L 和 R 都为 0,有一个形成窗口的过程,此过程没有最大值,L 不动,R 向右移。

  • 3.当窗口大小形成时,L 和 R 一起向右移,每次移动时,判断队首的值的数组下标是否在 [L,R] 中,如果不在则需要弹出队首的值,当前窗口的最大值即为队首的数。

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
		if(nums == null || nums.length < 2) return nums;
		//双向队列,保存当前窗口最大值的数组下标,保证队列中数组下标对应的数值从大到小排列
		LinkedList<Integer> queue = new LinkedList<>();
		int[] res = new int[nums.length - k + 1];
		//遍历nums数组,窗口区间为[i-k+1,i]
		for(int i = 0; i < nums.length; i++) {
			//保证从大到小,如果前面数小则需要一次弹出,直至满足要求
			while(!queue.isEmpty() && nums[queue.peekLast()] <= nums[i]) {
				queue.pollLast();
			}
			//添加当前值对应的下标
			queue.addLast(i);
			//判断当前队列中存的数组索引是否还在窗口内,i-k+1表示当前窗口的左边界
			if(queue.peek() < i - k + 1) {
				queue.poll();
			}
			//当前窗口长度为k时,保存窗口中的最大值
			if(i + 1 >= k) {
				res[i - k + 1] = nums[queue.peek()];
			}
		}
		return res;
    }
}

遍历

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
		if(nums.length < 2) return nums;
		int len = nums.length;
		int[] res = new int[len - k + 1];
		int maxIndex = -1; //当前滑动窗口中最大值的索引
		int max = Integer.MIN_VALUE; //当前滑动窗口中的最大值
		for(int i = 0; i < len - k + 1; i++) { //i表示当前窗口的左边界
			if(maxIndex < i) { //如果当前最大值不在窗口中
				//此时max已不在窗口中,故先令max等于窗口的左边界,再去与窗口剩余的元素进行比较
				max = nums[i]; 
				maxIndex = i;
				for(int j = i; j < i + k; j++) {//遍历从下标i开始,长度为k的窗口
					if(nums[j] > max) {
						max = nums[j];
						maxIndex = j;
					}
				}
			} else { //如果当前最大值在窗口中
				//判断当前新加进的窗口末尾值与之前窗口的最大值的大小
				if(nums[i + k - 1] > max) {
					max = nums[i + k - 1];
					maxIndex = i + k - 1;
				}
			}
			res[i] = max;
		}
		return res;
    }
}

————————————————————————————————————————

面试题59-Ⅱ.队列的最大值

面试题58-Ⅰ、58-Ⅱ、59-Ⅰ、59-Ⅱ
本文考虑创建两个队列,一个队列为普通的队列,正常执行入队出队的操作,另一个队列为双向递减队列,来保存队列所有递减的元素,并随着入队和出队操作实时更新,这样队列最大元素就始终对应递减列表的首元素
面试题58-Ⅰ、58-Ⅱ、59-Ⅰ、59-Ⅱ
双向队列的实线:

  • 1、当执行入队 push_back() 时: 若入队一个比队列某些元素更大的数字 x ,则为了保持此列表递减,需要将双向队列 尾部所有小于 x 的元素 弹出。

  • 2、当执行出队 pop_front() 时: 若出队的元素是最大元素,则 双向队列 需要同时将首元素出队 ,以保持队列和双向队列的元素一致性。

class MaxQueue {
    LinkedList<Integer> list; //普通队列
    LinkedList<Integer> maxList; //双向递减队列
    public MaxQueue() {
        list = new LinkedList<>();
        maxList = new LinkedList<>();
    }
    //获取最大值时,返回双向队列的队首即可,因为双向队列是单调递减的
    public int max_value() {
        if(maxList.isEmpty()) return -1;
        return maxList.peek();
    }
    
    public void push_back(int value) {
        list.addLast(value);
        //维护单调递减
        while(!maxList.isEmpty() && maxList.peekLast() < value)
            maxList.pollLast();
        //维护好后再将当前元素加入双向队列
        maxList.addLast(value);
    }
    
    public int pop_front() {
        if(list.isEmpty()) return -1;
        //双向队列只会保存普通队列中已存在的元素,如果普通队列的队首元素不等于双向队列头元素
        //只会说明
        if(list.peek().equals(maxList.peek())) maxList.poll();
        return list.poll();
    }
}
  • 时间复杂度 O(1) : max_value(), push_back(), pop_front() 方法的均摊时间复杂度均为 O(1) ;
    空间复杂度 O(N) : 当元素个数为 N 时,最差情况下deque 中保存 NN 个元素,使用 O(N) 的额外空间;
上一篇:58到家数据库30条军规解读


下一篇:剑指 Offer 58 - II. 左旋转字符串