#LeetCode:3. Longest Substring Without Repeating Characters

用 Sliding Window 的方式,用前後兩個 index 去紀錄目前所找到的子字串。

每次往後延伸 Window 時,先檢查前面是否有重複出現過該字母,若有就把頭移到重複出現的該字母前一次出現的 index 的後面一位,如果前一次的 index 已經不在所夾住的子字串中則忽略。接著再將目前往後延伸到的字母所在 index 給記錄下來,以利之後的查找。這樣在每次延伸出來的子字串中找出最長的長度即是答案。

C++(46ms)

/*******************************************************/
/* LeetCode 3. Longest Substring Without Repeating     */
/*             Characters                              */
/* Author: Maplewing [at] knightzone.org               */
/* Version: 2018/05/23                                 */
/*******************************************************/
class Solution {
public:
  int lengthOfLongestSubstring(string s) {
    map<char, int> currentIndexMap;

    int sLength = s.length();
    int maxSubstringLength = 0;
    int head = 0;
    for(int i = 0 ; i < sLength ; ++i){
      if(currentIndexMap.find(s[i]) != currentIndexMap.end()){
        head = max(currentIndexMap[s[i]] + 1, head);
      }

      currentIndexMap[s[i]] = i;
      maxSubstringLength = max(maxSubstringLength, i - head + 1);
    }

    return maxSubstringLength;      
  }
};

#LeetCode:2. Add Two Numbers

將兩個 Linked List 中的數值做相加,並將進位加給下一個 Node 即可。要多加小心指標的操作。

C++(64ms)

/*******************************************************/
/* LeetCode 2. Add Two Numbers                         */
/* Author: Maplewing [at] knightzone.org               */
/* Version: 2018/05/23                                 */
/*******************************************************/
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
  ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    int carry = 0;
    ListNode *head = NULL;
    ListNode *p1 = l1, *p2 = l2, *current = NULL;
    while(p1 != NULL || p2 != NULL){
      int sum = _iterateCurrent(&p1) + _iterateCurrent(&p2) + carry;
      int value = sum % 10;
      carry = sum / 10;

      if(head == NULL){
        head = new ListNode(value);
        current = head;
      }
      else{
        current->next = new ListNode(value);
        current = current->next;
      }
    }

    if(carry > 0) current->next = new ListNode(carry);

    return head;
  }

private:
  int _iterateCurrent(ListNode** p){
    if(*p != NULL){
      int value = (*p)->val;
      *p = (*p)->next;  
      return value;
    }

    return 0;
  }
};

#LeetCode:1. Two Sum

建 Hash 表將所選到之數字 a 所不足的那格 target - a 把自己的 index (i) 紀錄下來,這樣等到該不足之數 target - a 出現的時候可以直接查到與第 i 格湊起來即是答案。

C++(10ms)

/*******************************************************/
/* LeetCode 1. Two Sum                                 */
/* Author: Maplewing [at] knightzone.org               */
/* Version: 2018/05/23                                 */
/*******************************************************/
class Solution {
public:
  vector<int> twoSum(vector<int>& nums, int target) {
    map<int, int> complementMap;
    for(int i = 0 ; i < nums.size() ; ++i){
      auto complement = complementMap.find(nums[i]);
      if(complement != complementMap.end()){
        int result[] = {complement->second, i};
        return vector<int>(result, result + 2);
      }
      complementMap[target - nums[i]] = i;
    }
  }
};

#UVa:10338-Mischievous Children

排列組合的問題。有 n 個字母的總共排列方式是 n! ,而其中某個文字若是有重複 m 個的話則必須將結果除以 m! ,將所有重複的文字的排列數除掉後即是答案。

C++(0.040)

