华为笔试题
#算法 2024-01-17

70. 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int climbStairs(int n) {
        int[] dp = new int[n+1];
        dp[0] = 1;
        dp[1] = 1;
        for(int i = 2;i<=n;i++){
            dp[i] = dp[i-1]+dp[i-2];
        }

        return dp[n];
    }

}

112. 路经总和

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if(root==null)
            return false;
        if(root.left==null && root.right==null)
            return root.val == targetSum;

        return hasPathSum(root.left, targetSum-root.val) || hasPathSum(root.right, targetSum-root.val);
    }
}

509. 斐波那契数

斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1
给定 n ，请计算 F(n) 。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int fib(int n) {
        if(n<2)
            return n;
        int[] num = new int[n+1];
        num[0]=0;
        num[1]=1;
        for(int i=2;i<=n;i++){
            num[i]=num[i-1]+num[i-2];
        }
        return num[n];
    }
}

23. 合并k个有序链表

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        int n = lists.length;
        ListNode ans = null;
        for(int i=0;i<n;i++){
            ans = mergeTwoLists(ans, lists[i]);
        }

        return ans;
    }

    public ListNode mergeTwoLists(ListNode a, ListNode b){
        if (a == null || b == null) {
        return a != null ? a : b;
        }

        ListNode head = new ListNode(0);
        ListNode tail = head, aPtr = a, bPtr = b;

        while(aPtr!=null&&bPtr!=null){
            if(aPtr.val<bPtr.val){
                tail.next = aPtr;
                aPtr = aPtr.next;
            }else{
                tail.next = bPtr;
                bPtr = bPtr.next;
            }
            tail = tail.next;
        }

        tail.next = (aPtr!=null)?aPtr:bPtr;
        return head.next;
    }
}

169. 多数元素

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/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
class Solution {
    private int countInRange(int[] nums, int num, int lo, int hi) {
        int count = 0;
        for (int i = lo; i <= hi; i++) {
            if (nums[i] == num) {
                count++;
            }
        }
        return count;
    }

    private int majorityElementRec(int[] nums, int lo, int hi){
        if(lo == hi)
            return nums[lo];
        
        int mid = (hi-lo)/2 +lo;

        int left = majorityElementRec(nums, lo, mid);
        int right = majorityElementRec(nums, mid+1, hi);

        if(left == right){
            return left;
        }

        int leftCount = countInRange(nums, left, lo, hi);
        int rightCount = countInRange(nums, right, lo, hi);

        return leftCount>rightCount?left:right;
    }

    public int majorityElement(int[] nums){
        return majorityElementRec(nums, 0, nums.length-1);
    }
}

240. 搜索二维矩阵||

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

每行的元素从左到右升序排列。
每列的元素从上到下升序排列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length;

        int x = 0, y = n-1;
        while(x<m&&y>=0){
            if(matrix[x][y]==target)
                return true;
            if(matrix[x][y]>target){
                --y;
            }else{
                ++x;
            }
        }
        return false;
    }
}

84. 柱状图中的最大矩形

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 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
class Solution {
    public int largestRectangleArea(int[] heights) {
        Deque<Integer> stack = new ArrayDeque<>();
        int res = 0;
        stack.push(-1);

        for(int i=0;i<heights.length;i++){
            while(stack.peek()!=-1&&heights[i]<=heights[stack.peek()]){
                int height = heights[stack.pop()];
                int width = i-stack.peek()-1;
                res = Math.max(res, height*width);
            }
            stack.push(i);
        }

        while(stack.peek()!=-1){
            int height = heights[stack.pop()];
            int width = heights.length-stack.peek()-1;
            res = Math.max(res, height*width);
        }

        return res;
    }
}

547. 省份数量

有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。

省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。

给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。

返回矩阵中 省份 的数量。

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
class Solution {
    public int findCircleNum(int[][] isConnected) {
        int[] parent = new int[isConnected.length];
        
        int n = isConnected.length;
        for(int i=0;i<n;i++){
            parent[i] = i;
        }

        for(int i =0;i<n;i++){
            for(int j = i+1;j<n;j++){
                if(isConnected[i][j]==1){
                    union(parent, i, j);
                }
            }
        }
        int pro = 0;
        for(int i =0;i<n;i++){
            if(parent[i]==i){
                pro++;
            }
        }

        return pro;
    }

