Java List的equals(),hascode(),containsAll() 判断集合相等

一.通过equals(),hascode()判断相等都要求两个List的元素相同,且顺序相同,以下为各自的源码

public boolean equals(Object o) {
        if (o == this)
            return true;
        if (!(o instanceof List))
            return false;

        ListIterator<E> e1 = listIterator();
        ListIterator<?> e2 = ((List<?>) o).listIterator();
        while (e1.hasNext() && e2.hasNext()) {
            E o1 = e1.next();
            Object o2 = e2.next();
            if (!(o1==null ? o2==null : o1.equals(o2)))
                return false;
        }
        return !(e1.hasNext() || e2.hasNext());
    }
public int hashCode() {
        int hashCode = 1;
        for (E e : this)
            hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());
        return hashCode;
    }

注意:这源码和Set的会有不用

二.通过containsAll()判断相等只要元素相同就好了,以下为源码

    public boolean containsAll(Collection<?> c) {
        for (Object e : c)
            if (!contains(e))
                return false;
        return true;
    }

    public boolean contains(Object o) {
        Iterator<E> it = iterator();
        if (o==null) {
            while (it.hasNext())
                if (it.next()==null)
                    return true;
        } else {
            while (it.hasNext())
                if (o.equals(it.next()))
                    return true;
        }
        return false;
    }

 

 

0

删除排序链表中的相同元素

83. 删除排序链表中的重复元素

给定一个排序链表,删除所有重复的元素,使得每个元素只出现一次。

示例 1:

输入: 1->1->2
输出: 1->2
示例 2:

输入: 1->1->2->3->3
输出: 1->2->3
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        if (head.val == head.next.val) {
            while (head.next != null && head.val == head.next.val) {//相当于删除后面相同的节点
                head = head.next;
            }
            if (head.next == null) {//最后相同节点仅剩下一个,如果该节点后面为空,则删除完为空链表
                return head;
            }
        }
        head.next = deleteDuplicates(head.next);
        return head;
    }
}

 

82. 删除排序链表中的重复元素 II

给定一个排序链表,删除所有含有重复数字的节点,只保留原始链表中 没有重复出现 的数字。

示例 1:

输入: 1->2->3->3->4->4->5
输出: 1->2->5
示例 2:

输入: 1->1->1->2->3
输出: 2->3
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
       if (head == null || head.next == null) {
            return head;
        }
        if (head.val == head.next.val) {
            while (head.next != null && head.val == head.next.val) {//相当于删除后面相同的节点
                head = head.next;
            }
            if (head.next == null) {//最后相同节点仅剩下一个,如果该节点后面为空,则删除完为空链表
                return null;
            }
            head = head.next;
            return deleteDuplicates(head);//删除当前节点
        }
        head.next = deleteDuplicates(head.next);
        return head;   
    }
}

return the last

0

子集

78. 子集

给定一组不含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。

说明:解集不能包含重复的子集。

示例:

输入: nums = [1,2,3]
输出:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]
package gongel_first;

import java.util.ArrayList;
import java.util.List;

public class Seventy_eight {
    /**
     * 法一:递归+回溯法
     */
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> list = new ArrayList<Integer>();
        subsets(res, list, nums, 0);
        return res;
    }

    public void subsets(List<List<Integer>> res, List<Integer> temp, int[] nums, int start) {
        res.add(new ArrayList<>(temp));
        if (start == nums.length)
            return;
        for (int i = start; i < nums.length; i++) {
            temp.add(nums[i]);
            subsets(res, temp, nums, i + 1);
            temp.remove(temp.size() - 1);
        }
    }


    /**
     * 法二:位运算
     */
    public List<List<Integer>> subsets2(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        int end = (int) Math.pow(2, nums.length);
        for (int i = 0; i < end; i++)
            ans.add(helper(nums, i));
        return ans;
    }

    //把n化为二进制,0表示不取,1表示取
    public List<Integer> helper(int[] nums, int n) {
        List<Integer> ans = new ArrayList<>();
        int i = 0;
        while (n != 0) {
            if ((n & 1) == 1)//判断二进制最后一位是否为1
                ans.add(nums[i]);
            i++;
            n >>= 1;//右移1位去除最后1位二进制
        }
        return ans;
    }
}
class Solution {
public:
    vector<vector<int>> subsets(vector<int> &nums) {
        if (nums.empty())
            return vector<vector<int>>();
        vector<int> temp;
        vector<vector<int>> ans;
        helper(nums, ans, temp, 0);
        return ans;
    }

