Java练习 day4

一、存在重复元素 II

1、题目链接

点击跳转到题目位置

2、代码

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Map<Integer, Integer> mp = new HashMap<Integer, Integer>();
        int n = nums.length;
        for(int i = 0; i < n; ++i){
            if(mp.containsKey(nums[i]) && i - mp.get(nums[i]) <= k){
                return true;
            }
            mp.put(nums[i], i);
        }
    return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

3、知识点

(1) java中利用哈希表来解决问题。

二、用队列实现栈

1、题目链接

点击跳转到题目位置

2、代码

class MyStack {
    Queue<Integer> queue;

    public MyStack() {
        queue = new LinkedList<Integer>();
    }
    
    public void push(int x) {
        int n = queue.size();
        queue.offer(x);
        for(int i = 0; i < n; ++i){
            queue.offer(queue.poll());
        }
    }
    
    public int pop() {
        return queue.poll();
    }
    
    public int top() {
        return queue.peek();
    }
    
    public boolean empty() {
        return queue.isEmpty();
    }
}

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack obj = new MyStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * boolean param_4 = obj.empty();
 */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

3、知识点

(1) 本题目用java中自带的链式队列来解决问题。
(2) poll()用来返回队首元素并删除，offer()表示插入元素到队尾，isEmpty()用来判断队列元素是否为空，peek()用来返回队首元素。

三、翻转二叉树

1、题目链接

点击跳转到题目位置

2、代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root == null){
            return null;
        }
        TreeNode temp = new TreeNode() ;
        invertTree(root.left);
        invertTree(root.right);
        temp = root.left;
        root.left = root.right;
        root.right = temp;
    return root;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

3、知识点

(1) 树中问题，用递归解决即可。

四、汇总区间

1、题目链接

点击跳转到题目位置

2、代码、

