Zichuan365' Blog HomeArchivesCategoriesGalleryAbout
LeetCode / 笔试真题
|LeetCode笔试真题

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
    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
    #include <iostream>
    #include <vector>
    #include <algorithm>
    #include <numeric>

    using namespace std;

    int main() {
    	int pp[] = { 3,2,4 };
    	int *p = pp;
    	int plen = 3;

    	vector<int>res(plen, 1);
    	for (int i = 1; i < plen; i++) {
    		if (p[i] == p[i - 1])
    			res[i] = 1;
    		if (p[i] > p[i - 1])
    			res[i] = res[i-1]+1;
    		
    		if(p[i] < p[i - 1]&& res[i - 1]>1)
    			res[i] = 1;
    		if (p[i] < p[i - 1] && res[i - 1] == 1) {
    			if (i - 2 < 0) {
    				res[i - 1] = 2;
    				res[i] = 1;
    			}
    			else {
    				res[i] = 1;
    				int tmp = i;
    				while (p[tmp - 2] > p[tmp - 1] && tmp - 2 >= 0) {
    					res[tmp - 2]++;
    					res[tmp - 1]++;
    					tmp--;
    				}
    			}

    		}
    	}
    	int sum = 0;
    	for (int i = 0; i < plen; i++)
    		sum += res[i];


    	cout << sum;
    	return 0;
    }

    int candy(vector<int>& arr) {
    	// write code here
    	int len = arr.size();
    	vector<int>res(len, 1);
    	for (int i = 1; i < len; i++) {
    		if (arr[i] > arr[i - 1])
    			res[i] = res[i - 1] + 1;
    	}
    	for (int i = len - 2; i >= 0; i--) {
    		if (arr[i] > arr[i + 1] && res[i] <= res[i + 1])
    			res[i] = res[i + 1] + 1;
    	}

    	int ans = 0;
    	for (auto it : res) {
    		ans += it;
    	}
    	return ans;
    }

    2.打印矩阵问题

  • 小红书：打印矩阵米字型和十字型

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include<iostream>
#include<vector>

using namespace std;

int main() {

	int N = 0;
	int& P = N;
	int& I = P;

	cin >> N;
	vector<vector<int>>arr(N, vector<int>(N, 0));
	if (N % 2 == 0) {
		//偶数
		for (int i = 0; i < N / 2; i++) {
			int one = i;
			int two = N / 2;
			int three = N - i - 1;
			for (int j = 0; j < N; j++) {
				if (i + j == N - 1)
					continue;

				if (j < one)
					arr[i][j] = 7;
				else if (j > one && j < two)
					arr[i][j] = 8;
				else if (j >= two && j <= three)
					arr[i][j] = 1;
				else if (j > three)
					arr[i][j] = 2;
			}
		}

		for (int i = N / 2; i < N; i++) {
			int three = i;
			int two = N / 2;
			int one = N - i - 1;
			for (int j = 0; j < N; j++) {
				if (i + j == N - 1)
					continue;
				if (j < one)
					arr[i][j] = 6;
				else if (j > one && j < two)
					arr[i][j] = 5;
				else if (j >= two && j < three)
					arr[i][j] = 4;
				else if (j > three)
					arr[i][j] = 3;
			}
		}
	}
	else {
		//奇数
		for (int i = 0; i < N / 2; i++) {
			int one = i;
			int two = N / 2;
			int three = N - i - 1;
			for (int j = 0; j < N; j++) {
				if (j < one)
					arr[i][j] = 7;
				else if (j > one && j < two)
					arr[i][j] = 8;
				else if (j > two && j < three)
					arr[i][j] = 1;
				else if (j > three)
					arr[i][j] = 2;
			}
		}
		for (int i = N / 2 + 1; i < N; i++) {
			int three = i;
			int two = N / 2;
			int one = N - i - 1;
			for (int j = 0; j < N; j++) {
				if (j < one)
					arr[i][j] = 6;
				else if (j > one && j < two)
					arr[i][j] = 5;
				else if (j > two && j < three)
					arr[i][j] = 4;
				else if (j > three)
					arr[i][j] = 3;
			}
		}

	}
	for (int i = 0; i < arr.size(); i++) {
		for (int j = 0; j < arr.size(); j++) {
			cout << arr[i][j] << " ";
		}
		cout << endl;
	}
	system("pause");
	return 0;
}

3.最长的可整合子数组的长度

  • 可整合数组：如果一个数组在排序之后，每相邻两个数差的绝对值都为1，则该数组为可整合数组。

  • 给定一个整型数组arr，请返回其中最大可整合子数组的长度。

  • 解：1.连续数组不包含重复数

    • 2.maxx - minn + 1 = vis.size() 
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      int cal(vector<int> arr) {
      	int maxx = INT_MIN; 
      	int minn = INT_MAX;
      	int res = 0;

      	//以i开始的结果
      	unordered_map<int, int>vis;
      	for (int i = 0; i < arr.size(); i++) {
      		maxx = INT_MIN;
      		minn = INT_MAX;
      		for (int j = i; j < arr.size(); j++) {
      			vis[arr[j]]++;
      			if (vis[arr[j]] > 1)
      				break;

      			maxx = max(maxx, arr[j]);
      			minn = min(minn, arr[j]);
      			if (maxx - minn + 1 == vis.size())
      				res = max(res, maxx - minn + 1);
      		}
      		vis.clear();
      	}
      	return res;
      }

      4.360：老板打卡上下班

      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
      #include <iostream>
      #include <vector>

      using namespace std;

      int main() {
      	int m = 0;
      	int n = 0;
      	cin >> m >> n;

      	int tmp1, tmp2;
      	vector<int>arr(n);
      	int ii = 0;
      	int R = 0;
      	int L = 0;
      	bool flag = true;
      	while (n--) {
      		cin >> tmp1 >> tmp2;
      		arr[ii] = tmp1 - 1;
      		if (tmp2 == 0 && flag) {
      			R = ii;
      			L = ii - 1;
      			flag = false;
      		}	
      		ii++;
      	}
      	if (m == 1) {
      		cout << 1 << endl;
      		return 0;
      	}
      	vector<bool>res(m, true);
      	if (arr[0] == arr.back()) {
      		while (L >= 1 || R <= arr.size() - 2) {
      			if (L >= 1)
      				res[arr[L--]] = false;
      			if (R <= arr.size() - 2)
      				res[arr[R++]] = false;
      		}
      	}
      	else {
      		while (L >= 0 || R <= arr.size() - 1) {
      			if (L >= 0)
      				res[arr[L--]] = false;
      			if (R <= arr.size() - 1)
      				res[arr[R++]] = false;
      		}
      	}
      	for (int i = 0; i < res.size(); i++) {
      		if (res[i])
      			cout << i+1 << " ";
      	}
      	cout << endl;
      	return 0;
      }

      5.华为：做手串种类

  • M种颜色珠子，N种颜色做一串,能做几种

    1
    2
    3
    4
    5
    6
    7
    //1 2 3 4 5 6    当N = 5
    //1 2 3 4     2
    //2 3 4 5     1
    //所以答案： （ M - N）+（ M - N -1） + （ M - N -2） + ...... + 0;
    int res = 0;
    for(int i = 1;i<=M - N;i++)
    	res += i;
文章作者: Inter
文章链接: https://zuizichuan.cn/2020/09/02/LeetCode-%E7%AC%94%E8%AF%95%E7%9C%9F%E9%A2%98/
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Zichuan365' Blog！