# Coding-Interviews

**Repository Path**: xwr96/Coding-Interviews

## Basic Information

- **Project Name**: Coding-Interviews
- **Description**: 包括但不限于刷题经验、算法模板、后端需要掌握的基础知识等。
- **Primary Language**: Java
- **License**: Apache-2.0
- **Default Branch**: main
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 3
- **Forks**: 1
- **Created**: 2021-04-25
- **Last Updated**: 2022-06-20

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# Coding-Interviews

## 需要自己创建数据结构或是数据类型时的技巧
**要是构造函数有参数时，直接在类名外面创造对象，然后在参数里面直接`this.xx=xx`**

要是类没有参数时，直接在类外面创建对象，然后在里面调用就行。

```java
Map<Integer,Integer> dict;
    List<Integer> list;
    Random r=new Random();
    /** Initialize your data structure here. */
    public RandomizedSet() {
        dict=new HashMap<>();
        list=new ArrayList<>();
    }
```

## 数组+哈希表可以高效的既实现查找、删除、插入都是O(1)时间复杂度的算法
1、如果想高效地，等概率地随机获取元素，就要使用数组作为底层容器。

2、如果要保持数组元素的紧凑性，可以把待删除元素换到最后，然后 pop 掉末尾的元素，这样时间复杂度就是 O(1) 了。当然，我们需要额外的哈希表记录值到索引的映射。

## Java运算符优先级

优先级记忆方法：单目乘除为关系，逻辑三目后赋值

