iT邦幫忙

2026 iThome 鐵人賽

DAY 4
0
Software Development

30天刷完leetcoode75系列 第 4

C++ 演算法練習 Day4|283, 392, 11 題解與思路分享

  • 分享至 

  • xImage
  •  

https://ithelp.ithome.com.tw/upload/images/20260918/20184265cIJnbNRkqH.png

題目解析:給一個整數陣列,題目要求把所有的0都移到陣列的最後面,同時保持其他非零元素原本的相對順序,而且要求在原地(in-place)修改陣列,不能複製一份新的陣列
解題思路:設一個指標i從0開始,然後用j去跑遍整個陣列,只要nums[j]不是0,就把nums[j]和nums[i]交換,交換完i再往後移一格,這樣跑完一輪之後,所有非零的元素就會被依序集中到陣列前面,剩下的位置自然就會是0

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int i = 0;

        for(int j=0; j<nums.size(); j++){
            if(nums[j] != 0){
                swap(nums[j], nums[i]);
                i++;
            }
        }      
    }
};

https://ithelp.ithome.com.tw/upload/images/20260918/20184265P8FcQAQqvw.png

題目解析:給兩個字串s跟t,題目要求判斷s是不是t的子序列,也就是s裡面的字元能不能依照原本的順序,在t裡面依序找到,中間可以跳過其他字元
解題思路:設一個q紀錄目前搜尋到t的哪個位置,然後跑第一層迴圈去遍歷s的每個字元,內層再從q開始往後找t,只要找到相同的字元,就把q更新成該位置+1,並且讓ans加1,最後判斷ans有沒有等於s的長度,如果相等代表s裡面的每個字元都有依序在t裡面找到,回傳1,反之則回傳0

class Solution {
public:
    bool isSubsequence(string s, string t) {
        int q = 0, ans = 0;
        for(int i=0; i<s.size(); i++){
            for(int j=q; j<t.size(); j++){
                if(s[i] == t[j]){
                    q = j + 1;
                    ans++;
                    break;
                }
            }
        }

        if(ans == s.size()) return 1;
        return 0;
    }
};

https://ithelp.ithome.com.tw/upload/images/20260918/20184265XweRyijC1D.png

題目解析:給一個陣列height,每個元素代表一條垂直線的高度,題目要求從裡面選兩條線,跟x軸一起組成一個容器,求這個容器能裝的最大水量
解題思路:設兩個指標i跟j,分別指向陣列的最前面跟最後面,然後開始跑迴圈,每次都用(j-i)乘上兩條線裡面比較矮的那條,去更新ans,接著判斷height[i]跟height[j]誰比較矮,比較矮的那邊就往中間移動,因為容器的水量是取決於較矮的那條線,移動較高的那邊不可能讓水量變大,所以只移動較矮的那邊才有機會找到更大的面積,直到i跟j相遇為止

class Solution {
public:
    int maxArea(vector<int>& height) {
        int ans = 0;
        int i = 0, j = height.size()-1;
        while(i != j){
            ans = max(ans, (j-i)*min(height[i], height[j]));
            if(height[i] <= height[j]) i++;
            else j--;
        }

        return ans;
    }
};

上一篇
C++ 演算法練習 Day3|238, 334, 443 題解與思路分享
下一篇
C++ 演算法練習 Day5|1679, 643, 1456 題解與思路分享
系列文
30天刷完leetcoode756
圖片
  熱門推薦
圖片
{{ item.channelVendor }} | {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言