- 寻找两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))——看到时间复杂度包含log 要用分治算法，findKth
示例 1:
nums1 = [1, 3]
nums2 = [2]
关键：学会写在两个数组中，寻找Kth数字。
public class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int m = nums1.length, n = nums2.length, left = (m + n + 1) / 2, right = (m + n + 2) / 2;
return (findKth(nums1, 0, nums2, 0, left) + findKth(nums1, 0, nums2, 0, right)) / 2.0;
}
int findKth(int[] nums1, int i, int[] nums2, int j, int k) {
if (i >= nums1.length) return nums2[j + k - 1];
if (j >= nums2.length) return nums1[i + k - 1];
if (k == 1) return Math.min(nums1[i], nums2[j]);
int midVal1 = (i + k / 2 - 1 < nums1.length) ? nums1[i + k / 2 - 1] : Integer.MAX_VALUE;
int midVal2 = (j + k / 2 - 1 < nums2.length) ? nums2[j + k / 2 - 1] : Integer.MAX_VALUE;
if (midVal1 < midVal2) {
return findKth(nums1, i + k / 2, nums2, j, k - k / 2);
} else {
return findKth(nums1, i, nums2, j + k / 2, k - k / 2);
}
}
}
- 无重复字符串的最大长度
建立一个256位大小的整型数组来代替哈希表，这样做的原因是ASCII表共能表示256个字符，所以可以记录所有字符。
然后我们需要定义两个变量res和left，其中res用来记录最长无重复子串的长度，left指向该无重复子串左边的起始位置。
然后我们遍历整个字符串，对于每一个遍历到的字符，如果哈希表中该字符串对应的值为0，说明没有遇到过该字符，则此时计算最长无重复子串，i - left +１，其中ｉ是最长无重复子串最右边的位置，left是最左边的位置，还有一种情况也需要计算最长无重复子串，就是当哈希表中的值小于left，这是由于此时出现过重复的字符，left的位置更新了，如果又遇到了新的字符，就要重新计算最长无重复子串。最后每次都要在哈希表中将当前字符对应的值赋值为i+1。
public int lengthOfLongestSubstring1(String s) {
int[] m = new int[256];
int res = 0, left = 0;
for (int i = 0; i < s.length(); i++) {
left = Math.max(left, m[s.charAt(i)]);
res = Math.max(res, i - left + 1);
m[s.charAt(i)] = i + 1;
}
return res;
}
-
2sum 3sum 4sum
-
盛最多水的容器 —— 对撞指针
题目：给定 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
解题：头尾各一个指针：首指针i指向数组中的第一个元素，尾指针j指向数组中的最后一个元素。每一次循环都舍弃索引i和索引j中较短的那一条边。
代码：
public int maxArea(int[] height) {
int n = height.length;
int i = 0;
int j = n - 1;
int area = (n - 1) * Math.min(height[i], height[j]);
while(i < j) {
area = Math.max(area, (j - i) * Math.min(height[i], height[j]));
if(height[i] < height[j]) {
i++;
}else {
j--;
}
}
return area;
}
- 从排序数组中删除重复元素
题目：给定一个有序数组，删除重复内容，使每个元素只出现一次，并返回新的长度。
不要为其他数组分配额外的空间，您必须通过在 O（1）额外的内存中就地修改输入数组来实现这一点。
解题：采用两个标记点 number 和 i ，number记录不重复元素的位置，i从number的下一个开始遍历数组，如果i位置的数字等于number位置的数字，说明该数字重复出现，不予处理；如果i位置的数字不等于number位置的数字，说明该数字没有重复，需要放到l的下一位置，并使number加1。
代码：
int number = 0;
for(int i =0; i<nums.length;i++){
// 相邻两个值比较，不同才做统计操作
if(nums[i]!=nums[number]){
number++;
nums[number] = nums[i];
}
}
// 不同数字为总量= number+1
return ++number;
题目变形：给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素最多出现两次，返回移除后数组的新长度。
int removeDuplicates(vector<int>& nums) {
if (nums.empty())
return 0;
// 一次遍历，[0,number)为最终的每个元素最多出现两次的数组
int n = nums.size();
int number = 1;
int count = 1; // 计数器
for (int i = 1; i < nums.size(); i++) {
if (nums[i] == nums[number - 1] && count == 1) {
nums[number ++] = nums[i];
count++;
}
else if (nums[i] != nums[number - 1]) {
nums[number ++] = nums[i];
count = 1;
}
}
return number ;
- 分类颜色
题目： 给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
示例:
输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]
思路：维护三个指针
void sortColors2(vector<int>& nums) {
int zero_index = -1;
int n = nums.size();
int two_index = n;
for (int i = 0; i < n;) {
if (i >= two_index)
return;
if (nums[i] == 1)
i++;
else if (nums[i] == 0) {
swap(nums[++zero_index], nums[i]);
i++;
}
else if (nums[i] == 2) {
swap(nums[i], nums[--two_index]);
}
}
}
- 长度最小的子数组——双指针、滑动指针
给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组，返回 0。
示例:
输入:
s = 7, nums = [2,3,1,2,4,3]
输出: 2
解释: 子数组
[4,3]
代码：
int minSubArrayLen(int s, vector<int>& nums) {
// 根据当前nums[i,j]的值与s的大小关系决定i,j索引的更新
int i = 0;
int j = -1;
int minLen = nums.size() + 1;
int sum = 0;
int n = nums.size();
while (i < n) {
// 当前的滑动窗口sum小于s，那么就要滑动j，使得sun增加
if (sum < s) { // 如果sum不够，则增加j
sum += nums[++j];
if (j >= n) // 退出条件
break;
}
else { // 如果sum够大，则增加i
minLen = std::min(minLen, j - i + 1);
sum -= nums[i++];
}
}
return minLen == n + 1 ? 0 : minLen;
}
- 数组中的第K个最大元素
在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
示例 1:
输入:
[3,2,1,5,6,4] 和
k = 2
输出: 5
示例 2:
输入:
[3,2,3,1,2,4,5,5,6] 和
k = 4
输出: 4
思路：
针对这个题目，我们首先想到的就是先用排序算法对数据从大到小进行排序，然后直接返回降序后的第 K 个元素即可。
另外，我们也可以借鉴快速排序的思想。每次选取一个 pivot，将大于 pivot 的数放在 pivot 左边，将小于 pivot 的数放在 pivot 右边。这时：
(1)如果 pivot 正好是第 K 个数据，则 pivot 就是数组中的第 K 个最大元素；
(2)如果 pivot 所在的位置小于 K ，则说明数组中的第 K 个最大元素位于 pivot 的右边。此时，假设 pivot 的位置为 which_max，which_max 是几就代表 pivot 是数组中的第几个最大元素。这时候，我们再从 pivot 右边的数据中找到第 (K-which_max) 个最大元素即可；
(3)如果 pivot 所在的位置大于 K ，则说明数组中的第 K 个最大元素位于 pivot 的左边。这时候，pivot 左边的数据全部大于 pivot，我们继续从 pivot 左边的数据中找第 K 个最大元素即可
int findKthLargest(vector<int>& nums, int k) {
return quick_sort(nums, 0, nums.size()-1, k);
}
// 第一种快排思想
int quick_sort(vector<int>& data, int left, int right, int k)
{
int i = left;
int j = right;
int pivot = data[right];
int len = right - left + 1;
if (left < right)
{
// 从大到小对数组进行快排
while(i < j)
{
while(i < j && data[i] >= pivot) // 从左往右找第一个比 pivot 小的数
{
i++;
}
if (i < j)
{
data[j--] = data[i];
}
while(i < j && data[j] <= pivot) // 从右往左找第一个比 pivot 大的数
{
j--;
}
if (i < j)
{
data[i++] = data[j];
}
}
data[i] = pivot; // 此时 i == j
// pivot 此时位于索引 i 处，i - left + 1 表示 pivot 是第几大的数
int which_max = i - left + 1;
if (which_max == k) // pivot 正好是第 k 大的数
{
return pivot;
}
// 第 k 大的数在 pivot 右边，问题转化为找右边数组第 (k - which_max) 大的元素
// 比如 pivot 是第四大的数，要找第五大的数，则继续找右边数组第一大的数即可
else if(which_max < k)
{
return quick_sort(data, i + 1, right, k - which_max);
}
// 第 k 大的数在 pivot 左边，问题转化为找左边数组第 k 大的元素
// 比如 pivot 是第三大的数，要找第二大的数，则继续找左边数组第二大的数即可
else
{
return quick_sort(data, left, i - 1, k);
}
}
else
{
return pivot;
}
}
网友评论