剑指office算法

发表于 分类于 阅读次数：
本文字数： 11k 阅读时长 ≈ 10 分钟

不修改数组找出重复的数字

二分+抽屉原则

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
给定一个长度为 n+1 的数组nums，数组中所有的数均在 1∼n 的范围内，其中 n≥1。

请找出数组中任意一个重复的数，但不能修改输入的数组。

样例
给定 nums = [2, 3, 5, 4, 3, 2, 6, 7]。

返回 2 或 3。
*/
class Solution {
public:
    int duplicateInArray(vector<int>& nums) {
        int l = 1, r = nums.size() -1;
        while(l < r){
            int mid = r + l >> 1;
            int s = 0;
            for(auto x : nums) s += x >=l && x <= mid; //if(x >=l && x <= mid) s++  或者是  s+= (x >=l && x <=r)
            if(s > mid - l + 1) r = mid;
            else l = mid + 1;
        }
        return r;
    }
};

重建二叉树

二叉树递归

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
/**
给定：
前序遍历是：[3, 9, 20, 15, 7]
中序遍历是：[9, 3, 15, 20, 7]

返回：[3, 9, 20, null, null, 15, 7, null, null, null, null]
返回的二叉树如下所示：
    3
   / \
  9  20
    /  \
   15   7
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    map<int,int> hash;
    vector<int> preorder, inorder;
    
    TreeNode* buildTree(vector<int>& _preorder, vector<int>& _inorder) {
        preorder = _preorder, inorder = _inorder;
        for(int i = 0; i < inorder.size(); i++) hash[inorder[i]] = i;
        return dfs(0,preorder.size() -1,0,inorder.size() -1);
        TreeNode* dfs(int pl,int pr,int il, int ir){
            if(pl > pr) return nullptr;
            int k = hash[root -> val];
            auto left = dfs(pl+1, pl + k -il, il, k -1);
            auto right = dfs(pl+ k -il +1, pr, k + 1, ir);
            root->left = left, root->right = right;
            return root;
        }
        
    }
};

二叉树的下一个节点

二叉树操作

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
/*
*
给定一棵二叉树的其中一个节点，请找出中序遍历序列的下一个节点。

注意：

如果给定的节点是中序遍历序列的最后一个，则返回空节点;
二叉树一定不为空，且给定的节点一定不是空节点；
样例
假定二叉树是：[2, 1, 3, null, null, null, null]， 给出的是值等于2的节点。

则应返回值等于3的节点。

解释：该二叉树的结构如下，2的后继节点是3。
  2
 / \
1   3
*
/
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode *father;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL), father(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* inorderSuccessor(TreeNode* p) {
       if( p -> right)
       {
           while(p -> left) p = p -> left;
           return p;
       }
        while( p -> father && p == p -> father -> right)
            p = p -> father;
        return p -> father;
    }
};

##

用两个栈实现队列

栈操作

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 MyQueue {
public:

    stack<int> stk,cache;

    /** Initialize your data structure here. */
    MyQueue() {
        
    }
    
    /** Push element x to the back of queue. */
    void push(int x) {
        stk.push(x);
    }
    
    void copy(stack<int> a, stack<int>b){
        while(a.size()){
            b.push(a.top());
            a.pop();
        }
      
    }
    
    /** Removes the element from in front of queue and returns that element. */
    int pop() {
        copy(stk,cache);
        int result = cache.top();
        cache.pop();
        copy(cache,stk);
        return result;
    }
    
    /** Get the front element. */
    int peek() {
        copy(stk,cache);
        int result = cache.top();
        copy(cache,stk);
        return result;
    }
    
    /** Returns whether the queue is empty. */
    bool empty() {
        return stk.empty();
    }
};

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * bool param_4 = obj.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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/**
定义 a0=1a0=1, a1=1a1=1, an=an−1+an−2an=an−1+an−2，求 anan 是多少。
为了避免考虑整数溢出问题，我们求 an%pan%p 的值，p=109+7p=109+7。
*/
const int MOD = 1000000007;
// 1.递归
int f(int n){
    if(n <= 1) return 1;
    return (f(n-1) + f(n-2)) % MOD;
}

//2.记忆化搜索
//开一个大数组记录中间结果 如果状态被计算过，直接查表，否则递归计算  
//递归计算，递归层数太多会爆栈
const int N = 100000, MOD = 1000000007;
int a[N];
if f2(int n){
    if(a[n]) return a[n];
    if(n <= 1) return 1;
    a[n] = f2(n - 1) + f2(n - 2);
    a[n] %= MOD;
    return a[n];
}

