程序员老鬼

破产套路已经从三件套升到了七件套。。

刚刷到这个“中产破产七件套”,哈哈,这哪是七件套,这是打工人财务系统的连环炸弹。

以前说三件套就够吓人了,现在直接升级:一边脑子一热出去创业,钱还没赚着,房贷先按月敲门;家里一个人全职带娃,收入少一半,开销一点没少;孩子这边又开始卷班、卷学校、卷才艺,钱包跟着一起陪跑。

Image

更要命的是,很多人还觉得自己不能落后。别人买啥我也买,别人投啥我也跟,朋友圈看着体面,账单看着要命。身体也不管,熬夜硬扛,体检能拖就拖,真出问题才发现,健康才是最贵的那张账单。

这事最扎心的地方就是,它不是一下子把人打趴下的,是每一步看着都“好像有道理”,凑一块就把家底磨没了。

面试题:反转单词前缀

word = "abcdefd", ch = 'd',结果不是把整个字符串反过来,而是只反转第一个 d 之前这一截。

也就是:

abcdefd
   ^

只动 abcd,后面的 efd 原样放着,最后变成:

dcbaefd

这题叫“反转单词前缀”,看着像字符串小题,其实最容易写乱的是边界。尤其是 ch 不存在的时候,别手欠去截字符串,直接返回原字符串就行。

我一般不太喜欢一上来就 substring + reverse + substring 拼三段。不是不能写,是这种写法看着省事,边界多了就容易藏小坑。字符串题,能在字符数组里原地处理,就别搞太多中间对象。

思路很直接。

先从左往右找 ch 第一次出现的位置。

找不到,返回原来的 word。

找到了,比如位置是 idx,那就用两个指针:

left = 0
right = idx

然后交换 left 和 right 指向的字符,交换完之后 left++,right--,直到两个指针碰头。

代码可以这么写:

classSolution{
public String reversePrefix(String word, char ch){
if (word == null || word.length() <= 1) {
return word;
        }

char[] chars = word.toCharArray();

int hit = -1;
for (int i = 0; i < chars.length; i++) {
if (chars[i] == ch) {
                hit = i;
break;
            }
        }

if (hit == -1) {
return word;
        }

int left = 0;
int right = hit;

while (left < right) {
char tmp = chars[left];
            chars[left] = chars[right];
            chars[right] = tmp;

            left++;
            right--;
        }

returnnew String(chars);
    }
}

这里有几个点别忽略。

第一个,找的是第一次出现的位置。不是最后一次,也不是所有 ch 都要处理。

比如:

word = "abccdef"
ch = 'c'

第一个 c 的下标是 2,只反转 "abc",结果是:

cbacdef

后面的那个 c 不管。

第二个,ch 在第一个位置时,其实反转前缀长度就是 1,结果不变。

word = "leetcode"
ch = 'l'

返回还是:

leetcode

这不是特殊情况,双指针自然会处理掉,因为 left 和 right 一开始都是 0,循环根本不会进。

第三个,ch 不存在。

word = "abcd"
ch = 'z'

直接返回:

abcd

这个判断一定要放在反转前面。

如果想写得再短一点,也可以用 indexOf 找位置:

classSolution{
public String reversePrefix(String word, char ch){
int end = word.indexOf(ch);
if (end < 0) {
return word;
        }

char[] buf = word.toCharArray();
for (int l = 0, r = end; l < r; l++, r--) {
char t = buf[l];
            buf[l] = buf[r];
            buf[r] = t;
        }

returnnew String(buf);
    }
}

我更偏向第二版,代码短一点,也不绕。

复杂度没什么花活。找字符最多扫一遍,反转前缀最多再扫一段,所以时间复杂度是 O(n)。字符数组占了一份额外空间,空间复杂度是 O(n)。

这题别想复杂了。

它考的不是反转字符串本身,而是你能不能把“只反转第一个目标字符之前的前缀”这个范围卡准。范围一错,后面代码写得再漂亮也没用。