0%

LeetCode算法

发表于 分类于
本文字数： 阅读时长 ≈

LeetCode算法

1，TwoSum问题
给定数组arr = {2,3,5,7,12};一个target(int型，例如target=9)，求数组中两个元素之后等于target的两个元素的下表，并把它们的下标以一个二元数组的形式返回，在这题中，2 + 7等于9，也就是0下标和3下标的元素之和为9。所以返回 target_arr = {0,3};我们用打印数组元素的方式输出更直观。代码如下：

主代码(求下表数组的代码)：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public static int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> m = new HashMap<Integer, Integer>();
        int[] res = new int[2];
        for (int i = 0; i < nums.length; ++i) {
            m.put(nums[i], i);
        }
        for (int i = 0; i < nums.length; ++i) {
            int t = target - nums[i];
            if (m.containsKey(t) && m.get(t) != i) {
                res[0] = i;
                res[1] = m.get(t);
                break;
            }
        }
        return res;
    }
}

这里用了HashMap(哈希表结构)。
主方法中调用：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
printArr函数代码：

public static void printArr(int[] arr) {
		System.out.print("[");
		for (int i = 0; i < arr.length; i++) {
			if (i != arr.length - 1) {
				System.out.print(arr[i] + " ");
			} else {
				System.out.print(arr[i] + "]");
			}
		}
		System.out.println();
}

public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] arr = {2,3,5,7,12};
		int target = 9;
		int [] target_arr = Solution.twoSum(arr, target);
		printArr(target_arr);
}

注：这里有一个printArr函数，其实就是一个打印数组元素的函数，可以理解为code的定制。代码如上所示。
主函数输出结果为：

1
[0 3]

还有一个更直接暴力的算法，时间复杂度为O(n^2)，不过面试不要这样写，面试会直接挂的。
暴力方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution_2 {
	public static int[] twoSum (int[] nums,int target) {
		int[] res = new int[2];
		
		for (int i = 0; i < nums.length; i++) {
			for (int j = i + 1; j < nums.length; j++) {
				if ((nums[i] + nums[j]) == target) {
					res[0] = i;
					res[1] = j;
				}
			}
		}
		
		return res;
	}
}

2，Three_Sum问题
和原题意思差不多，不过变成了三个数相加等于target。
暴力代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution_4 {
	public static int[]  threeSum (int[] arr,int target) {
		int[] res = new int[3];
		for (int i = 0; i < arr.length; i++) {
			for (int j = i + 1; j < arr.length; j++) {
				for (int j2 = j+1; j2 < arr.length; j2++) {
					if ((arr[i] + arr[j]+ arr[j2] )== target) {
						res[0] = i;
						res[1] = j;
						res[2] = j2;
					}
				}
			}
		}
		
		return res;
	}
}

3,