    public void union(int[] parent, int index1, int index2){
        parent[find(parent, index1)] = find(parent, index2);
    }

    public int find(int[] parent, int index){
        if(parent[index]!=index){
            parent[index] = find(parent, parent[index]);
        }

        return parent[index];
    }
}

DFS

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
class Solution {
    public int findCircleNum(int[][] isConnected) {
        int pro = 0;
        int n = isConnected.length;
        boolean[] visited = new boolean[n];

        for(int i = 0;i<n;i++){
            if(!visited[i]){
                dfs(isConnected, visited, n, i);
                pro++;
            }
        }

        return pro;
    }

    public void dfs(int[][] isConnected, boolean[] visited, int n, int i){
        for(int j=0;j<n;j++){
            if(isConnected[i][j]==1 && !visited[j]){
                visited[j]=true;
                dfs(isConnected, visited, n, j);
            }
        }
    }
}

BFS

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
class Solution {
    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;
        boolean[] visited = new boolean[n];
        int pro = 0;

        Queue<Integer> queue = new LinkedList<>();
        for(int i =0;i<n;i++){
            if(!visited[i]){
                queue.offer(i);
                while(!queue.isEmpty()){
                    int j = queue.poll();
                    visited[j]=true;
                    for(int k = 0;k<n;k++){
                        if(isConnected[j][k]==1 && !visited[k]){
                            queue.offer(k);
                        }
                    }
                }
                pro++;
            }
        }

        return pro;
    }
}

200. 岛屿数量

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

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
class Solution {
    public int numIslands(char[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        int count = 0;

        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(grid[i][j]=='1'){
                    bfs(grid, i, j);
                    count++;
                }
            }
        }

        return count;
    }

    public void bfs(char[][] grid, int i, int j){
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[] {i, j});

        while(!queue.isEmpty()){
            int[] cur = queue.remove();
            i = cur[0];
            j = cur[1];
            if(i>=0&&i<grid.length && j>=0 && j<grid[0].length && grid[i][j]=='1'){
                grid[i][j] = '0';
                queue.add(new int[] {i+1, j});
                queue.add(new int[] {i-1, j});
                queue.add(new int[] {i, j-1});
                queue.add(new int[] {i, j+1});
            }
        }
    }
}

684. 冗余连接

树可以看成是一个连通且 无环 的 无向 图。

给定往一棵 n 个节点 (节点值 1～n) 的树中添加一条边后的图。添加的边的两个顶点包含在 1 到 n 中间，且这条附加的边不属于树中已存在的边。图的信息记录于长度为 n 的二维数组 edges ，edges[i] = [ai, bi] 表示图中在 ai 和 bi 之间存在一条边。

请找出一条可以删去的边，删除后可使得剩余部分是一个有着 n 个节点的树。如果有多个答案，则返回数组 edges 中最后出现的那个。

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
class Solution {
    public int[] findRedundantConnection(int[][] edges) {
        int n = edges.length;
        int[] parent = new int[n+1];
        for(int i=1;i<=n;i++){
            parent[i]=i;
        }

        for(int i = 0;i<n;i++){
            int[] edge = edges[i];
            int node1 = edge[0], node2 = edge[1];
            if(find(parent, node1)!=find(parent, node2)){
                union(parent, node1, node2);
            }else{
                return edge;
            }
        }

        return new int[0];
    }

    public void union(int[] parent, int index1, int index2){
        parent[find(parent, index1)] = find(parent, index2);
    }

    public int find(int[] parent, int index){
        if(parent[index]!=index){
            parent[index] = find(parent, parent[index]);
        }
        return parent[index];
    }
}

209. 长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的 连续
子数组
[numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length;
        int length = Integer.MAX_VALUE;
        int sum = 0;
        int end = 0, start = 0;
        while(end<n){
            sum += nums[end];
            while(sum>=target){
                length = Math.min(length, end-start+1);
                sum -= nums[start];
                start++;
            }
            end++;
        }

        return length == Integer.MAX_VALUE?0:length;
    }
}

