文档章节

LeetCode 第 150 场周赛

o
 osc_g8254g7s
发布于 2019/08/19 22:50
字数 1113
阅读 9
收藏 0

精选30+云产品,助力企业轻松上云!>>>

一、拼写单词(LeetCode-1160

1.1 题目描述

1.2 解题思路

由于给定的chars,每个字母只能用一次,所以用大小为26的数组charsArray来表示a-z(例如charsArray[0]代表字符a可以使用的次数,charsArray[25]代表字符z可以使用的次数),存放某字符的可使用的个数。

遍历单词列表,复制一份charsArray,使用一次,就将单词可使用次数减1。

若需要用到的字符时,该在charsArray的数量为0,则该单词不符合条件

1.3 实现代码


class Solution {
    public int countCharacters(String[] words, String chars) {
        int[] charLib = new int[26];
        int res = 0;
        for (Character character : chars.toCharArray()) {
            charLib[character - 'a']++;
        }
        OK:
        for (String word : words) {
            int len = word.length();
            if (len > chars.length()) {
                continue;
            }
            int[] wordLib = Arrays.copyOf(charLib, 26);
            for (Character character:word.toCharArray()){
                if(--wordLib[character - 'a'] <0){
                    continue OK;
                }
            }
            res += len;
        }
        return res;
    }
}

二、最大层内元素和(LeetCode-1161

2.1 题目描述

2.2 解题思路

使用BFS完成树的层次遍历,计算层的节点值之和,找到最大的值,返回对应的最小的层数。

2.3 实现代码

public int maxLevelSum(TreeNode root) {
        if (root == null) {
            throw new IllegalArgumentException("invalid parameters");
        }

        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        int index = 0;
        int sum = 0;
        //当队列不是空的时候,将队列头移除,将其儿子节点加入队列
        int ceng = 1;
        while (!queue.isEmpty()) {
            int size = queue.size();//记录当前层节点的个数
            TreeNode temp;
            int result = 0;
            //循环size次
            for (int i = 0; i < size; i++) {
                temp = queue.poll();
                result += temp.val;
                if (temp.left != null) {
                    queue.offer(temp.left);
                }
                if (temp.right!= null) {
                    queue.offer(temp.right);
                }
            }
            if (result > sum) {
                    index = ceng;
                    sum = result;
                }
            ceng++;
        }
        return index;
    }

三、地图分析(LeetCode-1162

3.1 题目描述

3.2 解题思路

使用BFS的思想解决

  1. 先找到所有陆地的坐标,放到队列
  2. 从队列中取出陆地坐标,找到离陆地最近的海洋
  3. 若找到海洋,则层数level加1,找到的海洋都当陆地算,海洋的坐标值grid[i][j]变为1,重新放到队列,重复2操作
  4. 若未找到任何海洋,则结束,返回level

3.3 实现代码


public class Solution {

    class Position {
        public int x;
        public int y;

        public Position(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public int maxDistance(int[][] grid) {
        int[] direction = {0, 1, 0, -1, 0};
        int N = grid.length;
        int res = 0;
        Queue<Position> queue = new ArrayDeque<>();
        //找到陆地
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (grid[i][j] == 1) {
                    queue.offer(new Position(i, j));
                }
            }
        }
        //全是海洋或陆地
        if (queue.size() == N * N || queue.isEmpty()) {
            return -1;
        }
        //使用BFS
        while (!queue.isEmpty()) {
            int size = queue.size();
            int r = 0;
            while (size != 0) {
                Position position = queue.poll();
                for (int i = 0; i < direction.length-1; i++) {
                    int nx = position.x + direction[i];
                    int ny = position.y + direction[i + 1];
                    if (nx < 0 || ny < 0 || nx >= N || ny >= N || grid[nx][ny] == 1) {
                        continue;
                    }
                    //将找到的海洋当做陆地,放到队列中
                    grid[nx][ny] = 1;
                    queue.offer(new Position(nx, ny));
                    r++;
                }
                size--;
            }
            //当前层的陆地能找到距离最近的海洋,则结果值+1
            if(r > 0){
                res++;
            }
        }
        return res;
    }


}

四、按字典序排在最后的子串(LeetCode-1163

4.1 题目描述

4.2 解题思路

根据题意。

截取的字符串,只需要选择一个位置k,截取k及之后的字符串即为最终答案(res = s.subString(k))

如何找到这个k?

例如zzaazcc,按照字典排序,肯定是要找到最大的字符z

存在两种情况:

  • 只有一个最大字符z,返回z及之后的所有字符,作为答案
  • 有多个最大字符z,例如存在2个最大字符z,对应的位置分别是x,y,则比较最大字符后面的第一位字符,即比较charArray[x+1]、charArray[y+1],根据k新的位置。

需要考虑一种特殊情况即,两个最大字符是邻位(zz),出现这种情况,我们只取index最小的(zz取前面的z的坐标)。通过charArray[i] != charArray[i-1],来排除。

4.3 实现代码

public class Solution {

    public String lastSubstring(String s) {
        //应该截取的字符串的起始位置res = k
        int k = 0;
        char[] charArray = s.toCharArray();
        int len = charArray.length;
        //找到最大字符首先出现位置k
        for (int i = 1; i < len; i++) {
            if (charArray[i] > charArray[k]) {
                k = i;
            }
        }
        //从k开始找到与k相等的字符,比较字符所在位置之后的第一个字符大小
        for (int i = k + 1; i < len; i++) {
            //考虑 zaazzcc的情况,两个相同字符串z出现,取index最小
            if (charArray[i] == charArray[k] && charArray[i] != charArray[i - 1]) {
                for (int j = 1; k + j < i && i+j < len; j++) {
                    if (charArray[k + j] < charArray[i + j]) {
                        k = i;
                        break;
                    }
                    if (charArray[k + j] > charArray[i + j]) {
                        break;
                    }
                }
            }
        }
        return s.substring(k);
    }

    public static void main(String[] args) {
        String str = "zzaazcc";
        str = "abab";
        str = "leetcode";
        Solution solution = new Solution();
        String res = solution.lastSubstring(str);
        System.out.println(res);
    }

}

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

物联网开发服务开发虚拟设备需要几步?

云栖号快速入门:【点击查看更多云产品快速入门】 不知道怎么入门?这里分分钟解决新手入门等基础问题,可快速完成产品配置操作! 物联网平台设备的正常开发流程是:设备端开发完成,设备上报...

osc_2axit9df
28分钟前
18
0
互联网互联网必看文章墙裂推荐

后端必看文章系列 大型项目架构演进过程及思考的点

code-ortaerc
29分钟前
20
0
ACL2020论文整理 - 知乎

ACL2020录取文章已经放出,链接如下: ACL2020论文集合 www.aclweb.org 为了以后更加方便地阅读论文,也本着一颗开源之心,花一个下午的时间整理了一下相关论文。鉴于本人精力有限,并且也只...

osc_5w65ebjo
30分钟前
10
0
SU(N) Hubbard 模型平均场

osc_31d5oo2i
31分钟前
18
0
Python语言及其应用PDF高清完整版百度云盘免费下载|python基础教程PDF电子书推荐

编辑推荐 本书内容易于理解,而且读起来生动有趣,是编程和Python初学者不可多得的教程。书中首先介绍了Python的基础知识,然后逐渐深入多种主题,结合教程和攻略式风格来讲解Python 3中的概...

osc_nbg2lo7i
32分钟前
17
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部