LeetCode回溯法经典题目

算法学习

求 1+2+3+…+n

求 1+2+3+…+n，要求不能使用乘除法、for、while、if、else、switch、case 等关键字及条件判断语句（A?B:C）。

采用了&&来进行流程控制

1
2
3
4
5
public int Sum_Solution(int n) {
    int ans = n;
    boolean flag=(ans!=0) && ((ans += Sum_Solution(n - 1))!=0);//注意java中不能强转boolean
    return ans;
}

不用加减乘除做加法

写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。

原理是两数相加，可以转化为位运算的异或，进位是与运算。

1
2
3
4
5
6
7
8
public int Add(int num1,int num2) {
    while(num2!=0){
        int temp=num1^num2;
        num2=(num1&num2)<<1;
        num1=temp;
    }
    return num1;
}

二进制中 1 的个数

输入一个整数，输出该数二进制表示中 1 的个数。其中负数用补码表示

注意：关键点是消除原来 n 中的 1，然后判断是否还有 1

1
2
3
4
5
6
7
8
public int NumberOf1(int n) {
    int count=0;
    while(n!=0){
        n=n&(n-1);
        count++;
    }
    return count;
}

数组中重复的数字

在一个长度为 n 的数组里的所有数字都在 0 到 n-1 的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为 7 的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字 2。

空间复杂度 O（n）

可以用一个 boolean 数组来进行标记，如果已经被用过了，那么就重复了。

1
2
3
4
5
6
7
8
9
10
11
12
public boolean duplicate(int numbers[],int length,int [] duplication) {
    boolean[] flag=new boolean[length];
    for(int i=0;i<length;i++){
        if(flag[numbers[i]]){
            duplication[0]=numbers[i];
            return true;
        }
        flag[numbers[i]]=true;
    }
    return false;

}

空间复杂度 O（1）

在原来的数组上进行标记，注意临界条件

1
2
3
4
5
6
7
8
9
10
11
12
public boolean duplicate(int numbers[],int length,int [] duplication) {
    for(int i=0;i<length;i++){
        int index=numbers[i];
        if(index<0) index+=length;
        if(numbers[index]<0){
            duplication[0]=index;
            return true;
        }
        numbers[index]=numbers[index]-length;
    }
    return false;
}