    void helper(vector<int> &nums, vector<vector<int>> &ans, vector<int> &temp, int start) {
        ans.push_back(temp);
        if (start == nums.size())
            return;
        for (int i = start; i < nums.size(); i++) {
            temp.push_back(nums[i]);
            helper(nums, ans, temp, i + 1);
            temp.pop_back();
        }
    }
};

90. 子集 II

给定一个可能包含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。

说明:解集不能包含重复的子集。

示例:

输入: [1,2,2]
输出:
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

package gongel_first;

import java.util.*;

public class Ninety {
    /**
     * 递归+回溯+去重
     */
    public void dfs(int[] nums, int start, List<Integer> temp, List<List<Integer>> ans) {
        if (!ans.contains(temp))
            ans.add(new ArrayList<>(temp));
        for (int i = start; i < nums.length; i++) {
            temp.add(nums[i]);
            dfs(nums, i + 1, temp, ans);
            temp.remove(temp.size() - 1);
        }
    }

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        if (nums == null || nums.length == 0)
            return new ArrayList<>();
        Arrays.sort(nums);
        List<Integer> temp = new ArrayList<>();
        List<List<Integer>> ans = new ArrayList<>();
        dfs(nums, 0, temp, ans);
        return ans;
    }
}
class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int> &nums) {
        if (nums.empty())
            return vector<vector<int>>();
        vector<int> temp;
        set<vector<int>> ans;
        sort(nums.begin(), nums.end());
        helper(nums, ans, temp, 0);
        return vector<vector<int>>(ans.begin(), ans.end());
    }

    void helper(vector<int> &nums, set<vector<int>> &ans, vector<int> &temp, int start) {
        ans.insert(temp);
        if (start == nums.size())
            return;
        for (int i = start; i < nums.size(); i++) {
            temp.push_back(nums[i]);
            helper(nums, ans, temp, i + 1);
            temp.pop_back();
        }
    }
};

 

0

全排列

46. 全排列

给定一个没有重复数字的序列,返回其所有可能的全排列。

示例:

输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]
public class Forty_six {
    /**
     * 回溯
     */
    public List<List<Integer>> permute(int[] nums) {
        if (nums == null || nums.length == 0)
            return new ArrayList<>();
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> temp = new ArrayList<>();
        dfs(ans, temp, nums);
        return ans;
    }

    public void dfs(List<List<Integer>> ans, List<Integer> temp, int[] nums) {
        if (temp.size() == nums.length) {
            ans.add(new ArrayList<>(temp));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (!temp.contains(nums[i])) {//temp暂时没有访问过的
                temp.add(nums[i]);
                dfs(ans, temp, nums);
                temp.remove(temp.size() - 1);
            }
        }
    }
}
class Solution {
public:
    vector<vector<int>> permute(vector<int> &nums) {
        vector<int> temp;
        vector<vector<int>> ans;
        helper(nums, temp, ans);
        return ans;
    }

    void helper(vector<int> &nums, vector<int> &temp, vector<vector<int>> &ans) {
        if (temp.size() == nums.size()) {
            ans.push_back(temp);
            return;
        }
        for (int i = 0; i < nums.size(); i++) {
            if (find(temp.begin(), temp.end(), nums[i]) == temp.end()) {
                temp.push_back(nums[i]);
                helper(nums, temp, ans);
                temp.pop_back();
            }
        }
    }
};

