我们使用交换元素的思路,尽量把第i个数放置到i-1这个索引上,如果对方已经符合要求,则不交换,否则交换,直到某个数不能再动了。最后从头到尾检查第一个不在位的数。
1 | class Solution { |
我们使用交换元素的思路,尽量把第i个数放置到i-1这个索引上,如果对方已经符合要求,则不交换,否则交换,直到某个数不能再动了。最后从头到尾检查第一个不在位的数。
1 | class Solution { |
相当于一些数字分布在数轴上多个连续区域,求这些连续区域中的最长值。
我们用hash table来实现常数时间查找及删除,然后从该数字向左右延伸。
1 | class Solution { |
本题求每个滑动窗口中的最大值,可以用堆实现,但单调队列会是更好的选择。我们维护一个单调减队列,并且队列中第i个元素中记录了大小在第i-1个到第i个的元素个数。这个信息能够归类一段数组,并以其最大值来代表这段数组,易于操作。
每次我们需要添加一个元素,删除一个元素,保证窗口大小恒定。
1 | struct Helper{ |
1 | class Solution { |
注意到对连续重复字符的优化,然后每次从中间向两边扩散。
给定一个长字符串,该模板用于求解出某个子串,该子串满足一定的条件。我们使用滑动窗口的技术,并且有一个通用模板。
1 | int findSubstring(string s){ |
启示:
1.双指针标记滑动窗口
2.count可以表示很多含义,例如已经找到的字符个数、重复的字符个数等,灵活运用之
3.?处的加减,取决于滑动窗口具体意义
4.注意最大值和最小值的更新地点
5.注意count的更新和滑动窗口含义的匹配
使用模板来解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```
class Solution {
public:
string minWindow(string s, string t) {
vector<int> mp(256, 0);
int begin , end, count, md;
begin = end = count = 0;
md = INT_MAX;
for (auto c : t) {
mp[c]++;
}
string res;
while (end < s.size()) {
if (mp[s[end++]]-->0) count++;
while (count == t.size()) {
if (md > end-begin) {
res = s.substr(begin, end-begin);
md = end-begin;
}
if (++mp[s[begin++]] > 0) count--;
}
}
return res;
}
};
使用模板来解1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24```
class Solution {
public:
int lengthOfLongestSubstring(string s) {
vector<int> mp(256, 0);
int begin , end, count, md;
begin = end = count = 0;
md = INT_MIN;
string res;
while (end < s.size()) {
if (mp[s[end++]]++>0) count++;
while (count > 0) {
if (mp[s[begin++]]-- > 1) count--;
}
if (md < end-begin) {
res = s.substr(begin, end-begin);
md = end-begin;
}
}
return res.size();
}
};
这里可以发现,count代表当前滑动窗口中,重复字符的个数。
相应地,滑动窗口表示当前每个字符的出现个数。
1 | class MedianFinder { |
用两个堆,并动态地让他们大小保持近似(相等或者small中多一个元素)。使用最大堆small记录较小的元素,使用最大对large记录元素的负值,这样他们的大小就翻转了,绝对值最小的数反而在上面。
1 | /** |
想找出错位的两个节点,只需观察树的中序遍历结果。
如果把数值用线连起来,可以发现从左到右有一到两次下降的过程,次数取决于错位节点是否相邻。
中序遍历时,将第一次遇到的构成下降线的第一个节点记为first,将最后遇到的构成下降线的第二个节点记为sec,最后交换这俩。
LC283
给一组数,把其中的0全部移到末尾,其他元素保持顺序
维持一个当前指针和非零数组的past by one指针1
2
3
4
5
6
7
8
9
10
11public void moveZeroes(int[] nums) {
int i = 0;
for (int j = 0; j < nums.length; j++) {
if (nums[j] != 0) {
int tmp = nums[j];
nums[j] = nums[i];
nums[i] = tmp;
i++;
}
}
}
其实类似于quicksort的partition过程,这种题目还有关于荷兰旗的问题
LC349 求两个数组的交集
1.用两个hash set1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21public int[] intersection(int[] nums1, int[] nums2) {
Set<Integer> set = new HashSet<>(), intersect = new HashSet<>();
for (int i = 0; i < nums1.length; i++) {
set.add(nums1[i]);
}
for (int i = 0; i < nums2.length; i++) {
if (set.contains(nums2[i])) {
intersect.add(nums2[i]);
}
}
int[] res = new int[intersect.size()];
int i = 0;
for (Integer num : intersect) {
res[i++] = num;
}
return res;
}
2.分别排序后双指针1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24public int[] intersection(int[] nums1, int[] nums2) {
Arrays.sort(nums1);
Arrays.sort(nums2);
Set<Integer> st = new HashSet<>();
for (int i = 0, j = 0; i < nums1.length && j < nums2.length; i++, j++) {
if (nums1[i] < nums2[j]) {
i++;
} else if (nums1[j] > nums2[j]) {
j++;
} else {
st.add(nums1[i]);
i++;
j++;
}
}
int[] res = new int[st.size()];
int i = 0;
for (Integer num : st) {
res[i++] = num;
}
return res;
}
3.排序后二分查找
二分查找不优雅的变种1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18int binarySearch(int[] num, int target) {
int low = -1, high = num.length;
while (low +1 != high) {
int mid = low + (high - low) / 2;
if (num[mid] <= target) {
low = mid;
} else if (num[mid] > target) {
high = mid;
}
}
if (high == num.length || num[low] != target) {
return -1;
}
return high;
}
在左右子树分别递归查找p,q节点,如果他们在同一边,则返回那一边的递归结果,否则,返回根节点。
1 | TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { |
这里要注意到一个特点:在处理第n层的next指针时,第n-1层的节点的next指针都已经被设置好,所以可以从左到右遍历第n-1层,即这里的level指针。
使用dummy节点,作为每一层的虚拟起始节点,在每一层结束时,dummy的next指针指向当前层的起始节点,我们利用完这个next信息后,需要把dummy变为白莲花,也就是next置空,这样它可以用于下一层了。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/**
* Definition for binary tree with next pointer.
* struct TreeLinkNode {
* int val;
* TreeLinkNode *left, *right, *next;
* TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
* };
*/
class Solution {
public:
void connect(TreeLinkNode *root) {
for(TreeLinkNode *dummy=new TreeLinkNode(0);root!=NULL;root=dummy->next,dummy->next=NULL){
for(TreeLinkNode*level=root,*last=dummy;level!=NULL;level=level->next){
if(level->left){
last->next=level->left;
last=last->next;
}
if(level->right){
last->next=level->right;
last=last->next;
}
}
}
}
};
不要在原函数上直接进行递归,会超时。
我们首先在对数时间内,通过最左路径找出两个字树的高度,然后根据子树高判断最后一层在哪个子树终止,并对对应的子树进行递归,同时得知另一子树的节点个数。
1 | /** |
[LeetCode] Search in Rotated Sorted Array
旋转数组二分查找,注意先确定区间再调整1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16Int search(int[] A, int target) {
int l = 0, r = A.length-1;
while (l <= r) {
int m = l + ((r-l)>>1);
if (A[m] == target) return m;
if (A[m] < A[r]) {
if (A[m] < target && target <= A[r]) l = m+1;
else r=m;
} else {
if (A[l] <= target && target <= A[r]) r = m;
else l=m;
}
}
return -1;
}
1 | class Solution { |
1 | public String customSortString(String S, String T) { |
1 | static public List<String> findAndReplacePattern(String[] words, String pattern) { |
使用一个引用保存上一个节点1
2
3
4
5
6
7
8
9
10
11
12
13
14TreeNode max;
public boolean isValidBST(TreeNode root){
if(root == null){
return true;
}
boolean left = isValidBST(root.left);
boolean isBigger = true;
if(max != null){
isBigger = root.val > max.val;
}
max = root;
return left && isBigger && isValidBST(root.right);
}
注意return的写法,即同时满足左、中、右
[LeetCode] Permutation in String 字符串中的全排列
双哈希表:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20public boolean checkInclusion(String s1, String s2) {
int n1 = s1.length(), n2 = s2.length();
if (n1 > n2) return false;
int[] m1 = new int[128], m2 = new int[128];
for (int i = 0; i != n1; i++) {
m1[s1.charAt(i)]++;m2[s2.charAt(i)]++;
}
if (Arrays.equals(m1, m2)) return true;
for (int i = n1; i < n2; ++i) {
m2[s2.charAt(i)]++;
m2[s2.charAt(i-n1)]--;
if (Arrays.equals(m1, m2)) return true;
}
return false;
}
一个哈希表+双指针:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19public static boolean checkInclusion(String s1, String s2) {
int n1 = s1.length(), n2 = s2.length(), left = 0;
int[] m = new int[256];
for (int i = 0; i != s1.length(); i++) {
m[s1.charAt(i)]++;
}
for (int i = 0; i != s2.length(); ++i) {
if (--m[s2.charAt(i)] < 0) {
while (++m[s2.charAt(left++)] != 0)
;
} else if (i-left+1 == n1) return true;
}
return n1 == 0;
}
二分求平分根
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19static double calRoot(int n) {
double i = 1, j = n-1;
while (i <= j) {
double mid = i + ((j-i)/2.0);
if (mid - i < 0.000001) {
return j;
}
if (mid * mid < n) {
i = mid;
} else if (mid * mid > n) {
j = mid;
} else {
return mid;
}
}
return -1;
}
1 | public void merge(int[] nums1, int m, int[] nums2, int n) { |
从后往前填充,因为这样不会覆盖第一个数组中较大的元素
1 | public boolean hasCycle(ListNode head) { |
1 | class Solution { |
简单的双指针,注意用last对象的空表示第一个元素的情况
1 | class Solution { |
简单的双指针
public boolean backspaceCompare(String S, String T) {
Stack
for (int i = 0; i != S.length(); i++) {
if (S.charAt(i) != '#') {
st.push(S.charAt(i));
} else if (!st.empty()) {
st.pop();
}
}
for (int i = 0; i != T.length(); i++) {
if (T.charAt(i) != '#') {
st2.push(T.charAt(i));
} else if (!st.empty()) {
st2.pop();
}
}
while (!st.empty() && !st2.empty()) {
if (st.pop() != st2.pop()) {
return false;
}
}
return st.empty() && st2.empty();
}
模拟并比较最终结果。
下面使用常数空间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
28public boolean backspaceCompare(String S, String T) {
if (S == null || T == null) return S == T;
int m = S.length(), n = T.length();
int i = m-1, j = n-1;
int cnt1 = 0, cnt2 = 0;
while (i >= 0 || j >= 0) {
while (i >= 0 && (cnt1 > 0 || S.charAt(i) == '#')) {
if (S.charAt(i) == '#') cnt1++;
else cnt1--;
i--;
}
while (j >= 0 && (cnt2 > 0 || T.charAt(j) == '#')) {
if (T.charAt(j) == '#') cnt2++;
else cnt2--;
j--;
}
if (i >= 0 && j >= 0 && S.charAt(i) == T.charAt(j)) {
i--;j--;
} else {
return i == -1 && j == -1;
}
}
return true;
}
从后向前进行遍历,如果遇到#则记录下来,并且剔除掉之前的字符。
如果typed中mismatch但是仍然是上一个match的字符,那么允许它重试1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21public boolean isLongPressedName(String name, String typed) {
char[] n = name.toCharArray();
char[] t = typed.toCharArray();
int j = 0;
Character last = null;
int i;
for (i = 0; i != n.length && j != t.length; j++) {
if (n[i] == t[j]) {
last = n[i];
i++;
continue;
}
if (last == null || last != t[j]) {
return false;
}
}
return i == n.length;
}
这次每个数字出现的次数等于原来两个数组的出现次数之和
注意,用较小的数组去匹配较大的,这样遍历次数较少1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23public static int[] intersect(int[] nums1, int[] nums2) {
Arrays.sort(nums1);
Arrays.sort(nums2);
List<Integer> l = new ArrayList<>();
for (int i = 0, j = 0; i < nums1.length && j < nums2.length;) {
if (nums1[i] < nums2[j]) {
i++;
} else if (nums1[i] > nums2[j]) {
j++;
} else {
l.add(nums1[i]);
i++;
j++;
}
}
int[] res = new int[l.size()];
int i = 0;
for (Integer num : l) {
res[i++] = num;
}
return res;
}
逆序字符串,练习用java实现 3441
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 public String reverseString(String s) {
int start = 0, end = s.length()-1;
char[] arr = s.toCharArray();
while (start < end) {
char tmp = arr[start];
arr[start] = arr[end];
arr[end] = tmp;
start++;
end--;
}
return new String(arr);
}
如果是用c呢?
int reverseString(char *str, int n) {
if (n < 0) return -1;
char *end = str+n-1;
while (str < end) {
swap(str++, end—);
}
return 0;
}
如果是c++呢
Bool reverseString(std::string &str) {
for (int I = 0; I != str.size()/2; I++) {
std::swap(str[I], str[str.size()-I-1]);
}
return true;
}
556
找到下一个比n大的数
例如,n = 21,那么没有比它大的数,根本原因在于它是降序排列的。
例如,n=12,那么比它大的数就是21.
解法:
首先从右往左找到第一个非降序的数字,然后从右往左找第一个比该数字大的数,交换它们,并对后面这一段数进行排序即可。排序的原因在于有序的数是所有排列中最小的。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
33public int nextGreaterElement(int n) {
char[] number = (n + "").toCharArray();
int i, j;
for (i = number.length-1; i > 0; i--) {
if (number[i-1] < number[i]) {
break;
}
}
if (i == 0) {
return -1;
}
int x = number[i-1];
for (j = number.length-1; j > i; j--) {
if (number[j] > x) {
break;
}
}
char tmp = number[i-1];
number[i-1] = number[j];
number[j] = tmp;
Arrays.sort(number, i, number.length);
long val = Long.parseLong(new String(number));
return (val <= Integer.MAX_VALUE ? (int)val : -1);
}
4
两个有序数组的中位数
1.总数组大小为m+n时,一个trick: 求 (第(m+n+1)/2大 + 第(m+n+2)/2大)/2 即是所求
2.中位数可转为求第k大的数
3.一次淘汰较小的k/2个数1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21public 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[] num1, int i, int[] num2, int j, int k) {
if (i >= num1.length) return num2[j+k-1];
if (j >= num2.length) return num1[i+k-1];
if (k == 1) return Math.min(num1[i], num2[j]);
int midVal1 = (i + k/2 - 1) < num1.length ? num1[i+k/2-1] : Integer.MAX_VALUE;
int midVal2 = (j + k/2 - 1) < num2.length ? num2[j+k/2-1] : Integer.MAX_VALUE;
if (midVal1 < midVal2) {
return findKth(num1, i+k/2, num2, j, k-k/2);
} else {
return findKth(num1, i, num2, j+k/2, k-k/2);
}
}
对于倒排记录表的merge算法,进行了一些简单的实现。目前实现了Intersect OR ANDNOT 和含位置信息的(k邻居内)的合并算法。
分别描述一下关键步骤:
docID相同时加入,否则将docID较小的一方前进一下
docID相同时加入,否则加入较小的一方,然后让它前进
docID相同时不能加入,因为这时不满足NOT的语义,前者小时,则说明后者无此id,可加入前者。后者小时,由于前置无此id,不能加入后者,只需要前进
先找到docID相同的倒排记录表,然后外层遍历前者,并维护一个由后者元素构成的窗口,这个窗口会包含与当前前者元素距离满足条件的后者元素。
总的来说就这么多啦,下次开始写带压缩和不带压缩的索引。Have fun!
1 | 数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。如果不存在则输出0。 |
1 | bool moreThanHalf(vector<int> v, int& res) { |
缺失模块。
1、请确保node版本大于6.2
2、在博客根目录(注意不是yilia根目录)执行以下命令:
npm i hexo-generator-json-content --save
3、在根目录_config.yml里添加配置:
jsonContent: meta: false pages: false posts: title: true date: true path: true text: false raw: false content: false slug: false updated: false comments: false link: false permalink: false excerpt: false categories: false tags: true