LeetCode中那些應該背下來的經典代碼
Maximum Subarray
問題描述
問題鏈接：https://leetcode.com/problems/maximum-subarray/#/description
Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.
經典解法
public static int maxSubArray(int[] A) {
int maxSoFar=A[0], maxEndingHere=A[0];
for (int i=1;i<A.length;++i){
maxEndingHere= Math.max(maxEndingHere+A[i],A[i]);
maxSoFar=Math.max(maxSoFar, maxEndingHere);
}
return maxSoFar;
}
1
2
3
4
5
6
7
8
136. Single Number中使用異或求解
問題描述
問題鏈接：https://leetcode.com/problems/single-number/#/description
Given an array of integers, every element appears twice except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
經典解法
known that A XOR A = 0 and the XOR operator is commutative, the solution will be very straightforward.
int singleNumber(int A[], int n) {
int result = 0;
for (int i = 0; i<n; i++)
{
result ^=A[i];
}
return result;
}
1
2
3
4
5
6
7
8
526. Beautiful Arrangement中回溯法求解
問題描述
問題鏈接：https://leetcode.com/problems/beautiful-arrangement/#/description
Suppose you have N integers from 1 to N. We define a beautiful arrangement as an array that is constructed by these N numbers successfully if one of the following is true for the ith position (1 ≤ i ≤ N) in this array:
The number at the ith position is divisible by i.
i is divisible by the number at the ith position.
Now given N, how many beautiful arrangements can you construct?
Example 1:
Input: 2
Output: 2
Explanation:
The first beautiful arrangement is [1, 2]:
Number at the 1st position (i=1) is 1, and 1 is divisible by i (i=1).
Number at the 2nd position (i=2) is 2, and 2 is divisible by i (i=2).
The second beautiful arrangement is [2, 1]:
Number at the 1st position (i=1) is 2, and 2 is divisible by i (i=1).
Number at the 2nd position (i=2) is 1, and i (i=2) is divisible by 1.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Note:
N is a positive integer and will not exceed 15.
經典解法
public class Solution {
private int count = 0;
public int countArrangement(int N) {
/*
思路是使用回溯法。如果當前的解滿足要求，就繼續向下走去探索子節點，否則就返回
是一種優秀的剪枝演算法
*/
int[] nums = new int[N + 1];
for(int i = 1; i <= N; i++){
nums[i] = i;
}
backTracking(nums,1);
return count;
}
private void backTracking(int[] nums, int start){
if(start >= nums.length){
count++; // 找到一個解
return;
}
for(int i = start; i < nums.length; i++){
swap(nums,i,start);
if(nums[start] % start == 0 || start % nums[start] == 0){ // 子節點可能有解
backTracking(nums,start + 1);
}
swap(nums,start,i);
}
}
private void swap(int[] nums, int from, int to){
int temp = nums[from];
nums[from] = nums[to];
nums[to] = temp;
}
}
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
38
【LeetCode】357. Count Numbers with Unique Digits
問題描述
問題鏈接：https://leetcode.com/problems/count-numbers-with-unique-digits/#/description
Given a non-negative integer n, count all numbers with unique digits, x, where 0 ≤ x < 10n.
Example:
Given n = 2, return 91. (The answer should be the total numbers in the range of 0 ≤ x < 100, excluding [11,22,33,44,55,66,77,88,99])
Hint:
A direct way is to use the backtracking approach.
經典代碼
Thanks for sharing. I think it could be simplified further. This problem is kind of like permutation + subset, so we start from 0 every recursion and count through the path. Forgive me if anything unclear, here is the code:
public class Solution {
public int countNumbersWithUniqueDigits(int n) {
return doCount(n, new boolean[10], 0);
}
private int doCount(int n, boolean[] used, int d) {
if (d == n) return 1;
int total = 1;
for (int i = (d == 0) ? 1 : 0; i <= 9; i++) {
if (!used[i]) {
used[i] = true;
total += doCount(n, used, d + 1);
used[i] = false;
}
}
return total;
}
}
※網站集群架構實戰（LVS負載均衡Nginx代理緩存Nginx動靜分離等）
※chrome開啟touch屏幕點擊事件
TAG:程序員小新人學習 |