3. 无重复字符的最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的 最长
子串的长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int lengthOfLongestSubstring(String s) {
        char[] ch = s.toCharArray();
        int n = s.length();
        int res = 0;
        for(int i =0;i<n;i++){
            Set<Character> hset = new HashSet<>();
            int j = i+1;
            hset.add(ch[i]);
            while(j<n&&!hset.contains(ch[j])){
                hset.add(ch[j]);
                j++;
            }
            res = Math.max(res, hset.size());
        }

        return res;
    }
}

1004. 最大连续1的个数

给定一个二进制数组 nums 和一个整数 k，如果可以翻转最多 k 个 0 ，则返回 数组中连续 1 的最大个数 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int longestOnes(int[] nums, int k) {
        int n = nums.length;
        int res = 0;
        int count = 0;
        int left = 0;
        int right = 0;
        while(right<n){
            if(nums[right]==0)
                count++;
            right++;
            while(count>k){
                if(nums[left]==0)
                    count--;
                left++;
            }
            res = Math.max(res,right-left);
        }

        return res;
    }
}

1208. 尽可能使字符串相等

给你两个长度相同的字符串，s 和 t。

将 s 中的第 i 个字符变到 t 中的第 i 个字符需要 |s[i] - t[i]| 的开销（开销可能为 0），也就是两个字符的 ASCII 码值的差的绝对值。

用于变更字符串的最大预算是 maxCost。在转化字符串时，总开销应当小于等于该预算，这也意味着字符串的转化可能是不完全的。

如果你可以将 s 的子字符串转化为它在 t 中对应的子字符串，则返回可以转化的最大长度。

如果 s 中没有子字符串可以转化成 t 中对应的子字符串，则返回 0。

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
class Solution {
    public int equalSubstring(String s, String t, int maxCost) {
        int n = s.length();
        int res = 0;
        int left = 0;
        int right = 0;
        int sum = 0;
        int[] diff = new int[n];
        for(int i=0;i<n;i++){
            diff[i] = Math.abs(s.charAt(i)-t.charAt(i));
        }

        while(right<n){
            sum += diff[right];
            right++;
            while(sum>maxCost){
                sum -= diff[left];
                left++;
            }
            res = Math.max(res, right-left);
        }

        return res;
    }
}

724. 寻找数组的中心下标

给你一个整数数组 nums ，请计算数组的 中心下标 。

数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。

如果中心下标位于数组最左端，那么左侧数之和视为 0 ，因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。

如果数组有多个中心下标，应该返回 最靠近左边 的那一个。如果数组不存在中心下标，返回 -1 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int pivotIndex(int[] nums) {
        int n = nums.length;
        int[] pre = new int[n];
        int[] after = new int[n];
        pre[0] = nums[0];
        after[n-1] = nums[n-1];
        for(int i =1;i<n;i++){
            pre[i] += pre[i-1] + nums[i];
        }
        for(int i = n-2;i>=0;i--){
            after[i] += after[i+1] + nums[i];
        }

        for(int i = 0;i<n;i++){
            if(pre[i]-nums[i] == after[i]-nums[i])
                return i;
        }

        return -1;
    }
}

560. 和为k的子数组

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。

子数组是数组中元素的连续非空序列。

暴力

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {
    public int subarraySum(int[] nums, int k) {
        int count = 0;
        for (int start = 0; start < nums.length; ++start) {
            int sum = 0;
            for (int end = start; end >= 0; --end) {
                sum += nums[end];
                if (sum == k) {
                    count++;
                }
            }
        }
        return count;
    }
}

前缀和+哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int subarraySum(int[] nums, int k) {
        int n = nums.length;
        int count = 0, pre = 0;
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        for(int i=0;i<n;i++){
            pre += nums[i];
            if(map.containsKey(pre-k)){
                count += map.get(pre-k);
            }
            map.put(pre, map.getOrDefault(pre, 0)+1);
        }

        return count;
    }
}