# LeetCode经典算法题：打家劫舍java详解

#### 解题思路与代码

    static int maxMoney(int[] nums,int index){
if (nums == null || index < 0) {
return 0;
}
if (index == 0) {
return nums[0];
}
return Math.max(maxMoney(nums,index - 2) + nums[index], maxMoney(nums,index
- 1));
}
static int maxMoney(int[] nums){
if (nums == null || nums.length == 0) {
return 0;
}
int length = nums.length;
if (length == 1) {
return nums[0];
}

/*
int[] dp = new int[length];
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for (int i = 2; i < length; i++) {
dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
}
return dp[length - 1];
*/

int first = nums[0], second = Math.max(nums[0], nums[1]);
for (int i = 2; i < length; i++) {
int temp = second;
second = Math.max(first + nums[i], second);
first = temp;
}
return second;
}

##### 如果房子首尾相连：
    public int rob(int[] nums) {
int length = nums.length;
if (length == 1) {
return nums[0];
} else if (length == 2) {
return Math.max(nums[0], nums[1]);
}
return Math.max(robRange(nums, 0, length - 2), robRange(nums, 1, length -
1));
}
public int robRange(int[] nums, int start, int end) {
int first = nums[start], second = Math.max(nums[start], nums[start + 1]);
for (int i = start + 2; i <= end; i++) {
int temp = second;
second = Math.max(first + nums[i], second);
first = temp;
}
return second;
}

    public int rob(TreeNode root) {
int[] rootStatus = dfs(root);
return Math.max(rootStatus[0], rootStatus[1]);
}
public int[] dfs(TreeNode node) {
if (node == null) {
return new int[]{0, 0};
}
int[] l = dfs(node.left);
int[] r = dfs(node.right);
int selected = node.val + l[1] + r[1];
int notSelected = Math.max(l[0], l[1]) + Math.max(r[0], r[1]);
return new int[]{selected, notSelected};
}



## 预测赢家

### 解题思路与代码

 static int maxScore(int[] nums, int l, int r) {
//剩下一个值，只能取该值
if (l == r) {
return nums[l];
}
int selectLeft =0, selectRight=nums.length-1;
//剩下大于两个值，先手选一边(使自己得分最高的一边)，后手则选使对手得分最低的一边
if ((r - l) >= 2) {
selectLeft = nums[l] +Math.min(maxScore(nums, l+2, r),maxScore(nums,
l+1, r-1));
selectRight = nums[r] +Math.min(maxScore(nums, l+1, r-1),maxScore(nums,
l, r-2));
}
//剩下两个值，取较大的
if ((r - l) == 1) {
selectLeft = nums[l];
selectRight = nums[r];
}
return Math.max(selectLeft, selectRight);
}
int getScore(int[] nums, int start, int end) {
int selectLeft, selectRight;
int gap = end - start;
if (gap == 0) {
return nums[start];
} else if (gap == 1) { // 此时直接取左右的值就可以
selectLeft = nums[start];
selectRight = nums[end];
} else if (gap >= 2) { // 如果gap大于2，递归计算selectLeft和selectRight
// 计算的过程为什么用min，因为要按照对手也是最聪明的来计算。
int num = getScore(nums, start + 1, end - 1);
selectLeft = nums[start] + min(getScore(nums, start + 2, end), num);
selectRight = nums[end] + min(num, getScore(nums, start, end - 2));
}
return max(selectLeft, selectRight);
}
bool PredictTheWinner(int[] nums) {
int sum = 0;
for (int i : nums) {
sum += i;
int player1 = getScore(nums, 0, nums.size() - 1);
int player2 = sum - player1;
// 如果最终两个玩家的分数相等，那么玩家 1 仍为赢家，所以是大于等于。
return player1 >= player2;
//return getScore(nums, 0, nums.size() - 1) >=0 ;
}
//差值
int getScore(int[] nums, int start, int end) {
if (end == start) {
return nums[start];
}
int selectLeft = nums[start] - getScore(nums, start + 1, end);
int selectRight = nums[end] - getScore(nums, start, end - 1);
return max(selectLeft, selectRight);
}



#### 动态规划：使用二维数组存储差值

    public boolean PredictTheWinner(int[] nums) {
int length = nums.length;
int[][] dp = new int[length][length];
for (int i = 0; i < length; i++) {
dp[i][i] = nums[i];
}
for (int i = length - 2; i >= 0; i--) {
for (int j = i + 1; j < length; j++) {
//j = i +1 因此可以优化为一维数组,下标位置相同才有值，据此推导其他的值
//Math.max(nums[i] - dp[j][j], nums[j] - dp[j - 1][j - 1]);
dp[i][j] = Math.max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1]);
}
}
return dp[0][length - 1] >= 0;
}


