企业网站建设的征求意见,镇江百度seo,建设部网站造价注册,免费申请自己的网站一、捡石头 292 思路就是#xff1a;
谁面对4块石头的时候#xff0c;谁就输#xff08;因为每次就是1-3块石头#xff0c;如果剩下4块石头#xff0c;你怎么拿#xff0c;我都能把剩下的拿走#xff0c;所以你就要想尽办法让对面面对4块石头的倍数#xff0c;
比如有…一、捡石头 292 思路就是
谁面对4块石头的时候谁就输因为每次就是1-3块石头如果剩下4块石头你怎么拿我都能把剩下的拿走所以你就要想尽办法让对面面对4块石头的倍数
比如有10块石头你想办法让对方面对4的倍数10%42也就是你先手拿走2块比如有13块石头你想办法让对方面对4的倍数13%41也就是你先手拿走1块
但是假如你面对了4的倍数你铁定输因为对方也是聪明人。
于是先手能不能赢就看
class Solution {public boolean canWinNim(int n) {return n % 4 ! 0 ;}
}
二、捡石头 Nim 游戏 II 1908
int nums [ 1, 5, 8, 6 ]
我和你进行捡石头游戏假如有4堆石头 第一堆有1个石头 第二堆有5个石头 第三堆有8个石头 第四堆有6个石头
每次只能从最前面或者最后面取1堆石头能否保证先手一定能赢 分析如下 public static void main(String[] args) {int[] nums {1, 5, 8, 6};int[] nums2 {3, 9, 1, 2};int[] nums3 {1, 1, 1, 1};int[] nums4 {2, 5, 1, 3, 7, 8, 9, 11};int[] nums5 {1000,0,10000,2,1};int[] nums6 {10, 8, 20, 15, 3};int[] nums7 {1, 1, 1, 10};// int[] nums0 {5, 8, 6};
// System.out.println(firstHandCanScore(nums0));System.out.println(firstHandCanScore(nums));System.out.println(firstHandCanScore(nums2));System.out.println(firstHandCanScore(nums3));System.out.println(firstHandCanScore(nums4));System.out.println(firstHandCanScore(nums5));}private static boolean firstHandCanScore(int[] nums) {WinScoreData winScoreData process(nums, 0, nums.length - 1);System.out.println(winScoreData.winScore);return winScoreData.winScore 0;}private static WinScoreData process(int[] nums, int fromIndex, int toIndex) {if (fromIndex toIndex) {return new WinScoreData(nums, fromIndex, toIndex, nums[fromIndex]);}int startLeft nums[fromIndex];WinScoreData chooseLeftWinScore process(nums, fromIndex 1, toIndex);int leftWinScore startLeft - chooseLeftWinScore.winScore; // 选左边之后的赢面int startRight nums[toIndex];WinScoreData chooseRightWinScore process(nums, fromIndex, toIndex - 1);int rightWinScore startRight - chooseRightWinScore.winScore; // 选右边之后的赢面int winScore Math.max(leftWinScore, rightWinScore);return new WinScoreData(nums, fromIndex, toIndex, winScore);}AllArgsConstructorpublic static class WinScoreData {private int[] nums;private int fromIndex;private int toIndex;private int winScore;}