class Solution {
    public List<String> summaryRanges(int[] nums) {
        List<String> res = new ArrayList<String>();
        int left = 0;
        int right = 1;
        int n = nums.length;
        if(n == 0){
            return res;
        }
        while(right < n){
            if(nums[right] == nums[right - 1] + 1){
                ++right;
                continue;
            } else{
                StringBuffer temp = new StringBuffer(Integer.toString(nums[left])); 
                if(right > left + 1){
                    temp.append("->");
                    temp.append(Integer.toString(nums[right - 1]));
                }
                res.add(temp.toString());
                left = right;
            }
            ++right; 
        } 
        StringBuffer temp = new StringBuffer(Integer.toString(nums[left])); 
        if(right > left + 1){
            temp.append("->");
            temp.append(Integer.toString(nums[right - 1]));
        }
        res.add(temp.toString());
    return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

3、知识点

(1) java中的字符串数组的操作。

五、2 的幂

1、题目链接

点击跳转到题目位置

2、代码

class Solution {
public:
    bool isPowerOfTwo(int n) {
        return n > 0 && (n & (n-1)) == 0;
    }
};
1
2
3
4
5
6

3、知识点

(1) 2的幂的相关知识，二进制只含有一个1.

六、用栈实现队列

1、题目链接

点击跳转到题目位置

2、代码

class MyQueue {
    Deque<Integer> inStack;
    Deque<Integer> outStack;

    public MyQueue() {
        inStack = new ArrayDeque<Integer>();
        outStack = new ArrayDeque<Integer>();
    }

    public void push(int x) {
        inStack.push(x);
    }

    public int pop() {
        if (outStack.isEmpty()) {
            in2out();
        }
        return outStack.pop();
    }

    public int peek() {
        if (outStack.isEmpty()) {
            in2out();
        }
        return outStack.peek();
    }

    public boolean empty() {
        return inStack.isEmpty() && outStack.isEmpty();
    }

    private void in2out() {
        while (!inStack.isEmpty()) {
            outStack.push(inStack.pop());
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

3、知识点

(1) 两个栈来解决。

七、回文链表

1、题目链接

点击跳转到题目位置

2、代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        while(head != null){
            res.add(head.val);
            head = head.next;
        }
        int left = 0;
        int right = res.size() - 1;
        while(left <= right){
            if(res.get(left) != res.get(right)){
                return false;
            }
            left++;
            right--;
        }
    return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

3、知识点

(1) 运用到一些关于java中数组的知识。

八、有效的字母异位词

1、题目链接

点击跳转到题目位置

2、代码

class Solution {
    public boolean isAnagram(String s, String t) {
        Map<Character, Integer> mp = new HashMap<Character, Integer>();
        int n = s.length();
        int m = t.length();
        if(m != n){
            return false;
        }
        for(int i = 0; i < n; ++i){
            char ch = s.charAt(i);
            mp.put(ch, mp.getOrDefault(ch, 0) + 1);
        }
        for(int i = 0; i < m; ++i){
            char ch = t.charAt(i);
            mp.put(ch, mp.getOrDefault(ch, 0) - 1);
            if(mp.get(ch) < 0){
                return false;
            }
        }
    return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

3、知识点

(1) Java中关于哈希表的知识。

九、二叉树的所有路径

1、题目链接

点击跳转到题目位置

2、代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public void Find(TreeNode root, String ret, List<String> res){
        if(root != null){
            StringBuffer s = new StringBuffer(ret);
            s.append(Integer.toString(root.val));
        
            if(root.left == null && root.right == null){
                res.add(s.toString());
            } else{
                s.append("->");
                Find(root.left, s.toString(), res);
                Find(root.right, s.toString(), res);
            }  
        }
    }

    public List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new ArrayList<String>();
        Find(root, "", res);
    return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

十、各位相加

1、题目链接

点击跳转到题目位置

2、代码

class Solution {
    public int addDigits(int num) {
        int num1 = 0;
        while(num > 0){
            num1 += (num % 10);
            num /= 10;
        }
        if(num1 >= 0 && num1 < 10){
            return num1;
        }
    return addDigits(num1);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

3、知识点

(1) 使用递归，每次个位相加得到结果判断是否已经是个位数，如果是就返回结果。

十一、丑数

1、题目链接

点击跳转到题目位置

2、代码

class Solution {
    public boolean isUgly(int n) {
        if(n <= 0){
            return false;
        }
        int[] factor = {2, 3, 5};
        for(int i = 0; i < 3; ++i){
            int factors = factor[i];
            while(n % factors == 0){
                n /= factors;
            }
        } 
    return n == 1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

3、知识点

(1) 模拟即可。

十二、丢失的数字

1、题目链接

点击跳转到题目位置

2、代码

class Solution {
    public int missingNumber(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        for(int i = 0; i < n; ++i){
            if(nums[i] != i){
                return i;
            }
        }
    return n;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

3、知识点

(1) Java中的排序。

十三、第一个错误的版本

1、题目链接

点击跳转到题目位置

2、代码

/* The isBadVersion API is defined in the parent class VersionControl.
      boolean isBadVersion(int version); */

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int ans = -1;
        int left = 1;
        int right = n;
        while(left <= right){
            int mid = ((right - left) >> 1) + left;
            if(isBadVersion(mid) == true){
                ans = mid;
                right = mid - 1;
            } else{
                left = mid + 1;
            }
        }
    return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

3、知识点

(1) 二分搜索。

十四、移动零

1、题目链接

点击跳转到题目位置

2、代码

class Solution {
    public void moveZeroes(int[] nums) {
        int left = 0;
        int n = nums.length;
        int right = 1;
        while(left < n){
            while(left < n && nums[left] != 0){
                ++left;
            }
            if(left == n){
                return ;
            } 
            right = left + 1;
            while(right < n && nums[right] == 0){
                ++right;
            }
            if(right == n){
                return ;
            }
            nums[left] = nums[right];
            nums[right] = 0;
            ++left;
        }
    return ;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

3、知识点

(1) 双指针。

十五、单词规律

1、题目链接

点击跳转到题目位置

2、代码

class Solution {
    public boolean wordPattern(String pattern, String str) {
        Map<String, Character> str2ch = new HashMap<String, Character>();
        Map<Character, String> ch2str = new HashMap<Character, String>();
        int m = str.length();
        int i = 0;
        for (int p = 0; p < pattern.length(); ++p) {
            char ch = pattern.charAt(p);
            if (i >= m) {
                return false;
            }
            int j = i;
            while (j < m && str.charAt(j) != ' ') {
                j++;
            }
            String tmp = str.substring(i, j);
            if (str2ch.containsKey(tmp) && str2ch.get(tmp) != ch) {
                return false;
            }
            if (ch2str.containsKey(ch) && !tmp.equals(ch2str.get(ch))) {
                return false;
            }
            str2ch.put(tmp, ch);
            ch2str.put(ch, tmp);
            i = j + 1;
        }
        return i >= m;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

3、知识点

(1) 哈希表。