## 省份数量

### 解题思路与代码

#### 解法一：深度优先

  public int findCircleNum(int[][] isConnected) {
int provinces = isConnected.length;
boolean[] visited = new boolean[provinces];
int circles = 0;
for (int i = 0; i < provinces; i++) {
if (!visited[i]) {
dfs(isConnected, visited, provinces, i);
circles++;
}
}
return circles;
}
public void dfs(int[][] isConnected, boolean[] visited, int provinces, int i) {
for (int j = 0; j < provinces; j++) {
if (isConnected[i][j] == 1 && !visited[j]) {
visited[j] = true;
dfs(isConnected, visited, provinces, j);
}
}
}


#### 解法二：广度优先

    public int bfs(int[][] isConnected) {
int provinces = isConnected.length;
boolean[] visited = new boolean[provinces];
int circles = 0;
for (int i = 0; i < provinces; i++) {
if (!visited[i]) {
queue.offer(i);
while (!queue.isEmpty()) {
int j = queue.poll();
visited[j] = true;
for (int k = 0; k < provinces; k++) {
if (isConnected[j][k] == 1 && !visited[k]) {
queue.offer(k);
}
}
}
circles++;
}
}
return circles;
}


#### 解法三：并查集

    static int mergeFind(int[][] isConnected){
int provinces = isConnected.length;
int[] level = new int[provinces];
for (int i = 0; i < provinces; i++) {
level[i] = 1;
}
for (int i = 0; i < provinces; i++) {
for (int j = i + 1; j < provinces; j++) {
if (isConnected[i][j] == 1) {
}
}
}
int count = 0;
for (int i = 0; i < provinces; i++) {
count++;
}
}
return count;
}
static int find(int x, int[] arr) {
if(arr[x] == x)
return x;
else
return arr[x];
}
static void merge(int x, int y,int[] arr,int[] level) {
int i = find(x,arr);
int j = find(y,arr);
if(i == j){
return;
}
if(level[i] <= level[j]){
arr[i] = j;
}else{
arr[j] = i;
}
//深度加1
level[j]++;
}



## 三角形的最大周长

### 解题思路与代码

#### 贪心算法：

n < (n-1) + (n-2)，如果不成立，意味着该数组中不可能有另外两个值之和大于n，此时将n左移，重新计算

 public int largestPerimeter(int[] A) {
Arrays.sort(A);
for (int i = A.length - 1; i >= 2; --i) {
if (A[i - 2] + A[i - 1] > A[i]) {
return A[i - 2] + A[i - 1] + A[i];
}
}
return 0;
}


|
1月前
|

44 1
|
30天前
|

41 1
|
27天前
|

42 1
|
20天前
|

【8月更文挑战第30天】设计模式是解决软件开发中特定问题的可重用方案。其中，策略模式是一种常用的行为型模式，允许在运行时选择算法行为。它通过定义一系列可互换的算法来封装具体的实现，使算法的变化与客户端分离。例如，在电商系统中，可以通过定义 DiscountStrategy 接口和多种折扣策略类（如 FidelityDiscount、BulkDiscount 和 NoDiscount），在运行时动态切换不同的折扣逻辑。这样，ShoppingCart 类无需关心具体折扣计算细节，只需设置不同的策略即可实现灵活的价格计算，符合开闭原则并提高代码的可维护性和扩展性。
36 2
|
28天前
|

java系列之~~网络通信安全 非对称加密算法的介绍说明

35 4
|
1月前
|

11 0
|
1月前
|

29 1
|
1月前
|

LeetCode经典算法题：井字游戏+优势洗牌+Dota2参议院java解法
LeetCode经典算法题：井字游戏+优势洗牌+Dota2参议院java解法
37 1
|
29天前
|

【高手进阶】Java排序算法：从零到精通——揭秘冒泡、快速、归并排序的原理与实战应用，让你的代码效率飙升！
【8月更文挑战第21天】Java排序算法是编程基础的重要部分，在算法设计与分析及实际开发中不可或缺。本文介绍内部排序算法，包括简单的冒泡排序及其逐步优化至高效的快速排序和稳定的归并排序，并提供了每种算法的Java实现示例。此外，还探讨了排序算法在电子商务、搜索引擎和数据分析等领域的广泛应用，帮助读者更好地理解和应用这些算法。
19 0
|
1月前
|

HanLP — HMM隐马尔可夫模型 -- 维特比(Viterbi)算法 --示例代码 - Java
HanLP — HMM隐马尔可夫模型 -- 维特比(Viterbi)算法 --示例代码 - Java
28 0