91. 不同路径（多维动态规划/不同路径/62）

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
假设：1 <= m, n <= 100；题目数据保证答案小于等于 2 * $(10)^9$。
示例：输入：m = 3, n = 7；输出：28。

【分析】
方法1：遍历整个矩阵，使用二维数组，时间复杂度O(m*n)，空间复杂度O(m*n)。
方法2：使用一维数组，时间复杂度O(m*n)，空间复杂度O(n)。

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
public class Solution {
    public int UniquePaths1(int m, int n) {
        int[,] dp=new int[m,n];
		//初始化第一行
		for(int j=0;j<n;j++){
			dp[0,j]=1;
		}
		//初始化第一列
		for(int i=0;i<m;i++){
			dp[i,0]=1;
		}
		
		for(int i=1;i<m;i++){
			for(int j=1;j<n;j++){
				dp[i,j]=dp[i-1,j]+dp[i,j-1];//累加左边一格和上面一格的值，表示走到这一格的路径和
			}
		}
		
		return dp[m-1,n-1];
    }
	
	public int UniquePaths2(int m, int n){
		int[] dp=new int[n];//n列
		//初始化第一行
		for(int j=0;j<n;j++){
			dp[j]=1;
		}
		
		for(int i=1;i<m;i++){
			for(int j=1;j<n;j++){
				dp[j]+=dp[j-1];//把横向和纵向的路径累加在一起
			}
		}
		
		return dp[n-1];
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Solution {
    public int UniquePaths1(int m, int n) {
        int[][] dp=new int[m][n];
		//初始化第一行
		for(int j=0;j<n;j++){
			dp[0][j]=1;
		}
		//初始化第一列
		for(int i=0;i<m;i++){
			dp[i][0]=1;
		}
		
		for(int i=1;i<m;i++){
			for(int j=1;j<n;j++){
				dp[i][j]=dp[i-1][j]+dp[i][j-1];
			}
		}
		
		return dp[m-1][n-1];
    }
}

96. 只出现一次的数字（技巧/136）

给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。
假设：1 <= nums.length <= 3 $(10)^4$；-3 $(10)^4$ <= nums[i] <= 3 * $(10)^4$；除了某个元素只出现一次以外，其余每个元素均出现两次。
示例：输入：nums = [2,2,1]，输出：1。

【分析】
将所有数字进行异或操作。
原理1：任何数与0异或，得到该数本身；
原理2：两个相同的数进行异或，得到0。
结合这两个原理，所有出现两次的数两两异或为0，剩下单独的数与0异或为该数。

1
2
3
4
5
6
7
8
9
public class Solution{
	public int SingleNumber(int[] nums){
		int single=0;
		foreach(int num in nums){
			single^=num;
		}
		return single;
	}
}
1
2
3
4
5
6
7
8
9
public class Solution{
	public int SingleNumber(int[] nums){
		int single=0;
		for(int num:nums){
			single^=num;
		}
		return single;
	}
}