Tag: 每日一题 - Hexo

242. Valid Anagram

Posted 2022-04-06Updated 2022-07-27LeetCode / Easya minute read (About 163 words)

242. Valid Anagram

Problem

Given two strings s and t, return true if t is an anagram of s, and false otherwise.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Solution

两数组相等时，直接遍历两个数组并记录各个字符出现的数量。
一个数组遍历时用做加法，另一个做减法。
如果最后每个字符出现的数量均为0，则返回真。

Code

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length()!=t.length()){
            return false;
        }
        int[] dic = new int[26];
        for (int i = 0; i < s.length(); i++){
            dic[s.charAt(i)-'a']++;
            dic[t.charAt(i)-'a']--;
        }
        
        for(int num : dic){
            if ( num != 0 ){
                return false;
            }
        }
        return true;
    }
}

Posted 2022-04-06Updated 2022-04-05LeetCode / Medium / 复习2 minutes read (About 346 words)

11. Container With Most Water

问题
You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).
Find two lines that together with the x-axis form a container, such that the container contains the most water.
Return the maximum amount of water a container can store.
Notice that you may not slant the container.

双指针在首尾，二者容量取决于两者中较小的一个。
贪心算法，保留两个指针上较大的元素，移动较小一边的指针。
由于指针移动时距离只会减小，因此当新的元素比上一个更大时才有可能比之前的容量更大。
遍历一次找到最大容量。
时间复杂度：O(n)

感觉这个移动有点博弈论的味了，每次都移动自己最差的一边，虽然可能变得更差，但是总比不动（或者减小）强，动最差的部分可能找到更好的结果，但是动另一边总会更差或者不变，兄弟们，这不是题，这是人生，逃离舒适圈！！（这解释我觉得无敌了，哈哈哈）

class Solution {
    public int maxArea(int[] height) {
        int best = 0;
        
        int i = 0;
        int j = height.length - 1;
        
        while ( i < j ){
            int product = 0;
            if (height[i] < height[j]){
                product = height[i] * ( j -i );
                i++;
            }
            else{
                product = height[j] * ( j -i );
                j--;
            }
            if ( product > best){
                best = product;
            }
        }
        return best;
    }
}