开心五月激情看看,美女被内射,日韩三级片网站,黄色视频免费精品,每日更新欧美韩国,欧美精品一区二区三区主播视频,国产一级片免费播放,91视频久久

算法的重要性，我就不多說了吧，想去大廠，就必須要經(jīng)過基礎(chǔ)知識和業(yè)務(wù)邏輯面試+算法面試。所以，為了提高大家的算法能力，這個公眾號后續(xù)每天帶大家做一道算法題，題目就從LeetCode上面選！

今天和大家聊的問題叫做 翻轉(zhuǎn)游戲II，我們先來看題面：

https://leetcode-cn.com/problems/flip-game-ii/

You are playing the following Flip Game with your friend: Given a string that contains only these two characters: + and -, you and your friend take turns to flip two consecutive "++" into "--". The game ends when a person can no longer make a move and therefore the other person will be the winner.

Write a function to determine if the starting player can guarantee a win.

你和朋友玩一個叫做「翻轉(zhuǎn)游戲」的游戲，游戲規(guī)則：給定一個只有 + 和 - 的字符串。你和朋友輪流將連續(xù) 的兩個 "++" 反轉(zhuǎn)成 "--"。當(dāng)一方無法進(jìn)行有效的翻轉(zhuǎn)時便意味著游戲結(jié)束，則另一方獲勝。

請你寫出一個函數(shù)來判定起始玩家是否存在必勝的方案。

示例

輸入: s = "++++"
輸出: true
解析: 起始玩家可將中間的 "++" 翻轉(zhuǎn)變?yōu)?"+--+" 從而得勝。
延伸：
請推導(dǎo)你算法的時間復(fù)雜度。

解題

https://www.cnblogs.com/grandyang/p/5226206.html

這道題是之前那道 Flip Game 的拓展，讓我們判斷先手的玩家是否能贏，可以窮舉所有的情況，用回溯法來解題，思路跟上面那題類似，也是從第二個字母開始遍歷整個字符串，如果當(dāng)前字母和之前那個字母都是+，那么遞歸調(diào)用將這兩個位置變?yōu)?-的字符串，如果返回 false，說明當(dāng)前玩家可以贏，結(jié)束循環(huán)返回 false。

這里同時貼上熱心網(wǎng)友 iffalse 的解釋，這道題不是問 “1p是否會怎么選都會贏”，而是 “如果1p每次都選特別的兩個+，最終他會不會贏”。所以 canWin 這個函數(shù)的意思是 “在當(dāng)前這種狀態(tài)下，至少有一種選法，能夠讓他贏”。而 (!canWin) 的意思就變成了 “在當(dāng)前這種狀態(tài)下，無論怎么選，都不能贏”。

所以 1p 要看的是，是否存在這樣一種情況，無論 2p 怎么選，都不會贏。所以只要有一個 (!canWin)，1p 就可以確定他會贏。這道題從博弈論的角度會更好理解。每個 player 都想讓自己贏，所以每輪他們不會隨機選+。每一輪的 player 會選能夠讓對手輸?shù)?。如果無論如何都選不到讓對手輸?shù)?，那么只能是當(dāng)前的 player 輸了，參見代碼如下：

class Solution {
public:
    bool canWin(string s) {
        for (int i = 1; i < s.size(); ++i) {
            if (s[i] == '+' && s[i - 1] == '+' && !canWin(s.substr(0, i - 1) + "--" + s.substr(i + 1))) {
                return true;
            }
        }
        return false;
    }
};