//3.递推
//开个大数组，记录每个数的值，用循环递推计算，
//计算n个状态 则开一个长度是 n 的数组，内存将成为瓶颈
const int N = 100000, MOD = 1000000007;
int f3(int n){
    a[0] = a[1] = 1;
    for(int i = 2; i <= n; i++)
    {
        a[i] = a[i -1] + a[i - 2];
        a[i] %= MOD;
    }
    return a[n];
}

//4.递归+滚动变量
//递推优化 记录前两项值 时间复杂度o(n) 变成 空间复杂度变成0（1）
const int MOD = 1000000007;
int f4(int n){
    int x,y,z;
    x = y = 1;
    for(int i = 2; i <= n; i++){
        z = (x + y) % MOD;
        x = y;
        y = z;
    }
}

最后一种使用矩阵运算+快速幂

快速幂模板
$$
m^k\pmod p
$$

1
2
3
4
5
6
7
8
9
10
11
//下次分析

//时间复杂度 O(logk)。
int qmi(int m, int k, int p){
    int res = 1 %p, t = m;
    while(k){
        if(k&1) res = res * t %p;
        t = t * t % p;
        k >>=1;
    }
}

旋转数组的最小数字

二分

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
/**
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
输入一个升序的数组的一个旋转，输出旋转数组的最小元素。
例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。
数组可能包含重复项。
注意：数组内所含元素非负，若数组大小为0，请返回-1。
样例
输入：nums=[2,2,2,0,1]
输出：0

*/
//粗暴法
class Solution {
public:
    int findMin(vector<int>& nums) {
        if(nums.empty()) return -1;
        int mix = nums.at(0);
        for(auto x : nums){
            if(x < mix) mix = x;
        }
        return mix;
    }
};
//二分法
class Solution{
    public:
    int findMid(vector<int>& nums){
        int n = nums.size() - 1;
        if(n < 0) return -1;
        while( n >0 && nums[0] == nums[n]) n--;
        if(nums[0] < nums[n]) return nums[0];
        int l = 0, r = n;
        while(l  < r ){
            int mid = l + r >> 1; //[l,mid] [mid+1,r]
            if(nums[0] < nums[mid]) l = mid+1;
            else r = mid
        }
        return nums[r];
    }
}

数组中只出现一次的数字O

异或位运算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
数组中数字均有重复，只有两个数分别都唯一，找出这两个数
输入:[2,5,2,7,3,2,3]
输出:[5,7]
思路： 数组所有数异或之后，[异或 同：0 不同：1]
剩下两个数， 此时 5    7
              0101 异或 0111 = 0010 
              用0001 和 0010 异或 如果不为1 ，0001 左移一位，步长++(jud << 1);
              之后就把 0101 和 0111 区分开来
              if(jud ^ nums) x ^= nums;
              else y ^= nums;
*/
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res = 0;
        for(auto x : nums)
            res ^= x;
        return res;
    }
};

数组中只出现一次的数字I

异或位运算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/** 136
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1:
输入: [2,2,1]
输出: 1
示例 2:
输入: [4,1,2,1,2]
输出: 4
思路： 每个数相互异或 得到的那个数就是只出现一次的数
*/
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        
    }
};

数组中只出现一次的数字II