/*******************************************************/
/* UVa 10338 Mischievous Children                      */
/* Author: Maplewing [at] knightzone.org               */
/* Version: 2018/05/21                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
#include <string>
using namespace std;

void makeFactorial(long long int f[], long long int n){
  for(int i = 0 ; i <= n ; ++i){
    if(i == 0 || i == 1){
      f[i] = 1;
      continue;
    }

    f[i] = f[i-1] * i;
  }
}

int main(){
  long long int factorial[25];
  makeFactorial(factorial, 20);

  int caseCount;
  while(scanf("%d", &caseCount) != EOF){
    for(int caseNumber = 1 ; caseNumber <= caseCount ; ++caseNumber){
      string word;
      cin >> word;

      int totalWordCount = word.length();
      long long int result = factorial[totalWordCount];
      int charCount[26] = {0};
      for(int i = 0 ; i < word.length() ; ++i){
        ++charCount[word[i] - 'A'];
      }

      for(int i = 0 ; i < 26 ; ++i){
        result /= factorial[charCount[i]];
      }

      printf("Data set %d: %lld\n", caseNumber, result);
    }
  }

  return 0;
}

#UVa:11723-Numbering Roads

計算有這麼多可以用的數字上,能夠用幾種方式分別所有的道路,如果超過 26 + 1 ( 26 個字母加上不加字母)種的話,就表示不可能。

C++(0.000)

/*******************************************************/
/* UVa 11723 Numbering Roads                           */
/* Author: Maplewing [at] knightzone.org               */
/* Version: 2018/05/20                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;

int main(){
  int N, R;
  int caseNumber = 1;
  while(scanf("%d%d", &N, &R) != EOF &&
        N != 0 && R != 0){
    int group = (int)ceil((double)N / R);

    printf("Case %d: ", caseNumber++);
    if( group > 27 ){
      printf("impossible");
    }
    else{
      printf("%d", group - 1);
    }
    printf("\n");

  }
  return 0;
}

#UVa:11715-Car

利用計算速度的物理公式以及僅知的參數去求出答案即可。我是用其中的兩個公式再去推導的:
\(
\begin{align}
v & = u + a \times t \newline
S & = u \times t + \frac{1}{2} \times a \times t^{2}
\end{align}
\)

關鍵字:等加速度直線運動

C++(0.000)

/*******************************************************/
/* UVa 11715 Car                                       */
/* Author: Maplewing [at] knightzone.org               */
/* Version: 2018/05/18                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;

int main(){
  int type;
  int caseNumber = 1;
  while(scanf("%d", &type) != EOF && type != 0){
    printf("Case %d: ", caseNumber++);
    double u, v, t, a, s;
    switch(type){
      case 1:
        scanf("%lf%lf%lf", &u, &v, &t);
        a = (v - u) / t;
        s = (u + v) * t / 2;
        printf("%.3lf %.3lf", s, a);
        break;
      case 2:
        scanf("%lf%lf%lf", &u, &v, &a);
        t = (v - u) / a;
        s = (u + v) * t / 2;
        printf("%.3lf %.3lf", s, t);
        break;
      case 3:
        scanf("%lf%lf%lf", &u, &a, &s);
        v = sqrt(u * u + 2 * a * s);
        t = (v - u) / a;
        printf("%.3lf %.3lf", v, t);
        break;
      case 4:
        scanf("%lf%lf%lf", &v, &a, &s);
        u = sqrt(v * v - 2 * a * s);
        t = (v - u) / a;
        printf("%.3lf %.3lf", u, t);
        break;
    }
    printf("\n");
  }

  return 0;
}

#UVa:507-Jill Rides Again

找出最大連續和即可。從頭開始當作範圍的頭去加總,遇到總和變成負數之後將加總歸零再從此處當作範圍的頭開始加總,因為從此處歸零開始選會比包含前面加總的結果更好。整段做完的最後看哪段範圍總和最大、範圍最大且出現在比較前面即是答案。

C++(0.060)

/*******************************************************/
/* UVa 507 Jill Rides Again                            */
/* Author: Maplewing [at] knightzone.org               */
/* Version: 2018/05/17                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

int main(){
  int b;
  while(scanf("%d", &b) != EOF){
    for(int r = 1 ; r <= b ; ++r){
      int s;
      scanf("%d", &s);

      vector<int> routes;
      for(int i = 0 ; i < s - 1 ; ++i){
        int n;
        scanf("%d", &n);
        routes.push_back(n);
      }

      int i = -1, sum = 0;
      int maxI = -1, maxJ = -1, maxSum = 0;
      for(int j = 0 ; j < s - 1 ; ++j){
        sum += routes[j];
        if(i == -1) i = j;

        if(sum > maxSum || (sum == maxSum && j - i > maxJ - maxI)){
          maxSum = sum;
          maxI = i;
          maxJ = j;
        }

        if(sum < 0){
          sum = 0;
          i = -1;
        }
      }

      if(maxSum <= 0){
        printf("Route %d has no nice parts\n", r);
      }
      else{
        printf("The nicest part of route %d is between stops %d and %d\n", r, maxI+1, maxJ+2);
      }
    }
  }
  return 0;
}

#UVa:1197-The Suspects

利用 DFS 檢查從 0 號學生開始可以連到多少學生即可得解。建圖時,每個群組可以將群組裡面的其他學生全部連到群組中的特定學生(例如:第一個學生)即可。

C++(0.000)

/*******************************************************/
/* UVa 1197 The Suspects                               */
/* Author: Maplewing [at] knightzone.org               */
/* Version: 2018/05/17                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

int getDFSNodeCount(const vector<vector<int>> &graph, vector<bool> &isVisited, int startPoint){
  isVisited[startPoint] = true;

  int count = 1;
  for(int i = 0 ; i < graph[startPoint].size() ; ++i){
    if(!isVisited[graph[startPoint][i]]){
      count += getDFSNodeCount(graph, isVisited, graph[startPoint][i]);
    }
  }

  return count;
}

int main(){
  int n, m;
  while(scanf("%d%d", &n, &m) != EOF &&
        (n != 0 || m != 0)){

    vector<vector<int>> studentConnectGraph(n, vector<int>());
    for(int i = 0 ; i < m ; ++i){
      int k;
      scanf("%d", &k);

      int rootStudent = 0;
      for(int j = 0 ; j < k ; ++j){
        int currentStudent;
        scanf("%d", &currentStudent);

        if(j == 0){
          rootStudent = currentStudent;
          continue;
        }
        studentConnectGraph[rootStudent].push_back(currentStudent);
        studentConnectGraph[currentStudent].push_back(rootStudent);
        rootStudent = currentStudent;
      }
    }

    vector<bool> isVisited(n, false);
    printf("%d\n", getDFSNodeCount(studentConnectGraph, isVisited, 0));  
  }
  return 0;
}

#UVa:1185-Big Number

對數字取以 10 為底的 log 即可得其位數,故要求 n 階層的位數有多少為:
\(
\begin{align}
GetDigit(n!) & = \lfloor {\log (n!)} \rfloor + 1 \newline
& = \lfloor {\log (n \times (n-1) \times (n-2) \times \dots 1)} \rfloor + 1 \newline
& = \lfloor {\log n} + {\log (n-1)} + {\log (n-2)} + \dots + {\log 1} \rfloor + 1 \newline
\end{align}
\)

透過公式了解可以對各項取 Log 再加總後,就利用 DP 解決即可。

C++(0.330)

/*******************************************************/
/* UVa 1185 Big Number                                 */
/* Author: Maplewing [at] knightzone.org               */
/* Version: 2018/05/17                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;

int main(){
  int caseCount;
  scanf("%d", &caseCount);

  double logValue[10000005] = {0};
  int maxNumber = 0;
  for(int caseNumber = 0 ; caseNumber < caseCount ; ++caseNumber){
    int n;
    scanf("%d", &n);

    if( n > maxNumber ){
      for(int i = maxNumber + 1 ; i <= n ; ++i ){
        logValue[i] = logValue[i-1] + log10(i);
      }
    }

    printf("%d\n", (int)logValue[n] + 1);
  }

  return 0;
}

#UVa:1121-Subsequence

找出最短長度的數列可以比指定的數 S 大。

利用記住連續數列的最前端和最後端,慢慢從後面增長。如果總和超過了指定數 S ,則從最前端縮回來,直到數列總和比 S 小為止。

P.S. 記得處理總和沒辦法超過 S 的狀況。

C++(0.020)

/*******************************************************/
/* UVa 1121 Subsequence                                */
/* Author: Maplewing [at] knightzone.org               */
/* Version: 2018/05/16                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
using namespace std;

int main(){
  int N, S;
  while(scanf("%d%d", &N, &S) != EOF){
    vector<int> sequence;
    for(int i = 0 ; i < N ; ++i){
      int number;
      scanf("%d", &number);
      sequence.push_back(number);
    }

    int sum = 0, minLength = N+1, front = 0;
    for(int i = 0 ; i < N ; ++i ){
      sum += sequence[i];

      while(sum >= S){
        minLength = min(minLength, i - front + 1);
        sum -= sequence[front];
        ++front;
      }
    }

    printf("%d\n", (minLength == N+1)? 0 : minLength);
  } 
  return 0;
}
共 40 頁1 2 3 40