2023-07-15

leetcode learnning

字数统计: 883字 | 阅读时长: 3分

力扣刷题

2023.7.15 刷题记录

有效的括号

题目

题解

class Solution {
    public boolean isValid(String s) {
        int n = s.length();
        if (n % 2 == 1) {
            return false;
        }

        Map<Character, Character> pairs = new HashMap<Character, Character>() {{
            put(')', '(');
            put(']', '[');
            put('}', '{');
        }};
        Deque<Character> stack = new LinkedList<Character>();
        for (int i = 0; i < n; i++) {
            char ch = s.charAt(i);
            if (pairs.containsKey(ch)) {
                if (stack.isEmpty() || stack.peek() != pairs.get(ch)) {
                    return false;
                }
                stack.pop();
            } else {
                stack.push(ch);
            }
        }
        return stack.isEmpty();
    }
}

思路

    本题考察字符串以及栈的使用。注意栈在java中一般有3种
普通队列(一端进另一端出):
    Queue queue = new LinkedList()或Deque deque = new LinkedList()
双端队列(两端都可进出)
    Deque deque = new LinkedList()
堆栈
    Deque deque = new LinkedList()

具体思路：
1.我们遍历给定的字符串 sss。当我们遇到一个左括号时，我们会期望在后续的遍历中，有一个相同类型的右括号将其闭合。
2.由于后遇到的左括号要先闭合，因此我们可以将这个左括号放入栈顶。
3.当我们遇到一个右括号时，我们需要将一个相同类型的左括号闭合。
4.此时，我们可以取出栈顶的左括号并判断它们是否是相同类型的括号。
5.如果不是相同的类型，或者栈中并没有左括号，那么字符串 sss 无效，返回 False。
6.为了快速判断括号的类型，我们可以使用哈希表存储每一种括号。哈希表的键为右括号，值为相同类型的左括号。
7.在遍历结束后，如果栈中没有左括号，说明我们将字符串 sss 中的所有左括号闭合，返回 True否则返回 False
8.注意到有效字符串的长度一定为偶数，因此如果字符串的长度为奇数，我们可以直接返回 False，省去后续的遍历判断过程。

队列的语法学习

动作	插入第一个元素（首部）	插入最后一个元素（尾部）
插入	addFirst(e)	addLast(e)
删除	removeFirst()	addLast(e)
取出	getFirst()	getLast()

等效性	Queue方法	等效Deque方法
	add(e)	addLast(e)
	offer(e)	offerLast(e)
	remove()	removeFirst()
	poll()	pollFirst()
	element()	pollFirst()
	peek()	pollFirst()

等效性	堆栈方法	等效Deque方法
	push(e)	addFirst(e)
	pop()	removeFirst()
	peek()	removeFirst()

键盘行

题目：

思路：

将第一行、第二行字母用字符串表示（包含大小写）
由于题目要求返回String数组，而String数组不能动态更改（初始化大小后数组种会出现null），因此使用ArrayList做存储，最后将ArrayList转换即可
遍历输入的字符串数组，遍历每个字符串，用f,t,s记录一个字符串中出现第一行、第二行、第三行字母的数量，只有f0或t0或s==0时，才符合题意
最后进行ArrayList与String[]转换，即result = (String[])re.toArray(new String[re.size()]);

代码：

class Solution {
    public String[] findWords(String[] words) {
        String firstWords = "qwertyuiopQWERTYUIOP";
        String secondWords = "asdfghjklASDFGHJKL";
        ArrayList<String> re = new ArrayList<>();
        String []result = new String[words.length];
        for(String word : words)
        {
            int f = 0 ,s = 0 ,t=0;
            for(int i = 0 ; i < word.length() ; i++)
            {
                if((f!=0&&s!=0)||(f!=0&&t!=0)||(t!=0&&s!=0))
                {
                    break;
                }
                if(firstWords.indexOf(word.charAt(i)) != -1)
                {
                    f++;
                }
                else if (secondWords.indexOf(word.charAt(i)) != -1)
                {
                    s++;
                }
                else
                {
                    t++;
                }

            }
            if(f == word.length() || s == word.length() || t == word.length())
            {
                re.add(word);
            }
            result = (String[])re.toArray(new String[re.size()]);
        }
        return result;
    }
}