文章

每日LeetCode 71-75

2021.4.4 ・ 共 865 字,您可能需要 2 分钟阅读

Tags: LeetCode

编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。

不要给另外的数组分配额外的空间,你必须**原地修改输入数组**、使用 O(1) 的额外空间解决这一问题。

你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。

示例 1:

输入:["h","e","l","l","o"]
输出:["o","l","l","e","h"]
class Solution {
    public void reverseString(char[] s) {
        int left = 0;
        int right = s.length - 1;
        while (left < right) {
            char temp = s[left];
            s[left] = s[right];
            s[right] = temp;
            left++;
            right--;
        }
    }
}

给定两个数组,编写一个函数来计算它们的交集。

示例 1:

输入:nums1 = [1,2,2,1], nums2 = [2,2]
输出:[2]
class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> set1 = new HashSet<Integer>();
        Set<Integer> set2 = new HashSet<Integer>();
        for (int i : nums1) {
            set1.add(i);
        }
        for (int i : nums2) {
            set2.add(i);
        }
        Set<Integer> ans = new HashSet<Integer>();
        if (set1.size() >= set2.size()) {
            for (int i : set2) {
                if (set1.contains(i)) {
                    ans.add(i);
                }
            }
        }
        else {
            for (int i : set1) {
                if (set2.contains(i)) {
                    ans.add(i);
                }
            }
        }
        int index = 0;
        int[] finalAns = new int[ans.size()];
        for (int i : ans) {
            finalAns[index++] = i;
        }
        return finalAns;
    }
}

给定两个数组,编写一个函数来计算它们的交集。

示例 1:

输入:nums1 = [1,2,2,1], nums2 = [2,2]
输出:[2,2]
class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int p1 = 0;
        int p2 = 0;
        int p = 0;
        int[] ans = new int[Math.min(nums1.length, nums2.length)];
        while (p1 < nums1.length && p2 < nums2.length) {
            if (nums1[p1] == nums2[p2]) {
                ans[p] = nums1[p1];
                p++;
                p1++;
                p2++;
            }
            else if (nums1[p1] < nums2[p2]) {
                p1++;
            }
            else if(nums1[p1] > nums2[p2]) {
                p2++;
            }
        }
        return Arrays.copyOfRange(ans, 0, p);
    }
}

给定一个 正整数 num ,编写一个函数,如果 num 是一个完全平方数,则返回 true ,否则返回 false

进阶:不要 使用任何内置的库函数,如 sqrt

示例 1:

输入:num = 16
输出:true
class Solution {
    public boolean isPerfectSquare(int num) {
        if (num == 1) {
            return true;
        }
        long left = 0;
        long right = num /2;
        long mid;
        long mul;
        while (left <= right) {
            mid = left + (right - left) / 2;
            mul = mid * mid;
            if (num == mul) {
                return true;
            }
            else if (mul < num) {
                left = mid + 1;
            }
            else {
                right = mid - 1;
            }
        }
        return false;
    }
}

给定一个二叉树的根节点 root ,返回它的 中序 遍历。

输入:root = [1,null,2,3]
输出:[1,3,2]
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<Integer>();
        inorder(root, ans);
        return ans;
    }
    public void inorder(TreeNode root, List<Integer> ans) {
        if (root == null) {
            return;
        }
        inorder(root.left, ans);
        ans.add(root.val);
        inorder(root.right, ans);
        
    }
}

一般会考这个

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        Deque<TreeNode> stk = new LinkedList<>();
        while (root != null || !stk.isEmpty()) {
            while (root != null) {
                stk.push(root);
                root = root.left;
            }
            root = stk.pop();
            ans.add(root.val);
            root = root.right;
        }
        return ans;
    }
}