LeetCode 之 JavaScript 解答第344題 —— 反轉字符串（Reverse Str

bbbbbb 發布于2019-08-23 17:03 / 1636人閱讀

摘要：小鹿題目反轉字符串編寫一個函數，其作用是將輸入的字符串反轉過來。輸入字符串以字符數組的形式給出。如果為奇數，當兩個指針相等時，反轉完畢。測試用例空字符串。奇數個數的字符串。長度為的字符串。考查內容對字符串的基本操作。

Time：2019/4/18
Title: Reverse String
Difficulty: Easy
Author: 小鹿

題目：Reverse String(反轉字符串)

Write a function that reverses a string. The input string is given as an array of characters char[].

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

You may assume all the characters consist of printable ascii characters.

編寫一個函數，其作用是將輸入的字符串反轉過來。輸入字符串以字符數組 char[] 的形式給出。

不要給另外的數組分配額外的空間，你必須原地修改輸入數組、使用 O(1) 的額外空間解決這一問題。

你可以假設數組中的所有字符都是 ASCII 碼表中的可打印字符。

Example 1:

Input: ["h","e","l","l","o"]
Output: ["o","l","l","e","h"]

Example 2:

Input: ["H","a","n","n","a","h"]
Output: ["h","a","n","n","a","H"]

Slove:

▉ 問題分析

1）反轉字符串，第一想到的就是將字符窗倒序存儲到數組中，可以先輸出，然后再 for 循環加入到數組中。題目中要求需要原地修改輸入數組，那么我們再想一個辦法。

2）數組中的操作，需要原地修改數組，第一想到的就是用到指針，為什么能想到用指針呢？當你做這種數組的也好還是鏈表的也好，做多了之后，下意識的給出解決方法然后去看看可不可行。

▉ 算法思路

通過以上分析，得出兩種方法：

字符串反轉法

雙指針法

字符串反轉法：

1）字符串反轉法很簡單了，按照我們正常的思路走就可以了，首先輸出數組中的字符拼接成字符串。

2）然后從字符串尾部開始遍歷，正向輸入數組。

雙指針法：

1）定義兩個指針，分別指向字符串頭部和尾部。

2）兩個指針指向的值進行交換。

3）注意終止條件。

如果為偶數，當頭指針 - 1 等于尾指針時，反轉完畢。

如果為奇數，當兩個指針相等時，反轉完畢。

▉ 測試用例

1）空字符串。

2）偶數個數的字符串。

3）奇數個數的字符串。

4）長度為 1 的字符串。

▉ 雙指針法

var reverseString = function(s) {
    //判斷輸入的字符串是否為空
   if(s.length ==0) return s;
    //定義兩個指針
    let low = 0;
    let high = s.length - 1;
    // 循環反轉字符
    while(true){
        // 分為奇數/偶數兩種可能
        if(low === high || high + 1 === low) break;
        let temp = s[low];
        s[low] = s[high];
        s[high] = temp;
        low++;
        high--;
    }
    // 返回反轉好的字符串
    return s;
};

▉ 字符串反轉法

var reverseString = function(s) {
    //判斷輸入的字符串是否為空
    if(s.length ==0) return s;
    let str = "";
    // 輸出字符串
    for(let i in s){
        str = str+`${s[i]}`;
    }
    // 反轉字符串輸入
    for(let i = s.length - 1,j = 0;i >= 0;i--,j++){
        s[j] = str.charAt(i);
    }
    //返回反轉好的字符串
    return s;
};

▉ 性能分析

字符串反轉法

時間復雜度：O（n）。遍歷整個數組，時間復雜度為 O（n）。

空間復雜度：O（n）。輸出數組需要額外的存儲空間，如果用數組存儲，需要開辟大小為 n 大小的內存空間。如果需要數組輸出拼接字符串，空間復雜度為 O(1) 了。

雙指針法：

時間復雜度：O（n）。需要遍歷 n/2 的數據，時間復雜度為 O(n)。

空間復雜度：O（n）。只需常量級別的內存空間，空間復雜度為O（1）。

▉ 考查內容

1）對字符串的基本操作。

2）數組的基本操作。

歡迎一起加入到 LeetCode 開源 Github 倉庫，可以向 me 提交您其他語言的代碼。在倉庫上堅持和小伙伴們一起打卡，共同完善我們的開源小倉庫！
Github：https://github.com/luxiangqia...
歡迎關注我個人公眾號：「一個不甘平凡的碼農」，記錄了自己一路自學編程的故事。

云服務器 GPU云服務器反轉字符串字符串反轉 php 將字符串反轉 js字符反轉

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/103729.html

LeetCode 之 JavaScript 解答第206題 —— 反轉鏈表（Reverse Link

摘要：算法思路兩種方法一般反轉遞歸法一般解決定義三個指針，分別為，存儲當前結點，指向反轉好的結點的頭結點，存儲下一結點信息。遞歸法重點分析先確定終止條件當下一結點為時，返回當前節點判斷當前的鏈表是否為遞歸找到尾結點，將其存儲為頭結點。 Time：2019/4/23Title: Reverse Linked ListDifficulty: EasyAuthor: 小鹿題目：Reverse...

zhangfaliang 2019-08-23 17:12 評論0 收藏0
LeetCode 之 JavaScript 解答第151題 —— 反轉字符串中的單詞

摘要：小鹿題目翻轉字符串里的單詞給定一個字符串，逐個翻轉字符串中的每個單詞。說明無空格字符構成一個單詞。遇到空格之后，將單詞進行倒序拼接。消除尾部的空格。測試用例空字符串。中間空格大于的字符串。 Time：2019/4/20Title: Reverse Words In a StringDifficulty: MidumnAuthor: 小鹿題目：Reverse Words In a ...

betacat 2019-08-23 17:05 評論0 收藏0
Leetcode 344：Reverse String 反轉字符串（python、java）

摘要：反轉字符串公眾號愛寫編寫一個函數，其作用是將輸入的字符串反轉過來。輸入字符串以字符數組的形式給出。解題思路第一個字符與最后一個交換位置，繼而第二個與倒數第二個交換位置，一直交換到到中位數結束。持續交換它們所指向的元素，直到這兩個指針相遇。 Leetcode 344：Reverse String 反轉字符串公眾號：愛寫bugWrite a function that reverses ...

Ajian 2019-07-31 11:24 評論0 收藏0
Leetcode 344：Reverse String 反轉字符串（python、java）

摘要：反轉字符串公眾號愛寫編寫一個函數，其作用是將輸入的字符串反轉過來。輸入字符串以字符數組的形式給出。解題思路第一個字符與最后一個交換位置，繼而第二個與倒數第二個交換位置，一直交換到到中位數結束。持續交換它們所指向的元素，直到這兩個指針相遇。 Leetcode 344：Reverse String 反轉字符串公眾號：愛寫bugWrite a function that reverses ...

duan199226 2019-08-16 18:25 評論0 收藏0
JS算法題之leetcode(1~10)

摘要：先去空白，去掉空白之后取第一個字符，判斷正負符號，若是英文直接返回，若數字則不取。回文數題目描述判斷一個整數是否是回文數。回文數是指正序從左向右和倒序從右向左讀都是一樣的整數。 JS算法題之leetcode(1~10) 前言一直以來，前端開發的知識儲備在數據結構以及算法層面是有所暫缺的，可能歸根于我們的前端開發的業務性質，但是我認為任何的編程崗位都離不開數據結構以及算法。因此，我作為...

SoapEye 2019-08-26 10:44 評論0 收藏0