异或位运算

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
/** 137
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1:
输入: [2,2,3,2]
输出: 3
示例 2:
输入: [0,1,0,1,0,1,99]
输出: 99
思路： [ 0010, 0010, 0011, 0010 ]
右移0位[ xxx0, xxx0, xxx1, xxx0 ]异或[ 0001 ] = [ 0, 0, 1, 0 ] =>sum= 1 ;cout += sum % 3  = 1;
右移1位[ xxx1, xxx1, xxx1, xxx1 ]异或[ 0001 ] = [ 1, 1, 1, 1 ] =>sum= 4 ;cout += sum % 3 = 1+ sum = 2;
右移2位[ xxx0, xxx0, xxx0, xxx0 ]异或[ 0000 ] = [ 0, 0, 0, 0 ] =>sum= 0 ;cout += sum % 3 = 0+ sum = 2;
右移3位[ xxx0, xxx0, xxx0, xxx0 ]异或[ 0000 ] = [ 0, 0, 0, 0 ] =>sum= 0 ;cout += sum % 3 = 0+ sum = 2;
输入为 0001左移0位 + 0001左移1位 ；
*/
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res = 0;
        for(int k= 0; k < 32; k++){
           int mask  = 1 << k ;
           int cout = 0;
            for(auto num : nums){
                if(num & mask) cout++;
            }
            if(cout % 3 != 0) res |= mask;
        }
        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
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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
/**
给定两个串a和b，问b是否是a的子串的变位词
例：
a = hello , b = lel,lle,ello 都是 true
            b = elo 是false
思路:
滑动窗口 + 维护数组
array[26] = 0
for(int index : b.size() -1) 
array[b[index] - 'a'] ++; onZero++;  a['l'] a['e' = 4]   onZero = 3;
                                        2      1
for(int index : a.size() -1)
{
	array[a[index] - 'a'] -- == 0; onZero --; //if(onZero == 0) -> true;
	a['h'] a['e'] a['l']
	  -1     0      1
	array[a[index] - 'a'] -- == -1; onZero ++;
	
	index 会滑动
}
return false;

*/
/* 普通版
*/
class Solution{
    public:
    bool isAnagram(String s, String t){
        if(s.length() != t.length) return false;
        int a[26] = {0};
        int length = sizeof(a)/sizeof(a[0]);
        for(int i =0; s[i] != '\0'; i++){
            a[s[i] - 'a']++;
            a[t[i] - 'a']--;
        }
        for(int i = 0 ; i < length ; i++)
            if(a[i] != 0) return false;
        return true;
    }
    
}
// 升级 窗口滑动
int nonZero = 0;
for(int i =0; i < lenb; ++i)
    if(++num[b[i] - 'a'] == 1) ++nonZero;
//非0出现

//找子串
for(int i = 0; i < lenb; ++i){
    int c= a[i] - 'a';
    --num[c];
    if(num[c] == 0) --nonZero;
    else if(num[c] == -1) ++nonZero;
}
if(nonZero == 0 ) return true;

//滑动窗口 向右移动
// new a[i-lenb +1 , i]
// old a[i-lenb , i-1]
// 扔 a[i-lenb] 加入a[i]
for(int i = lenb; i < lena; i++){
    int c = a[i - lenb] - 'a';
    ++num[c];
    if(num[c] == 1) ++nonZero;
    else if(num[c] == 0) --nonZero;
    c = a[i] -'a';
    --num[c];
    if(num[c] == 0) --nonZero;
    else if(num[c] == -1) ++nonZero;
    if(nonZero == 0) return true;
}
//小补充
num.empty();
num.at(); = num[i]
num.push_back();
vector<int> v ;
v.reserve(10);

矩阵中的路径

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
55
56
57
/**
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。
路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。
如果一条路径经过了矩阵中的某一个格子，则之后不能再次进入这个格子。
注意：

输入的路径不为空；
所有出现的字符均为大写英文字母；
样例
matrix=
[
  ["A","B","C","E"],
  ["S","F","C","S"],
  ["A","D","E","E"]
]
str="BCCE" , return "true" 
str="ASAE" , return "false"
*/
class Solution {
public:
    bool hasPath(vector<vector<char>>& matrix, string str) {
        for(int i =0 ; i < matrix.size(); i++)
        {
            for(int k = 0; k < matrix[i].size(); k++)
            {
                if(dfs(matrix, str,0, i , k))
                return true;
            }
        }
        return false;
    }
    
    bool dfs(vector<vector<char>>& matrix, string &str, int u, int x, int y ){
        //验证是否为当前是否对应
        if( matrix[x][y] != str[u] ) return false;
        //长度一致 返回 true
        if(u == str.size() -1 ) return true;
        
        //走的范围
        int dx[4] = {-1,0,1,0}, dy[4] = {0,1,0,-1};
        
        char t = matrix[x][y];
        //标记 此时这个点 为* （说明可能是其中一个点）
        matrix[x][y] = '*';
        
        for(int i = 0; i < 4; i++){
            int a = x + dx[i], b = y + dy[i];
            //只要走不超过矩阵访问 继续走  注意 a b 的范围
            if(a >= 0 && a < matrix.size() && b >= 0 && b < matrix[a].size()){
                if (dfs(matrix, str, u + 1, a, b)) return true;
            }
        }
        //该点 周围四角均不符合条件 把 * 恢复成 原来样子
        matrix[x][y] = t;
        return false;
    }
};
相关文章
0%