## 易错点
- 新建一个数值：new int[]{ , , }; **需要用大括号**
- 数组排序是Arrays.sort(nums)，List排序是collections.sort();
- 把数组转换为List需要用到API：Arrays.asList(),转换之后不能用List的add或是其它方法。
- 把list集合转换为数组需要用到API:Collection.toArray()
- 数组添加值不能用add方法，而是直接等号赋值。
- String类型只能通过"+"号来添加新的字符串，因为string类型是不可变类型。如果想要通过append()方法就需要把**String类型变为StringBuilder类型**，再通过方法 **.toString()** 转换为string类型。
- 在Integer类中有静态方法**toBinaryString**方法，此方法返回int变量的二进制表示的字符串。同理，Integer类中也提供了**toHexString（int i）方法和toOctalString**方法来分别返回int变量的16进制表示和8进制表示字符串。
- n&(n-1) 这个操作是算法中常见的，作用是消除数字 n 的二进制表示中的最后一个 1。
![图片](https://labuladong.gitee.io/algo/pictures/%E4%BD%8D%E6%93%8D%E4%BD%9C/1.png)

- **如果只有一个数字出现一次，其他数字都出现奇数次，要求求出只出现一个数字的值。**我们可以用下面代码来解决。

```Java
    // n是出现的次数
    public int findOnce(int[] nums, int n) {
        int bitLength = 32;
        int res = 0;
        for (int i = 0; i < bitLength; i++) {
            int oneCount = 0;
            for (int j = 0; j < nums.length; j++) {
                oneCount += (nums[j] >>> i) & 1;
            }
            if (oneCount % n != 0)
                res |= (1 << i);
        }
        return res;
    }

```
- 字符串转换为数字，代码简单写为：`s.charAt(i)-'0'`
- 数字转为字母,代码直接为`数字+'A'` A的ascii码为65.
- **不需要额外空间的方法，就往位运算上想**
- java 对于找出连续数出现的各种奇怪的场景，数组桶永远是好的选择,即重新再new一个数组。
- isDigit() 方法用于判断指定字符是否为数字。isLetter() 方法用于判断指定字符是否为字母,isSpaceChar()方法判断是否为空格。`Character.isLetter('c')`
- trim() 方法用于删除字符串的**头尾空白符**。`str.trim()`
- HashSet集合**不能直接排序**,需要**转换为hashmap排序**或是用TreeSet直接存储.
- 当判断一个数是否是2的幂次方时,可以直接`n&(n-1)==0`判断

- 如果数字很大，即可以用**BigInteger**这个大数相乘的类。加减乘除可以调用方法：
```Java
new BigInteger()
add()、subtract()、multiply()、divide()
```
- 二维数组二分查找时，怎么转换为[][]
```Java
int begin, mid, end;
begin = mid = 0;
int len1 = matrix.length, len2 = matrix[0].length;
end = len1 * len2 - 1;
while (begin < end) {
    mid = (begin + end) / 2;
    if (matrix[mid / len2][mid % len2]) // 二维数组展开之后再还原的坐标写法
 ```           
 - 表达式的计算一般可以借助数据结构「栈」完成，特别是带有括号的表达式。我们将暂时还不能确定的数据存入栈，确定了优先级最高以后，一旦可以计算出结果，我们就把数据从栈里取出，整个过程恰好符合了「后进先出」的规律。求解没有括号的中缀表达式的时候，可以用一句顺口溜来概括：**遇到乘除立即算，遇到加减先入栈。**

- 二维数组得到一维数组
```Java
int[][] intvs;
int[] intv = intvs[i];
```
- 看到要求两个整数 x,y 如何**拼接得到结果更大时**，就想到先转字符串，然后**比较 x+y 和 y+x**。上述排序规则满足传递性，两个元素比较就可以确定它们在排序以后的相对位置关系。
- **compareToIgnoreCase() 方法用于按字典顺序比较两个字符串，不考虑大小写**。
```Java
public class Test {

    public static void main(String args[]) {
        String str1 = "STRINGS";
        String str2 = "Strings";
        int result = str1.compareToIgnoreCase( str2 );
        System.out.println(result);  //结果为0
    }
}
```
- 栈结构的建立：`Deque<Character> stack=new LinkedList<>();`

### 异或规律
交换律：a ^ b ^ c <=> a ^ c ^ b

任何数于0异或为任何数 0 ^ n => n

相同的数异或为0: n ^ n => 0

var a = [2,3,2,4,4]

2 ^ 3 ^ 2 ^ 4 ^ 4等价于 2 ^ 2 ^ 4 ^ 4 ^ 3 => 0 ^ 0 ^3 => 3（对应LeetCode中136：只出现一次的数字）

### 进制运算的本质代码
```Java
 public int reverseBits(int n) { //n表示无符号32位进制数
        int res=0;
        for(int i=0;i<32;i++){
            res<<=1;
            res+=1&n;
            n>>=1;
        }
        return res;
    }
```
## 格式化数字用DecimalFormat类
```Java
public class TestNumberFormat{ 
　　public static void main(String[]args){
　　　　double pi =3.1415927;　//圆周率
　　　　//取一位整数
　　　　System.out.println(new DecimalFormat("0").format(pi));　　　//3
　　　　//取一位整数和两位小数
　　　　System.out.println(new DecimalFormat("0.00").format(pi));　//3.14
　　　　//取两位整数和三位小数，整数不足部分以0填补。
　　　　System.out.println(new DecimalFormat("00.000").format(pi));// 03.142
　　　　//取所有整数部分
　　　　System.out.println(new DecimalFormat("#").format(pi));　　　//3
　　　　//以百分比方式计数，并取两位小数
　　　　System.out.println(new DecimalFormat("#.##%").format(pi));　//314.16%
　　 　long c =299792458;　　//光速
　　　　//显示为科学计数法，并取五位小数
　　　　System.out.println(new DecimalFormat("#.#####E0").format(c));　//2.99792E8
　　　　//显示为两位整数的科学计数法，并取四位小数
　　　　System.out.println(new DecimalFormat("00.####E0").format(c));　//29.9792E7
　　　　//每三位以逗号进行分隔。
　　　　System.out.println(new DecimalFormat(",###").format(c));　　　//299,792,458
　　　　//将格式嵌入文本
　　　　System.out.println(new DecimalFormat("光速大小为每秒,###米。").format(c));
  
　　}
  
```
### 遍历HashMap里的key和value
```Java
for (Map.Entry<T, T> entry : map.entrySet()) {
   System.out.println("key= " + entry.getKey() + " and value= " + entry.getValue());
  }
  
```

### Arrays.sort重新排序(改为o1升序排序，o2降序排序)
```java
Arrays.sort(intervals, new Comparator<int[]>() {
      @Override
      public int compare(int[] o1, int[] o2) {
        // Sort by start point.
        // If two intervals share the same start point,
        // put the longer one to be the first.
        return o1[0] == o2[0] ? o2[1] - o1[1]: o1[0] - o2[0];
      }
    });

```
或者写成lambda表达式
```Java
Arrays.sort(intvs, (a, b) -> {
            if (a[0] == b[0]) {
                return b[1] - a[1];
            }
            return a[0] - b[0]; 
        });
```
**lambda表达式中，如果返回值大于0，表示a>b，则按(a,b)排序，如果小于0则表示a<b，按(b,a)排序**。Arrays.sort()中Comparator返回正值则发生交换。
## 遇到重复元素去除重复元素
用双指针
```java
int p=0,q=1;
        while(q<n){
            if(nums[p]!=nums[q]){
                nums[p+1]=nums[q];
                p++;
            }
            q++;
        }
```
## 求进制的模板。转换成几进制，就先求余几，然后再除以几，最后再倒序输出
```Java
List<Integer> list=new ArrayList<>();
        while(n!=0){
            list.add(n%k);
            n/=k;
        }
        int res=0;
        for(int i=list.size()-1;i>=0;i--){
            list.get(i);
        }
        
```
## 整数反转思路
用栈？或者把整数变成字符串，再去反转这个字符串？
这两种方式是可以，但并不好。实际上我们只要能拿到这个整数的 末尾数字 就可以了。

例如将12345反转：

1、将12345 % 10 得到5，之后将12345 / 10\
2、将1234 % 10 得到4，再将1234 / 10\
3、将123 % 10 得到3，再将123 / 10\
4、将12 % 10 得到2，再将12 / 10\
5、将1 % 10 得到1，再将1 / 10

## 计算二进制表达中 1 的数量的函数

`Integer.bitCount()`

## Java copyValueOf() 复制n次字符串方法。方法copyValueOf()用于将字符数组复制到String。这里需要注意的是，此方法不会将内容附加到String中，而是将现有的字符串值替换为数组的字符序列。
```Java
public static String copyValueOf(char[] data, int offset, int  count)
```

| 参数     | 描述                   |
|--------|----------------------|
| data   | 一个字符数组               |
| offset | 一个int值，表示char数组的开始索引 |
| count  | 一个int值，表示char的数组长度   |

例子：
```Java
public class CopyValueOfExample {
   public static void main(String args[]) {
       char[] data = {'a','b','c','d','e','f','g','h','i','j','k'};
       String str1 = "Text";
       String str2 = "String";
       //Variation 1:String copyValueOf(char[] data)
       str1 = str1.copyValueOf(data);
       System.out.println("str1 after copy: " + str1);

       //Variation 2:String copyValueOf(char[] data,int offset,int count)
       str2 = str2.copyValueOf(data, 5, 3 );
       System.out.println("str2 after copy: " + str2);
   }
}
```
输出：
```Java
str1 after copy: abcdefghijk
str2 after copy: fgh
```

## 异或运算（一看到异或就要想到前缀和）
![异或区间和](https://gitee.com/xwr96/Coding-Interviews/raw/main/Images/7.jpeg)
从而，数组 arr 的子区间 [i,j][i,j] 的元素异或和为可表示为：![](https://images.gitee.com/uploads/images/2021/0518/100201_e71a708d_6580894.jpeg "1.jpg")


```
int n=arr.length;
int[] s=new int[n+1]; //s为前缀和，s[0]=0,s[1]=arr[0]
```


**这种规律在做题很有用！**

#### 二维数组前缀和
二维数组前缀和公式如下：
![公式](https://gitee.com/xwr96/Coding-Interviews/raw/main/Images/8.png)

![输入图片说明](https://gitee.com/xwr96/Coding-Interviews/raw/main/Images/10.png)

## java compareTo()方法
compareTo() 方法用于将 Number 对象与方法的参数进行比较。可用于比较 Byte, Long, Integer等。

该方法用于两个相同数据类型的比较，两个不同类型的数据不能用此方法来比较。

## java codePointAt()方法
codePointAt()方法在字符串的指定索引处返回字符的Unicode值。第一个字符的索引为0，第二个字符的索引为1，依此类推。 

## 除数向上取整
> cnt = (x + speed - 1) / speed;或是为了避免浮点数造成的潜在误差，直接转化为整数之间的比较。后面有几个小数点就乘以几百

## List<String> 转换为String[]

```Java
int size=res.size();
        String[] ans=new String[size];//数组得指定大小size
        for(int i=0;i<size;i++){
            ans[i]=res.get(i);
        }
        return ans;
```
## 将字符串转换为数组方法
//将字符串数组ArrayList转化为String类型数组
`return list.toArray(new String[list.size()]);`

## LinkedList实现栈、队列、双向队列API
```Java
队列
Queue<T> queue = new LinkedList<T>();
     
queue.add("zero");
queue.offer("one");
queue.pull("two");
queue.peek()

栈
Deque<T> deque = new LinkedList<T>();
deque.push("a");
deque.pop("b");
deque.peek();
```
栈和队列只是双端队列的特殊情况，它们的方法都可以使用双端队列的方法替代，使用不同的名称和方法，概念上更为清晰。看看Deque接口里面的方法：
![](https://gitee.com/xwr96/Coding-Interviews/raw/main/Images/9.png)