Leetcode 949. Largest Time for Given Digits - 《YoungZHAO的算法学习之旅》

949. Largest Time for Given Digits

思路

其实这个思路挺简单的，就搜索全排列，然后找到合法的最大值即可。
但是自己写出来的代码和别人写出来的代码还是有差别的，所以还是记录下。

代码

我的代码

class Solution {
public:
  vector<bool> st;
  int path;
  int ans = -1;
  void dfs(vector<int> &arr, int depth) {
      if (depth == 4) {
          ans = max(ans, path);
          return;
      }
      for (int i = 0; i < 4; i ++) {
          if (st[i]) {
              continue;
          }
          path = path * 10 + arr[i];
          if (depth == 1) {
              if (path >= 24) {
                  path = path / 10;
                  continue;
              }
          }
          if (depth == 3) {
              if (path % 100 >= 60) {
                  path = path / 10;
                  continue;
              }
          }
          st[i] = true;
          dfs(arr, depth + 1);
          path = path / 10;
          st[i] = false;
      }
  }
  string largestTimeFromDigits(vector<int>& arr) {
      st = vector<bool>(4, false);
      path = 0;
      dfs(arr, 0);
      if (ans == -1) {
          return "";
      }
      string hour = to_string(ans / 100);
      if (hour.size() < 2) {
          hour = "0" + hour;
      }
      string minute = to_string(ans % 100);
      if (minute.size() < 2) {
          minute = "0" + minute;
      }
      return hour + ":" + minute;
  }
};

别人的代码
这个地方要注意，必须要排序，next_permutation返回比当前大的一个排列。

另外就是你是用的int，但其实用string也完全OK的。

class Solution {
public:
  string largestTimeFromDigits(vector<int>& arr) {
      sort(arr.begin(), arr.end());
      string res;
      do {
          string h = to_string(arr[0]) + to_string(arr[1]);
          string m = to_string(arr[2]) + to_string(arr[3]);
          if (h <= "23" && m <= "59") {
              string temp = h + ":" + m;
              if (res.empty() || res < temp) {
                  res = temp;
              }
          }
      } while(next_permutation(arr.begin(), arr.end()));
      return res;
  }
};