内容简介：[TOC]题目描述:
[TOC]
合并两个有序数组
题目描述:
给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。
输入: nums1 = [1,2,3,0,0,0], m = 3 nums2 = [2,5,6], n = 3 输出: [1,2,2,3,5,6] 复制代码
解题思路：
跟堆 排序 中的合并两个有序数组的方法类似。
从尾部进行遍历，比较两个数组的最大值，放入到第一个数组中的末尾。
public void merge(int[] nums1, int m, int[] nums2, int n) {
if (nums1 == null || nums2 == null) {
return;
}
int p1 = m - 1;
int p2 = n - 1;
while (p1 >= 0 && p2 >= 0) {
nums1[p1 + p2 + 1] = nums1[p1] > nums2[p2] ? nums1[p1--] : nums2[p2--];
}
while (p2 >= 0) {
nums1[p2] = nums2[p2];
p2--;
}
}
复制代码
移除元素
题目描述: 给定一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。 你不需要考虑数组中超出新长度后面的元素。 复制代码
解题思路: 使用双指针, i 是慢指针, j 是快指针, 原地置换元素, 最后返回新数组的长度.(由于 nums 数组是传参引用, 所以在方法内部修改后, 外部调用时是修改后的数组内容)
public int removeElement(int[] nums, int val) {
int i = 0;
for (int j = 0; j < nums.length; j ++) {
if (nums[j] != val) {
nums[i++] = nums[j];
}
}
return i;
}
复制代码
无重复字符的最长子串
题目描述：给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。 复制代码
解答思路： 使用滑动窗口，双指针进行左闭右开[i, j)，每次遍历刷新下标，保证set中不重复，取最长的ans，
代码：
public int lengthOfLongestSubstring(String s) {
int n = s.length();
Set<Character> set = new HashSet<>();
int ans = 0, i = 0, j = 0;
while (i < n && j < n) {
if (!set.contains(s.charAt(j))){
set.add(s.charAt(j++));
ans = Math.max(ans, j - i);
}
else {
// 有重复的情况下，去掉最左边
set.remove(s.charAt(i++));
}
}
return ans;
}
复制代码
进阶版
解答思路： 遇到重复的字符，将滑动窗口的左边直接滑到第一个重复的字符下标。如果 s[j] 在 [i, j) 范围内有与 j' 相同的字符, 可以直接跳过 [i, j']范围内的所有元素, 将 i 下标置为 j' + 1. 使用 HashMap 来存储字符对应的下标.
public static int lengthOfLongestSubstring(String s) {
Map<Character, Integer> map = new HashMap<>();
int length = s.length(), ans = 0;
for (int i = 0, j = 0; j < length; j++) {
char temp = s.charAt(j);
if (map.containsKey(temp)) {
i = Math.max(map.get(temp), i);
}
ans = Math.max(ans, j - i + 1);
map.put(temp, j + 1);
}
return ans;
}
复制代码
串联所有单词的子串
题目描述: 给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。
注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。
输入： s = "barfoothefoobarman", words = ["foo","bar"] 输出：[0,9] 解释： 从索引 0 和 9 开始的子串分别是 "barfoor" 和 "foobar" 。 输出的顺序不重要, [9,0] 也是有效答案。 复制代码
解题思路:
使用两个 HashMap 保存出现的字符和次数
遍历给定字符(直到总长度 totalLen减去单个待查找字符的长度wordLen), 在内部循环中, 以 wordLen 作为长度切分给定的字符。如果连续子字符中包含查询字符，继续找；如果不包含查询字符，调成内层循环，从下一个字符开始查询。最后内层循环结束后，判断查找次数是否一致，如果是，保存起始下标到结果集中。
代码:
public List<Integer> findSubstring(String s, String[] words) {
List<Integer> result = new ArrayList<>();
int wordSize = words.length;
if (wordSize == 0) {
return result;
}
// words 数组中每个字符的长度都一致, 取第一个
int wordLength = words[0].length();
// 字符数组有可能有重复的, 使用 allWordMap 存放每个 word 出现的次数
HashMap<String, Integer> allWordMap = new HashMap<>();
for (String word : words) {
allWordMap.put(word, allWordMap.getOrDefault(word, 0) + 1);
}
for (int i = 0; i < s.length() - wordSize * wordLength + 1; i++) {
HashMap<String, Integer> hashMap = new HashMap<>();
// 单趟循环中, 成功匹配的次数
int num = 0;
while (num < wordSize) {
// 根据查找字符的长度进行截断
String word = s.substring(i + num * wordLength, i + (num + 1) * wordLength);
if (allWordMap.containsKey(word)) {
hashMap.put(word, hashMap.getOrDefault(word, 0) + 1);
// 还有可能超过 words 中原来的数量
if (hashMap.get(word) > allWordMap.get(word)) {
break;
}
} else {
// 如果没有查询到, 跳过这次循环, 查找下一个字符
break;
}
num++;
}
if (num == wordSize) {
result.add(i);
}
}
return result;
}
复制代码
旋转链表
题目描述：
给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。
输入: 1->2->3->4->5->NULL, k = 2 输出: 4->5->1->2->3->NULL 解释: 向右旋转 1 步: 5->1->2->3->4->NULL 向右旋转 2 步: 4->5->1->2->3->NULL 复制代码
解题思路
①：遍历链表，获得链表长度和最后一个节点的地址。
②：计算得到需要移动的次数（k % length）
③：移动，以示例作为例子，k = 2，表示右移两次，可以认为是做了以下三步操作：
- 末尾节点指向了头部节点：5 -> 1
- 第三个节点变成了头部节点：head = 3
- 第二个节点变成了末尾节点：2.next -> null
代码：
public ListNode rotateRight(ListNode head, int k) {
if (head == null || k == 0) {
return head;
}
int length = 1;
ListNode tempNode = head;
ListNode endNode = null;
while (tempNode.next != null) {
length++;
tempNode = tempNode.next;
}
endNode = tempNode;
// 得到需要移动的次数
int moveNum = k % length;
if (moveNum == 0) {
return head;
}
// 找到待替换的下标
int findIndex = 1, index = length - moveNum + 1;
tempNode = head;
while (tempNode.next != null) {
findIndex++;
if (findIndex == index) {
endNode.next = head;
head = tempNode.next;
tempNode.next = null;
break;
}
tempNode = tempNode.next;
}
return head;
}
复制代码
最小覆盖子串
题目描述：(原题描述不完整，还有很多隐含条件，在评论区找出来的）
给定一个字符串 S 和一个字符串 T，请在 S 中找出包含 T 所有字母的最小子串。
示例： 输入: S = "ADOBECODEBANC", T = "ABC" 输出: "BANC" 说明： 如果 S 中不存这样的子串，则返回空字符串 ""。 如果 S 中存在这样的子串，我们保证它是唯一的答案。 复制代码
隐含条件:
① 输入: s='a' t='aa' 输出： '' ② 参数的全集是大写字母和小写字母 复制代码
解题思路，参考这篇文章
1. 注意到题目的关键："所有字母的最小子串"，也就是说两个串都只能是字母。 2. 于是，可以开辟一个大小为64的数组，来存放数组中字母的频率(Frequency)。准确的说， 通过字母的ASCII码作为数组的索引，开辟空间的大小为26+6+26=58：26个大写字母，26个小写字母， 还有中间的6个非字母 A~Z[65~90] 非字母[91~96] a~z[97~122] 3. 滑动窗口的使用：分三种情况来移动窗口：（这里令当前窗口的左右边界分别为l，r，窗口的大小为winSize=r-l+1） 1) 当winSize < t.size() r++; 也就是窗口右边界向右移动 2) 当winSize == t.size() : 2.1) 当窗口中的字符已经符合要求了，直接返回return，已经找到了 2.2) 否则r++，窗口右边界向右移动 3) 当winSize > t.size() 2.1) 当窗口中的字符已经符合要求了，l++，窗口左边界向右移动 2.2) 否则r++，窗口右边界向右移动 4. 上面是滑动窗口的使用思路，具体实现上有一定的不同，下面是需要考虑到的要点： 1) 啥叫作窗口中的字符已经符合要求了？ 1) 窗口滑动时的操作是关键 2) 要考虑到数组越界的问题 复制代码
代码实现(解答答案中耗时最少的回答）：
public String minWindow(String s, String t) {
int lenS = s.length(), lenT = t.length();
if(lenS < lenT){
return "";
}
int[] tCount = new int[256];
for(int i=0;i<lenT;i++){
tCount[t.charAt(i)] ++;
}
int[] sCount = new int[256];
int left = 0, right = 0;
//保存窗口中等于字符串t的字符的数量，当count等于lenT时，说明找到一个子串
int count = 0;
int minLen = lenS + 1, start = -1;
while(left < lenS){
if(right < lenS && count < lenT){
//right右滑一格
char charRight = s.charAt(right);
sCount[charRight] ++;
if(sCount[charRight] <= tCount[charRight]){
count ++;
}
right ++;
}else{
char charLeft = s.charAt(left);
//更新最小字串的长度和起始索引
if(count == lenT && right - left < minLen){
minLen = right - left;
start = left;
}
//left右滑一格
sCount[charLeft] --;
// 这里只会在 sCount 中，被去掉要查询的字符，才会减少窗口中的总数；
// 如果被去掉是其它无关字符，只需要 left 移动，总量 count 不需要改变
if(sCount[charLeft] < tCount[charLeft]){
count --;
}
left ++;
}
}
if(start != -1){
return s.substring(start, start + minLen);
}
return "";
}
复制代码
数组中的 k-diff 数对
题目描述： 给定一个整数数组和一个整数 k, 你需要在数组里找到不同的 k-diff 数对。这里将 k-diff 数对定义为一个整数对 (i, j), 其中 i 和 j 都是数组中的数字，且两数之差的绝对值是 k.
示例 1: 输入: [3, 1, 4, 1, 5], k = 2 输出: 2 解释: 数组中有两个 2-diff 数对, (1, 3) 和 (3, 5)。 尽管数组中有两个1，但我们只应返回不同的数对的数量。 复制代码
解题思路：
使用 map 保存给定的数组，每个数字出现的次数。根据 k 值判断两个数字间的差值是否符合条件。
代码：
public int findPairs(int[] nums, int k) {
int ans = 0;
HashMap<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
if (k == 0) {
for (int key : map.keySet()) {
if (map.get(key) > 1) {
ans++;
}
}
} else if (k > 0) {
for (int key : map.keySet()) {
if (map.containsKey(key + k)) {
ans++;
}
}
} else {
for (int key : map.keySet()) {
if (key >= 0) {
continue;
}
if (map.containsKey(key - k)) {
ans++;
}
}
}
return ans;
}
复制代码
进阶版
将数组排好序之后进行比较：
public int findPairs(int[] nums, int k) {
if (k < 0) {
return 0;
}
Arrays.sort(nums);
int length = nums.length;
int ans = 0, i = 0, j = 1;
if (k == 0) {
while (j < length) {
if (nums[j] == nums[i]) {
ans++;
}
int a = i++;
while (nums[i] == nums[a]) {
i++;
if (i == length) {
return ans;
}
}
j = i + 1;
}
} else {
while (j < length) {
while (nums[j] - nums[i] < k) {
j++;
if (j == length) {
return ans;
}
}
if (nums[j] - nums[i] == k) {
ans++;
}
int a = i++;
while (nums[i] == nums[a]) {
i++;
}
}
}
return ans;
}
复制代码
字符串的排列
题目描述：
给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。
换句话说，第一个字符串的排列之一是第二个字符串的子串。
输入: s1 = "ab" s2 = "eidbaooo"
输出: True
解释: s2 包含 s1 的排列之一 ("ba").
注意：
输入的字符串只包含小写字母
两个字符串的长度都在 [1, 10,000] 之间
复制代码
解题思路：
由于只包含小写字母，可以使用数组保存待匹配的字符出现的次数。然后通过两个指针的移动，匹配到 s1 长度的 s2 子串。
代码：
public boolean checkInclusion(String s1, String s2) {
int[] count = new int[26];
char[] pattern = s1.toCharArray();
char[] str = s2.toCharArray();
for (int i = 0; i < pattern.length; i++) {
count[pattern[i] - 'a']++;
}
int left = 0, right = 0;
while (right < str.length){
if (count[str[right] - 'a'] != 0) {
count[str[right] - 'a']--;
right++;
if (right - left == pattern.length) {
return true;
}
} else if (left == right) {
left++;
right++;
} else {
count[str[left] - 'a']++;
left++;
}
}
return false;
}
复制代码
希望各位帮忙点个star，给我加个小星星:sparkles:
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持 码农网
猜你喜欢:
- NULL 指针、零指针、野指针
- 将数组和矩阵传递给函数,作为C中指针的指针和指针
- C语言指针数组和数组指针
- python（函数指针和类函数指针）
- C++ 基类指针和派生类指针之间的转换
- golang的值类型，指针类型和引用类型&值传递&指针传递
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
The Lean Startup
Eric Ries / Crown Business / 2011-9-13 / USD 26.00
更多中文介绍：http://huing.com Most startups fail. But many of those failures are preventable. The Lean Startup is a new approach being adopted across the globe, chan ging the way companies are built and ......一起来看看 《The Lean Startup》 这本书的介绍吧!
JS 压缩/解压工具
在线压缩/解压 JS 代码
随机密码生成器
多种字符组合密码