47. 全排列 II

给定一个可包含重复数字的序列,返回所有不重复的全排列。

示例:

输入: [1,1,2]
输出:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]
public class Forty_seven {
    /**
     * 回溯
     */
    public List<List<Integer>> permuteUnique(int[] nums) {
        if (nums == null || nums.length == 0)
            return new ArrayList<>();
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> temp = new ArrayList<>();
        List<Integer> visited = new ArrayList<>();//在46题中,temp包含了此功能,但是本题有重复的值
        dfs(ans, temp, nums, visited);
        return ans;
    }

    public void dfs(List<List<Integer>> ans, List<Integer> temp, int[] nums, List<Integer> visited) {
        if (temp.size() == nums.length) {
            List<Integer> t = new ArrayList<>(temp);
            if (!ans.contains(t))//防止重复
                ans.add(t);
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (!visited.contains(i)) {//visited暂时没有访问过的,不能用temp,因为有重复的值
                temp.add(nums[i]);
                visited.add(i);
                dfs(ans, temp, nums, visited);
                temp.remove(temp.size() - 1);
                visited.remove(visited.size() - 1);
            }
        }
    }
}
class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int> &nums) {
        if (nums.empty())
            return vector<vector<int>>();
        vector<int> temp;
        vector<int> visited;
        set<vector<int>> ans;
        helper(nums, temp, visited, ans);
        return vector<vector<int>>(ans.begin(), ans.end());
    }

    void helper(vector<int> &nums, vector<int> &temp, vector<int> &visited, set<vector<int>> &ans) {
        if (temp.size() == nums.size()) {
            ans.insert(temp);
            return;
        }
        for (int i = 0; i < nums.size(); i++) {
            if (find(visited.begin(), visited.end(), i) == visited.end()) {
                visited.push_back(i);
                temp.push_back(nums[i]);
                helper(nums, temp, visited, ans);
                temp.pop_back();
                visited.pop_back();
            }
        }
    }
};
0

移位运算符:<<(左移)、>>(带符号右移)和>>>(无符号右移)

1.左移
  • 在数字没有溢出的前提下,对于正数和负数,左移一位都相当于乘以2的1次方,左移n位就相当于乘以2的n次方
  • 左移的规则只记住一点:丢弃最高位,0补最低位
2.带符号右移
  • 正数右移一位相当于除2,右移n位相当于除以2的n次方, 负数另计算
  • 按二进制形式把所有的数字向右移动对应的位数,低位移出(舍弃),高位的空位补符号位,即正数补零,负数补1
  • 1、正整数的原码、反码、补码完全一样,即符号位固定为0,数值位相同
  • 2、负整数的符号位固定为1,由原码变为补码时,规则如下:
    • 2.1原码符号位1不变,整数的每一位二进制数位求反,得到反码
    • 2.2反码符号位1不变,反码数值位最低位加1,得到补码
  • 3、补码求真值
    • 11111100为负整数=-1*(2**7)+1*(2**6)+1*(2**5)+1*(2**4)+1*(2**3)+1*(2**2)=-4
  • ref: 原码、反码、补码之间的转换和简单运算
-15>>2 = -4
数的二进制码=正数的二进制的补码=正数的二进制码的反码+1
所以-15的二进制码 = 00001111的补码 = ~(00001111)+1 = 11110000+1 = 11110001
>>运算,负数右移且符号位不移的时候,低位去掉,高位(符号位不变,符号位以后的高位)补1
>>>运算,负数右移且符号位也移的时候,低位去掉,高位(符号位前面的高位)补0
所以,-15的右移过程应该是
11110001 -> 11111100(-4)

 

3.无符号右移
  • 右移一位相当于除2,右移n位相当于除以2的n次方。
  • 无符号右移规则和右移运算是一样的,只是填充时不管左边的数字是正是负都用0来填充

ref:https://www.cnblogs.com/blog-cq/p/5793529.html

0