LeetCode刷题（一）

面试题58 - II. 左旋转字符串

题目：字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。
用时：100%，内存:100%
实现：

class Solution {
    public String reverseLeftWords(String s, int n) {
        String str = s.substring(0,n);
        String str2 = s.substring(n);
        return str2.concat(str);
    }
}

LCP 01.猜数字

题目：小A 和小B 在玩猜数字。小B 每次从 1, 2, 3 中随机选择一个，小A 每次也从 1, 2, 3 中选择一个猜。他们一共进行三次这个游戏，请返回小A 猜对了几次？
用时：100%，内存：5.88%
实现：

class Solution {
        public int game(int[] guess, int[] answer) {
            int cnt=0;
            for(int i = 0;i<3;i++){
                if(guess[i] == answer[i]){
                    cnt++;
                }
            }
            return cnt;
        }
    }

1295. 统计位数为偶数的数字

题目：给你一个整数数组 nums，请你返回其中位数为偶数的数字的个数。
用时：73.13%，内存：5.88%
实现：

class Solution {
    public int findNumbers(int[] nums) {
        int count = 0;
        for(int num:nums){
            String numStr = String.valueOf(num);
            int len = numStr.length();
            if(len%2 == 0) count++;
        }
        return count;
    }
}

21. 合并两个有序链表

题目：将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
用时：100.0%，内存：41.12%
实现：

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null) return l2;
        else if(l2 == null) return l1;
        else{
            if(l1.val < l2.val){
                l1.next = mergeTwoLists(l1.next,l2);
                return l1;
            }else{
                l2.next = mergeTwoLists(l1, l2.next);
                return l2;
            }
        }
    }
}

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

题目：给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。
用时：54.06%，内存：5.2%
实现：

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length(), ans = 0;
        Map<Character, Integer> map = new HashMap<>();
        for (int end = 0, start = 0; end < n; end++) {
            char alpha = s.charAt(end);
            if (map.containsKey(alpha)) {
                start = Math.max(map.get(alpha), start);
            }
            ans = Math.max(ans, end - start + 1);
            map.put(s.charAt(end), end + 1);
        }
        return ans;
    }
}

45. 跳跃游戏 II

题目：给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。
用时：94.93%，内存：5.2%
实现：

class Solution {
    public int jump(int[] nums) {
        int end = 0;
        int maxPosition = 0; 
        int steps = 0;
        for(int i = 0; i < nums.length - 1; i++){
            maxPosition = Math.max(maxPosition, nums[i] + i); 
            if( i == end){ 
                end = maxPosition;
                steps++;
            }
        }
    return steps;
    }
}

98. 验证二叉搜索树

题目：给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

用时：100.00%，内存：13.4%
实现：

class Solution {
     public boolean isValidBST(TreeNode root) {
        return dfs(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    boolean dfs(TreeNode node, long lower, long upper) {
        if (node == null)  return true;
        if (node.val <= lower) return false;
        if (node.val >= upper) return false;
        if (!dfs(node.left, lower, node.val)) return false;
        if (!dfs(node.right, node.val, upper)) return false;
        return true;
    }
}